forked from vigna/fastutil
-
Notifications
You must be signed in to change notification settings - Fork 0
/
CHANGES
1450 lines (984 loc) · 51.6 KB
/
CHANGES
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
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
8.5.13
- Thanks to Chanoch Goldfeder for fixing a number of bugs in ImmutableList.
8.5.12
- The fields of array-based containers are now protected.
- Entry.setValue() now works correctly in all iterators and iterator-like
methods of hash maps. Thanks to Nikita Sokolov for reporting that some
methods (e.g., fastForEach()) were not supporting setValue().
- New assertBigArray() methods help to check that arguments are
well-formed big arrays.
8.5.11
- Hash-based containers now expose ensureCapacity().
- HashCommon.nextPowerOf2() is now faster. Thanks to Richard Startin
for improving this method.
- A very long-standing bug in linked hash containers has been fixed.
Methods removing the last or first entry would not update correctly
the pointer to the first (or last, respectively) item, leading to
incorrect iteration behavior when removing the last element of a
container.
8.5.10
- Really fixed overflow bug in BigArrays.ensureOffsetLength(). Thanks
to Pierre Gruet for reporting this bug.
8.5.9
- Using BinIO to save arrays with a memory footprint larger than 2^31
bytes would have thrown an exception. Thanks to Sebastian Nagel for
reporting this bug.
- The capacity of pre-sized array FIFO queues was one element less than
necessary to avoid resizing at the given expected size.
- Arrays.ensureOffsetLength() could not work properly due to an
integer overflow. Thanks to Alex Herbert for fixing this bug.
8.5.8
- Fixed erroneous switch to Java 9.
- BinIO has been restructured to use java.nio whenever possible, and all
load/store methods now accept a byte order. The performance improvements
are very significant, in particular when handling data in native byte
order.
- Switched naming for mapped list to the standard type-first format.
Hopefully this should not hurt anyone.
8.5.7
- Memory-mapped big lists.
- Because of a wrong threshold radix sort in certain cases was much slower
than it should have been. Thanks to Johan Nystrom-Persson for reporting
this bug.
- Fixed subtle bug in OpenHashMap.merge(). Thanks to Ben Manes for
discovering this bug using Guava's testlib.
- Fixed other minor divergences from JDK's behavior detected by
Guava's testlib.
8.5.6
- Fixed broken export clause which was preventing it.unimi.dsi.fastutil
classes from being included in the main jar.
8.5.5
- New layout: fastutil-core.jar contains structures for integers, longs,
doubles, and objects, as before, but it has been fixed to contain
dependencies recursively (thanks to Preston Bennes for reporting this
bug). fastutil.jar is the usual, all-in-one fastutil jar. If your
dependency tree contains both fastutil-core.jar and fastutil.jar, you
have to exclude fastutil-core.jar.
- Several methods in hash-based map have better implementations in the
case both keys and values are references.
- Fixed problem with load factor in immutable sets. Thanks to Matthias
Seidel for reporting this bug.
8.5.4
- Fixed jar content.
8.5.3
- fastutil is now divided in three jars: fastutil-core.jar contains
structures for integers, longs, doubles, and objects: fastutil-extra.jar
contains additional structures for references, bytes, and characters;
fastutil.jar the remaining structures. Each jar depends on the previous
one (at the OSGi level, too).
- Unmodifiable wrappers now promote generic types as the JDK does. Thanks
to Scott Kilpatrick for suggesting this feature.
- Improved allocations for parallel streams. Thanks to C. Sean Young
<csyoung@google.com> for implementing this feature.
8.5.2
- Fixed wrong implementation of forEachRemaining() in hash-based
containers.
- Fixed iteration in linked hash maps.
- Fixed possible infinite recursion in AbstractMap.
8.5.1
- Fixed bug in AbstractIndexBasedBigIterator that was affecting
iterations on big lists.
- Added missing disambiguation method for type-specific Map.merge().
8.5.0
- Added type-specific spliterators and primitive stream methods to all
Collection types. Thanks to C. Sean Young <csyoung@google.com> for this
massive code contribution.
- Added fast spliterator implementations for most concrete types. The only
Collection types that do not currently have an optimized spliterator are
RBTreeSet/Map, AVLTreeSet/Map, and ArrayFrontCodedList. These are
planned for a future version. Thanks to C. Sean Young
<csyoung@google.com> for implementing this feature.
- Added a lot of special cases for AbstractList's methods to better take
advantage of RandomAccess based lists (the base List interface's default
methods will still use the iterator based versions always). Thanks to C.
Sean Young <csyoung@google.com> for implementing this feature.
- New immutable array-based lists and associated List.of() methods.
- Type specific versions of Predicate have been added.
Methods that take predicates (mainly Collection.removeIf) have been
updated to have an overload that takes that.
A consequence of this change is that removeIf(IntPredicate) on
ByteCollection, ShortCollection, and CharCollection have been deprecated
in favor of removeIf(Byte/Short/CharPredicate), which does not do widening casts.
If you have an implementation of ByteCollection, ShortCollection, or CharCollection
that implements removeIf(IntPredicate), you should update it to instead override
removeIf(Byte/Short/CharPredicate).
- Type-specific map methods merge() and computeIfAbsent() now have the
same name as in the JDK. The older names (with a type infix) have been
deprecated.
- computeIfAbsentPartial() has been renamed computeIfAbsent() so that
lambdas will generate fastutil type-specific functions.
- Fixed deserialization bug in front-coded big lists of arrays. Thanks
to Antoine Pietri for reporting this bug.
- New type-specific Map.merge() methods.
- Array lists have optimized addAll() methods for object lists, too, and
big lists have specialized addAll() methods for lists. Thanks to
Erich Schubert for reporting this issue.
8.4.4
- Renamed andThen/compose methods for type-specific functions
to avoid potential ambiguous calls.
- Now bulk colletion methods will try to use type-specific methods
if available. A side effect is that in case someone implemented
type-specific methods using the JDK version an infinite recursion
will happen. Thanks to C. Sean Young for this improvement.
- New Pair and SortedPair implementations, both standard and type-specific.
8.4.3
- Implemented andThen/compose methods for type-specific functions.
- Parallel sort implementations now use the common pool. Thanks to
shevek@github.com for suggesting this change.
- Static counting method for type-specific iterables.
- Static factory methods for immutable sets of primitive scalar types
within a given range.
- .of() factory methods for lists and sets.
8.4.2
- Big front-coded lists.
8.4.1
- Ported basic parallel quicksort to big arrays.
8.4.0
- Limited support for atomic big arrays of integers and longs.
8.3.2
- The documentation and the constructor for hash-based containers
was allowing a load factor of 1. Thanks to Andy Clegg for
reporting this bug.
- The copy constructor of array-based containers are now more efficient.
Thanks to Vladimir Krivosheev for proposing this enhancement.
8.3.1
- Fixed old-standing bug in the remove() method of the key set of
array-based maps. Thanks to Arnaud Floesser for reporting this bug.
- Fixed bug in ensureCapacity() for big lists based on big arrays.
Thanks to Nate Klein for reporting this bug.
8.3.0
- Add sort and unstableSort for type-specific lists. Thanks to C. Sean Young for
implementing this feature.
- Add methods in type-specific arrays that dynamically choose algorithm based
on input. Thanks to C. Sean Young for implementing this feature.
- Fixed very old-standing bug in trim() for hash containers: the
trimming was never happening due to variable shadowing.
- A number of type-specific methods for comparators have been implemented
by C. Sean Young.
- Big-array methods which can be told apart by dynamic binding are now
gathered in it.unimi.dsi.fastutil.BigArrays, and can be accessed very
easily by static imports. The old versions have been deprecated.
- New methods to unwrap iterators into big arrays.
8.2.3
- Array-based lists were not allocating a backing array even if the
required capacity was greater than the default capacity, violating
the contract. Thanks to 盏一 for reporting this bug.
- FastMultiByteArrayInputStream had since 2014 the wrong slice size
(1Ki instead of 1Gi). Thanks to Thibault Allançon for his detailed
reports, which dug out this old one.
8.2.2
- Fixed small bug in new lazy allocation scheme for array-based lists.
Resizing would throw an exception in certain circumstances.
- Now strategies must accept a supertype of the base type. Thanks to
shevek@github.com for suggesting this change.
- The Maven source jar does not contain tests anymore.
8.2.1
- Added default modularization to OSGi version, too.
8.2.0
- Added default modularization. Thanks to Joshua Popoff for taking care of
this issue.
- Implemented lazy allocation of arrays in array-based lists. Thanks to
Zheka Kozlov for suggesting this feature.
- Fixed a long-standing issue: the allocation of big lists based on big
arrays could not go beyond 2^31 because of a cut-and-paste bug.
- In line with the JDK, the default initial capacity for lists is 10 and
backing arrays (and, in generally, arrays) are automatically enlarged by
a 50% factor instead of a 100% factor.
- Included dependency-finding scripts by Tobias Meggendorfer.
8.1.1
- More default methods.
- Fixed lack of proper forEach()/fastForEach() method for entry sets of
linked maps (the order of iteration would be random). Thanks to Søren
Gjesse for reporting this bug.
- Fixed lack of proper licensing in test sources.
- A new NO_SMALL_TYPES makefile variable makes it possible to compile
a version of fastutil for ints, longs and doubles only. Thanks to
Tobias Meggendorfer for implementing this feature.
8.1.0
- WARNING: backward-incompatible name change for a few "compute"
methods.
- Implemented efficient new map methods and new iterable methods
in hash-based maps.
- A number of minor glitches has been fixed.
- FastIterable now has a fastForEach() method.
- Fixed ancient bug in the remove() method of entry sets of
tree-based maps.
- Array-based maps have a working key set and value collection.
8.0.0
- First release for Java 8 only, with implementation of new default
methods for iterators and maps. Thanks to Tobias Meggendorfer and
Salomon Sickert from the Technical University of Munich for help in the
implementation. Structure-specific, more efficient code will be
added in the near future. All wrapper (synchronized, etc.) have
been updated.
- Abstract type-specific comparators are deprecated: their only abstract
method has been pulled up as a default method of the type-specific
interface, which makes it possible to use lambda expressions to define
type-specific comparators.
- The default return value setter/getter are now optional for functions.
In this way, functions can now be defined using lambda expressions (and
they implement java.util.function.Function).
- New static methods in type-specific Maps and SortedMaps make it possible
to use easily fast iterators, even within for loops. Thanks to Tobias
Meggendorfer and Salomon Sickert from the Technical University of Munich
for implementing this feature.
- All hash-based structure now keep track of the size of their backing
array at creation time, and will never rehash below that size. Thanks
to Patrick Julien for suggesting this feature.
- Every deprecated method marked to be removed, or replaced by another
method, has been eliminated.
- Many abstract classes are now obsolete as their abstract methods have
become default methods.
- The type hierarchy of big-list iterators has been fixed.
7.2.0
- Major code cleanup. Several unnecessary method implementations have been
deleted. Several missing methods (e.g., equals()/hashCode() in wrappers)
have been implemented. All methods should now have a reasonable
Javadoc comment.
- Clarified the rem()/remove() conundrum: type-specific collections should
use and override rem(), but type-specific sets should use and override
remove().
- Fixed circular implementation of containsKey() in type-specific
abstract collections.
- Pulled up deprecation at the highest possible (interface) level.
- Collection.*All() methods do not assume anymore that they can
rely on the argument size().
7.1.1
- Fixed decade-old efficiency bug: implementation of RandomAccess
was hidden from synchronized and unmodifiable wrappers. Thanks to
Peter Burka for reporting this bug.
- The defaultReturnValue() getter in unmodifiable maps was throwing
an UnsupportedOperationException instead of delegating the call
to the underlying map. Thanks to Alex Fiennes for reporting this bug.
7.1.0
- Fixed decade-old efficiency bug. Due to a name clash between lists and
sets, the type-specific deletion method of a type-specific collection is
rem(), not remove(). The latter is reinstated in sets (but not, for
example, in lists) by the type-specific abstract set classes.
Nonetheless, implementors of subclasses must override rem(), not
remove(), as methods such as the type-specific version of removeAll()
invoke necessarily invoke rem() rather than remove(). Up to this
version, all concrete set implementations were overriding remove(),
instead, causing inefficiencies in the inherited methods. Thanks
to Christian Habermehl for reporting this bug.
- Fixed a bug introduced with the removal of old-style gcc assertions: all
load methods in BinIO that did not specify the number of elements to
read were computing the number of items in the loaded file incorrectly,
causing an EOFException (except for booleans and bytes).
7.0.13
- Fixed inheritance problem that would surface as key sets of
maps not implementing remove(). Thanks to Luke Nezda for
reporting this bug.
7.0.12
- Collection.isEmpty() was checking for iterator().hasNext() instead
of the opposite. Thanks to Olaf Krische for reporting this bug.
- Fixed lack of test for null/wrong class when testing entries.
7.0.11
- Several small glitches that were making fastutil's classes behave
differently from those of java.util have been fixed. Thanks to Balázs
Attila-Mihály or reporting these bug (obtained by massive testing using
Guava's battery of unit tests).
7.0.10
- The infinite-loop bug was affecting trim(int) besides trim(). Thanks
to Igor Kabiljo for reporting this bug.
- With the help of Erich Schubert, all methods with a type-specific,
more efficient counterpart have been deprecated.
7.0.9
- A subtle infinite-loop bug in hash-based structures (happening with load
factor 1 and tiny structures) has been fixed. Thanks to Tuomas Välimäki
and Jarkko Mönkkönen for reporting this bug.
- Now tree-based map have an addTo() method analogous to that of
hash-based maps. Thanks to Almog Gavra for implementing the method.
7.0.8
- Non-indirect priority queues are now serializable.
- Fixed implementation of structures based on a custom hash: keys
strategy-equal to zero zero would not be managed correctly. Thanks to
Shawn Cao for reporting this bug.
- Natural/opposite/abstract comparators are now serializable.
7.0.7
- Now we check whether ranges of parallel sorting algorithms
are too small *before* creating the thread pool.
- Merged Erich Schubert's fix for Object{AVL,RB}TreeSet.get().
7.0.6
- Faster priority queues: better variable caching, deleted
a spurious check, tests for parameters turned into assertions.
- New collection-based constructors for heap-based priority queues.
- Reviewed ObjectArrays.newArray() so that there is a fast track
for reallocation of arrays of type Object[].
7.0.4
- Fixed old-standing bug: iterators in linked maps would
return bogus data on entrySet().next()/entrySet().previous()
when no element is available instead of throwing an exception.
7.0.3
- Fixed wrong generation of custom-hash classes with primitive
keys. Thanks to Michael Henke for reporting this bug.
7.0.2
- Now we shutdown() correctly ForkJoinPool's.
- Constants limiting parallelism and recursion have been tuned.
- New implementations of indirect [parallel] quicksort (in ascending order
only).
- New stabilization method for post-processing of non-stable indirect
sorts.
7.0.1
- Now generated sources are formatted using the Eclipse command-line
facility.
7.0.0
- Now we need Java 7.
- New parallel versions of radix sort and quicksort. The sequential
implementations have been further improved.
- Restored the previous constants in mixing functions.
6.6.4
- Hopefully better mixing functions created by a genetic algorithm.
- Fixed a bug in floating-point hash-based containers: -0.0 and +0.0
were both converted to +0.0. Thanks to Dawid Weiss for reporting
this bug.
6.6.3
- Fixed subtle wrap-around bug in removal from iterator. Thanks to Eugene
Yakavets for reporting this bug.
6.6.2
- We now reduce backing arrays of hash-based classes when they are filled
below one fourth of the load factor. The reduction is not performed when
deleting from an iterator, as it would make iteration impossible.
- Significant simplification of Iterator.remove()'s implementations
for hash-based data structures.
6.6.1
- Fixed missed implementation: setValue() was not implemented for fast
iterators in hash-based maps.
6.6.0
- Major (transparent) rewrite of all hash-based classes inspired by the
Goldman-Sachs collections. We no longer allocate a byte array to store
the status of each slot: a null (or zero) key denotes an empty slot. The
null key is handled separately. The reduction in memory accesses makes
the cost of the additional logic negligible, and brings in significant
performance improvements. The code is actually simplified, as all loops
become a search for a nonzero element.
- Partial (one-step) unrolling of all lookup loops, following the strategy
used in Koloboke.
- Fixed an old bug: entrySet().remove(Entry) would remove entries checking
the value of the key, only.
- Fixed a bug in the iterator over hash big sets.
- OSGI metadata, thanks to Benson Margulies.
6.5.17
- Now TextIO methods trim strings before parsing numbers. This avoids
obnoxious exceptions when numbers are followed by whitespace.
6.5.16
- Improved speed of FastMultiByteArrayInputStream, and removed support
for mark()/reset().
- Deprecated array fill() methods in favour of java.util's.
6.5.15
- De-deprecated quicksort methods for primitive-type arrays. It turned out
that Java's Arrays.sort() switches to mergesort on large, semi-sorted
arrays. Moreover, in Java 7 the support array is allocated of the same
size of the argument array, not of the sorted fragment. This performance
bug was entirely killing the performance of Transform.transposeOffline()
and other methods. Until that bug is fixed, we will have to rely on our
quicksort method (which is a pity, because Java's sort is, for the rest,
so beautifully engineered).
6.5.14
- Equality in type-specific hash-based data structures with float or
double keys is now checked by converting to int/long bits using the
conversion method of the appropriate class. Previously, using NaNs as
keys would have led to misbehaviour. Thanks to Davide Savazzi for
reporting this bug.
6.5.13
- Fixed a very unlikely corner case that might have led to reduction in
size of an array instead of a growth. Thanks to Ernst Reissner for
reporting this bug.
- InspectableFileCachedInputStream no longer performs a call to
RandomAccessFile.position() when the end of file has been reached
and the file is entirely held in memory.
- All front-coded lists now implement java.util.RandomAccess.
6.5.12
- Removed some useless wrapper creation in a few methods of tree-based map
classes.
- Fixed pathological maxFill computation for very small-sized big open
hash sets.
6.5.11
- A very old and subtle performance bug in hash-based data structures has
been fixed. Backing arrays were allocated using the number of expected
elements divided by the load factor. However, since the test for
rehashing was fired by equality with the table size multiplied by the
load factor, if the expected number of elements multiplied by the load
factor was an integer a useless rehash would happen for the very last
added element. The only effect was an useless increase in object
creation.
6.5.10
- Now iterators in object set constructors are of type Iterator, and not
anymore ObjectIterator. The kind of allowed iterators has been
rationalised and made uniform through all classes implementing Set.
6.5.9
- New methods to get a type-specific Iterable from binary or
text files.
6.5.8
- Fixed stupid bug in creation of array-based FIFO queues.
6.5.7
- Fixed a very subtle bug in hash-based data structures: addAll() to a
newly created structure could require a very long time due to
correlation between the positions in structures with different table
sizes.
6.5.6
- equals() method between arrays have been deprecated in favour of the
java.util.Arrays version, which is intrinsified in recent JVMs.
- InspectableFileCachedInputStream.reopen() makes it possible to
read again from the start an instance on which close() was
invoked.
6.5.5
- The abstract implementation of equals() between (big) lists now uses
type-specific access methods (as the compareTo() method was already
doing) to avoid massive boxing/unboxing. Thanks to Adrien Grand for
suggesting this improvement.
- FIFO array-based queues are now serializable.
6.5.4
- Further fixes related to NaNs in sorting.
- Fixed very old bug in FastByteArrayOutputStream.write(int).
Thanks to Massimo Santini for reporting this bug.
- We now use Arrays.MAX_ARRAY_SIZE, which is equal to Integer.MAX_VALUE
minus 8, to bound all array allocations. Previously, it might happen
that grow() and other array-related functions could try to allocate an
array of size Integer.MAX_VALUE, which is technically correct from the
JLS, but will not work on most JVMs. The maximum length we use now is
the same value as that used by java.util.ArrayList. Thanks to William
Harvey for suggesting this change.
6.5.3
- Corrected erroneous introduction of compare() methods on integral
classes (they appeared in Java 7).
6.5.2
- A few changes were necessary to make fastutil behave as Java on NaNs
when sorting. Double.compareTo() and Float.compareTo() treat Double.NaN
as greater than Double.POSITIVE_INFINITY, and fastutil was not doing it.
As part of the change, now all comparisons between primitive types are
performed using the compare() method of the wrapper class
(microbenchmarks confirmed that there is no speed penalty for that,
probably due to inlining or even intrinsification). Thanks to Adam Klein
for reporting this bug.
- All quickSort() implementations that do not involve a comparator are now
deprecated, as there are equivalent/better versions in java.util.Arrays.
6.5.0 -> 6.5.1
- Now FastBuffered{Input/Output}Stream has a constructor with an
explicitly given buffer.
- Abandoned golden-ratio based expansion of arrays and lists in favour of
a (more standard) doubling approach.
- Array-based FIFO queues now reduce their capacity automatically by
halving when the size becomes one fourth of the length.
- The add() method for open hash maps has been deprecated and replaced by
addTo(), as the name choice proved to be a recipe for disaster.
- New InspectableFileCachedInputStream for caching easily large byte
streams partially on file and partially in memory.
- The front() method for semi-indirect heaps took no comparator, but
was used in queues in which you could support a comparator. There
is now a further version accepting a comparator.
- Serial Version UIDs are now private.
6.4.6 -> 6.5.0
- Fixed type of array hash strategies.
- Fixed use of equals() instead of compareTo() in
SemiIndirectHeaps.front(). Thanks to Matthew Hatem for reporting this
bug.
- Now we generate custom hash maps for primite types, too (as we were
already doing for sets).
6.4.5 -> 6.4.6
- In array-based priority queues changed() would not invalidate
the cached index of the smallest element.
6.4.4 -> 6.4.5
- In some very rare circumstances, enumeration of hash sets or maps
combined with massive element removal (using the iterator remove()
method) could have led to inconsistent enumeration (duplicates and
missing elements). Thanks to Hamish Morgan for reporting this bug.
6.4.3 -> 6.4.4
- Array-based maps were not implementing correctly entrySet().contains(),
and as a consequence equals() between such maps was broken. Thanks to
Benson Margulies for reporting this bug.
6.4.2 -> 6.4.3
- Now array-based priority queue cache their first element. Moreover,
they implement the correct type-specific interface.
6.4.1 -> 6.4.2
- Now we have indirect lexicographical radix sort on pairs of arrays,
mainly used to compute quickly Kendall's tau.
- New reverse method for arrays (useful for radix descending sorts).
- Radix sort (one or two arrays) for big arrays.
- Now radix sort uses correctly (minimally) sized support arrays when
sorting subarrays.
6.4 -> 6.4.1
- Now we have a separate directory, settable in the makefile, to generate
sources. This makes Maven integration easier.
- The store methods in TextIO for big arrays were broken.
- Now big-array lists implement the Stack interface.
- Fixed subtle bug in rehash() methods of big hash sets.
6.3 -> 6.4
- WARNING: Indirect queues must obviously have a way to determine whether
an index is in the queue. It was an oversight in the interface design
that a contains() method was not present. We wook the risk of adding it
now. At the same time, we modified remove() so that now returns a
boolean specifying whether the index to be removed was actually in the
queue, as this is more in line with the Java Collections Framework.
- Removed unused double-priority queue related classes.
- Now array-based sets and maps have a constructor based on
java.util.Collection and java.util.Map (as for the other
kind of sets and maps).
- New doubly linked implementation for linked hash maps and sets. It uses
twice the space for pointers, but mixes well with linear probing, so we
have again constant-time true deletions. Moreover, iterators can be
started from any key in constant time (albeit the first access to the
index of the list iterator will require a linear scan, unless the
iterator started from the first or the last key). Additional methods
such as getAndMoveToFirst() make the creation of LRU caches very easy.
Thanks to Brien Colwell for donating the code.
- Now object-based array FIFO queues provide deque methods. Moreover,
they clean up the backing array after returning an object or when
performing a clear().
- New get() method in set implementations makes it possible to recover
the actual object int the collection that is equal to the query key.
- A number of bugs were found and fixed by Christian Falz (thanks!). In
all binary search code the "to" parameter was *inclusive*, but the
documentation said *exclusive*, with obvious problems. Hash map
iterators could return under some very subtle and almost irreproducible
circumstances a previously deleted slot. Deleted hash map entries would
return spurious null values.
6.2.2 -> 6.3
- We now have radix sort. It's much faster than quicksort, but it can
only sort keys in their natural order. There are multiple-array
and indirect (and possibly stable) versions available.
- There are now custom hash sets also for type-specific keys. This makes
it possible to use hash sets to index data indirectly (e.g., using
integer or long just as indices).
- Shuffling static methods for all kinds of (big) list and arrays.
6.2.1 -> 6.2.2
- A new add() method makes the usage of maps as counters easier
and faster.
6.2.0 -> 6.2.1
- A very stupid bug was causing twice the rehashing that was
necessary. Now insertions in hash-based classes are significantly faster.
6.1.0 -> 6.2.0
- A better structure of the scan loop for hash tables borrowed
from HPPC (http://labs.carrotsearch.com/hppc.html) gives some
speed improvement to hash-based classes.
6.0.0 -> 6.1.0
- Hash-based classes have been rewritten using linear probing and
a good hash (MurmurHash3). The old classes can be still generated
using the target oldsources.
- Bizarre queues (double- and sesqui-indirect) have been removed
from the standard jar, but they can be still generated using the
target oldsources.
5.1.5 -> 6.0.0
- WARNING: the jar file is now fastutil.jar (not fastutil5.jar), again.
- WARNING: now fastutil requires Java 6+.
- fastutil is now released under the Apache License 2.0.
- New framework for big arrays, represented as arrays-of-arrays.
BigArrays and the type-specific counterparts provide static
methods of all kinds.
- New Size64 interface for classes implementing big collections.
- New framework for big lists--lists with longs as indices. The only
present implementation uses big arrays, but, for instance,
Sux4J's succinct lists will be retrofitted to LongBigList
(presently they implement LongBigList from dsiutils, which will
be deprecated).
- List.iterator() now returns a ListIterator. There is no real reason
not to do this, and the API change is handled from an implementation
viewpoint in AbstractList, so nodoby should really notice.
- New Collections.asCollection(Iterable) method to expose iterables as
collections (missing methods are computed using the iterator). This was
also the occasion to streamline type-specific abstract collections,
which now inherit from java.util.AbstractCollection, so we support
contains, clear, etc. methods as long as there is an iterator.
- Fixed bugged array-based constructors of ArrayMap and ArraySet.
- Fixed bugged put/remove methods in abstract functions. Thanks to
Katja Filippova for reporting this bug.
- New front-coded lists use big arrays, so they can store much more
(in fact, unlimited) data. Unfortunately, they are no longer
serialisation-compatible with previous versions.
- New MeasurableStream interface that is implemented by
MeasurableInputStream and by a new, analogous MeasurableOutputStream.
- Better FastBufferedOutputStream and FastByteArrayOutputStream that
are measurable and positionable.
- Now all clone() methods override covariantly the defult return type
(Object).
5.1.4 -> 5.1.5
- ArraySet was implementing isEmpty() with inverted logic (thanks to
Marko Srdanovic for reporting this bug).
- New constructor for FastMultiByteArrayInputStream: it takes a
MeasurableInputStream and uses length() to determine the number
of bytes to load into memory.
5.1.3 -> 5.1.4
- The implementation of RepositionableStream in FastByteArrayOutputStream
was fraught with a horrendous bug (thanks to Claudio Corsi for reporting),
in spite of extensive unit tests.
5.1.2 -> 5.1.3
- A bug existing since the first release was preventing tables
larger than 2^30 bits to work (the computation of the next bucket
to look at would cause an integer overflow).
- FastByteArrayOutputStream now implements RepositionableStream.
- Type-specific versions of Iterable.
- Some methods (e.g., iterator() and values()) are now explicitly
re-strengthened wherever necessary to avoid complaints about
ambiguous method invocations by some compilers.
- The introduction of functions added several bugs to the empty/singleton
map classes. Inheriting from the respective function counterparts left
several methods underspecified (equals(), etc.). This has been
(hopefully) fixed.
5.1.1 -> 5.1.2
- FastBufferedInputStream now supportw length() by FileChannel-fetching
on FileInputStream instances (it already used to support position()
by the same mechanism).
5.1.0 -> 5.1.1
- Byte-array MG4J I/O classes have been moved here.
5.0.9 -> 5.1.0
- Fixed documentation for custom/noncustom maps (it was exchanged).
- New type-specify entrySet() methods that avoid complicated casting
to get a type-specific entryset. Moreover, now entrySet() can
return an object implementing Fast(Sorted)EntrySet to indicate
that a fastIterator() method is available. Fast iterators can
return always the same Entry object, suitably mutated. We thank
Daniel Ramage for suggesting this feature.
- Several hundreds of new classes generated by the new Function interface,
which represent mappings for which the entry set is not enumerable
(e.g., hashes). Functions have their usual share of satellite objects
(wrappers, etc.). There are no implementations--the main purpose of
the new interfaces is to make Sux4J (http://sux.dsi.unimi.it/)
more object-oriented.
5.0.8 -> 5.0.9
- Slightly reduced overhead for bound checks in heap-based queues.
- BinIO was loading byte arrays one byte at a time. Now some conditionally
compiled code uses bulk-read methods instead. Moreover, horrible kluges
to work around Java bug #6478546 have been included.
5.0.7 -> 5.0.8
- Faster array maps and sets: System.arraycopy() is very slow on small arrays
(due to inherent costs of calling native code) and reflection-based array
creation is a disaster. Now we use object arrays and loops.
- New clone() methods for array-based structures and custom serialisation.
- FastBuffered*Stream has been simplified and streamlined. No more block alignment.
5.0.6 -> 5.0.7
- Better algorithm for front() in heaps.
- New comprehensive collection of array-based maps and sets. The motivation
behind such structures is the need for quick, low-footprint data
structures for *very* small sets (say, less than 10 elements). For
instance, in MG4J we were using sparse reference-based hash tables, but
it turned out that System.identityHashCode() is *deadly* slow and
scanning linearly an array searching for the desired element is
significantly faster.
5.0.5 -> 5.0.6
- Due to erratic and unpredictable behaviour of InputStream.skip(), which
does not correspond to its specification and Sun refuses to fix (see bug
6222822; don't be fooled by the “closed, fixed” label),
FastBufferedInputStream now peeks at the underlying stream and if it is
System.in it uses repeated reads. Moreover, it will use alternatively
reads and skips to guarantee that the number of skipped bytes will be
smaller than requested only if end of file has been reached.
- The insertion and key retrieval methods of hash-based structures are
now protected and final.
- New front() method for indirect queues. It retrieves quickly the indices
associated to elements equal to the top.
- First JUnit tests.
5.0.4 -> 5.0.5
- Fixed possible overflow in FastBufferedInputStream.available().