List is a subpattern of the container pattern. It implements a double-chained list data structure. The list pattern is a little special, since many operations takes list positions as arguments instead of elements. The reason is, that the typical usage of lists are to manipulate the list itself (finding the element just before a given position in the list, etc.). This adds a little extra complexity to the operations of the list pattern, relative to the other container patterns.
Central to the understanding of the list pattern, is the understanding of the theCellType pattern. TheCellType is a virtual pattern, defined in container pattern (but it is a private attribute, except for the list subpattern). In the list pattern, theCellType contains the references to the successor and predecessor list positions, as well as the elm reference to the element object contained at this list position. TheCellType describes the list positions (also often called list elements).
List defines the following additional operations:
- prepend: takes an element (i.e. a reference to an element) and adds it to the front of the list. Prepend returns the position of the element in the list (i.e. a reference to the instance of theCellType, containing the new element reference). This position may later be used to reference the element in the list (e.g. finding the succ of pred positions in the list).
- append: Similar to prepend, except that it inserts the element at the end of the list.
- head: Returns the position in the beginning of the list.
- last: Returns the position in the end of the list.
- tail: Returns a copy of the list, except for the first list element which have been removed.
- preample: Returns a copy of the list, except for the last list element which have been removed.
- concatenate: takes two lists and returns a new list which is the concatenation of the two lists.
- insertBefore, insertAfter: Takes an element and a list position, and inserts the element before (respectively after) the list position.
- delete, deleteBefore, deleteAfter: takes a list position and deletes the list position (respectively the list position before or after) from the list.
- splitBefore, splitAfter: takes a list position and returns two lists that are the lists from the beginning up to the list position, respectively from the list position until the end of the list. The list position will be in one of the lists.
- at: takes an element and returns the first list position, containing a reference to that element.
- 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.
- iterate, iterateFrom, iterateReverse, iterateReverseFrom: iterates through the list structure in different ways. In contrast to scan (inherited from container), all iterate variants respects the sublist structure such that a sublist will not be traversed automatically.
- scanFrom, scanReverse, scanReverseFrom: similar to the iterate operations above.
|Container Libraries - Reference Manual
||© 1992-2002 Mjølner Informatics
[Modified: Thursday October 19th 2000 at 12:51]