1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.bidimap;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.io.Serializable;
23 import java.util.ArrayList;
24 import java.util.Comparator;
25 import java.util.Iterator;
26 import java.util.ListIterator;
27 import java.util.Map;
28 import java.util.SortedMap;
29 import java.util.TreeMap;
30
31 import org.apache.commons.collections4.BidiMap;
32 import org.apache.commons.collections4.OrderedBidiMap;
33 import org.apache.commons.collections4.OrderedMap;
34 import org.apache.commons.collections4.OrderedMapIterator;
35 import org.apache.commons.collections4.ResettableIterator;
36 import org.apache.commons.collections4.SortedBidiMap;
37 import org.apache.commons.collections4.map.AbstractSortedMapDecorator;
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 public class DualTreeBidiMap<K, V> extends AbstractDualBidiMap<K, V>
60 implements SortedBidiMap<K, V>, Serializable {
61
62
63
64
65
66
67
68 protected static class BidiOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> {
69
70
71 private final AbstractDualBidiMap<K, V> parent;
72
73
74 private ListIterator<Map.Entry<K, V>> iterator;
75
76
77 private Map.Entry<K, V> last;
78
79
80
81
82
83 protected BidiOrderedMapIterator(final AbstractDualBidiMap<K, V> parent) {
84 this.parent = parent;
85 iterator = new ArrayList<>(parent.entrySet()).listIterator();
86 }
87
88 @Override
89 public K getKey() {
90 if (last == null) {
91 throw new IllegalStateException(
92 "Iterator getKey() can only be called after next() and before remove()");
93 }
94 return last.getKey();
95 }
96
97 @Override
98 public V getValue() {
99 if (last == null) {
100 throw new IllegalStateException(
101 "Iterator getValue() can only be called after next() and before remove()");
102 }
103 return last.getValue();
104 }
105
106 @Override
107 public boolean hasNext() {
108 return iterator.hasNext();
109 }
110
111 @Override
112 public boolean hasPrevious() {
113 return iterator.hasPrevious();
114 }
115
116 @Override
117 public K next() {
118 last = iterator.next();
119 return last.getKey();
120 }
121
122 @Override
123 public K previous() {
124 last = iterator.previous();
125 return last.getKey();
126 }
127
128 @Override
129 public void remove() {
130 iterator.remove();
131 parent.remove(last.getKey());
132 last = null;
133 }
134
135 @Override
136 public void reset() {
137 iterator = new ArrayList<>(parent.entrySet()).listIterator();
138 last = null;
139 }
140
141 @Override
142 public V setValue(final V value) {
143 if (last == null) {
144 throw new IllegalStateException(
145 "Iterator setValue() can only be called after next() and before remove()");
146 }
147 if (parent.reverseMap.containsKey(value) &&
148 parent.reverseMap.get(value) != last.getKey()) {
149 throw new IllegalArgumentException(
150 "Cannot use setValue() when the object being set is already in the map");
151 }
152 final V oldValue = parent.put(last.getKey(), value);
153
154
155 last.setValue(value);
156 return oldValue;
157 }
158
159 @Override
160 public String toString() {
161 if (last != null) {
162 return "MapIterator[" + getKey() + "=" + getValue() + "]";
163 }
164 return "MapIterator[]";
165 }
166 }
167
168
169
170
171
172
173
174 protected static class ViewMap<K, V> extends AbstractSortedMapDecorator<K, V> {
175
176
177
178
179
180 protected ViewMap(final DualTreeBidiMap<K, V> bidi, final SortedMap<K, V> sm) {
181
182
183
184 super(new DualTreeBidiMap<>(sm, bidi.reverseMap, bidi.inverseBidiMap));
185 }
186
187 @Override
188 public void clear() {
189
190 for (final Iterator<K> it = keySet().iterator(); it.hasNext();) {
191 it.next();
192 it.remove();
193 }
194 }
195
196 @Override
197 public boolean containsValue(final Object value) {
198
199 return decorated().normalMap.containsValue(value);
200 }
201
202 @Override
203 protected DualTreeBidiMap<K, V> decorated() {
204 return (DualTreeBidiMap<K, V>) super.decorated();
205 }
206
207 @Override
208 public SortedMap<K, V> headMap(final K toKey) {
209 return new ViewMap<>(decorated(), super.headMap(toKey));
210 }
211
212 @Override
213 public K nextKey(final K key) {
214 return decorated().nextKey(key);
215 }
216
217 @Override
218 public K previousKey(final K key) {
219 return decorated().previousKey(key);
220 }
221
222 @Override
223 public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
224 return new ViewMap<>(decorated(), super.subMap(fromKey, toKey));
225 }
226
227 @Override
228 public SortedMap<K, V> tailMap(final K fromKey) {
229 return new ViewMap<>(decorated(), super.tailMap(fromKey));
230 }
231 }
232
233
234 private static final long serialVersionUID = 721969328361809L;
235
236
237 private final Comparator<? super K> comparator;
238
239
240 private final Comparator<? super V> valueComparator;
241
242
243
244
245 public DualTreeBidiMap() {
246 super(new TreeMap<>(), new TreeMap<>());
247 this.comparator = null;
248 this.valueComparator = null;
249 }
250
251
252
253
254
255
256
257 public DualTreeBidiMap(final Comparator<? super K> keyComparator, final Comparator<? super V> valueComparator) {
258 super(new TreeMap<>(keyComparator), new TreeMap<>(valueComparator));
259 this.comparator = keyComparator;
260 this.valueComparator = valueComparator;
261 }
262
263
264
265
266
267
268
269 public DualTreeBidiMap(final Map<? extends K, ? extends V> map) {
270 super(new TreeMap<>(), new TreeMap<>());
271 putAll(map);
272 this.comparator = null;
273 this.valueComparator = null;
274 }
275
276
277
278
279
280
281
282
283 protected DualTreeBidiMap(final Map<K, V> normalMap, final Map<V, K> reverseMap,
284 final BidiMap<V, K> inverseBidiMap) {
285 super(normalMap, reverseMap, inverseBidiMap);
286 this.comparator = ((SortedMap<K, V>) normalMap).comparator();
287 this.valueComparator = ((SortedMap<V, K>) reverseMap).comparator();
288 }
289
290 @Override
291 public Comparator<? super K> comparator() {
292 return ((SortedMap<K, V>) normalMap).comparator();
293 }
294
295
296
297
298
299
300
301
302
303 @Override
304 protected DualTreeBidiMap<V, K> createBidiMap(final Map<V, K> normalMap, final Map<K, V> reverseMap,
305 final BidiMap<K, V> inverseMap) {
306 return new DualTreeBidiMap<>(normalMap, reverseMap, inverseMap);
307 }
308
309 @Override
310 public K firstKey() {
311 return ((SortedMap<K, V>) normalMap).firstKey();
312 }
313
314 @Override
315 public SortedMap<K, V> headMap(final K toKey) {
316 final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).headMap(toKey);
317 return new ViewMap<>(this, sub);
318 }
319
320 @Override
321 public SortedBidiMap<V, K> inverseBidiMap() {
322 return (SortedBidiMap<V, K>) super.inverseBidiMap();
323 }
324
325 public OrderedBidiMap<V, K> inverseOrderedBidiMap() {
326 return inverseBidiMap();
327 }
328
329 public SortedBidiMap<V, K> inverseSortedBidiMap() {
330 return inverseBidiMap();
331 }
332
333 @Override
334 public K lastKey() {
335 return ((SortedMap<K, V>) normalMap).lastKey();
336 }
337
338
339
340
341
342
343
344
345
346 @Override
347 public OrderedMapIterator<K, V> mapIterator() {
348 return new BidiOrderedMapIterator<>(this);
349 }
350
351 @Override
352 public K nextKey(final K key) {
353 if (isEmpty()) {
354 return null;
355 }
356 if (normalMap instanceof OrderedMap) {
357 return ((OrderedMap<K, ?>) normalMap).nextKey(key);
358 }
359 final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
360 final Iterator<K> it = sm.tailMap(key).keySet().iterator();
361 it.next();
362 if (it.hasNext()) {
363 return it.next();
364 }
365 return null;
366 }
367
368 @Override
369 public K previousKey(final K key) {
370 if (isEmpty()) {
371 return null;
372 }
373 if (normalMap instanceof OrderedMap) {
374 return ((OrderedMap<K, V>) normalMap).previousKey(key);
375 }
376 final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
377 final SortedMap<K, V> hm = sm.headMap(key);
378 if (hm.isEmpty()) {
379 return null;
380 }
381 return hm.lastKey();
382 }
383
384 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
385 in.defaultReadObject();
386 normalMap = new TreeMap<>(comparator);
387 reverseMap = new TreeMap<>(valueComparator);
388 @SuppressWarnings("unchecked")
389 final Map<K, V> map = (Map<K, V>) in.readObject();
390 putAll(map);
391 }
392
393 @Override
394 public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
395 final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).subMap(fromKey, toKey);
396 return new ViewMap<>(this, sub);
397 }
398
399 @Override
400 public SortedMap<K, V> tailMap(final K fromKey) {
401 final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).tailMap(fromKey);
402 return new ViewMap<>(this, sub);
403 }
404
405 @Override
406 public Comparator<? super V> valueComparator() {
407 return ((SortedMap<V, K>) reverseMap).comparator();
408 }
409
410
411 private void writeObject(final ObjectOutputStream out) throws IOException {
412 out.defaultWriteObject();
413 out.writeObject(normalMap);
414 }
415
416 }