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 ()

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

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

Constructor & Destructor Documentation

◆ NotSoSimpleVector()

template<class T >

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

inline

Definition at line 388 of file misc.hh.

◆ ~NotSoSimpleVector()

template<class T >

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

inline

Definition at line 397 of file misc.hh.

Member Function Documentation

◆ consolidate()

template<class T >

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

inlineprivate

Definition at line 374 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().

◆ empty()

template<class T >

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

inline

Definition at line 409 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 511 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 527 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 519 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 542 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 534 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()

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 476 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().

◆ increase()

template<class T >

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

inline

Definition at line 411 of file misc.hh.

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

Referenced by main().

◆ insert()

template<class T >

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

inline

Definition at line 420 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().

◆ resizeExtra()

template<class T >

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

inlineprivate

Definition at line 354 of file misc.hh.

References lout::misc::NotSoSimpleVector< T >::arrayExtra1, and lout::misc::NotSoSimpleVector< T >::numExtra.

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

◆ resizeMain()

template<class T >

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

inlineprivate

Definition at line 337 of file misc.hh.

References lout::misc::NotSoSimpleVector< T >::arrayMain, and lout::misc::NotSoSimpleVector< T >::numMain.

Referenced by lout::misc::NotSoSimpleVector< T >::consolidate(), and lout::misc::NotSoSimpleVector< T >::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 554 of file misc.hh.

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

Referenced by main().

◆ setLast()

template<class T >

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

inline

Store an object at the end of the vector.

Definition at line 561 of file misc.hh.

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

◆ setSize()

template<class T >

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

inline

Definition at line 413 of file misc.hh.

References lout::misc::NotSoSimpleVector< T >::numExtra, and lout::misc::NotSoSimpleVector< T >::resizeMain().

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

◆ size()

template<class T >

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

inline

Definition at line 407 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().

Member Data Documentation

◆ arrayExtra1

template<class T >

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

private

Definition at line 334 of file misc.hh.

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

◆ arrayExtra2

template<class T >

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

private

Definition at line 334 of file misc.hh.

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

◆ arrayMain

template<class T >

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

private

Definition at line 334 of file misc.hh.

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