On Wed, Mar 08, 2006 at 04:28:30PM +0100, Abdelrazak Younes wrote:
> #ifndef _RANDOM_ACESS_LIST_H
> #define _RANDOM_ACESS_LIST_H
#ifndef RANDOM_ACESS_LIST_H
#define RANDOM_ACESS_LIST_H
Leading underscore + capital letter is reserved for the compiler
implementation. Nothing we are supposed to use.
> #include "debug.h"
>
> #include <boost/utility.hpp>
>
> #include <vector>
> #include <list>
> #include <algorithm>
>
> using std::endl;
>
> /// Random Access List.
> /**
> This templatized class provide a std::vector like interface to a standard
> std::list
> underneath. An important property is that it keeps the std::list::iterator
> interface.
Please restrict line length to 72 (+\epsilon) chars.
> template <class T>
> class RandomAccessList
> {
> protected:
> typedef std::list<T> Container;
> typedef typename Container::const_iterator base_cit;
> typedef typename Container::iterator base_it;
>
> public:
>
> typedef T value_type;
> typedef typename Container::difference_type difference_type;
> typedef size_t size_type;
>
> ///
> class iterator: public Container::iterator
> {
> public:
> iterator() {
> }
> iterator(base_it const & it) {
> Container::iterator::operator=(it);
> }
> iterator & operator+=(difference_type pos) {
> std::advance(*this, pos);
> return *this;
> }
> iterator operator+(difference_type pos) const {
> return boost::next(*this,pos);
> }
> difference_type operator-(iterator it2) const {
> return std::distance(it2, *this);
> }
It shouldn't be much of a difference, but the canonical way for
such a 'symmetric' operation is to have it as free function outside the
class.
> };
>
> ///
> class const_iterator: public Container::const_iterator
> {
> public:
> const_iterator() {
> }
> const_iterator(base_cit const & it) {
> Container::const_iterator::operator=(it);
> }
> const_iterator(iterator const & it) {
>
> Container::const_iterator::operator=(static_cast<base_it>(it));
> }
> const_iterator & operator+=(difference_type pos) {
> std::advance(*this, pos);
> return *this;
> }
> const_iterator operator+(difference_type pos) const {
> return boost::next(*this, pos);
> }
> difference_type operator-(const_iterator it2) const {
> return std::distance(it2, *this);
> }
> };
>
> private:
> /// Our container.
> Container Container_;
> /// Our vector of container iterator.
> std::vector<iterator> ItVector_;
I am not sure there are many precedence for capitalized member variables
in LyX code.
>
> public:
> ///
> RandomAccessList() {
> }
>
> /// Copy constructor.
> RandomAccessList(RandomAccessList const & ext_list) {
> const_iterator it_end = ext_list.end();
> for (const_iterator it = ext_list.begin(); it != it_end; ++it)
> push_back(*it);
> }
>
> /// Partial copy constructor.
> /**
> Copy "length" elements from ext_list beginning at pos.
> */
> RandomAccessList(RandomAccessList const & ext_list, size_t pos, size_t
> length) {
> size_t end = pos+length;
size_t const end = pos + length;
> for (size_t i = pos; i != end; ++i)
> push_back(ext_list[i]);
> }
>
> /// Construct a new RandomAccessList by copying elements pointed from
> it_start to it_end.
> template<class It>
> RandomAccessList(It it_start, It it_end) {
Maybe adding 'reserve' is in order.
> for (It it = it_start; it != it_end; ++it)
> push_back(*it);
> }
>
[...]
'swap' would be nice to have in the long run...
>
> /// Erases 'length' elements starting from pos.
> /**
> \todo This could be optimized a bit by rebuilding ItVector instead of
> multiple deletion.
>
> Comments from Angus: use std::remove_if and vector<>::erase, passing the
> same predicate to remove_if as is used by erase(size_t);
> Refactor the other erase() member funtions to use this predicate
> also?
> std::remove_if doesn't actually remove anything from the vector. It
> simply rearranges the
> contents so that the stuff to be removed is all at the end, making it
> trivial
> (and cheap) to then used "itVector_.erase(it, itVector_.end());" to
> resize the
> vector. (it here is the iterator returned by std::remove_if). You just
> need to
> write the predicate that would actually flag up elements for removal.
> */
> bool erase(size_t pos, size_t length) {
> bool result=true;
> size_t end = pos+length;
Spacing
> for (size_t i = pos; i != end; ++i)
> result = result && erase(i);
>
> return result;
> }
>
> /// Erases last element.
> void pop_back() {
> lyxerr[Debug::ACTION] << "pop_back from Container"<< endl;
> Container_.pop_back();
> ItVector_.pop_back();
> lyxerr[Debug::ACTION] << "pop_back done"<< endl;
> }
>
> /// Erases the element at position pos.
> bool erase(size_t pos) {
>
> if (pos >= ItVector_.size()) {
> lyxerr[Debug::ACTION] << "trying to erase element at "
> << pos << " while size is "<< size() << endl;
> // What happened here?
> return false;
> }
>
> if (pos == ItVector_.size()-1) {
> pop_back();
> return true;
> }
>
> lyxerr[Debug::ACTION] << "erasing element from Container at "
> << pos << endl;
> Container_.erase(ItVector_[pos]);
> ItVector_.erase(ItVector_.begin()+pos);
> lyxerr[Debug::ACTION] << "erasing done"<< endl;
> return true;
> }
>
> bool erase(iterator it) {
> size_t pos = std::distance(Container_.begin(),
> static_cast<base_it>(it));
> return erase(pos);
> }
>
> bool erase(iterator start, iterator end) {
> size_t startpos = std::distance(Container_.begin(),
> static_cast<base_it>(start));
> size_t endpos = std::distance(Container_.begin(),
> static_cast<base_it>(end));
> return erase(startpos, endpos-startpos);
> }
const + spacing.
>
> void push_back(value_type const & new_element)
> {
> lyxerr[Debug::ACTION] << "push_back new_element in Container"<<
> endl;
> iterator it = Container_.insert(Container_.end(), new_element);
> ItVector_.push_back(it);
> lyxerr[Debug::ACTION] << "push_back done"<< endl;
> }
>
> /// Inserts the contents of an external container at position pos.
> /**
> The subsequent elements are shifted toward the end.
>
> \todo This could be optimized a bit by rebuilding ItVector instead of
> multiple insertion.
> */
> template<class SomeContainer>
> bool insert(size_t pos, SomeContainer const & some_container) {
>
> bool result=true;
> size_t i=pos;
> typedef typename SomeContainer::const_iterator It;
> It it_end = some_container.end();
> for (It it = some_container.begin(); it != it_end; ++it) {
> result = result && insert(i, *it);
> ++i;
> }
> return result;
> }
>
> /// Inserts an external RandomAccessList at position pos.
> /**
> The subsequent elements are shifted toward the end.
>
> \todo This could be optimized a bit by rebuilding ItVector instead of
> multiple insertion
> and maybe using list::splice.
> */
> bool insert(size_t pos, RandomAccessList const & ext_list, size_t
> ext_pos, size_t length) {
>
> bool result=true;
> size_t i=pos;
> size_t ext_end = ext_pos+length;
> for (size_t j = ext_pos; j != ext_end; ++j) {
> result = result && insert(i, ext_list[j]);
> ++i;
> }
> return result;
> }
>
> /// Inserts external elements pointed by iterator it_start and it_end
> at position pos.
> /**
> The subsequent elements are shifted toward the end.
> \return the position after the last inserted element.
>
> \todo This could be optimized a bit by rebuilding ItVector instead of
> multiple insertion
> and maybe using list::splice.
> */
> template<class It>
> size_t insert(size_t pos, It it_start, It it_end) {
>
> bool result=true;
> size_t i=pos;
> for (It it = it_start; it != it_end; ++it) {
> result = result && insert(i, *it);
> ++i;
> }
> if (result)
> return i;
>
> return size();
> }
>
> /// Inserts external elements pointed by iterator it_start and it_end
> before element pointed by it.
> /**
> The subsequent elements are shifted toward the end.
> \return the iterator after the last inserted element.
>
> \todo This could be optimized a bit by rebuilding ItVector instead of
> multiple insertion
> and maybe using list::splice.
> */
> template<class It>
> iterator insert(iterator it, It it_start, It it_end) {
>
> size_t pos = std::distance(Container_.begin(),
> static_cast<base_it>(it));
> pos = insert(pos, it_start, it_end);
> if (pos < size())
> return ItVector_[pos];
>
> return Container_.end();
> }
>
> /// Inserts new_element at position pos.
> /// The subsequent value_types are shifted toward the end.
> bool insert(size_t pos, value_type const & new_element) {
>
> if (pos > ItVector_.size()) {
> lyxerr[Debug::ACTION] << "trying to insert element at "
> << pos << " while size is "<< size() << endl;
> // What happened here?
> return false;
> }
>
> if (pos == ItVector_.size()) {
> push_back(new_element);
> return true;
> }
>
> lyxerr[Debug::ACTION] << "inserting new_element in Container at
> "<< pos << endl;
> iterator it = Container_.insert(ItVector_[pos], new_element);
> ItVector_.insert(ItVector_.begin()+pos, it);
> lyxerr[Debug::ACTION] << "insertion done"<< endl;
> return true;
> }
>
> /// Inserts new_element before element pointed by iterator it.
> /**
> \return The iterator pointing to the newly inserted element
> or Container_.end() if the insertion did not succeed.
> */
> iterator insert(iterator it, value_type const & new_element) {
>
> size_t pos = std::distance(Container_.begin(),
> static_cast<base_it>(it));
> if (insert(pos, new_element))
> return ItVector_[pos];
>
> return Container_.end();
> }
>
> value_type & operator[](size_t pos) {
> return at(pos);
> }
>
> value_type const & operator[](size_t pos) const {
> return at(pos);
> }
>
> iterator operator()(size_t pos) {
> return ItVector_[pos];
> }
>
> const_iterator operator()(size_t pos) const {
> return ItVector_[pos];
> }
>
> RandomAccessList & operator=(RandomAccessList const & ext_list) {
> assign(ext_list);
> return *this;
> }
Could you move this up a bit closer to the constructors?
Look pretty good in general.
Andre'
