Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- class Main {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- String talkme = null;
- String[] parts;
- Node aux;
- Tree splayt = new Tree();
- while(!(talkme = sc.nextLine()).equals("")) {
- parts = talkme.split(" ");
- if(parts[0].compareTo("STATUS") == 0) {
- if((aux = splayt.findNode(parts[1], splayt.root)) != null) {
- System.out.println(aux.getMatricula() + " " + aux.getPass() + " " + aux.getStatus());
- } else {
- System.out.println(parts[1] + " NO RECORD");
- }
- } else if(parts[0].compareTo("PASS") == 0) {
- if((aux = splayt.findNode(parts[1], splayt.root)) == null) {
- splayt.insert(parts[1], parts[2], splayt.root);
- } else {
- aux.passedAgain();
- aux.setStatus(parts[2]);
- }
- } else if(parts[0].compareTo("UNFLAG") == 0) {
- if((aux = splayt.findNode(parts[1], splayt.root)) != null) {
- aux.setStatus("R");
- }
- }
- }
- /*System.out.println("Rotations: " + splayt.getRotations());*/
- /*System.out.println("Crossed: " + splayt.getCrossed());*/
- }
- }
- class Node {
- public Node left;
- public Node right;
- public Node parent;
- public int pass;
- public String matricula;
- public String status;
- public Node(String matricula, String status) {
- this.pass = 1;
- this.matricula = matricula;
- this.status = status;
- }
- public String getMatricula() {
- return this.matricula;
- }
- public String getStatus() {
- return this.status;
- }
- public int getPass() {
- return this.pass;
- }
- public void passedAgain() {
- this.pass++;
- }
- public void setStatus(String status) {
- this.status = status;
- }
- public void setParent(Node parent) {
- this.parent = parent;
- }
- }
- class Tree {
- public Node root;
- public Tree() {
- this.root = null;
- }
- public void insert(String matricula, String status, Node root) {
- Node p = null;
- Node z = root;
- while(z != null) {
- p = z;
- if(matricula.compareTo(p.matricula) > 0) {
- z = z.right;
- } else if(matricula.compareTo(p.matricula) < 0){
- z = z.left;
- }
- }
- z = new Node(matricula, status);
- z.setParent(p);
- if(p == null) {
- root = z;
- } else if(matricula.compareTo(p.matricula) > 0) {
- p.right = z;
- } else if(matricula.compareTo(p.matricula) < 0) {
- p.left = z;
- }
- Splay(z);
- }
- public void Splay(Node x) {
- while(x.parent != null) {
- Node Parent = x.parent;
- Node grandParent = Parent.parent;
- if(grandParent == null) {
- if(x == Parent.left) { //nodes are one level below the root
- leftChildParent(x, Parent);
- } else {
- rightChildParent(x, Parent);
- }
- } else {
- if(x == Parent.left) {
- if(Parent == grandParent.left) { //preform zig zig operation
- leftChildParent(Parent, grandParent);
- leftChildParent(x, Parent);
- } else { //preform zigh zag operation
- leftChildParent(x, x.parent);
- rightChildParent(x, x.parent);
- }
- } else {
- if(Parent == grandParent.left) { //preform zig zag operation
- rightChildParent(x, x.parent);
- leftChildParent(x, x.parent);
- } else { //preform zag zag operation
- rightChildParent(Parent, grandParent);
- rightChildParent(x, Parent);
- }
- }
- }
- }
- root = x;
- }
- public void leftChildParent(Node child, Node father) {
- if(father.parent != null) { //in case there is no grandparent
- if(father == father.parent.left) {
- father.parent.left = child;
- } else {
- father.parent.right= child;
- }
- }
- if(child.right != null) {
- child.right.parent = father;
- }
- child.parent = father.parent;
- father.parent = child;
- father.left = child.right;
- child.right = father;
- }
- public void rightChildParent(Node child, Node father) {
- if(father.parent != null) { //in case there is no grandparent
- if(father == father.parent.left) {
- father.parent.left = child;
- } else {
- father.parent.right = child;
- }
- }
- child.parent = father.parent;
- father.parent = child;
- father.right = child.left;
- child.left = father;
- }
- public Node findNode(String matricula, Node root) {
- while(root != null) {
- if(matricula.compareTo(root.matricula) < 0) {
- root = root.left;
- } else if(matricula.compareTo(root.matricula) > 0) {
- root = root.right;
- } else {
- Splay(root);
- return root;
- }
- }
- return null;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement