## queue-via-paired-lists.pkg
#
# The Queue api implemented via paired lists.
#
# For bounded queues see:
#
# src/lib/src/bounded-queue-via-paired-lists.pkg#
# For mutable queues see:
#
# src/lib/src/rw-queue.pkg# Compiled by:
# src/lib/std/standard.lib### "I don't know anything about music.
### In my line you don't have to."
###
### -- Elvis Presley
package queue_via_paired_lists
: (weak) Queue # Queue is from src/lib/src/queue.api{
Queue(X) = QUEUE { front: List(X),
back: List(X)
};
empty_queue # To save clients from constantly recreating this value.
=
QUEUE { front => [],
back => []
};
fun queue_is_empty (QUEUE { front => [], back => [] } ) => TRUE;
queue_is_empty _ => FALSE;
end;
fun put_on_back_of_queue (QUEUE { front, back }, x)
=
QUEUE { front, back=>(x ! back) };
fun put_on_front_of_queue (QUEUE { front, back }, x)
=
QUEUE { front=>(x ! front), back };
fun take_from_front_of_queue ( QUEUE { front=>(head ! tail), back } ) => (QUEUE { front=>tail, back }, THE head);
take_from_front_of_queue (q as QUEUE { back => [], ... } ) => (q, NULL);
take_from_front_of_queue ( QUEUE { back, ... } ) => take_from_front_of_queue (QUEUE { front=>reverse back, back => [] } );
end;
# This is just the above with 'front' and 'back' swapped:
#
fun take_from_back_of_queue ( QUEUE { back=>(head ! tail), front } ) => (QUEUE { back=>tail, front }, THE head);
take_from_back_of_queue (q as QUEUE { front => [], ... } ) => (q, NULL);
take_from_back_of_queue ( QUEUE { front, ... } ) => take_from_back_of_queue (QUEUE { back=>reverse front, front => [] } );
end;
fun to_list (QUEUE { back, front } )
=
(front @ (reverse back));
fun from_list items
=
QUEUE { back => [], front => items };
# Synonyms:
#
push = put_on_back_of_queue;
pull = take_from_front_of_queue;
#
unpull = put_on_front_of_queue;
unpush = take_from_back_of_queue;
fun push' (QUEUE { front, back }, items)
=
QUEUE { front, back => list::reverse_and_prepend (items, back) };
fun unpull' (QUEUE { front, back }, items)
=
QUEUE { back, front => items @ front };
fun length (QUEUE { front, back })
=
list::length front
+
list::length back;
};
## COPYRIGHT (c) 1993 by AT&T Bell Laboratories. See SMLNJ-COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.