vigna / fastutil Goto Github PK

View Code? Open in Web Editor NEW

1.7K 1.7K 194.0 23.78 MB

fastutil extends the Java™ Collections Framework by providing type-specific maps, sets, lists and queues.

License: Apache License 2.0

Shell 4.49% Makefile 2.55% Java 87.98% HTML 4.98%

java primitive-collections sorting-algorithms

fastutil's People

Contributors

Stargazers

Watchers

Forkers

jgottero shijianguang babenovelty kno10 herberteuler shawncao-zz ame89 nilesh892003 valery-barysok gustvn jteagles zouzias ngadde luoli523 tommyettinger talalbutt rossjudson lemire pandasys raphaelcohn xinglongbing leobelive desperado1992 badhwarvikas stephenbrady neven7 easyfmxu alainlompo mainer yasserg dianhu hezhijie lidi100 mindis huangjun6919 xianhengma kangkot pburka jinyu0310 jxsd0084 seyhagithub hawkingrei gcr1992 loriopatrick sarathkumarsivan jason918 liushoo maximvegorov ruslan-khalitov landawn original-brownbear mdakin sophiameta sridhar-newsdistill alec-liu kelvinni zhouyonglong splavs pranavashok kakaxi2shi benmccann cxz mark-malynn wtx626 sesuncedu chenrui2014 zjpjohn godfreyhe saldi xiao-yun asitti liyazhou mrfsong363 joegana ohnosequences rice668 morristech techsy730 yshprasanth 7tony shishu94 yishenpaxos cmacdonald chakra-coder examin dendisuhubdy javalibrary endlessc caipengchengs jackyglony trantrungtin ting6688 trunglnm tienquanutc wyy-dev tomcatalinalee jiaaale morelli690 wiltonlazary speiger

fastutil's Issues

Compilation under Mac OS X

When installing from sources on OS X, make sources fails with the following errors:

./gencsource.sh drv/Iterable.drv src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c
gcc -w -I. -ftabstop=4   -DASSERTS_VALUE=false -E -C -P src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:7:2: error: invalid preprocessing directive
#unassert keyclass
 ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:8:2: error: invalid preprocessing directive
#assert keyclass(Boolean)
 ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:9:2: error: invalid preprocessing directive
#unassert keys
 ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:10:3: error: invalid preprocessing directive
 #assert keys(primitive)
  ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:11:2: error: invalid preprocessing directive
#unassert valueclass
 ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:12:2: error: invalid preprocessing directive
#assert valueclass(Object)
 ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:13:2: error: invalid preprocessing directive
#unassert values
 ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:14:3: error: invalid preprocessing directive
 #assert values(reference)
  ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:20:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:53:5: error: invalid token at start of a preprocessor expression
#if #valueclass(Object) || #valueclass(Reference)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:72:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:81:5: error: invalid token at start of a preprocessor expression
#if #valueclass(Object) || #valueclass(Reference)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:89:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference) || #valueclass(Object) || #valueclass(Reference)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:113:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:187:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:380:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:391:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object)
    ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:395:7: error: invalid token at start of a preprocessor expression
#elif #keyclass(Float)
      ^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:399:7: error: invalid token at start of a preprocessor expression
#elif #keyclass(Double)
      ^
fatal error: too many errors emitted, stopping now [-ferror-limit=]
20 errors generated.
make: *** [src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java] Error 1

Does parallel Quicksort require extra memory?

Does parallel Quicksort require extra memory? And if so, how much?

There is a note on sequential Quicksort indicating that it does not. However parallel Quicksort does not have this note.

Looking forward to a reply!

Is it possible to add this interface to existing fastutil (AVL,RB)TreeSet implementations? The lower and ceiling methods can be mimicked with calls to headSet().last() and tailSet().first() respectively, but they probably wouldn't be as fast, and the higher and floor methods cannot be mimicked easily at all.

Bug: IterableCollections, isEmpty() via iterable.iterator.hasNext()

I see this in in the IterableCollection of DoubleCollections and IntCollections, didnt check any further:

        public boolean isEmpty() {
            return iterable.iterator().hasNext();
        }

I think, there is a missing negation. Because this actually tells me, the iterable is not empty. Or am i missing something? :)

LongArrayList.removeAll(LongCollection) behaves differently from ArrayList.removeAll(Collection)

LongArrayList.removeAll(LongCollection) only removes the first match, while ArrayList.removeAll(Collection) removes all matches.
List<Long> list = new ArrayList<>(Arrays.asList(1L, 2L, 3L, 4L, 1L, 2L, 3L, 4L));
list.removeAll(Arrays.asList(2L, 4L));
System.out.println(list);

returns [1, 3, 1, 3]

while
LongList list = new LongArrayList(new long[] { 1, 2, 3, 4, 1, 2, 3, 4 });
list.removeAll(Arrays.asList(2L, 4L));
System.out.println(list);

returns [1, 3, 1, 2, 3, 4]

The documentation doesn't really say if that is an expected behaviour (e.g. "removes first occurence")

Bug in list iterator add for BigArrayBigLists

I think this is similar to issue #19:

  @Test
  public void testAddWithIterator() {
    IntBigList list = new IntBigArrayBigList();
    list.iterator().add(1);
    assertEquals(IntBigLists.singleton(1), list);
  }

This fails with an IllegalStateException in AbstractIntBigList line 151 (this is for fastutil 7.0.10).

Code generation fails when changing names in makefile

Hi! I decided to try modifying the makefile so to generate classes with different naming scheme, like this:

#  The capitalized types used to build class and method names; boolean and object types are not listed.
TYPE_NOBOOL_NOOBJ=Byte Short Int Long Char Float Double

#  The capitalized types used to build class and method names; boolean and reference are not listed.
TYPE_NOBOOL_NOREF=$(TYPE_NOBOOL_NOOBJ) Obj

#  The capitalized types used to build class and method names; object types are not listed.
TYPE_NOOBJ=Boolean $(TYPE_NOBOOL_NOOBJ)

#  The capitalized types used to build class and method names; references are not listed.
TYPE_NOREF=$(TYPE_NOOBJ) Obj

#  The capitalized types used to build class and method names; boolean is not listed.
TYPE_NOBOOL=$(TYPE_NOBOOL_NOREF) Ref

# The capitalized types used to build class and method names; now references appear as Reference.
TYPE=$(TYPE_NOREF) Ref

#  The capitalized types used to build class and method names; only types for which big structures are built are listed.
TYPE_BIG=Int Long Float Double Obj Ref

So you'd get something like Ref2ObjMap. Ideally I wanted it to be RefObjMap for example, removing the '2', names which are described in the same file.

The thing is that it seems to break code generation, for instance I get class definitions like:

 public abstract class Abstract2BooleanFunction implements 2BooleanFunction , java.io.Serializable {

That ought to be AbstractSomething2BooleanFunction and Something2BooleanFunction, so compilation fails.

Also if I change TYPE_NOOBJ from Boolean to Bool, I get an error for a missing file:

./drv/BinIO.drv:157:63: fatal error: src/it/unimi/dsi/fastutil/io/BooleanBinIOFragment.h: No such file or directory

Since it seems the full name "BooleanBinIOFragment" is hardcoded in the BinIO.drv file. The generator instead creates BoolBinIOFragment, thus why it cant find it.

Any ideas on what might be wrong or what I am missing?

ArrayMaps make values unmodifiable

  @Test
  public void testMapValuesShouldSupportClear() {
    Int2IntMap map = new Int2IntArrayMap(Int2IntMaps.singleton(42, 24));
    map.values().clear();
    assertTrue(map.isEmpty());
  }

  @Test
  public void testMapValuesShouldSupportRemove() {
    Int2IntMap map = new Int2IntArrayMap(Int2IntMaps.singleton(42, 24));
    map.values().remove(24);
    assertTrue(map.isEmpty());
  }

  @Test
  public void testMapValuesShouldSupportRemoveAll() {
    Int2IntMap map = new Int2IntArrayMap(Int2IntMaps.singleton(42, 24));
    map.values().removeAll(Collections.singleton(24));
    assertTrue(map.isEmpty());
  }

(note that it is ok to throw on add / addAll).

This also works as expected on OpenHashMaps, so the issue seems limited to ArrayMaps.

Packaging of sources is not "standard"

Standard packaging of sources makes the .java file names match the .class file names in the corresponding binary JAR file. This allows the IDEs, static analysis tools, etc to discover them.

fastutil packages sources under src/ and test/ which means that they are essentially useless in any automated environment, and can only be handled manually.

Please can you publish a more standard -sources.jar and either merge the test sources at the root of the sources JAR or publish a separate test sources JAR?

Thank you.

Build problems on Windows

I have been unable to build the latest code on Windows 7 64-bit. My terminal is Cygwin bash, the latest Apache Ant is the main tool being used, and Maven is installed but doesn't seem to be involved with the build. I don't have Ivy installed and I'm not sure if I need it. I put jUnit and Emma (which seems to no longer be needed) in my ~/.ant/lib/ directory, though I have no idea what file names they should have, or what versions to use. I just downloaded a fresh copy of the fastutil sources that incorporate the changes made a few hours ago, and ran make sources without errors or warnings. Running ant jar from Cygwin bash in the root of the downloaded sources gives me a large list of errors.

$ /cygdrive/c/dev/ant/bin/ant jar
Buildfile: C:\Users\User\Downloads\fastutil-master\fastutil-master\build.xml

init:
    [mkdir] Created dir: C:\Users\User\Downloads\fastutil-master\fastutil-master\build
    [mkdir] Created dir: C:\Users\User\Downloads\fastutil-master\fastutil-master\dist\lib

compile:
    [javac] Compiling 1878 source files to C:\Users\User\Downloads\fastutil-master\fastutil-master\build
    [javac] warning: [options] bootstrap class path not set in conjunction with -source 1.7
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\ByteLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\ByteLinkedOpenHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\ByteOpenCustomHashSet.java:27: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\CharLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\CharLinkedOpenHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\CharOpenCustomHashSet.java:27: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\DoubleLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\DoubleLinkedOpenHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\DoubleOpenCustomHashSet.java:27: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\FloatLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\FloatLinkedOpenHashSet.java:23: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\FloatOpenCustomHashSet.java:27: error: class, interface, or enum expected
    [javac] OpenHashSet.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
    [javac] OpenHashMap.drv
    [javac] ^
    [javac] 100 errors
    [javac] 1 warning

BUILD FAILED
C:\Users\User\Downloads\fastutil-master\fastutil-master\build.xml:136: Compile failed; see the compiler error output for details.

Total time: 3 seconds

The last file in that list of errors has unusual contents, and doesn't appear to be valid Java.

/* Generic definitions */




/* Assertions (useful to generate conditional code) */
/* Current type and class (and size, if applicable) */
/* Value methods */
/* Interfaces (keys) */
/* Interfaces (values) */
/* Abstract implementations (keys) */
/* Abstract implementations (values) */
/* Static containers (keys) */
/* Static containers (values) */
/* Implementations */
/* Synchronized wrappers */
/* Unmodifiable wrappers */
/* Other wrappers */
/* Methods (keys) */
/* Methods (values) */
/* Methods (keys/values) */
/* Methods that have special names depending on keys (but the special names depend on values) */
/* Equality */
/* Object/Reference-only definitions (keys) */
/* Primitive-type-only definitions (keys) */
/* Object/Reference-only definitions (values) */
/* Primitive-type-only definitions (values) */
OpenHashMap.drv

This only appears to affect LinkedOpenHashMap and OpenCustomHashMap implementations, though ant may be cutting the build short at 100 errors and more files may be missing implementations.

I suspect this has something to do with the literal string "OpenHashMap.drv" being inserted on Windows, instead of doing what the build should be doing and inserting the contents of that file, probably with preprocessing applied. I'd be happy to try different configurations of toolchain to get this to work.

I'm currently working around this by using the extracted sources jar from Maven for the latest release ( 7.0.10 ). I'm only using a fraction of the classes, so I've semi-manually moved any classes I don't use into an unused directory and copied the used classes into the source tree of my main library. Thanks for all your hard work on fastutil, and for the xorshift benchmarks and algorithms!

IntLists.EMPTY_LIST (and probably other EMPTY_LISTs) should return "[]" as string

Because it inherits toString from AbstractIntCollection it returns "{}" instead.

Regards,
Attila

Insert-Performance in Object2ObjectOpenHashMap depending on insertion order

I'm using an Object2ObjectOpenHashMap as an internal data structure. When my program ends, I write out the content to disk (using custom serialization code, iterating over the map). When the program the next time starts, it reads the data back in from disk, inserting the objects again into the map. I realized that reading the data back in is much slower than inserting the objects in the first round. After some testing, I found out the following:

Inserting objects into an Object2ObjectOpenHashMap in "random" order requires some amount of calls to equals() in the inserted Objects.
Inserting objects into an Object2ObjectOpenHashMap in the order as they are returned from the iterator from another Object2ObjectOpenHashMap, it requires many more calls to equals() in the inserted Objects (at least one magnitude more calls).

If the equals() method does a bit of logic, it has a huge impact on performance.

I'll attach a short piece of code that demonstrates the problem, inserting Strings into the Map (Actually, WrappedStrings so I'm able to count the number of equals() invocations). Inserting the 2 million Strings the first time requires about 5 million equal() calls, while inserting them the second time requires about 180 million equal() calls.

It reminds me a bit of the problem in Java's HashMap a while ago (Java 7?) where it was said inserting objects in a special order could lead to Denial of Service attacks due to very poor performance in such cases.

InsertTest.java.txt

Collection<T> compatibility methods should take null parameter

Since the collections declare that they implement the corresponding java.util.Collection interface (ie. IntSet implements Set), they should handle nulls gracefully. See tests here:

https://github.com/gpanther/fastutil-guava-tests/blob/c16625d/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L46
https://github.com/gpanther/fastutil-guava-tests/blob/c16625d/src/test/java/net/greypanther/fastutil/tests/IntArraySetTest.java

Ie. don't throw exception when .contains(null) is called (rather return false).

Note: throwing null for contains / containsAll / removeAll / retainAll IS allowed by the wording on collections (see https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#retainAll-java.util.Collection- - "NullPointerException - if this collection contains one or more null elements and the specified collection does not permit null elements (optional), or if the specified collection is null") so perhaps the only thing needs fixing here is the equals method for sets (the second link in the above case). I only gave the example for IntArraySet but the same problem is exhibited by the other set implementations also.

Regards,
Attila

Arrays.quicksort() produces results inconsistent with Collections.sort() with same data and comparator

Hi,

I'm trying to sort a set of integers that represents row indexes in a 'table' object, according to the values in the table, with the sorting logic provided by a comparator.

I have run a side-by-side test using java.util.Collections and it.unimi.dsi.fastutil.Arrays. A visual inspection confirms that the Collections#sort produces the expected order. Here is the code from the test:

    table1 = StorageManager.readTable("bigdata/airlines");
    table2 = StorageManager.readTable("bigdata/airlines");

   // This is just used to create a comparator below
    Sort key = Table.getSort("ORIGIN");

    // first try, with Collections.sort.
    IntComparator rowComparator = table1.getComparator(key);
    IntArrayList t1rows = table1.rows();
    Collections.sort(t1rows, rowComparator);

    // second try, with Arrays.quicksort()
    IntComparator rowComparator2 = table2.getComparator(key);
    IntArrayList t2rows = table2.rows();
    int[] values = t2rows.elements();

    Arrays.quickSort(0, t2rows.size(), rowComparator2, new Swapper() {
      @Override
      public void swap(int a, int b) {
        int temp = values[a];
        values[a] = values[b];
        values[b] = temp;
      }
    });

    // This assert fails. The arrays are sorted in a completely different order.
    assertTrue(java.util.Arrays.equals(values, t1rows.elements()));

My first thought was that there is a bug in my swap routine, but I can't see it.

This is the comparator being used:

  public final IntComparator rowComparator = new IntComparator() {

    @Override
    public int compare(int i, int i1) {
      return getString(i).compareTo(getString(i1));
    }

    @Override
    public int compare(Integer i, Integer i1) {
      return getString(i).compareTo(getString(i1));
    }
  };

The method is defined such that the row indexes from the sort column ("ORIGIN") are compared according to the standard lexicographical sort on the string values of that column.

Any suggestions would be very much appreciated. If you agree that this seems like a bug, I can try to provide a simple executable test case to recreate.

The method Long2DoubleArrayMap(Map<Long,Double>) is undefined

The following simple program doesn't compile in JDK8 with eclipse:

import java.util.HashMap;
import java.util.Map;

public class Test {
    public static void main(String[] args) {
        Map<Long, Double> map = new HashMap();
        System.out.println(Long2DoubleArrayMap(map));
    }
}

As the documentation states there should be a constructor for Long2DoubleArrayMap(Map<? extends Long,? extends Double> m).

I am probably missing something very basic. Newbe here.

Thanks

Some methods in SynchronizedMap don't use synchronization

I've looked into source code for SynchronizedMap and I'm not sure it's implemented correctly:

public LongSet keySet() {
    if ( keys == null ) keys = LongSets.synchronize( map.keySet(), sync );
        return keys;
    }
}

If multiple threads call this method at the same time, than mutliple LongSet instances might be created. They are thread-safe, so nothing bad will happen, but still it feels not right.

Moreover another method never sets the values variable:

public ObjectCollection<V> values() {
    if ( values == null ) return ObjectCollections.synchronize( map.values(), sync );
    return values;
}

Java's implementation in java.util.Collections.SynchronizedMap synchronizes the whole method:

public Set<K> keySet() {
    synchronized (mutex) {
        if (keySet==null)
            keySet = new SynchronizedSet<>(m.keySet(), mutex);
        return keySet;
    }
}

SubMap/Head/Tail implementation of Long2LongAVLTreeMap and Long2ObjectAVLTreeMap gives different results

`
@test
public void testSubSet() {
final Long2LongAVLTreeMap long2LongAVLTreeMap = new Long2LongAVLTreeMap();
final Long2ObjectAVLTreeMap long2ObjectAVLTreeMap = new Long2ObjectAVLTreeMap<>();
testSubSet(long2LongAVLTreeMap, long2ObjectAVLTreeMap);
}

void testSubSet(AbstractLong2LongSortedMap long2LongAVLTreeMap, AbstractLong2ObjectSortedMap long2ObjectAVLTreeMap) {
final TreeMap<Long, Long> treeMap = new TreeMap<>();
final long[] input = {1, 2, 3, 4, 5};
for (long l : input) {
treeMap.put(l, l);
long2LongAVLTreeMap.put(l, l);
long2ObjectAVLTreeMap.put(l, (Long) l);
}

for (long fromKey = 0; fromKey < 7; fromKey++) {
  for (long toKey = fromKey; toKey < 8; toKey++) {

    // SubMap
    final Long2LongSortedMap long2LongSubmap = long2LongAVLTreeMap.subMap(fromKey, toKey);
    final Long2ObjectSortedMap<Long> long2ObjectSubmap = long2ObjectAVLTreeMap.subMap(fromKey, toKey);
    final NavigableMap<Long, Long> treeSubmap = treeMap.subMap(fromKey, true, toKey, false);
    compare(long2LongSubmap, long2ObjectSubmap, treeSubmap);

    // Head
    final Long2LongSortedMap long2LongHead = long2LongAVLTreeMap.headMap(fromKey);
    final Long2ObjectSortedMap<Long> long2ObjectHead = long2ObjectAVLTreeMap.headMap(fromKey);
    final NavigableMap<Long, Long> treeHead = treeMap.headMap(fromKey, false);
    compare(long2LongHead, long2ObjectHead, treeHead);

    // Tail
    final Long2LongSortedMap long2LongTail = long2LongAVLTreeMap.tailMap(toKey);
    final Long2ObjectSortedMap<Long> long2ObjectTail = long2ObjectAVLTreeMap.tailMap(toKey);
    final NavigableMap<Long, Long> treeTail = treeMap.tailMap(toKey, true);
    compare(long2LongTail, long2ObjectTail, treeTail);

    // Subset Subset/Had/Tail
    if (treeSubmap.isEmpty()) continue;
    final ObjectSortedSet<Map.Entry<Long, Long>> long2LongEntries = long2LongSubmap.entrySet();
    final ObjectSortedSet<Map.Entry<Long, Long>> long2ObjectEntries = long2ObjectSubmap.entrySet();

    final Map.Entry<Long, Long> firstL = long2LongEntries.first();
    final Map.Entry<Long, Long> lastL = long2LongEntries.last();
    assertNotNull(firstL);
    assertNotNull(lastL);

    final Map.Entry<Long, Long> firstO = long2ObjectEntries.first();
    final Map.Entry<Long, Long> lastO = long2ObjectEntries.last();
    assertNotNull(firstL);
    assertNotNull(lastL);

    // Subset
    final List<Long> ss1 = long2LongEntries.subSet(firstL, lastL)
      .stream().map(kv -> kv.getKey()).collect(Collectors.toList());
    final List<Long> ss2 = long2ObjectEntries.subSet(firstO, lastO)
      .stream().map(kv -> kv.getKey()).collect(Collectors.toList());
    assertEquals(ss1, ss2);

    // Head
    final List<Long> h1 = long2LongEntries.headSet(firstL)
      .stream().map(kv -> kv.getKey()).collect(Collectors.toList());
    final List<Long> h2 = long2ObjectEntries.headSet(firstO)
      .stream().map(kv -> kv.getKey()).collect(Collectors.toList());
    assertEquals(h1, h2);

    // Tail
    final List<Long> t1 = long2LongEntries.tailSet(firstL)
      .stream().map(kv -> kv.getKey()).collect(Collectors.toList());
    final List<Long> t2 = long2ObjectEntries.tailSet(lastO)
      .stream().map(kv -> kv.getKey()).collect(Collectors.toList());
    assertEquals(t1, t2);
  }
}

void compare(
Long2LongSortedMap long2LongAVLTreeMap,
SortedMap<Long, Long> long2ObjectAVLTreeMap,
NavigableMap<Long, Long> treeMap) {
List list1 = new ArrayList<>(long2LongAVLTreeMap.keySet());
List list2 = new ArrayList<>(long2ObjectAVLTreeMap.keySet());
List list3 = new ArrayList<>(treeMap.keySet());
assertEquals(list1, list2);
assertEquals(list2, list3);
}
`

Fails on tail result comparison:
Expected :[1, 2]
Actual :[2]

entrySet().toArray() does not null next element after last

This is the same issue as in #18 (When calling toArray(T[]) the element after the last one should be null), but now it's for YYYEmptyMap.entrySet().toArray(T[]). See failing unit test here: https://github.com/gpanther/fastutil-guava-tests/blob/master/src/test/java/net/greypanther/fastutil/tests/Int2IntMapTest.java#L72

Allocations on Map/Set Removal

I am seeing a lot of allocations from the open hash set and map classes. For this use case I am using the ACT pattern to keep track of information for requests.

When responses are received, the ACT is re-read from the received response and used to remove the object from the corresponding map.
When new requests are made, objects are retrieved from the pool and associated to a new ACT by inserting into a Int2ObjectOpenHashMap

This is causing a massive amount of allocations because the map is constantly being halved and then moments later is doubled in size. This behavior is indeed documented:

If the table is emptied below one fourth of the load factor, it is halved in size

but I still feel this behavior is unwarranted because:

Trimming methods are provided for anyone who might care about using too much memory.
No facility, to my knowledge, is provided to anyone who cares about allocations instead of memory usage, not to mention all the copying this requires.
It's next to impossible to provide a valid sizing hint, i.e., the following immediately halves the table:

  Int2IntOpenHashMap m = new Int2IntOpenHashMap(4_096);

  m.put(1, 1);
  m.remove(1);

This has the following impact on my code:

In one of my applications with fastutil 7.0.11, this is causing several hundreds of GiBs worth of allocations per second with pauses ranging in the 200-400 milliseconds per second. In this case I am fortunate because I can work around it using clear
I have another application that uses a very small heap on Java 6 with fastutil 6.6.3. This application I thought was allocation free once it reached the steady state but because of this it makes about 1 MiB/s worth of allocations resulting in about 2 pauses of 8 ms each per minute.

The following code reproduces the issue in case I am not being clear:

import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import org.junit.Test;

import static org.junit.Assert.*;

public class RehashTest {
  @Test
  public void test() {
    Int2IntOpenHashMap m = new Int2IntOpenHashMap();

    for (int i = 0; i < 100_000_000; i++) {
      for (int j = 0; j < 1_000; j++) {
        m.put(j, j);
      }

      for (int j = 0; j < 1_000; j++) {
        m.remove(j, j);
      }
    }
  }
}

I am willing to provide the patch for this myself if there is interest. The solution is just not to rehash on remove, e.g., replace this

	private V removeEntry(final int pos) {
		final V oldValue = value[pos];
		value[pos] = null;
		size--;
		shiftKeys(pos);
		if (size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) rehash(n / 2);
		return oldValue;
	}

with

	private V removeEntry(final int pos) {
		final V oldValue = value[pos];
		value[pos] = null;
		size--;
		shiftKeys(pos);
		return oldValue;
	}

For completeness, I also looked at Agrona, its maps do not rehash on removal

Make YYYLinkedOpenHashSet.comparator return something meaningful

YYYLinkedOpenHashSet declares that it implements SortedSet, however it breaks [the contract for the comparator method|https://docs.oracle.com/javase/8/docs/api/java/util/SortedSet.html#comparator--] which states that:

Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.

However YYYLinkedOpenHashSet always returns null, even though it should return a comparator which does something like: "if element A was inserted before B then return -1, if B was inserted before A return 1 else return 0" (ie. don't use the "natural order" but rather use the "insertion order").

See a failing unittest [here|https://github.com/gpanther/fastutil-guava-tests/blob/master/src/test/java/net/greypanther/fastutil/tests/Int2IntSortedSetTest.java#L13].

An other option to implementing the above comparator (which is not-very-fast) is for YYYLinkedOpenHashSet to just not implement SortedSet (as java.util.LinkedHashSet does it).

Implement the PrimitiveIterator Interface

Java 8 introduced support for primitive iterators to avoid costs for boxing and unboxing values during iteration: Documentation. This is very similar to the existing IntIterator, LongIterator, and DoubleIterator. In order to improve compatibility with the standard Java Collection Framework I propose changing the IntIterator declaration from

public interface IntIterator extends Iterator<Integer>

public interface IntIterator extends PrimitiveIterator.OfInt

and analogously the two other interfaces. The obvious drawback of this is that the minimum requirement for fastutil gets bumped up to Java 8.

IntBigArrayBigList.listIterator does not check the index paremeter when called with a long

As per the documentation:

ListIterator listIterator(int index) ... Throws: IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())

However the following tests fail:

  @Test(expected=IndexOutOfBoundsException.class)
  public void testListIterator_tooLow() {
    new IntBigArrayBigList().listIterator(-1L);
  }

  @Test(expected=IndexOutOfBoundsException.class)
  public void testListIterator_tooHigh() {
    new IntBigArrayBigList().listIterator(1L);
  }

Note that they pass in longs not ints. This calls listIterator( final long index ) from AbstractIntBigList which does not have bounds checking (as opposed to the int version - listIterator( final int index ) on IntBigArrayBigList which does). While the fix is simple (adding ensureIndex( index ); to the former), perhaps some kind of code reuse can be achieved here (why isn't the method with int just calling the long method? why does it need a different implementation?)

Iterator.remove for entry set of ArrayMap throws ArrayIndexOutOfBounds instead of IllegalStateException

  @Test(expected = IllegalStateException.class)
  public void testArrayMapEmptyEntrySetThrowsExceptionOnIteratorRemove() {
    ObjectIterator<Entry<Integer, Integer>> iterator = new Int2IntArrayMap().entrySet().iterator();

    assertFalse(iterator.hasNext());
    iterator.remove();
  }

According to the documentation this should throw IllegalStateException (but at least it throws an exception 😄).

Java 8 Synchronization

From reviewing the source code I would expect some methods not to be synchronized correctly if xxxxMaps.synchronize(xxxxMap<K, V>) is called.

That would be probably every method being defined as default in java.util.Map, such as compute, computeIfAbsent or computeIfPresent.

When calling toArray(T[]) the element after the last one should be null...

if there is enough space in the passed-in array. Documented here: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#toArray-T:A-

"If this collection fits in the specified array with room to spare (i.e., the array has more elements than this collection), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of this collection only if the caller knows that this collection does not contain any null elements.)"

Test showing that fastutil does not respect this: https://github.com/gpanther/fastutil-guava-tests/blob/bea3e/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L30

Regards,
Attila

Left over benchmark code?

I think there is some left-over benchmark code here:

fastutil/src/it/unimi/dsi/fastutil/BigArrays.java

Line 562 in 14a7b91

public static void main(final String arg[]) {

BigList removeAll adds elements :-)

  @Test
  public void testRemoveAllModifiesCollection() {
    IntBigList list = new IntBigArrayBigList();
    assertFalse(list.removeAll(Collections.emptySet()));
    assertEquals(IntBigLists.EMPTY_BIG_LIST, list);
  }

The first assertion fails because removeAll return true (even though it should return false since the collection was not modified). But even if we ignore that assertion, it errors out at the second assert since "removing nothing" suddenly populated the BitList with [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 😄.

Missing emma_ant.properties referenced from build.xml

A tiny issue: build.xml references the missing emma_ant.properties around line 124 which prints the warning:

  [taskdef] Could not load definitions from resource emma_ant.properties. It could not be found.

HashCode for empty list should be one

As per the documentation: https://docs.oracle.com/javase/8/docs/api/java/util/List.html#hashCode--

Again, the issue is that IntLists.EMPTY_LIST inherits the hashCode implementation from AbstractIntCollection

Regards,
Attila

ObjectOpenCustomHashSet.rehash throws ArrayIndexOutOfBoundsException: -1

Version 7.0.6

Getting this
java.lang.ArrayIndexOutOfBoundsException: -1 at it.unimi.dsi.fastutil.objects.ObjectOpenCustomHashSet.rehash(ObjectOpenCustomHashSet.java:536) at it.unimi.dsi.fastutil.objects.ObjectOpenCustomHashSet.add(ObjectOpenCustomHashSet.java:255)

The set is created like
ObjectOpenCustomHashSet<byte[]> set = new ObjectOpenCustomHashSet<>(ByteArrays.HASH_STRATEGY);

And the only method that is ever called is
ObjectOpenCustomHashSet.add(byte[])

I don't have an exact path to reproduce but I am getting the error fairly often.

$ java -version
java version "1.7.0_80"
Java(TM) SE Runtime Environment (build 1.7.0_80-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.80-b11, mixed mode)
$ uname -r
2.6.32-573.12.1.el6.x86_64

LongOpenHashSet.removeAll(LongCollection) too slow

If I call LongOpenHashSet.removeAll(LongCollection), then AbstractLongCollection.removeAll(LongCollection) ist called.

For each long of the given collection, this method iterates over the whole Set until it finds a match. If a match is found, it's removed.

That may be useful for Lists, but for Sets it doesn't make sense, because it's extremely slow on large Sets.

For Sets it should just call remove for each given collection element.

Add efficient versions of Java 8 Map's methods (primitive specializations)

map.putIfAbsent(k, v): v
map.replace(k): v
map.replace(k, v): boolean
map.remove(k, v): boolean

Even not talking about lambda-accepting methods, putIfAbsent() is a painfully missing part.

RemoveAll should remove all occurrences of a given element from the collection

From the documentation: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#removeAll-java.util.Collection- (emphasis added):

"Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection."

This currently doesn't work for Lists where they only remove the first occurrences (the same seems to be true for BigLists). See tests at https://github.com/gpanther/fastutil-guava-tests/blob/37b76e/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L68

A quick glance seems to indicate that the problem is that the method is implemented at AbstractXXXCollection level where it calls "rem" in a loop. Probably the solution would be to add "remAll" methods (both boxed and unboxed versions) at the collection level and call those from AbstractXXXCollection (for sets for example rem and remAll can contain identical implementations).

Regards,
Attila

LongOpenHashSet gets stuck in infinite loop when removing if load factor is 1.0f and trim has been called

Here is how to reproduce with fastutil-7.0.8:

import it.unimi.dsi.fastutil.longs.LongOpenHashSet;

public class LongOpenHashSetInfiniteLoopInRemove {

    public static void main(String[] args) {
        LongOpenHashSet set = new LongOpenHashSet(4, 1.0f); // Changing load factor to 0.9f makes this work
        set.add(1);
        set.add(2);
        set.add(3);

        set.remove(2);
        set.trim();  // Removing this trim makes this work

        System.out.println("Remove 1 starts...");
        set.remove(1); // Will hang inside this call
        System.out.println("Remove 1 done!");
    }
}

Running:

javac -cp fastutil-7.0.8.jar LongOpenHashSetInfiniteLoopInRemove.java
java -cp ".:./fastutil-7.0.8.jar" LongOpenHashSetInfiniteLoopInRemove

Source is missing?

I was looking for the source of IntArrayList, and cannot find it in the repo. I did a repository search and found references to it, but there is no IntArrayList.java file. Is this a temporary thing, or am i missing something? Thank you. Love this library, btw.

Infinite loop in trim(n) when n < size()

This code produces infinite loop:
IntOpenHashSet set = new IntOpenHashSet();
set.add(1);
set.add(2);
set.add(3);
set.trim(1);

while it shouldn't rehash the set at all.

RemoveAll should remove all occurrences of a given element from the collection (for BigLists)

This is the same as issue #16 (RemoveAll should remove all occurrences of a given element from the collection), but it also needs fixing for ?BigArrayBigList.

Bug in list iterator add

I'm trying to add the battery of tests from Google Guava's testlib [1] to FastUtils and found the following discrepancy between ArrayList and (Byte)ArrayList (though I suspect that it's present in all of the *ArrayLists since they share the common template):

  @Test
  public void testAddUsingIteratorToTheFirstPosition() {
    testAddUsingIteratorToTheFirstPosition_internal(new ArrayList<>());
    testAddUsingIteratorToTheFirstPosition_internal(new ByteArrayList());
  }

  private void testAddUsingIteratorToTheFirstPosition_internal(List<Byte> list) {
    list.add((byte)24);
    ListIterator<Byte> it = list.listIterator();
    it.add((byte)42);
    assertTrue(it.hasNext());
    assertEquals(Arrays.asList((byte)42, (byte)24), list);
  }

Ie. adding an element using the list iterator on the first position fails with IllegalStateException. The test also demonstrates that using ArrayList works as expected.

Regards,
Attila

PS. I will post other bugs I discover as I debug them.

Compilation under Mac OS X

When installing from sources on OS X, make sources fails with the following errors:

`./gencsource.sh drv/Iterable.drv src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c
gcc -w -I. -ftabstop=4 -DASSERTS_VALUE=false -E -C -P src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:7:2: error: invalid preprocessing directive

unassert keyclass

^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:8:2: error: invalid preprocessing directive

assert keyclass(Boolean)

^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:9:2: error: invalid preprocessing directive

unassert keys

^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:10:3: error: invalid preprocessing directive
#assert keys(primitive)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:11:2: error: invalid preprocessing directive

unassert valueclass

^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:12:2: error: invalid preprocessing directive

assert valueclass(Object)

^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:13:2: error: invalid preprocessing directive

unassert values

^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:14:3: error: invalid preprocessing directive
#assert values(reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:20:5: error: invalid token at start of a preprocessor expression

if #keyclass(Object) || #keyclass(Reference)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:53:5: error: invalid token at start of a preprocessor expression

if #valueclass(Object) || #valueclass(Reference)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:72:5: error: invalid token at start of a preprocessor expression

if #keyclass(Object) || #keyclass(Reference)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:81:5: error: invalid token at start of a preprocessor expression

if #valueclass(Object) || #valueclass(Reference)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:89:5: error: invalid token at start of a preprocessor expression

if #keyclass(Object) || #keyclass(Reference) || #valueclass(Object) || #valueclass(Reference)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:113:5: error: invalid token at start of a preprocessor expression

if #keyclass(Object) || #keyclass(Reference)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:187:5: error: invalid token at start of a preprocessor expression

if #keyclass(Object)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:380:5: error: invalid token at start of a preprocessor expression

if #keyclass(Object) || #keyclass(Reference)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:391:5: error: invalid token at start of a preprocessor expression

if #keyclass(Object)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:395:7: error: invalid token at start of a preprocessor expression

elif #keyclass(Float)

src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:399:7: error: invalid token at start of a preprocessor expression

elif #keyclass(Double)

fatal error: too many errors emitted, stopping now [-ferror-limit=]
20 errors generated.
make: *** [src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java] Error 1
`

Iterator.remove throws on IntArraySet

The following code throws an UnsupportedOperationException, even though it should remove the element (or should it? Is IntArraySet considered to be immutable? then again, it implements add/remove on the class level):

    IntSet set = new IntArraySet(Arrays.asList(42));

    IntIterator iterator = set.iterator();
    assertTrue(iterator.hasNext());
    iterator.next();
    iterator.remove();

The stacktrace of the exception (with fastutil 7.0.10) is:

java.lang.UnsupportedOperationException
    at it.unimi.dsi.fastutil.ints.AbstractIntIterator.remove(AbstractIntIterator.java:66)
    at net.greypanther.fastutil.tests.IntArraySetTest.testRemoveFromIterator(IntArraySetTest.java:27)
...

Modularized version (of smaller size, e.g. without Big collections)

At 16 MB, fastutil is a pretty large package.

It would be nice to have a modularized version. For example, many users may not need the Big variants. I imagine that the Big variants add a considerable amount of size to fastutil.

I can also imagine that a lot of users only need double, int and long; but it seems difficult on where to draw a line for a "core" subset that most people use.

Right now, I'm still using Trove which is just 2.5 MB. I like trove iterators more than Java-compatible iterators (in particular for iterating over primitive maps, it.key()+it.value() are both readable and avoid boxing "Entry" objects), and whenever I tried to switch to fastutil, gsc, Koloboke/HFT I found a lot of code to be less elegant because of Java-style iterators. The other thing that is holding me back is the size. Fastutil for example would double the size of our project instantly.

Array map entrySet throws on remove / removeAll

This is just one example, but it will throw on all calls of remove / removeAll since *ArrayMap.EntrySet inherits from AbstractObjectSet which implements remove as throwing UnsupportedOperationException.

  @Test
  public void testEntrySetSupportsRemoveAll() {
    Int2IntMap map = new Int2IntArrayMap();
    assertFalse(map.entrySet().removeAll(Collections.singleton("TEST")));
  }

???ArrayFIFOQueue#dequeue??? should throw NoSuchElementException

dequeue??? should throw NoSuchElementException if there is no element in the queue like dequeueLast???. ??? is the primitive type name.

Alternatively have 2 methods like in Java where on rentuns a special value and another throws an exception. (https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html)

AbstractIntIterator.skip() should throw IAE on argument < 0

Currently it looks like

    public int skip(final int n) {
        int i = n;
        while (i-- != 0 && hasNext())
            nextInt();
        return n - i - 1;
    }

So it will iterate ~ 2 billion times

Lists should never be equal to sets

See test here: https://github.com/gpanther/fastutil-guava-tests/blob/97fda/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L88

This is again caused by the fact that IntLists.EMPTY_LIST inherits equals from AbstractIntCollection.

Regards,
Attila

Recyclable Iterators

I would like to introduce the idea that fastutil should support recyclable iterators. That is, when calling the iterator() method, the same iterator object should be returned but reset to the start.

When trying to avoid allocations, it's clear that escape analysis can remove these allocations, but that means nothing when trying to profile the application, all I can see is these iterators because escape analysis is turned off by the profiler so I just fallback to using elements() where I can.

As long as the collections are not being paired with a lock, it seems like this is pretty straightforward. For the synchronized collections, this might be complicated. Although a lock must be held for the duration of the iteration, the iterator itself might be retained beyond the scope of the lock, and then be used again when the lock is re-acquired

Jar empty with maven command

Hi,
i need to use fastutil in my thesys project, but i need to use a jar of it that will be imported; i try with the usual command mvn package but it is still empty. Can someone help me with this issue?
Thanks in advance

page isn’t working- fastutil.di.unimi.it

Seems this website is down. I am unable to access javadocs online

Singleton sets can throw NullPointer / ClassCast exception

See unittest here: https://github.com/gpanther/fastutil-guava-tests/blob/b154514cbaee3c06353d2c50a9babe77a21ddc6b/src/test/java/net/greypanther/fastutil/tests/Int2IntMapTest.java#L63

The problem seems to be that Maps.Singleton does not check the types of the Map.Entry it gets (IMHO it should do an instanceof check on both key and value which would also weed out null values):

fastutil/drv/Maps.drv

Line 166 in 0740dcd

Map.Entry<?,?> e = (Map.Entry<?,?>)o;

Versioning policy?

Hello!

I use fastutil in several projects with the types often appearing as part of published APIs. As fastutil is a healthy project with frequent releases, I often have to update version numbers. Is it safe to assume that fastutil is using semantic versioning? It seems like it is, given how the version numbers have changed over time, but I don't see an explicit policy written down anywhere. With an explicit policy in place, I can use version ranges in dependencies to make it easier to stay up-to-date.

vigna / fastutil Goto Github PK

fastutil's People

Contributors

Stargazers

Watchers

Forkers

fastutil's Issues

unassert keyclass

assert keyclass(Boolean)

unassert keys

unassert valueclass

assert valueclass(Object)

unassert values

if #keyclass(Object) || #keyclass(Reference)

if #valueclass(Object) || #valueclass(Reference)

if #keyclass(Object) || #keyclass(Reference)

if #valueclass(Object) || #valueclass(Reference)

if #keyclass(Object) || #keyclass(Reference) || #valueclass(Object) || #valueclass(Reference)

if #keyclass(Object) || #keyclass(Reference)

if #keyclass(Object)

if #keyclass(Object) || #keyclass(Reference)

if #keyclass(Object)

elif #keyclass(Float)

elif #keyclass(Double)

Recommend Projects

Recommend Topics

Recommend Org