ceph/src/boost/libs/graph/include/boost/pending/bucket_sorter.hpp

   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 //
  12 // Revision History:
  13 //   13 June 2001: Changed some names for clarity. (Jeremy Siek)
  14 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
  15 //
  16 #ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
  17 #define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
  18
  19 #include <vector>
  20 #include <cassert>
  21 #include <boost/limits.hpp>
  22
  23 namespace boost {
  24
  25   template <class BucketType, class ValueType, class Bucket,
  26             class ValueIndexMap>
  27   class bucket_sorter {
  28   public:
  29     typedef BucketType bucket_type;
  30     typedef ValueType value_type;
  31     typedef typename std::vector<value_type>::size_type size_type;
  32
  33     bucket_sorter(size_type _length, bucket_type _max_bucket,
  34                   const Bucket& _bucket = Bucket(),
  35                   const ValueIndexMap& _id = ValueIndexMap())
  36       : head(_max_bucket, invalid_value()),
  37         next(_length, invalid_value()),
  38         prev(_length, invalid_value()),
  39         id_to_value(_length),
  40         bucket(_bucket), id(_id) { }
  41
  42     void remove(const value_type& x) {
  43       const size_type i = get(id, x);
  44       const size_type& next_node = next[i];
  45       const size_type& prev_node = prev[i];
  46
  47       //check if i is the end of the bucket list
  48       if ( next_node != invalid_value() )
  49         prev[next_node] = prev_node;
  50       //check if i is the begin of the bucket list
  51       if ( prev_node != invalid_value() )
  52         next[prev_node] = next_node;
  53       else //need update head of current bucket list
  54         head[ bucket[x] ] = next_node;
  55     }
  56
  57     void push(const value_type& x) {
  58       id_to_value[get(id, x)] = x;
  59       (*this)[bucket[x]].push(x);
  60     }
  61
  62     void update(const value_type& x) {
  63       remove(x);
  64       (*this)[bucket[x]].push(x);
  65     }
  66     //  private:
  67     //    with KCC, the nested stack class is having access problems
  68     //    despite the friend decl.
  69     static size_type invalid_value() {
  70       return (std::numeric_limits<size_type>::max)();
  71     }
  72
  73     typedef typename std::vector<size_type>::iterator Iter;
  74     typedef typename std::vector<value_type>::iterator IndexValueMap;
  75
  76   public:
  77     friend class stack;
  78
  79     class stack {
  80     public:
  81       stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,
  82             const ValueIndexMap& _id)
  83       : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id) {}
  84
  85       // Avoid using default arg for ValueIndexMap so that the default
  86       // constructor of the ValueIndexMap is not required if not used.
  87       stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)
  88         : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v) {}
  89
  90       void push(const value_type& x) {
  91         const size_type new_head = get(id, x);
  92         const size_type current = head[bucket_id];
  93         if ( current != invalid_value() )
  94           prev[current] = new_head;
  95         prev[new_head] = invalid_value();
  96         next[new_head] = current;
  97         head[bucket_id] = new_head;
  98       }
  99       void pop() {
 100         size_type current = head[bucket_id];
 101         size_type next_node = next[current];
 102         head[bucket_id] = next_node;
 103         if ( next_node != invalid_value() )
 104           prev[next_node] = invalid_value();
 105       }
 106       value_type& top() { return value[ head[bucket_id] ]; }
 107       const value_type& top() const { return value[ head[bucket_id] ]; }
 108       bool empty() const { return head[bucket_id] == invalid_value(); }
 109     private:
 110       bucket_type bucket_id;
 111       Iter head;
 112       Iter next;
 113       Iter prev;
 114       IndexValueMap value;
 115       ValueIndexMap id;
 116     };
 117
 118     stack operator[](const bucket_type& i) {
 119       assert(i < head.size());
 120       return stack(i, head.begin(), next.begin(), prev.begin(),
 121                    id_to_value.begin(), id);
 122     }
 123   protected:
 124     std::vector<size_type>   head;
 125     std::vector<size_type>   next;
 126     std::vector<size_type>   prev;
 127     std::vector<value_type>  id_to_value;
 128     Bucket bucket;
 129     ValueIndexMap id;
 130   };
 131
 132 }
 133
 134 #endif