boost/pending/mutable_queue.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_MUTABLE_QUEUE_HPP
0012 #define BOOST_MUTABLE_QUEUE_HPP
0013
0014 #include <vector>
0015 #include <algorithm>
0016 #include <functional>
0017 #include <boost/property_map/property_map.hpp>
0018 #include <boost/pending/mutable_heap.hpp>
0019 #include <boost/pending/is_heap.hpp>
0020 #include <boost/graph/detail/array_binary_tree.hpp>
0021 #include <iterator>
0022
0023 namespace boost
0024 {
0025
0026 // The mutable queue whose elements are indexed
0027 //
0028 // This adaptor provides a special kind of priority queue that has
0029 // and update operation. This allows the ordering of the items to
0030 // change. After the ordering criteria for item x changes, one must
0031 // call the Q.update(x)
0032 //
0033 // In order to efficiently find x in the queue, a functor must be
0034 // provided to map value_type to a unique ID, which the
0035 // mutable_queue will then use to map to the location of the
0036 // item. The ID's generated must be between 0 and N, where N is the
0037 // value passed to the constructor of mutable_queue
0038
0039 template < class IndexedType,
0040     class RandomAccessContainer = std::vector< IndexedType >,
0041     class Comp = std::less< typename RandomAccessContainer::value_type >,
0042     class ID = identity_property_map >
0043 class mutable_queue
0044 {
0045 public:
0046     typedef IndexedType value_type;
0047     typedef typename RandomAccessContainer::size_type size_type;
0048
0049 protected:
0050     typedef typename RandomAccessContainer::iterator iterator;
0051 #if !defined BOOST_NO_STD_ITERATOR_TRAITS
0052     typedef array_binary_tree_node< iterator, ID > Node;
0053 #else
0054     typedef array_binary_tree_node< iterator, value_type, ID > Node;
0055 #endif
0056     typedef compare_array_node< RandomAccessContainer, Comp > Compare;
0057     typedef std::vector< size_type > IndexArray;
0058
0059 public:
0060     typedef Compare value_compare;
0061     typedef ID id_generator;
0062
0063     mutable_queue(size_type n, const Comp& x, const ID& _id)
0064     : index_array(n), comp(x), id(_id)
0065     {
0066         c.reserve(n);
0067     }
0068     template < class ForwardIterator >
0069     mutable_queue(ForwardIterator first, ForwardIterator last, const Comp& x,
0070         const ID& _id)
0071     : index_array(std::distance(first, last)), comp(x), id(_id)
0072     {
0073         while (first != last)
0074         {
0075             push(*first);
0076             ++first;
0077         }
0078     }
0079
0080     bool empty() const { return c.empty(); }
0081
0082     void pop()
0083     {
0084         value_type tmp = c.back();
0085         c.back() = c.front();
0086         c.front() = tmp;
0087
0088         size_type id_f = get(id, c.back());
0089         size_type id_b = get(id, tmp);
0090         size_type i = index_array[id_b];
0091         index_array[id_b] = index_array[id_f];
0092         index_array[id_f] = i;
0093
0094         c.pop_back();
0095         Node node(c.begin(), c.end(), c.begin(), id);
0096         down_heap(node, comp, index_array);
0097     }
0098     void push(const IndexedType& x)
0099     {
0100         c.push_back(x);
0101         /*set index-array*/
0102         index_array[get(id, x)] = c.size() - 1;
0103         Node node(c.begin(), c.end(), c.end() - 1, id);
0104         up_heap(node, comp, index_array);
0105     }
0106
0107     void update(const IndexedType& x)
0108     {
0109         size_type current_pos = index_array[get(id, x)];
0110         c[current_pos] = x;
0111
0112         Node node(c.begin(), c.end(), c.begin() + current_pos, id);
0113         update_heap(node, comp, index_array);
0114     }
0115
0116     value_type& front() { return c.front(); }
0117     value_type& top() { return c.front(); }
0118
0119     const value_type& front() const { return c.front(); }
0120     const value_type& top() const { return c.front(); }
0121
0122     size_type size() const { return c.size(); }
0123
0124     void clear() { c.clear(); }
0125
0126 #if 0
0127         // dwa 2003/7/11 - I don't know what compiler is supposed to
0128         // be able to compile this, but is_heap is not standard!!
0129     bool test() {
0130       return std::is_heap(c.begin(), c.end(), Comp());
0131     }
0132 #endif
0133
0134 protected:
0135     IndexArray index_array;
0136     Compare comp;
0137     RandomAccessContainer c;
0138     ID id;
0139 };
0140
0141 }
0142
0143 #endif // BOOST_MUTABLE_QUEUE_HPP