Dear lyx developers,
Please find attached to this mail my refined patch for the ParagraphList
rewrite problem. This patch makes "ParagraphList" derive from
"it_vector<std::list<Paragraph> >"
"it_vector" is a new template class that implement the vector alike
container. It is defined in "it_vector.h". I don't know how to make a
patch that add a new file so this file is attached to this mail. If you
think of a better name, please let me know.
This patch brings a straight forward replacement for ParagraphList
requiring no other change to current source code as required by Lars. I
mean _zero_ change :-)
I know that lars wanted a cpp only implementation but I think that by
making use of forward declaration of ParagraphList we can avoid to
rebuild the whole tree in case we want to modify it_vector; only those
cpp that works with ParagraphList directly (I know they are quite a few
but that is acceptable IMHO). In any case, playing with the inner
container will need a header change.
You could see "it_vector" as a proposal for the interface we where
taking about: "vector alike" (i.e. operator[] access) _plus_
vector::iterator access. I have covered all practical cases, at least
those used in current source code. I have added some useful interfaces
(ex: position access method, "for_each" methods that use a functor as an
argument, etc), we can add other methods later (or remove some) if this
first iteration is agreed upon developer.
I would like to emphasize that "it_vector" class is _my_ view of it. You
are of course free to use it, modify it or replace it with whatever
implementation you'd like to try that you think is more powerful. I just
hope that you retain the interface I am proposing in "it_vector". I have
tested it only with "list<Paragraph>" as the template argument so I am
sure it will work for any kind of container... but it should. IMHO this
implementation is fast enough, and there are much worse performance
problem to solve.
This patch is not yet ready because Cut&Paste and Copy&Paste don't work
but I prefer to send it now for review. Plus I am not sure whether the
bug is in ParagraphList or in my Qt4 frontend clipboard support. It
seems that what is copied in the selection is rubbish. I can see that
when I copy select something inside the paragraph and then paste it
elsewhere, weird characters are pasted that do not correspond to the
copied ones. I tried to analyze LFUN_COPY but I got lost in "LCursor",
"dociterator" and company... :-(
Someone could tell me where the text copying effectively take place?
Provided that you accept this patch, or at least that you retain the
interface, here is my TODO list concerning this ParagraphList thing:
1) Fix the Copy bug. This one is really difficult...
2) Try to reduce the time of rebuilding the tree in case of a change in
"it_vector.h". A priori, the main limiting factor is that "LyxText.h" is
included at many place in the code.
3) simplify the use of ParagraphList wherever possible by using
some of the convenience interface methods in it_vector (my original
patch did some simplifications already).
4) Rename ParagraphList into paragraph_container.
5) Transform some functions that uses ParagraphList into ParagraphList
member methods (in particular those in paragraph_func.C) or at least
create helper method for classes that uses ParagraphList (Undo,
CutAndPaste, etc).
6) See if some other classes can benefit from it_vector (InsetList and
FontList come to mind).
Abdel.
Index: ParagraphList_fwd.h
===================================================================
RCS file: /var/cvs/lyx/lyx-devel/src/ParagraphList_fwd.h,v
retrieving revision 1.4
diff -u -r1.4 ParagraphList_fwd.h
--- ParagraphList_fwd.h 16 Nov 2004 20:41:37 -0000 1.4
+++ ParagraphList_fwd.h 11 Feb 2006 19:58:48 -0000
@@ -7,27 +7,38 @@
* \author Angus Leeming
*
* Full author contact details are available in file CREDITS.
+ *
+ * \todo Rename this file to ParagraphList.h
*/
#ifndef PARAGRAPH_LIST_FWD_H
#define PARAGRAPH_LIST_FWD_H
+#include <list>
+
#include "paragraph.h"
+#include "it_vector.h"
+
+/// Container for all kind of Paragraphs used in Lyx.
+/**
+The line below could have been enougth
+ typedef it_vector<std::list<Paragraph> > ParagraphList;
-#include <vector>
+but in order to let other files that forward declare ParagraphList, we
+have to derive it from it_vector.
+And then there might be some useful specialisation depending on the
+type of Paragraph we want to store... food for thought.
+*/
-class ParagraphList : public std::vector<Paragraph>
+class ParagraphList: public it_vector<std::list<Paragraph> >
{
public:
- ///
- typedef std::vector<Paragraph> BaseType;
- ///
- ParagraphList();
- ///
- template <class Iter>
- ParagraphList(Iter beg, Iter end)
- : BaseType(beg, end)
- {}
+ ParagraphList()
+ : it_vector<std::list<Paragraph> > () {}
+ ParagraphList(ParagraphList const & externalItVector, size_t start,
size_t end)
+ : it_vector<std::list<Paragraph> > (externalItVector, start,
end) {}
+ ParagraphList(const_iterator it_start, const_iterator it_end)
+ : it_vector<std::list<Paragraph> > (it_start, it_end) {}
};
#endif
Index: paragraph.C
===================================================================
RCS file: /var/cvs/lyx/lyx-devel/src/paragraph.C,v
retrieving revision 1.419
diff -u -r1.419 paragraph.C
--- paragraph.C 5 Feb 2006 13:20:11 -0000 1.419
+++ paragraph.C 13 Feb 2006 14:44:22 -0000
@@ -66,10 +66,6 @@
using std::ostringstream;
-ParagraphList::ParagraphList()
-{}
-
-
Paragraph::Paragraph()
: begin_of_body_(0), pimpl_(new Paragraph::Pimpl(this))
{
// -*- C++ -*-
/**
* \file it_vector.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 IT_VECTOR_H
#define IT_VECTOR_H
#include <vector>
#include <algorithm>
#include "debug.h"
using std::endl;
/// vector of container iterator.
/**
This templatized class provide a std::vector like interface but with another
Container
underneath. An important property is that it keeps the Container iterator
interface.
A typical use would be:
typedef it_vector<std::list<some_class> > MyContainer;
Then you can use MyContainer as if it was a standard std::vector<some_class>.
In this
example, the main difference is that insertion of elements is much less costly
than
with the standard vector. 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 Container>
class it_vector
{
protected:
typedef typename Container::const_iterator base_cit;
typedef typename Container::iterator base_it;
public:
typedef typename Container::value_type value_type;
typedef size_t size_type;
///
class iterator: public Container::iterator
{
public:
iterator() {
}
iterator(base_it const & it) {
Container::iterator::operator=(it);
}
inline iterator & operator+= (int pos) {
std::advance(*this, pos);
return *this;
}
inline iterator operator+ (int pos) const {
iterator it=*this;
std::advance(it, pos);
return it;
}
inline int operator- (iterator it2) const {
return std::distance(*this, it2);
}
inline 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));
}
inline const_iterator & operator+= (int pos) {
std::advance(*this, pos);
return *this;
}
inline const_iterator operator+ (int pos) const {
const_iterator it=*this;
std::advance(it, pos);
return it;
}
inline int operator- (const_iterator it2) const {
return std::distance(*this, it2);
}
inline const const_iterator & operator= (base_cit const & it) {
Container::const_iterator::operator=(it);
return *this;
}
inline const const_iterator & operator= (base_it const & it) {
Container::const_iterator::operator=(it);
return *this;
}
inline 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:
///
it_vector() {
}
/// Construct a new it_vector by copying externalItVector from start to
end.
it_vector(it_vector const & externalItVector, size_t start, size_t end)
{
for (size_t i = start; i != end; ++i)
push_back(externalItVector[i]);
}
/// Construct a new it_vector by copying elements pointed from it_start
to it_end.
it_vector(const_iterator it_start, const_iterator it_end) {
for (const_iterator it = it_start; it != it_end; ++it)
push_back(*it);
}
/// Copy externalItVector.
inline void copy(it_vector const & externalItVector) {
copy(externalItVector, 0, externalItVector.size());
}
/// Copy externalItVector from it_start to it_end.
void copy(const_iterator it_start, const_iterator it_end) {
clear();
for (const_iterator it = it_start; it != it_end; ++it)
push_back(*it);
}
/// Copy externalItVector from start to end.
void copy(it_vector const & externalItVector, size_t start, size_t end)
{
clear();
for (size_t i = start; i != end; ++i)
push_back(externalItVector[i]);
}
inline value_type & at(size_t pos) {
BOOST_ASSERT(pos < ItVector_.size());
return *ItVector_[pos];
}
inline value_type const & at(size_t pos) const {
BOOST_ASSERT(pos < ItVector_.size());
return *ItVector_[pos];
}
inline size_t size() const {
return ItVector_.size();
}
inline const_iterator begin() const {
return static_cast<base_cit>(Container_.begin());
}
inline iterator begin() {
return Container_.begin();
}
inline const_iterator end() const {
return Container_.end();
}
inline iterator end() {
return Container_.end();
}
inline Paragraph & back() {
return Container_.back();
}
inline Paragraph const & back() const {
return Container_.back();
}
inline Paragraph & front() {
return Container_.front();
}
inline Paragraph const & front() const {
return Container_.front();
}
inline bool empty() const {
return Container_.empty();
}
inline void clear() {
Container_.clear();
ItVector_.clear();
}
/// Erases the paragraphs from start to end.
/**
\todo This could be optimized...
*/
bool erase(size_t start, size_t end) {
bool result=true;
for (size_t i = start; 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()) {
// 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);
}
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 an external it_vector at position pos.
/**
The subsequent elements are shifted toward the end.
\todo This could be optimized a bit...
*/
bool insert(size_t pos, it_vector const & externalItVector) {
bool result=true;
size_t i=pos;
for (const_iterator it = externalItVector.begin();
it != externalItVector.end(); ++it) {
result = result && insert(i, *it);
++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.
\todo This could be optimized a bit...
\return the position after the last inserted element.
*/
size_t insert(size_t pos, iterator it_start, iterator it_end) {
bool result=true;
size_t i=pos;
for (iterator 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.
*/
iterator insert(iterator it, iterator it_start, iterator 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 paragraphs are shifted toward the end.
bool insert(size_t pos, value_type const & new_element) {
if (pos > ItVector_.size()) {
// 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.
*/
inline 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();
}
inline void for_each(void func(value_type&))
{
std::for_each(Container_.begin(), Container_.end(), func);
}
void for_each(size_t start, size_t end, void func(value_type&))
{
for (size_t i = start; i != end; ++i)
func(at(i));
}
inline value_type & operator[](size_t pos) {
return at(pos);
}
inline value_type const & operator[](size_t pos) const {
return at(pos);
}
inline it_vector & operator=(it_vector const & it_vector_) {
copy(it_vector_);
return *this;
}
}; // it_vector
#endif
