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