|
0
|
1 using UnityEngine;
|
|
|
2 using System.Collections;
|
|
|
3 using System.Collections.Generic;
|
|
|
4 using System;
|
|
|
5
|
|
|
6 public class TreeMap<K, V> {
|
|
|
7 TreeMapNode<K, V> root;
|
|
1
|
8 Comparer<K> comparator;
|
|
0
|
9
|
|
|
10
|
|
|
11 public TreeMap(IComparer icompere) {
|
|
|
12 this.root = new EmptyNode<K, V> ();
|
|
|
13 }
|
|
|
14
|
|
|
15 public TreeMap() {
|
|
|
16 this.root = new EmptyNode<K, V> ();
|
|
1
|
17 this.comparator = Comparer<K>.Default;
|
|
0
|
18 }
|
|
|
19
|
|
|
20 public TreeMap(TreeMapNode<K, V> root) {
|
|
|
21 this.root = root;
|
|
|
22 }
|
|
|
23
|
|
1
|
24 public TreeMap(TreeMapNode<K, V> root, Comparer<K> comparator) {
|
|
0
|
25 this.root = root;
|
|
|
26 this.comparator = comparator;
|
|
|
27 }
|
|
|
28
|
|
|
29 public TreeMapNode<K, V> getRoot() {
|
|
|
30 return root;
|
|
|
31 }
|
|
|
32
|
|
|
33 public V get(K key) {
|
|
|
34 return root.get(key, this.comparator);
|
|
|
35 }
|
|
|
36
|
|
|
37 public TreeMap<K, V> put(K key, V value) {
|
|
|
38 if(isEmpty()) {
|
|
|
39 TreeMapNode<K, V> newRoot = new BlackNode<K, V> (key, value, new EmptyNode<K, V> (), new EmptyNode<K, V> ());
|
|
|
40 return new TreeMap<K, V> (newRoot, this.comparator);
|
|
|
41 }
|
|
|
42
|
|
|
43 TreeMapNode<K, V> newEntry = root.put (key, value, this.comparator);
|
|
|
44 TreeMapNode<K, V> newRoots = new BlackNode<K, V> (newEntry.getKey (), newEntry.getValue (), newEntry.lefts (), newEntry.rights ());
|
|
|
45 return new TreeMap<K, V> (newRoots, this.comparator);
|
|
|
46 }
|
|
|
47
|
|
|
48 public bool isEmpty() {
|
|
|
49 return !root.isNotEmpty ();
|
|
|
50 }
|
|
|
51
|
|
|
52 public TreeMap<K, V> delete(K key) {
|
|
7
|
53 if (key.Equals(default(K))) {
|
|
0
|
54 return this;
|
|
|
55 }
|
|
1
|
56 rebuildNode<K, V> rootRebuildNode = root.delete (key, null, this.comparator, Rotate.N);
|
|
0
|
57 if (!rootRebuildNode.notEmpty ()) {
|
|
|
58 return this;
|
|
|
59 }
|
|
|
60 TreeMapNode<K, V> roots = rootRebuildNode.getNode ();
|
|
|
61 if (!root.isNotEmpty ()) {
|
|
|
62 return new TreeMap<K, V> (new EmptyNode<K, V> (), this.comparator);
|
|
|
63 }
|
|
|
64 TreeMapNode<K, V> newRoot = new BlackNode<K, V> (roots.getKey (), roots.getValue (), roots.lefts (), roots.rights ());
|
|
|
65 return new TreeMap<K, V> (newRoot, this.comparator);
|
|
|
66 }
|
|
|
67 // like to iterator and IEmurator.
|
|
|
68 public IEnumerator<K> keys() {
|
|
|
69 return new iterators<K> ();
|
|
|
70 }
|
|
|
71
|
|
|
72
|
|
|
73 public void checkDepth() {
|
|
|
74 root.checkDepth (0, 0);
|
|
|
75 Debug.Log ("-----------------------------------");
|
|
|
76 }
|
|
|
77
|
|
|
78 public class iterators<K> : IEnumerator<K> {
|
|
|
79 Stack<TreeMapNode<K,V>> nodeStack = new Stack<TreeMapNode<K,V>>();
|
|
|
80 TreeMapNode<K,V> currentNode = new TreeMap<K,V>().getRoot();
|
|
|
81 public List<K> appLines { get; set; }
|
|
|
82 private int position;
|
|
|
83
|
|
|
84
|
|
|
85 public bool MoveNext() {
|
|
|
86 return currentNode != null;
|
|
|
87 }
|
|
|
88
|
|
|
89
|
|
|
90 public K Current{
|
|
|
91 get {
|
|
|
92 K key = currentNode.getKey ();
|
|
|
93 if (currentNode.lefts ().isNotEmpty ()) {
|
|
|
94 nodeStack.Push (currentNode);
|
|
|
95 currentNode = currentNode.lefts ();
|
|
|
96 return key;
|
|
|
97 } else if (currentNode.rights ().isNotEmpty ()) {
|
|
|
98 currentNode = currentNode.rights ();
|
|
|
99 return key;
|
|
|
100 } else if (nodeStack.Count == 0) {
|
|
|
101 currentNode = null;
|
|
|
102 return key;
|
|
|
103 }
|
|
|
104 do {
|
|
|
105 currentNode = nodeStack.Pop ().rights ();
|
|
|
106 if (currentNode.isNotEmpty ()) {
|
|
|
107 return key;
|
|
|
108 }
|
|
|
109 }while (nodeStack.Count != 0);
|
|
|
110 return key;
|
|
|
111 }
|
|
|
112 }
|
|
|
113
|
|
|
114 object IEnumerator.Current
|
|
|
115 {
|
|
4
|
116 get { return appLines; }
|
|
0
|
117 }
|
|
|
118
|
|
|
119 public void Dispose() {
|
|
|
120 ((IEnumerator<K>)this.appLines).Dispose ();
|
|
|
121 }
|
|
|
122
|
|
|
123 public void Reset() {
|
|
|
124 ((IEnumerator<K>)this.appLines).Reset();
|
|
|
125 }
|
|
|
126
|
|
|
127 }
|
|
|
128 }
|
|
|
129
|
|
|
130
|
