Line data    Source code

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