// 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 BinaryHeap_h
#define BinaryHeap_h

#include <LINK/basic/Container.h>


template <class Key, class Item> 
class BinaryHeapNode : public ContainerNode {
public:
    BinaryHeapNode() : index(0), key(0), item(0) {}
    virtual ~BinaryHeapNode() {};
    void               *info() const {return (void *) &item;}

    int		index;		// logical view of the heap
    Key		key;		// keys
    Item	item;		// value associated with key
};


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

    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 BINARYHEAP; 		}

    ContainerNode*	insert(Key passed_key, Item passed_item); 
    void		remove(Item passed_item)	{}
    Item		get();
    void		clear()				{}

    ostream&		display(ostream& os) const;

    BinaryHeapNode<Key,Item>*	minimum() const; 
    Item			min() const  { return info(minimum()); }
    BinaryHeapNode<Key,Item>*	extractMin(); 

    void		decreaseKey(ContainerNode* HeapNode, Key k);
    			// decreases the value of the key stored in node.  
    			// note: no check is made to insure that k is less
    			// than the current key, so beware
    void		deleteKey(ContainerNode* HeapNode);
    			// deletes the key in the heap pointed to by node

private: 
    int		iterate(Iterator<Item>& i, Item& e) const;
    int		parent(int i)	{ return i >> 1; }		// floor(i/2)
    int		left(int i)	{ return i << 1; }		// i*2
    int		right(int i)	{ return ((i<<1) | 0x1); }	// i*2+1
    void	heapify(int k); // used to update the heap

    int				_count;		// number of elements
    int				_size;		// maximum size of the heap
    BinaryHeapNode<Key,Item>**	_heap;		// contains keys in order
};


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


#endif