1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/pending/mutable_queue.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,135 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +#ifndef BOOST_MUTABLE_QUEUE_HPP
1.15 +#define BOOST_MUTABLE_QUEUE_HPP
1.16 +
1.17 +#include <vector>
1.18 +#include <algorithm>
1.19 +#include <functional>
1.20 +#include <boost/property_map.hpp>
1.21 +#include <boost/pending/mutable_heap.hpp>
1.22 +#include <boost/pending/is_heap.hpp>
1.23 +#include <boost/graph/detail/array_binary_tree.hpp>
1.24 +#include <iterator>
1.25 +
1.26 +namespace boost {
1.27 +
1.28 + // The mutable queue whose elements are indexed
1.29 + //
1.30 + // This adaptor provides a special kind of priority queue that has
1.31 + // and update operation. This allows the ordering of the items to
1.32 + // change. After the ordering criteria for item x changes, one must
1.33 + // call the Q.update(x)
1.34 + //
1.35 + // In order to efficiently find x in the queue, a functor must be
1.36 + // provided to map value_type to a unique ID, which the
1.37 + // mutable_queue will then use to map to the location of the
1.38 + // item. The ID's generated must be between 0 and N, where N is the
1.39 + // value passed to the constructor of mutable_queue
1.40 +
1.41 + template <class IndexedType,
1.42 + class RandomAccessContainer = std::vector<IndexedType>,
1.43 + class Comp = std::less<typename RandomAccessContainer::value_type>,
1.44 + class ID = identity_property_map >
1.45 + class mutable_queue {
1.46 + public:
1.47 + typedef IndexedType value_type;
1.48 + typedef typename RandomAccessContainer::size_type size_type;
1.49 + protected:
1.50 + typedef typename RandomAccessContainer::iterator iterator;
1.51 +#if !defined BOOST_NO_STD_ITERATOR_TRAITS
1.52 + typedef adstl::array_binary_tree_node<iterator, ID> Node;
1.53 +#else
1.54 + typedef adstl::array_binary_tree_node<iterator, value_type, ID> Node;
1.55 +#endif
1.56 + typedef adstl::compare_array_node<RandomAccessContainer,Comp> Compare;
1.57 + typedef std::vector<size_type> IndexArray;
1.58 + public:
1.59 + typedef Compare value_compare;
1.60 + typedef ID id_generator;
1.61 +
1.62 + mutable_queue(size_type n, const Comp& x, const ID& _id)
1.63 + : index_array(n), comp(x), id(_id) {
1.64 + c.reserve(n);
1.65 + }
1.66 + template <class ForwardIterator>
1.67 + mutable_queue(ForwardIterator first, ForwardIterator last,
1.68 + const Comp& x, const ID& _id)
1.69 + : index_array(std::distance(first, last)), comp(x), id(_id)
1.70 + {
1.71 + while( first != last ) {
1.72 + push(*first);
1.73 + ++first;
1.74 + }
1.75 + }
1.76 +
1.77 + bool empty() const { return c.empty(); }
1.78 +
1.79 + void pop() {
1.80 + value_type tmp = c.back();
1.81 + c.back() = c.front();
1.82 + c.front() = tmp;
1.83 +
1.84 + size_type id_f = get(id, c.back());
1.85 + size_type id_b = get(id, tmp);
1.86 + size_type i = index_array[ id_b ];
1.87 + index_array[ id_b ] = index_array[ id_f ];
1.88 + index_array[ id_f ] = i;
1.89 +
1.90 + c.pop_back();
1.91 + Node node(c.begin(), c.end(), c.begin(), id);
1.92 + down_heap(node, comp, index_array);
1.93 + }
1.94 + void push(const IndexedType& x) {
1.95 + c.push_back(x);
1.96 + /*set index-array*/
1.97 + index_array[ get(id, x) ] = c.size()-1;
1.98 + Node node(c.begin(), c.end(), c.end() - 1, id);
1.99 + up_heap(node, comp, index_array);
1.100 + }
1.101 +
1.102 + void update(const IndexedType& x) {
1.103 + size_type current_pos = index_array[ get(id, x) ];
1.104 + c[current_pos] = x;
1.105 +
1.106 + Node node(c.begin(), c.end(), c.begin()+current_pos, id);
1.107 + update_heap(node, comp, index_array);
1.108 + }
1.109 +
1.110 + value_type& front() { return c.front(); }
1.111 + value_type& top() { return c.front(); }
1.112 +
1.113 + const value_type& front() const { return c.front(); }
1.114 + const value_type& top() const { return c.front(); }
1.115 +
1.116 + size_type size() const { return c.size(); }
1.117 +
1.118 + void clear() { c.clear(); }
1.119 +
1.120 +#if 0
1.121 + // dwa 2003/7/11 - I don't know what compiler is supposed to
1.122 + // be able to compile this, but is_heap is not standard!!
1.123 + bool test() {
1.124 + return std::is_heap(c.begin(), c.end(), Comp());
1.125 + }
1.126 +#endif
1.127 +
1.128 + protected:
1.129 + IndexArray index_array;
1.130 + Compare comp;
1.131 + RandomAccessContainer c;
1.132 + ID id;
1.133 + };
1.134 +
1.135 +
1.136 +}
1.137 +
1.138 +#endif // BOOST_MUTABLE_QUEUE_HPP