Name

List, ListIndex -- collection of members in linear sequence

Synopsis

//
// List - collection of members in linear sequence
//
@deftype List <Collection, CREATABLE>
CREATING
- (void)	setEndsOnly: (BOOL)endsOnly;
USING
- (BOOL)	getEndsOnly;

- (void)	addFirst: anObject;
- (void)	addLast: anObject;

-		removeFirst;
-		removeLast;
@end

//
// ListIndex -- index with insertion capability at any point in list
//
@deftype ListIndex <Index>
- (void)	addAfter: anObject;
- (void)	addBefore: anObject;
@end

Description

A list is a collection of members that are all maintained at some externally assigned position in a linear sequence of all members. The sequence is established by the position at which members are added: members can be added at the start of list, at the end, or at any point in the middle.

A list is also one of the most dynamic of basic collections, in that the cost of adding and removing members is very low. Members can be removed from any position just as easily as they can be added. A list automatically grows and shrinks to reflect the number of members at any one time, and there is no fixed capacity which limits the size to which a list may grow.

Inherited behavior

@deftype List <Collection, CREATABLE>
The List type is supports all messages of Collection. If created with default options, it provides no special speedup of accesses by integer offset.

Unless the EndsOnly option is specified, the default value of IndexSafety is UnsafeAtMember. This means that indexes are inherently safe under all operations except those which affect the member at an index or immediately adjacent to an index between members. If the EndsOnly option is specified, the default value of IndexSafety is Unsafe. In this case, indexes could be invalidated by any operation that adds or removes members. The SafeAlways can be specified for any case to get a guarantee of full index safety.

ListIndex is a special index type just for list collections. It provides the only method to add members within the interior of a list.

Create-time options

CREATING
- (void)	setEndsOnly: (BOOL)endsOnly;
USING
- (BOOL)	getEndsOnly;

EndsOnly

(.. This option is not implemented yet.) The EndsOnly option restricts a list so that members can be added or removed only at either end. This restriction permits an alternate implementation that both reduces memory usage and enables fast, direct access to members by integer offset. It obtains key performance advantages of an array while preserving the dynamic extendability of a list.

List behavior

- (void)	addFirst: anObject;
- (void)	addLast: anObject;
The addFirst: and addLast: messages add a new member to either end of a list. With addFirst:, the new member becomes the first member of the array. With addLast:, it becomes the last member.

-		removeFirst;
-		removeLast;
removeFirst and removeLast remove either the first or last member of a list. They each return the value of the member just removed.

ListIndex behavior

//
// ListIndex -- index with insertion capability at any point in list
//
@deftype ListIndex <Index>
- (void)	addAfter: anObject;
- (void)	addBefore: anObject;
@end
The addAfter: and addBefore: messages add members at a particular point in the sequence of members maintained by a list. The current location of an index determines the point at which a new member will be added. The addAfter: message adds a member at the list position immediately following the current index location. addBefore: adds a member to the immediately preceding location. Neither message changes the current location of the index, except that an index can change from a Start or End location to a location of Between.

Since an index may be positioned to any location in a list, these messages enable the construction of any desired sequence of members. Since the current index location remains unchanged, multiple members may all be inserted successively at some point in a list; previously added members are just pushed out one-by-one as new members are added.

An index with a location of Start, End, or Between is just as valid a location for addAfter: or addBefore: as an index positioned at a member. In these cases, there is no member at the current location of the index, so the new member is just inserted directly at the current index location, and the index is left positioned between the new member and the member that was previously adjacent in the opposite direction. If the previous location was Start and the message addAfter:, or the location was End and the message addBefore:, the index location remains Start or End.

If either the addAfter: or addBefore: message is requested with the EndsOnly option, and the index location is not Start or End, or if remove is requested on an index that is not positioned at either the first or last member, an invalid operation error is raised.

Roger Burkhart <rmb@santafe.edu>
Last modified: