NAME

OTC_OrderedList - A collection class based on an ordered list.

SYNOPSIS


#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;
};

CLASS TYPE

Concrete

DESCRIPTION

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.

INITIALISATION

OTC_OrderedList(int (*theRankFn)(T const&,T const&)=0);
OTC_OrderedList(OTC_OrderedList<T> const& theList);

DESTRUCTION

void removeAll();

INSERTION

OTC_OrderedList<T>& operator=(OTC_OrderedList<T> const& theList);
u_int add(T const& theItem);

QUERY

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;

REMOVAL

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);

ITERATION

By default, iterators will perform reference counts on the buckets in the collection as the iterator moves over the items. Performing the reference counts ensures that the iterator is not corrupted by additions or removals to the collection. If an unsafe iterator is required, for example, to avoid grabbing a write lock when using ObjectStore, a second argument can be passed to the following functions. The value of this argument is either 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;

NOTES

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

SEE ALSO

OTC_Iterator, OTC_Bucket, OTC_BaseActions, OTC_RankActions, OTC_AVLTree

LIBRARY

OTC

AUTHOR(S)

Graham Dumpleton

COPYRIGHT

Copyright 1992 1993 OTC LIMITED
Copyright 1994 DUMPLETON SOFTWARE CONSULTING PTY LIMITED