Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * To change this license header, choose License Headers in Project Properties.
- * To change this template file, choose Tools | Templates
- * and open the template in the editor.
- */
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- import java.util.Iterator;
- import java.util.List;
- import java.util.StringTokenizer;
- /**
- * NPM :1406649132 Nama : Fahmi Azizi
- *
- * @author user
- */
- public class SDA1415T2 {
- public static void main(String[] args) throws IOException {
- AnaryTree anary = new AnaryTree();
- BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
- int maxInput = Integer.parseInt(input.readLine());
- for (int i = 0; i < maxInput; i++) {
- String line = input.readLine();
- StringTokenizer tokenizer = new StringTokenizer(line);
- if (tokenizer.hasMoreElements()) {
- if (line.toUpperCase().contains("TAMBAH")) {
- tokenizer.nextElement();
- String name = (String) tokenizer.nextElement();
- String phone = (String) tokenizer.nextElement();
- String regionalName = (String) tokenizer.nextElement();
- Node node = new Node(new Regional(name, phone), null);
- anary.insert(node, regionalName);
- } else if (line.toUpperCase().contains("HAPUS")) {
- tokenizer.nextElement();
- String regionalName = (String) tokenizer.nextElement();
- anary.remove(regionalName);
- } else if (line.toUpperCase().contains("TELEPON")) {
- tokenizer.nextElement();
- String regionalCaller = (String) tokenizer.nextElement();
- String regionalReceiver = (String) tokenizer.nextElement();
- if (regionalCaller.equals(regionalReceiver)) {
- } else {
- anary.call(regionalCaller, regionalReceiver);
- }
- }
- }
- }
- }
- }
- class Regional {
- String name;
- String phone;
- public Regional(String name, String phone) {
- this.name = name;
- this.phone = phone;
- }
- public String getName() {
- return name;
- }
- public void setName(String name) {
- this.name = name;
- }
- public String getPhone() {
- return phone;
- }
- public void setPhone(String phone) {
- this.phone = phone;
- }
- }
- class Node<T> {
- private T element;
- private Node parent;
- private List<Node> listNode;
- private int level;
- public Node(T element, Node parent) {
- this.element = element;
- this.parent = parent;
- listNode = new ArrayList<>();
- }
- public Node(T element, Node parent, int level) {
- this.element = element;
- this.parent = parent;
- listNode = new ArrayList<>();
- this.level = level;
- }
- public T getElement() {
- return element;
- }
- public void setElement(T element) {
- this.element = element;
- }
- public Node getParent() {
- return parent;
- }
- public void setParent(Node parent) {
- this.parent = parent;
- }
- public List<Node> getListNode() {
- return listNode;
- }
- public int getLevel() {
- return level;
- }
- public void setLevel(int level) {
- this.level = level;
- }
- }
- class AnaryTree<T> {
- Node<T> root;
- public AnaryTree() {
- this.root = null;
- }
- void insert(Node node, String regionalName) {
- if (root == null) {
- node.setLevel(0);
- node.setParent(null);
- root = node;
- System.out.println("Kantor " + ((Regional) node.getElement()).getName() + " Berhasil dimasukkan");
- } else {
- if (((Regional) root.getElement()).getName().equals(regionalName)) {
- node.setLevel(root.getLevel() + 1);
- node.setParent(root);
- root.getListNode().add(node);
- System.out.println("Kantor " + ((Regional) node.getElement()).getName() + " Berhasil dimasukkan");
- } else {
- Node n = find(root, regionalName);
- if (n == null) {
- System.out.println("Kantor " + regionalName + " Tidak ditemukan");
- } else {
- node.setLevel(n.getLevel() + 1);
- node.setParent(n);
- n.getListNode().add(node);
- System.out.println("Kantor " + ((Regional) node.getElement()).getName() + " Berhasil dimasukkan");
- }
- }
- }
- }
- Node find(Node node, String regionalName) {
- Node result = null;
- Iterator iterator = node.getListNode().iterator();
- while (iterator.hasNext()) {
- Node n = (Node) iterator.next();
- if (((Regional) n.getElement()).getName().equals(regionalName)) {
- result = n;
- if (result != null) {
- return result;
- }
- }
- if (n.getListNode().size() > 0) {
- result = find(n, regionalName);
- if (result != null) {
- return result;
- }
- }
- }
- return result;
- }
- public void display(Node node) {
- Iterator iterator = node.getListNode().iterator();
- while (iterator.hasNext()) {
- Node n = (Node) iterator.next();
- if (n.getListNode().size() > 0) {
- display(n);
- }
- System.out.println(((Regional) n.getElement()).getName() + " - " + n.getLevel() + " - " + ((Regional) n.getParent().getElement()).getName());
- }
- }
- void remove(String regionalName) {
- Node node = find(root, regionalName);
- if (node == null) {
- System.out.println("Kantor " + regionalName + " Tidak ditemukan");
- return;
- } else {
- Node parent = node.getParent();
- if (parent != null) {
- if (node.getListNode().size() == 0) {
- parent.getListNode().remove(node);
- System.out.println("Hapus " + regionalName + " : Kantor " + regionalName + " Berhasil dihapus ");
- } else {
- List<Node> oldList = new ArrayList<>();
- oldList.addAll(node.getListNode());
- parent.getListNode().remove(node);
- System.out.println("Hapus " + regionalName + " : Kantor " + regionalName + " Berhasil dihapus ");
- Iterator iterator = oldList.iterator();
- while (iterator.hasNext()) {
- Node n = (Node) iterator.next();
- n.setLevel(n.getLevel() - 1);
- n.setParent(parent);
- System.out.println("Hapus " + regionalName + " : Kantor " + ((Regional) n.getElement()).getName() + " dipindahkan ");
- }
- parent.getListNode().addAll(oldList);
- }
- }
- }
- }
- void call(String regionalCaller, String regionalReceiver) {
- Node caller, receiver;
- String rootRegional = ((Regional) root.getElement()).getName();
- List<Node> path1;
- List<Node> path2;
- if (rootRegional.equals(regionalCaller)) {
- caller = root;
- receiver = find(root, regionalReceiver);
- if (receiver != null) {
- path2 = generatePath(receiver);
- if (path2.size() == 1) {
- String phone = ((Regional) path2.get(0).getElement()).getPhone();
- System.out.println("Telepon " + regionalCaller + " " + regionalReceiver + " : Nomor Telepon " + regionalReceiver + " adalah " + phone);
- } else {
- for (int i = path2.size() - 2; i >= 0; i--) {
- String phone = ((Regional) path2.get(i).getElement()).getPhone();
- if (i > 0) {
- String phoneDown = ((Regional) path2.get(i - 1).getElement()).getPhone();
- System.out.println("Telepon " + regionalCaller + " " + regionalReceiver + " : Telepon " + phone + " dapat " + phoneDown);
- } else {
- System.out.println("Telepon " + regionalCaller + " " + regionalReceiver + " : Nomor Telepon " + regionalReceiver + " adalah " + phone);
- }
- }
- }
- } else {
- System.out.println("Kantor " + regionalReceiver + " Tidak ditemukan ");
- }
- } else if (rootRegional.equals(regionalReceiver)) {
- receiver = root;
- caller = find(root, regionalCaller);
- if (caller != null) {
- path1 = generatePath(caller);
- for (int i = 0; i < path1.size(); i++) {
- String phone = ((Regional) path1.get(i).getElement()).getPhone();
- if (path1.size() == 1) {
- System.out.println("Telepon " + regionalCaller + " " + regionalReceiver + " : Nomor Telepon " + regionalReceiver + " adalah " + phone);
- break;
- }
- if (i < path1.size() - 1) {
- String phoneParent = ((Regional) path1.get(i).getParent().getElement()).getPhone();
- System.out.println("Telepon " + regionalCaller + " " + regionalReceiver + " : Telepon " + phone + " dapat " + phoneParent);
- } else {
- System.out.println("Telepon " + regionalCaller + " " + regionalReceiver + " : Nomor Telepon " + regionalReceiver + " adalah " + phone);
- }
- }
- } else {
- System.out.println("Kantor " + regionalCaller + " Tidak ditemukan ");
- }
- } else {
- caller = find(root, regionalCaller);
- receiver = find(root, regionalReceiver);
- if (receiver == null) {
- System.out.println("Kantor " + regionalCaller + " Tidak ditemukan ");
- }
- if (caller == null) {
- System.out.println("Kantor " + regionalReceiver + " Tidak ditemukan ");
- }
- if (caller != null && receiver != null) {
- path1 = generatePath(caller);
- path2 = generatePath(receiver);
- int index = getIndexForSamePath(path1, path2);
- }
- }
- }
- int getIndexForSamePath(List<Node> path1, List<Node> path2) {
- int result = 0;
- if (path1.size() > path2.size()) {
- for (int i = path2.size()-1; i >=0 ; i++) {
- String regional1 = ((Regional) path1.get(i).getElement()).getName();
- String regional2 = ((Regional) path2.get(i).getElement()).getName();
- if (!regional1.equals(regional2)) {
- result = i + 1;
- break;
- }
- }
- } else {
- for (int i = path1.size()-1; i >=0; i++) {
- String regional1 = ((Regional) path1.get(i).getElement()).getName();
- String regional2 = ((Regional) path2.get(i).getElement()).getName();
- if (!regional1.equals(regional2)) {
- result = i + 1;
- break;
- }
- }
- }
- System.out.println(result);
- return result;
- }
- List<Node> generatePath(Node node) {
- List<Node> result = new ArrayList<>();
- System.out.println("Pathnya " + ((Regional) node.getElement()).getName() + " :");
- while (node.getParent() != null) {
- result.add(node.getParent());
- node = node.getParent();
- System.out.print(((Regional) node.getElement()).getName() + " - ");
- }
- System.out.println("");
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement