// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): ??

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

#ifndef BinomialHeap_h
#define BinomialHeap_h

#include <iostream.h>
#include <LINK/basic/Container.h>
#include <LINK/basic/Iterator.h>
#include <LINK/basic/Collection.h>
#define MINUSINF -1000001


template <class Key, class Item>
class  BinomialHeapNode: public ContainerNode {
    friend class BinomialHeap<Key, Item>;
public:
    BinomialHeapNode() : item(0), key(0), degree(0), parent(0),
                         child(0), sibling(0) { }
    BinomialHeapNode(Key key, Item item) : key(key), item(item),
                         degree(0), parent(0), child(0), sibling(0) {}
    virtual ~BinomialHeapNode() { };
//    Item    info() { return item;}
//    Key     key() { return key;}

//private:
    Item item;    // holds the information
    Key  key;     // key bound on item.
    int degree;   // degree of this node 
    BinomialHeapNode<Key, Item>* parent; // pointer to parent   
    BinomialHeapNode<Key, Item>* child ; // pointer to child.
    BinomialHeapNode<Key, Item>* sibling; // 
    
};

template <class Key, class Item> 
class BinomialHeap: public Dictionary<Key,Item> { 
  public:
    BinomialHeap();
    virtual ~BinomialHeap();     

    BinomialHeap<Key, Item>&       operator=(const BinomialHeap<Key,Item>& h);
    int                 size() const    { return _count; 		}
    Bool                emptyQ() const  { return _count ? FALSE : TRUE; }
    Bool                fullQ() const   { return FALSE; 		}
    Bool                memberQ(const Item& e) const;
    Bool                sortedQ() const { return FALSE;			}
    DataType            type() const    { return BINOMIALHEAP; 		}
    ContainerNode*      insert(Key passed_key, Item passed_item);
    ContainerNode*      minimum() const;
    Item		min() const  { return info(minimum()); }
    Item                extractMin(); 
    Item                get() { return extractMin();}
    void                remove(BinomialHeapNode<Key,Item>* passed_node);
    void                remove(Item passed_item);
    void                clear();
    ostream&            print(ostream& os) ;
    
    BinomialHeapNode<Key,Item>*      search(const Key& passed_key) const;
    BinomialHeapNode<Key,Item>*      searchItem(const Item& passed_item) const;
    BinomialHeapNode<Key,Item>*      getHead() const {return _head;}
    BinomialHeapNode<Key,Item>*      getNode(int index) const; 

    void 		decreaseKey(BinomialHeapNode<Key,Item>* node,Item k);  
    void                deleteKey(Key k);
    void                changeKey(BinomialHeapNode<Key,Item>* node, Key k);
    void 		merge(BinomialHeap<Key,Item>& H);
//    void                buildHeap(Sequence<ContainerNode> seq);
//    void                buildHeap(Array<ContainerNode> array);
    void                scramble();
    ostream&                display(ostream& os) const;
  private:
    int                 iterate(Iterator<Item>& it, Item& item) const;
    int _count;
    BinomialHeapNode<Key, Item>* _head;
 
    BinomialHeapNode<Key, Item>*
                    binomialLink(BinomialHeapNode<Key,Item>* y,
                                 BinomialHeapNode<Key,Item>* z);
    BinomialHeapNode<Key, Item>*
                    heapMerge(BinomialHeapNode<Key,Item>* y,
                              BinomialHeapNode<Key,Item>* z);
    BinomialHeapNode<Key,Item>*
                    heapUnion(BinomialHeapNode<Key,Item>* y,
                              BinomialHeapNode<Key,Item>* z);
    BinomialHeapNode<Key,Item>*
                    reverseSiblings(BinomialHeapNode<Key,Item>* y);
    BinomialHeapNode<Key,Item>*
                    searchKey(BinomialHeapNode<Key,Item>* y,
                              const Key& k) const;
    BinomialHeapNode<Key,Item>*
                    searchIt(BinomialHeapNode<Key,Item>* y,
                             const Item& item) const;
    void killHeap(BinomialHeapNode<Key,Item>*& node);
    void heapIterate(BinomialHeapNode<Key,Item>* root,
                     BinomialHeapNode<Key,Item>*& node,
                     int& index) const;
   

};

#ifdef DEFINE_TEMPLATE
#include <LINK/basic/BinomialHeap.cc>
#endif


#endif