ceph/src/boost/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 #include <boost/concept/assert.hpp>
  23 #include <boost/property_map/property_map.hpp>
  24
  25 namespace boost
  26 {
  27
  28 template < class BucketType, class ValueType, class Bucket,
  29     class ValueIndexMap >
  30 class bucket_sorter
  31 {
  32     BOOST_CONCEPT_ASSERT(
  33         (ReadablePropertyMapConcept< ValueIndexMap, ValueType >));
  34
  35 public:
  36     typedef BucketType bucket_type;
  37     typedef ValueType value_type;
  38     typedef typename std::vector< value_type >::size_type size_type;
  39
  40     bucket_sorter(size_type _length, bucket_type _max_bucket,
  41         const Bucket& _bucket = Bucket(),
  42         const ValueIndexMap& _id = ValueIndexMap())
  43     : head(_max_bucket, invalid_value())
  44     , next(_length, invalid_value())
  45     , prev(_length, invalid_value())
  46     , id_to_value(_length)
  47     , bucket(_bucket)
  48     , id(_id)
  49     {
  50     }
  51
  52     void remove(const value_type& x)
  53     {
  54         const size_type i = get(id, x);
  55         const size_type& next_node = next[i];
  56         const size_type& prev_node = prev[i];
  57
  58         // check if i is the end of the bucket list
  59         if (next_node != invalid_value())
  60             prev[next_node] = prev_node;
  61         // check if i is the begin of the bucket list
  62         if (prev_node != invalid_value())
  63             next[prev_node] = next_node;
  64         else // need update head of current bucket list
  65             head[bucket[x]] = next_node;
  66     }
  67
  68     void push(const value_type& x)
  69     {
  70         id_to_value[get(id, x)] = x;
  71         (*this)[bucket[x]].push(x);
  72     }
  73
  74     void update(const value_type& x)
  75     {
  76         remove(x);
  77         (*this)[bucket[x]].push(x);
  78     }
  79     //  private:
  80     //    with KCC, the nested stack class is having access problems
  81     //    despite the friend decl.
  82     static size_type invalid_value()
  83     {
  84         return (std::numeric_limits< size_type >::max)();
  85     }
  86
  87     typedef typename std::vector< size_type >::iterator Iter;
  88     typedef typename std::vector< value_type >::iterator IndexValueMap;
  89
  90 public:
  91     friend class stack;
  92
  93     class stack
  94     {
  95     public:
  96         stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,
  97             const ValueIndexMap& _id)
  98         : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id)
  99         {
 100         }
 101
 102         // Avoid using default arg for ValueIndexMap so that the default
 103         // constructor of the ValueIndexMap is not required if not used.
 104         stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)
 105         : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v)
 106         {
 107         }
 108
 109         void push(const value_type& x)
 110         {
 111             const size_type new_head = get(id, x);
 112             const size_type current = head[bucket_id];
 113             if (current != invalid_value())
 114                 prev[current] = new_head;
 115             prev[new_head] = invalid_value();
 116             next[new_head] = current;
 117             head[bucket_id] = new_head;
 118         }
 119         void pop()
 120         {
 121             size_type current = head[bucket_id];
 122             size_type next_node = next[current];
 123             head[bucket_id] = next_node;
 124             if (next_node != invalid_value())
 125                 prev[next_node] = invalid_value();
 126         }
 127         value_type& top() { return value[head[bucket_id]]; }
 128         const value_type& top() const { return value[head[bucket_id]]; }
 129         bool empty() const { return head[bucket_id] == invalid_value(); }
 130
 131     private:
 132         bucket_type bucket_id;
 133         Iter head;
 134         Iter next;
 135         Iter prev;
 136         IndexValueMap value;
 137         ValueIndexMap id;
 138     };
 139
 140     stack operator[](const bucket_type& i)
 141     {
 142         assert(i < head.size());
 143         return stack(i, head.begin(), next.begin(), prev.begin(),
 144             id_to_value.begin(), id);
 145     }
 146
 147 protected:
 148     std::vector< size_type > head;
 149     std::vector< size_type > next;
 150     std::vector< size_type > prev;
 151     std::vector< value_type > id_to_value;
 152     Bucket bucket;
 153     ValueIndexMap id;
 154 };
 155
 156 }
 157
 158 #endif