/*
 * Created on 10/06/2003
 */
package heap;

/**
 * @author André Santanchè
 */
public class WBinaryHeap implements MinimumHeap
{
  private int w = 0;
  private BinaryHeap q;
  private int wq[];
  
  public WBinaryHeap(int w)
  {
    this.w = w;
  }
  
  public void insertTop(WBElement x)
  {
    int key = x.value.getKey();
    if (wq[key] != -1)
    {
      int index = wq[key];
      WBElement he = (WBElement)q.elementAt(index);
      WBElement we = (WBElement)he.value.getIndex();
      x.next = we;
      we.prev = x;
      q.setElement(index, x);
    } else {
      q.heapInsert(x);
      wq[key] = ((Integer)x.getIndex()).intValue();
    }
  }
  
  public void remove(WBElement x)
  {
    int key = x.value.getKey();
    int index = wq[key];
    
    if (x.prev == null) {
      if (x.next == null) {
        q.heapDelete(x);
        wq[key] = -1;
      } else
        q.setElement(index, x.next);
    } else
      x.prev.next = x.next;
    
    if (x.next != null)
      x.next.prev = x.prev;
    
    x.prev = null;
    x.next = null;
  }
  
  public void buildMinHeap(HeapElement[] elem)
  {
    q = new BinaryHeap();
    wq = new int[(elem.length - 1) * w + 1];
    for (int j = 0; j < wq.length; j++)
      wq[j] = -1;
    
    for (int i = 0; i < elem.length; i++) {
      if (elem[i].getKey() == Integer.MAX_VALUE) // tratamento especial para infinito
        elem[i].setKey(wq.length - 1);
      WBElement wel = new WBElement(elem[i]);
      elem[i].setIndex(wel); 
      insertTop(wel);
    }
  }

  public HeapElement heapMinimum()
  {
    WBElement we = ((WBElement)q.heapMinimum());
    if (we == null)
      return null;
    else
      return we.value;
  }

  public HeapElement heapExtractMin()
  {
    HeapElement m = heapMinimum();
    if (m != null) {
      remove((WBElement)m.getIndex());
      if (heapMinimum() == null)
        q.heapExtractMin();
    }
    return m;
  }

  public void decreaseKey(HeapElement el, int key)
  {
    if (key > el.getKey())
      System.out.println("invalid new key");
    else {
      WBElement wel = (WBElement)el.getIndex();
      remove(wel);
      el.setKey(key);
      insertTop(wel);
    }
  }

  public boolean isEmpty()
  {
    return (heapMinimum() == null);
  }
  
  public String toString()
  {
    String ts = "";
    for (int i = 0; i < wq.length; i++)
      if (wq[i] != -1) {
        ts += "key:" + i + "(";
        WBElement we = (WBElement)q.elementAt(wq[i]).getIndex();
        ts += we;
        we = we.next;
        while (we != null) {
          ts += "," + we;
          we = we.next;
        }
        ts += "); "; 
      }
    return ts;
  }

  private class WBElement implements HeapElement
  {
    public HeapElement value;
    public WBElement prev = null,
                    next = null;
    private Object index;
    
    public WBElement(HeapElement value)
    {
      this.value = value;
    }
    
    public int getKey()
    {
      return value.getKey();
    }
    
    public void setKey(int key)
    {
      value.setKey(key);
    }
    
    public Object getIndex()
    {
      return index;
    }
    
    public void setIndex(Object index)
    {
      this.index = index;
    }
    
    public String toString()
    {
      return value.toString();
    }
  }

}