|
0
|
1 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
|
|
|
2
|
|
|
3
|
|
1
|
4 import java.util.Iterator;
|
|
|
5 import java.util.Optional;
|
|
|
6
|
|
|
7 import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
|
|
|
8
|
|
0
|
9 /**
|
|
|
10 * Created by e115731 on 15/03/23.
|
|
|
11 */
|
|
|
12 public class TreeMap<K, V> {
|
|
1
|
13 Node<K, V> root;
|
|
0
|
14 int size;
|
|
|
15
|
|
|
16 public TreeMap() {
|
|
4
|
17 this.root = new EmptyNode();
|
|
0
|
18 this.size = 0;
|
|
|
19 }
|
|
|
20
|
|
1
|
21
|
|
|
22 public Node getRoot() {
|
|
|
23 return root;
|
|
|
24 }
|
|
|
25
|
|
|
26 public TreeMap(Node<K, V> root, int size) {
|
|
0
|
27 this.root = root;
|
|
|
28 this.size = size;
|
|
|
29 }
|
|
|
30
|
|
1
|
31 public Optional<V> get(K key) {
|
|
5
|
32 return root.get(key);
|
|
2
|
33 }
|
|
0
|
34
|
|
|
35 public TreeMap put(K key, V value) {
|
|
|
36
|
|
|
37 if (key == null || value == null) // null check
|
|
|
38 throw new NullPointerException();
|
|
|
39
|
|
|
40 if (isEmpty()) {
|
|
1
|
41 Node<K, V> newRoot = new BlackNode(key, value, new EmptyNode(), new EmptyNode());
|
|
|
42 return new TreeMap<K, V>(newRoot, size++);
|
|
0
|
43 }
|
|
|
44
|
|
5
|
45 Node<K, V> newEntry = root.put(key, value);
|
|
1
|
46 Node<K, V> newRoot = new BlackNode(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right());
|
|
|
47 return new TreeMap(newRoot, 0);
|
|
0
|
48 }
|
|
|
49
|
|
|
50
|
|
|
51 public boolean isEmpty() {
|
|
|
52 return root == null;
|
|
|
53 }
|
|
|
54
|
|
9
|
55
|
|
5
|
56 public TreeMap<K,V> delete(K key) {
|
|
|
57 Node node = root.delete(key,null);
|
|
6
|
58
|
|
|
59 if (node == null)
|
|
|
60 return this; // not key
|
|
|
61
|
|
7
|
62 if (!node.exitNode())
|
|
|
63 return new TreeMap(new EmptyNode<>(),0);
|
|
5
|
64 Node newRoot = new BlackNode(node.getKey(),node.getValue(),node.left(),node.right());
|
|
|
65 return new TreeMap(newRoot,0);
|
|
|
66 }
|
|
1
|
67
|
|
7
|
68 public void checkBlackCount(){
|
|
|
69 root.checkBlackCount(0);
|
|
8
|
70 System.out.println("-----------------------------------");
|
|
7
|
71 }
|
|
0
|
72 }
|
