/**
 *  Classe Ordena.java
 *  Autor: Pedro Luis Furio Raphael
 *  Data 01/02/10
 */

package classesUteis;

import java.util.ArrayList;
import java.util.List;

import digrafos.Digrafo;
import digrafos.Par;

public class Ordena {

  public static List<Par> ordenacaoContagem(Digrafo T, List<Par> S) {
    int[] v = new int[T.vertices.size()];
    int[] w = new int[T.vertices.size()];
    Par[] novoS = new Par[T.vertices.size()];
    for (Par p : S) {
      v[p.dist]++;
    }
    w[0] = v[0];
    for (int i = 1; i < T.vertices.size(); i++) {
      w[i] = w[i - 1] + v[i];
    }
    for (Par p : S) {
      int i = 0;
      while (novoS[w[p.dist] - v[p.dist] + i] != null)
        i++;
      novoS[w[p.dist] - v[p.dist] + i] = p;
    }
    List<Par> Slinha = new ArrayList<Par>(T.vertices.size());
    for (Par p : novoS) {
      if (p == null)
        continue;
      Slinha.add(p);
    }
    v = null;
    w = null;
    novoS = null;
    return Slinha;
  }
}