/usr/share/doc/libfastutil-java/overview-summary.html is in libfastutil-java-doc 6.5.4-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html lang="en">
<head>
<!-- Generated by javadoc (version 1.7.0_25) on Sun Jul 21 23:35:46 UTC 2013 -->
<title>Overview (fastutil 6.5.4)</title>
<meta name="date" content="2013-07-21">
<link rel="stylesheet" type="text/css" href="stylesheet.css" title="Style">
</head>
<body>
<script type="text/javascript"><!--
if (location.href.indexOf('is-external=true') == -1) {
parent.document.title="Overview (fastutil 6.5.4)";
}
//-->
</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar_top">
<!-- -->
</a><a href="#skip-navbar_top" title="Skip navigation links"></a><a name="navbar_top_firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li class="navBarCell1Rev">Overview</li>
<li>Package</li>
<li>Class</li>
<li><a href="overview-tree.html">Tree</a></li>
<li><a href="deprecated-list.html">Deprecated</a></li>
<li><a href="index-all.html">Index</a></li>
<li><a href="help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li>Prev</li>
<li>Next</li>
</ul>
<ul class="navList">
<li><a href="index.html?overview-summary.html" target="_top">Frames</a></li>
<li><a href="overview-summary.html" target="_top">No Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="allclasses-noframe.html">All Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_top");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<a name="skip-navbar_top">
<!-- -->
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<div class="header">
<div class="subTitle">
<div class="block">Extends the the <a href="http://java.sun.com/j2se/1.5/docs/guide/collections/">Java™ Collections Framework</a>
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.</div>
</div>
<p>See: <a href="#overview_description">Description</a></p>
</div>
<div class="contentContainer">
<table class="overviewSummary" border="0" cellpadding="3" cellspacing="0" summary="Packages table, listing packages, and an explanation">
<caption><span>Packages</span><span class="tabEnd"> </span></caption>
<tr>
<th class="colFirst" scope="col">Package</th>
<th class="colLast" scope="col">Description</th>
</tr>
<tbody>
<tr class="altColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/package-summary.html">it.unimi.dsi.fastutil</a></td>
<td class="colLast"> </td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/booleans/package-summary.html">it.unimi.dsi.fastutil.booleans</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for boolean elements or keys.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/bytes/package-summary.html">it.unimi.dsi.fastutil.bytes</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for byte elements or keys.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/chars/package-summary.html">it.unimi.dsi.fastutil.chars</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for character elements or keys.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/doubles/package-summary.html">it.unimi.dsi.fastutil.doubles</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for double elements or keys.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/floats/package-summary.html">it.unimi.dsi.fastutil.floats</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for float elements or keys.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/ints/package-summary.html">it.unimi.dsi.fastutil.ints</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for integer elements or keys.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/io/package-summary.html">it.unimi.dsi.fastutil.io</a></td>
<td class="colLast">
<div class="block">Provides classes and static methods that make object and primitive-type I/O easier and faster.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/longs/package-summary.html">it.unimi.dsi.fastutil.longs</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for long elements or keys.</div>
</td>
</tr>
<tr class="rowColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/objects/package-summary.html">it.unimi.dsi.fastutil.objects</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for object elements or keys.</div>
</td>
</tr>
<tr class="altColor">
<td class="colFirst"><a href="it/unimi/dsi/fastutil/shorts/package-summary.html">it.unimi.dsi.fastutil.shorts</a></td>
<td class="colLast">
<div class="block">Provides type-specific classes for short elements or keys.</div>
</td>
</tr>
</tbody>
</table>
</div>
<div class="footer"><a name="overview_description">
<!-- -->
</a>
<div class="subTitle">
<div class="block"><P>Extends the the <a href="http://java.sun.com/j2se/1.5/docs/guide/collections/">Java™ Collections Framework</a>
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 <A HREF="http://www.apache.org/licenses/LICENSE-2.0.html">Apache License 2.0</A>.
<p><strong>Warning:</strong> <code>fastutil 6.1.0</code> 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).
<h2>Package Specification</h2>
<p><code>fastutil</code> is formed by three cores:
<ul>
<li>type-specific classes that extend naturally
the <a href="http://java.sun.com/j2se/1.5/docs/guide/collections/">Java™ Collections Framework</a>;
<li>classes that support very large collections;
<li>classes for fast and practical access to binary and text files.
</ul>
<p>The three cores are briefly introduced in the next sections, and then discussed at length in the rest of this overview.
<h3>Type-specific classes</h3>
<p><code>fastutil</code> specializes the most useful <code>HashSet</code>, <code>HashMap</code>, <code>LinkedHashSet</code>, <code>LinkedHashMap</code>, <code>TreeSet</code>, <code>TreeMap</code>, <code>IdentityHashMap</code>, <code>ArrayList</code> and <code>Stack</code> classes to versions that accept a specific kind of
key or value (e.g., <a href="it/unimi/dsi/fastutil/ints/IntSet.html" title="interface in it.unimi.dsi.fastutil.ints">integers</a>). Besides, there are also
several types of <a href="it/unimi/dsi/fastutil/PriorityQueue.html" title="interface in it.unimi.dsi.fastutil">priority
queues</a> and a large collection of static objects and
methods (such as <a href="it/unimi/dsi/fastutil/objects/ObjectSets.html#EMPTY_SET">immutable empty containers</a>, <a href="it/unimi/dsi/fastutil/ints/IntComparators.html#OPPOSITE_COMPARATOR">comparators implementing the opposite of the natural order</a>,
<a href="it/unimi/dsi/fastutil/ints/IntIterators.html#wrap(int[])">iterators obtained by wrapping an array</a> and so on.</p>
<p>To understand what's going on at a glance, the best thing is to look at
the <A HREF="#example">examples</A> provided. If you already used the
Collections Framework, everything should look
rather natural. If, in particular, you use an IDE such as <A
HREF="http://www.eclipse.org/">Eclipse</A>, which can suggest you the
method names, all you need to know is <A HREF="#names">the right name for
the class you need</A>.
<h3>Support for very large collections</h3>
<p>With <code>fastutil</code> 6, a new set of classes makes it possible
to handle very large collections: in particular, collections whose size exceeds
2<sup>31</sup>. <a href="it/unimi/dsi/fastutil/BigArrays.html" title="class in it.unimi.dsi.fastutil">Big arrays</a>
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;
<a href="it/unimi/dsi/fastutil/BigList.html" title="interface in it.unimi.dsi.fastutil">big lists</a> provide 64-bit list access;
<a href="it/unimi/dsi/fastutil/ints/IntOpenHashBigSet.html" title="class in it.unimi.dsi.fastutil.ints">big hash sets</a> provide support for sets whose
size is only limited by the amount of core memory.
<p>The usual methods from <code>Arrays</code> and similar classes have
been extended to big arrays: have a look at the Javadoc documentation of
<a href="it/unimi/dsi/fastutil/BigArrays.html" title="class in it.unimi.dsi.fastutil"><code>BigArrays</code></a> and <a href="it/unimi/dsi/fastutil/ints/IntBigArrays.html" title="class in it.unimi.dsi.fastutil.ints"><code>IntBigArrays</code></a>
to get an idea of the generic and type-specific methods available.
<h3>Fast and practical I/O</h3>
<code>fastutil</code> provides replacements for some standard classes of <code>java.io</code>
that are plagued by a number of problems (see, e.g., <a href="it/unimi/dsi/fastutil/io/FastBufferedInputStream.html" title="class in it.unimi.dsi.fastutil.io"><code>FastBufferedInputStream</code></a>).
The <a href="it/unimi/dsi/fastutil/io/BinIO.html" title="class in it.unimi.dsi.fastutil.io"><code>BinIO</code></a> and <a href="it/unimi/dsi/fastutil/io/TextIO.html" title="class in it.unimi.dsi.fastutil.io"><code>TextIO</code></a> 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.
<h2>More on type-specific classes</h2>
<p>All data structures in <code>fastutil</code> implement their standard
counterpart interface whenever possible (e.g., <code>Map</code> 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 <code>ClassCastException</code>). 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., <a href="it/unimi/dsi/fastutil/ints/Int2IntSortedMap.html" title="interface in it.unimi.dsi.fastutil.ints"><code>Int2IntSortedMap</code></a> or <a href="it/unimi/dsi/fastutil/ints/IntListIterator.html" title="interface in it.unimi.dsi.fastutil.ints"><code>IntListIterator</code></a>).</p>
<p><strong>Warning</strong>: automatic boxing and unboxing can lead you
to choose the wrong method when using <code>fastutil</code>. 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.
<p>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.
<p>The implementation techniques used in <code>fastutil</code> are quite
different than those of <code>java.util</code>: 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 <a href="it/unimi/dsi/fastutil/objects/Object2IntSortedMap.html#keySet()">keys of sorted maps
are sorted</a> and iterators on sorted containers are always <a href="it/unimi/dsi/fastutil/BidirectionalIterator.html" title="interface in it.unimi.dsi.fastutil">bidirectional</a>.
<p>More generally, the rationale behing <code>fastutil</code> is that
<em>you should never need to code explicitly natural
transformations</em>. You do to not need to define an anonymous class to
iterate over an array of integers—just <a href="it/unimi/dsi/fastutil/ints/IntIterators.html#wrap(int[])">wrap it</a>. You do not
need to write a loop to put the characters returned by an iterator into a
set—just <a href="it/unimi/dsi/fastutil/chars/CharOpenHashSet.html#CharOpenHashSet(it.unimi.dsi.fastutil.chars.CharIterator)">use the right constructor</a>. And so on.
<h3><A NAME="names"></A>The Names</h3>
<p>In general, class names adhere to the general pattern</p>
<div style="padding: 1em">
<var>valuetype</var> <var>collectiontype</var>
</div>
<p>for collections, and</p>
<div style="padding: 1em">
<var>keytype</var> 2 <var>valuetype</var> <var>maptype</var>
</div>
<p>for maps.
<P>By "type" here I mean a capitalized primitive type, <code>Object</code> or <code>Reference</code>. In the latter case, we
are treating objects, but their equality is established by reference
equality (that is, without invoking <code>equals()</code>), similarly
to <code>IdentityHashMap</code>. Of course, reference-based
classes are significantly faster.</p>
<P>Thus, an <a href="it/unimi/dsi/fastutil/ints/IntOpenHashSet.html" title="class in it.unimi.dsi.fastutil.ints"><code>IntOpenHashSet</code></a> stores
integers efficiently and implements <a href="it/unimi/dsi/fastutil/ints/IntSet.html" title="interface in it.unimi.dsi.fastutil.ints"><code>IntSet</code></a>, whereas a <a href="it/unimi/dsi/fastutil/longs/Long2IntAVLTreeMap.html" title="class in it.unimi.dsi.fastutil.longs"><code>Long2IntAVLTreeMap</code></a> does the same for maps from
longs to integers (but the map will be sorted, tree based, and balanced
using the AVL criterion), implementing <a href="it/unimi/dsi/fastutil/longs/Long2IntMap.html" title="interface in it.unimi.dsi.fastutil.longs"><code>Long2IntMap</code></a>. If you need additional
flexibility in choosing your <a href="it/unimi/dsi/fastutil/Hash.Strategy.html" title="interface in it.unimi.dsi.fastutil">hash strategy</a>, you can put, say, arrays
of integers in a <a href="it/unimi/dsi/fastutil/objects/ObjectOpenCustomHashSet.html" title="class in it.unimi.dsi.fastutil.objects"><code>ObjectOpenCustomHashSet</code></a>,
maybe using the ready-made <a href="it/unimi/dsi/fastutil/ints/IntArrays.html#HASH_STRATEGY">hash strategy for
arrays</a>. A <a href="it/unimi/dsi/fastutil/longs/LongLinkedOpenHashSet.html" title="class in it.unimi.dsi.fastutil.longs"><code>LongLinkedOpenHashSet</code></a>
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
<a href="it/unimi/dsi/fastutil/objects/Reference2ReferenceOpenHashMap.html" title="class in it.unimi.dsi.fastutil.objects"><code>Reference2ReferenceOpenHashMap</code></a> is
similar to an <code>IdentityHashMap</code>. You can manage a priority
queue of characters in a heap using a <a href="it/unimi/dsi/fastutil/chars/CharHeapPriorityQueue.html" title="class in it.unimi.dsi.fastutil.chars"><code>CharHeapPriorityQueue</code></a>, which implements <a href="it/unimi/dsi/fastutil/chars/CharPriorityQueue.html" title="interface in it.unimi.dsi.fastutil.chars"><code>CharPriorityQueue</code></a>. <a href="it/unimi/dsi/fastutil/bytes/ByteArrayFrontCodedList.html" title="class in it.unimi.dsi.fastutil.bytes">Front-coded lists</a> 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.
<p>For a number of data structures that were not available in the
<a href="http://java.sun.com/j2se/1.5/docs/guide/collections/">Java™ Collections Framework</a>
when <code>fastutil</code> was created, an object-based version is
contained <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>, and in that case the prefix
<code>Object</code> is not used (see, e.g., <a href="it/unimi/dsi/fastutil/PriorityQueue.html" title="interface in it.unimi.dsi.fastutil"><code>PriorityQueue</code></a>).
<p>Since there are eight primitive types in Java, and we support
reference-based containers, we get 1877 (!) classes (some nonsensical
classes, such as <code>Boolean2BooleanAVLTreeMap</code>, are not
generated). Many classes are generated just to mimic the hierarchy of
<code>java.util</code> 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.</p>
<p>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, <a href="it/unimi/dsi/fastutil/ints/IntSet.html" title="interface in it.unimi.dsi.fastutil.ints"><code>IntSet</code></a>
belongs to <a href="it/unimi/dsi/fastutil/ints/package-summary.html"><code>it.unimi.dsi.fastutil.ints</code></a> (the plural is required, as
<code>int</code> is a keyword and cannot be used in a package name), as
well as <a href="it/unimi/dsi/fastutil/ints/Int2ReferenceRBTreeMap.html" title="class in it.unimi.dsi.fastutil.ints"><code>Int2ReferenceRBTreeMap</code></a>. Note
that all classes for non-primitive elements and keys are gathered in <a href="it/unimi/dsi/fastutil/objects/package-summary.html"><code>it.unimi.dsi.fastutil.objects</code></a>. Finally, a number of non-type-specific
classes have been gathered in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>.
<h3>An In–Depth Look</h3>
<P>The following table summarizes the available interfaces and
implementations. To get more information, you can look at a specific
implementation in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a> or, for instance, <a href="it/unimi/dsi/fastutil/ints/package-summary.html"><code>it.unimi.dsi.fastutil.ints</code></a>.
<div align=center>
<table border=1 summary="Interfaces and Abstract Implementations" title="Interfaces and Abstract Implementations">
<tr><th>Interfaces<th>Abstract Implementations<th>Implementations
<tr><td>Iterable
<tr><td>Collection<td>AbstractCollection
<tr><td>Set<td>AbstractSet<td>OpenHashSet, OpenCustomHashSet, ArraySet, OpenHashBigSet
<tr><td>SortedSet<td>AbstractSortedSet<td>RBTreeSet, AVLTreeSet, LinkedOpenHashSet
<tr><td>Function<td>AbstractFunction<td>
<tr><td>Map<td>AbstractMap<td>OpenHashMap, OpenCustomHashMap, ArrayMap
<tr><td>SortedMap<td>AbstractSortedMap<td>RBTreeMap, AVLTreeMap, LinkedOpenHashMap
<tr><td>List, BigList†<td>AbstractList, AbstractBigList<td>ArrayList, BigArrayBigList, ArrayFrontCodedList
<tr><td>PriorityQueue†<td>AbstractPriorityQueue†<td>HeapPriorityQueue, ArrayPriorityQueue, ArrayFIFOQueue
<tr><td>IndirectPriorityQueue†<td>AbstractIndirectPriorityQueue†<td>HeapSemiIndirectPriorityQueue, HeapIndirectPriorityQueue, ArrayIndirectPriorityQueue
<tr><td>Stack†<td>AbstractStack†<td>ArrayList
<tr><td>Iterator, BigListIterator†<td>AbstractIterator, AbstractListIterator, AbstractBigListIterator
<tr><td>Comparator<td>AbstractComparator
<tr><td>BidirectionalIterator†<td>AbstractBidirectionalIterator
<tr><td>ListIterator<td>AbstractListIterator
<tr><td>Size64‡
</table>
</div>
<P>†: this class has also a non-type-specific implementation in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>.
<P>‡: this class has <em>only</em> a non-type-specific implementation in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>.
<P>Note that abstract implementations are named by prefixing the interface
name with <samp>Abstract</samp>. 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 <a href="it/unimi/dsi/fastutil/ints/AbstractIntSet.html" title="class in it.unimi.dsi.fastutil.ints"><code>AbstractIntSet</code></a>.
<P>The following table summarizes static containers, which usually give rise
both to a type-specific and to a generic class:
<div align=center>
<table border=1 style="border: solid thin black" title="Static Containers" summary="Static Containers">
<tr><th>Static Containers
<tr><td>Collections
<tr><td>Sets
<tr><td>SortedSets
<tr><td>Functions
<tr><td>Maps†
<tr><td>SortedMaps
<tr><td>Lists
<tr><td>BigLists
<tr><td>Arrays†
<tr><td>BigArrays†
<tr><td>Heaps
<tr><td>SemiIndirectHeaps
<tr><td>IndirectHeaps
<tr><td>PriorityQueues†
<tr><td>IndirectPriorityQueues†
<tr><td>Iterators
<tr><td>BigListIterators
<tr><td>Comparators
<tr><td>Hash‡
<tr><td>HashCommon‡
</table>
</div>
<P>†: this class has also a non-type-specific implementation in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>.
<P>‡: this class has <em>only</em> a non-type-specific implementation in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>.
<P>The static containers provide also special-purpose implementations for
all kinds of <a href="it/unimi/dsi/fastutil/objects/ObjectSets.html#EMPTY_SET">empty
structures</a> (including <a href="it/unimi/dsi/fastutil/objects/ObjectArrays.html#EMPTY_ARRAY">arrays</a>) and
<a href="it/unimi/dsi/fastutil/ints/Int2IntMaps.html#singleton(int, int)">singletons</a>.
<h3>Warnings</h3>
<p><strong>All classes are not synchronized</strong>. 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.
<p><strong>Reference-based classes violate the <code>Map</code>
contract</strong>. They intentionally compare objects by reference, and do
not use the <code>equals()</code> 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).
<p><strong>Linked classes do not implement wholly the <code>SortedMap</code> interface</strong>. 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 <code>UnsupportedOperationException</code>
(this may change in future versions).
<p><strong>Substructures in sorted classes allow the creation of
arbitrary substructures</strong>. In <code>java.util</code>, instead, you
can only create contained sub-substructures (BTW, why?). For instance,
<code>(new TreeSet()).tailSet(1).tailSet(0)</code> will throw an exception, but <a href="it/unimi/dsi/fastutil/ints/IntRBTreeSet.html" title="class in it.unimi.dsi.fastutil.ints"><code>(new
IntRBTreeSet()).tailSet(1).tailSet(0)</code></a> won't.
<p><strong>Immutability is syntactically based (as opposed to
semantically based)</strong>. All methods that are known not to be
causing modifications to the structure at compile time will not throw
exceptions (e.g., <a href="it/unimi/dsi/fastutil/objects/ObjectSets.html#EMPTY_SET"><code>EMPTY_SET.clear()</code></a>). All other methods will cause an <code>UnsupportedOperationException</code>. Note that (as of Java 5)
the situation in <code>java.util</code> is definitely different, and
inconsistent: for instance, in singletons <code>add()</code> always
throws an exception, whereas <code>remove()</code> does it only if the
singleton would be modified. This behaviour agrees with the interface documentation,
but it is nonetheless confusing.
<h3>Additional Features and Methods</h3>
<p>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 <code>fastutil</code> 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.
<P>More in detail:
<UL>
<LI>Keys and values of a map are of the <code>fastutil</code> type you
would expect (e.g., the keys of an <a href="it/unimi/dsi/fastutil/ints/Int2LongSortedMap.html" title="interface in it.unimi.dsi.fastutil.ints"><code>Int2LongSortedMap</code></a> are an <a href="it/unimi/dsi/fastutil/ints/IntSortedSet.html" title="interface in it.unimi.dsi.fastutil.ints"><code>IntSortedSet</code></a> and the values are a <a href="it/unimi/dsi/fastutil/longs/LongCollection.html" title="interface in it.unimi.dsi.fastutil.longs"><code>LongCollection</code></a>).
<LI>Hash-based maps that return primitive numeric values have an <code>add()</code>
method (see, e.g., <a href="it/unimi/dsi/fastutil/ints/Int2IntOpenHashMap.html#add(int, int)"><code>Int2IntOpenHashMap.add(int,int)</code></a>)
that <em>adds</em> 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).
<li>Hash-set implementations have an additional <a href="it/unimi/dsi/fastutil/objects/ObjectOpenHashSet.html#get(java.lang.Object)"><code>get()</code></a>
method that returns the actual object in the collection that is equal to the query key.
<LI>Linked hash-based maps and sets have a wealth of additional methods that make it easy
to use them as caches. See, for instance, <a href="it/unimi/dsi/fastutil/ints/Int2IntLinkedOpenHashMap.html#putAndMoveToLast(int, int)"><code>Int2IntLinkedOpenHashMap.putAndMoveToLast(int,int)</code></a>,
<a href="it/unimi/dsi/fastutil/ints/IntLinkedOpenHashSet.html#addAndMoveToLast(int)"><code>IntLinkedOpenHashSet.addAndMoveToLast(int)</code></a>
or <a href="it/unimi/dsi/fastutil/ints/Int2IntLinkedOpenHashMap.html#removeFirstInt()"><code>Int2IntLinkedOpenHashMap.removeFirstInt()</code></a>.
<LI>Submaps of a sorted map and subsets of a sorted sets are of the
<code>fastutil</code> type you would expect, too.
<LI>Iterators returned by <code>iterator()</code> are type-specific.
<LI>Sorted structures in <code>fastutil</code> return
type-specific <a href="it/unimi/dsi/fastutil/BidirectionalIterator.html" title="interface in it.unimi.dsi.fastutil">bidirectional
iterators</a>. This means that you can move back and forth among
entries, keys or values.
<li>Some classes for maps (check the specification) return a <em>fast entry set</em>
(see, e.g., <a href="it/unimi/dsi/fastutil/ints/Int2IntOpenHashMap.html#int2IntEntrySet()"><code>Int2IntOpenHashMap.int2IntEntrySet()</code></a>);
fast entry sets can, in turn, provide a <em><a href="it/unimi/dsi/fastutil/ints/Int2IntMap.FastEntrySet.html#fastIterator()">Int2IntMap.FastEntrySet.fastIterator()</a></em>
that is guaranteed not to create a large number of objects, <em>possibly by returning always the same entry</em> (of course, mutated).
<LI>The type-specific sorted set interfaces, moreover, feature an optional
method <code>iterator(from)</code> which creates a type-specific <a href="it/unimi/dsi/fastutil/BidirectionalIterator.html" title="interface in it.unimi.dsi.fastutil"><code>BidirectionalIterator</code></a> starting from a given
element of the domain (not necessarily in the set). See, for instance,
<a href="it/unimi/dsi/fastutil/ints/IntSortedSet.html#iterator(int)"><code>IntSortedSet.iterator(int)</code></a>. The method is
implemented by all type-specific sorted sets and subsets.
<LI>Finally, there are constructors that allow you to build easily sets
using array and iterators. This means, for instance, that you can create quickly a
set of strings with a statement like
<blockquote>
<code>new ObjectOpenHashSet( new String[] { "foo", "bar" } )</code>
</blockquote>
or just "unroll" the integers returned by an iterator into a list with
<blockquote>
<code>new IntArrayList( iterator )</code>
</blockquote>
</UL>
<P>There are a few quirks, however, that you should be aware of:
<ul>
<li>The versions of the <code>get()</code>, <code>put()</code> and
<code>remove()</code> methods that
return a primitive type cannot, of course, rely on returning
<code>null</code> to denote the absence of a certain
pair. Rather, they return a <em><a href="it/unimi/dsi/fastutil/ints/Int2LongFunction.html#defaultReturnValue(long)">default
return value</a></em>, which is set to 0 cast to the
return type (<code>false</code> for booleans) at creation, but
can be changed using the <code>defaultReturnValue()</code>
method (see, e.g., <a href="it/unimi/dsi/fastutil/ints/Int2IntMap.html" title="interface in it.unimi.dsi.fastutil.ints"><code>Int2IntMap</code></a>). 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
<code>defaultReturnValue()</code> (of course, in this case the
default return value is initialized to <code>null</code>). A
submap or subset has an independent default return value (which
however is initialized to the default return value of the
originator).</li>
<li>For all maps that have objects as keys, the <code>get()</code> and <code>remove()</code> methods do not admit
polymorphic versions, as Java does not allow return-value
polymorphism. Rather, the extended interfaces introduce new
methods of the form <a href="it/unimi/dsi/fastutil/objects/Object2IntOpenHashMap.html#getInt(java.lang.Object)"><code>get<var>valuetype</var>()</code></a> and <a href="it/unimi/dsi/fastutil/objects/Object2IntOpenHashMap.html#removeInt(java.lang.Object)"><code>remove<var>valuetype</var>()</code></a>. Similar problems occur with
<a href="it/unimi/dsi/fastutil/chars/CharSortedSet.html#firstChar()"><code>first()</code></a>, <a href="it/unimi/dsi/fastutil/chars/CharSortedSet.html#lastChar()"><code>last()</code></a>,
and so on.</li>
<LI>Similarly, all iterators have a suitable method <a href="it/unimi/dsi/fastutil/ints/IntIterator.html#nextInt()"><code>next<var>type</var>()</code></a> returning directly a primitive type.
And, of course, you have a type-specific version of <code>previous()</code>.
<li>For the same reason, the method <code>Collection.toArray()</code>
has a polymorphic version accepting a type-specific array, but there are
also explicitly typed methods
<a href="it/unimi/dsi/fastutil/bytes/ByteCollection.html#toByteArray()"><code>to<var>keytype</var>Array()</code></a>.</li>
<li>The standard entry-set iterators for hash-based maps use an entry object
that refers to the data contained in the hash table. If you retrieve an
entry and deleted it, the entry object will become invalid and will throw
an <code>java.util.ArrayIndexOutOfBounds</code> exception. This does not
apply to fast iterators (see above).
<li>A name clash between the list and collection interfaces
forces the deletion method of an collection to be named <a href="it/unimi/dsi/fastutil/doubles/DoubleCollection.html#rem(double)"><code>rem()</code></a>. At the risk of creating some confusion, <a href="it/unimi/dsi/fastutil/doubles/DoubleSet.html#remove(double)"><code>remove()</code></a>
reappears in the type-specific set interfaces, so the only
really unpleasant effect is that you must use
<code>rem()</code> on variables that are collections, but not
sets—for instance, <a href="it/unimi/dsi/fastutil/ints/IntList.html" title="interface in it.unimi.dsi.fastutil.ints">type-specific lists</a>.
<li>There are type-specific versions of <code>Comparator</code> that
require specifying both a type-specific comparison method and an object-based
one; this is necessary as a type-specific comparator must implement <code>Comparator</code>. 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.
<li>Stacks are <em>interfaces</em> implemented by array-based
lists: the interface, moreover, is slightly different from the
implementation contained in <code>Stack</code>.
</ul>
<h3>Functions</h3>
<a href="it/unimi/dsi/fastutil/Function.html" title="interface in it.unimi.dsi.fastutil"><code>Function</code></a> (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 <code>Map</code> that does not provide access to set representations.
<p><code>fastutil</code>
provides interfaces, abstract implementations and the usual array of wrappers
in the suitable static container (e.g., <a href="it/unimi/dsi/fastutil/ints/Int2IntFunctions.html" title="class in it.unimi.dsi.fastutil.ints"><code>Int2IntFunctions</code></a>).
Implementations will be provided by other projects (e.g., <a href="http://sux.dsi.unimi.it/">Sux4J</a>).
<p>All <code>fastutil</code> type-specific maps extend their respective type-specific
functions: but, alas, we cannot have <code>Map</code> extending <a href="it/unimi/dsi/fastutil/Function.html" title="interface in it.unimi.dsi.fastutil"><code>Function</code></a>.
<h3>Static Container Classes</h3>
<P><code>fastutil</code> provides a number of static methods and
singletons, much like <code>Collections</code>. To avoid creating
classes with hundreds of methods, there are separate containers for
sets, lists, maps and so on. Generic containers are placed in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>, whereas type-specific containers are in the
appropriate package. You should look at the documentation of the
static classes contained in <a href="it/unimi/dsi/fastutil/package-summary.html"><code>it.unimi.dsi.fastutil</code></a>, and in
type-specific static classes such as <a href="it/unimi/dsi/fastutil/chars/CharSets.html" title="class in it.unimi.dsi.fastutil.chars"><code>CharSets</code></a>, <a href="it/unimi/dsi/fastutil/floats/Float2ByteSortedMaps.html" title="class in it.unimi.dsi.fastutil.floats"><code>Float2ByteSortedMaps</code></a>, <a href="it/unimi/dsi/fastutil/longs/LongArrays.html" title="class in it.unimi.dsi.fastutil.longs"><code>LongArrays</code></a>, <a href="it/unimi/dsi/fastutil/floats/FloatHeaps.html" title="class in it.unimi.dsi.fastutil.floats"><code>FloatHeaps</code></a>. Presently, you can easily
obtain <a href="it/unimi/dsi/fastutil/objects/ObjectSets.html#EMPTY_SET">empty collections</a>,
<a href="it/unimi/dsi/fastutil/longs/Long2IntMaps.html#EMPTY_MAP">empty
type-specific collections</a>, <a href="it/unimi/dsi/fastutil/ints/IntLists.html#singleton(int)">singletons</a>,
<a href="it/unimi/dsi/fastutil/objects/Object2ReferenceSortedMaps.html#synchronize(it.unimi.dsi.fastutil.objects.Object2ReferenceSortedMap)">synchronized versions</a> of any type-specific container and
unmodifiable versions of <a href="it/unimi/dsi/fastutil/objects/ObjectLists.html#unmodifiable(it.unimi.dsi.fastutil.objects.ObjectList)">containers</a> and <a href="it/unimi/dsi/fastutil/ints/IntIterators.html#unmodifiable(it.unimi.dsi.fastutil.ints.IntBidirectionalIterator)">iterators</a> (of course,
unmodifiable containers always return unmodifiable iterators).
<P>On a completely different side, the <a href="it/unimi/dsi/fastutil/ints/IntArrays.html" title="class in it.unimi.dsi.fastutil.ints">type-specific static container
classes for arrays</a> 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 <a href="it/unimi/dsi/fastutil/doubles/DoubleArrayList.html" title="class in it.unimi.dsi.fastutil.doubles">type-specific
array-based list</a> because elements access is syntactically much
simpler. The version for objects uses reflection to return arrays of
the same type of the argument.
<P>For the same reason, <code>fastutil</code> provides a full
implementation of methods that manipulate arrays as type-specific
<a href="it/unimi/dsi/fastutil/ints/IntHeaps.html" title="class in it.unimi.dsi.fastutil.ints">heaps</a>, <a href="it/unimi/dsi/fastutil/ints/IntSemiIndirectHeaps.html" title="class in it.unimi.dsi.fastutil.ints">semi-indirect heaps</a> and
<a href="it/unimi/dsi/fastutil/ints/IntIndirectHeaps.html" title="class in it.unimi.dsi.fastutil.ints">indirect heaps</a>. There are
also quicksort and mergesort implementations that use arbitrary type-specific comparators.
<p><code>fastutil</code> offers also a less common choice—a very tuned
implementation of <a href="it/unimi/dsi/fastutil/ints/IntArrays.html#radixSort(int[], int, int)">radix sort</a> 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.
<p>There are several variants provided. First of all you can radix sort in parallel
<a href="it/unimi/dsi/fastutil/ints/IntArrays.html#radixSort(int[], int[], int, int)">two</a> or
<a href="it/unimi/dsi/fastutil/ints/IntArrays.html#radixSort(int[][], int, int)">even more</a> arrays. You
can also perform <a href="it/unimi/dsi/fastutil/ints/IntArrays.html#radixSortIndirect(int[], int[], int, int, boolean)">indirect</a> sorts,
for instance if you want to compute the sorting permutation of an array.
<p>The sorting algorithm is a tuned radix sort adapted from Peter M. McIlroy, Keith Bostic and M. Douglas
McIlroy, “Engineering radix sort”, <i>Computing Systems</i>, 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”,
<i>String Processing and Information Retrieval, 15th International Symposium</i>, 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.
<h3>Iterators and Comparators</h3>
<P><code>fastutil</code> provides type-specific iterators and
comparators. The interface of a <code>fastutil</code> iterator is
slightly more powerful than that of a <code>java.util</code> iterator, as
it contains a <a href="it/unimi/dsi/fastutil/objects/ObjectIterator.html#skip(int)"><code>skip()</code></a> method that allows to skip over a list of elements (an
<a href="it/unimi/dsi/fastutil/objects/ObjectBidirectionalIterator.html#back(int)">analogous
method</a> is provided for bidirectional iterators). For objects (even
those managed by reference), the extended interface is named <a href="it/unimi/dsi/fastutil/objects/ObjectIterator.html" title="interface in it.unimi.dsi.fastutil.objects"><code>ObjectIterator</code></a>; it is the return type, for
instance, of <a href="it/unimi/dsi/fastutil/objects/ObjectCollection.html#iterator()"><code>ObjectCollection.iterator()</code></a>.
<code>fastutil</code> 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., <a href="it/unimi/dsi/fastutil/ints/AbstractIntIterator.html" title="class in it.unimi.dsi.fastutil.ints"><code>AbstractIntIterator</code></a> or <a href="it/unimi/dsi/fastutil/ints/AbstractIntComparator.html" title="class in it.unimi.dsi.fastutil.ints"><code>AbstractIntComparator</code></a>).
<P>A plethora of useful static methods is also provided by various
type-specific static containers (e.g., <a href="it/unimi/dsi/fastutil/ints/IntIterators.html" title="class in it.unimi.dsi.fastutil.ints"><code>IntIterators</code></a>) and <a href="it/unimi/dsi/fastutil/ints/IntComparators.html" title="class in it.unimi.dsi.fastutil.ints"><code>IntComparators</code></a>: among other things, you can
<a href="it/unimi/dsi/fastutil/ints/IntIterators.html#wrap(int[])">wrap
arrays</a> and <a href="it/unimi/dsi/fastutil/ints/IntIterators.html#asIntIterator(java.util.Iterator)">standard iterators</a> in type-specific iterators, <a href="it/unimi/dsi/fastutil/ints/IntIterators.html#fromTo(int, int)">generate them</a>
giving an interval of elements to be returned, <a href="it/unimi/dsi/fastutil/objects/ObjectIterators.html#concat(it.unimi.dsi.fastutil.objects.ObjectIterator[])">concatenate them</a> or <a href="it/unimi/dsi/fastutil/objects/ObjectIterators.html#pour(java.util.Iterator, it.unimi.dsi.fastutil.objects.ObjectCollection)">pour them</a> into a set.
<h3>Queues</h3>
<P><code>fastutil</code> offers two types of queues: <em>direct
queues</em> and <em>indirect queues</em>. A direct queue offers type-specific method to <a href="it/unimi/dsi/fastutil/longs/LongPriorityQueue.html#enqueue(long)">enqueue</a> and
<a href="it/unimi/dsi/fastutil/longs/LongPriorityQueue.html#dequeueLong()">dequeue</a> elements. An indirect queue needs a <em>reference array</em>,
specified at construction time: <a href="it/unimi/dsi/fastutil/IndirectPriorityQueue.html#enqueue(int)">enqueue</a> and
<a href="it/unimi/dsi/fastutil/IndirectPriorityQueue.html#dequeue()">dequeue</a> operations refer to indices in the reference array. The advantage
is that it may be possible to <a href="it/unimi/dsi/fastutil/IndirectPriorityQueue.html#changed(int)">notify the change</a>
of any element of the reference array, or even to <a href="it/unimi/dsi/fastutil/IndirectPriorityQueue.html#remove(int)">remove an arbitrary
element</a>.
<P>Queues have two implementations: a trivial array-based
implementation, and a heap-based implementation. In particular, heap-based
indirect queues may be <a href="it/unimi/dsi/fastutil/objects/ObjectHeapIndirectPriorityQueue.html" title="class in it.unimi.dsi.fastutil.objects">fully
indirect</a> or just <a href="it/unimi/dsi/fastutil/objects/ObjectHeapSemiIndirectPriorityQueue.html" title="class in it.unimi.dsi.fastutil.objects">semi-indirect</a>: 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
<a href="it/unimi/dsi/fastutil/ints/IntArrayFIFOQueue.html" title="class in it.unimi.dsi.fastutil.ints">FIFO queues</a>.
<h3>Custom Hashing</h3>
<P>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,
<code>fastutil</code> provides <a href="it/unimi/dsi/fastutil/Hash.Strategy.html" title="interface in it.unimi.dsi.fastutil">custom hash strategies</a>,
which define new equality and hashing methods to be used inside the collection. There are even
<a href="it/unimi/dsi/fastutil/ints/IntArrays.html#HASH_STRATEGY">ready-made strategies</a> for arrays. Note, however,
that <code>fastutil</code> containers do not cache hash codes, so custom hash strategies must be efficient.
<h3>Abstract Classes</h3>
<p><code>fastutil</code> 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.
<h2>More on the support for very large collections</h2>
<p>With the continuous increase in core memory available, Java arrays are starting to show
their size limitation (indices cannot be larger than 2<sup>31</sup>). <code>fastutil</code>
proposes to store <em>big arrays</em> using arrays-of-arrays subject to certain
size restrictions and a number of supporting static methods. Please read the documentation
of <a href="it/unimi/dsi/fastutil/BigArrays.html" title="class in it.unimi.dsi.fastutil"><code>BigArrays</code></a> to understand how big arrays work.
<p>Correspondingly, <code>fastutil</code> proposes a new interface, called
<a href="it/unimi/dsi/fastutil/Size64.html" title="interface in it.unimi.dsi.fastutil"><code>Size64</code></a>, that should be implemented by very large
collections. <a href="it/unimi/dsi/fastutil/Size64.html" title="interface in it.unimi.dsi.fastutil"><code>Size64</code></a> contains a method
<a href="it/unimi/dsi/fastutil/Size64.html#size64()"><code>Size64.size64()</code></a> which returns the collection
size as a long integer.
<p><code>fastutil</code> provides <a href="it/unimi/dsi/fastutil/BigList.html" title="interface in it.unimi.dsi.fastutil">big lists</a>,
which are lists with 64-bit indices; of course, they implement <a href="it/unimi/dsi/fastutil/Size64.html" title="interface in it.unimi.dsi.fastutil"><code>Size64</code></a>.
An implementation based on big arrays is provided (see, e.g., <a href="it/unimi/dsi/fastutil/ints/IntBigArrayBigList.html" title="class in it.unimi.dsi.fastutil.ints"><code>IntBigArrayBigList</code></a>),
as well as static containers (see, e.g., <a href="it/unimi/dsi/fastutil/ints/IntBigLists.html" title="class in it.unimi.dsi.fastutil.ints"><code>IntBigLists</code></a>).
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 <a href="http://sux4j.dsi.unimi.it/">succinct data structures</a>,
in which a big list interface is natural.
<p>Unfortunately, lists and <a href="it/unimi/dsi/fastutil/BigList.html" title="interface in it.unimi.dsi.fastutil">big lists</a>,
as well as list iterators and <a href="it/unimi/dsi/fastutil/BigListIterator.html" title="interface in it.unimi.dsi.fastutil">big-list iterators</a>,
cannot be made compatible: we thus provide adapters (see, e.g., <a href="it/unimi/dsi/fastutil/ints/IntBigLists.html#asBigList(it.unimi.dsi.fastutil.ints.IntList)"><code>IntBigLists.asBigList(it.unimi.dsi.fastutil.ints.IntList)</code></a>).
<p>Finally, <code>fastutil</code> provides <a href="it/unimi/dsi/fastutil/longs/LongOpenHashBigSet.html" title="class in it.unimi.dsi.fastutil.longs">big hash sets</a>, 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.
<h2>More on fast and practical I/O</h2>
<P><code>fastutil</code> includes an <a href="it/unimi/dsi/fastutil/io/package-summary.html">I/O package</a> that provides, for instance, <a href="it/unimi/dsi/fastutil/io/FastBufferedInputStream.html" title="class in it.unimi.dsi.fastutil.io">fast, unsynchronized
buffered input streams</a>, <a href="it/unimi/dsi/fastutil/io/FastBufferedOutputStream.html" title="class in it.unimi.dsi.fastutil.io">fast, unsynchronized
buffered output streams</a>, and a wealth of static methods to store and
retrieve data in <a href="it/unimi/dsi/fastutil/io/TextIO.html" title="class in it.unimi.dsi.fastutil.io">textual</a> and
<a href="it/unimi/dsi/fastutil/io/BinIO.html" title="class in it.unimi.dsi.fastutil.io">binary</a> form. The latter, in particular,
contain methods that load and store big arrays.
<h2>Performance</h2>
<p>The main reason behind <code>fastutil</code> 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 <em>worse</em> (from a few percent to doubled time) than that of
<code>java.util</code>, because <code>fastutil</code> classes do not cache hash
codes (albeit it will not be that bad if keys cache internally hash codes,
as in the case of <code>String</code>). 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 <a href="it/unimi/dsi/fastutil/Hash.html#FAST_LOAD_FACTOR"><code>Hash.FAST_LOAD_FACTOR</code></a>
and <a href="it/unimi/dsi/fastutil/Hash.html#VERY_FAST_LOAD_FACTOR"><code>Hash.VERY_FAST_LOAD_FACTOR</code></a>.
<p>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 <var>n</var>), whereas red-black trees have
faster deletions (but their height is at most 2 log <var>n</var>). 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.
<p><code>fastutil</code> 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 <code>fastutil</code>
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).
<p>Maps whose iteration is very expensive in terms of object creation (e.g., hash-based classes) usually
return a type-specific <a href="it/unimi/dsi/fastutil/ints/Int2IntMap.FastEntrySet.html" title="interface in it.unimi.dsi.fastutil.ints"><code>FastEntrySet</code></a>
whose <a href="it/unimi/dsi/fastutil/ints/Int2IntMap.FastEntrySet.html#fastIterator()"><code>fastIterator()</code></a>
method significantly reduces object creation by returning always
the same entry object, suitably mutated.
<p>Whenever possible, <code>fastutil</code> tries to gain some speed by
checking for faster interfaces: for instance, the various set-theoretic
methods <code>addAll()</code>, <code>retainAll()</code>, ecc. check whether
their arguments are type-specific and use faster iterators and accessors
accordingly.
<h3>Faster Hash Tables</h3>
<p><code>fastutil</code> 6.1.0 changes significantly the implementation
of hash-based classes. Instead of <em>double hashing</em>, we use
<em>linear probing</em>. This has some consequences:
<ul>
<li>the classes are now about two times faster;
<li>deletions are effective—there is no “marking” of
deleted entries (the claim that this was impossible with open
addressing was, of course, wrong);
<li>given a size and a load factor, the backing array of a table will
be in general larger (in the worst case about two times larger);
<li>it is no longer possible to set the <em>growth factor</em> of the table, which
is fixed at 2 (the old methods to control the growth factor <a href="it/unimi/dsi/fastutil/ints/Int2IntOpenHashMap.html#growthFactor(int)">are now no-ops</a>—they
are kept just for backward compatibility);
<li>there are efficient implementations of <a href="it/unimi/dsi/fastutil/ints/IntOpenHashBigSet.html" title="class in it.unimi.dsi.fastutil.ints">big sets</a>.
</ul>
<h3>Memory Usage</h3>
<P>The absence of wrappers makes data structures in <code>fastutil</code>
much smaller: even in the case of objects, however, data structures in
<code>fastutil</code> try to be space-efficient.
<h4>Hash Tables</h4>
<p>To avoid memory waste, (unlinked) hash tables in
<code>fastutil</code> 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
<code>fastutil</code> iterators <em>faster</em> than <code>java.util</code>'s.
<p>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.
<p>More precisely, when you ask for a map that will hold <var>n</var>
elements with load factor 0 < <var>f</var> ≤ 1,
2<sup>⌈log <var>n</var> / <var>f</var>⌉</sup>
entries are allocated. When the table is filled up beyond the load factor, it is rehashed
doubling its size.
<p>In the case of linked hash tables, there is an additional vector of
2<sup>⌈log <var>n</var> / <var>f</var>⌉</sup> longs that is used to store link information. Each
element records the next and previous element (packed together so to be more cache friendly).
<h4>Balanced Trees</h4>
<p>The balanced trees implementation is also very parsimonious.
<code>fastutil</code> is based on the excellent (and unbelievably well
documented) code contained in Ben Pfaff's <A
HREF="http://www.msu.edu/~pfaffben/avl/">GNU libavl</A>, which describes in
detail how to handle balanced trees with <em>threads</em>. 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.
<P>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.
<h2><A NAME="example"></A>An Example</h2>
<P>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):
<PRE>
Long2IntSortedMap m = new Long2IntAVLTreeMap();
</PRE>
<P>Now we can easily modify and access its content:
<PRE>
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
</PRE>
<P>We can also try to change the default return value:
<PRE>
m.defaultReturnValue( -1 );
m.get( 4 ); // This method call will return -1
</PRE>
<P>We can obtain a type-specific iterator on the key set:
<PRE>
LongBidirectionalIterator i = m.keySet().iterator();
// Now we sum all keys
long s = 0;
while( i.hasNext() ) s += i.nextLong();
</PRE>
<P>We now generate a head map, and iterate bidirectionally over it starting
from a given point:
<PRE>
// 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)
</PRE>
<P>Should we need to access the map concurrently, we can wrap it:
<PRE>
// This map can be safely accessed by many threads
Long2IntSortedMap m2 = Long2IntSortedMaps.synchronize( m1 );
</PRE>
<P>Linked maps are very flexible data structures which can be used to implement, for
instance, queues whose content can be probed efficiently:
<PRE>
// 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
</PRE>
<P>Now, we play with iterators. It is easy to create iterators over
intervals or over arrays, and combine them:
<PRE>
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
</PRE>
<p>It is easy to build sets and maps on the fly using the array-based
constructors:
<pre>
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
</pre>
<P>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:
<PRE>
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
</PRE></div>
</div>
</div>
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar_bottom">
<!-- -->
</a><a href="#skip-navbar_bottom" title="Skip navigation links"></a><a name="navbar_bottom_firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li class="navBarCell1Rev">Overview</li>
<li>Package</li>
<li>Class</li>
<li><a href="overview-tree.html">Tree</a></li>
<li><a href="deprecated-list.html">Deprecated</a></li>
<li><a href="index-all.html">Index</a></li>
<li><a href="help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li>Prev</li>
<li>Next</li>
</ul>
<ul class="navList">
<li><a href="index.html?overview-summary.html" target="_top">Frames</a></li>
<li><a href="overview-summary.html" target="_top">No Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="allclasses-noframe.html">All Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_bottom");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<a name="skip-navbar_bottom">
<!-- -->
</a></div>
<!-- ======== END OF BOTTOM NAVBAR ======= -->
</body>
</html>
|