// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): ?Michael Murphy? (Los Alamos Nat. Lab.)

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


template <class Key, class Item> 
BinaryHeap<Key,Item>::BinaryHeap() 
{
    _size = BINHEAPSIZE;
    _size++;
    _heap = new BinaryHeapNode<Key,Item>*[_size];
    for (int i=0; i < _size; i++)
        _heap[i] = 0;
    _count = 0;
}


//
// constructor for a binary heap
//
template <class Key, class Item> 
BinaryHeap<Key,Item>::BinaryHeap(int sz) 
{
    _size = sz;
    _size++;
    _heap = new BinaryHeapNode<Key,Item>*[_size];
    for (int i=0; i < _size; i++)
        _heap[i] = 0;
    _count = 0;
}


//
// destructor for a binary heap
//
template <class Key, class Item> 
BinaryHeap<Key,Item>::~BinaryHeap() 
{
    for (int i=1; i< _size; i++)
        if (_heap[i])
            delete(_heap[i]);
    delete _heap;
}


template <class Key, class Item> 
void 
BinaryHeap<Key,Item>::heapify(int i) 
{
    int l = left(i);
    int r = right(i);
    int smallest;
    BinaryHeapNode<Key, Item> *temp;

    if (l <= _count && (_heap[l]->key <= _heap[i]->key))
        smallest = l;
    else
        smallest = i;

    if (r <= _count && (_heap[r]->key <= _heap[smallest]->key))
        smallest = r;

    if (smallest != i) {
        temp = _heap[i];
        _heap[i] = _heap[smallest];
        _heap[smallest] = temp;

        _heap[i]->index = i;
        _heap[smallest]->index = smallest;

        heapify(smallest);
    }  
}


template <class Key, class Item> 
ContainerNode* 
BinaryHeap<Key,Item>::insert(Key passed_key, Item passed_item) 
{
    int i;
    BinaryHeapNode<Key, Item>* h = new BinaryHeapNode<Key, Item>;

    _count++;
    if (_count == _size) {
        BinaryHeapNode<Key, Item>**  	oldheap = _heap;
        int oldsize = _size;

        _size += _size/2 +1;

        _heap = new BinaryHeapNode<Key, Item>*[_size];

        for (i=0; i < oldsize; i++)
	    _heap[i] = oldheap[i];
        for (i=oldsize; i < _size; i++)
            _heap[i] = 0;

        delete oldheap;
    } else {
        if (_heap[_count]) {
            delete _heap[_count];
            _heap[_count] = 0;
        }
    }


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

    i = _count;

    while (i > 1 && _heap[parent(i)]->key > passed_key) {
        _heap[i] = _heap[parent(i)];
        _heap[i]->index = i;
        i = parent(i);
    }

    h->index = i;
    _heap[i] = h;

    return (ContainerNode*) h;  // returns pointer to node of inserted item
}


template <class Key, class Item>
inline 
BinaryHeapNode<Key,Item>*
BinaryHeap<Key,Item>::minimum()  const
{
    //BinaryHeapNode<Key, Item> result;
    //result.index = _heap[1]->index;
    //result.key = _heap[1]->key;
    //result.item = _heap[1]->item;

    //return result;
    return _heap[1];
}

template <class Key, class Item>
void
BinaryHeap<Key,Item>::clear() 
{
	while (extractMin());
}

template <class Key, class Item>
BinaryHeapNode<Key,Item>*
BinaryHeap<Key,Item>::extractMin() 
{
    //BinaryHeapNode<Key, Item> min;
    BinaryHeapNode<Key, Item>* min;

    if (_count == 0)
        return(0);
        //return(min);

    //min.index = _heap[1]->index;
    //min.key = _heap[1]->key;
    //min.item = _heap[1]->item;
  
    //swap pointers
    min = _heap[1];
    _heap[1] = _heap[_count]; 
    _heap[1]->index = 1;
    _heap[_count] = min;
 
    _count--;
    heapify(1);

    //return min;
    return min;
}


template <class Key, class Item>
void 
BinaryHeap<Key,Item>::decreaseKey(ContainerNode* passed_node, Key k) 
{
    BinaryHeapNode<Key,Item>* node = (BinaryHeapNode<Key,Item>*) passed_node;
    node->key = k;
    int i = node->index;

    while (i > 1 && _heap[parent(i)]->key > k) {
        _heap[i] = _heap[parent(i)];
        _heap[i]->index = i;
        i = parent(i);
    }
    _heap[i]=node;
    node->index = i;
} 


template <class Key, class Item>
void 
BinaryHeap<Key,Item>::deleteKey(ContainerNode* passed_node) 
{
    BinaryHeapNode<Key,Item>* node = (BinaryHeapNode<Key,Item>*) passed_node;
    if (node->index != _count) {  // need to rebuild heap

        // shift up or down depending on size of key
        if (node->key < _heap[_count]->key) {  // downheap needed
            _heap[node->index] = _heap[_count];
            _heap[node->index]->index = node->index;
            _count--;
            heapify(node->index);
        } else if (node->key > _heap[_count]->key) { // upheap needed
            int i = node->index;
            while (i > 1 && _heap[parent(i)]->key > _heap[_count]->key) {
                _heap[i] = _heap[parent(i)];
                _heap[i]->index = i;
                i = parent(i);
            }
            _heap[i] = _heap[_count];
            _heap[i]->index = i;

            _count--;
            _heap[node->index] = _heap[_count];
            _heap[node->index]->index = node->index;
        }
    } else {
        // nothing needs to be done except:
        _count--;
    }
    delete node;   // killed to avoid memory holes 
}


template <class Key, class Item>
Item
BinaryHeap<Key,Item>::get()
{
    if (_count == 0)
        return 0;
    else {
        BinaryHeapNode<Key,Item>* tmp = extractMin();
        return tmp->item;
    }
}


template <class Key, class Item>
Bool
BinaryHeap<Key,Item>::memberQ(const Item& passed_item) const
{
    for (int i=1; i< _size; i++)
        if (ElementOps<Item>::compareItems(_heap[i]->item, passed_item)==0)
            return TRUE;
    return FALSE;
}


template <class Key, class Item>
int
BinaryHeap<Key,Item>::iterate(Iterator<Item>& iterator, Item& item) const
{
    if (iterator._index == -1) {
        if (_count == 0)
            return 0;
        else {
            iterator._index = 0;
            item = _heap[0]->item;
            return 1;
        }
    } else
        if (iterator._index >= _count || _count == 0)
            return 0;
        else {
            iterator._index++;
            item = _heap[iterator._index]->item;
            return 1;
        }
}

template <class Key, class Item>
ostream&
BinaryHeap<Key,Item>::display(ostream& os) const
{
    Iterator<Item> get_next(this);
    Item i;
    Bool start = FALSE;
    os << "[";
    while (get_next(i))
        if (!start) {
                ElementOps<Item>::displayItem(os, i);
                start = TRUE;
        } else {
                os << " ";
                ElementOps<Item>::displayItem(os, i);
	}
    os << "]";
    return os;
}