/* Copyright (c) 1997-2005
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_HEAP_H
#define _POLYMAKE_HEAP_H "$Project: polymake $$Id: Heap.h,v 1.9 2005/12/13 20:40:35 gawrilow Exp $"

#include <vector>
#include <comparators.h>
#include <ext/hash_map>

namespace pm {

template <typename> class Adapter;
template <typename> class RememberRemoved;

enum heap_element_state {
   heap_element_unvisited=-2, ///< the element was never seen before
   heap_element_removed=-1,   ///< the element was popped away
   heap_element_active=1      ///< the element is currently in the heap
};

struct hash_map_adapter {
   template <typename Key, typename Value>
   struct property_map {
      typedef hash_map_as_property_map<Key, Value> type;
   };

   template <typename Key, typename Value> static
   typename property_map<Key, Value>::type create_property_map(Key*, Value*)
   {
      return typename property_map<Key, Value>::type();
   }

   template <typename Key, typename Value> static
   void clear(hash_map_as_property_map<Key, Value>& map)
   {
      map.clear();
   }

   template <typename Key, typename Value> static
   void clear(hash_map_as_property_map<Key, Value>& map, const Value& v)
   {
      clear(map);
      map.set_default_value(v);
   }

   template <typename Key, typename Value> static
   void init(hash_map_as_property_map<Key, Value>& map)
   {
      clear(map);
   }

   template <typename Key, typename Value> static
   void init(hash_map_as_property_map<Key, Value>& map, const Value& v)
   {
      clear(map,v);
   }
};

/** Heap (priority queue).
    The queue is stored in a dynamic array, with element indices inducing an implicit binary tree structure
    (the child elements of the i-th element have indices 2*i+1 and 2*i+2.)
    The elements are mapped to their indices via a hash table.

    \param Key elements stored in the heap
    \param Traits tagged typelist: parameters for fine-tuning
       Comparator<.>  key comparator; default is polymake::operations::cmp (in the most cases it will use the standard relational operators
       Adapter<.>  some class defining the meta-constructors for property maps
 */
template <typename Key, typename Traits=void>
class Heap {
public:
   typedef Key key_type;
   typedef typename function_argument<key_type>::type key_arg_type;

   typedef typename extract_type_param<Traits, Comparator, operations::cmp<> >::result
      raw_comparator_type;
   typedef binary_op_builder<raw_comparator_type, const key_type*, const key_type*> cmp_builder;
   typedef typename cmp_builder::operation comparator_type;

protected:
   typedef typename extract_type_param<Traits, Adapter, hash_map_adapter>::result adapter;
   typedef typename adapter::template property_map<key_type, int>::type index_map_type;
   static const bool remember_removed=extract_bool_param<Traits, RememberRemoved>::result;
   static const heap_element_state removed_state= remember_removed ? heap_element_removed : heap_element_unvisited;

   std::vector<key_type> queue;
   comparator_type comparator;
   index_map_type index;

private:
   void init(const adapter& ad, int expected_qlen)
   {
      if (expected_qlen>0) queue.reserve(expected_qlen);
      ad.clear(index, int(heap_element_unvisited));
   }

public:
   /** Create an empty heap, comparator with its default constructor.
       @param expected_qlen expected maximal heap size (helps to avoid extra reallocations)
   */
   explicit Heap(int expected_qlen=0)
   {
      init(adapter(), expected_qlen);
   }

   /// Create an empty heap, comparator as a copy of the given object
   explicit Heap(const raw_comparator_type& cmp_arg, int expected_qlen=0)
      : comparator(cmp_builder::create(cmp_arg))
   {
      init(adapter(), expected_qlen);
   }

   explicit Heap(const adapter& ad, int expected_qlen=0)
      : index(ad.create_property_map((key_type*)0, (int*)0))
   {
      init(ad, expected_qlen);
   }

   Heap(const adapter& ad, const raw_comparator_type& cmp_arg, int expected_qlen=0)
      : comparator(cmp_builder::create(cmp_arg)),
        index(ad.create_property_map((key_type*)0, (int*)0))
   {
      init(ad, expected_qlen);
   }

   /// \retval \c true if the heap is empty
   bool empty() const { return queue.empty(); }

   void clear()
   {
      queue.clear();
      index.clear();
   }

   /// Look up the element
   heap_element_state get_state(key_arg_type k) const
   {
      int s=index(k);
      return s>0 ? heap_element_active : heap_element_state(s);
   }

   /** Add a new element or update its position in the queue.
       In the latter case it is assumed that its priority has been decreased,
       this method does not check the opposite case!
   */
   void push(key_arg_type);

   /// The currently topmost element
   key_arg_type top() const { return queue.front(); }

   /// Sift the topmost element down if its priority has been increased.
   void update_top()
   {
      sift_down(0);
   }

   /// Remove the topmost element and return it, adjust the heap
   key_type pop()
   {
      key_type top=queue.front();
      sift_down(queue.size()-1);
      queue.pop_back();
      index[top]=removed_state;
      return top;
   }

   /// Remove the element
   void erase(key_arg_type);

   const comparator_type& get_comparator() const { return comparator; }
private:
   /// Find the new location in the queue for the given key, starting at pos (default: the top position)
   void sift_down(int what, int pos=0);

#ifdef POLY_DEBUG
public:
   /// Sanity checks for the sake of debugging
   void check() const;

   typedef typename std::vector<key_type>::const_iterator iterator;
   typedef typename std::vector<key_type>::const_reverse_iterator reverse_iterator;
   typedef iterator const_iterator;
   typedef reverse_iterator const_reverse_iterator;
   typedef key_type value_type;
   typedef const key_type& reference;
   typedef reference const_reference;

   iterator begin() const { return queue.begin(); }
   iterator end() const { return queue.end(); }
#endif
};

#ifdef POLY_DEBUG
template <typename Key, typename Traits>
struct spec_object_traits< Heap<Key,Traits> > : spec_object_traits<is_container> {
   static const IO_separator_kind IO_separator=IO_sep_inherit;
};
#endif

/// Metaconstructor for this heap implementation
struct HeapConstructor {
   template <typename Key, typename Traits=void>
   struct defs {
      typedef Heap<Key, typename append_bool_param<Traits,RememberRemoved,true>::result> type;
   };
};

#ifdef POLY_DEBUG
template <typename Key, typename Traits>
void Heap<Key,Traits>::check() const
{
   for (int i=0, iend=queue.size(); i<iend; ++i) {
      key_arg_type k=queue[i];
      int pos=index(k);
      if (pos != i) {
	 std::cerr << "check(Heap): key " << k << " has wrong index " << pos << " instead of " << i << std::endl;
      }
      if (i>0) {
	 int p=(i-1)/2;
	 if (comparator(k,queue[p])<0) {
	    std::cerr << "check(Heap): parent(" << k << ")=" << p << std::endl;
	 }
      }
   }
}
#endif

template <typename Key, typename Traits>
void Heap<Key,Traits>::push(key_arg_type k)
{
   std::pair<typename index_map_type::iterator, bool> ii=index.insert(k, queue.size());
   if (ii.second) queue.push_back(k);
   int pos=ii.first->second;
   bool moved=false;

   while (pos>0) {
      key_arg_type p=queue[(pos-1)/2];	// parent node in the heap tree
      if (comparator(p,k) < 0) break;	// even if the new node has the same distance value as the old one,
      					// it should be pushed above it. This is important in the rounding case.
      queue[pos]=p;
      index[p]=pos;
      pos=(pos-1)/2;
      moved=true;
   }
   if (moved) {
      queue[pos]=k;
      ii.first->second=pos;
   }
}

template <typename Key, typename Traits>
void Heap<Key,Traits>::sift_down(int what, int pos)
{
   int end=queue.size()-(what!=0);
   key_arg_type k=queue[what];
   int cpos;
   while ((cpos=2*pos+1) < end) {
      if (cpos+1<end &&
	  comparator(queue[cpos+1],queue[cpos])<0) ++cpos;
      if (comparator(k,queue[cpos])<=0) break;
      index[queue[pos]=queue[cpos]]=pos;
      pos=cpos;
   }
   if (pos || what) {
      queue[pos]=k;
      index[k]=pos;
   }
}

template <typename Key, typename Traits>
void Heap<Key,Traits>::erase(key_arg_type k)
{
   int pos=index(k);
   index[k]=removed_state;
   if (pos>=0) {
      key_type n=queue.back();
      bool bubble_up=false;
      int ppos;
      while ((ppos=(pos-1)/2) > 0) {
	 if (comparator(n,queue[ppos])>=0) break;
	 index[queue[pos]=queue[ppos]]=pos;
	 bubble_up=true;
	 pos=ppos;
      }
      if (bubble_up)
	 index[queue[pos]=n]=pos;
      else
	 sift_down(queue.size()-1,pos);
      queue.pop_back();
   }
}

} // end namespace pm

namespace polymake {
   using pm::Heap;
}

#endif // _POLYMAKE_HEAP_H

// Local Variables:
// mode:C++
// c-basic-offset:3
// End:
