[EMAIL PROTECTED] (Lars Gullik Bjønnes) writes:
| The only think left that I'd like to change is the iterators,
| currently ÂRandomccessList::iterator is an bi-directional iterator,
| but not a random iterator, as such several operation are pretty
| costly.
This patch has that change. I am not overly confident in it, but it
seems to work as it should. It would be great if those of you seeing
speed problems due to slow ParagraphList could try this patch. With
USE_CONTAINER_ITERATOR set to both 0 and 1. (0 will use a
bidirectional iterator std::list::iterator, 1 will use a random access
iterator std::vector::iterator)
With the random access iterator, especially the erase functions and
one of the insert functions benefit the most, by avoiding calls to
recreateVector.
------------------------------------------------------------------------
Index: src/insets/insettext.h
===================================================================
--- src/insets/insettext.h (revision 13369)
+++ src/insets/insettext.h (working copy)
@@ -16,6 +16,7 @@
#include "RowList_fwd.h"
#include "lyxfont.h"
#include "lyxtext.h"
+#include "ParagraphList_fwd.h"
#include "support/types.h"
@@ -27,7 +28,6 @@
class CursorSlice;
class Dimension;
class LColor_color;
-class ParagraphList;
/**
Index: src/insets/insetbibitem.C
===================================================================
--- src/insets/insetbibitem.C (revision 13369)
+++ src/insets/insetbibitem.C (working copy)
@@ -19,7 +19,7 @@
#include "lyxfont.h"
#include "lyxlex.h"
#include "paragraph.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include "frontends/font_metrics.h"
Index: src/output_plaintext.C
===================================================================
--- src/output_plaintext.C (revision 13369)
+++ src/output_plaintext.C (working copy)
@@ -19,7 +19,7 @@
#include "output.h"
#include "outputparams.h"
#include "paragraph.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include "ParagraphParameters.h"
#include "support/lstrings.h"
Index: src/output_latex.h
===================================================================
--- src/output_latex.h (revision 13369)
+++ src/output_latex.h (working copy)
@@ -12,11 +12,12 @@
#ifndef OUTPUT_LATEX_H
#define OUTPUT_LATEX_H
+#include "ParagraphList_fwd.h"
+
#include <string>
class Buffer;
class OutputParams;
-class ParagraphList;
class TexRow;
/// Just a wrapper for the method below, first creating the ofstream.
Index: src/bufferlist.C
===================================================================
--- src/bufferlist.C (revision 13369)
+++ src/bufferlist.C (working copy)
@@ -22,7 +22,7 @@
#include "lyx_main.h"
#include "output_latex.h"
#include "paragraph.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include "frontends/Alert.h"
Index: src/undo.C
===================================================================
--- src/undo.C (revision 13369)
+++ src/undo.C (working copy)
@@ -22,6 +22,7 @@
#include "BufferView.h"
#include "lyxtext.h"
#include "paragraph.h"
+#include "ParagraphList.h"
#include "mathed/math_support.h"
#include "insets/inset.h"
Index: src/ParagraphList_fwd.h
===================================================================
--- src/ParagraphList_fwd.h (revision 13369)
+++ src/ParagraphList_fwd.h (working copy)
@@ -12,22 +12,11 @@
#ifndef PARAGRAPH_LIST_FWD_H
#define PARAGRAPH_LIST_FWD_H
-#include "paragraph.h"
+template <class T>
+class RandomAccessList;
-#include <vector>
+class Paragraph;
-class ParagraphList : public std::vector<Paragraph>
-{
-public:
- ///
- typedef std::vector<Paragraph> BaseType;
- ///
- ParagraphList();
- ///
- template <class Iter>
- ParagraphList(Iter beg, Iter end)
- : BaseType(beg, end)
- {}
-};
+typedef RandomAccessList<Paragraph> ParagraphList;
#endif
Index: src/lyxtext.h
===================================================================
--- src/lyxtext.h (revision 13369)
+++ src/lyxtext.h (working copy)
@@ -21,7 +21,7 @@
#include "lyxfont.h"
#include "layout.h"
#include "lyxlayout_ptr_fwd.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include <iosfwd>
Index: src/undo.h
===================================================================
--- src/undo.h (revision 13369)
+++ src/undo.h (working copy)
@@ -17,7 +17,7 @@
#define UNDO_H
#include "dociterator.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include "bufferparams.h"
#include "support/types.h"
Index: src/buffer.h
===================================================================
--- src/buffer.h (revision 13369)
+++ src/buffer.h (working copy)
@@ -15,6 +15,7 @@
#include "InsetList.h"
#include "dociterator.h"
+#include "ParagraphList_fwd.h"
#include "support/limited_stack.h"
#include "support/types.h"
@@ -42,7 +43,6 @@
class Language;
class MacroData;
class OutputParams;
-class ParagraphList;
class ParConstIterator;
class ParIterator;
class TeXErrors;
Index: src/CutAndPaste.h
===================================================================
--- src/CutAndPaste.h (revision 13369)
+++ src/CutAndPaste.h (working copy)
@@ -14,6 +14,8 @@
#ifndef CUTANDPASTE_H
#define CUTANDPASTE_H
+#include "ParagraphList_fwd.h"
+
#include "support/types.h"
#include <string>
@@ -23,7 +25,6 @@
class ErrorList;
class LyXTextClass;
class LCursor;
-class ParagraphList;
///
namespace lyx {
Index: src/support/RandomAccessList.h
===================================================================
--- src/support/RandomAccessList.h (revision 0)
+++ src/support/RandomAccessList.h (revision 0)
@@ -0,0 +1,453 @@
+// -*- 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>
+
+#define USE_CONTAINER_ITERATOR 0
+
+/// 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 (it_vector_) up
+to date.
+*/
+template <class T>
+class RandomAccessList {
+public:
+ // types
+ typedef std::list<T> Container;
+ typedef typename Container::reference reference;
+ typedef typename Container::const_reference const_reference;
+ // iterator (below)
+ // const_iterator (below)
+ typedef typename Container::size_type size_type;
+ typedef typename Container::difference_type difference_type;
+ typedef typename Container::value_type value_type;
+ typedef typename Container::allocator_type allocator_type;
+ typedef typename Container::pointer pointer;
+ typedef typename Container::const_pointer const_pointer;
+ // reverse_iterator
+ // const_reverse_iterator
+
+ typedef std::vector<typename Container::iterator> IterCont;
+
+#if USE_CONTAINER_ITERATOR
+ ///
+ class iterator: public Container::iterator {
+ public:
+ iterator()
+ {}
+
+ iterator(typename Container::iterator 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);
+ }
+ };
+
+ ///
+ class const_iterator: public Container::const_iterator {
+ public:
+ const_iterator()
+ {}
+
+ const_iterator(typename Container::const_iterator const & it)
+ {
+ Container::const_iterator::operator=(it);
+ }
+ const_iterator(iterator const & it)
+ {
+ Container::const_iterator::operator=(static_cast<typename
Container::iterator>(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);
+ }
+ };
+#else
+ ///
+ class iterator : public IterCont::iterator {
+ public:
+ iterator()
+ {}
+
+ iterator(iterator const & x)
+ : IterCont::iterator(x)
+ {}
+
+ reference operator*() const
+ {
+ return IterCont::iterator::operator->()->operator*();
+ }
+
+ pointer operator->() const
+ {
+ return IterCont::iterator::operator->()->operator->();
+ }
+
+
+ iterator operator+(difference_type pos) const
+ {
+ return boost::next(*this, pos);
+ }
+
+ iterator(typename IterCont::iterator const & i)
+ : IterCont::iterator(i)
+ {}
+
+ private:
+ friend class RandomAccessList;
+ typename IterCont::value_type shallowGet()
+ {
+ return IterCont::iterator::operator*();
+ }
+ };
+
+ ///
+ class const_iterator : public IterCont::const_iterator {
+ public:
+ const_iterator()
+ {}
+
+ const_iterator(const_iterator const & x)
+ : IterCont::const_iterator(x)
+ {}
+
+ const_reference operator*() const
+ {
+ return
IterCont::const_iterator::operator->()->operator*();
+ }
+
+ const_pointer operator->() const
+ {
+ return
IterCont::const_iterator::operator->()->operator->();
+ }
+
+ const_iterator operator+(difference_type pos) const
+ {
+ return boost::next(*this, pos);
+ }
+
+ const_iterator(typename IterCont::const_iterator const & ci)
+ : IterCont::const_iterator(ci)
+ {}
+
+ private:
+ friend class RandomAccessList;
+ typename IterCont::value_type shallowGet()
+ {
+ return IterCont::const_iterator::operator*();
+ }
+ };
+#endif
+
+ // construct/copy/destroy
+
+ RandomAccessList()
+ {}
+
+ // RandomAccessList(size_type n T const & value = T())
+
+ template<class InputIterator>
+ RandomAccessList(InputIterator first, InputIterator last)
+ {
+ assign(first, last);
+ }
+
+
+
+ RandomAccessList(RandomAccessList const & x)
+ {
+#if USE_CONTAINER_ITERATOR
+ assign(x.begin(), x.end());
+#else
+ assign(x.container_.begin(), x.container_.end());
+#endif
+ }
+
+ // ~RandomAccessList()
+
+ ///
+ RandomAccessList & operator=(RandomAccessList const & x)
+ {
+#if USE_CONTAINER_ITERATOR
+ assign(x.begin(), x.end());
+#else
+ assign(x.container_.begin(), x.container_.end());
+#endif
+ return *this;
+ }
+
+ template<class InputIterator>
+ void assign(InputIterator first, InputIterator last)
+ {
+ container_.assign(first, last);
+ recreateVector();
+ }
+
+
+ // void assign(size_type n, T const & u);
+
+ // iterators
+
+ iterator begin()
+ {
+#if USE_CONTAINER_ITERATOR
+ return container_.begin();
+#else
+ return iterCont_.begin();
+#endif
+ }
+
+ const_iterator begin() const
+ {
+#if USE_CONTAINER_ITERATOR
+ return container_.begin();
+#else
+ return const_iterator(iterCont_.begin());
+#endif
+ }
+
+ iterator end()
+ {
+#if USE_CONTAINER_ITERATOR
+ return container_.end();
+#else
+ return iterCont_.end();
+#endif
+ }
+
+ const_iterator end() const
+ {
+#if USE_CONTAINER_ITERATOR
+ return container_.end();
+#else
+ return const_iterator(iterCont_.end());
+#endif
+ }
+
+ // reverse_iterator rbegin();
+ // const_reverse_iterator rbegin() const;
+ // reverse_iterator rend();
+ // const_reverse_iterator rend() const;
+
+ // capacity
+ size_type size() const
+ {
+ return iterCont_.size();
+ }
+
+ size_type max_size() const
+ {
+ return iterCont_.max_size();
+ }
+
+ // void resize(size_type sz, T c = T());
+
+ size_type capacity() const
+ {
+ return iterCont_.capacity();
+ }
+
+ bool empty() const
+ {
+#if USE_CONTAINER_ITERATOR
+ return container_.empty();
+#else
+ return iterCont_.empty();
+#endif
+ }
+
+ // void reserve(size_type n);
+
+ // element access
+
+ reference operator[](size_type pos)
+ {
+ return *iterCont_[pos];
+ }
+
+ ///
+ const_reference operator[](size_type pos) const
+ {
+ return *iterCont_[pos];
+ }
+
+ reference at(size_type pos)
+ {
+ return *iterCont_.at(pos);
+ }
+
+ const_reference at(size_type pos) const
+ {
+ return *iterCont_.at(pos);
+ }
+
+ reference front()
+ {
+ return container_.front();
+ }
+
+ const_reference front() const
+ {
+ return container_.front();
+ }
+
+ reference back()
+ {
+ return container_.back();
+ }
+
+ const_reference back() const
+ {
+ return container_.back();
+ }
+
+ // modifiers
+
+ void push_back(T const & x)
+ {
+ typename Container::iterator it =
+ container_.insert(container_.end(), x);
+ iterCont_.push_back(it);
+ }
+
+ void pop_back()
+ {
+ container_.pop_back();
+ iterCont_.pop_back();
+ }
+
+ iterator insert(iterator position, T const & x)
+ {
+#if USE_CONTAINER_ITERATOR
+ typename Container::iterator it =
+ container_.insert(position, x);
+ recreateVector();
+ return it;
+#else
+ typename Container::iterator it =
+ container_.insert(position.shallowGet(), x);
+ return iterCont_.insert(position, it);
+#endif
+ }
+
+ // void insert(iterator position, size_type n, T const & x);
+
+ template<class InputIterator>
+ void insert(iterator position,
+ InputIterator first, InputIterator last)
+ {
+#if USE_CONTAINER_ITERATOR
+ container_.insert(position, first, last);
+ recreateVector();
+#else
+ container_.insert(position.shallowGet(), first, last);
+ recreateVector();
+#endif
+ }
+
+ iterator erase(iterator position)
+ {
+#if USE_CONTAINER_ITERATOR
+ typename Container::iterator it =
+ container_.erase(position);
+ recreateVector();
+ return it;
+#else
+ container_.erase(position.shallowGet());
+ return iterCont_.erase(position);
+#endif
+ }
+
+ iterator erase(iterator first, iterator last)
+ {
+#if USE_CONTAINER_ITERATOR
+ typename Container::iterator it =
+ container_.erase(first, last);
+ recreateVector();
+ return it;
+#else
+ container_.erase(first.shallowGet(), last.shallowGet());
+ return iterCont_.erase(first, last);
+#endif
+ }
+
+ void swap(RandomAccessList & x)
+ {
+ std::swap(container_, x.container_);
+ std::swap(iterCont_, x.iterCont_);
+ }
+
+ void clear()
+ {
+ container_.clear();
+ iterCont_.clear();
+ }
+
+private:
+ void recreateVector()
+ {
+ iterCont_.clear();
+ typename Container::iterator beg = container_.begin();
+ typename Container::iterator end = container_.end();
+ for (; beg != end; ++beg)
+ iterCont_.push_back(beg);
+ }
+
+ /// Our container.
+ Container container_;
+ /// Our container of iterators.
+ IterCont iterCont_;
+};
+
+#endif
Index: src/pariterator.h
===================================================================
--- src/pariterator.h (revision 13369)
+++ src/pariterator.h (working copy)
@@ -13,6 +13,7 @@
#define PARITERATOR_H
#include "dociterator.h"
+#include "ParagraphList_fwd.h"
#include "support/types.h"
@@ -24,7 +25,6 @@
class InsetBase;
class LyXText;
-class ParagraphList;
class ParIterator : public std::iterator<std::forward_iterator_tag, Paragraph>,
Index: src/output_linuxdoc.C
===================================================================
--- src/output_linuxdoc.C (revision 13369)
+++ src/output_linuxdoc.C (working copy)
@@ -17,7 +17,7 @@
#include "bufferparams.h"
#include "paragraph.h"
#include "paragraph_funcs.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include "ParagraphParameters.h"
#include "sgml.h"
Index: src/ParagraphList.h
===================================================================
--- src/ParagraphList.h (revision 0)
+++ src/ParagraphList.h (revision 0)
@@ -0,0 +1,22 @@
+// -*- C++ -*-
+/**
+ * \file ParagraphList_fwd.h
+ * This file is part of LyX, the document processor.
+ * Licence details can be found in the file COPYING.
+ *
+ * \author Angus Leeming
+ *
+ * Full author contact details are available in file CREDITS.
+ */
+
+#ifndef PARAGRAPH_LIST_H
+#define PARAGRAPH_LIST_H
+
+#include "paragraph.h"
+
+#include "support/RandomAccessList.h"
+
+/// Container for all kind of Paragraphs used in Lyx.
+typedef RandomAccessList<Paragraph> ParagraphList;
+
+#endif
Index: src/paragraph_funcs.h
===================================================================
--- src/paragraph_funcs.h (revision 13369)
+++ src/paragraph_funcs.h (working copy)
@@ -12,6 +12,8 @@
#ifndef PARAGRAPH_FUNCS_H
#define PARAGRAPH_FUNCS_H
+#include "ParagraphList_fwd.h"
+
#include "support/types.h"
class Buffer;
@@ -19,7 +21,6 @@
class InsetBase;
class LyXFont;
class Paragraph;
-class ParagraphList;
/**
* This breaks a paragraph at the specified position.
Index: src/output_docbook.C
===================================================================
--- src/output_docbook.C (revision 13369)
+++ src/output_docbook.C (working copy)
@@ -20,7 +20,7 @@
#include "debug.h"
#include "paragraph.h"
#include "paragraph_funcs.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include "ParagraphParameters.h"
#include "sgml.h"
Index: src/output_linuxdoc.h
===================================================================
--- src/output_linuxdoc.h (revision 13369)
+++ src/output_linuxdoc.h (working copy)
@@ -13,10 +13,11 @@
#ifndef OUTPUT_LINUXDOC_H
#define OUTPUT_LINUXDOC_H
+#include "ParagraphList_fwd.h"
+
#include <iosfwd>
class Buffer;
-class ParagraphList;
class OutputParams;
///
Index: src/output_docbook.h
===================================================================
--- src/output_docbook.h (revision 13369)
+++ src/output_docbook.h (working copy)
@@ -13,11 +13,12 @@
#ifndef OUTPUT_DOCBOOK_H
#define OUTPUT_DOCBOOK_H
+#include "ParagraphList_fwd.h"
+
#include <iosfwd>
class Buffer;
class OutputParams;
-class ParagraphList;
///
void docbookParagraphs(ParagraphList const & subset,
Index: src/paragraph.C
===================================================================
--- src/paragraph.C (revision 13369)
+++ src/paragraph.C (working copy)
@@ -66,10 +66,6 @@
using std::ostringstream;
-ParagraphList::ParagraphList()
-{}
-
-
Paragraph::Paragraph()
: begin_of_body_(0), pimpl_(new Paragraph::Pimpl(this))
{
Index: src/buffer_funcs.C
===================================================================
--- src/buffer_funcs.C (revision 13369)
+++ src/buffer_funcs.C (working copy)
@@ -27,7 +27,7 @@
#include "lyxtextclass.h"
#include "paragraph.h"
#include "paragraph_funcs.h"
-#include "ParagraphList_fwd.h"
+#include "ParagraphList.h"
#include "ParagraphParameters.h"
#include "pariterator.h"
#include "lyxvc.h"
------------------------------------------------------------------------
