jueves, 10 de diciembre de 2009

Preparar una lista de Objetos que se almacenan en arbol para presentarla en un combo

Algoritmo (no se si eficiente, pero como mucho de un tiempo de computacion n^2) para dada una lista de objetos, en este caso Category, que se almacena en forma de arbol a través de la propiedad parentCagegory, poderse presentar en un combo ordernadas en arbol. Lo típico es recogerlas primero ordenadas alfabeticamente ( o como se quiera), despues pasar este algoritmo y presentarlas ya en el combo:

private static List<Category> getAllCategoriesAsTree(List<Category> l , boolean indent, String indentText) {

Set<Category> allChildCategories = new HashSet<Category>();
Map<Long,Integer> indentationLevels = new HashMap<Long,Integer>();
List<Category> result = new ArrayList<Category>();

for (Category c:l) {
if (c.getParentCategory()==null) {
result.add(c);
indentationLevels.put(c.getId(), 0);
}
else
allChildCategories.add(c);
}


while (!allChildCategories.isEmpty()) {
if (allChildCategories.iterator().hasNext()) {
Category childCategory = allChildCategories.iterator().next();

int s = result.size();
for (int i=0;i<s;i++) {
if (result.get(i).getId()==childCategory.getParentCategory().getId()) {
indentationLevels.put(childCategory.getId(),
indentationLevels.get(childCategory.getParentCategory().getId())+1);
result.add(i+1, childCategory);
s = result.size();
}
}
allChildCategories.remove(childCategory);
}

}

if (indent) {
for (Category c:result)
c.setName(StringUtils.repeat(indentText, indentationLevels.get(c.getId()))+c.getName());
}

return result;
}



Para probarlo

List<Category> l = new ArrayList<Category>();

Category c0 = new Category(0L,"Cero",null);

Category c1 = new Category(1L,"Uno",null);

Category c2 = new Category(2L,"Dos",null);

Category c01 = new Category(11L,"CeroUno",c0);
Category c02 = new Category(12L,"CeroDos",c0);

Category c11 = new Category(21L,"UnoUno",c1);
Category c12 = new Category(22L,"UnoDos",c1);

Category c21 = new Category(31L,"DosUno",c2);
Category c22 = new Category(32L,"DosDos",c2);


Category c021 = new Category(1021L,"CeroDosUno",c02);
Category c111 = new Category(1111L,"UnoUnoUno",c11);
Category c221 = new Category(1221L,"DosDosUno",c22);

l.add(c0);
l.add(c1);
l.add(c2);
l.add(c01);
l.add(c02);
l.add(c11);
l.add(c12);
l.add(c21);
l.add(c22);
l.add(c021);
l.add(c111);
l.add(c221);

List<Category> l2 = getAllCategoriesAsTree(l, true, "\t");
for (Category c:l2){
System.out.println(c.getName());
}


y el resultado es

Cero
CeroUno
CeroDos
Uno
UnoUno
UnoDos
Dos
DosUno
DosDos
DosDosUno