SDSL  3.0.0
Succinct Data Structure Library
lcp_vlc.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
4 /* \file lcp_vlc.hpp
5  * \brief lcp_vlc.hpp contains an implementation of a (compressed) LCP array.
6  * \author Simon Gog
7  */
8 #ifndef INCLUDED_SDSL_LCP_VLC
9 #define INCLUDED_SDSL_LCP_VLC
10 
11 #include <cassert>
12 #include <iostream>
13 #include <vector>
14 
15 #include <sdsl/int_vector.hpp>
16 #include <sdsl/iterators.hpp>
17 #include <sdsl/vlc_vector.hpp>
18 
19 namespace sdsl
20 {
21 
22 // A class for a compressed LCP array based on variable-length coding.
23 /*
24  * \tparam t_vlc_vec Type of the underlying variable-length coder.
25  */
26 template <class t_vlc_vec = vlc_vector<>>
27 class lcp_vlc
28 {
29  public:
30  typedef typename t_vlc_vec::value_type value_type;
33  typedef const value_type const_reference;
36  typedef const pointer const_pointer;
37  typedef typename t_vlc_vec::size_type size_type;
38  typedef typename t_vlc_vec::difference_type difference_type;
39  typedef t_vlc_vec vlc_vec_type;
40 
43 
44  enum
45  {
48  sa_order = 1
49  };
50 
51  template <class Cst>
52  using type = lcp_vlc;
53 
54  private:
55  vlc_vec_type m_vec;
56 
57  public:
59  lcp_vlc() = default;
60 
62  lcp_vlc(const lcp_vlc &) = default;
63  lcp_vlc(lcp_vlc &&) = default;
64  lcp_vlc & operator=(const lcp_vlc &) = default;
65  lcp_vlc & operator=(lcp_vlc &&) = default;
66 
68  lcp_vlc(cache_config & config, std::string other_key = "")
69  {
70  std::string lcp_key = conf::KEY_LCP;
71  if ("" != other_key) { lcp_key = other_key; }
72  int_vector_buffer<> lcp_buf(cache_file_name(lcp_key, config));
73  m_vec = vlc_vec_type(lcp_buf);
74  }
75 
77  size_type size() const { return m_vec.size(); }
78 
80  static size_type max_size() { return vlc_vec_type::max_size(); }
81 
83  bool empty() const { return m_vec.empty(); }
84 
86  const_iterator begin() const { return const_iterator(this, 0); }
87 
89  const_iterator end() const { return const_iterator(this, size()); }
90 
92  inline value_type operator[](size_type i) const { return m_vec[i]; }
93 
95  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
96  {
97  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
98  size_type written_bytes = 0;
99  written_bytes += m_vec.serialize(out, child, "vec");
100  structure_tree::add_size(child, written_bytes);
101  return written_bytes;
102  }
103 
105  void load(std::istream & in) { m_vec.load(in); }
106 
107  template <typename archive_t>
108  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
109  {
110  ar(CEREAL_NVP(m_vec));
111  }
112 
113  template <typename archive_t>
114  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
115  {
116  ar(CEREAL_NVP(m_vec));
117  }
118 
120  bool operator==(lcp_vlc const & other) const noexcept { return (m_vec == other.m_vec); }
121 
123  bool operator!=(lcp_vlc const & other) const noexcept { return !(*this == other); }
124 };
125 
126 } // end namespace sdsl
127 #endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
static size_type max_size()
Returns the largest size that lcp_vlc can ever have.
Definition: lcp_vlc.hpp:80
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Definition: lcp_vlc.hpp:114
const value_type const_reference
Definition: lcp_vlc.hpp:33
lcp_vlc(lcp_vlc &&)=default
const_iterator iterator
Definition: lcp_vlc.hpp:32
bool empty() const
Returns if the data strucutre is empty.
Definition: lcp_vlc.hpp:83
size_type size() const
Number of elements in the instance.
Definition: lcp_vlc.hpp:77
lcp_vlc & operator=(const lcp_vlc &)=default
lcp_vlc()=default
Default Constructor.
value_type operator[](size_type i) const
[]-operator
Definition: lcp_vlc.hpp:92
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Definition: lcp_vlc.hpp:108
const_iterator begin() const
Returns a const_iterator to the first element.
Definition: lcp_vlc.hpp:86
lcp_vlc(cache_config &config, std::string other_key="")
Construct.
Definition: lcp_vlc.hpp:68
bool operator==(lcp_vlc const &other) const noexcept
Equality operator.
Definition: lcp_vlc.hpp:120
bool operator!=(lcp_vlc const &other) const noexcept
Inequality operator.
Definition: lcp_vlc.hpp:123
t_vlc_vec::value_type value_type
Definition: lcp_vlc.hpp:30
random_access_const_iterator< lcp_vlc > const_iterator
Definition: lcp_vlc.hpp:31
void load(std::istream &in)
Load from a stream.
Definition: lcp_vlc.hpp:105
lcp_plain_tag lcp_category
Definition: lcp_vlc.hpp:41
t_vlc_vec vlc_vec_type
Definition: lcp_vlc.hpp:39
t_vlc_vec::difference_type difference_type
Definition: lcp_vlc.hpp:38
const_reference * pointer
Definition: lcp_vlc.hpp:35
lcp_tag index_category
Definition: lcp_vlc.hpp:42
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition: lcp_vlc.hpp:89
t_vlc_vec::size_type size_type
Definition: lcp_vlc.hpp:37
const pointer const_pointer
Definition: lcp_vlc.hpp:36
lcp_vlc(const lcp_vlc &)=default
Copy / Move constructor.
lcp_vlc & operator=(lcp_vlc &&)=default
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
Definition: lcp_vlc.hpp:95
const_reference reference
Definition: lcp_vlc.hpp:34
Generic iterator for a random access container.
Definition: iterators.hpp:24
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector.hpp contains the sdsl::int_vector class.
iterators.hpp contains an generic iterator for random access containers.
constexpr char KEY_LCP[]
Definition: config.hpp:44
int_vector ::size_type size_type
Namespace for the succinct data structure library.
std::string cache_file_name(const std::string &key, const cache_config &config)
Returns the file name of the resource.
Definition: io.hpp:630
Helper class for construction process.
Definition: config.hpp:67
vlc_vector.hpp contains a vector which stores the values with variable length codes.