Wiselib
wiselib.testing/util/pstl/priority_queue.h
Go to the documentation of this file.
00001 /***************************************************************************
00002  ** This file is part of the generic algorithm library Wiselib.           **
00003  ** Copyright (C) 2008,2009 by the Wisebed (www.wisebed.eu) project.      **
00004  **                                                                       **
00005  ** The Wiselib is free software: you can redistribute it and/or modify   **
00006  ** it under the terms of the GNU Lesser General Public License as        **
00007  ** published by the Free Software Foundation, either version 3 of the    **
00008  ** License, or (at your option) any later version.                       **
00009  **                                                                       **
00010  ** The Wiselib is distributed in the hope that it will be useful,        **
00011  ** but WITHOUT ANY WARRANTY; without even the implied warranty of        **
00012  ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         **
00013  ** GNU Lesser General Public License for more details.                   **
00014  **                                                                       **
00015  ** You should have received a copy of the GNU Lesser General Public      **
00016  ** License along with the Wiselib.                                       **
00017  ** If not, see <http://www.gnu.org/licenses/>.                           **
00018  ***************************************************************************/
00019 #ifndef __WISELIB_INTERNAL_INTERFACE_STL_PRIORITY_QUEUE_H
00020 #define __WISELIB_INTERNAL_INTERFACE_STL_PRIORITY_QUEUE_H
00021 
00022 #include "util/pstl/iterator.h"
00023 
00024 namespace wiselib
00025 {
00026 
00027    template<typename OsModel_P,
00028             typename Value_P,
00029             int QUEUE_SIZE>
00030    class priority_queue
00031    {
00032    public:
00033       typedef Value_P value_type;
00034       typedef value_type* pointer;
00035 
00036       typedef typename OsModel_P::size_t size_type;
00037       // --------------------------------------------------------------------
00038       priority_queue()
00039       {
00040          start_ = &vec_[0];
00041          finish_ = start_;
00042          end_of_storage_ = start_ + QUEUE_SIZE;
00043       }
00044       // --------------------------------------------------------------------
00045       priority_queue( const priority_queue& pq )
00046       { *this = pq; }
00047       // --------------------------------------------------------------------
00048       ~priority_queue() {}
00049       // --------------------------------------------------------------------
00050       priority_queue& operator=( const priority_queue& pq )
00051       {
00052          memcpy( vec_, pq.vec_, sizeof(vec_) );
00053          start_ = &vec_[0];
00054          finish_ = start_ + (pq.finish_ - pq.start_);
00055          end_of_storage_ = start_ + QUEUE_SIZE;
00056          return *this;
00057       }
00058       // --------------------------------------------------------------------
00061       size_type size()
00062       { return size_type(finish_ - start_); }
00063       // --------------------------------------------------------------------
00064       size_type max_size()
00065       { return QUEUE_SIZE; }
00066       // --------------------------------------------------------------------
00067       size_type capacity()
00068       { return QUEUE_SIZE; }
00069       // --------------------------------------------------------------------
00070       bool empty()
00071       { return size() == 0; }
00072       // --------------------------------------------------------------------
00073       pointer data()
00074       { return pointer(this->start_); }
00076       // --------------------------------------------------------------------
00079       value_type top()
00080       {
00081          return vec_[0];
00082       }
00084       // --------------------------------------------------------------------
00087       void clear()
00088       {
00089          finish_ = start_;
00090       }
00091       // --------------------------------------------------------------------
00092       void push( const value_type& x )
00093       {
00094          int i = size();
00095          while ( i != 0 && x < vec_[i/2] )
00096          {
00097             vec_[i] = vec_[i/2];
00098             i = i/2;
00099          }
00100          vec_[i] = x;
00101          ++finish_;
00102       }
00103       // --------------------------------------------------------------------
00104       value_type pop()
00105       {
00106          int n = size() - 1;
00107          value_type e = vec_[0];
00108          value_type x = vec_[n];
00109          --finish_;
00110          int i = 0;
00111          int c = 1;
00112          while ( c <= n )
00113          {
00114             if ( c < n && vec_[c + 1] < vec_[c] )
00115                ++c;
00116             if ( !( vec_[c] < x ) )
00117                break;
00118             vec_[i] = vec_[c];
00119             i = c;
00120             c = 2 * i;
00121          }
00122          vec_[i] = x;
00123          return e;
00124       }
00126 
00127    protected:
00128       value_type vec_[QUEUE_SIZE];
00129 
00130       pointer start_, finish_, end_of_storage_;
00131    };
00132 
00133 }
00134 
00135 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines