00001 // -*- c++ -*- 00002 //------------------------------------------------------------------------------ 00003 // PriorityQueue_Impl.h 00004 //------------------------------------------------------------------------------ 00005 // Copyright (C) 1997-2002 Vladislav Grinchenko 00006 // 00007 // This library is free software; you can redistribute it and/or 00008 // modify it under the terms of the GNU Library General Public 00009 // License as published by the Free Software Foundation; either 00010 // version 2 of the License, or (at your option) any later version. 00011 //------------------------------------------------------------------------------ 00012 // Created: 09/17/1999 00013 //------------------------------------------------------------------------------ 00014 00015 #ifndef PRIORITY_QUEUE_IMPL_H 00016 #define PRIORITY_QUEUE_IMPL_H 00017 00018 namespace ASSA { 00019 00024 // less<> is borrowed from STL implementation. 00025 00029 template <class Arg1, class Arg2, class Result> 00030 struct Bfunc { 00031 typedef Arg1 first_argument_type; 00032 typedef Arg2 second_argument_type; 00033 typedef Result result_type; 00034 }; 00035 00036 00040 template <class T> 00041 struct Less : public Bfunc<T, T, bool> { 00042 bool operator()(const T& x, const T& y) const { return x < y; } 00043 }; 00044 00045 00052 template< class T, class Compare > 00053 class PriorityQueue_Impl 00054 { 00055 public: 00056 virtual ~PriorityQueue_Impl (); 00057 00058 virtual void insert (const T&) =0; 00059 virtual T pop () =0; 00060 virtual const T& top () const =0; 00061 virtual bool remove (T) =0; 00062 virtual size_t size () =0; 00063 virtual T& operator[] (int) =0; 00064 }; 00065 00066 template<class T, class Compare> 00067 inline 00068 PriorityQueue_Impl<T, Compare>:: 00069 ~PriorityQueue_Impl () 00070 { 00071 // Here is the twist: we must provide a definition for the virtual 00072 // destructor. We need the definition here because the way virtual 00073 // destructors work. Most derived class's destructor is called first, 00074 // then the destructor of each base class is called. That means that 00075 // the compiler will generate a call to ~PriorityQueue_Impl, even 00076 // though the class is abstract - that's why we need body here. 00077 00078 /* no-op */ 00079 } 00080 00081 } // end namespace ASSA 00082 00083 #endif /* PRIORITY_QUEUE_IMPL_H */
1.4.6