Mercurial > hg > Database > jungle-sharp

comparison Main/jungle-main/data/treemap/TreeMap.cs @ 20:1f99e150f336

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix folder and add Object Mapper.
author Kazuma Takeda
date Thu, 15 Dec 2016 22:52:48 +0900
parents
children 9588ad364fdd
comparison
equal deleted inserted replaced
19:0865819106cf 20:1f99e150f336
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
79 public class iterators<K> : IEnumerator<K> {
80 Stack<TreeMapNode<K,V>> nodeStack = new Stack<TreeMapNode<K,V>>();
81 TreeMapNode<K,V> currentNode = new TreeMap<K,V>().getRoot();
82 public List<K> appLines { get; set; }
83 private int position;
84
85
86 public bool MoveNext() {
87 return currentNode != null;
88 }
89
90
91 public K Current{
92 get {
93 K key = currentNode.getKey ();
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() {
121 ((IEnumerator<K>)this.appLines).Dispose ();
122 }
123
124 public void Reset() {
125 ((IEnumerator<K>)this.appLines).Reset();
126 }
127
128 }
129 }
130 }
131