Abdelrazak Younes a écrit :
An idea for testing: would i be possible
to add temporarily to the at() method a test that the paragraph
returned by the vector is the same as what would be obtained from the
list (by std::advance, I guess)? This would help to make sure the
vector and the list are always in sync.
With current class, insertion/deletion are always done at the same time
so this simply could not happen. And the fact that the inner vector and
list are private member, prevents any false manipulation. But when/if we
do the optimisation for multiple insertion/deletion this would be useful
indeed. I'll add this test next week-end.
Actually, it was easy enough that I've done it using boost::next.
Attached.
Abdel.
// -*- C++ -*-
/**
* \file RandomAccessList.h
* This file is part of LyX, the document processor.
* Licence details can be found in the file COPYING.
*
* \author Abdelrazak Younes
*
* Full author contact details are available in file CREDITS.
*
*/
#ifndef _RANDOM_ACESS_LIST_H
#define _RANDOM_ACESS_LIST_H
#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.
A typical use would be:
typedef RandomAccessList<some_class> MyContainer;
Then you can use MyContainer as if it was a standard std::vector<some_class>
for operator[] access
and as if it was a standard std::list for iterator access.
The main difference with std::vector is that insertion of elements is much less
costly. Compared
to a standard list alone, there is of course a small overhead because the class
always keeps its
internal vector of iterator (ItVector_) up to date.
*/
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 {
iterator it=*this;
std::advance(it, pos);
return it;
}
difference_type operator-(iterator it2) const {
return std::distance(*this, it2);
}
const iterator & operator=(base_it const & it) {
Container::const_iterator::operator=(it);
return *this;
}
};
///
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 {
const_iterator it=*this;
std::advance(it, pos);
return it;
}
difference_type operator-(const_iterator it2) const {
return std::distance(*this, it2);
}
const const_iterator & operator=(base_cit const & it) {
Container::const_iterator::operator=(it);
return *this;
}
const const_iterator & operator=(base_it const & it) {
Container::const_iterator::operator=(it);
return *this;
}
const const_iterator & operator=(iterator const & it) {
Container::const_iterator::operator=(static_cast<base_it>(it));
return *this;
}
};
private:
/// Our container.
Container Container_;
/// Our vector of container iterator.
std::vector<iterator> ItVector_;
public:
///
RandomAccessList() {
}
/// Copy constructor.
RandomAccessList(RandomAccessList const & ext_list) {
for (const_iterator it = ext_list.begin(); it !=
ext_list.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) {
for (size_t i = pos; i != pos+length; ++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) {
for (It it = it_start; it != it_end; ++it)
push_back(*it);
}
/// Copy ext_list.
void assign(RandomAccessList const & ext_list) {
assign(ext_list, 0, ext_list.size());
}
/// Copy ext_list from it_start to it_end.
template<class It>
void assign(It it_start, It it_end) {
clear();
for (It it = it_start; it != it_end; ++it)
push_back(*it);
}
/// Copy "length" elements from ext_list beginning at pos.
void assign(RandomAccessList const & ext_list, size_t pos, size_t
length) {
clear();
for (size_t i = pos; i != pos+length; ++i)
push_back(ext_list[i]);
}
value_type & at(size_t pos) {
// This test should be removed once output_*.C has been
verified.
if (pos >= ItVector_.size()) {
lyxerr[Debug::ACTION] << "trying to access element " <<
pos
<< " while size is "<< size() << endl;
return *ItVector_[size()-1];
}
// This test should be already done if compiled with
--enable-stdlib-debug
// but apparently not with mingw.
BOOST_ASSERT(pos < ItVector_.size());
// Make sure ItVector_ and Container_ are always in sync.
BOOST_ASSERT(ItVector_[pos]==boost::next(Container_.begin(),pos));
return *ItVector_[pos];
}
/// \todo remove first test (pos >= ItVector_.size()) when output_*.C
has been verified.
value_type const & at(size_t pos) const {
// This test should be removed once output_*.C has been
verified.
if (pos >= ItVector_.size()) {
lyxerr[Debug::ACTION] << "trying to access element " <<
pos
<< " while size is "<< size() << endl;
return *ItVector_[size()-1];
}
// This test should be already done if compiled with
--enable-stdlib-debug
// but apparently not with mingw.
BOOST_ASSERT(pos < ItVector_.size());
// Make sure ItVector_ and Container_ are always in sync.
BOOST_ASSERT(ItVector_[pos]==boost::next(Container_.begin(),pos));
return *ItVector_[pos];
}
size_t size() const {
return ItVector_.size();
}
const_iterator begin() const {
return Container_.begin();
}
iterator begin() {
return Container_.begin();
}
const_iterator end() const {
return Container_.end();
}
iterator end() {
return Container_.end();
}
value_type & back() {
return Container_.back();
}
value_type const & back() const {
return Container_.back();
}
value_type & front() {
return Container_.front();
}
value_type const & front() const {
return Container_.front();
}
bool empty() const {
return Container_.empty();
}
void clear() {
Container_.clear();
ItVector_.clear();
}
/// Erases 'length' elements starting from pos.
/**
\todo This could be optimized a bit by rebuilding ItVector instead of
multiple deletion.
*/
bool erase(size_t pos, size_t length) {
bool result=true;
for (size_t i = pos; i != pos+length; ++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);
}
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;
for (typename SomeContainer::const_iterator it =
some_container.begin();
it != some_container.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;
for (size_t j = ext_pos; j != ext_pos+length; ++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;
}
}; // RandomAccessList
#endif
