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