6.8 List Interface

ORIGIN 'container';
LIB_DEF 'list' '../lib';
BODY 'private/listBody';
(*
 * COPYRIGHT
 *       Copyright (C) Mjolner Informatics, 1992-96
 *       All rights reserved.
 *)
--- lib: attributes ---
list: container
  (* This list pattern defines a double-linked list data structure.
   * Most operations either enters or exits a list position.  List
   * positions are references into a particular place in the list,
   * containing an element.  These positions are instances of
   * theCellType.
   * 
   *     list
   *       cyclicList --- prev and next operations to impl. cyclic list
   *       priorityList --- elements ordered by priority
   *       recList --- allows for recursive lists (in separate fragment)
   * 
   * Defines the following new operations: prepend, append, head,
   *     tail, last, preample, at, locate, concatenate, splitBefore,
   *     splitAfter, insertBefore, insertAfter, delete, deleteBefore,
   *     deleteAfter, scanReverse, iterate, iterateFrom,
   *     iterateReverse, iterateReverseFrom
   *)
  (# <<SLOT listLib: attributes>>;
     theCellType::< 
       (* theCellType is the pattern from which the individual list
        * positions are created. It defines the succ and pred
        * references to the list positions immediately before/after
        * this position in the list (NONE means the end of the list
        * (either end).  The elm attribute refers to the element at
        * this position in the list.
        *)
       (# succ, pred: ^theCelltype; 
       do INNER
       #);
     clear::< (# ... #);
     size::< (# ... #);
     empty::< (# ... #);
     has::
       (# ... #);
     copy::<(#
            ... 
            #);
     prepend: (* insert elm as first element *)
       (# elm: ^element; 
          position: ^theCellType
       enter elm[]
       ...
       exit position[]
       #);
     append: (* insert elm as last element *)
       (# elm: ^element; 
          position: ^theCellType
       enter elm[]
       ...
       exit position[]
       #);
     head: 
       (* returns the position element of the first position in the
        * list
        *)
       (# position: ^theCellType
         ...
       exit position[]
       #);
     tail: 
       (* returns a copy of THIS(list), except the first element *)
       (# lst: ^list
         ...
       exit lst[]
       #);
     last: 
       (* returns the position element of the last position in the
        * list
        *)
       (# position: ^theCellType
         ...
       exit position[]
       #);
     preample: 
       (* returns a copy of THIS(list), except the last element *)
       (# lst: ^list
         ...
       exit lst[]
       #);
     concatenate: 
       (* returns a new list, containing the concatenated list *)
       (# otherList, newlist: ^list; 
       enter otherList[]
       ...
       exit newlist[]
       #);
     insertBefore: (* if position=NONE, insert elm as last element *)
       (# elm: ^element; position, newPosition: ^theCellType
       enter (elm[], position[])
       ...
       exit newPosition[]
       #);
     insertAfter: (* if position=NONE, insert elm as first element *)
       (# elm: ^element; position, newPosition: ^theCellType
       enter (elm[], position[])
       ...
       exit newPosition[]
       #);
     delete: (* if position=NONE, delete nothing *)
       (# deletedPosition, position: ^theCellType;
          empty:< emptyContainer
       enter position[]
       ...
       exit deletedPosition[]
       #);
     deleteBefore: 
       (* if position=NONE, delete last position element *)
       (# deletedPosition, position: ^theCellType;
          empty:< emptyContainer
       enter position[]
       ...
       exit deletedPosition[]
       #);
     deleteAfter: 
       (* if position=NONE, delete first position element *)
       (# deletedPosition, position: ^theCellType;
          empty:< emptyContainer
       enter position[]
       ...
       exit deletedPosition[]
       #);
     splitBefore: 
       (* splits this(list) into two lists, where the elements before
        * position (excluding position) is placed in preList and the
        * rest of this(list) is placed in postList.  PositionElm will
        * be the head of postList.  If position=NONE, preList will
        * become a copy of the entire list and postList will become
        * NONE
        *)
       (# position: ^theCellType;
          preList, postList: ^list;
          listSplitBeforePrivate: @...
       enter position[]
       do listSplitBeforePrivate; INNER
       exit (preList[], postList[])
       #);
     splitAfter: 
       (* splits this(list) into two lists, where the elements before
        * position (including position) is placed in preList and the
        * rest of this(list) is placed in postList. PositionElm will
        * be the last element in postList If position=NONE, preList
        * will become a copy of the entire list and postList will
        * become NONE
        *)
       (# position: ^theCellType;
          preList, postList: ^list;
          listSplitAfterPrivate: @...
       enter position[]
       do listSplitAfterPrivate; INNER
       exit (preList[], postList[])
       #);
     at: (* returns the position of elm in the list *)
       (# elm: ^element;
          position: ^theCellType
       enter elm[]
       ...
       exit position[]
       #);
     locate: 
       (* returns the position of the element in the list, satisfying
        * predicate.  This operation is similar to find, except that
        * it returns the position, not the element.
        *)
       (# predicate:< cellPredicate;
          notFound:< Notification
            (# 
            do none->position[];
               'Element not found in list'->msg.putLine;
               INNER
            #);
          start:< object;
          end:< object;
          position: ^theCellType;
       ...
       exit position[]
       #);
     find::
       (#
       ...
       #);
     thescanner::< (* private *)
       (# theCell:^theCelltype;
          notdone:@boolean;
       ...
       #);
     theReverseScanner:< (* private *)
       (# 
          w:^elementPredicate;
          s:^scanreverse;
          aCell:^theCellType;
          notdone:@boolean;
       enter (s[],w[])
       ...
       #);
     theFromScanner:< (* private *)
       (# 
          w:^elementPredicate;
          s:^scanFrom;
          aCell:^theCellType;
          notdone:@boolean;
       enter (s[],w[],aCell[])
       ...
       #);
     scanReverse: 
       (* similar to scan, except that it scans the list in reverse
        * direction
        *)
       (# first:@boolean;
          where:< elementPredicate;
          current: ^element;
          start:< object;
          end:< object;
       ...
       #);
     scanFrom:
       (* similar to scan, except that it scans the list from the
        * given position
        *)
       (# 
          first:@boolean;
          where:< elementPredicate;
          current: ^element;
          start:< object;
          end:< object;
          position:^theCelltype; (* start cell *)
       enter position[]
       ...
       #);
     scanReverseFrom: 
       (* similar to scanReverse, except that it scans the list in
        * reverse direction from the given position
        *)
       (# where:< elementPredicate;
          position: ^theCellType;
          current: ^element;
          theCell:^theCelltype;
          start:< object;
          end:< object;
       enter position[]
       ...
       #);
     iterate: 
       (* similar to scan, except that "current" refers to the
        * current cell in the list.  If furthermore the list is an
        * instance of the recList subpattern, iterate respects the
        * sublist structure by not scanning the elements in the
        * sublists (as scan does). I.e. during an iterate of a
        * recList, "current" may refer to a cell containing either an
        * element, or a sublist.
        *)
       (# where:< cellPredicate;
          current: ^theCellType;
          start:< object;
          end:< object;
          listIteratePrivate: @...
       ...
       #);
     iterateFrom: 
       (* similar to iterate, except that it takes a position, and
        * starts the iteration from that position.
        *)
       (# where:< cellPredicate;
          position: ^theCellType;
          current: ^theCellType;
          start:< object;
          end:< object;
          listIterateFromPrivate: @...
       enter position[]
       ...
       #);
     iterateReverse: 
       (* similar to iterate, except that it iterates backwards.
        *)
       (# where:< cellPredicate;
          current: ^theCellType;
          start:< object;
          end:< object;
          listIterateReversePrivate: @...
       ...
       #);
     iterateReverseFrom: 
       (* similar to iterateReverse, except that it takes a position,
        * and starts the reverse iteration from that position.
        *)
       (# where:< cellPredicate;
          position: ^theCellType;
          current: ^theCellType;
          start:< object;
          end:< object;
          listIterateReverseFromPrivate: @...
       enter position[]   
       ...
       #);
     cellPredicate: booleanValue
       (* This pattern is used as the superpattern for the predicates
        * in the locate and iterate operations.
        *)
       (# current: ^theCellType
       enter current[]
       do true->value;
          INNER
       #);
     doEnter::<
       (# containerType::<list;
          doneInInner:@boolean
       ...
       #);
     private:@...;
  do INNER
  #) (* list *);

cyclicList: list
  (* Add operations next and prev to enable traverse the list as a
   * cycle list
   *)
  (# theCellType::<
       (# prev:
            (# position: ^theCellType
            do pred[]->position[];
               (if position[]=NONE then last->position[] if);
            exit position[]
            #);
          next:
            (# position: ^theCellType
            do succ[]->position[];
               (if position[]=NONE then head->position[] if);
            exit position[]
            #);
       #);
  #);

priorityList: list
  (* implements a priority list where the elements added to the list
   * are ordered according to their priority (implemented by the
   * ordering relation 'less')
   *)
  (# less:< booleanValue
       (# left,right: ^element enter (left[],right[]) do INNER #);
     add:
       (# elm: ^element; added: @boolean
       enter elm[]
       do loop:
            iterate
            (#
            do (if (elm[],current.elm[])->less then
                   (elm[],current[])->insertBefore;
                   true->added;
                   leave loop
               if)
            #);
          (if not added then elm[]->append if)
       #)
  #)