/*
 * --- GSMP-COPYRIGHT-NOTE-BEGIN ---
 * 
 * This copyright note is auto-generated by ./scripts/Create-CopyPatch.
 * Please add additional copyright information _after_ the line containing
 * the GSMP-COPYRIGHT-NOTE-END tag. Otherwise it might get removed by
 * the ./scripts/Create-CopyPatch script. Do not edit this copyright text!
 * 
 * GSMP: utility/include/template/BinomiHeap.tcc
 * General Sound Manipulation Program is Copyright (C) 2000 - 2004
 *   Valentin Ziegler and René Rebe
 * 
 * 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; version 2. A copy of the GNU General
 * Public License can be found in the file LICENSE.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANT-
 * ABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
 * Public License for more details.
 * 
 * --- GSMP-COPYRIGHT-NOTE-END ---
 */

#ifndef BIN_HEAP_HH__
#  error "This file is included by BinomiHeap.hh"
#  error "manual inclusion is nonsense"
#endif // BIN_HEAP_HH__

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: BinomiHeap ()
{
  heap.push_back (0); // insert pseudo element
  cur_size = 1;
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: ~BinomiHeap ()
{
}


template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
id_t BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: Insert (ITEM_T item, KEY_T key)
{
  // init node data
  id_t id = node_data.size();
  node_data.push_back (Node (item, key, cur_size));

  // insert at end of heap
  unsigned int node_pos = id;
  if (cur_size > MaxElements())
    heap.push_back (node_pos);
  else
    heap[cur_size] = node_pos;

  unsigned int pos = cur_size;
  cur_size++;

  DrownElement (pos, key);
  return id;
}


template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
ITEM_T BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> ::  ExtractMin (KEY_T& val)
{
  if (RANGE_CHECKING)
    if (Empty())
      throw HeapEmptyException();

  // remember root data
  Node& t_node = node_data[heap [1]];
  ITEM_T r_item = t_node.item;
  val = t_node.key;
  // mark root as extracted
  t_node.map_position = 0;

  if (CurrentElements() > 1) {
    // insert last element as new root
    heap [1] = heap [--cur_size];

    Node& new_root = node_data[heap [1]];
    new_root.map_position = 1;

    // bubble element upwards
    unsigned int pos = 1;
    KEY_T key = new_root.key;

    unsigned int spos;
    while (spos = SmallestChildIndex (pos), node_data[heap [spos]].key < key)
      {
	ExchangeNodes (pos, spos);
	pos = spos;
      }
  } else
    cur_size--;

  return r_item;
}


template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline unsigned int BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: TotalIDs ()
{
  return node_data.size();
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline unsigned int BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: CurrentElements ()
{
  return cur_size - 1;
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline unsigned int BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: MaxElements ()
{
  return heap.size() - 1;
}


template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline bool BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: Empty ()
{
  return CurrentElements() == 0;
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
void BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: DecreaseKey (KEY_T new_key, id_t id)
{
  CheckInQ (id);
  if (RANGE_CHECKING)
    if (node_data [id].key < new_key)
      throw InvalidKeyException();

  node_data [id].key = new_key;
  unsigned int pos = (unsigned int) node_data[id].map_position;

  DrownElement (pos, new_key);
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
KEY_T BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: GetKey (id_t id)
{
  CheckId (id);
  return node_data[id].key;
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
ITEM_T BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: GetItem (id_t id)
{
  CheckId (id);
  return node_data [id].item;
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline bool BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: InHeap (id_t id)
{
  CheckId(id);
  return (node_data[id].map_position > 0); 
}


template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
void BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: DrownElement (unsigned int pos, KEY_T key)
{
  // drown element
  unsigned int mother;
  while (pos > 1 && (mother = MotherIndex(pos), node_data[heap [mother]].key > key))
    {
      ExchangeNodes (pos, mother);
      pos = mother;
    }
}



template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline void BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: ExchangeNodes (int i, int j)
{
  unsigned int dummy = heap [i];
  heap [i] = heap [j];
  heap [j] = dummy;

  node_data[heap [i]].map_position = i;
  node_data[heap [j]].map_position = j;
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline unsigned int BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: LeftChildIndex (int index)
{ // child 1 on position [index * 2]
  return index << 1;
}




template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline unsigned int BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: RightChildIndex (int index)
{ // child 2 on position [index * 2] + 1
  return (index << 1) + 1; 
}


template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline unsigned int BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: SmallestChildIndex (int index)
{ 
  unsigned int l = LeftChildIndex (index);
  unsigned int r = RightChildIndex (index);

  unsigned int elements=CurrentElements();
  if (l > elements)
    return index;   // node does not have any children
  else if (l == elements)
    return l;       // node only features one children
  else
    return (node_data[heap [l]].key < node_data[heap [r]].key) ? l : r;
}


template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline unsigned int BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: MotherIndex (int index)
{ // mother at position [index / 2]
  return index >> 1;
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline void BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: CheckId (id_t id)
{
  if (RANGE_CHECKING)
    if (id >= TotalIDs())
      throw InvalidIdException();
}

template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
inline void BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: CheckInQ (id_t id)
{
  if (!InHeap(id))
    throw InvalidIdException();
}

#ifdef HEAP_TESTING
template <typename ITEM_T, typename KEY_T, bool RANGE_CHECKING>
void BinomiHeap <ITEM_T, KEY_T, RANGE_CHECKING> :: PrintHeap (unsigned int pos, unsigned int spaces)
{
  for (unsigned int i=0; i<spaces; i++)
    std::cout << "\t";
  
  Node& node = node_data[heap[pos]];
  std::cout << node.item << " : " << node.key << std::endl;

  unsigned int l = LeftChildIndex (pos);
  unsigned int r = RightChildIndex (pos);

  unsigned int elements=CurrentElements();
  if (l > elements)
    ;   // node does not have any children
  else if (l == elements) { // node only features one children
    PrintHeap (l, spaces+1);
  } else {
    PrintHeap (l, spaces+1);
    PrintHeap (r, spaces+1);
  }

}

#endif