123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281 |
- #ifndef CORE_HASHMAP_HPP
- #define CORE_HASHMAP_HPP
- #include "core/data/LinkedList.hpp"
- #include "core/data/List.hpp"
- #include "core/utils/ArrayString.hpp"
- #include "core/utils/HashCode.hpp"
- #include "core/utils/Meta.hpp"
- namespace Core {
- template<typename K, typename V>
- struct HashMap final {
- class Node final {
- friend HashMap;
- friend List<Node>;
- friend LinkedList<Node>;
- K key;
- public:
- V value;
- const K& getKey() const {
- return key;
- }
- void toString(BufferString& s) const {
- s.append(key).append(" = ").append(value);
- }
- private:
- template<typename... Args>
- Node(const K& key_, Args&&... args)
- : key(key_), value(Core::forward<Args>(args)...) {
- }
- };
- private:
- using NodePointer = LinkedList<Node>::Node*;
- using NodePointerList = List<NodePointer>;
- using NodeIterator = LinkedList<Node>::Iterator;
- using ConstNodeIterator = LinkedList<Node>::ConstIterator;
- template<typename N, typename I, typename R, R& (*A)(I&)>
- class Iterator final {
- N iterator;
- public:
- Iterator(N iterator_) : iterator(iterator_) {
- }
- Iterator& operator++() {
- ++iterator;
- return *this;
- }
- bool operator!=(const Iterator& other) const {
- return iterator != other.iterator;
- }
- R& operator*() const {
- return A(*iterator);
- }
- };
- template<typename R>
- static R& access(R& node) {
- return node;
- }
- template<typename I, typename R>
- static R& accessValue(I& node) {
- return node.value;
- }
- static const K& accessKey(const Node& node) {
- return node.getKey();
- }
- template<typename N, typename R>
- using BaseEntryIterator = Iterator<N, R, R, access<R>>;
- using EntryIterator = BaseEntryIterator<NodeIterator, Node>;
- using ConstEntryIterator =
- BaseEntryIterator<ConstNodeIterator, const Node>;
- template<typename N, typename I, typename R>
- using BaseValueIterator = Iterator<N, I, R, accessValue<I, R>>;
- using ValueIterator = BaseValueIterator<NodeIterator, Node, V>;
- using ConstValueIterator =
- BaseValueIterator<ConstNodeIterator, const Node, const V>;
- using ConstKeyIterator =
- Iterator<ConstNodeIterator, const Node, const K, accessKey>;
- template<typename M, typename I>
- struct IteratorAdapter final {
- M& map;
- I begin() const {
- return I(map.nodes.begin());
- }
- I end() const {
- return I(map.nodes.end());
- }
- };
- using ValueIteratorAdapter = IteratorAdapter<HashMap, ValueIterator>;
- using ConstValueIteratorAdapter =
- IteratorAdapter<const HashMap, ConstValueIterator>;
- using ConstKeyIteratorAdapter =
- IteratorAdapter<const HashMap, ConstKeyIterator>;
- private:
- LinkedList<Node> nodes{};
- List<NodePointerList> nodePointers{};
- public:
- HashMap() = default;
- HashMap(const HashMap& other) {
- for(const auto& en : other) {
- add(en.getKey(), en.value);
- }
- }
- HashMap(HashMap&& other) {
- swap(other);
- }
- HashMap& operator=(HashMap other) {
- swap(other);
- return *this;
- }
- void rehash(size_t minCapacity) {
- if(minCapacity <= nodePointers.getLength()) {
- return;
- }
- HashMap<K, V> map;
- size_t l =
- 1lu << Math::roundUpLog2(Core::Math::max(minCapacity, 8lu));
- map.nodePointers.resize(l);
- for(NodePointerList& list : nodePointers) {
- for(NodePointer& n : list) {
- size_t h = map.hashIndex(n->data.key);
- map.nodePointers[h].add(n);
- }
- }
- Core::swap(map.nodePointers, nodePointers);
- }
- template<typename... Args>
- bool tryEmplace(V*& v, const K& key, Args&&... args) {
- rehash(nodes.getLength() + 1);
- size_t h = hashIndex(key);
- v = searchList(key, h);
- if(v != nullptr) {
- return false;
- }
- NodePointer np = nodes.put(key, Core::forward<Args>(args)...);
- nodePointers[h].add(np);
- v = &(np->data.value);
- return true;
- }
- template<typename VA>
- V& put(const K& key, VA&& value) {
- rehash(nodes.getLength() + 1);
- size_t h = hashIndex(key);
- V* v = searchList(key, h);
- if(v != nullptr) {
- *v = Core::forward<VA>(value);
- return *v;
- }
- NodePointer np = nodes.put(key, Core::forward<VA>(value));
- nodePointers[h].add(np);
- return np->data.value;
- }
- template<typename VA>
- HashMap& add(const K& key, VA&& value) {
- put(key, Core::forward<VA>(value));
- return *this;
- }
- bool remove(const K& key) {
- NodePointerList& list = nodePointers[hashIndex(key)];
- for(size_t i = 0; i < list.getLength(); i++) {
- if(list[i]->data.key == key) {
- nodes.remove(list[i]);
- list.removeBySwap(i);
- return true;
- }
- }
- return false;
- }
- const V* search(const K& key) const {
- return searchList(key, hashIndex(key));
- }
- V* search(const K& key) {
- return searchList(key, hashIndex(key));
- }
- bool contains(const K& key) const {
- return search(key) != nullptr;
- }
- HashMap& clear() {
- nodes.clear();
- for(NodePointerList& n : nodePointers) {
- n.clear();
- }
- return *this;
- }
- ConstKeyIteratorAdapter getKeys() const {
- return {*this};
- }
- ValueIteratorAdapter getValues() {
- return {*this};
- }
- ConstValueIteratorAdapter getValues() const {
- return {*this};
- }
- EntryIterator begin() {
- return EntryIterator(nodes.begin());
- }
- EntryIterator end() {
- return EntryIterator(nodes.end());
- }
- ConstEntryIterator begin() const {
- return ConstEntryIterator(nodes.begin());
- }
- ConstEntryIterator end() const {
- return ConstEntryIterator(nodes.end());
- }
- void swap(HashMap& other) {
- Core::swap(nodes, other.nodes);
- Core::swap(nodePointers, other.nodePointers);
- }
- void toString(BufferString& s) const {
- Core::toString(s, *this);
- }
- private:
- template<typename H>
- size_t hashIndex(const H& key) const {
- return hashCode(key) & (nodePointers.getLength() - 1);
- }
- const V* searchList(const K& key, size_t h) const {
- if(nodePointers.getLength() == 0) {
- return nullptr;
- }
- for(const NodePointer& n : nodePointers[h]) {
- if(n->data.key == key) {
- return &n->data.value;
- }
- }
- return nullptr;
- }
- V* searchList(const K& key, size_t h) {
- return const_cast<V*>(
- static_cast<const HashMap*>(this)->searchList(key, h));
- }
- };
- }
- #endif
|