OLDeque Class Reference
[Containers]

A double-ended queue. More...

#import <ObjectiveLib/Deque.h>

Inheritance diagram for OLDeque:

[legend]List of all members.

Public Member Functions
(void)	- assign:filledWith:
	Assign objects to the deque.
(void)	- assignAt:value:
	Assign object to the position at index.
(void)	- assignFrom:to:
	Assign a range of objects to the deque.
(id)	- at:
	Return the object at index.
(id)	- back
	Return the last object in the deque.
(OLDequeIterator *)	- begin
	Return an iterator pointing to the beginning of the sequence.
(void)	- clear
	Remove all elements.
(int)	- compare:
	Compare this deque to another object.
(id)	- copy
	Make a copy of this deque.
(BOOL)	- empty
	Test whether the deque is empty.
(OLDequeIterator *)	- end
	Return an iterator pointing to one position beyond the end of the sequence.
(OLDequeIterator *)	- erase:
	Remove the element designated by where.
(OLDequeIterator *)	- eraseFrom:to:
	Remove a range of elements.
(id)	- front
	Return the first object in the deque.
(void)	- insertAt:count:filledWith:
	Insert a number of objects into the deque.
(void)	- insertAt:from:to:
	Insert a range of objects into the deque.
(OLDequeIterator *)	- insertAt:value:
	Insert an object into the deque.
(BOOL)	- isEqual:
	Return whether this deque is equal to another one.
(unsigned)	- maxSize
	Return the maxiumum number of objects that can be stored in a deque.
(void)	- popBack
	Remove the last element in the deque.
(void)	- popFront
	Remove the first element in the deque.
(void)	- pushBack:
	Insert object at the end of the sequence.
(void)	- pushFront:
	Insert object at the beginning of the sequence.
(OLReverseRandomIterator *)	- rbegin
	Return a reverse iterator pointing to the end of the sequence.
(OLReverseRandomIterator *)	- rend
	Return a reverse iterator pointing to the beginning of the sequence.
(void)	- resize:filledWith:
	Resize the deque to newsize.
(unsigned)	- size
	Return the number of elements in the deque.
(void)	- swap:
	Swap this deque with another one.
(void)	- writeSelfToStream:
	Write the object to a stream.
Initializers and Deallocators
(id)	- free
	Finalize the deque and deallocate any allocated memory.
(id)	- init
	Initialize the deque.
(id)	- initFrom:to:
	Initialize the deque.
(id)	- initWithDeque:
	Initialize the deque.
(id)	- initWithObjectInStream:
	Initialize the object.
(id)	- initWithSize:filledWith:
	Initialize the deque.
Static Public Member Functions
(id)	+ deque
	Create and return a new deque.
(id)	+ dequeFrom:to:
	Create and return a new deque.
(id)	+ dequeWithDeque:
	Create and return a new deque.
(id)	+ dequeWithSize:filledWith:
	Create and return a new deque.
Protected Attributes
OLDequeIterator *	finish
	The end of the sequence.
id **	map
	The map of deque nodes.
unsigned	mapSize
	The number of nodes.
OLDequeIterator *	start
	The beginning of the sequence.

---

Detailed Description

A double-ended queue.

A double-ended queue is similar to a vector or array, except that its storage is additionally optimized for insertion and removal from the beginning of the sequence as well as from the end. It provides random access to its elements. It also serves as a suitable container for use by OLBackInsertIterator, OLFrontInsertIterator and OLInsertIterator.

See also:

OLDequeIterator

---

Member Function Documentation

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

Assign objects to the deque.

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

Parameters:

	count	the number of elements to assign
	value	the object to be copied into the deque

- (void) assignAt:		(unsigned)	index
value:		(id)	object

Assign object to the position at index.

The object currently in possession of the position at index is removed and replaced with object.

Note:

The range of the deque is not checked prior to performing this operation. Using values of index that do not lie within the deque's range will produce undefined results.

Parameters:

	index	the index to which to assign
	object	the object to put at index

- (void) assignFrom:		(OLForwardIterator *)	first
to:		(OLForwardIterator *)	last

Assign a range of objects to the deque.

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

Parameters:

	first	the first in the range of objects to assign
	last	one beyond the last in the range of objects to assign

- (id) at:

(unsigned)

index

Return the object at index.

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

Note:

The range of the deque is not checked prior to performing this operation. Using values of index that do not lie within the deque's range will produce undefined results.

Parameters:

index

the index of the object to look up

Returns:

a reference to the object at index

- (id) back

Return the last object in the deque.

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

Note:

The behavior of this message is undefined if the deque is empty.

Returns:

the last object

- (OLDequeIterator*) begin

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 deque to another object.

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

Parameters:

other

the 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) copy

Make a copy of this deque.

Returns:

the copy

+ (id) deque

Create and return a new deque.

The deque is empty.

Note:

If OpenStep is present the returned object will be autoreleased before being returned.

Returns:

a new deque

+ (id) dequeFrom:		(OLForwardIterator *)	first
to:		(OLForwardIterator *)	last

Create and return a new deque.

The deque 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:

	first	the first in the range of elements to insert
	last	one beyond the last in the range of elements to insert

Returns:

a new deque

+ (id) dequeWithDeque:

(OLDeque *)

right

Create and return a new deque.

The deque is initialized with the contents of right.

Note:

If OpenStep is present the returned object will be autoreleased before being returned.

Parameters:

right

the deque with which to initialize the new one

Returns:

a new deque

+ (id) dequeWithSize:		(unsigned)	size
filledWith:		(id)	value

Create and return a new deque.

The deque 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:

	size	the number of elements to insert
	value	the object to be copied

Returns:

a new deque

- (BOOL) empty

Test whether the deque is empty.

Returns:

YES if the deque is empty, NO otherwise

- (OLDequeIterator*) end

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

- (OLDequeIterator*) erase:

(OLDequeIterator *)

where

Remove the element designated by where.

Precondition:

where must point to an element in this deque.

Note:

If OpenStep is present the returned object will be autoreleased before being returned.

Parameters:

where

an iterator designating the element to remove

Returns:

an iterator indicating the next element in the sequence remaining after where

- (OLDequeIterator*) eraseFrom:		(OLDequeIterator *)	first
to:		(OLDequeIterator *)	last

Remove a range of elements.

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

Precondition:

first and last must refer to elements in this deque.

Note:

If OpenStep is present the returned object will be autoreleased before being returned.

Parameters:

	first	the first in the range of elements to remove
	last	one 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) free

Finalize the deque and deallocate any allocated memory.

- (id) front

Return the first object in the deque.

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

Note:

The behavior of this message is undefined if the deque is empty.

Returns:

the first object

- (id) init

Initialize the deque.

The deque begins life empty.

Returns:

a reference to this deque

- (id) initFrom:		(OLForwardIterator *)	first
to:		(OLForwardIterator *)	last

Initialize the deque.

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

Parameters:

	first	the first in the range of elements to insert
	last	one beyond the last in the range of elements to insert

Returns:

a reference to this deque

- (id) initWithDeque:

(OLDeque *)

deque

Initialize the deque.

The deque is initialized with the contents of the give deque.

Parameters:

deque

the deque to copy

Returns:

a reference to this deque

- (id) initWithObjectInStream:

(OLObjectInStream *)

stream

Initialize the object.

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

Parameters:

stream

the stream from which to read

Returns:

a reference to this object

Reimplemented from < OLStreamable >.

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

Initialize the deque.

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

Parameters:

	count	the number of elements to insert
	value	the object to be copied

Returns:

a reference to this deque

- (void) insertAt:		(OLDequeIterator *)	where
count:		(unsigned)	num
filledWith:		(id)	value

Insert a number of objects into the deque.

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 deque

Parameters:

	where	the position at which to insert the objects
	num	the number of objects to insert
	value	the object to be copied into the deque

- (void) insertAt:		(OLDequeIterator *)	where
from:		(OLForwardIterator *)	first
to:		(OLForwardIterator *)	last

Insert a range of objects into the deque.

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:

	where	the position at which to insert the objects
	first	the first in the range of objects to insert
	last	one position beyond the last in the range of objects to insert

- (OLDequeIterator*) insertAt:		(OLDequeIterator *)	where
value:		(id)	object

Insert an object into the deque.

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 deque

Note:

If OpenStep is present the returned object will be autoreleased before being returned.

Parameters:

	where	the position at which to insert object
	object	the object to insert

Returns:

an iterator pointing to the newly inserted object

- (BOOL) isEqual:

(id)

object

Return whether this deque is equal to another one.

Two deques 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:

object

the object to test

Returns:

YES if object is equal to this deque

Reimplemented from < OLBackInserter >.

- (unsigned) maxSize

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

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

Returns:

the maximum number of objects for a deque

- (void) popBack

Remove the last element in the deque.

Note:

If there are no elements in the deque, then the behavior of this message is undefined.

- (void) popFront

Remove the first element in the deque.

Note:

If there are no elements in the deque, then the behavior of this message is undefined.

- (void) pushBack:

(id)

object

Insert object at the end of the sequence.

Parameters:

object

the object to insert

Reimplemented from < OLBackInserter >.

- (void) pushFront:

(id)

object

Insert object at the beginning of the sequence.

Parameters:

object

the object to insert

Reimplemented from < OLFrontInserter >.

- (OLReverseRandomIterator*) rbegin

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

- (OLReverseRandomIterator*) rend

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)	newsize
filledWith:		(id)	value

Resize the deque 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 deque as many times as necessary to fill the new size.

Parameters:

	newsize	the new size of the deque
	value	the value with which to fill new elements, if necessary

- (unsigned) size

Return the number of elements in the deque.

Returns:

the number of elements

- (void) swap:

(OLDeque *)

right

Swap this deque with another one.

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

Parameters:

right

the deque with which to swap this one

- (void) writeSelfToStream:

(OLObjectOutStream *)

stream

Write the object to a stream.

All instance variables are written to stream.

Parameters:

stream

the stream to which to write.

Reimplemented from < OLStreamable >.

---

Member Data Documentation

- (OLDequeIterator*) finish [protected]

The end of the sequence.

- (id**) map [protected]

The map of deque nodes.

- (unsigned) mapSize [protected]

The number of nodes.

- (OLDequeIterator*) start [protected]

The beginning of the sequence.

---

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

• Deque.h

---

Generated Sun Apr 22 15:18:25 2007, © 2004-2007 Will Mason