wavelet_tree.h

Go to the documentation of this file.

#pragma once

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

enum class WaveletTreeBuildType { Standard, Huffman };

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

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

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

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

  std::vector<std::uint64_t> 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