tlx
string_ptr.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/sort/strings/string_ptr.hpp
3  *
4  * StringPtr, StringLcpPtr, StringShadowPtr, and StringShadowLcpPtr:
5  * Encapsulation of string, shadow and LCP array pointers.
6  *
7  * StringPtr -> (string,size)
8  * StringLcpPtr -> (string,lcp,size)
9  * StringShadowPtr -> (string,shadow,size,flip)
10  * StringShadowLcpPtr -> (string,shadow,lcp,size,flip)
11  *
12  * Part of tlx - http://panthema.net/tlx
13  *
14  * Copyright (C) 2013-2019 Timo Bingmann <tb@panthema.net>
15  * Copyright (C) 2013-2014 Andreas Eberle <email@andreas-eberle.com>
16  *
17  * All rights reserved. Published under the Boost Software License, Version 1.0
18  ******************************************************************************/
19 
20 #ifndef TLX_SORT_STRINGS_STRING_PTR_HEADER
21 #define TLX_SORT_STRINGS_STRING_PTR_HEADER
22 
24 
25 #include <algorithm>
26 #include <cassert>
27 #include <stdint.h>
28 
29 namespace tlx {
30 
31 //! \addtogroup tlx_sort
32 //! \{
33 
34 namespace sort_strings_detail {
35 
36 template <typename StringSet_>
37 class StringShadowPtr;
38 
39 template <typename StringSet_, typename LcpType_>
40 class StringShadowLcpPtr;
41 
42 /******************************************************************************/
43 // StringPtr
44 
45 //! Objectified string array pointer array.
46 template <typename StringSet_>
47 class StringPtr
48 {
49 public:
50  typedef StringSet_ StringSet;
51  typedef typename StringSet::String String;
52 
53 protected:
54  //! strings (front) array
56 
57 public:
58  //! constructor specifying all attributes
59  StringPtr(const StringSet& ss)
60  : active_(ss) { }
61 
62  //! return currently active array
63  const StringSet& active() const { return active_; }
64 
65  //! return valid length
66  size_t size() const { return active_.size(); }
67 
68  //! Advance (both) pointers by given offset, return sub-array
69  StringPtr sub(size_t offset, size_t sub_size) const {
70  assert(offset + sub_size <= size());
71  return StringPtr(active_.subi(offset, offset + sub_size));
72  }
73 
74  //! if we want to save the LCPs
75  static const bool with_lcp = false;
76 
77  //! set the i-th lcp to v and check its value
78  template <typename LcpType>
79  void set_lcp(size_t /* i */, const LcpType& /* v */) const { }
80 
81  //! fill entire LCP array with v, excluding the first lcp[0] position!
82  template <typename LcpType>
83  void fill_lcp(const LcpType& /* v */) const { }
84 
85  //! objectified string and shadow pointer class
87 
88  //! construct objectified string and shadow pointer class
89  WithShadow add_shadow(const StringSet& shadow) const;
90 };
91 
92 /******************************************************************************/
93 // StringLcpPtr
94 
95 //! Objectified string and LCP array pointer arrays.
96 template <typename StringSet_, typename LcpType_>
97 class StringLcpPtr
98 {
99 public:
100  typedef StringSet_ StringSet;
101  typedef LcpType_ LcpType;
102  typedef typename StringSet::String String;
103 
104 protected:
105  //! strings (front) array
107 
108  //! lcp array
109  LcpType* lcp_;
110 
111 public:
112  //! constructor specifying all attributes
113  StringLcpPtr(const StringSet& ss, LcpType* lcp)
114  : active_(ss), lcp_(lcp) { }
115 
116  //! return currently active array
117  const StringSet& active() const { return active_; }
118 
119  //! return valid length
120  size_t size() const { return active_.size(); }
121 
122  //! Advance (both) pointers by given offset, return sub-array
123  StringLcpPtr sub(size_t offset, size_t sub_size) const {
124  assert(offset + sub_size <= size());
125  return StringLcpPtr(active_.subi(offset, offset + sub_size),
126  lcp_ + offset);
127  }
128 
129  //! if we want to save the LCPs
130  static const bool with_lcp = true;
131 
132  //! return LCP array pointer
133  LcpType * lcp() const {
134  return lcp_;
135  }
136 
137  //! return LCP array value
138  LcpType get_lcp(size_t i) const {
139  assert(i < size());
140  return lcp_[i];
141  }
142 
143  //! set the i-th lcp to v and check its value
144  void set_lcp(size_t i, const LcpType& v) const {
145  assert(i < size());
146  lcp_[i] = v;
147  }
148 
149  //! fill entire LCP array with v, excluding the first lcp[0] position!
150  void fill_lcp(const LcpType& v) const {
151  for (size_t i = 1; i < size(); ++i)
152  set_lcp(i, v);
153  }
154 
155  //! objectified string and shadow pointer class
157 
158  //! construct objectified string and shadow pointer class
159  WithShadow add_shadow(const StringSet& shadow) const;
160 };
161 
162 /******************************************************************************/
163 // StringShadowPtr
164 
165 //! Objectified string array pointer and shadow pointer array for out-of-place
166 //! swapping of pointers.
167 template <typename StringSet_>
168 class StringShadowPtr
169 {
170 public:
171  typedef StringSet_ StringSet;
172  typedef typename StringSet::String String;
173  typedef typename StringSet::Iterator Iterator;
174 
175 protected:
176  //! strings (front) and temporary shadow (back) array
178 
179  //! false if active_ is original, true if shadow_ is original
180  bool flipped_;
181 
182 public:
183  //! constructor specifying all attributes
184  StringShadowPtr(const StringSet& original, const StringSet& shadow,
185  bool flipped = false)
186  : active_(original), shadow_(shadow), flipped_(flipped) { }
187 
188  //! return currently active array
189  const StringSet& active() const { return active_; }
190 
191  //! return current shadow array
192  const StringSet& shadow() const { return shadow_; }
193 
194  //! true if flipped to back array
195  bool flipped() const { return flipped_; }
196 
197  //! return valid length
198  size_t size() const { return active_.size(); }
199 
200  //! Advance (both) pointers by given offset, return sub-array without flip
201  StringShadowPtr sub(size_t offset, size_t sub_size) const {
202  assert(offset + sub_size <= size());
203  return StringShadowPtr(active_.subi(offset, offset + sub_size),
204  shadow_.subi(offset, offset + sub_size),
205  flipped_);
206  }
207 
208  //! construct a StringShadowPtr object specifying a sub-array with flipping
209  //! to other array.
210  StringShadowPtr flip(size_t offset, size_t sub_size) const {
211  assert(offset + sub_size <= size());
212  return StringShadowPtr(shadow_.subi(offset, offset + sub_size),
213  active_.subi(offset, offset + sub_size),
214  !flipped_);
215  }
216 
217  //! return subarray pointer to n strings in original array, might copy from
218  //! shadow before returning.
219  StringShadowPtr copy_back() const {
220  if (!flipped_) {
221  return *this;
222  }
223  else {
224  std::move(active_.begin(), active_.end(), shadow_.begin());
226  }
227  }
228 
229  //! if we want to save the LCPs
230  static const bool with_lcp = false;
231 
232  //! set the i-th lcp to v and check its value
233  template <typename LcpType>
234  void set_lcp(size_t /* i */, const LcpType& /* v */) const { }
235 
236  //! fill entire LCP array with v, excluding the first lcp[0] position!
237  template <typename LcpType>
238  void fill_lcp(const LcpType& /* v */) const { }
239 };
240 
241 /******************************************************************************/
242 // StringShadowLcpPtr
243 
244 //! Objectified string array pointer and shadow pointer array for out-of-place
245 //! swapping of pointers.
246 template <typename StringSet_, typename LcpType_>
248 {
249 public:
250  typedef StringSet_ StringSet;
251  typedef LcpType_ LcpType;
252  typedef typename StringSet::String String;
253  typedef typename StringSet::Iterator Iterator;
254 
255 protected:
256  //! strings (front) and temporary shadow (back) array
258 
259  //! lcp array
260  LcpType* lcp_;
261 
262  //! false if active_ is original, true if shadow_ is original
263  bool flipped_;
264 
265 public:
266  //! constructor specifying all attributes
267  StringShadowLcpPtr(const StringSet& original, const StringSet& shadow,
268  LcpType* lcp, bool flipped = false)
269  : active_(original), shadow_(shadow), lcp_(lcp), flipped_(flipped) { }
270 
271  //! return currently active array
272  const StringSet& active() const { return active_; }
273 
274  //! return current shadow array
275  const StringSet& shadow() const { return shadow_; }
276 
277  //! true if flipped to back array
278  bool flipped() const { return flipped_; }
279 
280  //! return valid length
281  size_t size() const { return active_.size(); }
282 
283  //! Advance (both) pointers by given offset, return sub-array without flip
284  StringShadowLcpPtr sub(size_t offset, size_t sub_size) const {
285  assert(offset + sub_size <= size());
286  return StringShadowLcpPtr(active_.subi(offset, offset + sub_size),
287  shadow_.subi(offset, offset + sub_size),
288  lcp_ + offset, flipped_);
289  }
290 
291  //! construct a StringShadowLcpPtr object specifying a sub-array with
292  //! flipping to other array.
293  StringShadowLcpPtr flip(size_t offset, size_t sub_size) const {
294  assert(offset + sub_size <= size());
295  return StringShadowLcpPtr(shadow_.subi(offset, offset + sub_size),
296  active_.subi(offset, offset + sub_size),
297  lcp_ + offset, !flipped_);
298  }
299 
300  //! return subarray pointer to n strings in original array, might copy from
301  //! shadow before returning.
302  StringShadowLcpPtr copy_back() const {
303  if (!flipped_) {
304  return *this;
305  }
306  else {
307  std::move(active_.begin(), active_.end(), shadow_.begin());
309  }
310  }
311 
312  //! if we want to save the LCPs
313  static const bool with_lcp = true;
314 
315  //! return LCP array pointer
316  LcpType * lcp() const {
317  return lcp_;
318  }
319 
320  //! return LCP array value
321  LcpType get_lcp(size_t i) const {
322  assert(i < size());
323  return lcp_[i];
324  }
325 
326  //! set the i-th lcp to v and check its value
327  void set_lcp(size_t i, const LcpType& v) const {
328  assert(i < size());
329  lcp_[i] = v;
330  }
331 
332  //! fill entire LCP array with v, excluding the first lcp[0] position!
333  void fill_lcp(const LcpType& v) const {
334  for (size_t i = 1; i < size(); ++i)
335  set_lcp(i, v);
336  }
337 };
338 
339 /******************************************************************************/
340 
341 template <typename StringSet_>
343 StringPtr<StringSet_>::add_shadow(const StringSet_& shadow) const {
344  return StringShadowPtr<StringSet_>(active_, shadow);
345 }
346 
347 template <typename StringSet_, typename LcpType_>
349 StringLcpPtr<StringSet_, LcpType_>::add_shadow(const StringSet_& shadow) const {
350  return StringShadowLcpPtr<StringSet_, LcpType_>(active_, shadow, lcp_);
351 }
352 
353 /******************************************************************************/
354 
355 } // namespace sort_strings_detail
356 
357 //! \}
358 
359 } // namespace tlx
360 
361 #endif // !TLX_SORT_STRINGS_STRING_PTR_HEADER
362 
363 /******************************************************************************/
tlx::sort_strings_detail::StringShadowLcpPtr::StringShadowLcpPtr
StringShadowLcpPtr(const StringSet &original, const StringSet &shadow, LcpType *lcp, bool flipped=false)
constructor specifying all attributes
Definition: string_ptr.hpp:284
tlx::sort_strings_detail::StringShadowLcpPtr::String
StringSet::String String
Definition: string_ptr.hpp:269
tlx::sort_strings_detail::StringPtr::String
StringSet::String String
Definition: string_ptr.hpp:68
tlx::sort_strings_detail::StringShadowLcpPtr::fill_lcp
void fill_lcp(const LcpType &v) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:350
tlx::sort_strings_detail::StringShadowLcpPtr::active
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:289
tlx::sort_strings_detail::StringShadowPtr
Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers.
Definition: string_ptr.hpp:54
tlx::sort_strings_detail::StringPtr::set_lcp
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:96
tlx::sort_strings_detail::StringShadowLcpPtr::copy_back
StringShadowLcpPtr copy_back() const
return subarray pointer to n strings in original array, might copy from shadow before returning.
Definition: string_ptr.hpp:319
tlx::sort_strings_detail::StringLcpPtr
Objectified string and LCP array pointer arrays.
Definition: string_ptr.hpp:114
tlx::sort_strings_detail::StringShadowLcpPtr::Iterator
StringSet::Iterator Iterator
Definition: string_ptr.hpp:270
string_set.hpp
tlx::sort_strings_detail::StringShadowPtr::fill_lcp
void fill_lcp(const LcpType &) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:255
tlx::sort_strings_detail::StringPtr::WithShadow
StringShadowPtr< StringSet_ > WithShadow
objectified string and shadow pointer class
Definition: string_ptr.hpp:103
tlx::sort_strings_detail::StringShadowPtr::sub
StringShadowPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array without flip.
Definition: string_ptr.hpp:218
tlx::sort_strings_detail::StringPtr::active_
StringSet active_
strings (front) array
Definition: string_ptr.hpp:72
tlx::sort_strings_detail::StringShadowLcpPtr::shadow
const StringSet & shadow() const
return current shadow array
Definition: string_ptr.hpp:292
tlx::sort_strings_detail::StringShadowPtr::StringShadowPtr
StringShadowPtr(const StringSet &original, const StringSet &shadow, bool flipped=false)
constructor specifying all attributes
Definition: string_ptr.hpp:201
tlx::sort_strings_detail::StringPtr::sub
StringPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
Definition: string_ptr.hpp:86
tlx::sort_strings_detail::StringShadowPtr::flipped
bool flipped() const
true if flipped to back array
Definition: string_ptr.hpp:212
tlx::sort_strings_detail::StringShadowLcpPtr::with_lcp
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:330
tlx::sort_strings_detail::StringShadowLcpPtr::sub
StringShadowLcpPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array without flip.
Definition: string_ptr.hpp:301
tlx::sort_strings_detail::StringShadowPtr::active_
StringSet active_
strings (front) and temporary shadow (back) array
Definition: string_ptr.hpp:194
tlx::sort_strings_detail::StringShadowPtr::set_lcp
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:251
tlx::sort_strings_detail::StringPtr::active
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:80
tlx::sort_strings_detail::StringLcpPtr::LcpType
LcpType_ LcpType
Definition: string_ptr.hpp:118
tlx::sort_strings_detail::StringShadowLcpPtr::get_lcp
LcpType get_lcp(size_t i) const
return LCP array value
Definition: string_ptr.hpp:338
tlx::sort_strings_detail::StringLcpPtr::size
size_t size() const
return valid length
Definition: string_ptr.hpp:137
tlx::sort_strings_detail::StringShadowLcpPtr::lcp
LcpType * lcp() const
return LCP array pointer
Definition: string_ptr.hpp:333
tlx::sort_strings_detail::StringShadowLcpPtr::lcp_
LcpType * lcp_
lcp array
Definition: string_ptr.hpp:277
tlx::sort_strings_detail::StringShadowPtr::with_lcp
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:247
tlx::sort_strings_detail::StringShadowPtr::flip
StringShadowPtr flip(size_t offset, size_t sub_size) const
construct a StringShadowPtr object specifying a sub-array with flipping to other array.
Definition: string_ptr.hpp:227
tlx::sort_strings_detail::StringPtr::with_lcp
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:92
tlx::sort_strings_detail::StringLcpPtr::String
StringSet::String String
Definition: string_ptr.hpp:119
tlx::sort_strings_detail::StringLcpPtr::fill_lcp
void fill_lcp(const LcpType &v) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:167
tlx::sort_strings_detail::StringLcpPtr::sub
StringLcpPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
Definition: string_ptr.hpp:140
tlx::sort_strings_detail::StringLcpPtr::set_lcp
void set_lcp(size_t i, const LcpType &v) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:161
tlx
Definition: exclusive_scan.hpp:17
tlx::sort_strings_detail::StringLcpPtr::with_lcp
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:147
tlx::sort_strings_detail::StringPtr::StringSet
StringSet_ StringSet
Definition: string_ptr.hpp:67
tlx::sort_strings_detail::StringShadowLcpPtr::flipped_
bool flipped_
false if active_ is original, true if shadow_ is original
Definition: string_ptr.hpp:280
tlx::sort_strings_detail::StringLcpPtr::get_lcp
LcpType get_lcp(size_t i) const
return LCP array value
Definition: string_ptr.hpp:155
tlx::sort_strings_detail::StringShadowLcpPtr::shadow_
StringSet shadow_
Definition: string_ptr.hpp:274
tlx::sort_strings_detail::StringShadowLcpPtr::active_
StringSet active_
strings (front) and temporary shadow (back) array
Definition: string_ptr.hpp:274
tlx::sort_strings_detail::StringShadowPtr::shadow
const StringSet & shadow() const
return current shadow array
Definition: string_ptr.hpp:209
tlx::sort_strings_detail::StringShadowPtr::flipped_
bool flipped_
false if active_ is original, true if shadow_ is original
Definition: string_ptr.hpp:197
tlx::sort_strings_detail::StringShadowPtr::size
size_t size() const
return valid length
Definition: string_ptr.hpp:215
tlx::sort_strings_detail::StringShadowPtr::copy_back
StringShadowPtr copy_back() const
return subarray pointer to n strings in original array, might copy from shadow before returning.
Definition: string_ptr.hpp:236
tlx::sort_strings_detail::StringShadowLcpPtr
Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers.
Definition: string_ptr.hpp:57
tlx::sort_strings_detail::StringShadowPtr::String
StringSet::String String
Definition: string_ptr.hpp:189
tlx::sort_strings_detail::StringShadowPtr::shadow_
StringSet shadow_
Definition: string_ptr.hpp:194
tlx::sort_strings_detail::StringLcpPtr::StringSet
StringSet_ StringSet
Definition: string_ptr.hpp:117
tlx::sort_strings_detail::StringLcpPtr::active_
StringSet active_
strings (front) array
Definition: string_ptr.hpp:123
tlx::sort_strings_detail::StringShadowLcpPtr::LcpType
LcpType_ LcpType
Definition: string_ptr.hpp:268
tlx::sort_strings_detail::StringShadowLcpPtr::set_lcp
void set_lcp(size_t i, const LcpType &v) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:344
tlx::sort_strings_detail::StringPtr
Objectified string array pointer array.
Definition: string_ptr.hpp:64
tlx::sort_strings_detail::StringShadowLcpPtr::flip
StringShadowLcpPtr flip(size_t offset, size_t sub_size) const
construct a StringShadowLcpPtr object specifying a sub-array with flipping to other array.
Definition: string_ptr.hpp:310
tlx::sort_strings_detail::StringLcpPtr::StringLcpPtr
StringLcpPtr(const StringSet &ss, LcpType *lcp)
constructor specifying all attributes
Definition: string_ptr.hpp:130
tlx::sort_strings_detail::StringLcpPtr::add_shadow
WithShadow add_shadow(const StringSet &shadow) const
construct objectified string and shadow pointer class
Definition: string_ptr.hpp:366
tlx::sort_strings_detail::StringLcpPtr::WithShadow
StringShadowLcpPtr< StringSet_, LcpType_ > WithShadow
objectified string and shadow pointer class
Definition: string_ptr.hpp:173
tlx::sort_strings_detail::StringPtr::add_shadow
WithShadow add_shadow(const StringSet &shadow) const
construct objectified string and shadow pointer class
Definition: string_ptr.hpp:360
tlx::sort_strings_detail::StringShadowLcpPtr::size
size_t size() const
return valid length
Definition: string_ptr.hpp:298
tlx::sort_strings_detail::StringPtr::fill_lcp
void fill_lcp(const LcpType &) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:100
tlx::sort_strings_detail::StringPtr::size
size_t size() const
return valid length
Definition: string_ptr.hpp:83
tlx::sort_strings_detail::StringLcpPtr::lcp_
LcpType * lcp_
lcp array
Definition: string_ptr.hpp:126
tlx::sort_strings_detail::StringShadowPtr::Iterator
StringSet::Iterator Iterator
Definition: string_ptr.hpp:190
tlx::sort_strings_detail::StringShadowPtr::StringSet
StringSet_ StringSet
Definition: string_ptr.hpp:188
tlx::sort_strings_detail::StringShadowLcpPtr::StringSet
StringSet_ StringSet
Definition: string_ptr.hpp:267
tlx::sort_strings_detail::StringLcpPtr::lcp
LcpType * lcp() const
return LCP array pointer
Definition: string_ptr.hpp:150
tlx::sort_strings_detail::StringShadowLcpPtr::flipped
bool flipped() const
true if flipped to back array
Definition: string_ptr.hpp:295
tlx::sort_strings_detail::StringPtr::StringPtr
StringPtr(const StringSet &ss)
constructor specifying all attributes
Definition: string_ptr.hpp:76
tlx::sort_strings_detail::StringLcpPtr::active
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:134
tlx::sort_strings_detail::StringShadowPtr::active
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:206