#include <OTC/collctn/ordlist.hh> template<class T> class OTC_OrderedList {
public:
static os_typespec* get_os_typespec();
~OTC_OrderedList();
OTC_OrderedList(int (*theRankFn)(T const&,T const&)=0);
OTC_OrderedList(OTC_OrderedList<T> const& theList);
void removeAll();
OTC_OrderedList<T>& operator=(OTC_OrderedList<T> const& theList);
u_int add(T const& theItem);
int index( T const& theItem, OTC_Occurrence theOccurrence=OTCLIB_ANY ) const;
OTC_Range range(T const& theItem) const;
T const& item(u_int theIndex) const;
T const& first() const;
T const& last() const;
OTC_Boolean contains(T const& theItem) const;
u_int frequency(T const& theItem) const;
inline u_int population() const;
inline OTC_Boolean isEmpty() const;
void removeAll(T const& theItem);
void removeFirst();
void removeLast();
void remove(T const& theItem);
void removeItem(u_int theIndex);
inline void removeRange(OTC_Range const& theRange);
inline void removeRange(u_int theStart, u_int theLength);
inline OTC_Iterator<T> items( OTC_Direction theDirection=OTCLIB_FORWARD, OTC_Protection theProtection=OTCLIB_SAFE ) const;
inline OTC_Iterator<T> items( OTC_Range const& theRange, OTC_Direction theDirection=OTCLIB_FORWARD, OTC_Protection theProtection=OTCLIB_SAFE ) const;
inline OTC_Iterator<T> items( u_int theStart, u_int theLength, OTC_Direction theDirection=OTCLIB_FORWARD, OTC_Protection theProtection=OTCLIB_SAFE ) const;
protected:
void _removeRange(int theStart, u_int theLength);
OTC_Cursor<T>* _items( OTC_Direction theDirection=OTCLIB_FORWARD, OTC_Protection theProtection=OTCLIB_SAFE ) const;
OTC_Cursor<T>* _items( int theStart, u_int theLength, OTC_Direction theDirection=OTCLIB_FORWARD, OTC_Protection theProtection=OTCLIB_SAFE ) const;
inline OTC_AVLTree* _tree() const;
inline OTC_LinkList* _list() const;
};
OTC_OrderedList
implements a list of objects, where the order of
objects is always maintained. This is achieved by ranking objects,
so that objects of least rank are located at the head of the list.
The ordering can be dictated by the user by defining an explicit
version of OTC_RankActions
, for the type that the list is
parameterised over.
OTC_OrderedList(int (*theRankFn)(T const&,T const&)=0);
theRankFn
is
a rank function to be used instead of
OTC_RankActions
.
OTC_OrderedList(OTC_OrderedList<T> const& theList);
theList
.
void removeAll();
OTC_OrderedList<T>& operator=(OTC_OrderedList<T> const& theList);
theList
.
Returns a reference to this list.
u_int add(T const& theItem);
theItem
into the list. Note that
duplicates are allowed. If you do not want
duplicates, you should check by calling
the contains()
function for an existing
item, before adding the item in. The index
where the item was added will be
returned, with 0
being the first
location. Note, that with subsequent
additions, this index may become invalid.
int index(
T const& theItem,
OTC_Occurrence theOccurrence=OTCLIB_ANY
) const;
theItem
within the
list. If there are multiple occurrences of
theItem
, the index of which item is
returned, is determined by theOccurrence
,
which can be either OTCLIB_ANY
,
OTCLIB_FIRST
or OTCLIB_LAST
, indicating
any item, the item with lowest index, or
the item with highest index respectively.
If theItem
doesn't exist, then -1
is
returned.
OTC_Range range(T const& theItem) const;
theItem
.
T const& item(u_int theIndex) const;
theIndex
. An
exception is raised if the index is
invalid.
T const& first() const;
T const& last() const;
OTC_Boolean contains(T const& theItem) const;
OTCLIB_TRUE
if theItem
exists.
u_int frequency(T const& theItem) const;
theItem
appears in the list.
inline u_int population() const;
inline OTC_Boolean isEmpty() const;
OTCLIB_TRUE
if the collection is
empty.
void removeAll(T const& theItem);
theItem
.
void removeFirst();
void removeLast();
void remove(T const& theItem);
theItem
found.
void removeItem(u_int theIndex);
theIndex
. Raises an exception if
theIndex
is invalid.
inline void removeRange(OTC_Range const& theRange);
theStart
through theEnd
. If the list is
empty, or any of the items do not
exist, an exception is raised.
inline void removeRange(u_int theStart, u_int theLength);
theLength
starting at index theStart
.
If the list is empty, or any of the items
do not exist, an exception is raised.
OTCLIB_SAFE
or OTCLIB_UNSAFE
.
To get an unsafe iterator, the OTCLIB_UNSAFE
argument should
be used.
The first argument to the following functions indicates the
direction of traversal of the iterator. Traversal in the
direction of first to last item is indicated by a value of
OTCLIB_FORWARD
. Traversal in the reverse direction is
indicated by a value of OTCLIB_BACkWARD
. The default value
is OTCLIB_FORWARD
. In the OTC_OrderedList
class, traversal
in the forward direction will result in the first item being
available being the least ranked item.
inline OTC_Iterator<T> items(
OTC_Direction theDirection=OTCLIB_FORWARD,
OTC_Protection theProtection=OTCLIB_SAFE
) const;
inline OTC_Iterator<T> items(
OTC_Range const& theRange,
OTC_Direction theDirection=OTCLIB_FORWARD,
OTC_Protection theProtection=OTCLIB_SAFE
) const;
inline OTC_Iterator<T> items(
u_int theStart,
u_int theLength,
OTC_Direction theDirection=OTCLIB_FORWARD,
OTC_Protection theProtection=OTCLIB_SAFE
) const;
OTC_Bucket
class is used internally to hold items in
the list. Thus, the OTC_BaseActions
class may be used to provide
actions to be performed, when items are inserted or removed from
the list.
Duplicates are allowed in the list. However users should be aware,
that the order in which similarly ranked items are ordered is
undefined. When adding in a duplicate, it may be added before, or
after the existing item. In addition, when removing an item using
an instance of an item, if there is a similarly ranked item found
before the actual one being used as the lookup item, it will be
removed. If more deterministic control is required, the
OTC_AVLTree
class may be used to implement a new list.
When parameterised over a pointer type, where the rank is based on
a part of the object and not the value of the pointer, it is
important that the list be parameterised over a pointer to const
object. If this is not done, it would be possible for someone
to change the object while it is in the list, thus corrupting the
ordering within the list.
OTC_Iterator
, OTC_Bucket
, OTC_BaseActions
,
OTC_RankActions
, OTC_AVLTree