rvec.h

/* -*- c++ -*- */
/*
 * A vector class template allowing gaps
 *
 * Copyright (C) 2004 Oskar Enoksson (enok@lysator.liu.se)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  
 */
#ifndef RPTR_RVEC_HDR
#define RPTR_RVEC_HDR

#include "rptr.h"

#include <vector>
#include <stdexcept>

namespace rptr {

  template<class T>
  class Rvec {
  public:
    typedef T value_type;
  private:
    struct Node {
      Rptr<T> ptr;
      typename std::vector<Node>::difference_type prev;
      typename std::vector<Node>::difference_type next;
      Node(): prev(0), next(0) {}
    };
  public:
    typedef value_type &reference;
    typedef const value_type &const_reference;
    typedef Rptr<T> pointer;
    typedef Rptr<const T> const_pointer;
    typedef typename std::vector<Node>::difference_type difference_type;
    typedef typename std::vector<Node>::size_type size_type;
  private:
    size_type begn;
    size_type rbegn;
    size_type sze;
    std::vector<Node> v;
  public:
    class const_iterator;

    class iterator {
      typename std::vector<Node>::iterator vi;
      friend class Rvec;
      friend class const_iterator;
      inline iterator(typename std::vector<Node>::iterator vi0):
        vi(vi0) {}

    public:
      typedef std::bidirectional_iterator_tag iterator_category;
      //typedef typename std::vector<Node>::iterator::iterator_category iterator_category;
      typedef Rvec::value_type value_type;
      typedef Rvec::difference_type difference_type;

      typedef Rvec::pointer pointer;
      typedef Rvec::reference reference;

      inline reference operator *() const { 
        return *vi->ptr; 
      }
      inline pointer operator ->() const { 
        return vi->ptr;
      }
      inline pointer ptr() const { 
        return vi->ptr; 
      }
      inline bool operator ==(const iterator &right) const { 
        return vi==right.vi; 
      }
      inline bool operator !=(const iterator &right) const { 
        return vi!=right.vi; 
      }
      inline bool operator <(const iterator &right) const { 
        return vi<right.vi; 
      }
      inline iterator & operator ++() {
        vi += vi->next;
        return *this; 
      }
      inline iterator operator ++(int) { 
        iterator tmp(*this);
        operator++(); 
        return tmp; 
      }
      inline iterator & operator --() {
        vi += vi->prev;
        return *this; 
      }
      inline iterator operator --(int) { 
        iterator tmp(*this);
        operator--(); 
        return tmp; 
      }
    };
    class const_iterator {
      typename std::vector<Node>::const_iterator vi;
      friend class Rvec;
      friend class iterator;
      inline const_iterator(typename std::vector<Node>::const_iterator vi0):
        vi(vi0) {}

    public:
      inline const_iterator(const iterator &src): vi(src.vi) {}
      typedef std::bidirectional_iterator_tag iterator_category;
      //typedef typename std::vector<Node>::const_iterator::iterator_category iterator_category;
      typedef Rvec::value_type value_type;
      typedef Rvec::difference_type difference_type;

      typedef Rvec::const_pointer pointer;
      typedef Rvec::const_reference reference;

      inline reference operator *() const { 
        return *vi->ptr; 
      }
      inline pointer operator ->() const { 
        return vi->ptr; 
      }
      inline pointer ptr() const { 
        return vi->ptr; 
      }
      inline bool operator ==(const const_iterator &right) const { 
        return vi==right.vi; 
      }
      inline bool operator !=(const const_iterator &right) const { 
        return vi!=right.vi; 
      }
      inline bool operator <(const const_iterator &right) const { 
        return vi<right.vi; 
      }
      inline const_iterator & operator ++() {
        vi += vi->next;
        return *this; 
      }
      inline const_iterator operator ++(int) { 
        const_iterator tmp(*this);
        operator++(); 
        return tmp; 
      }
      inline const_iterator & operator --() {
        vi += vi->prev;
        return *this; 
      }
      inline const_iterator operator --(int) { 
        const_iterator tmp(*this);
        operator--(); 
        return tmp; 
      }
    };


    inline Rvec(): begn(0), rbegn(0), sze(0), v(1) {
    }



    inline const_reference operator[](size_type n) const {
      if(!defined(n)) {
        throw std::out_of_range
          ("Rvec - attempt to access undefined element");
      }
      return *v[n+1].ptr;
    }
    inline const_pointer ptr(size_type n) const {
      if(!defined(n)) {
        throw std::out_of_range
          ("Rvec - attempt to access undefined element");
      }
      return v[n+1].ptr;
    }
    inline const_iterator begin() const { 
      return const_iterator(v.begin()+begn);
    }
    inline const_iterator end() const {
      return const_iterator(v.begin());
    }
    inline int ibegin() const {
      return begn-1;
    }
    inline int inext(int id) const {
      return id + v[id+1].next;
    }
    inline int iprev(int id) const {
      return id + v[id+1].prev;
    }
    inline size_type id(const iterator &it) const {
      return it.vi-v.begin()-1;
    }
    inline size_type id(const const_iterator &it) const {
      return it.vi-v.begin()-1;
    }
    inline size_type size() const {
      return sze;
    }
    inline bool defined(size_type n) const {
      return n+1>0 && n+1<v.size() && v[n+1].next!=0;
    }
    inline bool empty() const { 
      return begn==0;
    }



    inline iterator begin() { 
      return iterator(v.begin()+begn);
    }
    inline iterator end() { 
      return iterator(v.begin());
    }
    inline pointer ptr(size_type n) {
      if(!defined(n)) {
        throw std::out_of_range
          ("Rvec - attempt to access undefined position");
      }
      return v[n+1].ptr;
    }
    inline reference operator[](size_type n) {
      if(!defined(n)) {
        throw std::out_of_range
          ("Rvec - attempt to access undefined position");
      }
      return *v[n+1].ptr;
    }
    inline void swap(const Rvec &src) { 
      v.swap(src.v);
      size_type tmp = src.sze;
      src.sze = sze;
      sze = tmp;
      tmp = src.begn;
      src.begn = begn;
      begn = tmp;
    }
    inline size_type insert(pointer x) {
      size_type pos;
      for(pos=1; pos<v.size(); ++pos) {
        if(v[pos].next==0) {
          break;
        }
      }
      return set(pos-1,x);
    }
    size_type set(size_type pos, pointer x);
    inline void erase(size_type pos) {
      erase(iterator(v.begin()+pos+1));
    }
    void erase(const iterator &i);
    void clear() {
      v.resize(1);
      sze = rbegn = begn = 0;
    }
  };

  template<class T>
  typename Rvec<T>::size_type Rvec<T>::set(size_type pos, pointer x) {
    if(x==0) {
      if(defined(pos))
        erase(pos);
      return -1;
    }
    pos+=1;
    if(pos>=v.size()) {
      // Append element at end
      v.resize(pos+1);
    }
    if(v[pos].next==0) {
      size_type prev;
      // Find first preceeding non-null element
      for(prev=pos-1; prev>0; --prev) {
        if(v[prev].next!=0) {
          break;
        }
      }
      v[pos].prev=prev-pos;
      if(prev) {
        // We have a preceeding element!
        size_type next = prev+v[prev].next;
        v[pos].next=next-pos;
        v[prev].next=pos-prev;
        if(next) {
          // We have a following element!
          v[next].prev=pos-next;
        } else {
          // This element is the last
          rbegn = pos;
        }
      } else {
        // This element is the first
        begn = pos;
        size_type next;
        // Find first following non-null element
        for(next=pos+1; next<v.size(); ++next) {
          if(v[next].next!=0) {
            break;
          }
        }
        if(next<v.size()) {
          // We have a following element!
          v[pos].next = next-pos;
          v[next].prev = pos-next;
        } else {
          // This element is last
          v[pos].next = -pos;
          rbegn=pos;
        }
      }
      ++sze;
    }
    v[pos].ptr = x;
    return pos-1;
  }

  template<class T>
  void Rvec<T>::erase(const iterator &i) {
    size_type pos = id(i)+1;
    if(pos==0) {
      throw std::out_of_range
        ("Rvec - attempt to erase 'end()' iterator");
    }
    if(pos>v.size()) {
      throw std::out_of_range
        ("Rvec - attempt to erase element out of range");
    }
    if(v[pos].next==0) {
      throw std::out_of_range
        ("Rvec - attempt to erase undefined element");
    }
    size_type next = pos+v[pos].next;
    size_type prev = pos+v[pos].prev;
    --sze;
    if(next) {
      if(prev) {
        v[next].prev = prev-next;
        v[prev].next = next-prev;
      } else {
        // Element is at beginning
        v[next].prev = -next;
        begn = next;
      }
    } else {
      // Element is at end
      if(prev) {
        v[prev].next = -prev;
        rbegn = prev;
      } else {
        // Element was the only element
        rbegn = begn = 0;
      }
      v.resize(rbegn+1);
    }
    v[pos].ptr = 0;
    v[pos].next=v[pos].prev=0;
  }
}
#endif

---