CPriorityQueue.h

00001 /*
00002  * synergy -- mouse and keyboard sharing utility
00003  * Copyright (C) 2003 Chris Schoeneman
00004  * 
00005  * This package is free software; you can redistribute it and/or
00006  * modify it under the terms of the GNU General Public License
00007  * found in the file COPYING that should have accompanied this file.
00008  * 
00009  * This package is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  */
00014 
00015 #ifndef CPRIORITYQUEUE_H
00016 #define CPRIORITYQUEUE_H
00017 
00018 #include "stdvector.h"
00019 #include <algorithm>
00020 #include <functional>
00021 
00023 
00028 template <class T, class Container = std::vector<T>,
00029 #if defined(_MSC_VER)
00030             class Compare = std::greater<Container::value_type> >
00031 #else
00032             class Compare = std::greater<typename Container::value_type> >
00033 #endif
00034 class CPriorityQueue {
00035 public:
00036     typedef typename Container::value_type value_type;
00037     typedef typename Container::size_type size_type;
00038     typedef typename Container::iterator iterator;
00039     typedef typename Container::const_iterator const_iterator;
00040     typedef Container container_type;
00041 
00042     CPriorityQueue() { }
00043     CPriorityQueue(Container& swappedIn) { swap(swappedIn); }
00044     ~CPriorityQueue() { }
00045 
00047 
00048 
00050     void                push(const value_type& v)
00051     {
00052         c.push_back(v);
00053         std::push_heap(c.begin(), c.end(), comp);
00054     }
00055 
00057     void                pop()
00058     {
00059         std::pop_heap(c.begin(), c.end(), comp);
00060         c.pop_back();
00061     }
00062 
00064     void                erase(iterator i)
00065     {
00066         c.erase(i);
00067         std::make_heap(c.begin(), c.end(), comp);
00068     }
00069 
00071     iterator            begin()
00072     {
00073         return c.begin();
00074     }
00075 
00077     iterator            end()
00078     {
00079         return c.end();
00080     }
00081 
00083     void                swap(CPriorityQueue<T, Container, Compare>& q)
00084     {
00085         c.swap(q.c);
00086     }
00087 
00089     void                swap(Container& c2)
00090     {
00091         c.swap(c2);
00092         std::make_heap(c.begin(), c.end(), comp);
00093     }
00094 
00096 
00097 
00098 
00100     bool                empty() const
00101     {
00102         return c.empty();
00103     }
00104 
00106     size_type           size() const
00107     {
00108         return c.size();
00109     }
00110 
00112     const value_type&   top() const
00113     {
00114         return c.front();
00115     }
00116 
00118     const_iterator      begin() const
00119     {
00120         return c.begin();
00121     }
00122 
00124     const_iterator      end() const
00125     {
00126         return c.end();
00127     }
00128 
00130 
00131 private:
00132     Container           c;
00133     Compare             comp;
00134 };
00135 
00136 #endif

Generated on Fri Nov 6 00:18:45 2009 for synergy-plus by  doxygen 1.4.7