//
// $COPYRIGHT$
//
#ifndef MMD_AUX_H
#define MMD_AUX_H

namespace matrix_ordering {


  //: Array implementation of multiple stacks 
  //
  // This to use a single array for multiple stacks. It was used in
  // Fortran code orginally because of its efficiency.
  //
  //!category: ordering
  //!component: type
  //!definition: mmd_aux.h
  template <class Iter>
  class Stacks {
    typedef typename decorator_traits<Iter>::value_type value_type;
    typedef value_type size_type;
  public:
    Stacks(Iter _data) : data(_data) {}
  
    //: stack 
    class stack {
    
    public:
      stack(Iter _data, 
	    const value_type& head = -std::numeric_limits<value_type>::max())
	:  data(_data), current(head) {}

      void pop() 
      { current = data[current]; }

      void push(size_type v)
      { data[v] = current; current = v; }
    
      bool empty()
      { return (current == -std::numeric_limits<value_type>::max()); }

      value_type& top() {
	return current;
      }
      value_type& top() const {
	return current;
      }

      Iter data;
      size_type current;
    };

    //: To return a stack object with the head provided.
    stack operator[](size_type i) 
    { return stack(data, i); }

    //: To return a stack object 
    stack make_stack()
    { return stack(data); }
  protected:
    Iter data;
  };


  //: marker class, a generalization of coloring. 
  //
  // This class is to provide a generalization of coloring which has
  // complexity of amortized constant time to set all vertices' color
  // back to be white. It implemented by simply increasing a tag.
  //
  //!category: ordering
  //!component: type
  //!definition: mmd_aux.h
  template <class Iter>
  class Marker {
    typedef typename decorator_traits<Iter>::value_type value_type;
    typedef value_type size_type;

    static value_type DONE() 
    { return std::numeric_limits<value_type>::max()/2; }
  public:
    Marker(Iter _data, size_type _num) 
      : Tag(1-std::numeric_limits<value_type>::max()),
	data(_data), num(_num) {}

    void init(size_type n) {
      for (size_type i=0; i<n; i++)
	data[i] = -std::numeric_limits<value_type>::max();
    }

    void mark_done(size_type node) {
      data[node] = DONE();
    }

    bool is_done(size_type node) {
      return data[node] == DONE();
    }

    void mark_tag(size_type node) {
      data[node] = Tag;
    }

    void mark_mtag(size_type node) {
      data[node] = Mtag;
    }
  
    bool is_tagged(size_type node) const {
      return data[node] >= Tag;
    }

    bool is_not_tagged(size_type node) const {
      return data[node] < Tag;
    }

    bool is_mtagged(size_type node) const {
      return data[node] >= Mtag;
    }

    void increment_tag() {
      Tag++;
      if ( Tag >= DONE() ) {
	Tag = 1-std::numeric_limits<value_type>::max();
	for (size_type i=0; i<num; i++)
	  if ( data[i] < DONE() ) 
	    data[i] = -std::numeric_limits<value_type>::max();
      }
    }

    void set_mtag(value_type mdeg0) 
    { 
      Mtag = Tag + mdeg0; 
    
      if ( Mtag >= DONE() ) {
	Tag = 1-std::numeric_limits<value_type>::max();

	for (size_type i=0; i<num; i++)
	  if ( data[i] < DONE() ) 
	    data[i] = -std::numeric_limits<value_type>::max();
     
	Mtag = Tag + mdeg0; 
      }

    }

    void set_tag_as_mtag ()
    { Tag = Mtag; }

    void print(size_type n) {
      cout << "print markers: " << endl;
      cout << " current tag is "  
	   << Tag + std::numeric_limits<value_type>::max() << endl;
      for (size_type itemp=0; itemp<n; itemp++) {
	value_type d =  data[itemp];
	if ( d != DONE() )
	  d += std::numeric_limits<value_type>::max();
	  cout << d << " ";
      }
	cout<< endl;
    }

  protected:
    value_type Tag;
    value_type Mtag;
    Iter  data;
    size_type  num;
  };

  template< class Iter, int offset = 1 >
  class Numbering {
    typedef typename decorator_traits<Iter>::value_type value_type;
    /**/
    typedef int size_type;

    value_type num; //start from 1 instead of zero
    Iter data;
    value_type NUM;
  public:
    Numbering(Iter _data, value_type _NUM) 
      : num(1), data(_data), NUM(_NUM) {}

    void operator()(size_type node) {
      //node += offset;
      data[node] = -num;
    }

    /*
    template <class Vertex>
    void operator()(Vertex node) {
      data[ id_decorator()[node] ] = -num;
    }
    */

    bool all_done(size_type i=0) const {
      return num + i > NUM;
    }

    void increment(size_type i=1) {
      num += i;
    }

    bool is_numbered(size_type node) const {
      //node += offset;
      return data[node]<0;
    }

    void indistinguishable(size_type i, size_type j) {
      //i += offset;
      //j += offset;
      data[i] = - (j + offset);
    }

  };

}

#endif