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
29namespace tlx {
30
31//! \addtogroup tlx_sort
32//! \{
33
34namespace sort_strings_detail {
35
36template <typename StringSet_>
37class StringShadowPtr;
38
39template <typename StringSet_, typename LcpType_>
40class StringShadowLcpPtr;
41
42/******************************************************************************/
43// StringPtr
44
45//! Objectified string array pointer array.
46template <typename StringSet_>
48{
49public:
50 typedef StringSet_ StringSet;
51 typedef typename StringSet::String String;
52
53protected:
54 //! strings (front) array
56
57public:
58 //! constructor specifying all attributes
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.
96template <typename StringSet_, typename LcpType_>
98{
99public:
100 typedef StringSet_ StringSet;
101 typedef LcpType_ LcpType;
102 typedef typename StringSet::String String;
103
104protected:
105 //! strings (front) array
107
108 //! lcp array
110
111public:
112 //! constructor specifying all attributes
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.
167template <typename StringSet_>
169{
170public:
171 typedef StringSet_ StringSet;
172 typedef typename StringSet::String String;
173 typedef typename StringSet::Iterator Iterator;
174
175protected:
176 //! strings (front) and temporary shadow (back) array
178
179 //! false if active_ is original, true if shadow_ is original
181
182public:
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());
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.
246template <typename StringSet_, typename LcpType_>
248{
249public:
250 typedef StringSet_ StringSet;
251 typedef LcpType_ LcpType;
252 typedef typename StringSet::String String;
253 typedef typename StringSet::Iterator Iterator;
254
255protected:
256 //! strings (front) and temporary shadow (back) array
258
259 //! lcp array
261
262 //! false if active_ is original, true if shadow_ is original
264
265public:
266 //! constructor specifying all attributes
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());
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
341template <typename StringSet_>
342StringShadowPtr<StringSet_>
343StringPtr<StringSet_>::add_shadow(const StringSet_& shadow) const {
344 return StringShadowPtr<StringSet_>(active_, shadow);
345}
346
347template <typename StringSet_, typename LcpType_>
349StringLcpPtr<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/******************************************************************************/
Objectified string and LCP array pointer arrays.
Definition: string_ptr.hpp:98
StringShadowLcpPtr< StringSet_, LcpType_ > WithShadow
objectified string and shadow pointer class
Definition: string_ptr.hpp:156
StringLcpPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
Definition: string_ptr.hpp:123
size_t size() const
return valid length
Definition: string_ptr.hpp:120
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:117
LcpType * lcp() const
return LCP array pointer
Definition: string_ptr.hpp:133
LcpType get_lcp(size_t i) const
return LCP array value
Definition: string_ptr.hpp:138
StringSet active_
strings (front) array
Definition: string_ptr.hpp:106
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:130
void fill_lcp(const LcpType &v) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:150
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:349
StringLcpPtr(const StringSet &ss, LcpType *lcp)
constructor specifying all attributes
Definition: string_ptr.hpp:113
Objectified string array pointer array.
Definition: string_ptr.hpp:48
StringShadowPtr< StringSet_ > WithShadow
objectified string and shadow pointer class
Definition: string_ptr.hpp:86
size_t size() const
return valid length
Definition: string_ptr.hpp:66
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:63
StringPtr(const StringSet &ss)
constructor specifying all attributes
Definition: string_ptr.hpp:59
StringPtr sub(size_t offset, size_t sub_size) const
Advance (both) pointers by given offset, return sub-array.
Definition: string_ptr.hpp:69
void fill_lcp(const LcpType &) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:83
StringSet active_
strings (front) array
Definition: string_ptr.hpp:55
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:75
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:79
WithShadow add_shadow(const StringSet &shadow) const
construct objectified string and shadow pointer class
Definition: string_ptr.hpp:343
Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers.
Definition: string_ptr.hpp:248
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:281
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:272
LcpType * lcp() const
return LCP array pointer
Definition: string_ptr.hpp:316
const StringSet & shadow() const
return current shadow array
Definition: string_ptr.hpp:275
StringShadowLcpPtr copy_back() const
return subarray pointer to n strings in original array, might copy from shadow before returning.
Definition: string_ptr.hpp:302
StringShadowLcpPtr(const StringSet &original, const StringSet &shadow, LcpType *lcp, bool flipped=false)
constructor specifying all attributes
Definition: string_ptr.hpp:267
bool flipped() const
true if flipped to back array
Definition: string_ptr.hpp:278
LcpType get_lcp(size_t i) const
return LCP array value
Definition: string_ptr.hpp:321
bool flipped_
false if active_ is original, true if shadow_ is original
Definition: string_ptr.hpp:263
StringSet active_
strings (front) and temporary shadow (back) array
Definition: string_ptr.hpp:257
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:313
void fill_lcp(const LcpType &v) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:333
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
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:293
Objectified string array pointer and shadow pointer array for out-of-place swapping of pointers.
Definition: string_ptr.hpp:169
size_t size() const
return valid length
Definition: string_ptr.hpp:198
const StringSet & active() const
return currently active array
Definition: string_ptr.hpp:189
const StringSet & shadow() const
return current shadow array
Definition: string_ptr.hpp:192
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:210
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
bool flipped() const
true if flipped to back array
Definition: string_ptr.hpp:195
bool flipped_
false if active_ is original, true if shadow_ is original
Definition: string_ptr.hpp:180
StringShadowPtr(const StringSet &original, const StringSet &shadow, bool flipped=false)
constructor specifying all attributes
Definition: string_ptr.hpp:184
void fill_lcp(const LcpType &) const
fill entire LCP array with v, excluding the first lcp[0] position!
Definition: string_ptr.hpp:238
StringShadowPtr copy_back() const
return subarray pointer to n strings in original array, might copy from shadow before returning.
Definition: string_ptr.hpp:219
StringSet active_
strings (front) and temporary shadow (back) array
Definition: string_ptr.hpp:177
static const bool with_lcp
if we want to save the LCPs
Definition: string_ptr.hpp:230
void set_lcp(size_t, const LcpType &) const
set the i-th lcp to v and check its value
Definition: string_ptr.hpp:234