src/util/list-container.h

   1 /*
   2  * Inkscape::Util::ListContainer - encapsulates lists as STL containers,
   3  *                                 providing fast appending
   4  *
   5  * Authors:
   6  *   MenTaLguY <mental@rydia.net>
   7  *
   8  * Copyright (C) 2005 MenTaLguY
   9  *
  10  * Released under GNU GPL, read the file 'COPYING' for more information
  11  */
  12
  13 #ifndef SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H
  14 #define SEEN_INKSCAPE_UTIL_LIST_CONTAINER_H
  15
  16 #include <limits>
  17 #include "util/list.h"
  18
  19 namespace Inkscape {
  20
  21 namespace Util {
  22
  23 template <typename T>
  24 class ListContainer {
  25 public:
  26     /* default constructible */
  27     ListContainer() {}
  28
  29     /* assignable */
  30     ListContainer(ListContainer const &other) {
  31         *this = other;
  32     }
  33     ListContainer &operator=(ListContainer const &other) {
  34         clear();
  35         for ( const_iterator iter = other.begin() ; iter ; ++iter ) {
  36             push_back(*iter);
  37         }
  38         return *this;
  39     }
  40     void swap(ListContainer<T> &other) {
  41         std::swap(other._head, _head);
  42         std::swap(other._tail, _tail);
  43     }
  44
  45     /* equality comparable */
  46     bool operator==(ListContainer const &other) const {
  47         const_iterator iter = _head;
  48         const_iterator other_iter = other._head;
  49         while ( iter && other_iter ) {
  50             if (!( *iter == *other_iter )) {
  51                 return false;
  52             }
  53             ++iter;
  54             ++other_iter;
  55         }
  56         return !iter && !other_iter;
  57     }
  58     bool operator!=(ListContainer const &other) const {
  59         return !operator==(other);
  60     }
  61
  62     /* lessthan comparable */
  63     bool operator<(ListContainer const &other) const {
  64         const_iterator iter = _head;
  65         const_iterator other_iter = other._head;
  66         while ( iter && other_iter ) {
  67             if ( *iter < *other_iter ) {
  68                 return true;
  69             } else if ( *other_iter < *iter ) {
  70                 return false;
  71             }
  72             ++iter;
  73             ++other_iter;
  74         }
  75         return bool(other_iter);
  76     }
  77     bool operator>=(ListContainer const &other) const {
  78         return !operator<(other);
  79     }
  80
  81     /* container */
  82     typedef typename List<T>::value_type value_type;
  83     typedef List<T> iterator;
  84     typedef List<T const> const_iterator;
  85     typedef typename List<T>::reference reference;
  86     typedef typename List<T>::const_reference const_reference;
  87     typedef typename List<T>::pointer pointer;
  88     typedef typename List<T>::difference_type difference_type;
  89     typedef std::size_t size_type;
  90
  91     iterator begin() { return _head; }
  92     const_iterator begin() const { return _head; }
  93     iterator end() { return iterator(); }
  94     const_iterator end() const { return const_iterator(); }
  95     size_type size() const {
  96         size_type size=0;
  97         for ( iterator iter = _head ; iter ; ++iter ) {
  98             size++;
  99         }
 100         return size;
 101     }
 102     size_type max_size() const {
 103         return std::numeric_limits<std::size_t>::max();
 104     }
 105     bool empty() const { return !_head; }
 106
 107     /* sequence */
 108     ListContainer(size_type count, const_reference value) {
 109         for ( ; count ; --count ) {
 110             push_back(value);
 111         }
 112     }
 113     ListContainer(size_type count) {
 114         value_type default_value;
 115         for ( ; count ; --count ) {
 116             push_back(default_value);
 117         }
 118     }
 119     template <typename ForwardIterator>
 120     ListContainer(ForwardIterator i, ForwardIterator j) {
 121         for ( ; i != j ; ++i ) {
 122             push_back(*i);
 123         }
 124     }
 125
 126     reference front() { return *_head; }
 127     const_reference front() const { return *_head; }
 128
 129     iterator insert(const_iterator position, const_reference value) {
 130         if (position) {
 131             if ( position != _head ) {
 132                 MutableList<T> added(value);
 133                 MutableList<T> before=_before(position);
 134                 set_rest(added, rest(before));
 135                 set_rest(before, added);
 136                 return added;
 137             } else {
 138                 push_front(value);
 139                 return _head;
 140             }
 141         } else {
 142             push_back(value);
 143             return _tail;
 144         }
 145     }
 146     void insert(const_iterator position, size_type count, const_reference value)
 147     {
 148         _insert_from_temp(position, ListContainer(count, value));
 149     }
 150     template <typename ForwardIterator>
 151     void insert(const_iterator position, ForwardIterator i, ForwardIterator j) {
 152         _insert_from_temp(position, ListContainer(i, j));
 153     }
 154     void erase(const_iterator position) {
 155         erase(position, rest(position));
 156     }
 157     void erase(const_iterator i, const_iterator j) {
 158         if ( i == _head ) {
 159             _head = static_cast<MutableList<T> &>(j);
 160             if ( !j || !rest(j) ) {
 161                 _tail = _head;
 162             }
 163         } else {
 164             MutableList<T> before=_before(i);
 165             if (j) {
 166                 set_rest(before, static_cast<MutableList<T> &>(j));
 167             } else {
 168                 set_rest(before, MutableList<T>());
 169                 _tail = before;
 170             }
 171         }
 172     }
 173     void clear() {
 174         _head = _tail = MutableList<T>();
 175     }
 176     void resize(size_type size, const_reference fill) {
 177         MutableList<T> before;
 178         MutableList<T> iter;
 179         for ( iter = _head ; iter && size ; ++iter ) {
 180             before = iter;
 181             size--;
 182         }
 183         if (size) {
 184             ListContainer temp(size, fill);
 185             if (empty()) {
 186                 _head = temp._head;
 187                 _tail = temp._tail;
 188             } else {
 189                 set_rest(_tail, temp._head);
 190                 _tail = temp._tail;
 191             }
 192         } else if (iter) {
 193             if (before) {
 194                 set_rest(before, MutableList<T>());
 195                 _tail = before;
 196             } else {
 197                 _head = _tail = MutableList<T>();
 198             }
 199         }
 200     }
 201     void resize(size_type size) {
 202         resize(size, value_type());
 203     }
 204
 205     /* front insertion sequence */
 206     void push_front(const_reference value) {
 207         if (_head) {
 208             _head = cons(value, _head);
 209         } else {
 210             _head = _tail = MutableList<T>(value);
 211         }
 212     }
 213     void pop_front() {
 214         if (_head) {
 215             _head = rest(_head);
 216             if (!_head) {
 217                 _tail = _head;
 218             }
 219         }
 220     }
 221
 222     /* back insertion sequence */
 223     reference back() { return *_tail; }
 224     const_reference back() const { return *_tail; }
 225     void push_back(const_reference value) {
 226         if (_tail) {
 227             MutableList<T> added(value);
 228             set_rest(_tail, added);
 229             _tail = added;
 230         } else {
 231             _head = _tail = MutableList<T>(value);
 232         }
 233     }
 234     // we're not required to provide pop_back if we can't
 235     // implement it efficiently
 236
 237     /* additional */
 238     MutableList<T> detatchList() {
 239         MutableList<T> list=_head;
 240         _head = _tail = MutableList<T>();
 241         return list;
 242     }
 243     iterator insert_after(const_iterator pos, const_reference value) {
 244         MutableList<T> added(value);
 245         if (pos) {
 246             MutableList<T> before=static_cast<MutableList<T> &>(pos);
 247             set_rest(added, rest(before));
 248             set_rest(before, added);
 249             if ( _tail == before ) {
 250                 _tail = added;
 251             }
 252         } else {
 253             push_front(value);
 254         }
 255     }
 256     void insert_after(const_iterator position, size_type count,
 257                       const_reference value)
 258     {
 259         _insert_after_from_temp(position, ListContainer(count, value));
 260     }
 261     template <typename ForwardIterator>
 262     void insert_after(const_iterator position,
 263                       ForwardIterator i, ForwardIterator j)
 264     {
 265         _insert_after_from_temp(position, ListContainer(i, j));
 266     }
 267     void erase_after(const_iterator position) {
 268         if (!position) {
 269             pop_front();
 270         } else {
 271             MutableList<T> before=static_cast<MutableList<T> &>(position);
 272             MutableList<T> removed=rest(before);
 273             set_rest(before, rest(removed));
 274             if ( removed == _tail ) {
 275                 _tail = before;
 276             }
 277         }
 278     }
 279
 280 private:
 281     MutableList<T> _head;
 282     MutableList<T> _tail;
 283
 284     MutableList<T> _before(const_iterator position) {
 285         for ( MutableList<T> iter = _head ; iter ; ++iter ) {
 286             if ( rest(iter) == position ) {
 287                 return iter;
 288             }
 289         }
 290         return MutableList<T>();
 291     }
 292     void _insert_from_temp(const_iterator pos, ListContainer const &temp) {
 293         if (temp.empty()) {
 294             return;
 295         }
 296         if (empty()) { /* if empty, just take the whole thing */
 297             _head = temp._head;
 298             _tail = temp._tail;
 299         } else if (pos) {
 300             if ( pos == _head ) { /* prepend */
 301                 set_rest(temp._tail, _head);
 302                 _head = temp._head;
 303             } else { /* insert somewhere in the middle */
 304                 MutableList<T> before=_before(pos);
 305                 set_rest(temp._tail, static_cast<MutableList<T> &>(pos));
 306                 set_rest(before, temp._head);
 307             }
 308         } else { /* append */
 309             set_rest(_tail, temp._head);
 310             _tail = temp._tail;
 311         }
 312     }
 313     void _insert_after_from_temp(const_iterator pos,
 314                                  ListContainer const &temp)
 315     {
 316         if (temp.empty()) {
 317             return;
 318         }
 319         if (empty()) { /* if empty, just take the whole thing */
 320             _head = temp._head;
 321             _tail = temp._tail;
 322         } else if (pos) {
 323             if ( pos == _tail ) { /* append */
 324                 set_rest(_tail, temp._head);
 325                 _tail = temp._tail;
 326             } else { /* insert somewhere in the middle */
 327                 MutableList<T> before=static_cast<MutableList<T> &>(pos);
 328                 set_rest(temp._tail, rest(before));
 329                 set_rest(before, temp._head);
 330             }
 331         } else { /* prepend */
 332             set_rest(temp._tail, _head);
 333             _head = temp._head;
 334         }
 335     }
 336 };
 337
 338 }
 339
 340 }
 341
 342 #endif
 343 /*
 344   Local Variables:
 345   mode:c++
 346   c-file-style:"stroustrup"
 347   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 348   indent-tabs-mode:nil
 349   fill-column:99
 350   End:
 351 */
 352 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :