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

/**
 * @author André Santanchè
 */
public class WHeap implements MinimumHeap
{
  private int w = 0;
  private WElement q[];
  private int p = 0;  // posicao corrente
  
  public WHeap(int w)
  {
    this.w = w;
  }
  
  public void insertTop(WElement x)
  {
    int key = x.value.getKey();
    if (q[key] != null) {
      x.next = q[key];
      q[key].prev = x;
    }
    q[key] = x;
  }
  
  public void remove(WElement x)
  {
    if (x.prev == null) {
      int key = x.value.getKey();
      q[key] = q[key].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 WElement[(elem.length - 1) * w + 1];
    for (int i = 0; i < elem.length; i++) {
      if (elem[i].getKey() == Integer.MAX_VALUE) // tratamento especial para infinito
        elem[i].setKey(q.length - 1);
      WElement wel = new WElement(elem[i]);
      elem[i].setIndex(wel); 
      insertTop(wel);
    }
      
    p = 0;
  }

  public HeapElement heapMinimum()
  {
    while (p < q.length && q[p] == null)
      p++;
      
    if (p == q.length)
      return null;
    else {
      HeapElement m = q[p].value;
      return m;
    }
  }

  public HeapElement heapExtractMin()
  {
    HeapElement m = heapMinimum();
    if (m != null)
      remove(q[p]);
    return m;
  }

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

  public boolean isEmpty()
  {
    while (p < q.length && q[p] == null)
      p++;
    return (p == q.length);
  }
  
  public String toString()
  {
    String ts = "";
    for (int i = 0; i < q.length; i++)
      if (q[i] != null) {
        ts += "key:" + i + "(" + q[i];
        WElement we = q[i].next;
        while (we != null) {
          ts += "," + we;
          we = we.next;
        }
        ts += "); "; 
      }
    return ts;
  }

  private class WElement
  {
    public HeapElement value;
    public WElement prev = null,
                    next = null;
    
    public WElement(HeapElement value)
    {
      this.value = value;
    }
    
    public String toString()
    {
      return value.toString();
    }
  }

}