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

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

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.

Definition at line 262 of file misc.hh.

Constructor & Destructor Documentation

◆ NotSoSimpleVector() [1/2]

template<class T>

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

inline

Definition at line 319 of file misc.hh.

◆ NotSoSimpleVector() [2/2]

template<class T>

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

inline

Definition at line 328 of file misc.hh.

◆ ~NotSoSimpleVector()

template<class T>

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

inline

Definition at line 345 of file misc.hh.

Member Function Documentation

◆ consolidate()

template<class T>

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

inlineprivate

Definition at line 305 of file misc.hh.

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

◆ 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 442 of file misc.hh.

◆ getFirst()

template<class T>

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

inline

Return the first element, explicitly.

Definition at line 458 of file misc.hh.

◆ getFirstRef()

template<class T>

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

inline

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

Definition at line 450 of file misc.hh.

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

◆ getLast()

template<class T>

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

inline

Return the last element, explicitly.

Definition at line 473 of file misc.hh.

◆ getLastRef()

template<class T>

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

inline

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

Definition at line 465 of file misc.hh.

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

◆ getRef()

template<class T>

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

inline

Return the reference of one element.

See also: misc::SimpleVector::get

Definition at line 422 of file misc.hh.

Referenced by 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().

◆ increase()

template<class T>

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

inline

Definition at line 357 of file misc.hh.

◆ insert()

template<class T>

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

inline

Definition at line 366 of file misc.hh.

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

◆ resizeExtra()

template<class T>

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

inlineprivate

Definition at line 285 of file misc.hh.

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

◆ resizeMain()

template<class T>

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

inlineprivate

Definition at line 268 of file misc.hh.

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

◆ set()

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.

Definition at line 485 of file misc.hh.

◆ setSize()

template<class T>

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

inline

Definition at line 359 of file misc.hh.

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

◆ size()

template<class T>

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

inline

Definition at line 355 of file misc.hh.

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

Member Data Documentation

◆ arrayExtra1

template<class T>

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

private

Definition at line 265 of file misc.hh.

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

◆ arrayExtra2

template<class T>

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

private

Definition at line 265 of file misc.hh.

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

◆ arrayMain

template<class T>

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

private

Definition at line 265 of file misc.hh.

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