StringIterator.h

   1 /******************************************************************************
   2  *   Copyright (C) 2009 by Niko Välimäki                                      *
   3  *                                                                            *
   4  *                                                                            *
   5  *   This program is free software; you can redistribute it and/or modify     *
   6  *   it under the terms of the GNU Lesser General Public License as published *
   7  *   by the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                      *
   9  *                                                                            *
  10  *   This program is distributed in the hope that it will be useful,          *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  13  *   GNU Lesser General Public License for more details.                      *
  14  *                                                                            *
  15  *   You should have received a copy of the GNU Lesser General Public License *
  16  *   along with this program; if not, write to the                            *
  17  *   Free Software Foundation, Inc.,                                          *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            *
  19  *****************************************************************************/
  20
  21 #ifndef _CSA_MYSTRINGITERATOR_
  22 #define _CSA_MYSTRINGITERATOR_
  23
  24 #include "BitRank.h"
  25 #include <iterator>
  26 #include <utility>
  27
  28 namespace SXSI
  29 {
  30
  31 /**
  32  * Custom random access iterator for a string of texts separated by '\0'.
  33  *
  34  * Maps from char array [0.255] to unsigned alphabet [0...] so that
  35  * each endmarker '\0' in original array is given an unique
  36  * number that retains ordering among the endmarkers.
  37  * Other characters [1..255] are mapped to range [numberOfTexts..255+numberOfText].
  38  */
  39 class StringIterator : public std::iterator<std::random_access_iterator_tag,
  40         unsigned,
  41         long>
  42 {
  43 protected:
  44     uchar const * ptr_;
  45     uchar const * begin_;
  46     ulong n_;
  47     unsigned numberOfTexts_;
  48     BitRank * br_;
  49
  50 public:
  51
  52     StringIterator()
  53         : ptr_(0), begin_(0), n_(0), numberOfTexts_(0), br_(0)
  54     {}
  55     StringIterator(uchar const * ptr, uchar const * begin, ulong n, unsigned noTexts, BitRank* br)
  56         : ptr_(ptr), begin_(begin), n_(n), numberOfTexts_(noTexts), br_(br)
  57     {}
  58     StringIterator( StringIterator const & other )
  59         : ptr_( other.ptr_ ), begin_(other.begin_), n_(other.n_), numberOfTexts_(other.numberOfTexts_),
  60         br_(other.br_)
  61     {}
  62
  63 /*    uchar const * operator &()
  64     {
  65         return( ptr_ );
  66     }
  67
  68     uchar const * operator &() const
  69     {
  70         return( ptr_ );
  71         }*/
  72
  73     StringIterator& operator=( StringIterator const & other )
  74     {
  75         ptr_ = other.ptr_;
  76         begin_ = other.begin_;
  77         n_ = other.n_;
  78         numberOfTexts_ = other.numberOfTexts_;
  79         br_ = other.br_;
  80         return( *this );
  81     }
  82
  83     bool operator<=( StringIterator const & other ) const
  84     {
  85         long d = other.ptr_ - ptr_;
  86         return( d > 0 || ptr_ == other.ptr_ );
  87     }
  88
  89     bool operator<( StringIterator const & other ) const
  90     {
  91         long d = other.ptr_ - ptr_;
  92         return( d > 0 );
  93     }
  94
  95     bool operator==( StringIterator const & other ) const
  96     {
  97         return( ptr_ == other.ptr_ );
  98     }
  99
 100     bool operator!=( StringIterator const & other ) const
 101     {
 102         return( ptr_ != other.ptr_ );
 103     }
 104
 105     unsigned operator*()
 106     {
 107         if (ptr_ - begin_ < 0 || (ulong)(ptr_ - begin_) >= n_)
 108             return 0;
 109
 110         uchar c = (uchar)*ptr_;
 111         if (c == 0)
 112             return br_->rank(ptr_-begin_);
 113
 114         unsigned result = (unsigned)c + numberOfTexts_;
 115
 116         return result;
 117     }
 118
 119     uchar const * operator->()
 120     {
 121         return( ptr_ );
 122     }
 123
 124     StringIterator& operator++()
 125     {
 126         ++ptr_;
 127         return( *this );
 128     }
 129
 130     StringIterator operator++(int)
 131     {
 132         StringIterator tmp( *this );
 133         ++ptr_;
 134         return( tmp );
 135     }
 136
 137     StringIterator& operator--()
 138     {
 139         --ptr_;
 140         return( *this );
 141     }
 142
 143     StringIterator operator--(int)
 144     {
 145         StringIterator tmp( *this );
 146         --ptr_;
 147         return( tmp );
 148     }
 149
 150     long operator-( StringIterator const & other ) const
 151     {
 152         long d = ptr_ - other.ptr_;
 153         return( d );
 154     }
 155
 156     unsigned operator[]( size_t nPos ) const
 157     {
 158         StringIterator tmp( *this );
 159         tmp.ptr_ += nPos;
 160         return( *tmp );
 161     }
 162
 163     StringIterator& operator+=( int nPos )
 164     {
 165         ptr_ += nPos;
 166         return( *this );
 167     }
 168
 169     StringIterator& operator-=( int nPos )
 170     {
 171         ptr_ -= nPos;
 172         return( *this );
 173     }
 174
 175     StringIterator operator+( int n ) const
 176     {
 177         StringIterator tmp( *this );
 178         tmp += n;
 179         return( tmp );
 180     }
 181
 182     StringIterator operator-( int n ) const
 183     {
 184         StringIterator tmp( *this );
 185         tmp -= n;
 186         return( tmp );
 187     }
 188 }; // class
 189
 190
 191 /*static StringIterator operator+( int n, StringIterator const & iterator )
 192 {
 193     return( iterator + n );
 194     }*/
 195
 196 } // namespace SXSI
 197
 198 #endif // _CSA_MYSTRINGITERATOR_