fastutil/CHANGES

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.