1 | |
|
2 | |
|
3 | |
|
4 | |
|
5 | |
|
6 | |
package jaggregate; |
7 | |
|
8 | |
import java.io.Serializable; |
9 | |
import java.util.Comparator; |
10 | |
|
11 | |
import static jaggregate.Objects.*; |
12 | |
import static jaggregate.OrderedCollection.*; |
13 | |
import static jaggregate.internal.ArgumentChecks.*; |
14 | |
import jaggregate.internal.ReadOnlySequences; |
15 | |
import static jaggregate.internal.ReadOnlySequences.*; |
16 | |
import jaggregate.internal.SequenceIndexOutOfBoundsException; |
17 | |
|
18 | |
|
19 | |
|
20 | |
|
21 | |
|
22 | |
|
23 | |
|
24 | |
|
25 | |
|
26 | |
|
27 | |
|
28 | |
|
29 | |
|
30 | 44 | public class SortedCollection<E> extends AbstractExtensibleCollection<E> |
31 | |
implements ContractibleSequence<E>, ReadOnlySequence<E>, Serializable { |
32 | |
|
33 | |
private static final long serialVersionUID = -1L; |
34 | |
|
35 | |
private final OrderedCollection<E> storage; |
36 | |
private final Comparator<? super E> comparator; |
37 | |
|
38 | |
|
39 | |
|
40 | |
|
41 | |
|
42 | |
|
43 | |
|
44 | |
|
45 | 834 | public SortedCollection( Comparator<? super E> comparator ) { |
46 | 834 | ensureNotNull( comparator, "comparator" ); |
47 | |
|
48 | 830 | this.comparator = comparator; |
49 | 830 | storage = emptyOrderedCollection(); |
50 | 830 | } |
51 | |
|
52 | |
|
53 | |
|
54 | |
|
55 | |
|
56 | |
|
57 | |
|
58 | |
|
59 | |
|
60 | |
|
61 | |
public SortedCollection( Comparator<? super E> comparator, |
62 | |
Collection<? extends E> newElements ) { |
63 | |
|
64 | 52 | this( comparator ); |
65 | 51 | addAll( newElements ); |
66 | 49 | } |
67 | |
|
68 | |
|
69 | |
|
70 | |
|
71 | |
|
72 | |
|
73 | |
|
74 | |
|
75 | |
|
76 | |
|
77 | |
public SortedCollection( Comparator<? super E> comparator, E... newElements ) { |
78 | 206 | this( comparator ); |
79 | 205 | addAll( newElements ); |
80 | 203 | } |
81 | |
|
82 | |
|
83 | |
|
84 | |
|
85 | |
|
86 | |
|
87 | |
|
88 | |
|
89 | |
|
90 | |
|
91 | |
public SortedCollection( Comparator<? super E> comparator, |
92 | |
Iterable<? extends E> newElements ) { |
93 | |
|
94 | 5 | this( comparator ); |
95 | 4 | addAll( newElements ); |
96 | 2 | } |
97 | |
|
98 | |
|
99 | |
|
100 | |
|
101 | |
|
102 | |
|
103 | |
|
104 | |
|
105 | |
|
106 | |
|
107 | |
public static <T> SortedCollection<T> emptySortedCollection( |
108 | |
Comparator<? super T> comparator ) { |
109 | |
|
110 | 59 | return new SortedCollection<T>( comparator ); |
111 | |
} |
112 | |
|
113 | |
|
114 | |
|
115 | |
|
116 | |
|
117 | |
|
118 | |
|
119 | |
|
120 | |
|
121 | |
|
122 | |
|
123 | |
|
124 | |
public static <T> SortedCollection<T> sortedCollectionFrom( |
125 | |
Comparator<? super T> comparator, Collection<? extends T> newElements ) { |
126 | |
|
127 | 18 | return new SortedCollection<T>( comparator, newElements ); |
128 | |
} |
129 | |
|
130 | |
|
131 | |
|
132 | |
|
133 | |
|
134 | |
|
135 | |
|
136 | |
|
137 | |
|
138 | |
|
139 | |
|
140 | |
|
141 | |
public static <T> SortedCollection<T> sortedCollectionWith( |
142 | |
Comparator<? super T> comparator, T... newElements ) { |
143 | |
|
144 | 1 | return new SortedCollection<T>( comparator, newElements ); |
145 | |
} |
146 | |
|
147 | |
|
148 | |
|
149 | |
|
150 | |
|
151 | |
|
152 | |
|
153 | |
|
154 | |
|
155 | |
|
156 | |
|
157 | |
|
158 | |
public static <T> SortedCollection<T> sortedCollectionFrom( |
159 | |
Comparator<? super T> comparator, Iterable<? extends T> newElements ) { |
160 | |
|
161 | 3 | return new SortedCollection<T>( comparator, newElements ); |
162 | |
} |
163 | |
|
164 | |
|
165 | |
|
166 | |
|
167 | |
|
168 | |
|
169 | |
@Override |
170 | |
public SortedCollection<E> toSortedCollection() { |
171 | 1 | return this; |
172 | |
} |
173 | |
|
174 | |
|
175 | |
|
176 | |
|
177 | |
|
178 | |
|
179 | |
@Override |
180 | |
public <R> OrderedCollection<R> collect( |
181 | |
UnaryFunctor<? super E, ? extends R> transformer ) { |
182 | |
|
183 | 6 | return (OrderedCollection<R>) super.collect( transformer ); |
184 | |
} |
185 | |
|
186 | |
|
187 | |
|
188 | |
|
189 | |
public void forEachDo( UnaryFunctor<? super E, ?> operation ) { |
190 | 283 | storage.forEachDo( operation ); |
191 | 246 | } |
192 | |
|
193 | |
|
194 | |
|
195 | |
|
196 | |
|
197 | |
|
198 | |
@Override |
199 | |
public SortedCollection<E> reject( UnaryCondition<? super E> discriminator ) { |
200 | 10 | return (SortedCollection<E>) super.reject( discriminator ); |
201 | |
} |
202 | |
|
203 | |
|
204 | |
|
205 | |
|
206 | |
|
207 | |
|
208 | |
@Override |
209 | |
public SortedCollection<E> select( UnaryCondition<? super E> discriminator ) { |
210 | 10 | return (SortedCollection<E>) super.select( discriminator ); |
211 | |
} |
212 | |
|
213 | |
|
214 | |
|
215 | |
|
216 | |
public int size() { |
217 | 3375 | return storage.size(); |
218 | |
} |
219 | |
|
220 | |
|
221 | |
|
222 | |
|
223 | |
|
224 | |
|
225 | |
|
226 | |
|
227 | |
|
228 | |
|
229 | |
|
230 | |
public SortedCollection<E> concat( ReadOnlySequence<? extends E> otherSequence ) { |
231 | 5 | SortedCollection<E> concatenation = sortedCollectionFrom( comparator(), this ); |
232 | 5 | concatenation.addAll( otherSequence ); |
233 | |
|
234 | 5 | return concatenation; |
235 | |
} |
236 | |
|
237 | |
|
238 | |
|
239 | |
|
240 | |
public E after( E target ) { |
241 | 16 | return storage.after( target ); |
242 | |
} |
243 | |
|
244 | |
|
245 | |
|
246 | |
|
247 | |
public E at( int index ) { |
248 | 5238 | return storage.at( index ); |
249 | |
} |
250 | |
|
251 | |
|
252 | |
|
253 | |
|
254 | |
public E before( E target ) { |
255 | 16 | return storage.before( target ); |
256 | |
} |
257 | |
|
258 | |
|
259 | |
|
260 | |
|
261 | |
public SortedCollection<E> copyRange( int start, int stop ) { |
262 | 52 | if ( start > stop ) |
263 | 12 | return new SortedCollection<E>( comparator() ); |
264 | |
|
265 | 40 | if ( stop > start ) { |
266 | 24 | if ( start < 0 || start >= size() ) |
267 | 3 | throw new SequenceIndexOutOfBoundsException( STARTING_INDEX, start ); |
268 | |
|
269 | 21 | if ( stop < 0 || stop >= size() ) |
270 | 3 | throw new SequenceIndexOutOfBoundsException( ENDING_INDEX, stop ); |
271 | |
} |
272 | |
|
273 | 34 | final SortedCollection<E> subsequence = new SortedCollection<E>( comparator() ); |
274 | 34 | storage.forEachInRangeDo( start, stop, new UnaryFunctor<E, Void>() { |
275 | 98 | public Void evaluate( E argument ) { |
276 | 64 | subsequence.add( argument ); |
277 | 64 | return null; |
278 | |
} |
279 | |
} ); |
280 | |
|
281 | 34 | return subsequence; |
282 | |
} |
283 | |
|
284 | |
|
285 | |
|
286 | |
|
287 | |
public SortedCollection<E> copyWith( E newElement ) { |
288 | 8 | SortedCollection<E> copy = sortedCollectionFrom( comparator(), this ); |
289 | 8 | copy.add( newElement ); |
290 | |
|
291 | 8 | return copy; |
292 | |
} |
293 | |
|
294 | |
|
295 | |
|
296 | |
|
297 | |
public SortedCollection<E> copyWithout( final E oldElement ) { |
298 | 25 | final SortedCollection<E> copy = new SortedCollection<E>( comparator() ); |
299 | |
|
300 | 25 | storage.forEachDo( new UnaryFunctor<E, Void>() { |
301 | 97 | public Void evaluate( E argument ) { |
302 | 72 | if ( !areEqual( oldElement, argument ) ) |
303 | 54 | copy.add( argument ); |
304 | 72 | return null; |
305 | |
} |
306 | |
} ); |
307 | |
|
308 | 25 | return copy; |
309 | |
} |
310 | |
|
311 | |
|
312 | |
|
313 | |
|
314 | |
public int findFirst( UnaryCondition<? super E> discriminator ) { |
315 | 7 | return storage.findFirst( discriminator ); |
316 | |
} |
317 | |
|
318 | |
|
319 | |
|
320 | |
|
321 | |
public int findLast( UnaryCondition<? super E> discriminator ) { |
322 | 7 | return storage.findLast( discriminator ); |
323 | |
} |
324 | |
|
325 | |
|
326 | |
|
327 | |
|
328 | |
public void forEachInReverseDo( UnaryFunctor<? super E, ?> operation ) { |
329 | 3 | storage.forEachInReverseDo( operation ); |
330 | 3 | } |
331 | |
|
332 | |
|
333 | |
|
334 | |
|
335 | |
public E first() { |
336 | 12 | return storage.first(); |
337 | |
} |
338 | |
|
339 | |
|
340 | |
|
341 | |
|
342 | |
public void forEachInRangeDo( int start, int stop, |
343 | |
UnaryFunctor<? super E, ?> operation ) { |
344 | |
|
345 | 49 | storage.forEachInRangeDo( start, stop, operation ); |
346 | 43 | } |
347 | |
|
348 | |
|
349 | |
|
350 | |
|
351 | |
public void forEachInRangeDoWithIndex( int start, int stop, |
352 | |
BinaryFunctor<? super Integer, ? super E, ?> operation ) { |
353 | |
|
354 | 49 | storage.forEachInRangeDoWithIndex( start, stop, operation ); |
355 | 43 | } |
356 | |
|
357 | |
|
358 | |
|
359 | |
|
360 | |
public int indexOf( E target ) { |
361 | 19 | return storage.indexOf( target ); |
362 | |
} |
363 | |
|
364 | |
|
365 | |
|
366 | |
|
367 | |
public int indexOf( ReadOnlySequence<? extends E> targetSequence, int start ) { |
368 | 22 | return storage.indexOf( targetSequence, start ); |
369 | |
} |
370 | |
|
371 | |
|
372 | |
|
373 | |
|
374 | |
public void doWithIndex( BinaryFunctor<? super Integer, ? super E, ?> operation ) { |
375 | 249 | storage.doWithIndex( operation ); |
376 | 248 | } |
377 | |
|
378 | |
|
379 | |
|
380 | |
|
381 | |
public E last() { |
382 | 7 | return storage.last(); |
383 | |
} |
384 | |
|
385 | |
|
386 | |
|
387 | |
|
388 | |
public ReadOnlySequence<E> reverse() { |
389 | 7 | return storage.reverse(); |
390 | |
} |
391 | |
|
392 | |
|
393 | |
|
394 | |
|
395 | |
public <T> void doWithOthers( ReadOnlySequence<? extends T> otherSequence, |
396 | |
BinaryFunctor<? super E, ? super T, ?> operation ) { |
397 | |
|
398 | 7 | storage.doWithOthers( otherSequence, operation ); |
399 | 7 | } |
400 | |
|
401 | |
|
402 | |
|
403 | |
|
404 | |
public void add( E newElement ) { |
405 | 2469 | storage.addBeforeIndex( newElement, indexBeforeWhichToInsert( newElement ) ); |
406 | 2469 | } |
407 | |
|
408 | |
|
409 | |
|
410 | |
|
411 | |
public boolean remove( E oldElement ) { |
412 | 28 | return storage.remove( oldElement ); |
413 | |
} |
414 | |
|
415 | |
|
416 | |
|
417 | |
|
418 | |
public E removeAt( int index ) { |
419 | 10 | return storage.removeAt( index ); |
420 | |
} |
421 | |
|
422 | |
|
423 | |
|
424 | |
|
425 | |
public E removeFirst() { |
426 | 3 | return storage.removeFirst(); |
427 | |
} |
428 | |
|
429 | |
|
430 | |
|
431 | |
|
432 | |
public E removeLast() { |
433 | 3 | return storage.removeLast(); |
434 | |
} |
435 | |
|
436 | |
|
437 | |
|
438 | |
|
439 | |
@Override |
440 | |
public boolean removeIf( UnaryCondition<? super E> discriminator ) { |
441 | 11 | return storage.removeIf( discriminator ); |
442 | |
} |
443 | |
|
444 | |
|
445 | |
|
446 | |
|
447 | |
@Override |
448 | |
public boolean retainIf( UnaryCondition<? super E> discriminator ) { |
449 | 2 | return storage.retainIf( discriminator ); |
450 | |
} |
451 | |
|
452 | |
|
453 | |
|
454 | |
|
455 | |
|
456 | |
|
457 | |
public Comparator<? super E> comparator() { |
458 | 3900 | return comparator; |
459 | |
} |
460 | |
|
461 | |
|
462 | |
|
463 | |
|
464 | |
@Override |
465 | |
public boolean equals( Object that ) { |
466 | 449 | return areSequencesEqual( this, that ); |
467 | |
} |
468 | |
|
469 | |
|
470 | |
|
471 | |
|
472 | |
@Override |
473 | |
public int hashCode() { |
474 | 90 | return ReadOnlySequences.hashCode( this ); |
475 | |
} |
476 | |
|
477 | |
|
478 | |
|
479 | |
|
480 | |
@Override |
481 | |
public String toString() { |
482 | 5 | return ReadOnlySequences.toString( this ); |
483 | |
} |
484 | |
|
485 | |
|
486 | |
|
487 | |
|
488 | |
@Override |
489 | |
protected <T> Set<T> newEmptySet() { |
490 | 9 | return Set.emptySet(); |
491 | |
} |
492 | |
|
493 | |
|
494 | |
|
495 | |
|
496 | |
@Override |
497 | |
protected SortedCollection<E> newEmptyExtensibleCollection() { |
498 | 20 | return new SortedCollection<E>( comparator() ); |
499 | |
} |
500 | |
|
501 | |
|
502 | |
|
503 | |
|
504 | |
@Override |
505 | |
protected <R> OrderedCollection<R> newEmptyExtensibleResultCollection() { |
506 | 6 | return emptyOrderedCollection(); |
507 | |
} |
508 | |
|
509 | |
private int indexBeforeWhichToInsert( E newElement ) { |
510 | 2469 | int lowerBound = 0; |
511 | 2469 | int upperBound = size(); |
512 | |
|
513 | 6086 | while ( lowerBound < upperBound ) { |
514 | 3796 | int medianIndex = ( upperBound + lowerBound ) / 2; |
515 | 3796 | int comparison = comparator().compare( at( medianIndex ), newElement ); |
516 | |
|
517 | 3796 | if ( comparison == 0 ) |
518 | 179 | return medianIndex; |
519 | 3617 | else if ( comparison < 0 ) |
520 | 2875 | ++lowerBound; |
521 | |
else |
522 | 742 | --upperBound; |
523 | 3617 | } |
524 | |
|
525 | 2290 | return lowerBound; |
526 | |
} |
527 | |
} |