source: NonGTP/Boost/boost/pending/mutable_queue.hpp @ 857

Revision 857, 4.3 KB checked in by igarcia, 19 years ago (diff)
Line 
1//
2//=======================================================================
3// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
4// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
5//
6// Distributed under the Boost Software License, Version 1.0. (See
7// accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//=======================================================================
10//
11#ifndef BOOST_MUTABLE_QUEUE_HPP
12#define BOOST_MUTABLE_QUEUE_HPP
13
14#include <vector>
15#include <algorithm>
16#include <functional>
17#include <boost/property_map.hpp>
18#include <boost/pending/mutable_heap.hpp>
19#include <boost/pending/is_heap.hpp>
20#include <boost/graph/detail/array_binary_tree.hpp>
21#include <iterator>
22
23namespace boost {
24
25  // The mutable queue whose elements are indexed
26  //
27  // This adaptor provides a special kind of priority queue that has
28  // and update operation. This allows the ordering of the items to
29  // change. After the ordering criteria for item x changes, one must
30  // call the Q.update(x)
31  //
32  // In order to efficiently find x in the queue, a functor must be
33  // provided to map value_type to a unique ID, which the
34  // mutable_queue will then use to map to the location of the
35  // item. The ID's generated must be between 0 and N, where N is the
36  // value passed to the constructor of mutable_queue
37
38  template <class IndexedType,
39            class RandomAccessContainer = std::vector<IndexedType>,
40            class Comp = std::less<typename RandomAccessContainer::value_type>,
41            class ID = identity_property_map >
42  class mutable_queue {
43  public:
44    typedef IndexedType value_type;
45    typedef typename RandomAccessContainer::size_type size_type;
46  protected:
47    typedef typename RandomAccessContainer::iterator iterator;
48#if !defined BOOST_NO_STD_ITERATOR_TRAITS
49    typedef  adstl::array_binary_tree_node<iterator, ID> Node;
50#else
51    typedef  adstl::array_binary_tree_node<iterator, value_type, ID> Node;
52#endif
53    typedef  adstl::compare_array_node<RandomAccessContainer,Comp> Compare;
54    typedef std::vector<size_type> IndexArray;
55  public:
56    typedef Compare value_compare;
57    typedef ID id_generator;
58
59    mutable_queue(size_type n, const Comp& x, const ID& _id)
60      : index_array(n), comp(x), id(_id) {
61      c.reserve(n);
62    }
63    template <class ForwardIterator>
64    mutable_queue(ForwardIterator first, ForwardIterator last,
65                  const Comp& x, const ID& _id)
66      : index_array(std::distance(first, last)), comp(x), id(_id)
67    {
68      while( first != last ) {
69        push(*first);
70        ++first;
71      }
72    }
73
74    bool empty() const { return c.empty(); }
75   
76    void pop() {
77      value_type tmp = c.back();
78      c.back() = c.front();
79      c.front() = tmp;
80
81      size_type id_f = get(id, c.back());
82      size_type id_b = get(id, tmp);
83      size_type i = index_array[ id_b ];
84      index_array[ id_b ] = index_array[ id_f ];
85      index_array[ id_f ] = i;
86
87      c.pop_back();
88      Node node(c.begin(), c.end(), c.begin(), id);
89      down_heap(node, comp, index_array);       
90    }
91    void push(const IndexedType& x) {
92      c.push_back(x);
93      /*set index-array*/
94      index_array[ get(id, x) ] = c.size()-1;
95      Node node(c.begin(), c.end(), c.end() - 1, id);
96      up_heap(node, comp, index_array);
97    }
98
99    void update(const IndexedType& x) {
100      size_type current_pos = index_array[ get(id, x) ];
101      c[current_pos] = x;
102
103      Node node(c.begin(), c.end(), c.begin()+current_pos, id);
104      update_heap(node, comp, index_array);
105    }
106
107    value_type& front() { return c.front(); }
108    value_type& top() { return c.front(); }
109
110    const value_type& front() const { return c.front(); }
111    const value_type& top() const { return c.front(); }
112
113    size_type size() const { return c.size(); }
114
115    void clear() { c.clear(); }
116
117#if 0
118        // dwa 2003/7/11 - I don't know what compiler is supposed to
119        // be able to compile this, but is_heap is not standard!!
120    bool test() {
121      return std::is_heap(c.begin(), c.end(), Comp());
122    }
123#endif
124
125   protected:
126    IndexArray index_array;
127    Compare comp;
128    RandomAccessContainer c;
129    ID id;
130  };
131
132
133}
134
135#endif // BOOST_MUTABLE_QUEUE_HPP
Note: See TracBrowser for help on using the repository browser.