|
0
|
1 package fj.data;
|
|
|
2
|
|
1
|
3 import fj.*;
|
|
0
|
4
|
|
|
5 import java.util.Iterator;
|
|
|
6 import java.util.Map;
|
|
|
7
|
|
|
8 import static fj.Function.compose;
|
|
|
9 import static fj.Function.flip;
|
|
|
10 import static fj.P.p;
|
|
|
11 import static fj.data.IterableW.join;
|
|
|
12 import static fj.data.List.iterableList;
|
|
|
13
|
|
|
14 /**
|
|
|
15 * An immutable, in-memory map, backed by a red-black tree.
|
|
|
16 */
|
|
|
17 public final class TreeMap<K, V> implements Iterable<P2<K, V>> {
|
|
1
|
18 private final Set<P2<K, V>> tree;
|
|
0
|
19
|
|
1
|
20 private TreeMap(final Set<P2<K, V>> tree) {
|
|
|
21 this.tree = tree;
|
|
|
22 }
|
|
0
|
23
|
|
1
|
24 private static <K, V> Ord<P2<K, V>> ord(final Ord<K> keyOrd) {
|
|
|
25 return keyOrd.comap(P2.<K, V>__1());
|
|
|
26 }
|
|
0
|
27
|
|
1
|
28 /**
|
|
|
29 * Constructs an empty tree map.
|
|
|
30 *
|
|
|
31 * @param keyOrd An order for the keys of the tree map.
|
|
|
32 * @return an empty TreeMap with the given key order.
|
|
|
33 */
|
|
|
34 public static <K, V> TreeMap<K, V> empty(final Ord<K> keyOrd) {
|
|
|
35 return new TreeMap<K, V>(Set.empty(TreeMap.<K, V>ord(keyOrd)));
|
|
|
36 }
|
|
0
|
37
|
|
1
|
38 /**
|
|
|
39 * Returns a potential value that the given key maps to.
|
|
|
40 *
|
|
|
41 * @param k The key to look up in the tree map.
|
|
|
42 * @return A potential value for the given key.
|
|
|
43 */
|
|
2
|
44 public Option<V> get(final K k) {
|
|
1
|
45 // Option<V> op = Option.<V> none();
|
|
|
46 // Option<P2<K, Option<V>>> attribute = tree.mapGet(P.p(k, op));
|
|
|
47 // return attribute.bind(P2.<K, Option<V>> __2());
|
|
|
48 // // P3<Set<P2<K, Option<V>>>, Option<P2<K, Option<V>>>, Set<P2<K,
|
|
|
49 // // Option<V>>>> splitTree = tree.split(P.p(k, op));
|
|
|
50 // // final Option<P2<K, Option<V>>> x = splitTree._2();
|
|
|
51 // //
|
|
|
52 // // System.out.println("aaaa");
|
|
|
53 // // return x.bind(P2.<K, Option<V>>__2());
|
|
4
|
54 return Option.<V>some(getLoop(k));
|
|
2
|
55 }
|
|
|
56
|
|
4
|
57 public V getLoop(final K k) {
|
|
1
|
58 Set<P2<K, V>> cur = tree;
|
|
2
|
59 // Option<V> op = Option.<V>none();
|
|
1
|
60 while (!cur.isEmpty()) {
|
|
2
|
61 // Ord<P2<K, V>> ttt = cur.ord();
|
|
|
62
|
|
|
63 P2<K, V> head = cur.head();
|
|
|
64 K h = head._1();
|
|
|
65 final int i = h.hashCode() - k.hashCode();
|
|
|
66 // Ord<P2<K, V>> ord = cur.ord();
|
|
|
67 // Ordering i = ord.compare(P.p(k,null), cur.head());
|
|
1
|
68 if (i > 0)
|
|
|
69 cur = cur.l();
|
|
|
70 else if (i < 0)
|
|
|
71 cur = cur.r();
|
|
|
72 else
|
|
4
|
73 return head._2();
|
|
1
|
74
|
|
|
75
|
|
|
76 }
|
|
4
|
77 return null;
|
|
2
|
78 // return Option.<V>none();
|
|
0
|
79 }
|
|
|
80
|
|
1
|
81 /**
|
|
|
82 * Inserts the given key and value association into the tree map. If the given
|
|
|
83 * key is already mapped to a value, the old value is replaced with the given
|
|
|
84 * one.
|
|
|
85 *
|
|
|
86 * @param k The key to insert.
|
|
|
87 * @param v The value to insert.
|
|
|
88 * @return A new tree map with the given value mapped to the given key.
|
|
|
89 */
|
|
|
90 public TreeMap<K, V> set(final K k, final V v) {
|
|
|
91 return new TreeMap<K, V>(tree.insert(P.p(k, v)));
|
|
|
92 }
|
|
0
|
93
|
|
1
|
94 /**
|
|
|
95 * Deletes the entry in the tree map that corresponds to the given key.
|
|
|
96 *
|
|
|
97 * @param k The key to delete from this tree map.
|
|
|
98 * @return A new tree map with the entry corresponding to the given key
|
|
|
99 * removed.
|
|
|
100 */
|
|
|
101 public TreeMap<K, V> delete(final K k) {
|
|
|
102 Option<V> op = Option.<V>none();
|
|
|
103 P2<K, V> p = P.p(k, null);
|
|
|
104 return new TreeMap<K, V>(tree.delete(p));
|
|
|
105 }
|
|
0
|
106
|
|
1
|
107 /**
|
|
|
108 * Returns the number of entries in this tree map.
|
|
|
109 *
|
|
|
110 * @return The number of entries in this tree map.
|
|
|
111 */
|
|
|
112 public int size() {
|
|
|
113 return tree.size();
|
|
|
114 }
|
|
0
|
115
|
|
1
|
116 /**
|
|
|
117 * Determines if this tree map has any entries.
|
|
|
118 *
|
|
|
119 * @return <code>true</code> if this tree map has no entries,
|
|
|
120 * <code>false</code> otherwise.
|
|
|
121 */
|
|
|
122 public boolean isEmpty() {
|
|
|
123 return tree.isEmpty();
|
|
|
124 }
|
|
0
|
125
|
|
1
|
126 /**
|
|
|
127 * Returns all values in this tree map.
|
|
|
128 *
|
|
|
129 * @return All values in this tree map.
|
|
|
130 */
|
|
|
131 // public List<V> values() {
|
|
|
132 // return iterableList(join(tree.toList().map(compose(IterableW.<V, Option<V>> wrap(), P2.<K, Option<V>> __2()))));
|
|
|
133 // }
|
|
|
134
|
|
|
135 /**
|
|
|
136 * Returns all keys in this tree map.
|
|
|
137 *
|
|
|
138 * @return All keys in this tree map.
|
|
|
139 */
|
|
|
140 public List<K> keys() {
|
|
|
141 return tree.toList().map(P2.<K, V>__1());
|
|
|
142 }
|
|
0
|
143
|
|
1
|
144 /**
|
|
|
145 * Determines if the given key value exists in this tree map.
|
|
|
146 *
|
|
|
147 * @param k
|
|
|
148 * The key value to look for in this tree map.
|
|
|
149 * @return <code>true</code> if this tree map contains the given key,
|
|
|
150 * <code>false</code> otherwise.
|
|
|
151 */
|
|
|
152 // public boolean contains(final K k) {
|
|
|
153 // return tree.member(P.p(k, Option.<V> none()));
|
|
|
154 // }
|
|
0
|
155
|
|
1
|
156 /**
|
|
|
157 * Returns an iterator for this map's key-value pairs. This method exists to
|
|
|
158 * permit the use in a <code>for</code>-each loop.
|
|
|
159 *
|
|
|
160 * @return A iterator for this map's key-value pairs.
|
|
|
161 */
|
|
|
162 public Iterator<P2<K, V>> iterator() {
|
|
3
|
163 return tree.iterator();
|
|
1
|
164 // join(
|
|
|
165 // tree.toStream().map(P2.<K, Option<V>, IterableW<V>> map2_(IterableW.<V, Option<V>> wrap()))
|
|
|
166 // .map(P2.tuple(compose(IterableW.<V, P2<K, V>> map(), P.<K, V> p2())))).iterator();
|
|
0
|
167 }
|
|
|
168
|
|
1
|
169 /**
|
|
|
170 * A mutable map projection of this tree map.
|
|
|
171 *
|
|
|
172 * @return A new mutable map isomorphic to this tree map.
|
|
|
173 */
|
|
|
174 public Map<K, V> toMutableMap() {
|
|
|
175 final Map<K, V> m = new java.util.TreeMap<K, V>();
|
|
|
176 for (final P2<K, V> e : this) {
|
|
|
177 m.put(e._1(), e._2());
|
|
|
178 }
|
|
|
179 return m;
|
|
0
|
180 }
|
|
|
181
|
|
1
|
182 /**
|
|
|
183 * An immutable projection of the given mutable map.
|
|
|
184 *
|
|
|
185 * @param ord An order for the map's keys.
|
|
|
186 * @param m A mutable map to project to an immutable one.
|
|
|
187 * @return A new immutable tree map isomorphic to the given mutable map.
|
|
|
188 */
|
|
|
189 public static <K, V> TreeMap<K, V> fromMutableMap(final Ord<K> ord, final Map<K, V> m) {
|
|
|
190 TreeMap<K, V> t = empty(ord);
|
|
|
191 for (final Map.Entry<K, V> e : m.entrySet()) {
|
|
|
192 t = t.set(e.getKey(), e.getValue());
|
|
|
193 }
|
|
|
194 return t;
|
|
|
195 }
|
|
|
196
|
|
|
197 /**
|
|
|
198 * Returns a first-class version of the get method for this TreeMap.
|
|
|
199 *
|
|
|
200 * @return a functional representation of this TreeMap.
|
|
|
201 */
|
|
|
202 public F<K, Option<V>> get() {
|
|
|
203 return new F<K, Option<V>>() {
|
|
|
204 public Option<V> f(final K k) {
|
|
4
|
205 return get(k);
|
|
1
|
206 }
|
|
|
207 };
|
|
|
208 }
|
|
0
|
209
|
|
1
|
210 /**
|
|
|
211 * Modifies the value for the given key, if present, by applying the given
|
|
|
212 * function to it.
|
|
|
213 *
|
|
2
|
214 * @param k The key for the value to modify.
|
|
|
215 * @param f A function with which to modify the value.
|
|
1
|
216 * @return A new tree map with the value for the given key transformed by the
|
|
2
|
217 * given function, paired with True if the map was modified, otherwise
|
|
|
218 * False.
|
|
1
|
219 */
|
|
2
|
220 public P2<Boolean, TreeMap<K, V>> update(final K k, final F<V, V> f) {
|
|
|
221 return null;
|
|
1
|
222 // final P2<Boolean, Set<P2<K, Option<V>>>> up = tree.update(p(k, Option.<V> none()),
|
|
|
223 // P2.<K, Option<V>, Option<V>> map2_(Option.<V, V> map().f(f)));
|
|
|
224 // return P.p(up._1(), new TreeMap<K, V>(up._2()));
|
|
2
|
225 }
|
|
0
|
226
|
|
1
|
227 /**
|
|
|
228 * Modifies the value for the given key, if present, by applying the given
|
|
|
229 * function to it, or inserts the given value if the key is not present.
|
|
|
230 *
|
|
|
231 * @param k
|
|
|
232 * The key for the value to modify.
|
|
|
233 * @param f
|
|
|
234 * A function with which to modify the value.
|
|
|
235 * @param v
|
|
|
236 * A value to associate with the given key if the key is not already
|
|
|
237 * present.
|
|
|
238 * @return A new tree map with the value for the given key transformed by the
|
|
|
239 * given function.
|
|
|
240 */
|
|
|
241 // public TreeMap<K, V> update(final K k, final F<V, V> f, final V v) {
|
|
|
242 // final P2<Boolean, TreeMap<K, V>> up = update(k, f);
|
|
|
243 // return up._1() ? up._2() : set(k, v);
|
|
|
244 // }
|
|
0
|
245
|
|
1
|
246 /**
|
|
|
247 * Splits this TreeMap at the given key. Returns a triple of:
|
|
|
248 * <ul>
|
|
|
249 * <li>A set containing all the values of this map associated with keys less
|
|
|
250 * than the given key.</li>
|
|
|
251 * <li>An option of a value mapped to the given key, if it exists in this map,
|
|
|
252 * otherwise None.
|
|
|
253 * <li>A set containing all the values of this map associated with keys
|
|
|
254 * greater than the given key.</li>
|
|
|
255 * </ul>
|
|
|
256 *
|
|
|
257 * @param k
|
|
|
258 * A key at which to split this map.
|
|
|
259 * @return Two sets and an optional value, where all elements in the first set
|
|
|
260 * are mapped to keys less than the given key in this map, all the
|
|
|
261 * elements in the second set are mapped to keys greater than the
|
|
|
262 * given key, and the optional value is the value associated with the
|
|
|
263 * given key if present, otherwise None.
|
|
|
264 */
|
|
|
265 // public P3<Set<V>, Option<V>, Set<V>> split(final K k) {
|
|
|
266 // final F<Set<P2<K, Option<V>>>, Set<V>> getSome = F1Functions.mapSet(
|
|
|
267 // F1Functions.o(Option.<V> fromSome(), P2.<K, Option<V>> __2()),
|
|
|
268 // tree.ord().comap(F1Functions.o(P.<K, Option<V>> p2().f(k), Option.<V> some_())));
|
|
|
269 // return tree.split(p(k, Option.<V> none())).map1(getSome).map3(getSome)
|
|
|
270 // .map2(F1Functions.o(Option.<V> join(), F1Functions.mapOption(P2.<K, Option<V>> __2())));
|
|
|
271 // }
|
|
0
|
272
|
|
1
|
273 /**
|
|
|
274 * Maps the given function across the values of this TreeMap.
|
|
|
275 *
|
|
|
276 * @param f
|
|
|
277 * A function to apply to the values of this TreeMap.
|
|
|
278 * @return A new TreeMap with the values transformed by the given function.
|
|
|
279 */
|
|
|
280 // @SuppressWarnings({ "unchecked" })
|
|
|
281 // public <W> TreeMap<K, W> map(final F<V, W> f) {
|
|
|
282 // final F<P2<K, Option<V>>, P2<K, Option<W>>> g = P2.map2_(F1Functions.mapOption(f));
|
|
|
283 // final F<K, P2<K, Option<V>>> coord = flip(P.<K, Option<V>> p2()).f(Option.<V> none());
|
|
|
284 // final Ord<K> o = tree.ord().comap(coord);
|
|
|
285 // return new TreeMap<K, W>(tree.map(TreeMap.<K, Option<W>> ord(o), g));
|
|
|
286 // }
|
|
0
|
287
|
|
|
288 }
|
