wavelet_tree.h

Go to the documentation of this file.

#pragma once

 
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <vector>
 
namespace pixie {

enum class WaveletTreeBuildType { Standard, Huffman };

template <class T>
concept WaveletTreeSymbol = std::unsigned_integral<T> && !std::same_as<T, bool>;

template <class Impl, WaveletTreeSymbol Symbol>
class WaveletTreeBase {
 public:
  std::size_t size() const { return impl().size_impl(); }

  bool empty() const { return size() == 0; }

  std::size_t rank(Symbol symbol, std::size_t end_position) const {
    return impl().rank_impl(symbol, end_position);
  }

  std::size_t select(Symbol symbol, std::size_t rank) const {
    return impl().select_impl(symbol, rank);
  }

  std::vector<Symbol> get_segment(std::size_t begin, std::size_t end) const {
    return impl().get_segment_impl(begin, end);
  }
 
 private:
  const Impl& impl() const { return static_cast<const Impl&>(*this); }
};
 
}  // namespace pixie