RWSortedVector Class Reference
[RWCollectable-derived]

Represents a group of ordered items. More...

#include <rw/sortvec.h>

Inheritance diagram for RWSortedVector:

List of all members.

Public Member Functions
virtual RWCollectable *	newSpecies () const
virtual RWClassID	isA () const
	RWSortedVector (size_t size=RWCollection::DEFAULT_CAPACITY)
	RWSortedVector (const RWSortedVector &sv)
	RWSortedVector (RWSortedVector &&sv)
RWSortedVector &	operator= (const RWSortedVector &sv)
RWSortedVector &	operator= (RWSortedVector &&sv)
bool	operator== (const RWSortedVector &sv) const
virtual const RWCollectable *	at (size_t) const
virtual size_t	index (const RWCollectable *target) const
virtual RWCollectable *	insert (RWCollectable *c)
virtual size_t	occurrencesOf (const RWCollectable *target) const
virtual bool	isEqual (const RWCollectable *a) const
const RWCollectable *	operator[] (size_t i) const
const RWCollectable *	operator() (size_t i) const
Static Public Member Functions
static RWClassID	classIsA ()
Private Member Functions
virtual RWCollectable *&	at (size_t)
virtual RWCollectable *	append (RWCollectable *a)
virtual RWCollectable *	insertAt (size_t, RWCollectable *)
virtual RWCollectable *	prepend (RWCollectable *)
void	push (RWCollectable *)
RWCollectable *	pop ()
RWCollectable *	top () const
Related Functions
(Note that these are not member functions.)
typedef RWOrderedIterator	RWSortedVectorIterator

---

Detailed Description

Class RWSortedVector represents a group of ordered items, internally sorted by the compareTo() function and accessible by an index number. Duplicates are allowed. An object stored by RWSortedVector must inherit from the abstract base class RWCollectable. An insertion sort is used to maintain the vector in sorted order.

Because class RWSortedVector is implemented as a vector of pointers, traversing the collection is more efficient than using RWBinaryTree. However, insertions are slower in the center of the collection.

Note:

The vector is sorted; do not modify elements contained in the vector in such a way as to invalidate the ordering.

Synopsis

 #include <rw/sortvec.h>
 RWSortedVector a;

Persistence

Polymorphic

Examples

 #include <rw/sortvec.h>
 #include <rw/collstr.h>

 int main ()
 {
     RWSortedVector sv;

     sv.insert(new RWCollectableString("monster"));
     sv.insert(new RWCollectableString("rabbit"));
     sv.insert(new RWCollectableString("hog"));
     sv.insert(new RWCollectableString("dog"));
     sv.insert(new RWCollectableString("cat"));
     sv.insert(new RWCollectableString("fish"));

     RWSortedVectorIterator next(sv);
     RWCollectableString* item;

     while( (item = (RWCollectableString*)next() ) != 0)
         std::cout << *item << std::endl;

     sv.clearAndDestroy();

     return 0;
 }

Program output:

 cat
 dog
 fish
 hog
 monster
 rabbit

---

Constructor & Destructor Documentation

RWSortedVector::RWSortedVector

(

size_t

size = RWCollection::DEFAULT_CAPACITY

)

Constructs an empty RWSortedVector that has an initial capacity of size items. The capacity will be increased automatically as needed.

RWSortedVector::RWSortedVector

(

const RWSortedVector &

sv

)

[inline]

Copy constructor. Makes a shallow copy of sv.

RWSortedVector::RWSortedVector

(

RWSortedVector &&

sv

)

[inline]

Move constructor. The constructed RWSortedVector takes ownership of the data owned by sv.

Condition:

This method is only available on platforms with rvalue reference support.

---

Member Function Documentation

virtual RWCollectable* RWSortedVector::append

(

RWCollectable *

a

)

[private, virtual]

Adds a to the end of the collection and returns it. Returns rwnil if the insertion was unsuccessful.

Reimplemented from RWOrdered.

virtual RWCollectable*& RWSortedVector::at

(

size_t

i

)

[private, virtual]

Allows access to the i ^th element of the collection. The return value can be used as an lvalue. The index i must be between zero and the number of items in the collection less one, or the function throws an exception of type RWBoundsErr.

Reimplemented from RWOrdered.

virtual const RWCollectable* RWSortedVector::at

(

size_t

i

)

const [virtual]

Allows access to the i ^th element of the collection. The return value cannot be used as an lvalue. The index i must be between zero and the number of items in the collection less one, or an exception of type RWBoundsErr will be thrown.

Reimplemented from RWOrdered.

static RWClassID RWSortedVector::classIsA

(

)

[static]

Returns the RWClassID of this class.

Reimplemented from RWOrdered.

virtual size_t RWSortedVector::index

(

const RWCollectable *

target

)

const [virtual]

Performs a binary search to return the index of the first item that compares equal to the target item, or RW_NPOS if no such item can be found.

Note:

Derived methods RWOrdered::find() and RWOrdered::remove() use this virtual function to perform their search. Hence, these methods called on an instance of RWSortedVector results in a binary search.

Reimplemented from RWOrdered.

virtual RWCollectable* RWSortedVector::insert

(

RWCollectable *

c

)

[virtual]

Performs a binary search to insert the item pointed to by c after all items that compare less than or equal to it, but before all items that compare greater to it. Returns c if the insertion was successful, otherwise returns rwnil.

Reimplemented from RWOrdered.

virtual RWCollectable* RWSortedVector::insertAt	(	size_t	indx,
		RWCollectable *	e
	)			[private, virtual]

Adds a new item to the collection at position indx. The item previously at position i is moved to i+1, etc. The index indx must be between 0 and the number of items in the collection, or an exception of type RWBoundsErr will be thrown.

Reimplemented from RWOrdered.

virtual RWClassID RWSortedVector::isA

(

)

const [virtual]

Returns __RWSORTEDVECTOR, i.e. a class identifier, that identifies this object's class.

Reimplemented from RWOrdered.

virtual bool RWSortedVector::isEqual

(

const RWCollectable *

a

)

const [virtual]

Returns true or false based on operator==().

Reimplemented from RWOrdered.

virtual RWCollectable* RWSortedVector::newSpecies

(

)

const [virtual]

Allocates a new object off the heap of the same type as self and returns a pointer to it. You are responsible for deleting the object when done with it.

Reimplemented from RWOrdered.

virtual size_t RWSortedVector::occurrencesOf

(

const RWCollectable *

target

)

const [virtual]

Returns the number of items that compare isEqual() to the item pointed to by target.

Reimplemented from RWOrdered.

const RWCollectable* RWSortedVector::operator()

(

size_t

i

)

const [inline]

Returns the i ^th element in the collection. Bounds checking is enabled by defining the preprocessor directive RWBOUNDS_CHECK before including the header file <rw/sortvec.h>. In this case, if i is out of range, an exception of type RWBoundsErr is thrown. The return value cannot be used as an lvalue.

Reimplemented from RWOrdered.

RWSortedVector& RWSortedVector::operator=

(

RWSortedVector &&

sv

)

[inline]

Move assignment. Self takes ownership of the data owned by sv.

Condition:

This method is only available on platforms with rvalue reference support.

RWSortedVector& RWSortedVector::operator=

(

const RWSortedVector &

sv

)

[inline]

Assignment operator. Makes a shallow copy of o.

bool RWSortedVector::operator==

(

const RWSortedVector &

sv

)

const [inline]

Returns true if for every item in self, the corresponding item in sv at the same index isEqual(). The two collections must also have the same number of members.

const RWCollectable* RWSortedVector::operator[]

(

size_t

i

)

const [inline]

Returns the i ^th element in the collection. If i is out of range, an exception of type RWBoundsErr is thrown. The return value cannot be used as an lvalue.

Reimplemented from RWOrdered.

RWCollectable* RWSortedVector::pop

(

)

[private]

This is an alternative implementation of a stack to class RWSlistCollectablesStack. The last item in the collection is removed and returned. If there are no items in the collection, rwnil is returned.

Reimplemented from RWOrdered.

virtual RWCollectable* RWSortedVector::prepend

(

RWCollectable *

c

)

[private, virtual]

Adds c to the beginning of the collection and returns it. Returns rwnil if the insertion was unsuccessful.

Reimplemented from RWOrdered.

void RWSortedVector::push

(

RWCollectable *

c

)

[private]

This is an alternative implementation of a stack to class RWSlistCollectablesStack. The item pointed to by c is put at the end of the collection.

Reimplemented from RWOrdered.

RWCollectable* RWSortedVector::top

(

)

const [private]

This is an alternative implementation of a stack to class RWSlistCollectablesStack. The last item in the collection is returned. If there are no items in the collection, rwnil is returned.

Reimplemented from RWOrdered.

---

Friends And Related Function Documentation

typedef RWOrderedIterator RWSortedVectorIterator [related]

RWSortedVectorIterator is a typedef for RWOrderedIterator. For information on how to use it, please see RWOrderedIterator.