src/support/RandomAccessList.h

   1 // -*- C++ -*-
   2 /**
   3  * \file RandomAccessList.h
   4  * This file is part of LyX, the document processor.
   5  * Licence details can be found in the file COPYING.
   6  *
   7  * \author Abdelrazak Younes
   8  *
   9  * Full author contact details are available in file CREDITS.
  10  *
  11  */
  12
  13 #ifndef RANDOM_ACESS_LIST_H
  14 #define RANDOM_ACESS_LIST_H
  15
  16 #include <vector>
  17 #include <list>
  18
  19
  20 namespace lyx {
  21
  22 #define USE_OLD_ITERATOR 1
  23
  24 /// Random Access List.
  25 /**
  26 This templatized class provide a std::vector like interface to a
  27 standard std::list underneath. An important property is that it
  28 keeps the std::list::iterator interface. A typical use would be:
  29
  30         typedef RandomAccessList<some_class> MyContainer;
  31
  32 Then you can use MyContainer as if it was a standard
  33 std::vector<some_class> for operator[] access and as if it was a
  34 standard std::list for iterator access. The main difference with
  35 std::vector is that insertion of elements is much less costly. Compared
  36 to a standard list alone, there is of course a small overhead because
  37 the class always keeps its internal vector of iterator (it_vector_) up
  38 to date.
  39 */
  40 template <class T>
  41 class RandomAccessList {
  42 public:
  43         // types
  44         typedef std::list<T> Container;
  45         typedef typename Container::reference reference;
  46         typedef typename Container::const_reference const_reference;
  47 #if USE_OLD_ITERATOR
  48         // iterator (below)
  49         typedef typename Container::iterator iterator;
  50         // const_iterator (below)
  51         typedef typename Container::const_iterator const_iterator;
  52 #else
  53         // wip
  54 #endif
  55         typedef typename Container::size_type size_type;
  56         typedef typename Container::difference_type difference_type;
  57         typedef typename Container::value_type value_type;
  58         typedef typename Container::allocator_type allocator_type;
  59         typedef typename Container::pointer pointer;
  60         typedef typename Container::const_pointer const_pointer;
  61         // reverse_iterator
  62         // const_reverse_iterator
  63
  64         typedef std::vector<typename Container::iterator> IterCont;
  65
  66         // construct/copy/destroy
  67
  68         RandomAccessList()
  69         {}
  70
  71         // RandomAccessList(size_type n T const & value = T())
  72
  73         template<class InputIterator>
  74         RandomAccessList(InputIterator first, InputIterator last)
  75         {
  76                 assign(first, last);
  77         }
  78
  79
  80
  81         RandomAccessList(RandomAccessList const & x)
  82         {
  83                 assign(x.begin(), x.end());
  84         }
  85
  86         // ~RandomAccessList()
  87
  88         ///
  89         RandomAccessList & operator=(RandomAccessList const & x)
  90         {
  91                 assign(x.begin(), x.end());
  92                 return *this;
  93         }
  94
  95         template<class InputIterator>
  96         void assign(InputIterator first, InputIterator last)
  97         {
  98                 container_.assign(first, last);
  99                 recreateVector();
 100         }
 101
 102
 103         // void assign(size_type n, T const & u);
 104
 105         // iterators
 106
 107         iterator begin()
 108         {
 109                 return container_.begin();
 110         }
 111
 112         const_iterator begin() const
 113         {
 114                 return container_.begin();
 115         }
 116
 117         iterator end()
 118         {
 119                 return container_.end();
 120         }
 121
 122         const_iterator end() const
 123         {
 124                 return container_.end();
 125         }
 126
 127         // reverse_iterator rbegin();
 128         // const_reverse_iterator rbegin() const;
 129         // reverse_iterator rend();
 130         // const_reverse_iterator rend() const;
 131
 132         // capacity
 133         size_type size() const
 134         {
 135                 return iterCont_.size();
 136         }
 137
 138         size_type max_size() const
 139         {
 140                 return iterCont_.max_size();
 141         }
 142
 143         // void resize(size_type sz,  T c = T());
 144
 145         size_type capacity() const
 146         {
 147                 return iterCont_.capacity();
 148         }
 149
 150         bool empty() const
 151         {
 152                 return container_.empty();
 153         }
 154
 155         // void reserve(size_type n);
 156
 157         // element access
 158
 159         reference operator[](size_type pos)
 160         {
 161                 return *iterCont_[pos];
 162         }
 163
 164         ///
 165         const_reference operator[](size_type pos) const
 166         {
 167                 return *iterCont_[pos];
 168         }
 169
 170         reference at(size_type pos)
 171         {
 172                 return *iterCont_.at(pos);
 173         }
 174
 175         const_reference at(size_type pos) const
 176         {
 177                 return *iterCont_.at(pos);
 178         }
 179
 180         reference front()
 181         {
 182                 return container_.front();
 183         }
 184
 185         const_reference front() const
 186         {
 187                 return container_.front();
 188         }
 189
 190         reference back()
 191         {
 192                 return container_.back();
 193         }
 194
 195         const_reference back() const
 196         {
 197                 return container_.back();
 198         }
 199
 200         // modifiers
 201
 202         void push_back(T const & x)
 203         {
 204                 typename Container::iterator it =
 205                         container_.insert(container_.end(), x);
 206                 iterCont_.push_back(it);
 207         }
 208
 209         void pop_back()
 210         {
 211                 container_.pop_back();
 212                 iterCont_.pop_back();
 213         }
 214
 215         iterator insert(iterator position, T const & x)
 216         {
 217                 typename Container::iterator it =
 218                         container_.insert(position, x);
 219                 recreateVector();
 220                 return it;
 221         }
 222
 223         // void insert(iterator position, size_type n, T const & x);
 224
 225         template<class InputIterator>
 226         void insert(iterator position,
 227                     InputIterator first, InputIterator last)
 228         {
 229                 container_.insert(position, first, last);
 230                 recreateVector();
 231         }
 232
 233         iterator erase(iterator position)
 234         {
 235                 typename Container::iterator it =
 236                         container_.erase(position);
 237                 recreateVector();
 238                 return it;
 239         }
 240
 241         iterator erase(iterator first, iterator last)
 242         {
 243                 typename Container::iterator it =
 244                         container_.erase(first, last);
 245                 recreateVector();
 246                 return it;
 247         }
 248
 249         void swap(size_t i, size_t j)
 250         {
 251                 size_t const p = std::max(i, j);
 252                 size_t const q = std::min(i, j);
 253                 container_.splice(iterCont_[p], container_, iterCont_[q]);
 254                 container_.splice(iterCont_[q], container_, iterCont_[p]);
 255                 recreateVector();
 256         }
 257
 258         void splice(iterator where, iterator first, iterator last)
 259         {
 260                 container_.splice(where, container_, first, last);
 261                 recreateVector();
 262         }
 263
 264         void swap(RandomAccessList & x)
 265         {
 266                 std::swap(container_, x.container_);
 267                 std::swap(iterCont_, x.iterCont_);
 268         }
 269
 270         void clear()
 271         {
 272                 container_.clear();
 273                 iterCont_.clear();
 274         }
 275
 276         size_t position(iterator it) const
 277         {
 278                 size_t const s = iterCont_.size();
 279                 for (size_t i = 0; it != s; ++i) {
 280                         if (iterCont_[i] == it)
 281                                 return i;
 282                 }
 283                 return s;
 284         }
 285
 286         size_t position(const_iterator it) const
 287         {
 288                 size_t const s = iterCont_.size();
 289                 for (size_t i = 0; i != s; ++i) {
 290                         if (iterCont_[i] == it)
 291                                 return i;
 292                 }
 293                 return s;
 294         }
 295
 296
 297         const_iterator constIterator(size_t i) const
 298         {
 299                 return iterCont_[i];
 300         }
 301
 302 private:
 303         void recreateVector()
 304         {
 305                 iterCont_.clear();
 306                 typename Container::iterator beg = container_.begin();
 307                 typename Container::iterator end = container_.end();
 308                 for (; beg != end; ++beg)
 309                         iterCont_.push_back(beg);
 310         }
 311
 312         /// Our container.
 313         Container container_;
 314         /// Our container of iterators.
 315         IterCont iterCont_;
 316 };
 317
 318
 319 } // namespace lyx
 320
 321 #endif