Posted By

wickedhood on 07/01/14


Tagged


Versions (?)

OrderedTree


 / Published in: Java
 

the tree structure

  1. import java.util.*;
  2.  
  3. public class OrderedTree<T> {
  4.  
  5. private Node<T> root = null;
  6. private boolean found = false;
  7. private Node<T> temp = null;
  8. public Stack<Node<T>> path = new Stack<>();
  9. public ArrayList<Node<T>> allNodes = new ArrayList<>();
  10.  
  11. public void printTree() {
  12. reset(this.root);
  13. printTree(this.root);
  14. System.out.println();
  15. }
  16.  
  17. private void printTree(Node<T> G) {
  18. System.out.print(G.element + " - ");
  19. if (G.visited == true) {
  20. } else {
  21. G.visited = true;
  22. for (Node<T> n : G.children) {
  23. if (n.visited != true) {
  24. printTree(n);
  25. }
  26. }
  27. }
  28. }
  29.  
  30. private class NoComparator implements Comparator<Node<T>> {
  31.  
  32. @Override
  33. public int compare(Node<T> o1, Node<T> o2) {
  34. String h = "I need a String";
  35. Integer i = 0;
  36. if (o1.element.getClass() == h.getClass()) {
  37. return ((String) o1.element).compareTo((String) o2.element);
  38. } else if (o1.element.getClass() == i.getClass()) {
  39. return (Integer) o1.element - (Integer) o2.element;
  40. } else {
  41. return 0;
  42. }
  43. }
  44. }
  45. //return 0 is only good option
  46.  
  47. public int add(T parent, T child, int x, int y) {
  48.  
  49. //if the parent exists and the child is unique
  50. if (find(parent) && !find(child)) {
  51. Node<T> tempParent = get(parent);
  52. Node<T> tempChild = new Node<>(child, x, y);
  53. tempChild.children.add(tempParent);
  54. tempParent.children.add(tempChild);
  55. this.allNodes.add(tempChild);
  56. Collections.sort(tempChild.children, new NoComparator());
  57. Collections.sort(tempParent.children, new NoComparator());
  58. return 0;
  59. } else if (find(child)) {
  60. return 1;
  61. } else {
  62. return -1;
  63. }
  64. }
  65.  
  66. public boolean add(Node<T> n) {
  67. return add(n.element, n.x, n.y);
  68. }
  69.  
  70. public boolean add(T t, int x, int y) {
  71. if (root == null) {
  72. this.root = new Node<>(t, x, y);
  73. this.allNodes.add(this.root);
  74. return true;
  75. } else {
  76. Node<T> n = new Node<>(t, x, y);
  77. this.allNodes.add(n);
  78. n.children.add(this.root);
  79. this.root.children.add(n);
  80.  
  81. Collections.sort(this.root.children, new NoComparator());
  82. return false;
  83. }
  84. }
  85.  
  86. public boolean find(T v) {
  87. reset(this.root);
  88. return find(this.root, v);
  89. }
  90.  
  91. public Node<T> get(T t) {
  92. reset(this.root);
  93. return get(this.root, t);
  94. }
  95.  
  96. public boolean addRelationship(T parent, T child) {
  97. if (find(parent) && find(child)) {
  98. Node<T> tempChild = get(child);
  99. Node<T> tempParent = get(parent);
  100. boolean uniqueChild = true;
  101. boolean uniqueParent = true;
  102. for (Node<T> n : tempChild.children) {
  103. if (tempParent.element.equals(n.element)) {
  104. uniqueChild = false;
  105. }
  106. }
  107. for (Node<T> n : tempParent.children) {
  108. if (tempChild.element.equals(n.element)) {
  109. uniqueParent = false;
  110. }
  111. }
  112. if (uniqueChild && uniqueParent) {
  113. tempChild.children.add(tempParent);
  114. tempParent.children.add(tempChild);
  115. Collections.sort(tempChild.children, new NoComparator());
  116. Collections.sort(tempParent.children, new NoComparator());
  117. reset(this.root);
  118. return true;
  119. } else {
  120. return false;
  121. }
  122. }
  123. return false;
  124. }
  125.  
  126. private Node<T> get(Node<T> G, T t) {
  127.  
  128. if (G.element.equals(t)) {
  129. this.temp = G;
  130. } else {
  131. G.visited = true;
  132. for (Node<T> n : G.children) {
  133. if (n.visited != true) {
  134. get(n, t);
  135. }
  136. }
  137. }
  138. return this.temp;
  139. }
  140.  
  141. private void reset(Node<T> G) {
  142. this.temp = null;
  143. if (G.visited != true) {
  144. } else {
  145. G.visited = false;
  146. for (Node<T> n : G.children) {
  147. if (n.visited == true) {
  148. reset(n);
  149. }
  150. }
  151. }
  152. }
  153.  
  154. private boolean find(Node<T> G, T v) {
  155. if (this.root == G) {
  156. this.found = false;
  157. }
  158. if (G.element.equals(v)) {
  159. this.found = true;
  160. } else {
  161. G.visited = true;
  162. for (Node<T> n : G.children) {
  163. if (n.visited != true) {
  164. find(n, v);
  165. }
  166. }
  167. }
  168. return found;
  169. }
  170.  
  171. public void getPath(T o1, T o2) {
  172.  
  173. if (find(o1) && find(o2)) {
  174. Node<T> s = get(o1);
  175. Node<T> e = get(o2);
  176. reset(this.root);
  177. this.path = new Stack<Node<T>>();
  178. getPath(s, e);
  179. }
  180.  
  181.  
  182. }
  183.  
  184. public double distanceBetweenNodes(T o1, T o2) {
  185. return distanceBetweenNodes(get(o1), get(o2));
  186. }
  187.  
  188. private double distanceBetweenNodes(Node<T> o1, Node<T> o2) {
  189. return Math.sqrt(Math.pow((o2.x - o1.x), 2) + Math.pow(o2.y - o1.y, 2));
  190. }
  191.  
  192. public double pathLength() {
  193. Node<T> o1 = this.path.pop();
  194. Node<T> o2 = this.path.pop();
  195. return pathLength(o1, o2, 0);
  196. }
  197.  
  198. private double pathLength(Node<T> o1, Node<T> o2, double total) {
  199. Node<T> temp = null;
  200. if (o2 == null) {
  201. return total;
  202. } else {
  203. total += distanceBetweenNodes(o1, o2);
  204. if (this.path.size() >= 1) {
  205. temp = this.path.pop();
  206. }
  207. return pathLength(o2, temp, total);
  208. }
  209. }
  210.  
  211. private void getPath(Node<T> start, Node<T> end) {
  212. //TODO THIS DOES NOT WORK
  213. //I want it find the shortest path between 2 nodes
  214. if (!start.equals(end)) {
  215. start.visited = true;
  216. this.path.push(new Node<T>(start.element, start.x, start.y));
  217. for (Node<T> n : start.children) {
  218. if ((n.visited != true && n.children.size() > 1) || n.equals(end)) {
  219. getPath(n, end);
  220. }
  221. }
  222. } else {
  223. this.path.push(new Node<T>(end.element, end.x, end.y));
  224. }
  225. }
  226.  
  227. public List<Node<T>> getDirections(T o1, T o2) {
  228. Node<T> n1 = get(o1);
  229.  
  230. Node<T> n2 = get(o2);
  231.  
  232. return getDirections(n1, n2);
  233. }
  234. private Map<Node<T>, Boolean> vis = new HashMap<Node<T>, Boolean>();
  235. private Map<Node<T>, Node<T>> prev = new HashMap<Node<T>, Node<T>>();
  236.  
  237. public List getDirections(Node<T> start, Node<T> finish) {
  238. List<Node<T>> directions = new LinkedList<Node<T>>();
  239. Queue<Node<T>> q = new LinkedList<Node<T>>();
  240. Node<T> current = start;
  241. q.add(current);
  242. vis.put(current, true);
  243. while (!q.isEmpty()) {
  244. current = q.poll();
  245. if (current.equals(finish)) {
  246. break;
  247. } else {
  248. for (Node<T> node : current.children) {
  249. if (!vis.containsKey(node)) {
  250. q.add(node);
  251. vis.put(node, true);
  252. prev.put(node, current);
  253. }
  254. }
  255. }
  256. }
  257. if (!current.equals(finish)) {
  258. System.out.println("can't reach destination");
  259. }
  260. for (Node node = finish; node != null; node = prev.get(node)) {
  261. directions.add(node);
  262. }
  263. //Might need to reverse directions
  264. return reverseList(directions);
  265. }
  266. public List reverseList(List l){
  267. List r = new LinkedList<>();
  268. for(int x = l.size()-1;x>=0;x--){
  269. r.add(l.get(x));
  270. }
  271. return r;
  272. }
  273. }

Report this snippet  

You need to login to post a comment.