mirror of
https://github.com/maxkratz/fastutil.git
synced 2024-09-08 00:32:56 +00:00
1452 lines
52 KiB
Text
1452 lines
52 KiB
Text
8.5.13
|
|
|
|
- Thanks to Chanoch Goldfeder for fixing a number of bugs in ImmutableList.
|
|
|
|
- Thanks to Barak Ugav for implementing a faster ArrayList.removeIf().
|
|
|
|
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().
|
|
|
|
- Indirect heaps have faster checks for elements belonging or not to the
|
|
queue. In particular, we just rely on array access for detecting indices
|
|
out of bounds. Profiling with LaMa4J showed that in some circumstances
|
|
checking explicitly the indices were within bounds was taking more time
|
|
that the actual heap inner workings.
|
|
|
|
- Fixed obnoxious bug dating to the first fastutil implementation. The
|
|
macro KEY_EQUALS_HASH(x,h,y), which checks for equality between x and y
|
|
given that the hash of x is h, was evaluating hashCode() on y without
|
|
guarantee that y was non-null. As a result, adding a null to a mapped
|
|
followed by the insertion of an element with hash code 0 would have
|
|
thrown a NullPointerException. The bug went unobserved for years because
|
|
no one use nulls as keys, and was actually detected by a bug in BUbiNG's
|
|
code (which was in turn mistakenly inserting nulls in a set).
|
|
|
|
5.0.3 -> 5.0.4
|
|
|
|
- Fixed missing declaration of generic type for HASH_STRATEGY.
|
|
|
|
- A new abstract class, MeasurableInputStream, is used for streams
|
|
whose length and current position are always known. This actually
|
|
was needed for BUbiNG development.
|
|
|
|
- New readLine() family of method for reading "lines" directly
|
|
from a FastBufferedInputStream.
|
|
|
|
- In FastBufferedInputStream, reset() has been deprecated in favour
|
|
of flush().
|
|
|
|
- Array-based lists of objects now reallocate the backing array
|
|
using reflection *only* if they were created by wrapping. This
|
|
won't change the previous behaviour, but at the price of a boolean
|
|
per list we have unbelievably faster array reallocation.
|
|
|
|
- New explicit fast load factors in Hash.
|
|
|
|
5.0.2 -> 5.0.3
|
|
|
|
- Bizarrily, java.util.List re-specifies iterator(), even if it extends
|
|
Collection. As a result, we need to re-strengthen it in type-specific lists.
|
|
|
|
- Fixed new horrible bug introduced by adding Booleans to BinIO and TextIO.
|
|
Problem is, I didn't know #assert is cumulative.
|
|
|
|
5.0.1 -> 5.0.2
|
|
|
|
- Fixed bug in sorted maps key sets and values that would cause a
|
|
stack overflow when calling size() and a few other methods.
|
|
|
|
- Fixed lack of booleans in BinIO and TextIO.
|
|
|
|
- BinIO now checks for too large files.
|
|
|
|
5.0 -> 5.0.1
|
|
|
|
- In BinIO, it was assumed that .SIZE would give the size of
|
|
primitive types in *bytes*. Bad mistake.
|
|
|
|
4.4.3 -> 5.0
|
|
|
|
- Java 5 only!
|
|
|
|
- Support for generics. This led to a number of backward-incompatible changes:
|
|
* toArray(Object[]) does not accept any longer null as an argument;
|
|
* singletons for empty collections (sets, lists, ecc.) are type-specific;
|
|
* iterators on sorted collections are bidirectional *by specification*;
|
|
* the new, covariantly stronger methods defined in all interfaces (e.g.,
|
|
iterator() returning a type-specific iterator) are now the default,
|
|
and in the abstract classes the old methods (e.g., objectIterator())
|
|
now just delegate to the standard method, which is the contrary
|
|
of what was happening before: you'll have to turn all methods
|
|
such as objectIterator() in iterator(), etc.
|
|
* all deprecated methods have been dropped.
|
|
|
|
- Array growth functions now will return the correct empty array for
|
|
object arrays (it used to return ObjectArrays.EMPTY_ARRAY).
|
|
|
|
- Strategies are generic and no longer required to accept REMOVED.
|
|
|
|
- Stale references could hang around in the nodePath array for
|
|
Red-Black trees and map; this has been fixed.
|
|
|
|
- The difference in semantics with the standard toArray(Object[])
|
|
specification, which has always been in place, is now exhaustively
|
|
explained.
|
|
|
|
- Major code cleanup (mostly code deletion) due to passing fastutil
|
|
into Eclipse to check unused code, etc.
|
|
|
|
4.4.2 -> 4.4.3
|
|
|
|
- Important bug fix in FastBufferedInputStream.
|
|
|
|
4.4.1 -> 4.4.2
|
|
|
|
- New reset() method to invalidate the buffer of a FastBufferedInputStream,
|
|
making it possible to read safely files written by other processes
|
|
(given, of course, that you are synchronising the accesses).
|
|
|
|
4.4.0 -> 4.4.1
|
|
|
|
- New parallel-array constructor for all maps. Very useful for
|
|
static final map initialisation.
|
|
|
|
- Following considerations in Jakarta Commons I/O, the standard
|
|
buffer size has be lowered to 8Ki.
|
|
|
|
- Some arguments were declared as DataInputStream instead of
|
|
DataInput.
|
|
|
|
- New methods for reading/writing objects from/to streams.
|
|
|
|
4.3.2 -> 4.4
|
|
|
|
- New static containers for reading and writing easily text and binary
|
|
data streams. They load/save arrays, iterators etc. to buffered readers
|
|
or streams.
|
|
|
|
- Moved here fast input/output buffered classes from MG4J. This makes
|
|
fastutil self-contained.
|
|
|
|
- The trivial implementation of the type-specific iterator was missing
|
|
from AbstractList.drv (surprisingly, not from the subclass implementation!).
|
|
|
|
- The sublist implementation in AbstractList.drv is now protected and static.
|
|
The attributes are protected, too.
|
|
|
|
- Now we compare booleans (false<true). As a result, also lists of
|
|
booleans do get lexicographical comparability.
|
|
|
|
- add(k) in AbstractList.drv now calls add(size(), k).
|
|
|
|
- Fixed error messages for out-of-bound indices in lists.
|
|
|
|
4.3.1 -> 4.3.2
|
|
|
|
- Fixed small innocuous bug: a code fragment related to non-linked
|
|
hash table was generated for linked hash tables, too, do to a
|
|
case type in a preprocessor directive. The code fragment, however,
|
|
had no effect.
|
|
|
|
- Fixed memory leak in OpenHashMap: the remove() method was not clearing
|
|
the key (whereas OpenHashSet was).
|
|
|
|
4.3 -> 4.3.1
|
|
|
|
- New fully indirect heap-based double priority queues.
|
|
|
|
- Fixed docs for queues: in 4.3, we were claiming that greater elements
|
|
are dequeued first, while the opposite happens.
|
|
|
|
4.2 -> 4.3
|
|
|
|
- New full-fledged set of unmodifiable structures *and* iterators.
|
|
|
|
- Removed about a dozen spurious final method modifiers.
|
|
|
|
- Made rehash() protected, so that everybody can play with different
|
|
rehashing strategies.
|
|
|
|
- trim() in array lists wasn't doing the right thing, because trim(int)
|
|
wasn't doing it in the first place. Now if n is smaller than the size
|
|
of the list, we trim at the list size (previously we were doing nothing).
|
|
|
|
- Analogously, trim() in hash-table-based structures was fixed so that
|
|
trimming a table below its size will result in rehashing to the minimum
|
|
possible size.
|
|
|
|
4.1 -> 4.2
|
|
|
|
- Improved array methods: now all methods on objects (e.g., grow()) return an
|
|
array of the same type of the array that was passed to them, similarly to
|
|
toArray() in collections.
|
|
|
|
- Fixed missing macro substitution for empty iterator methods. In any
|
|
case, they were already deprecated.
|
|
|
|
4.0 -> 4.1
|
|
|
|
- New classes for custom hashing methods (mainly thought for
|
|
arrays). Correspondingly, methods for arrays have been implemented in
|
|
the static containers.
|
|
|
|
- BasicEntry now throws an UnsupportedOperationException on calls to
|
|
setValue(). If you ever used that method, you got wierd results, as
|
|
it does not update the underlying map. The method is now implemented
|
|
correctly in open hash maps, in which previously did not correctly
|
|
update the underying map.
|
|
|
|
- Reimplemented copy of an entire array using clone().
|
|
|
|
- Fixed a bug in clear() for indirect heaps (the inversion array was not
|
|
being cleared).
|
|
|
|
- Indirect priority queue interfaces now feature an optional allChanged()
|
|
method that can be used to force a complete heap rebuild. It is implemented by
|
|
all current array-based and head-based concrete classes.
|
|
|
|
3.1 -> 4.0
|
|
|
|
- IMPORTANT: The optimized methods that a type-specific must provide now
|
|
include an addElements() method that quickly adds an array of elements. As
|
|
usual, the method is fully implemented by the type-specific abstract lists.
|
|
|
|
- IMPORTANT: The abstract generic version of get(), put() and remove() for maps
|
|
with non-object keys or values now always return null to denote a missing
|
|
key. They used to return an object-wrapped default return value.
|
|
|
|
- Completely new and comprehensive implementation of priority queues, both
|
|
direct and indirect. Implementations are by heaps and by flat arrays. There
|
|
are also static containers with all relevant heap methods, for people
|
|
wanting to do their own thing.
|
|
|
|
- New static containers for comparators.
|
|
|
|
- All singletons, empty sets and snychronized wrappers are public so
|
|
you can inherit from them.
|
|
|
|
- Abstract maps now provide keySet() and values() based on entrySet().
|
|
|
|
- New abstract classes for sorted sets and maps with delegators to
|
|
type-specific methods.
|
|
|
|
- New public methods in Arrays and in type-specific Arrays classes for checking
|
|
ranges.
|
|
|
|
- New static methods for type-specific arrays that allow to grow, enlarge
|
|
and trim them with ease.
|
|
|
|
- Clarified abstract implementation of default return values, and implemented
|
|
clarified specification. Just a couple of method in hash maps were not
|
|
already compliant.
|
|
|
|
- The pour() method now returns a list. The previous version was returning
|
|
a linked hash set, which was rather nonsensical anyway, since an iterator
|
|
build on the returned set could have been different from the original iterator.
|
|
You can always pour an iterator into a set by providing the set explicitly.
|
|
|
|
- An exception-throwing implementation of some methods in AbstractSet
|
|
was missing. Same for AbstractCollection, AbstractMap and AbstractList.
|
|
|
|
- New basic inner entry class for abstract maps, which makes it easier to write
|
|
entrySet() methods for classes that do not have their own entries.
|
|
|
|
- Added missing get(Object) method in AbstractMap (just delegates to
|
|
the type-specific version).
|
|
|
|
- For lazy people, now containsKey() and containsValue() in AbstractMap
|
|
are defined by looking into keySet() and values().
|
|
|
|
- Fixed a few methods of EMPTY_LIST which were throwing exception
|
|
semantically (see the introduction).
|
|
|
|
- The interval iterators are now list iterators, except for longs.
|
|
|
|
- Fixed a bug in size() for array lists (reducing the size of an array
|
|
would lead to an exception).
|
|
|
|
- Fixed double bug in hash tables: first of all, on very small sizes adding
|
|
growthFactor would have left the size unchanged, giving rise to infinite
|
|
loops. (Thanks to Heikki Uusitalo for reporting this bug.) Second, growthFactor
|
|
was not being used *at all* by hash maps.
|
|
|
|
- Fixed entries emitted by singleton maps. Now they are type-specific.
|
|
|
|
- Fixed a number of minor glitches in gencsource.sh, and added some comments.
|
|
|
|
- HashCommon.removed has been renamed HashCommon.REMOVED.
|
|
|
|
- Boolean objects are now generated using valueOf() instead of the constructor.
|
|
|
|
- New type-specific wrappers for list iterators.
|
|
|
|
3.0 -> 3.1
|
|
|
|
- IMPORTANT: it.unimi.dsi.fastutil.Iterators methods have
|
|
been spread in type-specific static containers.
|
|
|
|
- New Stack interface, implemented by type-specific lists.
|
|
|
|
- New static container classes Collections, Sets, and Lists.
|
|
Presently they just provide empty containers.
|
|
|
|
- New type-specific static contains (e.g., IntSets) providing
|
|
singletons and synchronized wrappers.
|
|
|
|
- Entry sets now have entries that are equal() to entries
|
|
coming from corresponding maps in java.util.
|
|
|
|
- Spelling everywhere changed to Pure American. "synchronized" in code and
|
|
"synchronise" in text side-by-side were looking really wierd...
|
|
|
|
3.0 -> 3.0.1
|
|
|
|
- New unwrap() methods for type-specific collections.
|
|
|
|
- Fixed old-as-world-bug, apparently wide but that evidently no one ever
|
|
noticed: AbstractMap was not serialisable, and, as a result, the default
|
|
return value was not serialised (I find sincerely counterintuitive that
|
|
making a class serialisable doesn't do the same for its supertypes). It
|
|
wasn't ever even *documented* as preserved, so probably everyone thought
|
|
this was my idea, too. Too bad this breaks once more serialisation
|
|
compatibility. Since I had to break some serialisation anyway, I decided
|
|
to eliminate the residual serialisation of p in hash table classes, too
|
|
(which breaks serialisation for all hash-based classes).
|
|
|
|
2.60 -> 3.0
|
|
|
|
- IMPORTANT: All classes have been repackaged following the type of
|
|
elements/keys. Sources will have to be retouched (just to change
|
|
the import clause) and recompiled.
|
|
|
|
- IMPORTANT: Because of an unavoidable name clash in the new type-specific list
|
|
interface, the method remove(int) of IntCollection has been renamed rem(int).
|
|
The only really unpleasant effect is that you must use rem(int) on variables of
|
|
type IntCollection that are not of type IntSet (as IntSet reinstates
|
|
remove(int) in its right place)--for instance, IntList.
|
|
|
|
- Brand-new implementation of type-specific lists, with all the features you'd
|
|
expect and more.
|
|
|
|
- Insertions for readObject() in hash tables are now handled in a special way
|
|
(20% faster).
|
|
|
|
- Implemented linear-time tree reconstruction for readObject() (in practice, more
|
|
than twice faster).
|
|
|
|
- Fixed a problem with serialisation of hash tables: the table would have
|
|
been reloaded with the same p, even if it was preposterous. We still
|
|
save p, however, to avoid breaking serialisation compatibility.
|
|
|
|
- Fixed missing implementation of type-specific sets, which should
|
|
have extended type-specific collections, but they weren't.
|
|
|
|
- The default return value is now protected.
|
|
|
|
- New family of pour() methods that pour an iterator into a set.
|
|
|
|
- New programmable growth factor for hash-table-based classes.
|
|
|
|
- Eliminated a few useless method calls in tree map.
|
|
|
|
- Wide range of complex assertions, which are compiled in or out using the
|
|
"private static final boolean" idiom.
|
|
|
|
- For references we now use System.identityHashCode(); this shouldn't change
|
|
much, but it seems definitely more sensible.
|
|
|
|
- Fixed major bug in subSet()/subMap(): creating a subMap of a tailMap (or
|
|
headMap) a right extreme (left, resp.) equal to 0 would have caused the
|
|
creation of a tailMap (or headMap, resp.), discarding the extreme. Very,
|
|
very unlikely, but it happened in a test.
|
|
|
|
- Fixed small bug in standard remove() method of submaps, which would have
|
|
returned a default return value wrapped in a suitable object instead of
|
|
null on non-existing keys.
|
|
|
|
2.52 -> 2.60
|
|
|
|
- IMPORTANT: Major overhaul of iterators. Now iterators must be skippable,
|
|
so previous implementation of type-specific iterator interfaces will
|
|
not work. However, new abstract classes allow to build iterator with ease
|
|
by providing for free the skipping logic, and many useful static methods in
|
|
Iterators allow to generate type-specific iterators wrapping standard
|
|
iterators, arrays, etc.
|
|
|
|
- Better strategy for clear() on hash tables: we don't do anything only
|
|
if all entries are free (which means that an empty table with deleted
|
|
entry will be cleared).
|
|
|
|
2.51 -> 2.52
|
|
|
|
- IMPORTANT: The package name has changed to it.unimi.dsi.fastutil to be
|
|
uniform with JPackage conventions. However, this means that you must manually
|
|
erase the old one and update your sources.
|
|
|
|
- clear() doesn't do anything on empty hash tables.
|
|
|
|
2.50 -> 2.51
|
|
- New trim(int) method to reduce a hash table size avoiding to
|
|
make it too small.
|
|
|
|
- serialVersionUID is now fixed, to avoid future incompatibilities.
|
|
|
|
2.11 -> 2.50
|
|
|
|
- IMPORTANT: The Collection interface now prescribes an iterator
|
|
method with a type-specific name (e.g., intIterator()) that
|
|
returns directly a type-specific iterator.
|
|
|
|
- New Reference maps and sets that allow to store more quickly
|
|
canonised objects.
|
|
|
|
- New linked maps mimicking java.util's, but with a boatload
|
|
of additional features.
|
|
|
|
- Small bug fix: the get(Object) method would return null
|
|
instead of the default return value for maps with object
|
|
keys.
|
|
|
|
- Major bug fix: iterating backwards on submaps was leading
|
|
to unpredictable results.
|
|
|
|
- Major bug fix: cloning maps would have caused inconsistent behaviour.
|
|
|
|
- Major code redistribution: now whenever possible wrappers
|
|
belong to abstract superclasses.
|
|
|
|
2.1 -> 2.11
|
|
|
|
- Now we cache the hash of an object before entering
|
|
the hash table loop.
|
|
|
|
2.0 -> 2.1
|
|
|
|
- A simple optimisation in hash-table inner loops has given
|
|
quite a performance boost under certain conditions (we do
|
|
not compute the secondary hashing if it is not necessary). Inspired
|
|
by Gnu Trove.
|
|
- The trim() method would have in fact trimmed nothing, just
|
|
rehashed the table.
|
|
- The computed maxFill value was sligtly too small.
|
|
- Also tree sets now have constructors from arrays.
|
|
- More internal methods have been made final.
|
|
|
|
1.3 -> 2.0
|
|
|
|
- ALL MAPS AND SETS HAVE NEW NAMES DEPENDING ON THE IMPLEMENTATION.
|
|
- Introducing new high-performance, low memory-footprint implementation of
|
|
SortedMap and SortedSet.
|
|
- Two tree implementations are available: RB trees and
|
|
AVL trees. Both implementations are threaded. See the README.
|
|
- Fixed a bug in hashCode() and contains() for HashMap.drv (it was
|
|
considering keys only!).
|
|
- Fixed a bug in contains() for entrySet() in all maps (it was using
|
|
VALUE_EQUAL to test equality for values given as objects).
|
|
- I realised that a default return value can be useful also for maps and sets
|
|
returning objects, so now you have it. It is even independent for submaps and
|
|
subsets.
|
|
- Classes are no longer final. The performance gain is around 1%, and
|
|
the decrease in usefulness is orders of magnitudes greater.
|
|
- We now check equality using first hashCode() and then equals().
|
|
- The tests for speed now warm up the trees by doing repeated insertions
|
|
and deletions, so that the benefits of a better balancing criterion
|
|
are more evident.
|
|
- The regression tests are much more stringent.
|
|
- Fixed hashCode() for hash maps (wasn't conforming to the Map interface
|
|
specification).
|
|
- Implemented linear cloning for tree classes.
|