See: Description
| Package | Description |
|---|---|
| it.unimi.dsi.fastutil | |
| it.unimi.dsi.fastutil.booleans |
Provides type-specific classes for boolean elements or keys.
|
| it.unimi.dsi.fastutil.bytes |
Provides type-specific classes for byte elements or keys.
|
| it.unimi.dsi.fastutil.chars |
Provides type-specific classes for character elements or keys.
|
| it.unimi.dsi.fastutil.doubles |
Provides type-specific classes for double elements or keys.
|
| it.unimi.dsi.fastutil.floats |
Provides type-specific classes for float elements or keys.
|
| it.unimi.dsi.fastutil.ints |
Provides type-specific classes for integer elements or keys.
|
| it.unimi.dsi.fastutil.io |
Provides classes and static methods that make object and primitive-type I/O easier and faster.
|
| it.unimi.dsi.fastutil.longs |
Provides type-specific classes for long elements or keys.
|
| it.unimi.dsi.fastutil.objects |
Provides type-specific classes for object elements or keys.
|
| it.unimi.dsi.fastutil.shorts |
Provides type-specific classes for short elements or keys.
|
Extends the the Java™ Collections Framework by providing type-specific maps, sets, lists and priority queues with a small memory footprint and fast access and insertion; provides also big (64-bit) arrays, sets and lists, and fast, practical I/O classes for binary and text files. It is free software distributed under the Apache License 2.0.
Warning: fastutil 6.1.0 has been significantly reorganised.
A number of not-so-useful classes (double- and sequi-indirect priority queues) are no longer
distributed (but you can still generate their sources). The old implementation of
hash tables (both sets and maps) has been replaced by a linear-probing implementation that is
about twice faster and has true deletions, but does not let you set a growth factor (again,
you can still generate their sources).
fastutil is formed by three cores:
The three cores are briefly introduced in the next sections, and then discussed at length in the rest of this overview.
fastutil specializes the most useful HashSet, HashMap, LinkedHashSet, LinkedHashMap, TreeSet, TreeMap, IdentityHashMap, ArrayList and Stack classes to versions that accept a specific kind of
key or value (e.g., integers). Besides, there are also
several types of priority
queues and a large collection of static objects and
methods (such as immutable empty containers, comparators implementing the opposite of the natural order,
iterators obtained by wrapping an array and so on.
To understand what's going on at a glance, the best thing is to look at the examples provided. If you already used the Collections Framework, everything should look rather natural. If, in particular, you use an IDE such as Eclipse, which can suggest you the method names, all you need to know is the right name for the class you need.
With fastutil 6, a new set of classes makes it possible
to handle very large collections: in particular, collections whose size exceeds
231. Big arrays
are arrays-of-arrays handled by a wealth of static methods that act on them
as if they were monodimensional arrays with 64-bit indices;
big lists provide 64-bit list access;
big hash sets provide support for sets whose
size is only limited by the amount of core memory.
The usual methods from Arrays and similar classes have
been extended to big arrays: have a look at the Javadoc documentation of
BigArrays and IntBigArrays
to get an idea of the generic and type-specific methods available.
fastutil provides replacements for some standard classes of java.io
that are plagued by a number of problems (see, e.g., FastBufferedInputStream).
The BinIO and TextIO static
containers contain dozens of methods that make it possible to load and save quickly
(big) arrays to disks, to adapt binary and text file to iterators, and so on.
All data structures in fastutil implement their standard
counterpart interface whenever possible (e.g., Map for maps). Thus, they
can be just plugged into existing code, using the standard access methods
(of course, any attempt to use the wrong type for keys or values will
produce a ClassCastException). However, they also provide
(whenever possible) many polymorphic versions of the most used methods that
avoid boxing/unboxing. In doing so, they implement more stringent interfaces that
extend and strengthen the standard ones (e.g., Int2IntSortedMap or IntListIterator).
Warning: automatic boxing and unboxing can lead you
to choose the wrong method when using fastutil. It is also extremely inefficient.
We suggest that your programming environment is set so to mark boxin/unboxing as
a warning, or even better, as an error.
Of course, the main point of type-specific data structures is that the absence of wrappers around primitive types can increase speed and reduce space occupancy by several times. The presence of generics in Java does not change this fact, since there is no genericity for primitive types.
The implementation techniques used in fastutil are quite
different than those of java.util: for instance, open-addressing
hash tables, threaded AVL trees, threaded red-black trees and exclusive-or
lists. An effort has also been made to provide powerful derived objects and
to expose them overriding covariantly return types:
for instance, the keys of sorted maps
are sorted and iterators on sorted containers are always bidirectional.
More generally, the rationale behing fastutil is that
you should never need to code explicitly natural
transformations. You do to not need to define an anonymous class to
iterate over an array of integers—just wrap it. You do not
need to write a loop to put the characters returned by an iterator into a
set—just use the right constructor. And so on.
In general, class names adhere to the general pattern
for collections, and
for maps.
By "type" here I mean a capitalized primitive type, Object or Reference. In the latter case, we
are treating objects, but their equality is established by reference
equality (that is, without invoking equals()), similarly
to IdentityHashMap. Of course, reference-based
classes are significantly faster.
Thus, an IntOpenHashSet stores
integers efficiently and implements IntSet, whereas a Long2IntAVLTreeMap does the same for maps from
longs to integers (but the map will be sorted, tree based, and balanced
using the AVL criterion), implementing Long2IntMap. If you need additional
flexibility in choosing your hash strategy, you can put, say, arrays
of integers in a ObjectOpenCustomHashSet,
maybe using the ready-made hash strategy for
arrays. A LongLinkedOpenHashSet
stores longs in a hash table, but provides a predictable iteration order
(the insertion order) and access to first/last elements of the order. A
Reference2ReferenceOpenHashMap is
similar to an IdentityHashMap. You can manage a priority
queue of characters in a heap using a CharHeapPriorityQueue, which implements CharPriorityQueue. Front-coded lists are
highly specialized immutable data structures that store compactly a large
number of arrays: if you don't know them you probably don't need them.
For a number of data structures that were not available in the
Java™ Collections Framework
when fastutil was created, an object-based version is
contained it.unimi.dsi.fastutil, and in that case the prefix
Object is not used (see, e.g., PriorityQueue).
Since there are eight primitive types in Java, and we support
reference-based containers, we get 1877 (!) classes (some nonsensical
classes, such as Boolean2BooleanAVLTreeMap, are not
generated). Many classes are generated just to mimic the hierarchy of
java.util so to redistribute common code in a similar way. There
are also several abstract classes that ease significantly the creation of
new type-specific classes by providing automatically generic methods based
on the type-specific ones.
The huge number of classes required a suitable division in subpackages
(more than anything else, to avoid crashing browsers with a preposterous
package summary). Each subpackage is characterized by the type of elements
or keys: thus, for instance, IntSet
belongs to it.unimi.dsi.fastutil.ints (the plural is required, as
int is a keyword and cannot be used in a package name), as
well as Int2ReferenceRBTreeMap. Note
that all classes for non-primitive elements and keys are gathered in it.unimi.dsi.fastutil.objects. Finally, a number of non-type-specific
classes have been gathered in it.unimi.dsi.fastutil.
The following table summarizes the available interfaces and
implementations. To get more information, you can look at a specific
implementation in it.unimi.dsi.fastutil or, for instance, it.unimi.dsi.fastutil.ints.
| Interfaces | Abstract Implementations | Implementations |
|---|---|---|
| Iterable | ||
| Collection | AbstractCollection | |
| Set | AbstractSet | OpenHashSet, OpenCustomHashSet, ArraySet, OpenHashBigSet |
| SortedSet | AbstractSortedSet | RBTreeSet, AVLTreeSet, LinkedOpenHashSet |
| Function | AbstractFunction | |
| Map | AbstractMap | OpenHashMap, OpenCustomHashMap, ArrayMap |
| SortedMap | AbstractSortedMap | RBTreeMap, AVLTreeMap, LinkedOpenHashMap |
| List, BigList† | AbstractList, AbstractBigList | ArrayList, BigArrayBigList, ArrayFrontCodedList |
| PriorityQueue† | AbstractPriorityQueue† | HeapPriorityQueue, ArrayPriorityQueue, ArrayFIFOQueue |
| IndirectPriorityQueue† | AbstractIndirectPriorityQueue† | HeapSemiIndirectPriorityQueue, HeapIndirectPriorityQueue, ArrayIndirectPriorityQueue |
| Stack† | AbstractStack† | ArrayList |
| Iterator, BigListIterator† | AbstractIterator, AbstractListIterator, AbstractBigListIterator | |
| Comparator | AbstractComparator | |
| BidirectionalIterator† | AbstractBidirectionalIterator | |
| ListIterator | AbstractListIterator | |
| Size64‡ |
†: this class has also a non-type-specific implementation in it.unimi.dsi.fastutil.
‡: this class has only a non-type-specific implementation in it.unimi.dsi.fastutil.
Note that abstract implementations are named by prefixing the interface
name with Abstract. Thus, if you want to define a
type-specific structure holding a set of integers without the hassle of
defining object-based methods, you should inherit from AbstractIntSet.
The following table summarizes static containers, which usually give rise both to a type-specific and to a generic class:
| Static Containers |
|---|
| Collections |
| Sets |
| SortedSets |
| Functions |
| Maps† |
| SortedMaps |
| Lists |
| BigLists |
| Arrays† |
| BigArrays† |
| Heaps |
| SemiIndirectHeaps |
| IndirectHeaps |
| PriorityQueues† |
| IndirectPriorityQueues† |
| Iterators |
| BigListIterators |
| Comparators |
| Hash‡ |
| HashCommon‡ |
†: this class has also a non-type-specific implementation in it.unimi.dsi.fastutil.
‡: this class has only a non-type-specific implementation in it.unimi.dsi.fastutil.
The static containers provide also special-purpose implementations for all kinds of empty structures (including arrays) and singletons.
All classes are not synchronized. If multiple threads access one of these classes concurrently, and at least one of the threads modifies it, it must be synchronized externally. Iterators will behave unpredictably in the presence of concurrent modifications. Reads, however, can be carried out concurrently.
Reference-based classes violate the Map
contract. They intentionally compare objects by reference, and do
not use the equals() method. They should be used only
when reference-based equality is desired (for instance, if all
objects involved are canonized, as it happens with interned strings).
Linked classes do not implement wholly the SortedMap interface. They provide methods to get the
first and last element in iteration order, and to start a bidirectional iterator from any element,
but any submap or subset
method will cause an UnsupportedOperationException
(this may change in future versions).
Substructures in sorted classes allow the creation of
arbitrary substructures. In java.util, instead, you
can only create contained sub-substructures (BTW, why?). For instance,
(new TreeSet()).tailSet(1).tailSet(0) will throw an exception, but (new
IntRBTreeSet()).tailSet(1).tailSet(0) won't.
Immutability is syntactically based (as opposed to
semantically based). All methods that are known not to be
causing modifications to the structure at compile time will not throw
exceptions (e.g., EMPTY_SET.clear()). All other methods will cause an UnsupportedOperationException. Note that (as of Java 5)
the situation in java.util is definitely different, and
inconsistent: for instance, in singletons add() always
throws an exception, whereas remove() does it only if the
singleton would be modified. This behaviour agrees with the interface documentation,
but it is nonetheless confusing.
The new interfaces add some very natural methods and strengthen many of
the old ones. Moreover, whenever possible, the object returned is type-specific,
or implements a more powerful interface. Before fastutil 5, the
impossibility of overriding covariantly return types made these features
accessible only by means of type casting, but fortunately this is no longer true.
More in detail:
fastutil type you
would expect (e.g., the keys of an Int2LongSortedMap are an IntSortedSet and the values are a LongCollection).
add()
method (see, e.g., Int2IntOpenHashMap.add(int,int))
that adds an increment to the current value of a key; it is
most useful to avoid the inefficient procedure of getting a value,
incrementing it and then putting it back into the map (typically, when
counting the number of occurrences of elements in a sequence).
get()
method that returns the actual object in the collection that is equal to the query key.
Int2IntLinkedOpenHashMap.putAndMoveToLast(int,int),
IntLinkedOpenHashSet.addAndMoveToLast(int)
or Int2IntLinkedOpenHashMap.removeFirstInt().
fastutil type you would expect, too.
iterator() are type-specific.
fastutil return
type-specific bidirectional
iterators. This means that you can move back and forth among
entries, keys or values.
Int2IntOpenHashMap.int2IntEntrySet());
fast entry sets can, in turn, provide a Int2IntMap.FastEntrySet.fastIterator()
that is guaranteed not to create a large number of objects, possibly by returning always the same entry (of course, mutated).
iterator(from) which creates a type-specific BidirectionalIterator starting from a given
element of the domain (not necessarily in the set). See, for instance,
IntSortedSet.iterator(int). The method is
implemented by all type-specific sorted sets and subsets.
new ObjectOpenHashSet( new String[] { "foo", "bar" } )
or just "unroll" the integers returned by an iterator into a list with
new IntArrayList( iterator )
There are a few quirks, however, that you should be aware of:
get(), put() and
remove() methods that
return a primitive type cannot, of course, rely on returning
null to denote the absence of a certain
pair. Rather, they return a default
return value, which is set to 0 cast to the
return type (false for booleans) at creation, but
can be changed using the defaultReturnValue()
method (see, e.g., Int2IntMap). Note that changing the
default return value does not change anything about the data
structure; it is just a way to return a reasonably meaningful
result—it can be changed at any time. For uniformity reasons,
even maps returning objects can use
defaultReturnValue() (of course, in this case the
default return value is initialized to null). A
submap or subset has an independent default return value (which
however is initialized to the default return value of the
originator).get() and remove() methods do not admit
polymorphic versions, as Java does not allow return-value
polymorphism. Rather, the extended interfaces introduce new
methods of the form getvaluetype() and removevaluetype(). Similar problems occur with
first(), last(),
and so on.nexttype() returning directly a primitive type.
And, of course, you have a type-specific version of previous().
Collection.toArray()
has a polymorphic version accepting a type-specific array, but there are
also explicitly typed methods
tokeytypeArray().java.util.ArrayIndexOutOfBounds exception. This does not
apply to fast iterators (see above).
rem(). At the risk of creating some confusion, remove()
reappears in the type-specific set interfaces, so the only
really unpleasant effect is that you must use
rem() on variables that are collections, but not
sets—for instance, type-specific lists.
Comparator that
require specifying both a type-specific comparison method and an object-based
one; this is necessary as a type-specific comparator must implement Comparator. However, to simplify the creation of type-specific
comparators there are abstract type-specific comparator classes that
implement an object-based comparator wrapping the (abstract)
type-specific one; thus, if you need to create a type-specific comparator
you just have to inherit from those classes and define the type-specific
method. Analogously for iterators.
Stack.
Function (and its type-specific versions) is a new
interface geared towards mathematical functions (e.g., hashes) which associates
values to keys, but in which enumerating keys or values is not possible. It is essentially
a Map that does not provide access to set representations.
fastutil
provides interfaces, abstract implementations and the usual array of wrappers
in the suitable static container (e.g., Int2IntFunctions).
Implementations will be provided by other projects (e.g., Sux4J).
All fastutil type-specific maps extend their respective type-specific
functions: but, alas, we cannot have Map extending Function.
fastutil provides a number of static methods and
singletons, much like Collections. To avoid creating
classes with hundreds of methods, there are separate containers for
sets, lists, maps and so on. Generic containers are placed in it.unimi.dsi.fastutil, whereas type-specific containers are in the
appropriate package. You should look at the documentation of the
static classes contained in it.unimi.dsi.fastutil, and in
type-specific static classes such as CharSets, Float2ByteSortedMaps, LongArrays, FloatHeaps. Presently, you can easily
obtain empty collections,
empty
type-specific collections, singletons,
synchronized versions of any type-specific container and
unmodifiable versions of containers and iterators (of course,
unmodifiable containers always return unmodifiable iterators).
On a completely different side, the type-specific static container classes for arrays provide several useful methods that allow to treat an array much like an array-based list, hiding completely the growth logic. In many cases, using this methods and an array is even simpler then using a full-blown type-specific array-based list because elements access is syntactically much simpler. The version for objects uses reflection to return arrays of the same type of the argument.
For the same reason, fastutil provides a full
implementation of methods that manipulate arrays as type-specific
heaps, semi-indirect heaps and
indirect heaps. There are
also quicksort and mergesort implementations that use arbitrary type-specific comparators.
fastutil offers also a less common choice—a very tuned
implementation of radix sort for
all primitive types. It is significantly faster than quicksort already at small sizes (say, more than 10000 elements), and should
be considered the sorting algorithm of choice if you do not need a generic comparator.
There are several variants provided. First of all you can radix sort in parallel two or even more arrays. You can also perform indirect sorts, for instance if you want to compute the sorting permutation of an array.
The sorting algorithm is a tuned radix sort adapted from Peter M. McIlroy, Keith Bostic and M. Douglas McIlroy, “Engineering radix sort”, Computing Systems, 6(1), pages 5−27 (1993), and further improved using the digit-oracle idea described by Juha Kärkkäinen and Tommi Rantala in “Engineering radix sort for strings”, String Processing and Information Retrieval, 15th International Symposium, volume 5280 of Lecture Notes in Computer Science, pages 3−14, Springer (2008). The basic algorithm is not stable, but this is immaterial for arrays of primitive types. For the indirect case, there is a parameter specifying whether the algorithm should be stable.
fastutil provides type-specific iterators and
comparators. The interface of a fastutil iterator is
slightly more powerful than that of a java.util iterator, as
it contains a skip() method that allows to skip over a list of elements (an
analogous
method is provided for bidirectional iterators). For objects (even
those managed by reference), the extended interface is named ObjectIterator; it is the return type, for
instance, of ObjectCollection.iterator().
fastutil provides also classes and methods that makes it
easy to create type-specific iterators and comparators. There are abstract versions of
each (type-specific) iterator and comparator that implement in the
obvious way some of the methods (see, e.g., AbstractIntIterator or AbstractIntComparator).
A plethora of useful static methods is also provided by various
type-specific static containers (e.g., IntIterators) and IntComparators: among other things, you can
wrap
arrays and standard iterators in type-specific iterators, generate them
giving an interval of elements to be returned, concatenate them or pour them into a set.
fastutil offers two types of queues: direct
queues and indirect queues. A direct queue offers type-specific method to enqueue and
dequeue elements. An indirect queue needs a reference array,
specified at construction time: enqueue and
dequeue operations refer to indices in the reference array. The advantage
is that it may be possible to notify the change
of any element of the reference array, or even to remove an arbitrary
element.
Queues have two implementations: a trivial array-based implementation, and a heap-based implementation. In particular, heap-based indirect queues may be fully indirect or just semi-indirect: in the latter case, there is no need for an explicit indirection array (which saves one integer per queue entry), but not all operations will be available. Note there there are also FIFO queues.
Sometimes, the behaviour of the built-in equality and hashing methods is
not what you want. In particular, this happens if you store in a hash-based
collection arrays, and you would like to compare them by equality. For this kind of applications,
fastutil provides custom hash strategies,
which define new equality and hashing methods to be used inside the collection. There are even
ready-made strategies for arrays. Note, however,
that fastutil containers do not cache hash codes, so custom hash strategies must be efficient.
fastutil provides a wide range of abstract classes, to
help in implementing its interfaces. They take care, for instance, of
providing wrappers for non-type-specific method calls, so that you have to
write just the (usually simpler) type-specific version.
With the continuous increase in core memory available, Java arrays are starting to show
their size limitation (indices cannot be larger than 231). fastutil
proposes to store big arrays using arrays-of-arrays subject to certain
size restrictions and a number of supporting static methods. Please read the documentation
of BigArrays to understand how big arrays work.
Correspondingly, fastutil proposes a new interface, called
Size64, that should be implemented by very large
collections. Size64 contains a method
Size64.size64() which returns the collection
size as a long integer.
fastutil provides big lists,
which are lists with 64-bit indices; of course, they implement Size64.
An implementation based on big arrays is provided (see, e.g., IntBigArrayBigList),
as well as static containers (see, e.g., IntBigLists).
Whereas it is unlikely that such collection will be in main memory as big arrays, there
are number of situations, such as exposing large files through a list interface or
storing a large amount of data using succinct data structures,
in which a big list interface is natural.
Unfortunately, lists and big lists,
as well as list iterators and big-list iterators,
cannot be made compatible: we thus provide adapters (see, e.g., IntBigLists.asBigList(it.unimi.dsi.fastutil.ints.IntList)).
Finally, fastutil provides big hash sets, which
are based on big arrays. They are about 30% slower than non-big sets, but their size is limited only by
the amount core memory.
fastutil includes an I/O package that provides, for instance, fast, unsynchronized
buffered input streams, fast, unsynchronized
buffered output streams, and a wealth of static methods to store and
retrieve data in textual and
binary form. The latter, in particular,
contain methods that load and store big arrays.
The main reason behind fastutil is performance, both in
time and in space. The relevant methods of type-specific hash maps and sets
are something like 2 to 10 times faster than those of the standard
classes. Note that performance of hash-based classes on object keys is
usually worse (from a few percent to doubled time) than that of
java.util, because fastutil classes do not cache hash
codes (albeit it will not be that bad if keys cache internally hash codes,
as in the case of String). Of course, you can try to get
more speed from hash tables using a small load factors: to this purpose,
alternative load factors are proposed in Hash.FAST_LOAD_FACTOR
and Hash.VERY_FAST_LOAD_FACTOR.
For tree-based classes you have two choices: AVL and red-black trees. The essential difference is that AVL trees are more balanced (their height is at most 1.44 log n), whereas red-black trees have faster deletions (but their height is at most 2 log n). So on small trees red-black trees could be faster, but on very large sets AVL trees will shine. In general, AVL trees have slightly slower updates but faster searches; however, on very large collections the smaller height may lead in fact to faster updates, too.
fastutil reduces enormously the creation and collection of
objects. First of all, if you use the polymorphic methods and iterators no
wrapper objects have to be created. Moreover, since fastutil
uses open-addressing hashing techniques, creation and garbage collection of
hash-table entries are avoided (but tables have to be rehashed whenever
they are filled beyond the load factor). The major reduction of the number
of objects around has a definite (but very difficult to measure) impact on
the whole application (as garbage collection runs proportionally to the
number of alive objects).
Maps whose iteration is very expensive in terms of object creation (e.g., hash-based classes) usually
return a type-specific FastEntrySet
whose fastIterator()
method significantly reduces object creation by returning always
the same entry object, suitably mutated.
Whenever possible, fastutil tries to gain some speed by
checking for faster interfaces: for instance, the various set-theoretic
methods addAll(), retainAll(), ecc. check whether
their arguments are type-specific and use faster iterators and accessors
accordingly.
fastutil 6.1.0 changes significantly the implementation
of hash-based classes. Instead of double hashing, we use
linear probing. This has some consequences:
The absence of wrappers makes data structures in fastutil
much smaller: even in the case of objects, however, data structures in
fastutil try to be space-efficient.
To avoid memory waste, (unlinked) hash tables in
fastutil keep no additional information about elements
(such as a list of keys). In particular, this means that enumerations
are always linear in the size of the table (rather than in the number
of keys). Usually, this would imply slower iterators. Nonetheless, the
iterator code includes a single, tight loop; moreover, it is possible
to avoid the creation of wrappers. These two facts make in practice
fastutil iterators faster than java.util's.
The memory footprint for a table of length ℓ is exactly the memory required for the related types times ℓ, plus a overhead of ℓ booleans to store the state of each entry. The absence of wrappers around primitive types can reduce space occupancy by several times (this applies even more to serialized data, e.g., when you save such a data structure in a file). These figures can greatly vary with your virtual machine, JVM versions, CPU etc.
More precisely, when you ask for a map that will hold n elements with load factor 0 < f ≤ 1, 2⌈log n / f⌉ entries are allocated. When the table is filled up beyond the load factor, it is rehashed doubling its size.
In the case of linked hash tables, there is an additional vector of 2⌈log n / f⌉ longs that is used to store link information. Each element records the next and previous element (packed together so to be more cache friendly).
The balanced trees implementation is also very parsimonious.
fastutil is based on the excellent (and unbelievably well
documented) code contained in Ben Pfaff's GNU libavl, which describes in
detail how to handle balanced trees with threads. Thus, the
overhead per entry is two pointers and one integer, which compares well to
three pointers plus one boolean of the standard tree maps. The trick is
that we use the integer bit by bit, so we consume two bits to store thread
information, plus one or two bits to handle balancing. As a result, we get
bidirectional iterators in constant space and amortized constant time
without having to store references to parent nodes.
It should be mentioned that all tree-based classes have a fixed overhead for some arrays that are used as stacks to simulate recursion; in particular, we need 48 booleans for AVL trees and 64 pointers plus 64 booleans for red-black trees.
Suppose you want to store a sorted map from longs to integers. The first step is to define a variable of the right interface, and assign it a new tree map (say, of the AVL type):
Long2IntSortedMap m = new Long2IntAVLTreeMap();
Now we can easily modify and access its content:
m.put( 1, 5 );
m.put( 2, 6 );
m.put( 3, 7 );
m.put( 1000000000L, 10 );
m.get( 1 ); // This method call will return 5
m.get( 4 ); // This method call will return 0
We can also try to change the default return value:
m.defaultReturnValue( -1 );
m.get( 4 ); // This method call will return -1
We can obtain a type-specific iterator on the key set:
LongBidirectionalIterator i = m.keySet().iterator();
// Now we sum all keys
long s = 0;
while( i.hasNext() ) s += i.nextLong();
We now generate a head map, and iterate bidirectionally over it starting from a given point:
// This map contains only keys smaller than 4
Long2IntSortedMap m1 = m.headMap( 4 );
// This iterator is positioned between 2 and 3
LongBidirectionalIterator t = m1.keySet().iterator( 2 );
t.previous(); // This method call will return 2 (t.next() would return 3)
Should we need to access the map concurrently, we can wrap it:
// This map can be safely accessed by many threads
Long2IntSortedMap m2 = Long2IntSortedMaps.synchronize( m1 );
Linked maps are very flexible data structures which can be used to implement, for instance, queues whose content can be probed efficiently:
// This map remembers insertion order (note that we are using the array-based constructor)
IntSortedSet s = new IntLinkedOpenHashSet( new int[] { 4, 3, 2, 1 } );
s.firstInt(); // This method call will return 4
s.lastInt(); // This method call will return 1
s.contains(5); // This method will return false
IntBidirectionalIterator i = s.iterator( s.lastInt() ); // We could even cast it to a list iterator
i.previous(); // This method call will return 1
i.previous(); // This method call will return 2
s.remove(s.lastInt()); // This will remove the last element in constant time
Now, we play with iterators. It is easy to create iterators over intervals or over arrays, and combine them:
IntIterator i = IntIterators.fromTo( 0, 10 ); // This iterator will return 0, 1, ..., 9
int[] a = new int[] { 5, 1, 9 };
IntIterator j = IntIterators.wrap( a ); // This iterator will return 5, 1, 9.
IntIterator k = IntIterators.concat( new IntIterator[] { i , j } ); // This iterator will return 0, 1, ..., 9, 5, 1, 9
It is easy to build sets and maps on the fly using the array-based constructors:
IntSet s = new IntOpenHashSet( new int[] { 1, 2, 3 } ); // This set will contain 1, 2, and 3
Char2IntMap m = new Char2IntRBTreeMap( new char[] { '@', '-' }, new int[] { 0, 1 } ); // This map will map '@' to 0 and '-' to 1
Whenever you have some data structure, it is easy to serialize it in an efficient (buffered) way, or to dump their content in textual form:
BinIO.storeObject( s, "foo" ); // This method call will save s in the file named "foo"
TextIO.storeInts( s.intIterator(), "foo.txt" ); // This method call will save the content of s in ASCII
i = TextIO.asIntIterator( "foo.txt" ); // This iterator will parse the file and return the integers therein