[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
ADT List LISP-style
Here is my current proposal of a lispish style list implementation.
Note that I had to do some severe changes to the list data structure,
because we cannot use NIL for the empty list (at least in this
context).
While I was hacking away on the implementation of double-linked lists,
I noticed a little loophole in our specs for riders. The dl list can
define an indexed rider, but the time of access would be O(n), instead
of the expected O(1). Therefore I propose to require that all
implementations of index riders implement `SetPos' and `ReadX' in such
a way, that both operations are executed in O(1) time.
Should we also require an upper limit on the implementation on the
space and time requirements for forward and bidirectional riders?
-- mva
------------------------------------------------------------------------
(* $Id: ListSL.Mod,v 1.2 1998/06/24 13:55:37 acken Exp $ *)
MODULE ListSL;
(*
$Log: ListSL.Mod,v $
Revision 1.2 1998/06/24 13:55:37 acken
Renamed module from ListLISP to ListSL.
Borrowed as many procedures as possible from ListDL.
Added blurb about node sharing.
Revision 1.1 1998/06/23 14:00:34 acken
Initial revision
*)
IMPORT
AcObject, AcContainer;
(*
This module provides a LISP-like implementation of a list. It differs from
the LISP cons cell in that a list is not identified with a cons cell. Rather,
a list is a separate entity, which refers to cons cells (which are called
`Node' in this context).
Sharing of nodes between different lists is permitted. E.g., suppose we
have to lists A and B:
A: a --- b --- c
B: d --- e --- f
Then the result of
a.AppendList(b)
will be
A: \ B: \
a --- b --- c --- d --- e --- f
The last three list nodes d, e, and f, appear both as part of A and B.
Even cyclic structures are possible:
a.ReplaceNext(Head(a).next.next, Head(A))
gives
A: a --- b --- c
\ /
---------
This is a cycel of length 3. While this is legal, some operations on lists
(like Copy, Append, Apply, and so on) do not work with this kind of list.
*)
TYPE
Node = POINTER TO NodeDesc;
NodeDesc = RECORD
next-: Node;
obj-: AcObject.Object;
END;
List* = POINTER TO ListDesc;
ListDesc* = RECORD
(AcContainer.ContainerDesc)
head: Node;
END;
(* Constructors and Deconstructors
======================================================================== *)
PROCEDURE Init* (l: List);
(* Initializes the instance of `List' to the empty list. *)
BEGIN
l. head := NIL
END Init;
PROCEDURE New*(): List;
(* Creates an instance of `List', and initializes it to the empty list. *)
VAR
l: List;
BEGIN
NEW (l);
Init (l);
RETURN l
END New;
PROCEDURE Destroy* (l: List);
(* Removes all elements from list `l' and destroys the list object itself.
The variable parameter `l' is set to NIL. If other instances of `List'
share nodes of `l', the other lists will be affected, too. Use this with
caution.
Note: The user is not required to call this procedure. Resources like
unused lists are automatically freed by the garbage collector. This
procedure is provided for convenience, both for the user and the garbage
collector. *)
VAR
ptr, next: Node;
BEGIN
AcContainer.Destroy (l);
ptr := l. head;
WHILE (ptr # NIL) DO
next := ptr. next;
ptr. next := NIL;
ptr := next
END;
l. head := NIL
END Destroy;
PROCEDURE (l: List) Copy* (): List;
(* Creates a copy of the given list `l'. That is, a new list is created,
with new instances of `List.Node', that contains the same data objects,
in the same sequence, as the orginal list. Note that no copies of objects
are created in the process.
pre: `l' has no cycles
cost: time O(n), space O(n) *)
END Copy;
(* Node Insertion
======================================================================== *)
PROCEDURE (l: List) Append* (obj: AcObject.Object);
(* Adds a new element `obj' to the list. The new element is placed at the
end of the list.
pre: obj # NIL
cost: O(1) time, O(1) space *)
END Append;
PROCEDURE (l: List) Prepend* (obj: AcObject.Object);
(* Adds a new element `obj' to the list. The new element is placed at the
beginning of the list.
pre: obj # NIL
cost: O(1) time, O(1) space *)
END Prepend;
PROCEDURE (l: List) InsertNext* (dest: Node; obj: AcObject.Object);
(* Adds a new element `obj' to the list. The new element is placed after
`dest', and before `dest. next'. If `dest' is NIL, this operation is
equivalent to `Prepend'.
pre: l.PartOfList(dest) & (obj # NIL)
cost: O(1) time, O(1) space *)
END InsertNext;
PROCEDURE (l: List) AppendList* (src: List);
(* Appends list `src' to list `l'. The source list is not modified. The list
elements of `src' are afterwards shared by both `l' and `src'.
pre: `l' has no cycles
cost: O(n) time, O(1) space *)
END AppendList;
(* Node Removal
======================================================================== *)
PROCEDURE (l: List) Remove* (node: Node);
(* Removes the given `node' from list `l'.
pre: l.PartOfList(node)
cost: O(1) time, O(1) space
Note: Operations on a removed node are undefined. In practice, the fields
of a removed node are set to NIL, to limit the scope of potential unwanted
side effects, and to simplify debugging. *)
END Remove;
PROCEDURE (l: List) Replace* (node: Node; obj: AcObject.Object);
(* Replaces list element at place `node' with `obj'.
pre: l.PartOfList(node) & (obj # NIL)
cost: O(1) time, O(1) space *)
BEGIN
ASSERT (obj # NIL);
node. obj := obj
END Replace;
PROCEDURE (l: List) ReplaceNext* (node: Node; newNext: Node);
(* Replaces `next' pointer of `node' with `newNext'.
pre: l.PartOfList(node) & (obj # NIL)
cost: O(1) time, O(1) space *)
BEGIN
node. next := newNext
END ReplaceNext;
(* List Permutations
======================================================================== *)
PROCEDURE (l: List) Reverse*;
(* Reverses the sequence of elements in list `l'.
pre: `l' has no cycles
cost: O(n) time, O(1) space *)
END Reverse;
(* Node Retrieval
======================================================================== *)
PROCEDURE (l: List) Head* (): Node;
(* Returns the node of the first element of the list. Result is NIL if the
list is empty.
cost: O(1) time, O(1) space *)
END Head;
PROCEDURE (l: List) Get* (start: Node; obj: AcObject.Object): Node;
(* Beginning at node `start', this procedure searches forward for the first
occurence of `obj' in the list. Result is NIL if no matching list element
was found, or `start' is NIL.
pre: (start = NIL) OR l.PartOfList(start) & `l' has no cycles
cost: O(n/2) time (on the average), O(1) space *)
END Get;
PROCEDURE (l: List) Nth* (pos: LONGINT): AcObject.Object;
(* Returns the object stored in the n-th list element of `l'. Values of `pos'
(0 <= pos < l.Length()) refer to list elements counting from the beginning:
0 is the first element, 1 the second, and so on. If `pos' is out of range,
the value NIL is returned.
cost: O(n/2) time on the average, O(1) space *)
END Nth;
(* Iterators
======================================================================== *)
PROCEDURE (l: List) Apply* (op: AcObjFct.Operator);
(* Successively applies operator `op' to the elements of `l'. The procedure
`op.Apply' must not perform any structural modifications on `l' (like
insertion, removal, or moving elements), or the result of this procedure is
undefined.
pre: `l' has no cycles
cost: O(n) time, O(1) space, disregarding any effects of `op.Apply' *)
END Apply;
PROCEDURE (l: List) Map* (fct: AcObjFct.Function): List;
(* Successively applies the function `fct' to the elements of `l', and collects
the results into a new list. The list `l' is not destroyed. The procedure
`fct.Apply' must not perform any structural modifications on `l' (like
insertion, removal, or moving elements), or the result of this procedure is
undefined.
pre: `l' has no cycles
cost: O(n) time, O(1) space, disregarding any effects of `fct.Apply' *)
END Map;
PROCEDURE (l: List) Select* (pred: AcObjFct.Predicate): List;
(* Successively applies the predicate `fct' to the elements of `l'. All nodes,
for which `pred' evaluates to TRUE, are collected into a new list, in the
order in which they appear in the original list. The original list `l' is
not modified. The procedure `pred.Apply' must not perform any structural
modifications on `l' (like insertion, removal, or moving elements), or the
result of this procedure is undefined.
pre: `l' has no cycles
cost: O(n) time, O(1) space, disregarding any effects of `pred.Apply' *)
END Select;
(* Miscellaneous
======================================================================== *)
PROCEDURE (l: List) Empty* (): BOOLEAN;
END Empty;
PROCEDURE (l: List) Length* (): LONGINT;
(* Returns the number of elements in list `l'.
pre: `l' has no cycles *)
END Length;
PROCEDURE (l: List) Size* (): LONGINT;
(* Returns the number of elements in list `l'. *)
END Size;
END ListSL.