Dillo v3.1.1-46-g8a360e32
Loading...
Searching...
No Matches
lout::misc::NotSoSimpleVector< T > Class Template Reference

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.
 
get (int i) const
 Return the one element, explicitly.
 
T * getFirstRef () const
 Return the reference of the first element (convenience method).
 
getFirst () const
 Return the first element, explicitly.
 
T * getLastRef () const
 Return the reference of the last element (convenience method).
 
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
 

Detailed Description

template<class T>
class lout::misc::NotSoSimpleVector< T >

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.

Definition at line 311 of file misc.hh.

Constructor & Destructor Documentation

◆ NotSoSimpleVector() [1/2]

template<class T >
lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector ( int  initAlloc)
inline

Definition at line 368 of file misc.hh.

◆ NotSoSimpleVector() [2/2]

◆ ~NotSoSimpleVector()

template<class T >
lout::misc::NotSoSimpleVector< T >::~NotSoSimpleVector ( )
inline

Definition at line 394 of file misc.hh.

Member Function Documentation

◆ consolidate()

◆ empty()

template<class T >
bool lout::misc::NotSoSimpleVector< T >::empty ( ) const
inline

Definition at line 406 of file misc.hh.

References lout::misc::NotSoSimpleVector< T >::size().

◆ get()

template<class T >
T lout::misc::NotSoSimpleVector< T >::get ( int  i) const
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().

◆ getFirst()

template<class T >
T lout::misc::NotSoSimpleVector< T >::getFirst ( ) const
inline

Return the first element, explicitly.

Definition at line 524 of file misc.hh.

References lout::misc::NotSoSimpleVector< T >::getFirstRef().

◆ getFirstRef()

template<class T >
T * lout::misc::NotSoSimpleVector< T >::getFirstRef ( ) const
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().

◆ getLast()

template<class T >
T lout::misc::NotSoSimpleVector< T >::getLast ( ) const
inline

Return the last element, explicitly.

Definition at line 539 of file misc.hh.

References lout::misc::NotSoSimpleVector< T >::getLastRef().

◆ getLastRef()

template<class T >
T * lout::misc::NotSoSimpleVector< T >::getLastRef ( ) const
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().

◆ getRef()

◆ increase()

template<class T >
void lout::misc::NotSoSimpleVector< T >::increase ( )
inline

◆ insert()

◆ resizeExtra()

◆ resizeMain()

◆ set()

template<class T >
void lout::misc::NotSoSimpleVector< T >::set ( int  i,
t 
)
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().

◆ setLast()

template<class T >
void lout::misc::NotSoSimpleVector< T >::setLast ( t)
inline

Store an object at the end of the vector.

Definition at line 558 of file misc.hh.

References lout::misc::NotSoSimpleVector< T >::getLastRef().

◆ setSize()

template<class T >
void lout::misc::NotSoSimpleVector< T >::setSize ( int  newSize)
inline

◆ size()

Member Data Documentation

◆ arrayExtra1

◆ arrayExtra2

template<class T >
T * lout::misc::NotSoSimpleVector< T >::arrayExtra2
private

Definition at line 314 of file misc.hh.

Referenced by lout::misc::NotSoSimpleVector< T >::insert().

◆ arrayMain

◆ numAllocExtra

template<class T >
int lout::misc::NotSoSimpleVector< T >::numAllocExtra
private

Definition at line 315 of file misc.hh.

Referenced by lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector().

◆ numAllocMain

template<class T >
int lout::misc::NotSoSimpleVector< T >::numAllocMain
private

Definition at line 315 of file misc.hh.

Referenced by lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector().

◆ numExtra

◆ numMain

◆ startExtra


The documentation for this class was generated from the following file: