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. More...

T	get (int i) const
	Return the one element, explicitly. More...

T *	getFirstRef () const
	Return the reference of the first element (convenience method). More...

T	getFirst () const
	Return the first element, explicitly. More...

T *	getLastRef () const
	Return the reference of the last element (convenience method). More...

T	getLast () const
	Return the last element, explicitly. More...

void	set (int i, T t)
	Store an object in the vector. More...

void	setLast (T t)
	Store an object at the end of the vector. More...

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(n²) 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.

Constructor & Destructor Documentation

template<class T>

lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector ( int initAlloc )

inline

template<class T>

lout::misc::NotSoSimpleVector< T >::NotSoSimpleVector ( const NotSoSimpleVector< T > & o )

inline

template<class T>

lout::misc::NotSoSimpleVector< T >::~NotSoSimpleVector ( )

inline

Member Function Documentation

template<class T>

void lout::misc::NotSoSimpleVector< T >::consolidate ( )

inlineprivate

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::insert().

template<class T>

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

inline

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.

Referenced by print().

template<class T>

T lout::misc::NotSoSimpleVector< T >::getFirst ( ) const

inline

Return the first element, explicitly.

template<class T>

T* lout::misc::NotSoSimpleVector< T >::getFirstRef ( ) const

inline

Return the reference of the first element (convenience method).

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getFirst().

template<class T>

T lout::misc::NotSoSimpleVector< T >::getLast ( ) const

inline

Return the last element, explicitly.

template<class T>

T* lout::misc::NotSoSimpleVector< T >::getLastRef ( ) const

inline

Return the reference of the last element (convenience method).

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getLast(), and lout::misc::NotSoSimpleVector< dw::Textblock::Word >::setLast().

template<class T>

T* lout::misc::NotSoSimpleVector< T >::getRef ( int i ) const

inline

Return the reference of one element.

See also: misc::SimpleVector::get

Referenced by dw::Textblock::calcPenaltyIndexForNewLine(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::get(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getFirstRef(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getLastRef(), and lout::misc::NotSoSimpleVector< dw::Textblock::Word >::set().

template<class T>

void lout::misc::NotSoSimpleVector< T >::increase ( )

inline

Referenced by main().

template<class T>

void lout::misc::NotSoSimpleVector< T >::insert	(	int	index,
		int	numInsert
	)

inline

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::insert(), and main().

template<class T>

void lout::misc::NotSoSimpleVector< T >::resizeExtra ( )

inlineprivate

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::insert(), and lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector().

template<class T>

void lout::misc::NotSoSimpleVector< T >::resizeMain ( )

inlineprivate

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::consolidate(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector(), and lout::misc::NotSoSimpleVector< dw::Textblock::Word >::setSize().

template<class T>

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

Referenced by main().

template<class T>

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

inline

Store an object at the end of the vector.

template<class T>

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

inline

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::increase().

template<class T>

int lout::misc::NotSoSimpleVector< T >::size ( ) const

inline

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::empty(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getFirstRef(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getLastRef(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::increase(), main(), and print().

Member Data Documentation

template<class T>

T * lout::misc::NotSoSimpleVector< T >::arrayExtra1

private

template<class T>

T * lout::misc::NotSoSimpleVector< T >::arrayExtra2

private

template<class T>

T* lout::misc::NotSoSimpleVector< T >::arrayMain

private

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector().

template<class T>

int lout::misc::NotSoSimpleVector< T >::numAllocExtra

private

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector().

template<class T>

int lout::misc::NotSoSimpleVector< T >::numAllocMain

private

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector().

template<class T>

int lout::misc::NotSoSimpleVector< T >::numExtra

private

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::consolidate(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getRef(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::insert(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::setSize(), and lout::misc::NotSoSimpleVector< dw::Textblock::Word >::size().

template<class T>

int lout::misc::NotSoSimpleVector< T >::numMain

private

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector().

template<class T>

int lout::misc::NotSoSimpleVector< T >::startExtra

private

Referenced by lout::misc::NotSoSimpleVector< dw::Textblock::Word >::getRef(), lout::misc::NotSoSimpleVector< dw::Textblock::Word >::insert(), and lout::misc::NotSoSimpleVector< dw::Textblock::Word >::NotSoSimpleVector().

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

lout/misc.hh

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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