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