-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathPersistentTreeSet.java
297 lines (250 loc) · 11.8 KB
/
PersistentTreeSet.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
/*
Copyright (c) Rich Hickey. All rights reserved. The use and distribution terms for this software
are covered by the Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
which can be found in the file epl-v10.html at the root of this distribution. By using this
software in any fashion, you are agreeing to be bound by the terms of this license. You must not
remove this notice, or any other, from this software.
*/
/* rich Mar 3, 2008 */
package org.organicdesign.fp.collections;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Comparator;
import java.util.Map;
import java.util.SortedSet;
import org.organicdesign.fp.oneOf.Option;
import static org.organicdesign.fp.collections.Equator.defaultComparator;
/**
A wrapper that turns a PersistentTreeMap into a set.
This file is a derivative work based on a Clojure collection licensed under the Eclipse Public
License 1.0 Copyright Rich Hickey. Errors by Glen Peterson.
*/
public class PersistentTreeSet<E> extends AbstractUnmodSet<E>
implements ImSortedSet<E>, Serializable {
/**
Be extremely careful with this because it uses the default comparator, which only works for
items that implement Comparable (have a "natural ordering"). An attempt to use it with other
items will blow up at runtime. Either a withComparator() method will be added, or this will
be removed.
*/
// TODO: Should really require a comparator.
@SuppressWarnings("unchecked")
static public final PersistentTreeSet EMPTY = new PersistentTreeSet(PersistentTreeMap.EMPTY);
/**
Be extremely careful with this because it uses the default comparator, which only works for
items that implement Comparable (have a "natural ordering"). An attempt to use it with other
items will blow up at runtime. Either a withComparator() method will be added, or this will
be removed.
*/
@SuppressWarnings("unchecked")
static public <T extends Comparable<T>> PersistentTreeSet<T> empty() { return EMPTY; }
/**
Returns a new PersistentTreeSet of the given comparator. Always use this instead of starting
with empty() because there is no way to assign a comparator to an existing set.
*/
public static <T> PersistentTreeSet<T> ofComp(Comparator<? super T> comp) {
return new PersistentTreeSet<>(PersistentTreeMap.empty(comp));
}
/**
Returns a new PersistentTreeSet of the given comparator and items.
@param comp A comparator that defines the sort order of elements in the new set. This
becomes part of the set (it's not for pre-sorting).
@param elements items to go into the set. In the case of a duplicate element, later
values in the input list overwrite the earlier ones.
@return a new PersistentTreeSet of the specified comparator and the given elements
*/
public static <T> PersistentTreeSet<T> ofComp(Comparator<? super T> comp,
Iterable<T> elements) {
PersistentTreeSet<T> ret = new PersistentTreeSet<>(PersistentTreeMap.empty(comp));
if (elements == null) { return ret; }
for (T element : elements) {
ret = ret.put(element);
}
return ret;
}
/** Returns a new PersistentTreeSet of the given comparable items. */
public static <T extends Comparable<T>> PersistentTreeSet<T> of(Iterable<T> items) {
// empty() uses default comparator
if (items == null) { return empty(); }
PersistentTreeSet<T> ret = empty();
for (T item : items) {
ret = ret.put(item);
}
return ret;
}
/**
Returns a new PersistentTreeSet of the keys and comparator in the given map. Since
PersistentTreeSet is just a wrapper for a PersistentTreeMap, this can be a very cheap
operation.
*/
public static <T> PersistentTreeSet<T> ofMap(ImSortedMap<T,?> i) {
return new PersistentTreeSet<>(i);
}
// ==================================== Instance Variables ====================================
private transient final ImSortedMap<E,?> impl;
// ======================================= Constructor =======================================
private PersistentTreeSet(ImSortedMap<E,?> i) { impl = i; }
// ======================================= Serialization =======================================
// This class has a custom serialized form designed to be as small as possible. It does not
// have the same internal structure as an instance of this class.
// For serializable. Make sure to change whenever internal data format changes.
private static final long serialVersionUID = 20160904120000L;
// Check out Josh Bloch Item 78, p. 312 for an explanation of what's going on here.
private static class SerializationProxy<K> implements Serializable {
// For serializable. Make sure to change whenever internal data format changes.
private static final long serialVersionUID = 20160904120000L;
private Comparator<? super K> comparator;
private final int size;
private transient ImSortedMap<K,?> theMap;
SerializationProxy(ImSortedMap<K,?> phm) {
comparator = phm.comparator();
if ( (comparator != null) && !(comparator instanceof Serializable) ) {
throw new IllegalStateException("Comparator must implement serializable." +
" Instead it was " + comparator);
}
if (comparator instanceof PersistentTreeMap.KeyComparator) {
Comparator wc = ((PersistentTreeMap.KeyComparator) comparator).unwrap();
if ( !(wc instanceof Serializable) ) {
throw new IllegalStateException("Wrapped key comparator must implement" +
"serializable. Instead it was " + wc);
}
}
size = phm.size();
theMap = phm;
}
// Taken from Josh Bloch Item 75, p. 298
private void writeObject(ObjectOutputStream s) throws IOException {
s.defaultWriteObject();
// Write out all elements in the proper order
for (Map.Entry<K,?> entry : theMap) {
s.writeObject(entry.getKey());
}
}
@SuppressWarnings("unchecked")
private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
s.defaultReadObject();
if (comparator == null) {
comparator = defaultComparator();
}
theMap = PersistentTreeMap.ofComp(comparator, null);
for (int i = 0; i < size; i++) {
theMap = theMap.assoc((K) s.readObject(), null);
}
}
private Object readResolve() { return new PersistentTreeSet<>(theMap); }
}
private Object writeReplace() { return new SerializationProxy<>(impl); }
private void readObject(java.io.ObjectInputStream in) throws IOException,
ClassNotFoundException {
throw new InvalidObjectException("Proxy required");
}
// ===================================== Instance Methods =====================================
/**
Returns the comparator used to order the items in this set, or null if it uses
Fn2.DEFAULT_COMPARATOR (for compatibility with java.util.SortedSet).
*/
@Override public Comparator<? super E> comparator() { return impl.comparator(); }
/**
Returns true if the set contains the given item in O(log n) time. This is the defining method
of a set.
*/
@SuppressWarnings("SuspiciousMethodCalls")
@Override public boolean contains(Object o) { return impl.containsKey(o); }
/** {@inheritDoc} */
@Override public PersistentTreeSet<E> without(E key) {
return (impl.containsKey(key)) ? new PersistentTreeSet<>(impl.without(key))
: this;
}
/** {@inheritDoc} */
@Override
public UnmodSortedIterator<E> iterator() {
return new UnmodSortedIterator<E>() {
UnmodSortedIterator<? extends UnmodMap.UnEntry<E,?>> iter = impl.iterator();
@Override public boolean hasNext() { return iter.hasNext(); }
@Override public E next() {
UnmodMap.UnEntry<E,?> e = iter.next();
return e == null ? null : e.getKey();
}
};
}
/**
This is designed to be correct, rather than fully compatible with TreeSet.equals().
TreeSet.equals() does not take ordering into account and this does.
You want better equality? Define an Equator. This is for Java@trade; interop.
*/
@Override public boolean equals(Object other) {
if (this == other) { return true; }
if ( !(other instanceof SortedSet) ) { return false; }
SortedSet<?> that = (SortedSet) other;
if (size() != that.size()) { return false; }
return UnmodSortedIterable.equal(this, UnmodSortedIterable.castFromSortedSet(that));
}
/**
Use head() inherited from Sequence instead of this method which is inherited from SortedSet.
This method returns the first element if it exists, or throws a NoSuchElementException if the
set is empty.
head() returns an Option of the first element where as this method throws an exception if this
set is empty. I had to rename the method on Sequence from first() to head() to work around
this. Also returning an Option is thread-safe for building a lazy sequence. The alternative,
examining the rest() of a sequence to see if it's == Sequence.empty() gets ugly very quickly
and makes many transformations eager (especially flatMap).
*/
@Override public E first() { return impl.firstKey(); }
/** {@inheritDoc} */
@Override public Option<E> head() {
return size() > 0 ? Option.some(impl.firstKey()) : Option.none();
}
/** {@inheritDoc} */
@Override public boolean isEmpty() { return impl.isEmpty(); }
/**
Inherited from SortedSet, returns the last item in this set, or throw an exception if this set
is empty. Good luck with that.
*/
@Override public E last() { return impl.lastKey(); }
/** {@inheritDoc} */
@Override public PersistentTreeSet<E> put(E e) {
return (impl.containsKey(e)) ? this
: new PersistentTreeSet<>(impl.assoc(e, null));
}
/** The size of this set. */
@Override public int size() { return impl.size(); }
/** {@inheritDoc} */
@Override public ImSortedSet<E> subSet(E fromElement, E toElement) {
return PersistentTreeSet.ofMap(impl.subMap(fromElement, toElement));
}
/** {@inheritDoc} */
@Override public ImSortedSet<E> tailSet(E fromElement) {
return PersistentTreeSet.ofMap(impl.tailMap(fromElement));
}
// /** {@inheritDoc} */
// @Override public Sequence<E> tail() { return impl.without(first()).keySet().seq(); }
// @Override
// public ISeq<E> rseq() {
// return APersistentMap.KeySeq.create(((Reversible<E>) impl).rseq());
// }
//
// @Override
// public Comparator comparator() {
// return ((Sorted) impl).comparator();
// }
// @Override
// public Object entryKey(E entry) {
// return entry;
// }
// @SuppressWarnings("unchecked")
// @Override
// public ISeq<E> seq(boolean ascending) {
// PersistentTreeMap m = (PersistentTreeMap) impl;
// return RT.keys(m.seq(ascending));
// }
//
// @SuppressWarnings("unchecked")
// @Override
// public ISeq<E> seqFrom(Object key, boolean ascending) {
// PersistentTreeMap m = (PersistentTreeMap) impl;
// return RT.keys(m.seqFrom(key, ascending));
// }
}