PreviousUpNext

15.4.870  src/lib/src/fifo.pkg

## 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.


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext