/sys/doc/ Documentation archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

list-based queues

A list-based implementation of fifo queues used in functional
programming may be of interest to Limbo programmers.  The approach
extends trivially to output-restricted deques.  The inventor is
Burton and a reference is Paulson's MLWP, 1st ed., 238-240.

queue: adt {
	h: list of string; 
	t: list of string;
	put: fn(q: self ref queue, s: string);
	remove: fn(q: self ref queue) : string;
	new: fn(): ref queue;
};

queue.new() : ref queue
{
	q := queue(nil, nil);
	return ref q;
}

queue.put(q: self ref queue, s: string)
{
	q.t = s :: q.t;
	if(q.h == nil){
		q.h = revlist(q.t);
		q.t = nil;
	}
}

queue.remove(q: self ref queue) : string
{
	s := "";
	if(q.h == nil){
		q.h = revlist(q.t);
		q.t = nil;
	}
	if(q.h != nil){
		s = hd q.h;
		q.h = tl q.h;
	}
	return s;
}

# or inline
revlist(ls: list of string) : list of string
{
	rs: list of string;
	while(ls != nil){
		rs = hd ls :: rs;
		ls = tl ls;
	}
	return rs;
}