williamr@2: //
williamr@2: //=======================================================================
williamr@2: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2: // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2: //
williamr@2: // Distributed under the Boost Software License, Version 1.0. (See
williamr@2: // accompanying file LICENSE_1_0.txt or copy at
williamr@2: // http://www.boost.org/LICENSE_1_0.txt)
williamr@2: //=======================================================================
williamr@2: //
williamr@2: //
williamr@2: // Revision History:
williamr@2: //   13 June 2001: Changed some names for clarity. (Jeremy Siek)
williamr@2: //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
williamr@2: //
williamr@2: #ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
williamr@2: #define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
williamr@2: 
williamr@2: #include <vector>
williamr@2: #include <cassert>
williamr@2: #include <boost/limits.hpp>
williamr@2: 
williamr@2: namespace boost {
williamr@2: 
williamr@2:   template <class BucketType, class ValueType, class Bucket, 
williamr@2:             class ValueIndexMap>
williamr@2:   class bucket_sorter {
williamr@2:   public:
williamr@2:     typedef BucketType bucket_type;
williamr@2:     typedef ValueType value_type;
williamr@2:     typedef typename std::vector<value_type>::size_type size_type;
williamr@2:     
williamr@2:     bucket_sorter(size_type _length, bucket_type _max_bucket, 
williamr@2:                   const Bucket& _bucket = Bucket(), 
williamr@2:                   const ValueIndexMap& _id = ValueIndexMap()) 
williamr@2:       : head(_max_bucket, invalid_value()),
williamr@2:         next(_length, invalid_value()), 
williamr@2:         prev(_length, invalid_value()),
williamr@2:         id_to_value(_length),
williamr@2:         bucket(_bucket), id(_id) { }
williamr@2:     
williamr@2:     void remove(const value_type& x) {
williamr@2:       const size_type i = get(id, x);
williamr@2:       const size_type& next_node = next[i];
williamr@2:       const size_type& prev_node = prev[i];
williamr@2:     
williamr@2:       //check if i is the end of the bucket list 
williamr@2:       if ( next_node != invalid_value() )
williamr@2:         prev[next_node] = prev_node; 
williamr@2:       //check if i is the begin of the bucket list
williamr@2:       if ( prev_node != invalid_value() )
williamr@2:         next[prev_node] = next_node;
williamr@2:       else //need update head of current bucket list
williamr@2:         head[ bucket[x] ] = next_node;
williamr@2:     }
williamr@2: 
williamr@2:     void push(const value_type& x) {
williamr@2:       id_to_value[get(id, x)] = x;
williamr@2:       (*this)[bucket[x]].push(x);
williamr@2:     }
williamr@2:     
williamr@2:     void update(const value_type& x) {
williamr@2:       remove(x);
williamr@2:       (*this)[bucket[x]].push(x);
williamr@2:     }
williamr@2:     //  private: 
williamr@2:     //    with KCC, the nested stack class is having access problems
williamr@2:     //    despite the friend decl.
williamr@2:     static size_type invalid_value() {
williamr@2:       return (std::numeric_limits<size_type>::max)();
williamr@2:     }
williamr@2:     
williamr@2:     typedef typename std::vector<size_type>::iterator Iter;
williamr@2:     typedef typename std::vector<value_type>::iterator IndexValueMap;
williamr@2:     
williamr@2:   public:
williamr@2:     friend class stack;
williamr@2: 
williamr@2:     class stack {
williamr@2:     public:
williamr@2:       stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,
williamr@2:             const ValueIndexMap& _id)
williamr@2:       : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id) {}
williamr@2: 
williamr@2:       // Avoid using default arg for ValueIndexMap so that the default
williamr@2:       // constructor of the ValueIndexMap is not required if not used.
williamr@2:       stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)
williamr@2:         : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v) {}
williamr@2:       
williamr@2:       void push(const value_type& x) {
williamr@2:         const size_type new_head = get(id, x);
williamr@2:         const size_type current = head[bucket_id];
williamr@2:         if ( current != invalid_value() )
williamr@2:           prev[current] = new_head;
williamr@2:         prev[new_head] = invalid_value();
williamr@2:         next[new_head] = current;
williamr@2:         head[bucket_id] = new_head;
williamr@2:       }
williamr@2:       void pop() {
williamr@2:         size_type current = head[bucket_id];
williamr@2:         size_type next_node = next[current];
williamr@2:         head[bucket_id] = next_node;
williamr@2:         if ( next_node != invalid_value() )
williamr@2:           prev[next_node] = invalid_value();
williamr@2:       }
williamr@2:       value_type& top() { return value[ head[bucket_id] ]; }
williamr@2:       const value_type& top() const { return value[ head[bucket_id] ]; }
williamr@2:       bool empty() const { return head[bucket_id] == invalid_value(); }
williamr@2:     private:
williamr@2:       bucket_type bucket_id;
williamr@2:       Iter head;
williamr@2:       Iter next;
williamr@2:       Iter prev;
williamr@2:       IndexValueMap value;
williamr@2:       ValueIndexMap id;
williamr@2:     };
williamr@2:     
williamr@2:     stack operator[](const bucket_type& i) {
williamr@2:       assert(i < head.size());
williamr@2:       return stack(i, head.begin(), next.begin(), prev.begin(),
williamr@2:                    id_to_value.begin(), id);
williamr@2:     }
williamr@2:   protected:
williamr@2:     std::vector<size_type>   head;
williamr@2:     std::vector<size_type>   next;
williamr@2:     std::vector<size_type>   prev;
williamr@2:     std::vector<value_type>  id_to_value;
williamr@2:     Bucket bucket;
williamr@2:     ValueIndexMap id;
williamr@2:   };
williamr@2:   
williamr@2: }
williamr@2: 
williamr@2: #endif