Dillo v3.1.1-46-g8a360e32
|
Container similar to lout::misc::SimpleVector, but some cases of insertion optimized (used for hyphenation). More...
#include <misc.hh>
Public Member Functions | |
NotSoSimpleVector (int initAlloc) | |
NotSoSimpleVector (const NotSoSimpleVector &o) | |
~NotSoSimpleVector () | |
int | size () const |
bool | empty () const |
void | increase () |
void | setSize (int newSize) |
void | insert (int index, int numInsert) |
T * | getRef (int i) const |
Return the reference of one element. | |
T | get (int i) const |
Return the one element, explicitly. | |
T * | getFirstRef () const |
Return the reference of the first element (convenience method). | |
T | getFirst () const |
Return the first element, explicitly. | |
T * | getLastRef () const |
Return the reference of the last element (convenience method). | |
T | getLast () const |
Return the last element, explicitly. | |
void | set (int i, T t) |
Store an object in the vector. | |
void | setLast (T t) |
Store an object at the end of the vector. | |
Private Member Functions | |
void | resizeMain () |
void | resizeExtra () |
void | consolidate () |
Private Attributes | |
T * | arrayMain |
T * | arrayExtra1 |
T * | arrayExtra2 |
int | numMain |
int | numExtra |
int | numAllocMain |
int | numAllocExtra |
int | startExtra |
Container similar to lout::misc::SimpleVector, but some cases of insertion optimized (used for hyphenation).
For hyphenation, words are often split, so that some space must be inserted by the method NotSoSimpleVector::insert. Typically, some elements are inserted quite at the beginning (when the word at the end of the first or at the beginning of the second line is hyphenated), then, a bit further (end of second line/beginning of third line) and so on. In the first time, nearly all words must be moved; in the second time, a bit less, etc. After all, using a simple vector would result in O(n2) number of elements moved total. With this class, however, the number can be kept at O(n).
The basic idea is to keep an extra array (actually two, of which the second one is used temporarily), which is inserted in a logical way. Since there is only one extra array at max, reading is rather simple and fast (see NotSoSimpleVector::getRef): check whether the position is before, within, or after the extra array. The first insertion is also rather simple, when the extra array has to be created. The following sketch illustrates the most complex case, when an extra array exists, and something is inserted after it (the case for which this class has been optimized):
Dotted lines are used to keep the boxes aligned.
As you see, only a relatively small fraction of elements has to be moved.
There are some other cases, which have to be documented.
|
inline |
|
inline |
Definition at line 377 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::arrayMain, lout::misc::NotSoSimpleVector< T >::numAllocExtra, lout::misc::NotSoSimpleVector< T >::numAllocMain, lout::misc::NotSoSimpleVector< T >::numExtra, lout::misc::NotSoSimpleVector< T >::numMain, lout::misc::NotSoSimpleVector< T >::resizeExtra(), lout::misc::NotSoSimpleVector< T >::resizeMain(), and lout::misc::NotSoSimpleVector< T >::startExtra.
|
inline |
|
inlineprivate |
Definition at line 354 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::arrayExtra1, lout::misc::NotSoSimpleVector< T >::arrayMain, lout::misc::NotSoSimpleVector< T >::numExtra, lout::misc::NotSoSimpleVector< T >::numMain, lout::misc::NotSoSimpleVector< T >::resizeMain(), and lout::misc::NotSoSimpleVector< T >::startExtra.
Referenced by lout::misc::NotSoSimpleVector< T >::insert().
|
inline |
Definition at line 406 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::size().
|
inline |
Return the one element, explicitly.
The element is copied, so for complex elements, you should rather used misc::SimpleVector::getRef.
Definition at line 508 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::getRef().
Referenced by print().
|
inline |
Return the first element, explicitly.
Definition at line 524 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::getFirstRef().
|
inline |
Return the reference of the first element (convenience method).
Definition at line 516 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::getRef(), and lout::misc::NotSoSimpleVector< T >::size().
Referenced by lout::misc::NotSoSimpleVector< T >::getFirst().
|
inline |
Return the last element, explicitly.
Definition at line 539 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::getLastRef().
|
inline |
Return the reference of the last element (convenience method).
Definition at line 531 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::getRef(), and lout::misc::NotSoSimpleVector< T >::size().
Referenced by lout::misc::NotSoSimpleVector< T >::getLast(), and lout::misc::NotSoSimpleVector< T >::setLast().
|
inline |
Return the reference of one element.
Definition at line 473 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::numExtra, lout::misc::NotSoSimpleVector< T >::numMain, and lout::misc::NotSoSimpleVector< T >::startExtra.
Referenced by lout::misc::NotSoSimpleVector< T >::get(), lout::misc::NotSoSimpleVector< T >::getFirstRef(), lout::misc::NotSoSimpleVector< T >::getLastRef(), and lout::misc::NotSoSimpleVector< T >::set().
|
inline |
Definition at line 408 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::setSize(), and lout::misc::NotSoSimpleVector< T >::size().
Referenced by main().
|
inline |
Definition at line 417 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::arrayExtra1, lout::misc::NotSoSimpleVector< T >::arrayExtra2, lout::misc::NotSoSimpleVector< T >::arrayMain, lout::misc::NotSoSimpleVector< T >::consolidate(), lout::misc::NotSoSimpleVector< T >::insert(), lout::misc::NotSoSimpleVector< T >::numExtra, lout::misc::NotSoSimpleVector< T >::resizeExtra(), and lout::misc::NotSoSimpleVector< T >::startExtra.
Referenced by lout::misc::NotSoSimpleVector< T >::insert(), and main().
|
inlineprivate |
Definition at line 334 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::arrayExtra1, and lout::misc::NotSoSimpleVector< T >::numExtra.
Referenced by lout::misc::NotSoSimpleVector< T >::insert(), and lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector().
|
inlineprivate |
Definition at line 317 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::arrayMain, and lout::misc::NotSoSimpleVector< T >::numMain.
Referenced by lout::misc::NotSoSimpleVector< T >::consolidate(), lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector(), and lout::misc::NotSoSimpleVector< T >::setSize().
|
inline |
Store an object in the vector.
Unlike in container::untyped::Vector and container::typed::Vector, you have to care about the size, so a call to misc::SimpleVector::increase or misc::SimpleVector::setSize may be necessary before.
Definition at line 551 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::getRef().
Referenced by main().
|
inline |
Store an object at the end of the vector.
Definition at line 558 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::getLastRef().
|
inline |
Definition at line 410 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::numExtra, and lout::misc::NotSoSimpleVector< T >::resizeMain().
Referenced by lout::misc::NotSoSimpleVector< T >::increase().
|
inline |
Definition at line 404 of file misc.hh.
References lout::misc::NotSoSimpleVector< T >::numExtra.
Referenced by lout::misc::NotSoSimpleVector< T >::empty(), lout::misc::NotSoSimpleVector< T >::getFirstRef(), lout::misc::NotSoSimpleVector< T >::getLastRef(), lout::misc::NotSoSimpleVector< T >::increase(), main(), and print().
|
private |
Definition at line 314 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::consolidate(), lout::misc::NotSoSimpleVector< T >::insert(), and lout::misc::NotSoSimpleVector< T >::resizeExtra().
|
private |
Definition at line 314 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::insert().
|
private |
Definition at line 314 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::consolidate(), lout::misc::NotSoSimpleVector< T >::insert(), lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector(), and lout::misc::NotSoSimpleVector< T >::resizeMain().
|
private |
Definition at line 315 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector().
|
private |
Definition at line 315 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector().
|
private |
Definition at line 315 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::consolidate(), lout::misc::NotSoSimpleVector< T >::getRef(), lout::misc::NotSoSimpleVector< T >::insert(), lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector(), lout::misc::NotSoSimpleVector< T >::resizeExtra(), lout::misc::NotSoSimpleVector< T >::setSize(), and lout::misc::NotSoSimpleVector< T >::size().
|
private |
Definition at line 315 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::consolidate(), lout::misc::NotSoSimpleVector< T >::getRef(), lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector(), and lout::misc::NotSoSimpleVector< T >::resizeMain().
|
private |
Definition at line 315 of file misc.hh.
Referenced by lout::misc::NotSoSimpleVector< T >::consolidate(), lout::misc::NotSoSimpleVector< T >::getRef(), lout::misc::NotSoSimpleVector< T >::insert(), and lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector().