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

A queue that orders its elements by priority. More...

#import <ObjectiveLib/Queue.h>

Inheritance diagram for OLPriorityQueue:
Inheritance graph
[legend]

List of all members.

Public Member Functions

(int) - compare:
 Compare this queue to another object.
(id) - copyWithZone:
 Make a copy of this queue allocating memory from the given zone.
(BOOL) - empty
 Test whether the queue is empty.
(void) - encodeWithCoder:
 Encode the queue.
(BOOL) - isEqual:
 Return whether this queue is equal to another one.
(void) - pop
 Remove the highest priority item.
(void) - push:
 Add an item to the queue.
(unsigned) - size
 Return the number of elements in the queue.
(id) - top
 Return the highest priority element.
(void) - writeSelfToStream:
 Write the object to a stream.
Initializers and Deallocators
(id) - init
 Initialize the queue.
(id) - initFrom:to:
 Initialize the queue.
(id) - initFrom:to:predicate:
 Initialize the queue.
(id) - initWithCoder:
 Initialize the queue.
(id) - initWithObjectInStream:
 Initialize the object.
(id) - initWithPredicate:
 Initialize the queue.
(id) - initWithPriorityQueue:
 Initialize the queue.
(void) - dealloc
 Finalize the queue and deallocate any allocated memory.

Static Public Member Functions

(id) + priorityQueue
 Create and return a new queue.
(id) + priorityQueueFrom:to:
 Create and return a new queue.
(id) + priorityQueueFrom:to:predicate:
 Create and return a new queue.
(id) + priorityQueueWithPredicate:
 Create and return a new queue.
(id) + priorityQueueWithPriorityQueue:
 Create and return a new queue.

Protected Attributes

OLStreamableFunctor
< OLBoolBinaryFunction > * 
predicate
 The function object used to order the queue.
OLVectorvector
 The container that provides that underlying data structure.

Detailed Description

A queue that orders its elements by priority.

This is similar to a first-in-first-out queue in that elements are pushed to the back of the queue and retrieved from the head of the queue. The difference is that rather than ordering elements according to the order in which they were placed in the queue, the priority queue orders elements according to a function object that determines each elements priority. Thus, the priority queue's top (OLPriorityQueue) message retrieves the element with the highest priority regardless of when that element was placed in the queue. As with OLQueue, OLPriorityQueue is not a true container because it does not provide iterators, and therefore cannot be used with generic algorithms.

The function object that orders the elements considers the highest priority element to be the one that fails the comparison when compared to all other elements in the queue. Therefore, to create a queue where the largest elements are considered the ones of highest priority, the function OLLess should be used.

See also:
OLQueue

Member Function Documentation

- (int) compare: (id)  other

Compare this queue to another object.

If the other object is of type OLPriorityQueue, the underlying vector of this object will compared to the underlying vector of other using the compare: (OLVector) 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 queue allocating memory from the given zone.

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

Finalize the queue and deallocate any allocated memory.

- (BOOL) empty

Test whether the queue is empty.

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

Encode the queue.

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

Parameters:
encoderthe coder which will save the bit queue to the archive
- (id) init

Initialize the queue.

The queue is initially empty and the comparison function OLLess.

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

Initialize the queue.

The queue uses the comparison function OLLess. All elements in the range [first, last) are inserted into the queue.

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 queue
- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
predicate: (OLStreamableFunctor< OLBoolBinaryFunction > *)  pred 

Initialize the queue.

The queue uses the comparison function pred. All elements in the range [first, last) are inserted into the queue.

Note:
The predicate pred will order the queue in reverse order. Thus, the highest priority element is the one that fails to satisfy the predicate when compared to all other objects. Therefore, to order a queue in ascending order, with the largest element considered the highest priority, use the predicate OLLess.
Parameters:
firstthe first in the range of elements to insert
lastone beyond the last in the range of elements to insert
predthe function object used to order elements
Returns:
a reference to this queue
- (id) initWithCoder: (NSCoder *)  decoder

Initialize the queue.

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

Postcondition:
The queue returned will be identical to the queue saved to the archive using the encodeWithCoder: message.
Parameters:
decoderthe coder which will decode the archived queue
Returns:
a reference to this queue

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>.

Initialize the queue.

The queue is empty and uses the function object pred to order elements.

Parameters:
predthe function object used to order elements
Returns:
a reference to this queue

Initialize the queue.

The comparison function and all elements are copied from right into this queue.

Parameters:
rightthe queue to copy
Returns:
a reference to this queue
- (BOOL) isEqual: (id)  object

Return whether this queue is equal to another one.

Two queues 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 queue
- (void) pop

Remove the highest priority item.

The element returned by the message top is removed from the queue.

Precondition:
The queue cannot be empty.
+ (id) priorityQueue

Create and return a new queue.

An instance of OLLess is used to order the items by priority.

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

Create and return a new queue.

The queue is initialized with the contents of the range [first, last). An instance of OLLess is used to order the items by priority.

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 queue
+ (id) priorityQueueFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
predicate: (OLStreamableFunctor< OLBoolBinaryFunction > *)  pred 

Create and return a new queue.

The queue is initialized with the contents of the range [first, last), and pred is used to order the items by priority.

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
predthe function object used to order elements
Returns:
a new queue

Create and return a new queue.

The function object pred is used to order the items by priority.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
predthe function object used to order elements
Returns:
a new queue

Create and return a new queue.

The queue is initialized with the contents of the priority queue right.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
rightthe priority queue to copy into the new one
Returns:
a new queue
- (void) push: (id)  object

Add an item to the queue.

The element object will be added to the queue at whatever position is determined by predicate.

Parameters:
objectthe element to add
- (unsigned) size

Return the number of elements in the queue.

Returns:
the number of elements
- (id) top

Return the highest priority element.

This is the same element that will be removed by the message pop.

Returns:
the highest priority element
- (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

The function object used to order the queue.

- (OLVector*) vector [protected]

The container that provides that underlying data structure.


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

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