6.10 SeqContainers Interface

ORIGIN 'container';
LIB_DEF 'contseq' '../lib';
BODY 'private/seqContainersBody';
(*
 * COPYRIGHT
 *       Copyright (C) Mjolner Informatics, 1992-94
 *       All rights reserved.
 *)
--- lib: attributes ---
sequentialContainer: container
  (* sequentialContainer is an abstract superpattern and the
   * currently available subpatterns are (indentation specifies
   * specialization): 
   *     sequentialContainer
   *       stack
   *       queue
   *       deque
   *)
  (# <<SLOT sequentialContainerLib: attributes>>;
     theScanner::<(# 
       ...
       #);
     size:: 
       (# 
       ...
       #);
     clear::
       (# 
       ...
       #);
     empty::
       (# 
       ...
       #);
     has::<
       (# 
       ...
       #);
     theCellType::< (* Private *)
       (# succ, pred: (* Private *) ^theCellType; 
       do INNER #);
     private:@...;
  do INNER
  #) (* sequentialContainer *);

(*------------------------------------------------------------*)
(*--- stack---------------------------------------------------*)
(*------------------------------------------------------------*)

stack: sequentialContainer
  (* Stack is an ordinary stack data structure.  Defines the
   * operations: top, push, pop
   *)
  (# <<SLOT stackLib: attributes>>;
     find::
       (#  privateFinder:@...;
       ...
       #);
     copy::<
       (# 
       ...
       #);
     top: (* Returns the topmost element on THIS(stack) *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
     push: 
       (* Takes an element and places it on the top of THIS(stack) *)
       (# elm: ^element
       enter elm[]
       ...
       #);
     pop: 
       (* Returns the topmost element, and removes it from the stack
        *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
     doEnter::<
       (# containerType::<stack;
       ...
       #)
  do INNER
  #) (* stack *);

(*------------------------------------------------------------*)   
(*--- queue --------------------------------------------------*)   
(*------------------------------------------------------------*)   

queue: sequentialContainer
  (* Queue is an ordinary queue data structure.  Defines the
   * operations: front, insert, remove
   *)
  (# <<SLOT queueLib: attributes>>;
     has::<
       (# 
       ...
       #);
     find::
       (#  privateFinder:@...;
       ...
       #);
     copy::<
       (# 
       ...
       #);
     front: (* Returns the element in the front of THIS(queue) *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
     insert: 
       (* Takes an element and inserts it at the end of THIS(queue) *)
       (# elm: ^element
       enter elm[]
       ...
       #);
     remove: 
       (* Returns the element in front, and removes it from the queue
        *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
      doEnter::<
       (# containerType::<queue;
       ...
       #)
     (*     private:@...;*)
  do INNER
  #) (* queue *);


(*---------------------------------------------------------------*)   
(*--- deque -----------------------------------------------------*)   
(*---------------------------------------------------------------*)   

deque: sequentialContainer
  (* Deque is a double-ended queue in which elements may be inserted
   * and removed from both ends of the queue.  Defines the operations: 
   * front, insertFront, removeFront, back, insertBack, removeBack
   *)
  (# <<SLOT dequeLib: attributes>>;
     find::
       (# 
       ...  
       #);
     front: (* Returns the element in the front *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
     insertFront: (* Takes an element and inserts it at the front *)
       (# elm: ^element
       enter elm[]
       ...
       #);
     removeFront: 
       (* Remove and return the element in front of THIS(deque) *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
     back: (* Returns the element in the back *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
     insertBack: (* Takes an element and inserts it at the back *)
       (# elm: ^element
       enter elm[]
       ...
       #);
     removeBack: (* Returns the element in the back, removing it *)
       (# elm: ^element; empty:< emptyContainer
         ...
       exit elm[]
       #);
     doEnter::<
       (# containerType::<deque;
       ...
       #)
  do INNER
  #) (* deque *);


(* These are to different priorityqueues! *)

(*----------------------------------------------------------------*)   
(*--- prioQueue --------------------------------------------------*)   
(*----------------------------------------------------------------*)   

prioQueue: sequentialContainer
  (* PrioQueue is a priority queue, in which the elements are kept in
   * SEPARATE queues for each priority.  Defines the operations: 
   * front, insert, remove, scanPriority.
   *)
  (# <<SLOT prioQueueLib: attributes>>;
     theScanner::<
       (# 
       ...
       #); 
     front: (* Returns the element in front with the given priority *)
       (# prio: @integer; elm: ^element; empty:< emptyContainer
       enter prio
       ...
       exit elm[]
       #);
     insert: 
       (* Insert an element in the queue with the given priority *)
       (# prio: @integer; elm: ^element
       enter (elm[],prio)
       ...
       #);
     remove: 
       (* Remove and returns the front element with the given
        * priority
        *)
       (# prio: @integer; elm: ^element; empty:< emptyContainer
       enter prio
       ...
       exit elm[]
       #);
     scanPriority: 
       (* scans through all elements of the given priority *)
       (# prio: @integer;
          where:< elementPredicate;
          current: ^element;
          start:< object;
          end:< object;
       enter prio
       ...
       #);
     copy::<
       (# 
       ...
       #);    
     theCellType::< (* Private *)
       (# prio: @integer;
          theQueue: ^queue;
          copy::< (# 
                  do prio->theCellCopy.prio;
                     (if theQueue[] = NONE then
                      else
                         theQueue.copy->theCellCopy.theQueue[]
                     if)
                  #)
       do INNER #);
     doEnter::<
       (# containerType::<prioQueue;
       ...
       #)
  do INNER
  #) (* prioQueue *);

(*----------------------------------------------------------------*)   
(*--- priorityQueue ----------------------------------------------*)   
(*----------------------------------------------------------------*)   
PriorityQueue:container
  (* This implements a general priorityqueue. 
   * O(log n) time for insert and deletemin. (list based balanced treee)
   * Does not require elments to have and explicit
   * priority. It is based purely on the less attribute.
   * Futherbind element and less to use your own priotities
   * Note this redefines basic attributes!
   *)

(# <<SLOT priorityQueueLib: attributes>>;
   less:<booleanValue
     (# e1,e2:^element;
     enter (e1[],e2[])
     do INNER
     #);
   
   insert:
     (# elm: ^element;
        doInsert: @...;
     enter elm[]
     do doInsert
     #);
   
   deleteMin:
     (# elm: ^element;
        doDeleteMin: @...;
     do doDeleteMin;
     exit elm[]
     #);
   
   min:
     (# elm: ^element;
     ...
     exit elm[]
     #);
   
   scan:
     (# current: ^element;
     ... 
     #);

   init::<
     (# ... #);
   
   clear:<
     (# ... #);
   size:IntegerValue
     (# ... #);
   empty:<BooleanValue
     (# ... #);
   has:<BooleanValue
     (# elm:^element;
     enter elm[]
     ... 
     #);
   
   emptyContainer:< exception;
   storage: @...;
#)