Transposition_Table.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
# ifndef TRANSPOSITION_TABLE_H
# define TRANSPOSITION_TABLE_H
 
#include <concepts>
#include <utility>
 
#include <state_search_common.H>
 
namespace Aleph {
 
enum class TranspositionBound
{
  Exact,        
  Lower_Bound,  
  Upper_Bound   
};
 
enum class TranspositionStoreStatus
{
  Inserted,  
  Replaced,  
  Rejected   
};
 
struct TranspositionStats
{
  size_t probes = 0;            
  size_t hits = 0;              
  size_t misses = 0;            
  size_t cutoffs = 0;           
  size_t stores = 0;            
  size_t replacements = 0;      
  size_t rejected_updates = 0;  
};
 
template <typename Policy, typename Entry>
concept TranspositionReplacementPolicy
  = requires(const Policy &policy, const Entry &candidate, const Entry &current) {
      { policy(candidate, current) } -> std::convertible_to<bool>;
    };
 
template <typename Table, typename Key, typename Entry>
concept MemoTable = requires(Table &table, const Key &key, const Entry &entry) {
  { table.probe(key) } -> std::same_as<Entry *>;
  { table.store(key, entry) } -> std::same_as<TranspositionStoreStatus>;
};
 
template <typename Entry>
struct Replace_Always
{
  bool operator()(const Entry &, const Entry &) const noexcept
  {
    return true;
  }
};
 
template <typename Entry>
  requires requires(const Entry &entry) {
    { entry.depth } -> std::convertible_to<size_t>;
  }
struct Prefer_Deeper_Entry
{
  bool operator()(const Entry &candidate, const Entry &current) const noexcept
  {
    return candidate.depth > current.depth;
  }
};
 
template <typename Key,
          typename Entry,
          template <typename, typename, class> class HashMapTable = MapOLhash,
          class Cmp = Aleph::equal_to<Key>,
          typename ReplacePolicy = Replace_Always<Entry>>
  requires TranspositionReplacementPolicy<ReplacePolicy, Entry>
class Transposition_Table
{
public:
  static constexpr bool enabled = true;  
 
  using Key_Type = Key;
  using Entry_Type = Entry;
  using Map_Type = SearchStorageMap<Key, Entry, HashMapTable, Cmp>;
  using Replace_Policy = ReplacePolicy;
 
  Transposition_Table() = default;
 
  explicit Transposition_Table(ReplacePolicy replace) : replace_(std::move(replace))
  {
    // empty
  }
 
  void clear() noexcept
  {
    table_.empty();
  }
 
  void reset_stats() noexcept
  {
    stats_ = {};
  }
 
  [[nodiscard]] size_t size() const noexcept
  {
    return table_.size();
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return table_.is_empty();
  }
 
  [[nodiscard]] const TranspositionStats &stats() const noexcept
  {
    return stats_;
  }
 
  [[nodiscard]] Entry *probe(const Key &key)
  {
    return probe_impl(key);
  }
 
  [[nodiscard]] Entry *probe(Key &&key)
  {
    return probe_impl(std::move(key));
  }
 
  [[nodiscard]] TranspositionStoreStatus store(const Key &key, const Entry &entry)
  {
    return store_impl(key, entry);
  }
 
  [[nodiscard]] TranspositionStoreStatus store(Key &&key, Entry entry)
  {
    return store_impl(std::move(key), std::move(entry));
  }
 
private:
  template <typename KeyLike>
  [[nodiscard]] Entry *probe_impl(KeyLike &&key)
  {
    ++stats_.probes;
 
    auto *pair = table_.search(std::forward<KeyLike>(key));
    if (pair == nullptr)
      {
        ++stats_.misses;
        return nullptr;
      }
 
    ++stats_.hits;
    return &pair->second;
  }
 
  template <typename KeyLike, typename EntryLike>
  [[nodiscard]] TranspositionStoreStatus store_impl(KeyLike &&key, EntryLike &&entry)
  {
    if (auto *current = table_.search(key); current != nullptr)
      {
        if (not replace_(entry, current->second))
          {
            ++stats_.rejected_updates;
            return TranspositionStoreStatus::Rejected;
          }
 
        current->second = std::forward<EntryLike>(entry);
        ++stats_.stores;
        ++stats_.replacements;
        return TranspositionStoreStatus::Replaced;
      }
 
    (void) table_.insert(std::forward<KeyLike>(key), std::forward<EntryLike>(entry));
    ++stats_.stores;
    return TranspositionStoreStatus::Inserted;
  }
 
  Map_Type table_;
  ReplacePolicy replace_ = {};
  TranspositionStats stats_;
};
 
}  // end namespace Aleph
 
# endif  // TRANSPOSITION_TABLE_H