//

 //=======================================================================

 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

 //

 // Distributed under the Boost Software License, Version 1.0. (See

 // accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 //=======================================================================

 //

 //

 // Revision History:

 //   13 June 2001: Changed some names for clarity. (Jeremy Siek)

 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)

 //

 #ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP

 #define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP

 #include <vector>

 #include <cassert>

 #include <boost/limits.hpp>

 namespace boost {

   template <class BucketType, class ValueType, class Bucket, 

             class ValueIndexMap>

   class bucket_sorter {

   public:

     typedef BucketType bucket_type;

     typedef ValueType value_type;

     typedef typename std::vector<value_type>::size_type size_type;

     bucket_sorter(size_type _length, bucket_type _max_bucket, 

                   const Bucket& _bucket = Bucket(), 

                   const ValueIndexMap& _id = ValueIndexMap()) 

       : head(_max_bucket, invalid_value()),

         next(_length, invalid_value()), 

         prev(_length, invalid_value()),

         id_to_value(_length),

         bucket(_bucket), id(_id) { }

     void remove(const value_type& x) {

       const size_type i = get(id, x);

       const size_type& next_node = next[i];

       const size_type& prev_node = prev[i];

       //check if i is the end of the bucket list 

       if ( next_node != invalid_value() )

         prev[next_node] = prev_node; 

       //check if i is the begin of the bucket list

       if ( prev_node != invalid_value() )

         next[prev_node] = next_node;

       else //need update head of current bucket list

         head[ bucket[x] ] = next_node;

     }

     void push(const value_type& x) {

       id_to_value[get(id, x)] = x;

       (*this)[bucket[x]].push(x);

     }

     void update(const value_type& x) {

       remove(x);

       (*this)[bucket[x]].push(x);

     }

     //  private: 

     //    with KCC, the nested stack class is having access problems

     //    despite the friend decl.

     static size_type invalid_value() {

       return (std::numeric_limits<size_type>::max)();

     }

     typedef typename std::vector<size_type>::iterator Iter;

     typedef typename std::vector<value_type>::iterator IndexValueMap;

   public:

     friend class stack;

     class stack {

     public:

       stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,

             const ValueIndexMap& _id)

       : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id) {}

       // Avoid using default arg for ValueIndexMap so that the default

       // constructor of the ValueIndexMap is not required if not used.

       stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)

         : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v) {}

       void push(const value_type& x) {

         const size_type new_head = get(id, x);

         const size_type current = head[bucket_id];

         if ( current != invalid_value() )

           prev[current] = new_head;

         prev[new_head] = invalid_value();

         next[new_head] = current;

         head[bucket_id] = new_head;

       }

       void pop() {

         size_type current = head[bucket_id];

         size_type next_node = next[current];

         head[bucket_id] = next_node;

         if ( next_node != invalid_value() )

           prev[next_node] = invalid_value();

       }

       value_type& top() { return value[ head[bucket_id] ]; }

       const value_type& top() const { return value[ head[bucket_id] ]; }

       bool empty() const { return head[bucket_id] == invalid_value(); }

     private:

       bucket_type bucket_id;

       Iter head;

       Iter next;

       Iter prev;

       IndexValueMap value;

       ValueIndexMap id;

     };

     stack operator[](const bucket_type& i) {

       assert(i < head.size());

       return stack(i, head.begin(), next.begin(), prev.begin(),

                    id_to_value.begin(), id);

     }

   protected:

     std::vector<size_type>   head;

     std::vector<size_type>   next;

     std::vector<size_type>   prev;

     std::vector<value_type>  id_to_value;

     Bucket bucket;

     ValueIndexMap id;

   };

 }

 #endif