|
0
|
1 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
|
|
|
2
|
|
|
3
|
|
20
|
4 import org.junit.Test;
|
|
|
5
|
|
24
|
6 import java.util.Iterator;
|
|
1
|
7 import java.util.Optional;
|
|
24
|
8 import java.util.Stack;
|
|
1
|
9
|
|
|
10
|
|
0
|
11 /**
|
|
|
12 * Created by e115731 on 15/03/23.
|
|
|
13 */
|
|
|
14 public class TreeMap<K, V> {
|
|
16
|
15 final Node<K, V> root;
|
|
|
16 final int size;
|
|
0
|
17
|
|
|
18 public TreeMap() {
|
|
4
|
19 this.root = new EmptyNode();
|
|
0
|
20 this.size = 0;
|
|
|
21 }
|
|
|
22
|
|
1
|
23
|
|
|
24 public Node getRoot() {
|
|
|
25 return root;
|
|
|
26 }
|
|
|
27
|
|
|
28 public TreeMap(Node<K, V> root, int size) {
|
|
0
|
29 this.root = root;
|
|
|
30 this.size = size;
|
|
|
31 }
|
|
|
32
|
|
24
|
33 public Optional<V> get(final K key) {
|
|
|
34 return root.get(key);
|
|
|
35 }
|
|
0
|
36
|
|
|
37 public TreeMap put(K key, V value) {
|
|
|
38
|
|
|
39 if (key == null || value == null) // null check
|
|
|
40 throw new NullPointerException();
|
|
|
41
|
|
|
42 if (isEmpty()) {
|
|
1
|
43 Node<K, V> newRoot = new BlackNode(key, value, new EmptyNode(), new EmptyNode());
|
|
16
|
44 return new TreeMap<K, V>(newRoot, size + 1);
|
|
0
|
45 }
|
|
|
46
|
|
24
|
47 Node<K, V> newEntry = root.put((Comparable<? super K>) key, value);
|
|
1
|
48 Node<K, V> newRoot = new BlackNode(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right());
|
|
|
49 return new TreeMap(newRoot, 0);
|
|
0
|
50 }
|
|
|
51
|
|
|
52
|
|
|
53 public boolean isEmpty() {
|
|
16
|
54 return !root.isNotEmpty();
|
|
0
|
55 }
|
|
|
56
|
|
9
|
57
|
|
24
|
58 public TreeMap<K, V> delete(K key) {
|
|
|
59 Node node = null;
|
|
|
60 try {
|
|
|
61 node = root.delete((Comparable<? super K>) key, null, Rotate.N);
|
|
|
62 } catch (RotateParent rotateParent) {
|
|
|
63 }
|
|
6
|
64 if (node == null)
|
|
|
65 return this; // not key
|
|
13
|
66 if (!node.isNotEmpty())
|
|
24
|
67 return new TreeMap(new EmptyNode<>(), 0);
|
|
|
68 Node newRoot = new BlackNode(node.getKey(), node.getValue(), node.left(), node.right());
|
|
|
69 return new TreeMap(newRoot, 0);
|
|
|
70 }
|
|
|
71
|
|
|
72 public Iterator<K> keys() {
|
|
|
73 return new Iterator<K>() {
|
|
|
74 Stack<Node> nodeStack = new Stack();
|
|
|
75 Node currentNode = root;
|
|
|
76
|
|
|
77 @Override
|
|
|
78 public boolean hasNext() {
|
|
|
79 return currentNode != null;
|
|
|
80 }
|
|
|
81
|
|
|
82 @Override
|
|
|
83 public K next() {
|
|
|
84 K key = (K) currentNode.getKey();
|
|
|
85
|
|
|
86 if (currentNode.left().isNotEmpty()) {
|
|
|
87 nodeStack.push(currentNode);
|
|
|
88 currentNode = currentNode.left();
|
|
|
89 return key;
|
|
|
90 } else if (currentNode.right().isNotEmpty()) {
|
|
|
91 currentNode = currentNode.right();
|
|
|
92 return key;
|
|
|
93 } else if (nodeStack.isEmpty()) {
|
|
|
94 currentNode = null;
|
|
|
95 return key;
|
|
|
96 }
|
|
|
97
|
|
|
98 do {
|
|
|
99 currentNode = nodeStack.pop().right();
|
|
|
100 if (currentNode.isNotEmpty())
|
|
|
101 return key;
|
|
|
102
|
|
|
103 } while (!nodeStack.isEmpty());
|
|
|
104 return key;
|
|
|
105 }
|
|
|
106 };
|
|
5
|
107 }
|
|
1
|
108
|
|
20
|
109 @Test
|
|
24
|
110 public void checkDepth() {
|
|
|
111 root.checkDepth(0, 0);
|
|
8
|
112 System.out.println("-----------------------------------");
|
|
7
|
113 }
|
|
0
|
114 }
|
