BoundedNodeTrie.h

Go to the documentation of this file.

#ifndef INCLUDE_MOLASSEMBLER_TEMPLE_BOUNDED_NODE_TRIE_H
#define INCLUDE_MOLASSEMBLER_TEMPLE_BOUNDED_NODE_TRIE_H

#include <memory>
#include <cassert>

#include "Molassembler/Temple/Functional.h"

#include "boost/dynamic_bitset.hpp"

namespace Scine {
namespace Molassembler {
namespace Temple {

template<typename ChoiceIndex>
struct BoundedNodeTrie {
  static_assert(std::is_integral<ChoiceIndex>::value, "ChoiceIndex must be an integral type");

public:
  using ChoiceList = std::vector<ChoiceIndex>;
  using ChoosingFunction = std::function<ChoiceIndex(const std::vector<ChoiceIndex>&, const boost::dynamic_bitset<>&)>;

  BoundedNodeTrie() = default;
  BoundedNodeTrie(ChoiceList bounds) {
    setBounds(std::move(bounds));
  }


  bool insert(const ChoiceList& values) {
    // Ensure the bounds are set
    if(bounds_.empty()) {
      throw std::logic_error("No bounds are set!");
    }

    // Make sure we have a root to insert to
    if(!root_) {
      establishRoot_();
    }

    InsertResult result = root_->insert(values, bounds_, 0);

    if(result.insertedSomething) {
      ++size_;
    }

    return result.insertedSomething;
  }

  ChoiceList generateNewEntry(const ChoosingFunction& chooseFunction) {
    if(bounds_.empty()) {
      throw std::logic_error("No bounds are set!");
    }

    if(!root_) {
      establishRoot_();
    }

    if(size_ == capacity_) {
      throw std::logic_error("Trie is at capacity!");
    }

    ChoiceList values;
    values.reserve(bounds_.size());

    InsertResult result = root_->generate(chooseFunction, values, bounds_, 0);

    if(!result.insertedSomething) {
      throw std::logic_error("Trie has failed to generate a new entry");
    }

    ++size_;

    return values;
  }

  void setBounds(ChoiceList bounds) {
    bounds_ = std::move(bounds);

    // Make sure there is at least a single bound
    assert(!bounds_.empty());
    // For there to be a decision, there need to be at least two options
    assert(
      Temple::all_of(
        bounds_,
        [](const ChoiceIndex value) -> bool {
          return value > 1;
        }
      )
    );

    establishCapacity_();
    clear();
  }

  void clear() {
    if(root_) {
      root_.reset();
    }

    size_ = 0;
  }


  bool contains(const ChoiceList& values) const {
    if(!root_) {
      return false;
    }

    return root_->contains(values, 0);
  }

  const ChoiceList& bounds() const {
    return bounds_;
  }

  unsigned size() const {
    if(root_) {
      assert(root_->size() == size_);
    }

    return size_;
  }

  unsigned capacity() const {
    return capacity_;
  }

private:
  struct InsertResult {
    bool subtreeIsFull;
    bool insertedSomething;
  };

  struct AbstractNode {
    virtual ~AbstractNode() = default;

    virtual bool contains(const ChoiceList& values, unsigned depth) const = 0;

    virtual InsertResult insert(
      const ChoiceList& values,
      const ChoiceList& bounds,
      unsigned depth
    ) = 0;

    virtual InsertResult generate(
      const ChoosingFunction& choosingFunction,
      ChoiceList& values,
      const ChoiceList& bounds,
      unsigned depth
    ) = 0;

    virtual unsigned size() const = 0;
  };

  using NodePtr = std::unique_ptr<AbstractNode>;

  class Node final : public AbstractNode {
  public:
    Node(const ChoiceIndex U) : children(U), fullChildren(U) {
      assert(U > 1);
    }

    bool contains(const ChoiceList& values, const unsigned depth) const final {
      const ChoiceIndex& branch = values.at(depth);
      const NodePtr& childPtr = children.at(branch);

      if(!childPtr) {
        return false;
      }

      return childPtr->contains(values, depth + 1);
    }

    InsertResult insert(const ChoiceList& values, const ChoiceList& bounds, const unsigned depth) final {
      const ChoiceIndex& branchChoice = values.at(depth);
      NodePtr& childPtr = children.at(branchChoice);

      InsertResult subtreeResult;

      bool insertedSomething = false;
      if(!childPtr) {
        if(depth + 1 == bounds.size() - 1) {
          childPtr = std::make_unique<Leaf>(bounds.at(depth + 1));
        } else {
          childPtr = std::make_unique<Node>(bounds.at(depth + 1));
        }

        insertedSomething = true;
      }

      subtreeResult = childPtr->insert(values, bounds, depth + 1);
      subtreeResult.insertedSomething |= insertedSomething;

      if(subtreeResult.subtreeIsFull) {
        fullChildren.set(branchChoice);
      }

      subtreeResult.subtreeIsFull = fullChildren.all();

      return subtreeResult;
    }

    InsertResult generate(
      const ChoosingFunction& choosingFunction,
      ChoiceList& values,
      const ChoiceList& bounds,
      const unsigned depth
    ) final {
      // Prepare parameters for the choosing function
      const unsigned N = children.size();
      boost::dynamic_bitset<> existingChildren(N);
      for(unsigned i = 0; i < N; ++i) {
        if(children[i]) {
          existingChildren.set(i);
        }
      }

      std::vector<ChoiceIndex> viableIndices;
      viableIndices.reserve(N);
      for(unsigned i = 0; i < N; ++i) {
        if(!fullChildren.test(i)) {
          viableIndices.push_back(i);
        }
      }

      const ChoiceIndex choice = choosingFunction(viableIndices, existingChildren);
      assert(choice < N);
      assert(Temple::makeContainsPredicate(viableIndices)(choice));

      values.push_back(choice);
      NodePtr& childPtr = children.at(choice);

      bool insertedSomething = false;
      if(!childPtr) {
        insertedSomething = true;
        if(depth + 1 == bounds.size() - 1) {
          childPtr = std::make_unique<Leaf>(bounds.at(depth + 1));
        } else {
          childPtr = std::make_unique<Node>(bounds.at(depth + 1));
        }
      }

      InsertResult subtreeResult = childPtr->generate(choosingFunction, values, bounds, depth + 1);

      subtreeResult.insertedSomething |= insertedSomething;

      if(subtreeResult.subtreeIsFull) {
        fullChildren.set(choice);
      }

      subtreeResult.subtreeIsFull = fullChildren.all();

      return subtreeResult;
    }

    unsigned size() const final {
      unsigned count = 0;

      for(const NodePtr& nodePtr : children) {
        if(nodePtr) {
          count += nodePtr->size();
        }
      }

      return count;
    }

  private:
    std::vector<NodePtr> children;
    boost::dynamic_bitset<> fullChildren;
  };

  class Leaf final : public AbstractNode {
  public:
    Leaf(const ChoiceIndex U) : children(U) {
      assert(U > 1);
    }

    bool contains(const ChoiceList& values, const unsigned depth) const final {
      const ChoiceIndex& choice = values.at(depth);
      return children.test(choice);
    }

    InsertResult insert(const ChoiceList& values, const ChoiceList& /* bounds */, const unsigned depth) final {
      const ChoiceIndex& choice = values.at(depth);
      assert(choice < children.size());

      InsertResult result;
      result.insertedSomething = !children.test(choice);
      result.subtreeIsFull = children.all();

      children.set(choice);

      return result;
    }

    InsertResult generate(
      const ChoosingFunction& choosingFunction,
      ChoiceList& values,
      const ChoiceList& /* bounds */,
      const unsigned /* depth */
    ) final {
      std::vector<ChoiceIndex> viableIndices;
      const ChoiceIndex N = children.size();
      viableIndices.reserve(N);
      for(ChoiceIndex i = 0; i < N; ++i) {
        if(!children.test(i)) {
          viableIndices.push_back(i);
        }
      }

      const ChoiceIndex choice = choosingFunction(viableIndices, children);
      assert(choice < N);
      assert(Temple::makeContainsPredicate(viableIndices)(choice));

      InsertResult result;
      result.insertedSomething = !children.test(choice);

      values.push_back(choice);
      children.set(choice);

      result.subtreeIsFull = children.all();

      return result;
    }

    unsigned size() const final {
      return children.count();
    }

  private:
    boost::dynamic_bitset<> children;
  };

  void establishRoot_() {
    if(bounds_.size() == 1) {
      root_ = std::make_unique<Leaf>(bounds_.front());
    } else {
      root_ = std::make_unique<Node>(bounds_.front());
    }
  }

  void establishCapacity_() {
    capacity_ = Temple::accumulate(
      bounds_,
      1U,
      std::multiplies<>()
    );
  }

  ChoiceList bounds_;
  NodePtr root_;
  unsigned size_ = 0;
  unsigned capacity_ = 0;
};

} // namespace Temple
} // namespace Molassembler
} // namespace Scine

#endif