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

Revision 857, 4.5 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//
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
23namespace 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
Note: See TracBrowser for help on using the repository browser.