Advertisement
Guest User

Untitled

a guest
May 23rd, 2015
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.66 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. class Main {
  4. public static void main(String[] args) {
  5. Scanner sc = new Scanner(System.in);
  6. String talkme = null;
  7. String[] parts;
  8. Node aux;
  9. Tree splayt = new Tree();
  10.  
  11. while(!(talkme = sc.nextLine()).equals("")) {
  12. parts = talkme.split(" ");
  13. if(parts[0].compareTo("STATUS") == 0) {
  14. if((aux = splayt.findNode(parts[1], splayt.root)) != null) {
  15. System.out.println(aux.getMatricula() + " " + aux.getPass() + " " + aux.getStatus());
  16. } else {
  17. System.out.println(parts[1] + " NO RECORD");
  18. }
  19. } else if(parts[0].compareTo("PASS") == 0) {
  20. if((aux = splayt.findNode(parts[1], splayt.root)) == null) {
  21. splayt.insert(parts[1], parts[2], splayt.root);
  22. } else {
  23. aux.passedAgain();
  24. aux.setStatus(parts[2]);
  25. }
  26. } else if(parts[0].compareTo("UNFLAG") == 0) {
  27. if((aux = splayt.findNode(parts[1], splayt.root)) != null) {
  28. aux.setStatus("R");
  29. }
  30. }
  31. }
  32. /*System.out.println("Rotations: " + splayt.getRotations());*/
  33. /*System.out.println("Crossed: " + splayt.getCrossed());*/
  34. }
  35. }
  36.  
  37. class Node {
  38. public Node left;
  39. public Node right;
  40. public Node parent;
  41. public int pass;
  42. public String matricula;
  43. public String status;
  44.  
  45. public Node(String matricula, String status) {
  46. this.pass = 1;
  47. this.matricula = matricula;
  48. this.status = status;
  49. }
  50.  
  51. public String getMatricula() {
  52. return this.matricula;
  53. }
  54.  
  55. public String getStatus() {
  56. return this.status;
  57. }
  58.  
  59. public int getPass() {
  60. return this.pass;
  61. }
  62.  
  63. public void passedAgain() {
  64. this.pass++;
  65. }
  66.  
  67. public void setStatus(String status) {
  68. this.status = status;
  69. }
  70.  
  71. public void setParent(Node parent) {
  72. this.parent = parent;
  73. }
  74. }
  75.  
  76. class Tree {
  77. public Node root;
  78.  
  79. public Tree() {
  80. this.root = null;
  81. }
  82.  
  83. public void insert(String matricula, String status, Node root) {
  84. Node p = null;
  85. Node z = root;
  86.  
  87. while(z != null) {
  88. p = z;
  89. if(matricula.compareTo(p.matricula) > 0) {
  90. z = z.right;
  91. } else if(matricula.compareTo(p.matricula) < 0){
  92. z = z.left;
  93. }
  94. }
  95. z = new Node(matricula, status);
  96. z.setParent(p);
  97. if(p == null) {
  98. root = z;
  99. } else if(matricula.compareTo(p.matricula) > 0) {
  100. p.right = z;
  101. } else if(matricula.compareTo(p.matricula) < 0) {
  102. p.left = z;
  103. }
  104. Splay(z);
  105. }
  106.  
  107. public void Splay(Node x) {
  108. while(x.parent != null) {
  109. Node Parent = x.parent;
  110. Node grandParent = Parent.parent;
  111. if(grandParent == null) {
  112. if(x == Parent.left) { //nodes are one level below the root
  113. leftChildParent(x, Parent);
  114. } else {
  115. rightChildParent(x, Parent);
  116. }
  117. } else {
  118. if(x == Parent.left) {
  119. if(Parent == grandParent.left) { //preform zig zig operation
  120. leftChildParent(Parent, grandParent);
  121. leftChildParent(x, Parent);
  122. } else { //preform zigh zag operation
  123. leftChildParent(x, x.parent);
  124. rightChildParent(x, x.parent);
  125. }
  126. } else {
  127. if(Parent == grandParent.left) { //preform zig zag operation
  128. rightChildParent(x, x.parent);
  129. leftChildParent(x, x.parent);
  130. } else { //preform zag zag operation
  131. rightChildParent(Parent, grandParent);
  132. rightChildParent(x, Parent);
  133. }
  134. }
  135. }
  136. }
  137. root = x;
  138. }
  139.  
  140. public void leftChildParent(Node child, Node father) {
  141.  
  142. if(father.parent != null) { //in case there is no grandparent
  143. if(father == father.parent.left) {
  144. father.parent.left = child;
  145. } else {
  146. father.parent.right= child;
  147. }
  148. }
  149.  
  150. if(child.right != null) {
  151. child.right.parent = father;
  152. }
  153.  
  154. child.parent = father.parent;
  155. father.parent = child;
  156. father.left = child.right;
  157. child.right = father;
  158. }
  159.  
  160. public void rightChildParent(Node child, Node father) {
  161. if(father.parent != null) { //in case there is no grandparent
  162. if(father == father.parent.left) {
  163. father.parent.left = child;
  164. } else {
  165. father.parent.right = child;
  166. }
  167. }
  168.  
  169. child.parent = father.parent;
  170. father.parent = child;
  171. father.right = child.left;
  172. child.left = father;
  173. }
  174.  
  175. public Node findNode(String matricula, Node root) {
  176. while(root != null) {
  177. if(matricula.compareTo(root.matricula) < 0) {
  178. root = root.left;
  179. } else if(matricula.compareTo(root.matricula) > 0) {
  180. root = root.right;
  181. } else {
  182. Splay(root);
  183. return root;
  184. }
  185. }
  186. return null;
  187. }
  188.  
  189. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement