How to use a non-number type as a key for maps (for example std::bitset)

[Jaimies]

I'm certain that this is a feature unsupported by junction, but just in case, I'll provide some system details.

OS: Ubuntu 20.04.2 LTS
Build system: CMake (used through CLion IDE). Not sure which CMake version it uses under the hood though.

I'm trying to create something like a transposition table for a chess engine. So the following code compiles:

#include <junction/ConcurrentMap_Leapfrog.h>

struct Foo {};

int main() {
    typedef junction::ConcurrentMap_Leapfrog<unsigned long long, Foo*> ConcurrentMap;
    ConcurrentMap map;
    return 0;
}

However, in my case, I'm unable to use unsigned long long as the position hash, because it can't hold enough values. So I use std::bitset. But there is a problem, the following won't compile:

#include <bitset>
#include <junction/ConcurrentMap_Leapfrog.h>

struct Foo {};

int main() {
    typedef junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*> ConcurrentMap;
    ConcurrentMap map;
    return 0;
}

The error is the following:

In file included from /path/to/project/main.cpp:2:
/path/to/project/junction/junction/ConcurrentMap_Leapfrog.h: In instantiation of ‘class junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>’:
/path/to/project/main.cpp:8:19:   required from here
/path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:33:57: error: invalid use of incomplete type ‘struct turf::util::BestFit<std::bitset<100> >’
   33 |     typedef typename turf::util::BestFit<Key>::Unsigned Hash;
      |                                                         ^~~~
In file included from /path/to/project/junction/junction/details/Leapfrog.h:20,
                 from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                 from /path/to/project/main.cpp:2:
/path/to/project/turf/turf/Util.h:22:8: note: declaration of ‘struct turf::util::BestFit<std::bitset<100> >’
   22 | struct BestFit;
      |        ^~~~~~~
In file included from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                 from /path/to/project/main.cpp:2:
/path/to/project/junction/junction/details/Leapfrog.h: In instantiation of ‘static junction::details::Leapfrog<Map>::Table* junction::details::Leapfrog<Map>::Table::create(turf::intTypes::ureg) [with Map = junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>; turf::intTypes::ureg = long long unsigned int]’:
/path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:40:97:   required from ‘junction::ConcurrentMap_Leapfrog<K, V, KT, VT>::ConcurrentMap_Leapfrog(turf::intTypes::ureg) [with K = std::bitset<100>; V = Foo*; KT = junction::DefaultKeyTraits<std::bitset<100> >; VT = junction::DefaultValueTraits<Foo*>; turf::intTypes::ureg = long long unsigned int]’
/path/to/project/main.cpp:8:19:   required from here
/path/to/project/junction/junction/details/Leapfrog.h:81:37: error: ‘struct junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*> >::Cell’ has no member named ‘hash’
   81 |                     group->cells[j].hash.storeNonatomic(KeyTraits::NullHash);
      |                     ~~~~~~~~~~~~~~~~^~~~
In file included from /path/to/project/junction/junction/details/Leapfrog.h:21,
                 from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                 from /path/to/project/main.cpp:2:
/path/to/project/junction/junction/MapTraits.h: In instantiation of ‘struct junction::DefaultKeyTraits<std::bitset<100> >’:
/path/to/project/junction/junction/details/Leapfrog.h:81:21:   required from ‘static junction::details::Leapfrog<Map>::Table* junction::details::Leapfrog<Map>::Table::create(turf::intTypes::ureg) [with Map = junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>; turf::intTypes::ureg = long long unsigned int]’
/path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:40:97:   required from ‘junction::ConcurrentMap_Leapfrog<K, V, KT, VT>::ConcurrentMap_Leapfrog(turf::intTypes::ureg) [with K = std::bitset<100>; V = Foo*; KT = junction::DefaultKeyTraits<std::bitset<100> >; VT = junction::DefaultValueTraits<Foo*>; turf::intTypes::ureg = long long unsigned int]’
/path/to/project/main.cpp:8:19:   required from here
/path/to/project/junction/junction/MapTraits.h:24:55: error: invalid use of incomplete type ‘struct turf::util::BestFit<std::bitset<100> >’
   24 |     typedef typename turf::util::BestFit<T>::Unsigned Hash;
      |                                                       ^~~~
In file included from /path/to/project/junction/junction/details/Leapfrog.h:20,
                 from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                 from /path/to/project/main.cpp:2:
/path/to/project/turf/turf/Util.h:22:8: note: declaration of ‘struct turf::util::BestFit<std::bitset<100> >’
   22 | struct BestFit;
      |        ^~~~~~~
In file included from /path/to/project/junction/junction/details/Leapfrog.h:21,
                 from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                 from /path/to/project/main.cpp:2:
/path/to/project/junction/junction/MapTraits.h:25:22: error: ‘constexpr’ needed for in-class initialization of static data member ‘const Key junction::DefaultKeyTraits<std::bitset<100> >::NullKey’ of non-integral type [-fpermissive]
   25 |     static const Key NullKey = Key(0);
      |                      ^~~~~~~
In file included from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                 from /path/to/project/main.cpp:2:
/path/to/project/junction/junction/details/Leapfrog.h: In instantiation of ‘static junction::details::Leapfrog<Map>::Table* junction::details::Leapfrog<Map>::Table::create(turf::intTypes::ureg) [with Map = junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>; turf::intTypes::ureg = long long unsigned int]’:
/path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:40:97:   required from ‘junction::ConcurrentMap_Leapfrog<K, V, KT, VT>::ConcurrentMap_Leapfrog(turf::intTypes::ureg) [with K = std::bitset<100>; V = Foo*; KT = junction::DefaultKeyTraits<std::bitset<100> >; VT = junction::DefaultValueTraits<Foo*>; turf::intTypes::ureg = long long unsigned int]’
/path/to/project/main.cpp:8:19:   required from here
/path/to/project/junction/junction/details/Leapfrog.h:81:21: error: ‘NullHash’ is not a member of ‘junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*> >::KeyTraits’ {aka ‘junction::DefaultKeyTraits<std::bitset<100> >’}
   81 |                     group->cells[j].hash.storeNonatomic(KeyTraits::NullHash);
      |                     ^~~~~
make[3]: *** [CMakeFiles/test.dir/build.make:82: CMakeFiles/test.dir/main.cpp.o] Error 1
make[2]: *** [CMakeFiles/Makefile2:136: CMakeFiles/test.dir/all] Error 2
make[1]: *** [CMakeFiles/Makefile2:143: CMakeFiles/test.dir/rule] Error 2
make: *** [Makefile:137: test] Error 2

To my understanding, the error is caused by turf being unable to hash std::bitset. Also, C++11 supports hashing std::bitset and a few other types by default so maybe using std::hash in junction implementation could help. I could submit a PR, if you gave me a bit of guidance.