This file is indexed.

/usr/share/doc/libfastutil-java/overview-summary.html is in libfastutil-java-doc 7.1.0-2.

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
970
971
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html>
<head>
<title>Overview (fastutil 7.1.0)</title>
<meta name="date" content="2017-06-24">
<link rel="stylesheet" type="text/css" href="stylesheet.css" title="Style">
<script type="text/javascript" src="script.js"></script>
</head>
<body>
<script type="text/javascript"><!--
    try {
        if (location.href.indexOf('is-external=true') == -1) {
            parent.document.title="Overview (fastutil 7.1.0)";
        }
    }
    catch(err) {
    }
//-->
</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar.top">
<!--   -->
</a>
<div class="skipNav"><a href="#skip.navbar.top" title="Skip navigation links">Skip navigation links</a></div>
<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&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="allclasses-noframe.html">All&nbsp;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&trade; 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">&nbsp;</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">&nbsp;</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="contentContainer"><a name="overview.description">
<!--   -->
</a>
<div class="block"><P>Extends the the <a href="http://java.sun.com/j2se/1.5/docs/guide/collections/">Java&trade; 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>.

    <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&trade; 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:A-">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 by 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&mdash;just <a href="it/unimi/dsi/fastutil/ints/IntIterators.html#wrap-int:A-">wrap it</a>. You do not
    need to write a loop to put the characters returned by an iterator into a
    set&mdash;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&trade; 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. 
    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&ndash;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&dagger;<td>AbstractList, AbstractBigList<td>ArrayList, BigArrayBigList, ArrayFrontCodedList
        <tr><td>PriorityQueue&dagger;<td>AbstractPriorityQueue&dagger;<td>HeapPriorityQueue, ArrayPriorityQueue, ArrayFIFOQueue
        <tr><td>IndirectPriorityQueue&dagger;<td>AbstractIndirectPriorityQueue&dagger;<td>HeapSemiIndirectPriorityQueue, HeapIndirectPriorityQueue, ArrayIndirectPriorityQueue
        <tr><td>Stack&dagger;<td>AbstractStack&dagger;<td>ArrayList
        <tr><td>Iterator, BigListIterator&dagger;<td>AbstractIterator, AbstractListIterator, AbstractBigListIterator
        <tr><td>Comparator<td>AbstractComparator
        <tr><td>BidirectionalIterator&dagger;<td>AbstractBidirectionalIterator
        <tr><td>ListIterator<td>AbstractListIterator
        <tr><td>Size64&Dagger;  
    </table>
    </div>

    <P>&dagger;: 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>&Dagger;: 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&dagger;
        <tr><td>SortedMaps
        <tr><td>Lists
        <tr><td>BigLists
        <tr><td>Arrays&dagger;
        <tr><td>BigArrays&dagger;
        <tr><td>Heaps
        <tr><td>SemiIndirectHeaps
        <tr><td>IndirectHeaps
        <tr><td>PriorityQueues&dagger;
        <tr><td>IndirectPriorityQueues&dagger;
        <tr><td>Iterators
        <tr><td>BigListIterators
        <tr><td>Comparators
        <tr><td>Hash&Dagger;
        <tr><td>HashCommon&Dagger;
    </table>
    </div>

    <P>&dagger;: 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>&Dagger;: 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 and tree-based maps that return primitive numeric values have an <code>addTo()</code>
        method (see, e.g., <a href="it/unimi/dsi/fastutil/ints/Int2IntOpenHashMap.html#addTo-int-int-"><code>Int2IntOpenHashMap.addTo(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&mdash;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 a 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&mdash;for instance, <a href="it/unimi/dsi/fastutil/ints/IntList.html" title="interface in it.unimi.dsi.fastutil.ints">type-specific lists</a>, and
        that a subclass of a type-specific abstract collection must
        override <code>rem()</code>, rather than <code>remove()</code>, to
        make all inherited methods work properly.

      <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. It is of course
    unfortunate that Java 8 introduced an identically named interface with a different signature.

    <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&mdash;a very tuned
    implementation of <a href="it/unimi/dsi/fastutil/ints/IntArrays.html#radixSort-int:A-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:A-int:A-int-int-">two</a> or
        <a href="it/unimi/dsi/fastutil/ints/IntArrays.html#radixSort-int:A:A-int-int-">even more</a> arrays. You
        can also perform <a href="it/unimi/dsi/fastutil/ints/IntArrays.html#radixSortIndirect-int:A-int:A-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, &ldquo;Engineering radix sort&rdquo;, <i>Computing Systems</i>, 6(1), pages 5&minus;27 (1993),
     and further improved using the digit-oracle idea described by
     Juha K&auml;rkk&auml;inen and Tommi Rantala in &ldquo;Engineering radix sort for strings&rdquo;,
     <i>String Processing and Information Retrieval, 15th International Symposium</i>, volume 5280 of
     Lecture Notes in Computer Science, pages 3&minus;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:A-">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:A-">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>slightly worse</em> 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 factor: 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&mdash;there is no &ldquo;marking&rdquo; 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>&mdash;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 &#x2113; is exactly the
      memory required for the related types times &#x2113;. 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&nbsp;&lt;&nbsp;<var>f</var>&nbsp;&le;&nbsp;1, 
      2<sup>&lceil;log <var>n</var>&nbsp;/&nbsp;<var>f</var>&rceil;</sup>
      entries are allocated. When the table is filled up beyond the load factor, it is rehashed 
      doubling its size. When it is emptied below a <em>fourth</em> of the load factor, it
      is rehashed halving its size.

    <p>In the case of linked hash tables, there is an additional vector of
      2<sup>&lceil;log <var>n</var>&nbsp;/&nbsp;<var>f</var>&rceil;</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>
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar.bottom">
<!--   -->
</a>
<div class="skipNav"><a href="#skip.navbar.bottom" title="Skip navigation links">Skip navigation links</a></div>
<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&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="allclasses-noframe.html">All&nbsp;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>