//

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

// 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