Skip to content

Instantly share code, notes, and snippets.

@felipebizz
Last active January 19, 2016 13:57
Show Gist options
  • Save felipebizz/513f8a44ca8d40a8d991 to your computer and use it in GitHub Desktop.
Save felipebizz/513f8a44ca8d40a8d991 to your computer and use it in GitHub Desktop.
Tree with Ancestors e descendants
package global.visto.core.service;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Classe que varre arvore buscando descentes e ascendentes a partir de um nó
* Created by felipe on 19/01/16.
*/
public class Tree {
/**
* Busca nó no Map
* @param map map de NODE
* @param id id do nó a ser encontrado
* @return Map com o nó e parent
*/
public Map<Long, Long> findNode(Map<Long, Long> map, final long id){
Map<Long, Long> nodefound = new HashMap<>();
for (Map.Entry<Long, Long> entry : map.entrySet()) {
if(entry.getKey().equals(id)){
nodefound.put(entry.getKey(), entry.getValue());
}
}
return nodefound.values().size() == 0 ? null : nodefound;
}
/**
* Busca a lista de Ancestrais do Nó passado
*
* @param nodeMap Map com todos nos
* @param id id do no
* @param curr Lista corrente que armazena os ancestrais do id pesquisado
* @return Lista com os acentrais do node
*/
public List ancestors(Map<Long, Long> nodeMap, final Long id, List<Long> curr) {
if (curr == null) {
curr = new ArrayList<>();
}
Map<Long, Long> node = this.findNode(nodeMap, id);
if (node == null) {
return curr;
}
Long parent = node.get(id);
if (parent == null) {
return curr;
}
curr.add(parent);
return ancestors(nodeMap, parent, curr);
}
/**
* Verifica se é Ancestral
* @param nodeMap Map de nodes
* @param ancestorId Id do ancestral
* @param candidateId id do nó raiz
* @return true / false
*/
public Boolean isAncestor(Map<Long, Long> nodeMap, Long ancestorId, Long candidateId){
List<Long> list = this.ancestors(nodeMap, candidateId, new ArrayList<Long>());
for(Long node : list){
if(node.longValue() == ancestorId.longValue()){
return true;
}
}
return false;
}
public Boolean isDescendant(Map<Long, Long> nodeMap, Long ancestorId, Long candidateId){
return isAncestor(nodeMap, candidateId, ancestorId);
}
/**
* Retorna lista de todos NODEs descendentes de Id passado
*
* @param nodeMap Map de node
* @param ancestorId id do ancestral
* @return lista de ids descendentes do ancestorId
*/
public List<Long> descendants(Map<Long, Long> nodeMap, Long ancestorId){
List<Long> descendantsList = new ArrayList<>();
for (Map.Entry<Long, Long> entry :nodeMap.entrySet()){
if(isDescendant(nodeMap, entry.getKey(), ancestorId)){
descendantsList.add(entry.getKey());
}
}
return descendantsList;
}
public static void main (String[] args){
Tree tree = new Tree();
Map<Long, Long> nodeMap = new HashMap<>();
nodeMap.put(21L, 14L);nodeMap.put(17L, 14L);
nodeMap.put(20L, 14L);nodeMap.put(19L, 12L);
nodeMap.put(15L, 13L);nodeMap.put(14L, 13L);
nodeMap.put(13L, 1L);nodeMap.put(1L, null);
nodeMap.put(22L, 15L);nodeMap.put(2L, null);
nodeMap.put(11L, 1L);nodeMap.put(12L, 1L);
nodeMap.put(18L, 1L);nodeMap.put(111L, 11L);
System.out.println("Find by node :" + tree.findNode(nodeMap, 14));
System.out.println("Is Ancestor ?: " + tree.isAncestor(nodeMap, 14L, 17L));
System.out.println("Ancestors : " + tree.ancestors(nodeMap, 17L, new ArrayList<Long>()));
System.out.println("Descendants : " + tree.descendants(nodeMap, 1L));
/*
Essa é arvore que foi montada a partir do nodeMap acima, nessa arvore é possivel varrer
todos ancestrais e dependentes
+-- 11 ----- 111
|
|
|
1 --+-- 18
|
|
|
+-- 12---19 +--- 20
| |
| +---14---+--- 17
| | |
+-- 13 --+ +--- 21
|
|
+---15---22
2
*/
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment