Thrill  0.1
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 <[email protected]>
15  * Copyright (C) 2013-2014 Andreas Eberle <[email protected]>
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_>
38 
39 template <typename StringSet_, typename LcpType_>
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
55  StringSet active_;
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_>
98 {
99 public:
100  typedef StringSet_ StringSet;
101  typedef LcpType_ LcpType;
102  typedef typename StringSet::String String;
103 
104 protected:
105  //! strings (front) array
106  StringSet active_;
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
177  StringSet active_, shadow_;
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.
220  if (!flipped_) {
221  return *this;
222  }
223  else {
224  std::move(active_.begin(), active_.end(), shadow_.begin());
225  return StringShadowPtr(shadow_, active_, !flipped_);
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_>
247 class StringShadowLcpPtr
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
257  StringSet active_, shadow_;
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.
303  if (!flipped_) {
304  return *this;
305  }
306  else {
307  std::move(active_.begin(), active_.end(), shadow_.begin());
308  return StringShadowLcpPtr(shadow_, active_, lcp_, !flipped_);
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 {
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 /******************************************************************************/
size_t size() const
return valid length
Definition: string_ptr.hpp:66
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:117
StringLcpPtr(const StringSet &ss, LcpType *lcp)
constructor specifying all attributes
Definition: string_ptr.hpp:113
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:189
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:272
bool flipped() const
true if flipped to back array
Definition: string_ptr.hpp:278
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:201
void fill_lcp(const LcpType &) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:238
void fill_lcp(const LcpType &v) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:333
StringSet active_
strings (front) array
Definition: string_ptr.hpp:55
StringShadowPtr(const StringSet &original, const StringSet &shadow, bool flipped=false)
constructor specifying all attributes
Definition: string_ptr.hpp:184
const StringSet & shadow() const
return current shadow array
Definition: string_ptr.hpp:275
void fill_lcp(const LcpType &v) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:150
bool flipped() const
true if flipped to back array
Definition: string_ptr.hpp:195
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:79
StringLcpPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
Definition: string_ptr.hpp:123
StringShadowPtr< StringSet_ > WithShadow
objectified string and shadow pointer class
Definition: string_ptr.hpp:86
LcpType * lcp() const
return LCP array pointer
Definition: string_ptr.hpp:316
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:234
StringPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
Definition: string_ptr.hpp:69
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:284
size_t size() const
return valid length
Definition: string_ptr.hpp:120
StringShadowPtr flip(size_t offset, size_t sub_size) const
Definition: string_ptr.hpp:210
bool flipped_
false if active_ is original, true if shadow_ is original
Definition: string_ptr.hpp:180
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:75
LcpType get_lcp(size_t i) const
return LCP array value
Definition: string_ptr.hpp:321
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:63
bool flipped_
false if active_ is original, true if shadow_ is original
Definition: string_ptr.hpp:263
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:144
WithShadow add_shadow(const StringSet &shadow) const
construct objectified string and shadow pointer class
Definition: string_ptr.hpp:343
Objectified string and LCP array pointer arrays.
Definition: string_ptr.hpp:97
StringSet active_
strings (front) array
Definition: string_ptr.hpp:106
void fill_lcp(const LcpType &) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:83
size_t size() const
return valid length
Definition: string_ptr.hpp:198
StringShadowLcpPtr< StringSet_, LcpType_ > WithShadow
objectified string and shadow pointer class
Definition: string_ptr.hpp:156
LcpType get_lcp(size_t i) const
return LCP array value
Definition: string_ptr.hpp:138
const StringSet & shadow() const
return current shadow array
Definition: string_ptr.hpp:192
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:327
StringPtr(const StringSet &ss)
constructor specifying all attributes
Definition: string_ptr.hpp:59
LcpType * lcp() const
return LCP array pointer
Definition: string_ptr.hpp:133
Objectified string array pointer array.
Definition: string_ptr.hpp:47
StringShadowLcpPtr flip(size_t offset, size_t sub_size) const
Definition: string_ptr.hpp:293
size_t size() const
return valid length
Definition: string_ptr.hpp:281
WithShadow add_shadow(const StringSet &shadow) const
construct objectified string and shadow pointer class
Definition: string_ptr.hpp:349
StringShadowLcpPtr(const StringSet &original, const StringSet &shadow, LcpType *lcp, bool flipped=false)
constructor specifying all attributes
Definition: string_ptr.hpp:267