ObjectiveLib  1.0.0
Public Member Functions | Static Public Member Functions | Protected Attributes
OLList Class Reference

A doubly linked list. More...

#import <ObjectiveLib/List.h>

Inheritance diagram for OLList:
Inheritance graph
[legend]

List of all members.

Public Member Functions

(void) - assign:filledWith:
 Assign objects to the list.
(void) - assignFrom:to:
 Assign a range of objects to the list.
(id) - back
 Return the last object in the list.
(OLListIterator *) - begin
 Return an iterator pointing to the beginning of the sequence.
(void) - clear
 Remove all elements.
(int) - compare:
 Compare this list to another object.
(id) - copyWithZone:
 Make a copy of this list allocating memory from the given zone.
(BOOL) - empty
 Test whether the list is empty.
(void) - encodeWithCoder:
 Encode the list.
(OLListIterator *) - end
 Return an iterator pointing to one position beyond the end of the sequence.
(OLListIterator *) - erase:
 Remove the element designated by where.
(OLListIterator *) - eraseFrom:to:
 Remove a range of elements.
(id) - front
 Return the first object in the list.
(void) - insertAt:count:filledWith:
 Insert a number of objects into the list.
(void) - insertAt:from:to:
 Insert a range of objects into the list.
(OLListIterator *) - insertAt:value:
 Insert an object into the list.
(BOOL) - isEqual:
 Return whether this list is equal to another one.
(unsigned) - maxSize
 Return the maxiumum number of objects that can be stored in a list.
(void) - merge:
 Merge the contents of two lists.
(void) - merge:withOrder:
 Merge the contents of two lists.
(void) - popBack
 Remove the last element in the list.
(void) - popFront
 Remove the first element in the list.
(void) - pushBack:
 Insert object at the end of the sequence.
(void) - pushFront:
 Insert object at the beginning of the sequence.
(OLReverseBidiIterator *) - rbegin
 Return a reverse iterator pointing to the end of the sequence.
(void) - remove:
 Remove all objects equal to object.
(void) - removeIf:
 Remove all objects for which pred returns YES.
(OLReverseBidiIterator *) - rend
 Return a reverse iterator pointing to the beginning of the sequence.
(void) - resize:filledWith:
 Resize the list to newsize.
(void) - reverse
 Reverse the order of the list.
(unsigned) - size
 Return the number of elements in the list.
(void) - sort
 Sort the list in ascending order.
(void) - sortWith:
 Sort the list.
(void) - spliceAt:list:
 Splice another list into this one.
(void) - spliceAt:list:from:
 Splice an element from another list into this one.
(void) - spliceAt:list:from:to:
 Splice a range of elements into this list.
(void) - swap:
 Swap this list with another one.
(void) - unique
 Remove all but one of each consecutive element in the list.
(void) - uniqueWith:
 Remove all but one of each consecutive element for which pred returns YES.
(void) - writeSelfToStream:
 Write the object to a stream.
Initializers and Deallocators
(id) - init
 Initialize the list.
(id) - initFrom:to:
 Initialize the list.
(id) - initWithCoder:
 Initialize the list.
(id) - initWithList:
 Initialize the list.
(id) - initWithObjectInStream:
 Initialize the object.
(id) - initWithSize:filledWith:
 Initialize the list.
(void) - dealloc
 Finalize the list and deallocate any allocated memory.

Static Public Member Functions

(id) + list
 Create and return a new list.
(id) + listFrom:to:
 Create and return a new list.
(id) + listWithList:
 Create and return a new list.
(id) + listWithSize:filledWith:
 Create and return a new list.

Protected Attributes

OLListNode * node
 The head of the list.

Detailed Description

A doubly linked list.

A sequence of elements that is a bidirectional linked list, and thus may be traversed both forwards and backwards. An important feature of lists is that insertion and removal do not affect existing iterators unless the iterator points directly to an object that has been removed. Due to the fact that some algorithms from OLAlgorithm require random access iterators and lists only provide bidirectional iterators, some messages are provided in OLList to make up for the unavailability of the functionality in OLAlgorithm. Examples of these messages include sort (OLList), unique (OLList) and merge: (OLList).

See also:
OLListIterator

Member Function Documentation

- (void) assign: (unsigned)  count
filledWith: (id)  value 

Assign objects to the list.

The current contents of the list are removed, and the list is filled with count elements of value.

Parameters:
countthe number of elements to assign
valuethe object to be copied into the list
- (void) assignFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Assign a range of objects to the list.

The current contents of the list are removed, and all elements in the range [first, last) are inserted into the list.

Parameters:
firstthe first in the range of objects to assign
lastone beyond the last in the range of objects to assign
- (id) back

Return the last object in the list.

A reference to the object is returned, though the list still owns the object in question.

Note:
The results of this message are undefined if the list is empty.
Returns:
the last object

Return an iterator pointing to the beginning of the sequence.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
an iterator pointing to the first element
- (void) clear

Remove all elements.

- (int) compare: (id)  other

Compare this list to another object.

If the other object is of type OLList, each of the contained objects is compared to the corresponding object in other by calling the compare: method.

Parameters:
otherthe object with which to compare this one
Returns:
a value greater than, equal to, or less than zero accoringly as this object is greater than, equal to, or less than other
- (id) copyWithZone: (NSZone *)  zone

Make a copy of this list allocating memory from the given zone.

Parameters:
zonethe zone from which to allocate memory
Returns:
the copy
- (void) dealloc

Finalize the list and deallocate any allocated memory.

- (BOOL) empty

Test whether the list is empty.

Returns:
YES if the list is empty, NO otherwise
- (void) encodeWithCoder: (NSCoder *)  encoder

Encode the list.

The list is saved to an archive using encoder. The list will be retrieved from the archive using the initializer initWithCoder:.

Parameters:
encoderthe coder which will save the bit set to the archive

Return an iterator pointing to one position beyond the end of the sequence.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
an iterator pointing to one position beyond the last element

Remove the element designated by where.

Precondition:
where must point to an element in this list.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
wherean iterator designating the element to remove
Returns:
an iterator indicating the next element in the sequence remaining after where
- (OLListIterator*) eraseFrom: (OLListIterator *)  first
to: (OLListIterator *)  last 

Remove a range of elements.

All elements in the range [first, last) will be removed from the list.

Precondition:
first and last must refer to elements in this list.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range of elements to remove
lastone position beyond the last in the range of elements to remove
Returns:
an iterator indicating the next element in the sequence remaining after removal of the range
- (id) front

Return the first object in the list.

A reference to the object is returned, though the list still owns the object in question.

Note:
The results of this message are undefined if the list is empty.
Returns:
the first object
- (id) init

Initialize the list.

The resulting list will be empty.

Returns:
a reference to this list
- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Initialize the list.

The list inserts all elements referred to in the range [first, last).

Parameters:
firstthe first in the range of elements to insert
lastone beyond the last in the range of elements to insert
Returns:
a reference to this list
- (id) initWithCoder: (NSCoder *)  decoder

Initialize the list.

This initializer creates a new list from an archive and returns it.

Postcondition:
The list returned will be identical to the list saved to the archive using the encodeWithCoder: message.
Parameters:
decoderthe coder which will decode the archived list
Returns:
a reference to this list
- (id) initWithList: (OLList *)  list

Initialize the list.

All the elements of list are copied into the current list.

Parameters:
listthe list to copy
Returns:
a reference to this list

Initialize the object.

Each instance variable is read from stream and all other initialization is performed.

Parameters:
streamthe stream from which to read
Returns:
a reference to this object

Reimplemented from <OLStreamable>.

- (id) initWithSize: (unsigned)  size
filledWith: (id)  value 

Initialize the list.

The initial size of the list will be size, and value will be copied into the list size times.

Parameters:
sizethe number of elements to insert
valuethe object to be copied
Returns:
a reference to this list
- (void) insertAt: (OLListIterator *)  where
count: (unsigned)  num
filledWith: (id)  value 

Insert a number of objects into the list.

num objects of value will be inserted just before the position referred to by where. Thus, it is valid to use an iterator returned by end as an argument.

Precondition:
where must refer to a position in this list
Parameters:
wherethe position at which to insert the objects
numthe number of objects to insert
valuethe object to be copied into the list
- (void) insertAt: (OLListIterator *)  where
from: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Insert a range of objects into the list.

All objects in the range [first, last) are inserted just before the position referred to by where. Thus, it is valid to use an iterator returned by end as an argument.

Parameters:
wherethe position at which to insert the objects
firstthe first in the range of objects to insert
lastone position beyond the last in the range of objects to insert
- (OLListIterator*) insertAt: (OLListIterator *)  where
value: (id)  object 

Insert an object into the list.

The object will be inserted just before the position referred to by where. Thus, it is valid to use an iterator returned by end as an argument.

Precondition:
where must refer to a position in this list.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
wherethe position at which to insert object
objectthe object to insert
Returns:
an iterator pointing to the newly inserted object
- (BOOL) isEqual: (id)  object

Return whether this list is equal to another one.

Two lists are considered equal if they both contain the same number of objects that all return YES to the message isEqual: and they are in the same order.

Parameters:
objectthe object to test
Returns:
YES if object is equal to this list

Reimplemented from <OLBackInserter>.

+ (id) list

Create and return a new list.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
a new list
+ (id) listFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Create and return a new list.

The list is initialized with the contents of the range [first, last).

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range of elements to insert
lastone beyond the last in the range of elements to insert
Returns:
a new list
+ (id) listWithList: (OLList *)  right

Create and return a new list.

The list is initialized with the contents of right.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
rightthe list with which to initialize the new one
Returns:
a new list
+ (id) listWithSize: (unsigned)  size
filledWith: (id)  value 

Create and return a new list.

The list is initialized with a size of size and is filled with value.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
sizethe number of elements to insert
valuethe object to be copied
Returns:
a new list
- (unsigned) maxSize

Return the maxiumum number of objects that can be stored in a list.

This limit is theoretical, meaning that there is no guarantee that you can insert this many objects into any given list. The memory conditions of the run-time system play an important role.

Returns:
the maximum number of objects for a list
- (void) merge: (OLList *)  right

Merge the contents of two lists.

Both lists must be sorted in ascending order. That is, they must be sorted using the function object OLLess, or with a function object that perfroms the same operation as OLLess. All elements are removed from right and inserted in order into this list. This is a stable merge in that if two elements are equal, the one from this list will precede the one from right after the merge.

Parameters:
rightthe list to merge into this list
- (void) merge: (OLList *)  right
withOrder: (id< OLBoolBinaryFunction >)  pred 

Merge the contents of two lists.

Both lists must be sorted in the order defined by pred. All elements are removed from right and inserted in order into this list. This is a stable merge in that if two elements are equal, the one from this list will precede the one from right after the merge.

Parameters:
rightthe list to merge into this list
predthe function object that defines the sorting order
- (void) popBack

Remove the last element in the list.

Note:
If there are no elements in the list, then the behavior of this message is undefined.
- (void) popFront

Remove the first element in the list.

Note:
If there are no elements in the list, then the behavior of this message is undefined.
- (void) pushBack: (id)  object

Insert object at the end of the sequence.

Parameters:
objectthe object to insert

Reimplemented from <OLBackInserter>.

- (void) pushFront: (id)  object

Insert object at the beginning of the sequence.

Parameters:
objectthe object to insert

Reimplemented from <OLFrontInserter>.

Return a reverse iterator pointing to the end of the sequence.

Advancing the returned iterator will move backwards through the sequence to the point indicated by the iterator returned by rend.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
a reverse iterator for the end of the sequence
- (void) remove: (id)  object

Remove all objects equal to object.

For each element in the list this message performs an equivilance check using the message isEqual:, and if the check succeeds the element is removed from the list.

Precondition:
object must respond to the message isEqual:.
Parameters:
objectthe object with which to compare this list's members
- (void) removeIf: (id< OLBoolUnaryFunction >)  pred

Remove all objects for which pred returns YES.

For each element in the list this message uses the function object pred to test the element. If the function object returns YES, then the element is removed from the list.

Parameters:
predthe object to perform the check

Return a reverse iterator pointing to the beginning of the sequence.

This iterator indicates one position beyond the last position that may be referenced by a reverse iterator.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
a reverse iterator for the beginning of the sequence
- (void) resize: (unsigned)  count
filledWith: (id)  value 

Resize the list to newsize.

If newsize is smaller than the current size, then the sequence will be truncated. If newsize is larger than the current size, then value will be inserted at the end of the list as many times as necessary to fill the new size.

Parameters:
countthe new size of the list
valuethe value with which to fill new elements, if necessary
- (void) reverse

Reverse the order of the list.

The elements are placed in reverse order.

- (unsigned) size

Return the number of elements in the list.

Returns:
the number of elements
- (void) sort

Sort the list in ascending order.

The function object OLLess is used to compare elements in the list to establish the order.

- (void) sortWith: (id< OLBoolBinaryFunction >)  pred

Sort the list.

The function object pred is used to compare elements in the list to establish the order.

Parameters:
predthe object used to compare elements
- (void) spliceAt: (OLListIterator *)  where
list: (OLList *)  right 

Splice another list into this one.

All elements are removed from right and inserted just before the element pointed to by where.

Precondition:
where must point to an element in this list.
Parameters:
wherethe position at which to perform the splice
rightthe list to splice to this one
- (void) spliceAt: (OLListIterator *)  where
list: (OLList *)  right
from: (OLListIterator *)  first 

Splice an element from another list into this one.

The element pointed to by first is removed from right and inserted into this list just before where.

Precondition:
where must point to an element in this list, and first must point to an element in right.
Parameters:
wherethe position at which to perform the splice
rightthe list that contains first
firstthe element in right to splice into this list
- (void) spliceAt: (OLListIterator *)  where
list: (OLList *)  right
from: (OLListIterator *)  first
to: (OLListIterator *)  last 

Splice a range of elements into this list.

The elements in the list right in the range [first, last) are removed from right and inserted into this list just before the element pointed to by where.

Precondition:
where must point to an element in this list, and first and last must refer to a valid range in right.
Parameters:
wherethe position at which to perform the splice
rightthe list that contains first and last
firstthe first element in the range to splice
lastone position beyond the last element in the range to splice
- (void) swap: (OLList *)  right

Swap this list with another one.

All elements in right will be placed into this list, and all elements in this list will be placed in right.

Parameters:
rightthe list with which to swap this one
- (void) unique

Remove all but one of each consecutive element in the list.

The first of equivilent elements is retained, and the others are removed. This message will only be useful if the list is sorted first, as only consecutive elements are compared.

- (void) uniqueWith: (id< OLBoolBinaryFunction >)  pred

Remove all but one of each consecutive element for which pred returns YES.

For any two consecutive elements for which pred returns YES only the first is retained in the list. All others are removed.

Parameters:
predthe function to use to compare list elements
- (void) writeSelfToStream: (OLObjectOutStream *)  stream

Write the object to a stream.

All instance variables are written to stream.

Parameters:
streamthe stream to which to write.

Reimplemented from <OLStreamable>.


Member Data Documentation

- (OLListNode*) node [protected]

The head of the list.


The documentation for this class was generated from the following file:

ObjectiveLibGenerated Sat Feb 15 2014 07:45:34, © 2004-2007 Will Mason