Koloboke Collections 1.0 API

This library is a carefully designed and efficient extension of the Java Collections Framework with primitive specializations and more.

See: Description

Packages 
Package Description
com.koloboke.collect
The root package of the collection library.
com.koloboke.collect.hash
Contains basic interfaces and commonly used classes related to containers, based on hash tables.
com.koloboke.collect.map
Contains interfaces of Map specializations, their factories and cursors.
com.koloboke.collect.map.hash
Contains interfaces of Map specializations, based on hash tables, their factories and static factory methods.
com.koloboke.collect.set
Contains interfaces of Set specializations and their factories.
com.koloboke.collect.set.hash
Contains interfaces of Set specializations, based on hash tables, their factories and static factory methods.
com.koloboke.function
The complete set of functional interfaces, following java.util.function scheme.
This library is a carefully designed and efficient extension of the Java Collections Framework with primitive specializations and more.

Overview

With a few exceptions, the library API consists of three types of classes:
  1. Interface hierarchy, which generally repeats and extends Java Collection Framework (JCF) interface and class hierarchy. Also, all interfaces are populated for all 7 primitive type specializations, and "object specialization" for API symmetry (see primitive specializations naming convention for more information on this). For example, in JCF HashSet class extends Set extends Collection. In this library HashCharSet interface extends CharSet, which extends Set and CharCollection, which extends Collection and Container.

    Also, a complete set of functional interfaces is defined in the com.koloboke.function package, it is needed because the library backports many methods from Java 8 Collections API (see API additions), which employ these interfaces.

  2. Factory interfaces, each of them defines several dozens of factory methods which construct corresponding container interface instances. You can construct instances of three mutability profiles. Factory interfaces also form a hierarchy, which follow container's interface hierarchy, to ease making common configurations. For example, you can define a method which accept a HashContainerFactory to configure all factories which produce hash sets and maps in the application.

    Note that all factories in the library are immutable, on changing any configuration a new copy of the factory is returned, with the target configuration changed.

  3. Final uninstantiable classes for each "leaf" container and the corresponding factory interface, which define the same set of static methods as the factory interface does, all of them just delegate to the default factory instance, obtained via ServiceLoader. This default factory instance is returned by getDefaultFactory() static method in each static factory method holder class. These classes have a name of container interface plus -s suffix, for example, HashIntShortMaps define static factory methods which return HashIntShortMap instances, delegating to the default HashIntShortMapFactory implementation.

Table of equivalents of JDK collection patterns

JDK The closest equivalent from this library The recommended equivalent from this library 
 new HashMap<String, String>();
 
 HashObjObjMaps.getDefaultFactory()

     .withNullKeyAllowed(true)

     .<String, String>newMutableMap();
 
 HashObjObjMaps.<String, String>newUpdatableMap();
 
 // unclear how "capacity" (100)

 // is translated to size. 50? 75? 100?

 new HashMap<Integer, String>(100);
 
 HashIntObjMaps.<String>newMutableMap(

     (int) (100 * HashConfig.getDefault().getTargetLoad()));
 
 // 50 is expected _size_

 HashIntObjMaps.<String>newUpdatableMap(50);
 
 new IdentityHashMap<Object, Double>(map);
 
 HashObjDoubleMaps.getDefaultFactory()

     // these loads used in IdentityHashMap internally

     .withHashConfig(HashConfig.fromLoads(1./3., 2./3., 2./3.))

     .withNullKeyAllowed(true)

     .withKeyEquivalence(Equivalence.identity())

     .newMutableMap(map);
 
 HashObjDoubleMaps.getDefaultFactory()

     .withKeyEquivalence(Equivalence.identity())

     .newImmutableMap(map);
 
 Collections.unmodifiableSet(new HashSet<>() {{

     add("Summer");

     add("Autumn");

     add("Winter");

     add("Spring");

 }});
 
 HashObjSets.newImmutableSetOf("Summer", "Autumn", "Winter", "Spring");

Mutability profiles

Container factories allow to construct containers with several distinct degrees of mutability. It is useful for two main purposes: first, to defend your data from occasional (or intentional) container misuse, i. e. the same purpose for what Collections.unmodifiable* methods exist. Second, containers of lesser mutability are implemented in more efficient manner, whenever possible. So using immutable collections when applicable could improve your application's performance a bit.

Immutable

Any operations that change the conceptual container state, e. g. insertions and removals, as well as that could touch internal representation, e. g. Container.shrink(), are disallowed. Other ones are allowed.

Updatable

Everything is allowed, except removals of individual elements (entries), typically names of these operations include "remove" or "retain" verb. Emphasis on "individual" means that Container.clear() (i. e. removal all elements or entries at once) is allowed.

Think about updatable containers as "non-decreasing", which could be "reset" from time to time by calling clear().

In real practice individual removals are rarely needed, so most of the time you should use updatable containers rather than fully mutable ones. On the other hand, prohibition of removals permits faster implementation of hash containers and iterators over many data structures.

Mutable

All operations are allowed.

In Koloboke Compile, the @Updatable and @Mutable annotations specify that Koloboke Compile should generate an updatable or a mutable implementation of a container interface, respectively.

Collection mutability matrix

This matrix shows which methods in the ObjCollection, IntCollection, etc. interfaces are supported by collections with different mutability profiles.
Method \ MutabilityMutableUpdatableImmutable
size() ✓✓✓
sizeAsLong() ✓✓✓
isEmpty() ✓✓✓
contains(e) ✓✓✓
containsAll(c) ✓✓✓
toArray() ✓✓✓
toArray(array) ✓✓✓
iterator() ✓✓, except Iterator.remove()
cursor() ✓✓, except Cursor.remove()
ensureCapacity(minSize) ✓✓-
shrink() ✓✓-
clear() ✓✓-
add(e) ✓✓-
addAll(c) ✓✓-
remove(e) ✓--
removeAll(c) ✓--
retainAll(c) ✓--
removeIf(filter)✓--

Map mutability matrix

This matrix shows which methods in the ObjObjMap, ObjIntMap, LongObjMap, etc. interfaces are supported by maps with different mutability profiles.
Method \ MutabilityMutableUpdatableImmutable
size() ✓✓✓
sizeAsLong() ✓✓✓
isEmpty() ✓✓✓
containsKey(key) ✓✓✓
containsValue(value) ✓✓✓
get(key) ✓✓✓
getOrDefault(key, defaultValue) ✓✓✓
forEach(action) ✓✓✓
cursor() ✓✓, except Cursor.remove()
keySet() ✓✓, same mutability applied to the returned Set
values() ✓✓, same mutability applied to the returned Collection
entrySet() ✓✓, same mutability applied to the returned Set,
if Immutable - additionally, Map.Entry.setValue(value) not supported
ensureCapacity(minSize) ✓✓-
shrink() ✓✓-
clear() ✓✓-
put(key, value) ✓✓-
putIfAbsent(key, value) ✓✓-
computeIfAbsent(key, mappingFunction) ✓✓-
replace(key, value) ✓✓-
replace(key, oldValue, newValue) ✓✓-
putAll(m) ✓✓-
replaceAll(function) ✓✓-
compute(key, remappingFunction) ✓✓, except removing entry on returning null from the remappingFunction-
computeIfPresent(key, remappingFunction) ✓✓, except removing entry on returning null from the remappingFunction-
merge(key, value, remappingFunction) ✓✓, except removing entry on returning null from the remappingFunction-
remove(key) ✓--
remove(key, value) ✓--
removeIf(filter) ✓--

See other matrices for information if the concrete method is supported by the given mutability profile: Container.

Comparison of iteration ways

In addition to the standard way — iterators, the library supplies cursors for every container and forEach()-like methods which accept closures.
Overview comparison of the ways to iterate over containers within the library
Iterator Cursor forEach() forEachWhile() removeIf()
Available for Collection sub-interfaces in the library Yes
Available for Map sub-interfaces in the library Yes
Coding convenience High, if elements aren't removed and generic version of Iterator.next() method is used, Java "for-each" syntax is applicable. Medium otherwise. Medium Low, nasty anonymous classes declarations
Supports early break from the iteration Yes, by simple break from the loop Yes, by simple break from the loop No Yes, by returning false No
Supports remove of iterated elements (entries) Yes, by Iterator.remove() Yes, by Cursor.remove() No No Yes, by returning true
Performance, iteration over Collection High, if specialized version of Iterator.next() method is used. Medium otherwise, because every element is boxed. Very high
Performance, iteration over Map Medium, Map.Entry objects are allocated Very high

Compatibility with Java Collections Framework

All containers from the library have least possible (given initial design decisions) semantic difference with the most widely used implementation from JCF of the same parental interface. For example, HashCharSet extends java.util.Set<Character>, and made as similar as possible to java.util.HashSet<Character>, which extends the same interface. Non-obvious things, made compatible with JCF in the library:
  • Library is made forward-compatible with Java 8 and it's own version for Java 8. This means that if you run the project on Java 6 or 7 and use this library, then move to Java 8 and simultaneously change the dependency to this library from the version for Java 6 or 7 (you read documentation for this version now) to the version for Java 8, the project should compile and work without changing the code (if there are no compatibility issues related to other dependencies or JDK itself, of cause). If it doesn't compile or work, this situation is considered as a bug, please report about it.
  • Containers of objects support null elements, keys and values, despite this is an antipattern, because most JCF implementations does. Important: hash maps and sets with Object keys, e. g. HashObjDoubleMap, don't support null key by default, you should configure factory.withNullKeyAllowed(true).
  • All containers try to detect concurrent access to themselves, if at least one thread modify the container structurally, and to throw ConcurrentModificationException on best-effort basis, i. e. they have fail-fast semantics. See documentation for ConcurrentModificationException for more information.
  • Although Float.NaN != Float.NaN (similarly for Double) in Java, in this library in containers these values are treated consistently with their boxed versions (i. e. new Float(Float.NaN), all such objects are equal to each other.

Known incompatibilities

  • Collections of primitives don't support null element, key or value. Obviously, this is by design and can't be fixed.
  • Collections don't implement Cloneable yet. To be fixed, see the issue.
  • Collections don't implement Serializable yet. To be fixed, see the issue.
  • Hash sets and maps with byte, char or short keys can't be complete, i. e. contain all keys of the type, unlike HashSet<Byte>, HashSet<Character> and HashSet<Short>. There should be 1-2 absent keys. On attempt of insertion the last keys HashOverflowException is thrown.
  • It is not guaranteed that any hash set or map implementation can hold more than 250 millions of elements or entries. HashOverflowException is thrown on attempt of insertion an element or entry beyond the actual limit. java.util.HashMap and java.util.HashSet have higher limit, if there is enough heap space.

Primitive specializations naming convention

  1. The name of the specialized class is the name of the "basic" class with prefix equal to capitalized Java primitive type name of the element specialization, or key specialization type name followed value specialization type name without anything in between. Examples: CharCollection extends Collection, IntFloatMap extends Map. There are also classes with Obj- prefix, they bring API additions to collections of objects, if there are no additions for the class or interface, Obj- "specializations" are present anyway, for global API symmetry.
  2. If the specialized method has arguments of the specialized type, it has the same name as the non-specialized, thanks to Java's method overloading feature. There could be compilation issues in the client code, due to ambiguity, if there are several specialized arguments and some of them are boxed. You should "cast" them to unboxed values. For example: 
     IntIntMap map = HashIntIntMaps.newUpdatableMap();

 Integer key = 1;

 map.put(key, 2); // ambiguous method call

 map.put((int) key, 2); // correct
    There is one exception from this rule: ByteCollection.removeByte(byte) is a specialized version of Collection.remove(Object), but have a different name (the same for LongCollection, FloatCollection, etc. for symmetry). This is because remove(int) in IntCollection will conflict with List.remove(int) method in IntList (not implemented yet, however).
  3. If the specialized method doesn't have arguments of the specialized types, but return the specialized type, capitalized primitive type name, optionally preceded by -As- infix, is added to the original method name. Examples:
  4. Method DoubleCollection.toDoubleArray(), and others similar, is exceptional from those rules and have special name.

API additions beyond JCF interfaces

The library brings some extra functionality beyond implementing JCF interfaces and generating primitive specializations for each interface and method.

The concept of pluggable element (key, value) equivalences

JCF interfaces and implementations rely on Java built-in equality and hash code infrastructure: Object.equals(Object) and Object.hashCode(). Container factories in the library allow to configure equivalences for elements, keys and values. This allows to implement some functionality very easy, without defining new subclasses of the existing collections implementations. See the documentation to ObjCollection.equivalence(), ObjObjMap.keyEquivalence() and ObjObjMap.valueEquivalence() methods for more information.

Functional additions to Collection interface:

Of cause, there are appropriate specialized methods in the Collection interface primitive specializations: ByteCollection, CharCollection, etc.

Functional additions to Map interface:

Additional control over hash table behaviour

The single thing in the API of JDK hash table implementations, including HashMap, LinkedHashMap, HashSet and WeakHashMap, that allows to control it's memory footprint and performance characteristics, is loadFactor constructor argument. IdentityHashMap don't have even this one. This library allows to tune hash tables very precisely via a bunch of per-instance methods and factory configurations. See the documentation to HashContainer and HashConfig classes for more information.