## fifo.pkg
# Compiled by:
# src/lib/std/standard.lib# Applicative fifos
# See also:
# src/lib/src/queue.pkg### "I don't know anything about music.
### In my line you don't have to."
###
### -- Elvis Presley
package fifo
: (weak) Fifo # Fifo is from src/lib/src/fifo.api{
Fifo(X) = FIFO { front: List(X),
rear: List(X)
};
exception DEQUEUE;
empty = FIFO { front => [],
rear => []
};
fun is_empty (FIFO { front => [], rear => [] } ) => TRUE;
is_empty _ => FALSE;
end;
fun enqueue (FIFO { front, rear }, x)
=
FIFO { front, rear=>(x ! rear) };
fun dequeue (FIFO { front=>(head ! tail), rear } ) => (FIFO { front=>tail, rear }, head);
dequeue (FIFO { rear => [], ... } ) => raise exception DEQUEUE;
dequeue (FIFO { rear, ... } ) => dequeue (FIFO { front=>reverse rear, rear => [] } );
end;
# Drop all queue elements for which
# 'predicate' returns TRUE:
#
fun delete (FIFO { front, rear }, predicate)
=
FIFO (do_front front)
where
fun do_front []
=>
{ front => do_rear (reverse rear), rear => [] };
do_front (this ! rest)
=>
if (predicate this)
#
{ front => rest, rear };
else
my { front, rear } = do_front rest;
{ front => this ! front, rear };
fi;
end
also
fun do_rear [] => [];
do_rear (this ! rest) => if (predicate this) rest;
else this ! (do_rear rest);
fi;
end;
end;
fun peek (FIFO { front => (head ! _), ... } ) => THE head;
peek (FIFO { rear => [], ... } ) => NULL;
peek (FIFO { rear, ... } ) => THE (head (reverse rear));
end;
fun head (FIFO { front => (head ! _), ... } ) => head;
head (FIFO { rear => [], ... } ) => raise exception DEQUEUE;
head (FIFO { rear, ... } ) => list::head (reverse rear);
end;
fun length (FIFO { rear, front } )
=
(list::length rear) + (list::length front);
fun contents (FIFO { rear, front } )
=
(front @ (reverse rear));
fun apply f (FIFO { front, rear } )
=
{ list::apply f front;
list::apply f (list::reverse rear);
};
fun map f (FIFO { front, rear } )
=
FIFO { front => list::map f front, rear => reverse (list::map f (reverse rear)) };
fun fold_left f b (FIFO { front, rear } ) = list::fold_right f (list::fold_left f b front) rear;
fun fold_right f b (FIFO { front, rear } ) = list::fold_right f (list::fold_left f b rear) front;
};
## COPYRIGHT (c) 1993 by AT&T Bell Laboratories. See COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2012,
## released under Gnu Public Licence version 3.