Line data Source code
1 : // Copyright (c) 2011-2022 Made to Order Software Corp. All Rights Reserved
2 : //
3 : // https://snapwebsites.org/project/snapdev
4 : // contact@m2osw.com
5 : //
6 : // This program is free software; you can redistribute it and/or modify
7 : // it under the terms of the GNU General Public License as published by
8 : // the Free Software Foundation; either version 2 of the License, or
9 : // (at your option) any later version.
10 : //
11 : // This program is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 : //
16 : // You should have received a copy of the GNU General Public License along
17 : // with this program; if not, write to the Free Software Foundation, Inc.,
18 : // 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 : #pragma once
20 :
21 : /** \file
22 : * \brief Iterator to search a string in reverse.
23 : *
24 : * This implementation is used to search characters starting the
25 : * search from the end of the string. However, the iterator looks
26 : * like it is used in a normal way which better matches certain
27 : * function which would not otherwise accept rbegin() and rend().
28 : */
29 :
30 : // C++ lib
31 : //
32 : #include <iterator>
33 :
34 : namespace snapdev
35 : {
36 :
37 : /** \brief Iterate a standard C string in reverse.
38 : *
39 : * This function lets you iterate a standard C string, such as "12345",
40 : * in reverse order. The begin() and end() functions return a reverse
41 : * iterator (watch out!) We do not offer a rbegin() and rend() since
42 : * in most cases, using the string pointers as is would have to exact
43 : * same effect.
44 : *
45 : * \note
46 : * There may already be something in STL to be able to do that without
47 : * a specific implementation, if so I have not found it yet. This
48 : * class satisfy various needs such as finding the last character
49 : * that do not match a set of characters:
50 : *
51 : * \code
52 : * std::string match(":,/");
53 : * reverse_cstring rstr(start, start + strlen(start));
54 : * auto last = std::find_if_not(
55 : * rstr.begin(),
56 : * rstr.end(),
57 : * [](char const c)
58 : * {
59 : * return match.find(c) != std::string::npos;
60 : * });
61 : * // last.get() == "first character found in 'match' at the end part of string"
62 : * // for example, in "/,:test:,/" would return a pointer on the last ':'
63 : * \endcode
64 : *
65 : * \warning
66 : * This function uses the specified start and end pointer of a C string
67 : * that must be valid as long as these iterators are used.
68 : *
69 : * \tparam T The type of string container.
70 : */
71 : template <typename T>
72 : class reverse_cstring
73 : {
74 : public:
75 :
76 : /** \brief Reverse C-string iterator.
77 : *
78 : * This iterator allows us to go through a C-string (i.e. a `char *`
79 : * pointer to a null terminated string) in reverse (i.e. from the
80 : * end to the start.)
81 : *
82 : * This is a very efficient iterator that allows us to avoid a full
83 : * copy of the string in an std::string. At this time, it is primarily
84 : * used to trim the end of strings.
85 : */
86 : class iterator
87 : : public std::iterator<std::random_access_iterator_tag, T>
88 : {
89 : public:
90 : // Iterator traits
91 : //
92 : typedef std::ptrdiff_t difference_type;
93 : typedef T value_type;
94 : typedef T * pointer;
95 : typedef T & reference;
96 :
97 : // ForwardIterator
98 : //
99 70 : reference operator * ()
100 : {
101 70 : return i_[-1];
102 : }
103 :
104 : value_type operator * () const
105 : {
106 : return i_[-1];
107 : }
108 :
109 : iterator operator ++ (int)
110 : {
111 : iterator const copy(*this);
112 : --i_;
113 : return copy;
114 : }
115 :
116 39 : iterator & operator ++ ()
117 : {
118 39 : --i_;
119 39 : return *this;
120 : }
121 :
122 : // BidirectionalIterator
123 : //
124 : iterator operator -- (int)
125 : {
126 : iterator const copy(*this);
127 : ++i_;
128 : return copy;
129 : }
130 :
131 : iterator & operator -- ()
132 : {
133 : ++i_;
134 : return *this;
135 : }
136 :
137 : // RandomAccessIterator
138 : //
139 : iterator & operator += (int n)
140 : {
141 : i_ -= n;
142 : return *this;
143 : }
144 :
145 : iterator operator + (int n) const
146 : {
147 : return iterator(i_ - n);
148 : }
149 :
150 : friend iterator operator + (int n, iterator & rhs)
151 : {
152 : return iterator(rhs.i_ - n);
153 : }
154 :
155 : iterator & operator -= (int n)
156 : {
157 : i_ += n;
158 : return *this;
159 : }
160 :
161 : iterator operator - (int n) const
162 : {
163 : return iterator(i_ + n);
164 : }
165 :
166 : friend iterator operator - (int n, iterator & rhs)
167 : {
168 : return iterator(rhs.i_ + n);
169 : }
170 :
171 35 : difference_type operator - (iterator const & rhs) const
172 : {
173 35 : return rhs.i_ - i_;
174 : }
175 :
176 : reference operator [] (int idx)
177 : {
178 : return i_[-idx - 1];
179 : }
180 :
181 : value_type operator [] (int idx) const
182 : {
183 : return i_[-idx - 1];
184 : }
185 :
186 : bool operator < (iterator const & rhs) const
187 : {
188 : return i_ > rhs.i_;
189 : }
190 :
191 : bool operator > (iterator const & rhs) const
192 : {
193 : return i_ < rhs.i_;
194 : }
195 :
196 : bool operator <= (iterator const & rhs) const
197 : {
198 : return i_ >= rhs.i_;
199 : }
200 :
201 : bool operator >= (iterator const & rhs) const
202 : {
203 : return i_ <= rhs.i_;
204 : }
205 :
206 : // Other
207 : //
208 : bool operator == (iterator const & rhs) const
209 : {
210 : return i_ == rhs.i_;
211 : }
212 :
213 : bool operator != (iterator const & rhs) const
214 : {
215 : return i_ != rhs.i_;
216 : }
217 :
218 31 : T * get() const
219 : {
220 31 : return i_;
221 : }
222 :
223 : private:
224 : friend class reverse_cstring;
225 :
226 62 : iterator(T * it)
227 62 : : i_(it)
228 : {
229 62 : }
230 :
231 : T * i_;
232 : };
233 :
234 31 : reverse_cstring(T * start, T * end)
235 : : s_(start)
236 31 : , e_(end)
237 : {
238 31 : }
239 :
240 31 : iterator begin() const
241 : {
242 31 : return iterator(e_);
243 : }
244 :
245 31 : iterator end() const
246 : {
247 31 : return iterator(s_);
248 : }
249 :
250 : std::size_t size() const
251 : {
252 : return e_ - s_;
253 : }
254 :
255 : private:
256 : T * s_;
257 : T * e_;
258 : };
259 :
260 :
261 :
262 : /** \fn reverse_cstring::reverse_cstring(T * start, T * end)
263 : * \brief Initialize the reverse string with a start and end pointers.
264 : *
265 : * This constructor initializes a reverse string. You can then retrieve
266 : * the `begin()` and `end()` iterators to walk the string. Remember that
267 : * you will be walking the string going backward using what looks like
268 : * a usual forward iterator.
269 : *
270 : * The start is the smaller pointer. So if you have a C-string, you want
271 : * to create a reverse cstring with:
272 : *
273 : * \code
274 : * char const * str("a C-string");
275 : * reverse_cstring(str, str + strlen(str));
276 : * \endcode
277 : *
278 : * Of course, it is not mandatory to pass the entire string to this
279 : * constructor. However, we do not make a copy of the string. We use
280 : * your bare pointers as is. You must make sure that this string
281 : * remains available for the whole time you want to use the
282 : * reverse_cstring.
283 : *
284 : * \param[in] start The start of the string.
285 : * \param[in] end The end of the string.
286 : */
287 :
288 : /** \fn reverse_cstring::begin() const
289 : * \brief Create an iterator at the beginning of the C-string.
290 : *
291 : * This function creates an iterator at the beginning of the reversed string.
292 : *
293 : * \note
294 : * The begin() actually uses the end pointer as passed to the constructor.
295 : *
296 : * \return A reverse_cstring iterator to the beginning of the string.
297 : */
298 :
299 : /** \fn reverse_cstring::end() const
300 : * \brief Create an iterator at the end of the C-string.
301 : *
302 : * This function creates an iterator at the end of the reverse string.
303 : *
304 : * \note
305 : * The end() actually uses the begin pointer as passed to the constructor.
306 : *
307 : * \return A reverse_cstring iterator to the end of the string.
308 : */
309 :
310 : /** \fn reverse_cstring::size() const
311 : * \brief Return the total size of the reverse C-string.
312 : *
313 : * The size of the string calculated as the end pointer minus the start
314 : * pointer.
315 : *
316 : * \return The size of the reverse C-string.
317 : */
318 :
319 : /** \var reverse_cstring::s_
320 : * \brief The start of the string.
321 : *
322 : * This variable member points to the start of the string. This is the
323 : * pointer used to represent the end() iterator.
324 : */
325 :
326 : /** \var reverse_cstring::e_
327 : * \brief The end of the string.
328 : *
329 : * This variable member points to the end of the string. Usually the
330 : * last character + 1. This is the pointer used to represent the
331 : * begin() iterator.
332 : */
333 :
334 :
335 :
336 :
337 :
338 :
339 :
340 :
341 :
342 : /** \typedef reverse_cstring::iterator::difference_type
343 : * \brief Type used to calculate the difference between iterators.
344 : *
345 : * This type is expected to fit a pointer and to be signed.
346 : */
347 :
348 :
349 : /** \typedef reverse_cstring::iterator::value_type
350 : * \brief Type of each item in the string.
351 : *
352 : * This type represents the type of characters in the string.
353 : */
354 :
355 :
356 : /** \typedef reverse_cstring::iterator::pointer
357 : * \brief Direct pointer to the string characters.
358 : *
359 : * This type represents a direct pointer (not a smart pointer) to the
360 : * string data.
361 : *
362 : * It is expected that the person using this template will make sure
363 : * that the string remains available for the whole duration.
364 : */
365 :
366 :
367 : /** \typedef reverse_cstring::iterator::reference
368 : * \brief Reference to the string characters.
369 : *
370 : * This type represents a reference to the string character type.
371 : */
372 :
373 : /** \fn reverse_cstring::iterator::operator * ()
374 : * \brief Retrieve a reference to the character at the current position.
375 : *
376 : * This function returns a reference to the string character at the
377 : * current location. It can be used to modify the character.
378 : *
379 : * \return A reference to the current character.
380 : */
381 :
382 : /** \fn reverse_cstring::iterator::operator * () const
383 : * \brief Retrieve the character at the current position.
384 : *
385 : * This function returns a copy of the character at the current position.
386 : *
387 : * \return A copy of the current character.
388 : */
389 :
390 : /** \fn reverse_cstring::iterator::operator ++ (int)
391 : * \brief Run a post increment.
392 : *
393 : * This function makes a copy of the current position, then it increments
394 : * it. Since we are the "reverse string" the position is actually
395 : * decremented.
396 : *
397 : * \return A reference to this iterator.
398 : */
399 :
400 : /** \fn reverse_cstring::iterator::operator ++ ()
401 : * \brief Run a pre-increment.
402 : *
403 : * This function increments the position and then returns a reference to
404 : * the iterator. Since we are the "reverse string" the position is actually
405 : * decremented.
406 : *
407 : * \return A reference to this iterator.
408 : */
409 :
410 : /** \fn reverse_cstring::iterator::operator -- (int)
411 : * \brief Run a post decrement.
412 : *
413 : * This function makes a copy of the current position, then it decrements
414 : * it. Since we are the "reverse string" the position is actually
415 : * incremented.
416 : *
417 : * \return A reference to this iterator.
418 : */
419 :
420 : /** \fn reverse_cstring::iterator::operator -- ()
421 : * \brief Run a pre-decrement.
422 : *
423 : * This function decrements the position and then returns a reference to
424 : * the iterator. Since we are the "reverse string" the position is actually
425 : * incremented.
426 : *
427 : * \return A reference to this iterator.
428 : */
429 :
430 : /** \fn reverse_cstring::iterator::operator += (int n) const
431 : * \brief Add an offset to the position of this iterator and returns the copy.
432 : *
433 : * This function increments the position by n and then returns a
434 : * reference. Since we are the "reverse string" the position is
435 : * actually decrementing the position.
436 : *
437 : * \param[in] n The number to add.
438 : *
439 : * \return A reference to this iterator.
440 : */
441 :
442 : /** \fn reverse_cstring::iterator::operator + (int n) const
443 : * \brief Add an offset to the position of this iterator and returns the copy.
444 : *
445 : * This function increments the position by n and then returns the copy to
446 : * the iterator. Since we are the "reverse string" the position is actually
447 : * decrementing the position.
448 : *
449 : * \param[in] n The number to add.
450 : *
451 : * \return A new iterator.
452 : */
453 :
454 : /** \fn reverse_cstring::iterator::operator + (int n, iterator & rhs)
455 : * \brief Add an offset to the position of this iterator and returns the copy.
456 : *
457 : * This function increments the position by n and then returns the copy to
458 : * the iterator. Since we are the "reverse string" the position is actually
459 : * decrementing the position.
460 : *
461 : * \param[in] n The number to add.
462 : * \param[in] rhs The right hand side iterator.
463 : *
464 : * \return A new iterator.
465 : */
466 :
467 : /** \fn reverse_cstring::iterator::operator -= (int n) const
468 : * \brief Subtract an offset from the position of this iterator and returns the copy.
469 : *
470 : * This function decrements the position by n and then returns a
471 : * reference. Since we are the "reverse string" the position is
472 : * actually incrementing the position.
473 : *
474 : * \param[in] n The number to subtract.
475 : *
476 : * \return A reference to this iterator.
477 : */
478 :
479 : /** \fn reverse_cstring::iterator::operator - (int n) const
480 : * \brief Subtract an offset from the position of this iterator and returns the copy.
481 : *
482 : * This function decrements the position by n and then returns the copy to
483 : * the iterator. Since we are the "reverse string" the position is actually
484 : * incrementing the position.
485 : *
486 : * \param[in] n The number to subtract.
487 : *
488 : * \return A new iterator.
489 : */
490 :
491 : /** \fn reverse_cstring::iterator::operator - (int n, iterator & rhs)
492 : * \brief Subtract an offset from the position of this iterator and returns the copy.
493 : *
494 : * This function decrements the position by n and then returns the copy to
495 : * the iterator. Since we are the "reverse string" the position is actually
496 : * incrementing the position.
497 : *
498 : * \param[in] n The number to add.
499 : * \param[in] rhs The right hand side.
500 : *
501 : * \return A new iterator.
502 : */
503 :
504 : /** \fn reverse_cstring::iterator::operator - (iterator const & rhs) const
505 : * \brief Compare the difference between two iterators.
506 : *
507 : * This function calculates the difference between two iterators.
508 : *
509 : * \param[in] rhs The right hand side.
510 : *
511 : * \return A new iterator.
512 : */
513 :
514 : /** \fn reverse_cstring::iterator::operator [] (int idx)
515 : * \brief Get a reference to the character at the current position.
516 : *
517 : * This function gets a reference to the character at the current position.
518 : * It can be used to read or write the character.
519 : *
520 : * \param[in] idx The index of the character to retrieve.
521 : *
522 : * \return A reference to the index character.
523 : */
524 :
525 : /** \fn reverse_cstring::iterator::operator [] (int idx) const
526 : * \brief Get a copy of the character at the current position.
527 : *
528 : * This function returns a copy of the character at the current position.
529 : *
530 : * \param[in] idx The index of the character to retrieve.
531 : *
532 : * \return A of the character at the \p idx position.
533 : */
534 :
535 : /** \fn reverse_cstring::iterator::operator < (iterator const & rhs) const
536 : * \brief Compare two iterators.
537 : *
538 : * This function returns true if the left hand side iterator is at an
539 : * earlier position than the right hand side.
540 : *
541 : * \param[in] rhs The right hand side.
542 : *
543 : * \return true if this is less than right hand side.
544 : */
545 :
546 : /** \fn reverse_cstring::iterator::operator > (iterator const & rhs) const
547 : * \brief Compare two iterators.
548 : *
549 : * This function returns true if the left hand side iterator is at a
550 : * later position than the right hand side.
551 : *
552 : * \param[in] rhs The right hand side.
553 : *
554 : * \return true if this is more than right hand side.
555 : */
556 :
557 : /** \fn reverse_cstring::iterator::operator <= (iterator const & rhs) const
558 : * \brief Compare two iterators.
559 : *
560 : * This function returns true if the left hand side iterator is at an
561 : * earlier or equal position than the right hand side.
562 : *
563 : * \param[in] rhs The right hand side.
564 : *
565 : * \return true if this is less or equal than right hand side.
566 : */
567 :
568 : /** \fn reverse_cstring::iterator::operator >= (iterator const & rhs) const
569 : * \brief Compare two iterators.
570 : *
571 : * This function returns true if the left hand side iterator is at a
572 : * later or equal position than the right hand side.
573 : *
574 : * \param[in] rhs The right hand side.
575 : *
576 : * \return true if this is larger or equal than right hand side.
577 : */
578 :
579 : /** \fn reverse_cstring::iterator::operator == (iterator const & rhs) const
580 : * \brief Compare two iterators.
581 : *
582 : * This function returns true if the left hand side iterator is at
583 : * the same position than the right hand side.
584 : *
585 : * \param[in] rhs The right hand side.
586 : *
587 : * \return true if this is equal the right hand side.
588 : */
589 :
590 : /** \fn reverse_cstring::iterator::operator != (iterator const & rhs) const
591 : * \brief Compare two iterators.
592 : *
593 : * This function returns true if the left hand side iterator is not at
594 : * the same position than the right hand side.
595 : *
596 : * \param[in] rhs The right hand side.
597 : *
598 : * \return true if this is not equal the right hand side.
599 : */
600 :
601 : /** \fn reverse_cstring::iterator::get() const
602 : * \brief Get the current position, which is a pointer to a character.
603 : *
604 : * This function returns the current iterator position. This is a
605 : * pointer right after a character in the string. If you want to
606 : * retrieve the character, may sure to use `pointer[-1]`.
607 : *
608 : * \return The pointer to the string at the current iterator location.
609 : */
610 :
611 : /** \fn reverse_cstring::iterator::iterator(T * it)
612 : * \brief Initialize the iterator.
613 : *
614 : * This function initialize the iterator with the specified pointer.
615 : *
616 : * \param[in] it The string pointer the iterator likes to use.
617 : */
618 :
619 : /** \var reverse_cstring::iterator::i_
620 : * \brief The position in the iterator.
621 : *
622 : * This variable member is a pointer to the character in the string
623 : * this iterator points to. The character is actually at `i_[-1]`
624 : * since we are in reverse.
625 : */
626 :
627 :
628 :
629 :
630 :
631 : } // namespace snapdev
632 : // vim: ts=4 sw=4 et
|
