# extqueue.b## Written in 2018 by David Boddie <david@boddie.org.uk>## To the extent possible under law, the author(s) have dedicated all copyright# and related and neighboring rights to this software to the public domain# worldwide. This software is distributed without any warranty.## You should have received a copy of the CC0 Public Domain Dedication along with# this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.# An extensible queue container.implement ExtQueueTest;# Import modules to be used and declare any instances that will be accessed# globally.include "sys.m";include "draw.m";include "string.m";ExtQueueTest: module{ init: fn(ctxt: ref Draw->Context, args: list of string);};ExtQueue: adt[T] { a: array of T; front, back: int; original_size: int; full: int; new: fn(size: int): ref ExtQueue[T]; count: fn(eq: self ref ExtQueue[T]): int; extend: fn(eq: self ref ExtQueue[T], size: int); push: fn(eq: self ref ExtQueue[T], value: T); pop: fn(eq: self ref ExtQueue[T]): T;};init(ctxt: ref Draw->Context, args: list of string){ # Load instances of modules, one local to init, the other global. sys := load Sys Sys->PATH; str := load String String->PATH; s := "The quick brown fox jumps over the lazy dog."; earray := ExtQueue[string].new(4); while (s != nil) { word: string; (word, s) = str->splitstrl(s, " "); sys->print("Push: %s ", word); earray.push(word); sys->print("front=%d, back=%d, size=%d, count=%d\n", earray.front, earray.back, len earray.a, earray.count()); if (len s > 0) s = s[1:]; } while (earray.count() != 0) { value := earray.pop(); sys->print("Value: %s\n", value); } sys->print("front=%d, back=%d, size=%d, count=%d\n", earray.front, earray.back, len earray.a, earray.count());}ExtQueue[T].new(size: int): ref ExtQueue[T]{ a := array[size] of T; return ref ExtQueue[T](a, 0, 0, size, 0);}ExtQueue[T].count(eq: self ref ExtQueue[T]): int{ if (eq.full) return len eq.a; l := eq.back - eq.front; if (l < 0) l = len eq.a + l; return l;}ExtQueue[T].extend(eq: self ref ExtQueue[T], size: int){ na := array[size] of T; i := eq.front; j := 0; do { na[j] = eq.a[i]; i = (i + 1) % (len eq.a); j++; } while (i != eq.front); eq.front = 0; eq.back = j; eq.a = na; eq.full = 0;}ExtQueue[T].push(eq: self ref ExtQueue[T], value: T){ if (eq.full) eq.extend(len eq.a + eq.original_size); eq.a[eq.back] = value; # Update the back of the queue, wrapping round to the start of the array # if necessary. eq.back = (eq.back + 1) % (len eq.a); if (eq.front == eq.back) eq.full = 1;}ExtQueue[T].pop(eq: self ref ExtQueue[T]): T{ # Return nil for an empty queue. if (eq.front == eq.back) return nil; item := eq.a[eq.front]; # Update the front of the queue, wrapping round to the start of the array # if necessary. eq.front = (eq.front + 1) % (len eq.a); if (eq.front == eq.back) eq.full = 0; return item;}
# extqueue.b
#
# Written in 2018 by David Boddie <david@boddie.org.uk>
#
# To the extent possible under law, the author(s) have dedicated all copyright
# and related and neighboring rights to this software to the public domain
# worldwide. This software is distributed without any warranty.
#
# You should have received a copy of the CC0 Public Domain Dedication along with
# this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
# An extensible queue container.
implement ExtQueueTest;
# Import modules to be used and declare any instances that will be accessed
# globally.
include "sys.m";
include "draw.m";
include "string.m";
ExtQueueTest: module
{
init: fn(ctxt: ref Draw->Context, args: list of string);
};
ExtQueue: adt[T] {
a: array of T;
front, back: int;
original_size: int;
full: int;
new: fn(size: int): ref ExtQueue[T];
count: fn(eq: self ref ExtQueue[T]): int;
extend: fn(eq: self ref ExtQueue[T], size: int);
push: fn(eq: self ref ExtQueue[T], value: T);
pop: fn(eq: self ref ExtQueue[T]): T;
};
init(ctxt: ref Draw->Context, args: list of string)
{
# Load instances of modules, one local to init, the other global.
sys := load Sys Sys->PATH;
str := load String String->PATH;
s := "The quick brown fox jumps over the lazy dog.";
earray := ExtQueue[string].new(4);
while (s != nil) {
word: string;
(word, s) = str->splitstrl(s, " ");
sys->print("Push: %s ", word);
earray.push(word);
sys->print("front=%d, back=%d, size=%d, count=%d\n", earray.front,
earray.back, len earray.a, earray.count());
if (len s > 0)
s = s[1:];
}
while (earray.count() != 0) {
value := earray.pop();
sys->print("Value: %s\n", value);
}
sys->print("front=%d, back=%d, size=%d, count=%d\n", earray.front,
earray.back, len earray.a, earray.count());
}
ExtQueue[T].new(size: int): ref ExtQueue[T]
{
a := array[size] of T;
return ref ExtQueue[T](a, 0, 0, size, 0);
}
ExtQueue[T].count(eq: self ref ExtQueue[T]): int
{
if (eq.full)
return len eq.a;
l := eq.back - eq.front;
if (l < 0)
l = len eq.a + l;
return l;
}
ExtQueue[T].extend(eq: self ref ExtQueue[T], size: int)
{
na := array[size] of T;
i := eq.front;
j := 0;
do {
na[j] = eq.a[i];
i = (i + 1) % (len eq.a);
j++;
} while (i != eq.front);
eq.front = 0;
eq.back = j;
eq.a = na;
eq.full = 0;
}
ExtQueue[T].push(eq: self ref ExtQueue[T], value: T)
{
if (eq.full)
eq.extend(len eq.a + eq.original_size);
eq.a[eq.back] = value;
# Update the back of the queue, wrapping round to the start of the array
# if necessary.
eq.back = (eq.back + 1) % (len eq.a);
if (eq.front == eq.back)
eq.full = 1;
}
ExtQueue[T].pop(eq: self ref ExtQueue[T]): T
{
# Return nil for an empty queue.
if (eq.front == eq.back)
return nil;
item := eq.a[eq.front];
# Update the front of the queue, wrapping round to the start of the array
# if necessary.
eq.front = (eq.front + 1) % (len eq.a);
if (eq.front == eq.back)
eq.full = 0;
return item;
}