Main Page Modules Class Hierarchy Data Structures File List Data Fields Globals Related Pages

# oscl_priqueue.h

Go to the documentation of this file.

    00001 // -*- c++ -*-
    00002 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
    00003
    00004 //       O S C L _ P R I Q U E U E   ( P R I O R I T Y   Q U E U E )
    00005
    00006 // = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
    00007
    00014 #ifndef OSCL_PRIQUEUE_H_INCLUDED
    00015 #define OSCL_PRIQUEUE_H_INCLUDED
    00016
    00017
    00018
    00030 #ifndef OSCL_BASE_H_INCLUDED
    00031 #include "oscl_base.h"
    00032 #endif
    00033
    00034
    00035 #ifndef OSCL_VECTOR_H_INCLUDED
    00036 #include "oscl_vector.h"
    00037 #endif
    00038
    00046 class OsclPriorityQueueBase
    00047 {
    00048     protected:
    00049         virtual ~OsclPriorityQueueBase()
    00050         {}
    00051
    00052         OSCL_IMPORT_REF void push_heap(OsclAny* first, OsclAny* last) ;
    00053
    00054         OSCL_IMPORT_REF void pop_heap(OsclAny* first, OsclAny* last) ;
    00055
    00056         OSCL_IMPORT_REF OsclAny* find_heap(const OsclAny* input, OsclAny* first, OsclAny* last) ;
    00057
    00058         OSCL_IMPORT_REF int remove(const OsclAny* input) ;
    00059
    00060         void construct(Oscl_Opaque_Type_Compare* ot, Oscl_Vector_Base* vec)
    00061         {
    00062             pOpaqueType = ot;
    00063             pVec = vec;
    00064         }
    00065
    00066     private:
    00067
    00068         //return delta from "first" to "last" expressed as a number of T elements.
    00069         int delta_T(OsclAny*first, OsclAny*last)
    00070         {
    00071             return ((int)last - (int)first) / pVec->sizeof_T;
    00072         }
    00073
    00074         Oscl_Opaque_Type_Compare* pOpaqueType;
    00075         Oscl_Vector_Base* pVec;
    00076 };
    00077
    00078 template < class T> class OsclCompareLess
    00079 {
    00080     public:
    00081         int compare(T& a, T& b) const
    00082         {
    00083             return (a < b);
    00084         }
    00085 };
    00086
    00087
    00088
    00089
    00090
    00091
    00092
    00093
    00094 template < class Qelem, class Alloc,
    00095 class Container = Oscl_Vector<Qelem, Alloc>,
    00096 class Compare = OsclCompareLess<Qelem> >
    00097
    00098 class OsclPriorityQueue : public OsclPriorityQueueBase
    00099         , public Oscl_Opaque_Type_Compare
    00100 {
    00101
    00102     public:
    00103         typedef typename Container::value_type  value_type;
    00104         typedef Container                       container_type;
    00105         typedef typename Container::iterator    iterator;
    00106         typedef typename Container::const_reference const_reference;
    00107
    00108         bool empty() const
    00109         {
    00110             return c.empty();
    00111         };
    00112         uint32 size() const
    00113         {
    00114             return c.size();
    00115         };
    00116         void reserve(uint32 n)
    00117         {
    00118             c.reserve(n);
    00119         };
    00120         const_reference top() const
    00121         {
    00122             return c.front();
    00123         };
    00124         const Container & vec()
    00125         {
    00126             return c;
    00127         }
    00128
    00129         void push(const value_type& input)
    00130         {
    00131             c.push_back(input);
    00132             push_heap(c.begin(), c.end());
    00133         }
    00134
    00135         //remove top element
    00136         void pop()
    00137         {
    00138             pop_heap(c.begin(), c.end());
    00139             c.pop_back();
    00140         }
    00141
    00142         //Remove an arbitrary element, by value.
    00143         //If there are multiple matches, this removes the first one it finds.
    00144         //Returns number of items removed(either 0 or 1).
    00145         int remove(const value_type& input)
    00146         {
    00147             return OsclPriorityQueueBase::remove(&input);
    00148         }
    00149
    00150         //Constructor
    00151         OsclPriorityQueue(): OsclPriorityQueueBase(), Oscl_Opaque_Type_Compare()
    00152                 , c()
    00153         {
    00154             OsclPriorityQueueBase::construct(this, &c);
    00155         }
    00156
    00157         virtual ~OsclPriorityQueue()
    00158         {}
    00159
    00160     protected:
    00161         Container c;
    00162         Compare comp;
    00163
    00164
    00165         void push_heap(iterator first, iterator last)
    00166         {
    00167             OsclPriorityQueueBase::push_heap(first, last);
    00168         }
    00169
    00170         void pop_heap(iterator first, iterator last)
    00171         {
    00172             OsclPriorityQueueBase::pop_heap(first, last);
    00173         }
    00174
    00175         iterator find_heap(const value_type& input, iterator first, iterator last)
    00176         {
    00177             return OsclPriorityQueueBase::find_heap(&input, first, last);
    00178         }
    00179
    00180         //a debug routine for validating the current sort.
    00181         int validate()
    00182         {
    00183             unsigned int ch;
    00184             for (unsigned int par = 0; par < c.size(); par++)
    00185             {
    00186                 ch = 2 * par + 1;
    00187                 if (ch < c.size() && comp.compare(c[par], c[ch]))
    00188                     return par;//error-- parent<child
    00189                 ch++;
    00190                 if (ch < c.size() && comp.compare(c[par], c[ch]))
    00191                     return par;//error-- parent<child
    00192             }
    00193             return -1;//ok
    00194         }
    00195
    00196         friend class oscl_priqueue_test;
    00197
    00198         //from Oscl_Opaque_Type_Compare
    00199         void swap(OsclAny* dest, const OsclAny* src)
    00200         {
    00201             OSCL_ASSERT(dest);
    00202             OSCL_ASSERT(src);
    00203             if (dest != src)
    00204             {
    00205                 value_type temp(*((value_type*)dest));
    00206                 *((value_type*)dest) = *((value_type*)src);
    00207                 *((value_type*)src) = temp;
    00208             }
    00209         }
    00210
    00211         //from Oscl_Opaque_Type_Compare
    00212         int compare_LT(OsclAny* a, OsclAny* b) const
    00213         {
    00214             OSCL_ASSERT(a);
    00215             OSCL_ASSERT(b);
    00216             return comp.compare(*((value_type*)a), *((value_type*)b));
    00217         }
    00218
    00219         //from Oscl_Opaque_Type_Compare
    00220         int compare_EQ(const OsclAny* a, const OsclAny* b) const
    00221         {
    00222             OSCL_ASSERT(a);
    00223             OSCL_ASSERT(b);
    00224             return (*((value_type*)a)) == (*((value_type*)b));
    00225
    00226         }
    00227
    00228 };
    00229
    00230 #endif
    00231