// Last edited on 2000-09-03 05:57:11 by stolfi
// Um "heap" de Nodos, ordenado pelo campo "custoTot".

import Nodo;

class MonteDeNodos {
  
  private Nodo[] data;
  private int n;

  public MonteDeNodos(int n)
    // Cria um "heap" para n nodos;
    {
      data = new Nodo[n];
      this.n = 0;
    }
  
  public int tamanho()
    { return n; }

  public Nodo remove()
    // Remove o nó de menor "custoTot"
    {
      Nodo umin = null;
      switch (n) {
      case 0:
        return null;
      case 1:
        umin = data[0];
        n = 0;
        break;
      default:
        umin = data[0];
        data[0] = data[n-1]; 
        data[0].indice = 0;
        n--;
        desce(0);
        break;
      }
      return umin;
    }

  public boolean possui(Nodo u)
    // True se o nodo "u" está no monte.
    { 
      return 
        (u.indice >= 0) && 
        (u.indice < n) && 
        (data[u.indice] == u);
    }
  
  public void insere(Nodo u)
    {
      // System.out.println("Inserindo " + u + " em data[" + n + "]");
      data[n] = u; 
      u.indice = n;
      n++;
      sobe(n - 1);
    }

  public void ajusta(Nodo u)
    // Ajusta a posição do nó "u" após uma redução no seu "custoTot"
    {
      int indice = u.indice;
      if ((indice >= 0) && (indice < n) && (data[indice] == u)) 
        { sobe(indice); }
    }

  private void troca(int pos1, int pos2)
    {
      Nodo temp = data[pos1]; data[pos1] = data[pos2]; data[pos2] = temp;
      data[pos1].indice = pos1;
      data[pos2].indice = pos2;
    }

  private void sobe(int pos)
    // Ajusta o elemento "data[pos]" na direção da raiz.
    {
      int paiPos = pos / 2;
      Nodo curr = data[pos];
      Nodo pai = data[paiPos];
      if (pos > 0 && curr.custoTot < pai.custoTot)
        { troca(pos, paiPos); sobe(paiPos); }
    }

  private void desce(int pos)
    {
      Nodo curr = data[pos];
      int filho1Pos = pos * 2 + 1;
      Nodo filho1 = (filho1Pos < n ? data[filho1Pos] : null);
      int filho2Pos = pos * 2 + 2;
      Nodo filho2 = (filho2Pos < n ? data[filho2Pos] : null);
      if (filho1 != null && filho2 != null) 
        { int filhoPos = (filho1.custoTot < filho2.custoTot ? filho1Pos : filho2Pos);
          Nodo filho = data[filhoPos];
          if (curr.custoTot > filho.custoTot)
            { troca(pos, filhoPos); desce(filhoPos); }
        }
      else if (filho1 != null)
        { if (curr.custoTot > filho1.custoTot)
            { troca(pos, filho1Pos); desce(filho1Pos); }
        } 
      else if (filho2 != null)
        { if (curr.custoTot > filho2.custoTot)
            { troca(pos, filho2Pos); desce(filho2Pos); }
        }
  }

  public void debuga(String message)
    {
      System.out.println("MonteDeNodos(" + message + ")");
      for (int i = 0; i < n; i++)
        { Nodo u = data[i];
          System.out.println("  " + u + " " + u.prev + " " + u.custoTot);
        }
    }
}