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