Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
string_set.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/sort/strings/string_set.hpp
3  *
4  * Implementations of a StringSet concept. This is an internal implementation
5  * header, see tlx/sort/strings.hpp for public front-end functions.
6  *
7  * A StringSet abstracts from arrays of strings, we provide six abstractions:
8  *
9  * - UCharStringSet: (const) unsigned char**
10  * - StdStringSet: std::string*
11  * - UPtrStdStringSet: std::unique_ptr<std::string>*
12  * - StringSuffixSet: suffix sorting indexes of a std::string text
13  *
14  * Part of tlx - http://panthema.net/tlx
15  *
16  * Copyright (C) 2015-2018 Timo Bingmann <[email protected]>
17  *
18  * All rights reserved. Published under the Boost Software License, Version 1.0
19  ******************************************************************************/
20 
21 #ifndef TLX_SORT_STRINGS_STRING_SET_HEADER
22 #define TLX_SORT_STRINGS_STRING_SET_HEADER
23 
24 #include <cassert>
25 #include <cstdint>
26 #include <memory>
27 #include <string>
28 #include <utility>
29 #include <vector>
30 
31 #include <tlx/logger/core.hpp>
32 #include <tlx/math/bswap.hpp>
33 
34 namespace tlx {
35 namespace sort_strings_detail {
36 
37 /******************************************************************************/
38 
39 /*!
40  * Base class for common string set functions, included via CRTP.
41  */
42 template <typename StringSet, typename Traits>
44 {
45 public:
46  //! \name CharIterator Comparisons
47  //! \{
48 
49  //! check equality of two strings a and b at char iterators ai and bi.
50  bool is_equal(const typename Traits::String& a,
51  const typename Traits::CharIterator& ai,
52  const typename Traits::String& b,
53  const typename Traits::CharIterator& bi) const {
54  const StringSet& ss = *static_cast<const StringSet*>(this);
55  return !ss.is_end(a, ai) && !ss.is_end(b, bi) && (*ai == *bi);
56  }
57 
58  //! check if string a is less or equal to string b at iterators ai and bi.
59  bool is_leq(const typename Traits::String& a,
60  const typename Traits::CharIterator& ai,
61  const typename Traits::String& b,
62  const typename Traits::CharIterator& bi) const {
63  const StringSet& ss = *static_cast<const StringSet*>(this);
64  return ss.is_end(a, ai) ||
65  (!ss.is_end(a, ai) && !ss.is_end(b, bi) && *ai <= *bi);
66  }
67 
68  //! \}
69 
70  //! \name Character Extractors
71  //! \{
72 
73  typename Traits::Char
74  get_char(const typename Traits::String& s, size_t depth) const {
75  const StringSet& ss = *static_cast<const StringSet*>(this);
76  return *ss.get_chars(s, depth);
77  }
78 
79  //! Return up to 1 characters of string s at iterator i packed into a
80  //! uint8_t (only works correctly for 8-bit characters)
81  uint8_t get_uint8(
82  const typename Traits::String& s, typename Traits::CharIterator i) const {
83  const StringSet& ss = *static_cast<const StringSet*>(this);
84 
85  if (ss.is_end(s, i)) return 0;
86  return uint8_t(*i);
87  }
88 
89  //! Return up to 2 characters of string s at iterator i packed into a
90  //! uint16_t (only works correctly for 8-bit characters)
91  uint16_t get_uint16(
92  const typename Traits::String& s, typename Traits::CharIterator i) const {
93  const StringSet& ss = *static_cast<const StringSet*>(this);
94 
95  uint16_t v = 0;
96  if (ss.is_end(s, i)) return v;
97  v = (uint16_t(*i) << 8);
98  ++i;
99  if (ss.is_end(s, i)) return v;
100  v |= (uint16_t(*i) << 0);
101  return v;
102  }
103 
104  uint8_t get_uint8(const typename Traits::String& s, size_t depth) const {
105  const StringSet& ss = *static_cast<const StringSet*>(this);
106  return get_uint8(s, ss.get_chars(s, depth));
107  }
108 
109  uint16_t get_uint16(const typename Traits::String& s, size_t depth) const {
110  const StringSet& ss = *static_cast<const StringSet*>(this);
111  return get_uint16(s, ss.get_chars(s, depth));
112  }
113 
114  //! \}
115 
116  //! Subset this string set using index range.
117  StringSet subi(size_t begin, size_t end) const {
118  const StringSet& ss = *static_cast<const StringSet*>(this);
119  return ss.sub(ss.begin() + begin, ss.begin() + end);
120  }
121 
122  bool check_order(const typename Traits::String& s1,
123  const typename Traits::String& s2) const {
124  const StringSet& ss = *static_cast<const StringSet*>(this);
125 
126  typename StringSet::CharIterator c1 = ss.get_chars(s1, 0);
127  typename StringSet::CharIterator c2 = ss.get_chars(s2, 0);
128 
129  while (ss.is_equal(s1, c1, s2, c2))
130  ++c1, ++c2;
131 
132  return ss.is_leq(s1, c1, s2, c2);
133  }
134 
135  bool check_order() const {
136  const StringSet& ss = *static_cast<const StringSet*>(this);
137 
138  for (typename Traits::Iterator pi = ss.begin() + 1;
139  pi != ss.end(); ++pi)
140  {
141  if (!check_order(ss[pi - 1], ss[pi])) {
142  TLX_LOG1 << "check_order() failed at position " << pi - ss.begin();
143  return false;
144  }
145  }
146  return true;
147  }
148 
149  void print() const {
150  const StringSet& ss = *static_cast<const StringSet*>(this);
151  size_t i = 0;
152  for (typename Traits::Iterator pi = ss.begin(); pi != ss.end(); ++pi)
153  {
154  TLX_LOG1 << "[" << i++ << "] = " << *pi
155  << " = " << ss.get_string(*pi, 0);
156  }
157  }
158 };
159 
160 /******************************************************************************/
161 
162 /*!
163  * Traits class implementing StringSet concept for char* and unsigned char*
164  * strings.
165  */
166 template <typename CharType>
168 {
169 public:
170  //! exported alias for character type
171  typedef CharType Char;
172 
173  //! String reference: pointer to first character
174  typedef Char* String;
175 
176  //! Iterator over string references: pointer over pointers
177  typedef String* Iterator;
178 
179  //! iterator of characters in a string
180  typedef const Char* CharIterator;
181 
182  //! exported alias for assumed string container
183  typedef std::pair<Iterator, size_t> Container;
184 };
185 
186 /*!
187  * Class implementing StringSet concept for char* and unsigned char* strings.
188  */
189 template <typename CharType>
191  : public GenericCharStringSetTraits<CharType>,
192  public StringSetBase<GenericCharStringSet<CharType>,
193  GenericCharStringSetTraits<CharType> >
194 {
195 public:
197 
198  typedef typename Traits::Char Char;
199  typedef typename Traits::String String;
200  typedef typename Traits::Iterator Iterator;
202  typedef typename Traits::Container Container;
203 
204  //! Construct from begin and end string pointers
206  : begin_(begin), end_(end)
207  { }
208 
209  //! Construct from a string container
210  explicit GenericCharStringSet(const Container& c)
211  : begin_(c.first), end_(c.first + c.second)
212  { }
213 
214  //! Return size of string array
215  size_t size() const { return end_ - begin_; }
216  //! Iterator representing first String position
217  Iterator begin() const { return begin_; }
218  //! Iterator representing beyond last String position
219  Iterator end() const { return end_; }
220 
221  //! Iterator-based array access (readable and writable) to String objects.
223  { return *i; }
224 
225  //! Return CharIterator for referenced string, which belong to this set.
226  CharIterator get_chars(const String& s, size_t depth) const
227  { return s + depth; }
228 
229  //! Returns true if CharIterator is at end of the given String
230  bool is_end(const String&, const CharIterator& i) const
231  { return (*i == 0); }
232 
233  //! Return complete string (for debugging purposes)
234  std::string get_string(const String& s, size_t depth = 0) const
235  { return std::string(reinterpret_cast<const char*>(s) + depth); }
236 
237  //! Subset this string set using iterator range.
239  { return GenericCharStringSet(begin, end); }
240 
241  //! Allocate a new temporary string container with n empty Strings
242  static Container allocate(size_t n)
243  { return std::make_pair(new String[n], n); }
244 
245  //! Deallocate a temporary string container
246  static void deallocate(Container& c)
247  { delete[] c.first; c.first = nullptr; }
248 
249 protected:
250  //! array of string pointers
252 };
253 
256 
259 
260 /******************************************************************************/
261 
262 /*!
263  * Class implementing StringSet concept for a std::string objects.
264  */
266 {
267 public:
268  //! exported alias for character type
269  typedef uint8_t Char;
270 
271  //! String reference: std::string, which should be reference counted.
273 
274  //! Iterator over string references: pointer to std::string.
275  typedef String* Iterator;
276 
277  //! iterator of characters in a string
278  typedef const Char* CharIterator;
279 
280  //! exported alias for assumed string container
281  typedef std::pair<Iterator, size_t> Container;
282 };
283 
284 /*!
285  * Class implementing StringSet concept for arrays of std::string objects.
286  */
288  : public StdStringSetTraits,
289  public StringSetBase<StdStringSet, StdStringSetTraits>
290 {
291 public:
292  //! Construct from begin and end string pointers
294  : begin_(begin), end_(end)
295  { }
296 
297  //! Construct from a string container
298  explicit StdStringSet(Container& c)
299  : begin_(c.first), end_(c.first + c.second)
300  { }
301 
302  //! Return size of string array
303  size_t size() const { return end_ - begin_; }
304  //! Iterator representing first String position
305  Iterator begin() const { return begin_; }
306  //! Iterator representing beyond last String position
307  Iterator end() const { return end_; }
308 
309  //! Array access (readable and writable) to String objects.
310  String& operator [] (const Iterator& i) const
311  { return *i; }
312 
313  //! Return CharIterator for referenced string, which belongs to this set.
314  CharIterator get_chars(const String& s, size_t depth) const
315  { return reinterpret_cast<CharIterator>(s.data()) + depth; }
316 
317  //! Returns true if CharIterator is at end of the given String
318  bool is_end(const String& s, const CharIterator& i) const
319  { return (i >= reinterpret_cast<CharIterator>(s.data()) + s.size()); }
320 
321  //! Return complete string (for debugging purposes)
322  std::string get_string(const String& s, size_t depth = 0) const
323  { return s.substr(depth); }
324 
325  //! Subset this string set using iterator range.
327  { return StdStringSet(begin, end); }
328 
329  //! Allocate a new temporary string container with n empty Strings
330  static Container allocate(size_t n)
331  { return std::make_pair(new String[n], n); }
332 
333  //! Deallocate a temporary string container
334  static void deallocate(Container& c)
335  { delete[] c.first; c.first = nullptr; }
336 
337 protected:
338  //! pointers to std::string objects
340 };
341 
342 /******************************************************************************/
343 
344 /*!
345  * Class implementing StringSet concept for a std::unique_ptr<std::string
346  * objects, which are non-copyable.
347  */
349 {
350 public:
351  //! exported alias for character type
352  typedef uint8_t Char;
353 
354  //! String reference: std::string, which should be reference counted.
355  typedef std::unique_ptr<std::string> String;
356 
357  //! Iterator over string references: using std::vector's iterator
358  typedef String* Iterator;
359 
360  //! iterator of characters in a string
361  typedef const Char* CharIterator;
362 
363  //! exported alias for assumed string container
364  typedef std::pair<Iterator, size_t> Container;
365 };
366 
367 /*!
368  * Class implementing StringSet concept for a std::vector containing std::string
369  * objects.
370  */
372  : public UPtrStdStringSetTraits,
373  public StringSetBase<UPtrStdStringSet, UPtrStdStringSetTraits>
374 {
375 public:
376  //! Construct from begin and end string pointers
378  : begin_(begin), end_(end)
379  { }
380 
381  //! Construct from a string container
383  : begin_(c.first), end_(c.first + c.second)
384  { }
385 
386  //! Return size of string array
387  size_t size() const { return end_ - begin_; }
388  //! Iterator representing first String position
389  Iterator begin() const { return begin_; }
390  //! Iterator representing beyond last String position
391  Iterator end() const { return end_; }
392 
393  //! Array access (readable and writable) to String objects.
394  String& operator [] (const Iterator& i) const
395  { return *i; }
396 
397  //! Return CharIterator for referenced string, which belongs to this set.
398  CharIterator get_chars(const String& s, size_t depth) const
399  { return reinterpret_cast<CharIterator>(s->data()) + depth; }
400 
401  //! Returns true if CharIterator is at end of the given String
402  bool is_end(const String& s, const CharIterator& i) const
403  { return (i >= reinterpret_cast<CharIterator>(s->data()) + s->size()); }
404 
405  //! Return complete string (for debugging purposes)
406  std::string get_string(const String& s, size_t depth = 0) const
407  { return s->substr(depth); }
408 
409  //! Subset this string set using iterator range.
411  { return UPtrStdStringSet(begin, end); }
412 
413  //! Allocate a new temporary string container with n empty Strings
414  static Container allocate(size_t n)
415  { return std::make_pair(new String[n], n); }
416 
417  //! Deallocate a temporary string container
418  static void deallocate(Container& c)
419  { delete[] c.first; c.first = nullptr; }
420 
421  void print() const {
422  size_t i = 0;
423  for (Iterator pi = begin(); pi != end(); ++pi)
424  {
425  TLX_LOG1 << "[" << i++ << "] = " << pi->get()
426  << " = " << get_string(*pi, 0);
427  }
428  }
429 
430 protected:
431  //! vector of std::string objects
433 };
434 
435 /******************************************************************************/
436 
437 /*!
438  * Class implementing StringSet concept for suffix sorting indexes of a
439  * std::string text object.
440  */
442 {
443 public:
444  //! exported alias for assumed string container
445  typedef std::string Text;
446 
447  //! exported alias for character type
448  typedef uint8_t Char;
449 
450  //! String reference: suffix index of the text.
451  typedef typename Text::size_type String;
452 
453  //! Iterator over string references: using std::vector's iterator over
454  //! suffix array vector
455  typedef typename std::vector<String>::iterator Iterator;
456 
457  //! iterator of characters in a string
458  typedef const Char* CharIterator;
459 
460  //! exported alias for assumed string container
461  typedef std::pair<Text, std::vector<String> > Container;
462 };
463 
464 /*!
465  * Class implementing StringSet concept for suffix sorting indexes of a
466  * std::string text object.
467  */
469  : public StringSuffixSetTraits,
470  public StringSetBase<StringSuffixSet, StringSuffixSetTraits>
471 {
472 public:
473  //! Construct from begin and end string pointers
474  StringSuffixSet(const Text& text,
475  const Iterator& begin, const Iterator& end)
476  : text_(&text),
477  begin_(begin), end_(end)
478  { }
479 
480  //! Initializing constructor which fills output vector sa with indices.
481  static StringSuffixSet
482  Initialize(const Text& text, std::vector<String>& sa) {
483  sa.resize(text.size());
484  for (size_t i = 0; i < text.size(); ++i)
485  sa[i] = i;
486  return StringSuffixSet(text, sa.begin(), sa.end());
487  }
488 
489  //! Return size of string array
490  size_t size() const { return end_ - begin_; }
491  //! Iterator representing first String position
492  Iterator begin() const { return begin_; }
493  //! Iterator representing beyond last String position
494  Iterator end() const { return end_; }
495 
496  //! Array access (readable and writable) to String objects.
497  String& operator [] (const Iterator& i) const
498  { return *i; }
499 
500  //! Return CharIterator for referenced string, which belongs to this set.
501  CharIterator get_chars(const String& s, size_t depth) const
502  { return reinterpret_cast<CharIterator>(text_->data()) + s + depth; }
503 
504  //! Returns true if CharIterator is at end of the given String
505  bool is_end(const String&, const CharIterator& i) const
506  { return (i >= reinterpret_cast<CharIterator>(text_->data()) + text_->size()); }
507 
508  //! Return complete string (for debugging purposes)
509  std::string get_string(const String& s, size_t depth = 0) const
510  { return text_->substr(s + depth); }
511 
512  //! Subset this string set using iterator range.
514  { return StringSuffixSet(*text_, begin, end); }
515 
516  //! Allocate a new temporary string container with n empty Strings
517  Container allocate(size_t n) const
518  { return std::make_pair(*text_, std::vector<String>(n)); }
519 
520  //! Deallocate a temporary string container
521  static void deallocate(Container& c)
522  { std::vector<String> v; v.swap(c.second); }
523 
524  //! Construct from a string container
526  : text_(&c.first),
527  begin_(c.second.begin()), end_(c.second.end())
528  { }
529 
530 protected:
531  //! reference to base text
532  const Text* text_;
533 
534  //! iterators inside the output suffix array.
536 };
537 
538 /******************************************************************************/
539 
540 //! Objectified string array pointer and shadow pointer array for out-of-place
541 //! swapping of pointers.
542 template <typename StringSet_>
544 {
545 public:
546  typedef StringSet_ StringSet;
547  typedef typename StringSet::String String;
548  typedef typename StringSet::Iterator Iterator;
549 
550 protected:
551  //! strings (front) and temporary shadow (back) array
553 
554  //! false if active_ is original, true if shadow_ is original
555  bool flipped_;
556 
557 public:
558  //! constructor specifying all attributes
559  StringShadowPtr(const StringSet& original, const StringSet& shadow,
560  bool flipped = false)
561  : active_(original), shadow_(shadow), flipped_(flipped)
562  { }
563 
564  //! return currently active array
565  const StringSet& active() const { return active_; }
566 
567  //! return current shadow array
568  const StringSet& shadow() const { return shadow_; }
569 
570  //! true if flipped to back array
571  bool flipped() const { return flipped_; }
572 
573  //! return valid length
574  size_t size() const { return active_.size(); }
575 
576  //! construct a StringShadowPtr object specifying a sub-array with flipping
577  //! to other array.
578  StringShadowPtr flip(size_t begin, size_t end) const {
579  assert(end <= size());
580  return StringShadowPtr(shadow_.subi(begin, end),
581  active_.subi(begin, end), !flipped_);
582  }
583 
584  //! construct a StringShadowPtr object specifying a sub-array with flipping
585  //! to other array.
588  }
589 
590  //! return subarray pointer to n strings in original array, might copy from
591  //! shadow before returning.
592  const StringSet& copy_back() const {
593  if (!flipped_) {
594  return active_;
595  }
596  else {
597  std::move(active_.begin(), active_.end(), shadow_.begin());
598  return shadow_;
599  }
600  }
601 };
602 
603 } // namespace sort_strings_detail
604 } // namespace tlx
605 
606 #endif // !TLX_SORT_STRINGS_STRING_SET_HEADER
607 
608 /******************************************************************************/
std::string get_string(const String &s, size_t depth=0) const
Return complete string (for debugging purposes)
Definition: string_set.hpp:509
Char * String
String reference: pointer to first character.
Definition: string_set.hpp:174
GenericCharStringSet(const Container &c)
Construct from a string container.
Definition: string_set.hpp:210
Iterator begin() const
Iterator representing first String position.
Definition: string_set.hpp:492
StdStringSet(const Iterator &begin, const Iterator &end)
Construct from begin and end string pointers.
Definition: string_set.hpp:293
StringSuffixSet(Container &c)
Construct from a string container.
Definition: string_set.hpp:525
String & operator[](const Iterator &i) const
Array access (readable and writable) to String objects.
Definition: string_set.hpp:497
StringShadowPtr flip(size_t begin, size_t end) const
Definition: string_set.hpp:578
GenericCharStringSet sub(Iterator begin, Iterator end) const
Subset this string set using iterator range.
Definition: string_set.hpp:238
uint16_t get_uint16(const typename Traits::String &s, size_t depth) const
Definition: string_set.hpp:109
static void deallocate(Container &c)
Deallocate a temporary string container.
Definition: string_set.hpp:521
Class implementing StringSet concept for a std::unique_ptr<std::string objects, which are non-copyabl...
Definition: string_set.hpp:348
uint8_t get_uint8(const typename Traits::String &s, size_t depth) const
Definition: string_set.hpp:104
std::pair< Text, std::vector< String > > Container
exported alias for assumed string container
Definition: string_set.hpp:461
CharType Char
exported alias for character type
Definition: string_set.hpp:171
std::string get_string(const String &s, size_t depth=0) const
Return complete string (for debugging purposes)
Definition: string_set.hpp:406
static void deallocate(Container &c)
Deallocate a temporary string container.
Definition: string_set.hpp:334
String & operator[](const Iterator &i) const
Array access (readable and writable) to String objects.
Definition: string_set.hpp:394
Traits class implementing StringSet concept for char* and unsigned char* strings. ...
Definition: string_set.hpp:167
static Container allocate(size_t n)
Allocate a new temporary string container with n empty Strings.
Definition: string_set.hpp:330
Iterator end() const
Iterator representing beyond last String position.
Definition: string_set.hpp:307
static void deallocate(Container &c)
Deallocate a temporary string container.
Definition: string_set.hpp:418
uint8_t Char
exported alias for character type
Definition: string_set.hpp:352
std::pair< Iterator, size_t > Container
exported alias for assumed string container
Definition: string_set.hpp:364
StringSet active_
strings (front) and temporary shadow (back) array
Definition: string_set.hpp:552
const StringSet & active() const
return currently active array
Definition: string_set.hpp:565
StringShadowPtr(const StringSet &original, const StringSet &shadow, bool flipped=false)
constructor specifying all attributes
Definition: string_set.hpp:559
const Char * CharIterator
iterator of characters in a string
Definition: string_set.hpp:278
std::pair< Iterator, size_t > Container
exported alias for assumed string container
Definition: string_set.hpp:183
StringSuffixSet sub(Iterator begin, Iterator end) const
Subset this string set using iterator range.
Definition: string_set.hpp:513
UPtrStdStringSet(Container &c)
Construct from a string container.
Definition: string_set.hpp:382
Class implementing StringSet concept for suffix sorting indexes of a std::string text object...
Definition: string_set.hpp:441
Class implementing StringSet concept for char* and unsigned char* strings.
Definition: string_set.hpp:190
GenericCharStringSet< const char > CCharStringSet
Definition: string_set.hpp:257
GenericCharStringSet< char > CharStringSet
Definition: string_set.hpp:254
UPtrStdStringSet(const Iterator &begin, const Iterator &end)
Construct from begin and end string pointers.
Definition: string_set.hpp:377
Class implementing StringSet concept for arrays of std::string objects.
Definition: string_set.hpp:287
String & operator[](const Iterator &i) const
Array access (readable and writable) to String objects.
Definition: string_set.hpp:310
StringSet subi(size_t begin, size_t end) const
Subset this string set using index range.
Definition: string_set.hpp:117
std::pair< Iterator, size_t > Container
exported alias for assumed string container
Definition: string_set.hpp:281
CharIterator get_chars(const String &s, size_t depth) const
Return CharIterator for referenced string, which belongs to this set.
Definition: string_set.hpp:398
GenericCharStringSet< const unsigned char > CUCharStringSet
Definition: string_set.hpp:258
bool flipped() const
true if flipped to back array
Definition: string_set.hpp:571
String * Iterator
Iterator over string references: using std::vector's iterator.
Definition: string_set.hpp:358
std::string get_string(const String &s, size_t depth=0) const
Return complete string (for debugging purposes)
Definition: string_set.hpp:322
size_t size() const
return valid length
Definition: string_set.hpp:574
bool flipped_
false if active_ is original, true if shadow_ is original
Definition: string_set.hpp:555
std::string get_string(const String &s, size_t depth=0) const
Return complete string (for debugging purposes)
Definition: string_set.hpp:234
uint8_t Char
exported alias for character type
Definition: string_set.hpp:448
Class implementing StringSet concept for a std::string objects.
Definition: string_set.hpp:265
String * Iterator
Iterator over string references: pointer to std::string.
Definition: string_set.hpp:275
size_t size() const
Return size of string array.
Definition: string_set.hpp:387
Iterator begin_
vector of std::string objects
Definition: string_set.hpp:432
bool is_end(const String &s, const CharIterator &i) const
Returns true if CharIterator is at end of the given String.
Definition: string_set.hpp:402
Iterator begin_
iterators inside the output suffix array.
Definition: string_set.hpp:535
String & operator[](Iterator i) const
Iterator-based array access (readable and writable) to String objects.
Definition: string_set.hpp:222
static Container allocate(size_t n)
Allocate a new temporary string container with n empty Strings.
Definition: string_set.hpp:242
Iterator begin_
pointers to std::string objects
Definition: string_set.hpp:339
Iterator begin_
array of string pointers
Definition: string_set.hpp:251
CharIterator get_chars(const String &s, size_t depth) const
Return CharIterator for referenced string, which belongs to this set.
Definition: string_set.hpp:501
uint16_t get_uint16(const typename Traits::String &s, typename Traits::CharIterator i) const
Definition: string_set.hpp:91
bool check_order(const typename Traits::String &s1, const typename Traits::String &s2) const
Definition: string_set.hpp:122
const Char * CharIterator
iterator of characters in a string
Definition: string_set.hpp:361
GenericCharStringSetTraits< CharType > Traits
Definition: string_set.hpp:196
std::basic_string< char, std::char_traits< char >, Allocator< char > > string
string with Manager tracking
Definition: allocator.hpp:220
uint8_t Char
exported alias for character type
Definition: string_set.hpp:269
Text::size_type String
String reference: suffix index of the text.
Definition: string_set.hpp:451
Traits::Char get_char(const typename Traits::String &s, size_t depth) const
Definition: string_set.hpp:74
bool is_leq(const typename Traits::String &a, const typename Traits::CharIterator &ai, const typename Traits::String &b, const typename Traits::CharIterator &bi) const
check if string a is less or equal to string b at iterators ai and bi.
Definition: string_set.hpp:59
StringSuffixSet(const Text &text, const Iterator &begin, const Iterator &end)
Construct from begin and end string pointers.
Definition: string_set.hpp:474
bool is_equal(const typename Traits::String &a, const typename Traits::CharIterator &ai, const typename Traits::String &b, const typename Traits::CharIterator &bi) const
check equality of two strings a and b at char iterators ai and bi.
Definition: string_set.hpp:50
StdStringSet sub(Iterator begin, Iterator end) const
Subset this string set using iterator range.
Definition: string_set.hpp:326
Class implementing StringSet concept for suffix sorting indexes of a std::string text object...
Definition: string_set.hpp:468
bool is_end(const String &, const CharIterator &i) const
Returns true if CharIterator is at end of the given String.
Definition: string_set.hpp:505
GenericCharStringSet< unsigned char > UCharStringSet
Definition: string_set.hpp:255
Iterator end() const
Iterator representing beyond last String position.
Definition: string_set.hpp:391
const Char * CharIterator
iterator of characters in a string
Definition: string_set.hpp:458
Iterator end() const
Iterator representing beyond last String position.
Definition: string_set.hpp:219
GenericCharStringSet(Iterator begin, Iterator end)
Construct from begin and end string pointers.
Definition: string_set.hpp:205
StdStringSet(Container &c)
Construct from a string container.
Definition: string_set.hpp:298
std::unique_ptr< std::string > String
String reference: std::string, which should be reference counted.
Definition: string_set.hpp:355
static void deallocate(Container &c)
Deallocate a temporary string container.
Definition: string_set.hpp:246
const StringSet & copy_back() const
Definition: string_set.hpp:592
std::string String
String reference: std::string, which should be reference counted.
Definition: string_set.hpp:272
static StringSuffixSet Initialize(const Text &text, std::vector< String > &sa)
Initializing constructor which fills output vector sa with indices.
Definition: string_set.hpp:482
Class implementing StringSet concept for a std::vector containing std::string objects.
Definition: string_set.hpp:371
Container allocate(size_t n) const
Allocate a new temporary string container with n empty Strings.
Definition: string_set.hpp:517
Iterator end() const
Iterator representing beyond last String position.
Definition: string_set.hpp:494
Iterator begin() const
Iterator representing first String position.
Definition: string_set.hpp:389
const Char * CharIterator
iterator of characters in a string
Definition: string_set.hpp:180
size_t size() const
Return size of string array.
Definition: string_set.hpp:303
size_t size() const
Return size of string array.
Definition: string_set.hpp:490
UPtrStdStringSet sub(Iterator begin, Iterator end) const
Subset this string set using iterator range.
Definition: string_set.hpp:410
bool is_end(const String &, const CharIterator &i) const
Returns true if CharIterator is at end of the given String.
Definition: string_set.hpp:230
CharIterator get_chars(const String &s, size_t depth) const
Return CharIterator for referenced string, which belongs to this set.
Definition: string_set.hpp:314
Base class for common string set functions, included via CRTP.
Definition: string_set.hpp:43
#define TLX_LOG1
Definition: core.hpp:145
uint8_t get_uint8(const typename Traits::String &s, typename Traits::CharIterator i) const
Definition: string_set.hpp:81
CharIterator get_chars(const String &s, size_t depth) const
Return CharIterator for referenced string, which belong to this set.
Definition: string_set.hpp:226
bool is_end(const String &s, const CharIterator &i) const
Returns true if CharIterator is at end of the given String.
Definition: string_set.hpp:318
std::string Text
exported alias for assumed string container
Definition: string_set.hpp:445
Iterator begin() const
Iterator representing first String position.
Definition: string_set.hpp:217
std::vector< String >::iterator Iterator
Definition: string_set.hpp:455
const StringSet & shadow() const
return current shadow array
Definition: string_set.hpp:568
Iterator begin() const
Iterator representing first String position.
Definition: string_set.hpp:305
static Container allocate(size_t n)
Allocate a new temporary string container with n empty Strings.
Definition: string_set.hpp:414
String * Iterator
Iterator over string references: pointer over pointers.
Definition: string_set.hpp:177
size_t size() const
Return size of string array.
Definition: string_set.hpp:215
const Text * text_
reference to base text
Definition: string_set.hpp:532