NAME

OTC_PriorityQueue - Implements a priority queue.

SYNOPSIS


#include <OTC/collctn/priqueue.hh>

template<class T>
class OTC_PriorityQueue
{
  public:
    static os_typespec* get_os_typespec();
    OTC_PriorityQueue(OTC_QueueType theType=OTCLIB_ASCENDING);
    OTC_PriorityQueue(int (*theRankFn)(
      T const&,
      T const&),
      OTC_QueueType theType=OTCLIB_ASCENDING
    );
    OTC_PriorityQueue(OTC_PriorityQueue<T> const& theQueue);
    ~OTC_PriorityQueue();
    OTC_Boolean isEmpty() const;
    inline u_int count() const;
    T const& head() const;
    void add(T const& theItem);
    T remove();
    void clear();
    void discard(u_int theCount);
  protected:
    OTC_PriorityQueue<T>& operator=(
      OTC_PriorityQueue<T> const& theQueue
    );
};

CLASS TYPE

Concrete

DESCRIPTION

This class implements a priority queue. This is different to a normal queue in that items are not added to the end of the queue, but are inserted into the queue based on an intrinsic ordering. This ordering can be dictated by the user, by defining an explicit version of OTC_RankActions for the type that the queue is parameterised over. For a particular instance of the class, a function which determines the ordering, may also be passed to the constructor. The priority queue can be instantiated in two forms, either as an ascending queue, or a descending queue. In an ascending queue, a remove() operation will remove the least ranked item in the queue. In a descending queue, the highest ranked item will be removed. In situations where a particular type of queue must be ensured, the derived versions of this class can be used. The derived classes are OTC_AscendingQueue and OTC_DescendingQueue. Note that it is the user's responsibility to deal with deletion of objects held in the queue, when it is parameterised over a pointer type, ie., this class works independently of the OTC_BaseActions class.

INITIALISATION

OTC_PriorityQueue(OTC_QueueType theType=OTCLIB_ASCENDING);
OTC_PriorityQueue(int (*theRankFn)(
  T const&,
  T const&),
  OTC_QueueType theType=OTCLIB_ASCENDING
);
OTC_PriorityQueue(OTC_PriorityQueue<T> const& theQueue);

DESTRUCTION

~OTC_PriorityQueue();

QUERY

OTC_Boolean isEmpty() const;
inline u_int count() const;
T const& head() const;

MODIFICATION

void add(T const& theItem);
T remove();
void clear();
void discard(u_int theCount);

NOTES

Duplicates, or items of equivalent rank, are permitted in the queue. When duplicates are inserted the ordering of similar items is undefined. A duplicate item will not necessarily be placed into the queue after that which already existed; it may be placed before it.

SEE ALSO

OTC_AscendingQueue, OTC_DescendingQueue, OTC_Queue, OTC_RankActions

LIBRARY

OTC

AUTHOR(S)

Graham Dumpleton

COPYRIGHT

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