// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): SUNY Stony Brook students

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#include <LINK/basic/Error.cc>

/*****************************private routines*****************************/
//
//Link binomial trees whose roots have the same degree. The following
//procedure links the B(k-1) tree rooted at node y to the B(k-1) tree
//rooted at node z, that is makes z the parent of y. Node z thus become
//the root of a B(k) tree.
//
template <class Key, class Item>
BinomialHeapNode<Key, Item>*
BinomialHeap<Key, Item>::binomialLink(BinomialHeapNode<Key, Item>* y,
                                      BinomialHeapNode<Key, Item>* z)
{
  if (!y || !z) {
     error("BinomialHeap::binomialLink(): Null parameters!");
     return(0);
  }
 
  if ( y->degree != z->degree){
     error("BinomialHeap::binomialLink(): y and z have different degree!");
     return(0);
  }
  y->parent = z;
  y->sibling = z->child;
  z->child = y;
  z->degree += 1;
  return z;
}
//
//The following procedure merges the root lists of binomial heaps y and
//z into a single linked list that is sorted by degree into monotonically 
//increasing order.
//
template <class Key, class Item>
BinomialHeapNode<Key, Item>*
BinomialHeap<Key, Item>::heapMerge(BinomialHeapNode<Key, Item>* y, 
                                   BinomialHeapNode<Key, Item>* z)
{
  if (!y)
     return z;
  if (!z)
     return y;

  BinomialHeapNode<Key, Item> *cursor1,*cursor2, 
                               *front,  *tmp,
                               *result, *merged;
  if (y->degree <= z->degree) {
     result = y;
     merged = z;
  }else {
     result = z;
     merged = y;
  }
  cursor1 = result;  
  cursor2 = merged;
  front = cursor1->sibling;

  while (cursor2) {
    //find a proper position for cursor2 in result list.
    while ( (front) && (front->degree <= cursor2->degree) ) {
      cursor1 = front; 
      front = front->sibling; 
    }
    //front reachs the end of result list.
    if (!front) {
      cursor1->sibling = cursor2;
      break;
    }
    
    tmp = cursor2->sibling;
    //merge cursor2 into result list.
    cursor1->sibling =cursor2;
    cursor2->sibling = front;
    //forword the cursor1 , front and cursor2. 
    cursor1 = cursor2;
    front = cursor1->sibling;
    cursor2 = tmp;
  } 
  return(result);
}
 
//
// Following routine reverse a sibling list.
//
template <class Key, class Item>
BinomialHeapNode<Key, Item>*
BinomialHeap<Key, Item>::reverseSiblings(BinomialHeapNode<Key, Item>* x) 
{
  if (!x) 
    return(0);
  x->parent = 0;
  cout << "eeels?" <<endl;
  if (!x->sibling)
    return(x);
  BinomialHeapNode<Key, Item> *result= reverseSiblings(x->sibling);
  BinomialHeapNode<Key, Item> *tmp = result;
  while(tmp->sibling)    // reach the end of result
    tmp = tmp->sibling;
  tmp->sibling = x;
  return(result);
}

//
//Routine heapUnion() has two phases. The first phase, performed
//by the call of heapMerge, merges the root lists of binomial heaps
//y and z into a singled linked list H that is sorted by degree
//into monotonically increasing order. The second phase links
//roots of equall degree until at most one root remains of each
//degree. ( An improtant operation in binomial heaps.)
//

template <class Key, class Item>
BinomialHeapNode<Key, Item>*
BinomialHeap<Key, Item>::heapUnion(BinomialHeapNode<Key, Item>* y, 
                                   BinomialHeapNode<Key, Item>* z) 
{

  BinomialHeapNode<Key, Item> *H, 
                              *prevx,
                              *nextx,
                              *x;

  // The first phase.
  H = heapMerge(y,z); 
  if (!H->sibling) //There is only one binomial tree in roote list. 
    return(H);
  cout << "merge ok."<<endl;
 
  // The second phase. 
  prevx= 0; //point to the root preceding x : prevx->sibling = x.
  x = H;   // point to the root currently being examined.
  nextx = x->sibling; //point to the root following x:
                      //x->sibling = nextx.

  //At each iteration we decide whether to link x and nextx based on 
  //their degrees and possibly the degree of nextx->sibling. 
  //An invariant of the loop is that each time we start the body of
  //the loop, both x and nextx are non-NIL. There are four cases.

  while (nextx) {
    //case1 and case2: case1 occurs when x->degree != nextx->degree,
    //case2 occurs when x is the first of three roots of equal degree,
    //in both cases we just march the pointers one position further
    //down the list.

    if ((x->degree != nextx->degree) || 
    ((nextx->sibling) && (nextx->sibling->degree == x->degree))) {
      prevx = x;
      x = nextx;
    }  // end of case1 and case2. 
    
    else {
      // case3 and case4 occur when x is the first of two roots of
      // of equal degree: 
      // x->degree == nextx->degree != next->sibling->degree.
      // in both cases we link x and nextx.
      // In case3 nextx has a larger key , nextx is linked to x. 
      // In case4 x has a larger key, x is linked to nextx.

      if (x->key <= nextx->key) {    //case3
        x->sibling = nextx->sibling;
        binomialLink(nextx, x);

      } else {                      //case4
        if (!prevx)   
          H = nextx;
        else 
          prevx->sibling = nextx;
        binomialLink(x, nextx);
        x=nextx;
      }
    }
    nextx = x->sibling;     
  } //end of while
  return(H);
}
//
// Kill the heap rooted at node. We just recursively
// kill the heaps rooted at node->child and node->sibling.
//
template <class Key, class Item>
void
BinomialHeap<Key, Item>::killHeap(BinomialHeapNode<Key,Item>*& node)
{
  if (!node) 
    return;
  if ( (!node->child) && (!node->sibling) ) {
    delete node;
    node = 0;
    _count--;    //????
    return;
  }
 
  killHeap(node->child);
  killHeap(node->sibling);
}
//
// This routine search a key through a Binomial Tree.
//
template <class Key, class Item>
BinomialHeapNode<Key,Item>*
BinomialHeap<Key, Item>::searchKey(BinomialHeapNode<Key,Item>* y,
                                   const Key& k) const
{
  if (!y) 
     return(0);
  if (y->key == k)
     return y;
  BinomialHeapNode<Key,Item>* result = searchKey(y->child, k);
  if (result)
     return result;
  return searchKey(y->sibling, k); 
}
// 
//This routine search an item through a Binomail Tree. 
// 
template <class Key, class Item>
BinomialHeapNode<Key,Item>* 
BinomialHeap<Key, Item>::searchIt(BinomialHeapNode<Key,Item>* y,
                                  const Item& item) const
{
  if (!y)  
     return(0); 
  if (ElementOps<Item>::compareItems(y->item, item)==0) 
     return y;
  BinomialHeapNode<Key,Item>* result = searchIt(y->child, item); 
  if (result) 
     return result; 
  return searchIt(y->sibling, item); 
}
//
//
//
template <class Key, class Item>
void
BinomialHeap<Key, Item>::heapIterate(BinomialHeapNode<Key,Item>* root, 
                                     BinomialHeapNode<Key,Item>*& node,
                                     int& index ) const
{   
    if (index <= 0) 
       return;
    if (root) {
       heapIterate(root->child, node, index); 
       index--; 
       if (!index) {
          node = root;
          return;
       }
       heapIterate(root->sibling, node, index);
    }
 
}
/*************************public routines**********************************/
//
//Constructor
//
template <class Key, class Item>
BinomialHeap<Key, Item>::BinomialHeap()
{
   _head = new BinomialHeapNode<Key, Item>;  //dummy header
   _count = 0;
}

// 
//Destructor 
//
template <class Key, class Item>
BinomialHeap<Key, Item>::~BinomialHeap()
{ 
  clear();
  delete _head;
}

//
// clear all the nodes in the heap.
//
template <class Key, class Item>
void
BinomialHeap<Key, Item>::clear()
{
  killHeap(_head->sibling);
} 

//
// Search the root result with minimun key in the root list of heap;
// return the pointer which points the root.
//
template <class Key, class Item>
ContainerNode*
BinomialHeap<Key, Item>::minimum() const
{ 
  BinomialHeapNode<Key,Item> *Head = _head->sibling;
  if (!Head) {
    warning("BinomialHeap::minimum(): Empty heap.");
    return(0);
  }
 
  Key min= Head->key;
  BinomialHeapNode<Key, Item> *x = Head->sibling;
  BinomialHeapNode<Key, Item> *result = Head;
 
  while (x) {
    if (x->key < min) {
      min = x->key;
      result = x;
    }
    x = x->sibling;
  }
  
  return(ContainerNode *) result;
}

//
//Make a one-node binomial heap , then call heapUnion() to unit
//it with current heap.
//

template <class Key, class Item> 
ContainerNode*
BinomialHeap<Key, Item>::insert(Key passed_key, Item passed_item) 
{
  BinomialHeapNode<Key, Item> *node = new BinomialHeapNode<Key, Item>;

  node->key  = passed_key;
  node->item = passed_item;

  BinomialHeapNode<Key, Item>* heap = heapUnion(_head->sibling, node);
  _head->sibling = heap;
  _count++;
  return(ContainerNode *) node;
}

//
//
//
template <class Key, class Item>
Item 
BinomialHeap<Key, Item>::extractMin()
{
  BinomialHeapNode<Key,Item> *Head = _head->sibling;
  if (!Head) {
    warning("BinomialHeap::extractMin(): Empty heap.");
    return(0);
  }

  Key min= Head->key;
  BinomialHeapNode<Key, Item> *x = Head->sibling;
  BinomialHeapNode<Key, Item> *prevx = Head;
  BinomialHeapNode<Key, Item> *node = Head;
  BinomialHeapNode<Key, Item> *prev = _head;

  while (x) {     // search minimum throug the root list. 
    if (x->key < min) {
      min = x->key;
      prev = prevx;
      node = x;
    } 
    prevx = x;
    x = x->sibling;
  }
 
  prev->sibling = node->sibling; // delete the minimum node.
  BinomialHeapNode<Key,Item> *child = node->child;
  Item item = node->item;
  delete node;
  _count--;
  cout << "ok find min."<<endl;
  cout << "minimum deleted :"<< item <<endl;

  BinomialHeapNode<Key,Item> *H ;

  // reverse node's children

  H = reverseSiblings(child);
  cout <<"ok reverse child list."<<endl;
  _head->sibling = heapUnion(Head,H);
  // unite the sibling list with current heap.
  return(item);
}

//
//
//

template <class Key, class Item>
void 
BinomialHeap<Key, Item>::decreaseKey(BinomialHeapNode<Key,Item>* node, Key k)
{
  if (!node) {
    error("BinomialHeap::decreaseKey() : NUll pointer.");
    return;
  }
  if (k >= node->key) {
    error("BinomialHeap::decreaseKey()
          : new key is greater than current key");
    return;
  }
  
  node->key = k;
  Key tmpk;
  Item tmpi;
  BinomialHeapNode<Key, Item> *x = node;
  BinomialHeapNode<Key, Item> *parent = x->parent;
  while ( (parent) && (parent->key > k) ) {
     tmpk = parent->key;
     tmpi = parent->item;    // swap contents of current node with parent.
     parent->key = x->key;
     parent->item = x->item;
     x->key = tmpk;
     x->item = tmpi;
     x = parent;
     parent = x->parent;
  } 
}
//
//
//
template <class Key, class Item>
void
BinomialHeap<Key, Item>::changeKey(BinomialHeapNode<Key,Item>* node, Key k)
{
  if (!node) {
    error("BinomialHeap::changeKey() : NUll pointer.");
    return;
  } 
  if ( k = node->key) {
     warning("BinomialHeap::changeKey() : key is not changed.");
     return;
  }
  if (k < node->key) {
     decreaseKey(node, k);
     return;
  }
  node->key = k;
  Key tmpk;
  Item tmpi;
  BinomialHeapNode<Key, Item> *x = node;
  BinomialHeapNode<Key, Item> *child = x->child;
  
  while ( (child) && (child->key < k) ) {
     tmpk = child->key;
     tmpi = child->item;    // swap contents of current node with child.
     child->key = x->key;
     child->item = x->item;
     x->key = tmpk;
     x->item = tmpi;
     x = child;
     child = x->child;
  }
  
}
//
//
//
template <class Key, class Item>
void 
BinomialHeap<Key, Item>::merge(BinomialHeap<Key,Item> &H)
{
  if ( H.size() == 0) {
       warning("BinomialHeap<Key,Item>::merge(BinomialHeap &H)
                : merge empty heap."); 
       return;
    }
  BinomialHeapNode<Key,Item> *Hhead = H.getHead(); 
  _head->sibling =  heapUnion(_head->sibling,Hhead->sibling);
  delete Hhead;
  _count += H.size();
}
//
//
//
template <class Key, class Item>
void
BinomialHeap<Key, Item>::remove(BinomialHeapNode<Key,Item>* passed_node)
{
  if (!passed_node) {
     warning("BinomialHeap::remove(): NULL pointer.");
     return;
  } 
  decreaseKey(passed_node, MINUSINF);
  extractMin();
}
//
//
//
template <class Key, class Item>
void 
BinomialHeap<Key, Item>::deleteKey(Key k)
{
   BinomialHeapNode<Key,Item>* node = search(k); 
   remove(node);
}
//
//
//
template <class Key, class Item>
void
BinomialHeap<Key, Item>::remove(Item passed_item) 
{ 
   BinomialHeapNode<Key,Item>* node = searchItem(passed_item);
   remove(node);
}

//
//
//
template <class Key, class Item>
BinomialHeapNode<Key,Item>*
BinomialHeap<Key, Item>::search(const Key& passed_key) const
{
  if (!_head->sibling) {
     warning("BinomialHeap::search(): Empty heap.");
     return(0);
  }
  return searchKey(_head->sibling, passed_key);
}
//
//
//
template <class Key, class Item>
BinomialHeapNode<Key,Item>*
BinomialHeap<Key, Item>::searchItem(const Item& passed_item) const
{
  if (!_head->sibling) {
     warning("BinomialHeap::searchItem(): Empty heap.");
     return(0);
  }
  return searchIt(_head->sibling, passed_item);
}
//
//
//
template <class Key, class Item>
Bool
BinomialHeap<Key, Item>::memberQ(const Item& e) const
{
  if (!_head->sibling) {
     warning("BinomialHeap::memberQ(): Empty heap.");
     return FALSE;
  }
  if (searchItem(e))
     return TRUE;
  else
     return FALSE;
}
// 
// 
// 
template <class Key, class Item>
int
BinomialHeap<Key, Item>::iterate(Iterator<Item>& iterator, Item& item) const
{
   if (_count <= 0)
       return 0;
   if (iterator._index > _count || iterator._index < 0)
       return 0;
   else {
       iterator._index++;
       BinomialHeapNode<Key,Item>* node = 0;
       int index = iterator._index++;
       heapIterate(_head->sibling, node, index);
       if (node) {
           item = node->item;
           return 1;
       } else 
           return 0; 
   }
       
}
//
// This function prints out all the items in the heap
// in the order of heap.
//
template <class Key, class Item>
ostream&
BinomialHeap<Key,Item>::print(ostream& os) 
{
    os << "(";

    Iterator<Item> get_next(this);
    Item i;
    while (get_next(i))
        os << i << " ";
    os << ")" ;
    return os;
}
//
//
//
 
template <class Key, class Item>
BinomialHeapNode<Key,Item>*
BinomialHeap<Key,Item>::getNode(int index) const 
{
   BinomialHeapNode<Key,Item>* node = 0;
   int j = index;
   heapIterate(_head->sibling, node, j);
   return node;
}

//
//
//

template <class Key, class Item>
void
BinomialHeap<Key,Item>::scramble()
{  
    if (_count <= 1)
       return;
    int j;
    BinomialHeapNode<Key, Item>** heap;
    heap = new BinomialHeapNode<Key,Item>*[_count + 1];
    BinomialHeapNode<Key, Item>* tmp;
    for (int i = 1; i <= _count; i ++) {
        heap[i] = new BinomialHeapNode<Key,Item>;
        tmp = getNode(_count - i + 1);
        heap[i]->key = tmp->key;
        heap[i]->item = tmp->item; 
    }
    int count = _count;
    clear();
    
    // generate a random permutation on heap[].
    for( i = count; i >= 1; i--) {
       j = (int)Link_randomLong() % i + 1 ; //generate a random number in [1,i)
       tmp = heap[i];
       heap[i] = heap[j];   //swap _heap[i] with _heap[j].
       heap[j] = tmp;
    };
    
    // rebuild the heap from the permutation
    BinomialHeapNode<Key, Item> *H = 0; 
    for (i = 1; i <= count; i++) 
       H =  heapUnion(H, heap[i]);

    _head->sibling = H;
    delete [] heap;       
}
//
// Produce a human-readable display of BinaryHeap.
// BinaryHeap is displayed as a binary tree.
//
template <class Key, class Item>
ostream &
BinomialHeap<Key,Item>::display(ostream& os ) const
{
    if (!_count) 
       os <<"Empty BinomialHeap."<<endl;
    else {
       os << "<";
       BinomialHeapNode<Key, Item>* node; 
       for (int i = 1; i < _count ; i++) {
         os << "(";
         node = getNode(i);
         os << node->key;
         os <<",";
	 ElementOps<Item>::displayItem(os, node->item);
         os << ")";
          os <<",";
       } 
       node = getNode(_count);
       os << "(";
       os << node->key;
       os <<",";
       ElementOps<Item>::displayItem(os, node->item);
       os << ")";
       os << ">";
       os << endl;
   }   
   return os;
}
//
// Copies the contents of h to current _heap.
//
template <class Key, class Item>
BinomialHeap<Key, Item>&
BinomialHeap<Key,Item>::operator=(const BinomialHeap<Key,Item>& h)
{
   if (&h == this)
      return *this;
   clear();
   int hsize = h.size();
   if (!hsize)
      return *this;
   _count = hsize;
 
   BinomialHeapNode<Key,Item> *tmp, *node;
   for (int i = 1; i <= _count; i++) {
     node = new BinomialHeapNode<Key,Item>;
     tmp = h.getNode(i);
     node->item = tmp->item;
     node->key = tmp->key;
     _head->sibling = heapUnion(_head->sibling, node); 
   }
   return *this;
}