TVec< TVal, TSizeTy > Class Template Reference

Vector is a sequence TVal objects representing an array that can change in size. More...

#include <ds.h>

Public Types
typedef TVal *	TIter
	Random access iterator to TVal. More...

Public Member Functions
	TVec ()
	TVec (const TVec< TVal, TSizeTy > &Vec)
	TVec (const TSizeTy &_Vals)
	Constructs a vector (an array) of length _Vals. More...
	TVec (const TSizeTy &_MxVals, const TSizeTy &_Vals)
	Constructs a vector (an array) of length _Vals, while reserving enough memory to store _MxVals elements. More...
	TVec (TVal *_ValT, const TSizeTy &_Vals)
	Constructs a vector of _Vals elements of memory array _ValT. More...
	~TVec ()
	TVec (TSIn &SIn)
void	LoadShM (TShMIn &ShMIn)
	Constructs the vector from a shared memory input. More...
template<typename TLoadShMElem >
void	LoadShM (TShMIn &ShMIn, TLoadShMElem LoadFromShMFn)
	Constructs vector from shared memory input passing in functor to initialize elements. More...
void	Load (TSIn &SIn)
void	Save (TSOut &SOut) const
void	LoadXml (const PXmlTok &XmlTok, const TStr &Nm="")
void	SaveXml (TSOut &SOut, const TStr &Nm) const
TVec< TVal, TSizeTy > &	operator= (const TVec< TVal, TSizeTy > &Vec)
	Assigns new contents to the vector, replacing its current content. More...
TVec< TVal, TSizeTy > &	operator+ (const TVal &Val)
	Appends value Val to the vector. More...
bool	operator== (const TVec< TVal, TSizeTy > &Vec) const
	Checks that the two vectors have the same contents. More...
bool	operator< (const TVec< TVal, TSizeTy > &Vec) const
	Lexicographically compares two vectors. More...
const TVal &	operator[] (const TSizeTy &ValN) const
	Returns a reference to the element at position ValN in the vector. More...
TVal &	operator[] (const TSizeTy &ValN)
	Returns a reference to the element at position ValN in the vector. More...
TSizeTy	GetMemUsed () const
	Returns the memory footprint (the number of bytes) of the vector. More...
TSizeTy	GetMemSize () const
	Returns the memory size (the number of bytes) of a binary representation. More...
int	GetPrimHashCd () const
	Returns primary hash code of the vector. Used by THash. More...
int	GetSecHashCd () const
	Returns secondary hash code of the vector. Used by THash. More...
void	Gen (const TSizeTy &_Vals)
	Constructs a vector (an array) of _Vals elements. More...
void	Gen (const TSizeTy &_MxVals, const TSizeTy &_Vals)
	Constructs a vector (an array) of _Vals elements, while reserving enough memory for _MxVals elements. More...
void	GenExt (TVal *_ValT, const TSizeTy &_Vals)
	Constructs a vector of _Vals elements of memory array _ValT. More...
bool	IsExt () const
	Returns true if the vector was created using the GenExt(). More...
void	Reserve (const TSizeTy &_MxVals)
	Reserves enough memory for the vector to store _MxVals elements. More...
void	Reserve (const TSizeTy &_MxVals, const TSizeTy &_Vals)
	Reserves enough memory for the vector to store _MxVals elements and sets its length to _Vals. More...
void	Clr (const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
	Clears the contents of the vector. More...
void	Trunc (const TSizeTy &_Vals=-1)
	Truncates the vector's length and capacity to _Vals elements. More...
void	Reduce (const TSizeTy &_Vals=-1)
	Reduces the vector's length to _Vals elements, which must be less than the current length. More...
void	Pack ()
	Reduces vector capacity (frees memory) to match its size. More...
void	MoveFrom (TVec< TVal, TSizeTy > &Vec)
	Takes over the data and the capacity from Vec. More...
void	CopyUniqueFrom (TVec< TVal, TSizeTy > &Vec, TInt Offset, TInt Sz)
	Copy Sz values from Vec starting at Offset. More...
void	Swap (TVec< TVal, TSizeTy > &Vec)
	Swaps the contents of the vector with Vec. More...
bool	Empty () const
	Tests whether the vector is empty. More...
TSizeTy	Len () const
	Returns the number of elements in the vector. More...
TSizeTy	Reserved () const
	Returns the size of allocated storage capacity. More...
const TVal &	Last () const
	Returns a reference to the last element of the vector. More...
TVal &	Last ()
	Returns a reference to the last element of the vector. More...
TSizeTy	LastValN () const
	Returns the position of the last element. More...
const TVal &	LastLast () const
	Returns a reference to the one before last element of the vector. More...
TVal &	LastLast ()
	Returns a reference to the one before last element of the vector. More...
const TVal &	GetRndVal (TRnd &Rnd=TInt::Rnd) const
	Returns a reference to a random element in the vector. More...
TVal &	GetRndVal (TRnd &Rnd=TInt::Rnd)
	Returns a reference to a random element in the vector. More...
TIter	BegI () const
	Returns an iterator pointing to the first element in the vector. More...
TIter	EndI () const
	Returns an iterator referring to the past-the-end element in the vector. More...
TIter	GetI (const TSizeTy &ValN) const
	Returns an iterator an element at position ValN. More...
TSizeTy	Add ()
	Adds a new element at the end of the vector, after its current last element. More...
TSizeTy	Add (const TVal &Val)
	Adds a new element at the end of the vector, after its current last element. More...
TSizeTy	Add (TVal &Val)
TSizeTy	Add (const TVal &Val, const TSizeTy &ResizeLen)
	Adds element Val at the end of the vector. #TVec::Add2. More...
TSizeTy	AddMP (const TVal &Val)
	Adds element Val at the end of the vector in a thread safe manner, returns the element index in the vector. TVec::AddMP. More...
TSizeTy	MoveLastMP (const TVal &Val, int Inc)
	Reserves space after the current last element in a thread safe manner, returning the old vector size. More...
TSizeTy	AddV (const TVec< TVal, TSizeTy > &ValV)
	Adds the elements of the vector ValV to the to end of the vector. More...
TSizeTy	AddSorted (const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
	Adds element Val to a sorted vector. More...
TSizeTy	AddBackSorted (const TVal &Val, const bool &Asc)
	Adds element Val to a sorted vector. More...
TSizeTy	AddMerged (const TVal &Val)
	Adds element Val to a sorted vector only if the element Val is not already in the vector. More...
TSizeTy	AddVMerged (const TVec< TVal, TSizeTy > &ValV)
	Adds elements of ValV to a sorted vector only if a particular element is not already in the vector. More...
TSizeTy	AddUnique (const TVal &Val)
	Adds element Val to a vector only if the element Val is not already in the vector. More...
const TVal &	GetVal (const TSizeTy &ValN) const
	Returns a reference to the element at position ValN in the vector. More...
TVal &	GetVal (const TSizeTy &ValN)
	Returns a reference to the element at position ValN in the vector. More...
void	SetVal (const TSizeTy &ValN, const TVal &Val)
	Sets the value of element at position ValN to Val. More...
void	GetSubValV (const TSizeTy &BValN, const TSizeTy &EValN, TVec< TVal, TSizeTy > &ValV) const
	Fills ValV with elements at positions BValN...EValN. More...
void	Ins (const TSizeTy &ValN, const TVal &Val)
	Inserts new element Val before the element at position ValN. More...
void	Del (const TSizeTy &ValN)
	Removes the element at position ValN. More...
void	Del (const TSizeTy &MnValN, const TSizeTy &MxValN)
	Removes the elements at positions MnValN...MxValN. More...
void	DelLast ()
	Removes the last element of the vector. More...
bool	DelIfIn (const TVal &Val)
	Removes the first occurrence of element Val. More...
void	DelAll (const TVal &Val)
	Removes all occurrences of element Val. More...
void	PutAll (const TVal &Val)
	Sets all elements of the vector to value Val. More...
void	Swap (const TSizeTy &ValN1, const TSizeTy &ValN2)
	Swaps elements at positions ValN1 and ValN2. More...
bool	NextPerm ()
	Generates next permutation of the elements in the vector. More...
bool	PrevPerm ()
	Generates previous permutation of the elements in the vector. More...
TSizeTy	GetPivotValN (const TSizeTy &LValN, const TSizeTy &RValN) const
	Picks three random elements at positions LValN...RValN and returns the middle one. More...
void	BSort (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
	Bubble sorts the values between positions MnLValN...MxLValN. More...
void	ISort (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
	Insertion sorts the values between positions MnLValN...MxLValN. More...
TSizeTy	Partition (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
	Partitions the values between positions MnLValN...MxLValN. More...
void	QSort (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
	Quick sorts the values between positions MnLValN...MxLValN. More...
void	Sort (const bool &Asc=true)
	Sorts the elements of the vector. More...
bool	IsSorted (const bool &Asc=true) const
	Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order. More...
void	Shuffle (TRnd &Rnd)
	Randomly shuffles the elements of the vector. More...
void	Reverse ()
	Reverses the order of the elements in the vector. More...
void	Reverse (TSizeTy LValN, TSizeTy RValN)
	Reverses the order of elements between LValN...RValN. More...
void	Merge ()
	Sorts the vector and only keeps a single element of each value. More...
template<class TCmp >
void	SortCmp (const TCmp &Cmp)
	Sorts the elements of the vector using the comparator Cmp. More...
template<class TCmp >
bool	IsSortedCmp (const TCmp &Cmp) const
	Checks whether the vector is sorted according to the comparator Cmp. More...
void	Intrs (const TVec< TVal, TSizeTy > &ValV)
	Sets this vector to its intersection with ValV. Assumes the vectors are sorted! More...
void	Union (const TVec< TVal, TSizeTy > &ValV)
	Sets this vector to its union with ValV. Assumes the vectors are sorted! More...
void	Diff (const TVec< TVal, TSizeTy > &ValV)
	Subtracts ValV from this vector. Assumes the vectors are sorted! More...
void	Intrs (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
	Sets DstValV to the intersection of this vector and ValV. Assumes the vectors are sorted! More...
void	Union (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
	Sets DstValV to the union of this vector and ValV. Assumes the vectors are sorted! More...
void	Diff (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
	Sets DstValV to the difference between this vector and ValV. Assumes the vectors are sorted! More...
TSizeTy	IntrsLen (const TVec< TVal, TSizeTy > &ValV) const
	Returns the size of the intersection of vectors this and ValV. Assumes the vectors are sorted! More...
TSizeTy	UnionLen (const TVec< TVal, TSizeTy > &ValV) const
	Returns the size of the union of vectors this and ValV. Assumes the vectors are sorted! More...
TSizeTy	Count (const TVal &Val) const
	Counts the number of occurrences of Val in the vector. More...
TSizeTy	SearchBin (const TVal &Val) const
	Returns the position of an element with value Val. More...
TSizeTy	SearchBin (const TVal &Val, TSizeTy &InsValN) const
	Returns the position of an element with value Val. More...
TSizeTy	SearchBinLeft (const TVal &Val, TSizeTy &InsValN) const
	Returns the position of an element with value Val. More...
TSizeTy	SearchForw (const TVal &Val, const TSizeTy &BValN=0) const
	Returns the position of an element with value Val. More...
TSizeTy	SearchBack (const TVal &Val) const
	Returns the position of an element with value Val. More...
TSizeTy	SearchVForw (const TVec< TVal, TSizeTy > &ValV, const TSizeTy &BValN=0) const
	Returns the starting position of vector ValV. More...
bool	IsIn (const TVal &Val) const
	Checks whether element Val is a member of the vector. More...
bool	IsIn (const TVal &Val, TSizeTy &ValN) const
	Checks whether element Val is a member of the vector. More...
bool	IsInBin (const TVal &Val) const
	Checks whether element Val is a member of the vector. More...
const TVal &	GetDat (const TVal &Val) const
	Returns reference to the first occurrence of element Val. More...
TVal &	GetAddDat (const TVal &Val)
	Returns reference to the first occurrence of element Val. More...
TSizeTy	GetMxValN () const
	Returns the position of the largest element in the vector. More...

Static Public Member Functions
static void	SwapI (TIter LVal, TIter RVal)
	Swaps the elements that iterators LVal and RVal point to. More...
template<class TCmp >
static TIter	GetPivotValNCmp (const TIter &BI, const TIter &EI, const TCmp &Cmp)
	Picks three random elements at positions BI...EI and returns the middle one under the comparator Cmp. More...
template<class TCmp >
static TIter	PartitionCmp (TIter BI, TIter EI, const TVal Pivot, const TCmp &Cmp)
	Partitions the values between positions BI...EI under the comparator Cmp. More...
template<class TCmp >
static void	BSortCmp (TIter BI, TIter EI, const TCmp &Cmp)
	Bubble sorts the values between positions BI...EI under the comparator Cmp. More...
template<class TCmp >
static void	ISortCmp (TIter BI, TIter EI, const TCmp &Cmp)
	Insertion sorts the values between positions BI...EI under the comparator Cmp. More...
template<class TCmp >
static void	QSortCmp (TIter BI, TIter EI, const TCmp &Cmp)
	Quick sorts the values between positions BI...EI under the comparator Cmp. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1)
	Returns a vector on element Val1. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2)
	Returns a vector on elements Val1, Val2. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3)
	Returns a vector on elements Val1...Val3. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4)
	Returns a vector on elements Val1...Val4. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4, const TVal &Val5)
	Returns a vector on elements Val1...Val5. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4, const TVal &Val5, const TVal &Val6)
	Returns a vector on elements Val1...Val6. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4, const TVal &Val5, const TVal &Val6, const TVal &Val7)
	Returns a vector on elements Val1...Val7. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4, const TVal &Val5, const TVal &Val6, const TVal &Val7, const TVal &Val8)
	Returns a vector on elements Val1...Val8. More...
static TVec< TVal, TSizeTy >	GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4, const TVal &Val5, const TVal &Val6, const TVal &Val7, const TVal &Val8, const TVal &Val9)
	Returns a vector on elements Val1...Val9. More...

Protected Member Functions
void	Resize (const TSizeTy &_MxVals=-1)
	Resizes the vector so that it can store at least _MxVals. More...
TStr	GetXOutOfBoundsErrMsg (const TSizeTy &ValN) const
	Constructs the out of bounds error message. More...

Protected Attributes
TSizeTy	MxVals
	Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by the vector, and it won't free it at destruction. More...
TSizeTy	Vals
	Vector length. Length is the number of elements stored in the vector. More...
TVal *	ValT
	Pointer to the memory where the elements of the vector are stored. More...
bool	IsShM

Detailed Description

template<class TVal, class TSizeTy = int>
class TVec< TVal, TSizeTy >

Vector is a sequence TVal objects representing an array that can change in size.

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time. Vectors may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). The reallocations only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity. Use TSizeTy=int for vectors of maximum size of 2 billion (2^31) and TSizeTy=int64 for vectors that can store up to 2^61 elements.

Definition at line 430 of file ds.h.

Member Typedef Documentation

template<class TVal, class TSizeTy = int>

typedef TVal* TVec< TVal, TSizeTy >::TIter

Random access iterator to TVal.

Definition at line 432 of file ds.h.

Constructor & Destructor Documentation

template<class TVal, class TSizeTy = int>

TVec< TVal, TSizeTy >::TVec ( )

inline

Definition at line 443 of file ds.h.

: MxVals(0), Vals(0), ValT(NULL), IsShM(false) {}

template<class TVal, class TSizeTy>

TVec< TVal, TSizeTy >::TVec

(

const TVec< TVal, TSizeTy > &

Vec

)

Definition at line 922 of file ds.h.

                                                       {
  MxVals=Vec.MxVals;
  Vals=Vec.Vals;
  if (MxVals==0) {ValT=NULL;} else {ValT=new TVal[MxVals];}
  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
  IsShM = false;
}

template<class TVal, class TSizeTy = int>

TVec< TVal, TSizeTy >::TVec ( const TSizeTy &  _Vals )

inlineexplicit

Constructs a vector (an array) of length _Vals.

Definition at line 446 of file ds.h.

                                     {
    IsShM = false;
    IAssert(0<=_Vals); MxVals=Vals=_Vals;
    if (_Vals==0){ValT=NULL;} else {ValT=new TVal[_Vals];}}

template<class TVal, class TSizeTy = int>

TVec< TVal, TSizeTy >::TVec ( const TSizeTy &  _MxVals, const TSizeTy &  _Vals  )

inline

Constructs a vector (an array) of length _Vals, while reserving enough memory to store _MxVals elements.

Definition at line 451 of file ds.h.

                                                    {
    IsShM = false;
    IAssert((0<=_Vals)&&(_Vals<=_MxVals)); MxVals=_MxVals; Vals=_Vals;
    if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}

template<class TVal, class TSizeTy = int>

TVec< TVal, TSizeTy >::TVec ( TVal *  _ValT, const TSizeTy &  _Vals  )

inlineexplicit

Constructs a vector of _Vals elements of memory array _ValT.

The data is not copied and the vector does not own the memory (i.e., the vector won't free the memory at destruction).

Definition at line 459 of file ds.h.

                                                  :
    MxVals(-1), Vals(_Vals), ValT(_ValT), IsShM(false){}

template<class TVal, class TSizeTy = int>

TVec< TVal, TSizeTy >::~TVec ( )

inline

Definition at line 461 of file ds.h.

{if ((ValT!=NULL) && (MxVals!=-1)) {delete[] ValT;}}

template<class TVal, class TSizeTy = int>

TVec< TVal, TSizeTy >::TVec ( TSIn &  SIn )

inlineexplicit

Definition at line 462 of file ds.h.

: MxVals(0), Vals(0), ValT(NULL), IsShM(false) {Load(SIn);}

Member Function Documentation

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::Add ( )

inline

Adds a new element at the end of the vector, after its current last element.

This increases the vector size by one.

Definition at line 602 of file ds.h.

               { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize();} return Vals++;}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::Add ( const TVal &  Val )

inline

Adds a new element at the end of the vector, after its current last element.

The content of Val is copied to the new element.

Definition at line 608 of file ds.h.

                              { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::Add ( TVal &  Val )

inline

Definition at line 610 of file ds.h.

                        { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::Add ( const TVal &  Val, const TSizeTy &  ResizeLen  )

inline

Adds element Val at the end of the vector. #TVec::Add2.

Definition at line 613 of file ds.h.

                                                        { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize(MxVals+ResizeLen);} ValT[Vals]=Val; return Vals++;}

template<class TVal, class TSizeTy >

TSizeTy TVec< TVal, TSizeTy >::AddBackSorted	(	const TVal &	Val,
		const bool &	Asc
	)

Adds element Val to a sorted vector.

Parameters

Asc	Adds the element so that ascending (if true) or descending (if false) order is maintained.

Definition at line 1133 of file ds.h.

                                                                          {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Add();
  TSizeTy ValN=Vals-2;
  while ((ValN>=0)&&((Asc&&(Val<ValT[ValN]))||(!Asc&&(Val>ValT[ValN])))){
    ValT[ValN+1]=ValT[ValN]; ValN--;}
  ValT[ValN+1]=Val;
  return ValN+1;
}

template<class TVal, class TSizeTy >

TSizeTy TVec< TVal, TSizeTy >::AddMerged

(

const TVal &

Val

)

Adds element Val to a sorted vector only if the element Val is not already in the vector.

Uses binary search to check whether an element is already in the vector.

Definition at line 1145 of file ds.h.

                                                     {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=SearchBin(Val);
  if (ValN==-1){return AddSorted(Val);}
  else {GetVal(ValN)=Val; return -1;}
}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::AddMP ( const TVal &  Val )

inline

Adds element Val at the end of the vector in a thread safe manner, returns the element index in the vector. TVec::AddMP.

Definition at line 617 of file ds.h.

                                { const int Idx = __sync_fetch_and_add(&Vals, 1);
     ValT[Idx]=Val; return Idx;}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::AddSorted	(	const TVal &	Val,
		const bool &	Asc = true,
		const TSizeTy &	_MxVals = -1
	)

Adds element Val to a sorted vector.

Parameters

Asc	Adds the element so that ascending (if true) or descending (if false) order is maintained.

Definition at line 1117 of file ds.h.

                                                                                              {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=Add(Val);
  if (Asc){
    while ((ValN>0)&&(ValT[ValN]<ValT[ValN-1])){
      Swap(ValN, ValN-1); ValN--;}
  } else {
    while ((ValN>0)&&(ValT[ValN]>ValT[ValN-1])){
      Swap(ValN, ValN-1); ValN--;}
  }
  if ((_MxVals!=-1)&&(Len()>_MxVals)){Del(_MxVals, Len()-1);}
  return ValN;
}

template<class TVal, class TSizeTy >

TSizeTy TVec< TVal, TSizeTy >::AddUnique

(

const TVal &

Val

)

Adds element Val to a vector only if the element Val is not already in the vector.

Does not assume the vector to be sorted and thus uses linear search to check whether Val is already in the vector.

Definition at line 1162 of file ds.h.

                                                     {
  AssertR(MxVals!=-1 || IsShM, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=SearchForw(Val);
  if (ValN==-1){return Add(Val);}
  else {GetVal(ValN)=Val; return -1;}
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::AddV

(

const TVec< TVal, TSizeTy > &

ValV

)

Adds the elements of the vector ValV to the to end of the vector.

Definition at line 1110 of file ds.h.

                                                                {
  AssertR(MxVals!=-1 || IsShM, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){Add(ValV[ValN]);}
  return Len();
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::AddVMerged

(

const TVec< TVal, TSizeTy > &

ValV

)

Adds elements of ValV to a sorted vector only if a particular element is not already in the vector.

Uses binary search to check whether an element is already in the vector.

Definition at line 1154 of file ds.h.

                                                                      {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){AddMerged(ValV[ValN]);}
  return Len();
}

template<class TVal, class TSizeTy = int>

TIter TVec< TVal, TSizeTy >::BegI ( ) const

inline

Returns an iterator pointing to the first element in the vector.

Definition at line 593 of file ds.h.

{return ValT;}

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::BSort	(	const TSizeTy &	MnLValN,
		const TSizeTy &	MxRValN,
		const bool &	Asc
	)

Bubble sorts the values between positions MnLValN...MxLValN.

Parameters

Asc	Sorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1235 of file ds.h.

                                                                                              {
  for (TSizeTy ValN1=MnLValN; ValN1<=MxRValN; ValN1++){
    for (TSizeTy ValN2=MxRValN; ValN2>ValN1; ValN2--){
      if (Asc){
        if (ValT[ValN2]<ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
      } else {
        if (ValT[ValN2]>ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
      }
    }
  }
}

template<class TVal, class TSizeTy = int>

template<class TCmp >

static void TVec< TVal, TSizeTy >::BSortCmp ( TIter  BI, TIter  EI, const TCmp &  Cmp  )

inlinestatic

Bubble sorts the values between positions BI...EI under the comparator Cmp.

Definition at line 750 of file ds.h.

                                                            {
    for (TIter i = BI; i != EI; ++i) {
      for (TIter j = EI-1; j != i; --j) {
        if (Cmp(*j, *(j-1))) { SwapI(j, j-1); } } } }

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::Clr	(	const bool &	DoDel = true,
		const TSizeTy &	NoDelLim = -1
	)

Clears the contents of the vector.

Vector's memory gets deallocated only if DoDel=true or if vector's capacity is greater than NoDelLim.

Definition at line 1022 of file ds.h.

                                                                       {
  if ((DoDel)||((!DoDel)&&(NoDelLim!=-1)&&(MxVals>NoDelLim))){
    if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
    MxVals=Vals=0; ValT=NULL;
  } else {
    IAssertR(MxVals!=-1 || IsShM, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    Vals=0;
  }
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::CopyUniqueFrom	(	TVec< TVal, TSizeTy > &	Vec,
		TInt	Offset,
		TInt	Sz
	)

Copy Sz values from Vec starting at Offset.

Definition at line 1082 of file ds.h.

                                                                                      {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  if (this!=&Vec){
    if (ValT!=NULL && MxVals!=-1 && MxVals < Sz){
      delete[] ValT;
      ValT=new TVal[Sz];
    }
    if (Sz == 0) { Vals = 0; return; }
    ValT[0] = Vec.ValT[Offset];
    Vals = 1;
    for (TSizeTy ValN=1; ValN<Sz; ValN++){
      if (ValT[Vals-1] != Vec.ValT[Offset+ValN]) {
        ValT[Vals++] = Vec.ValT[Offset+ValN];
      }
    }
  }
}

template<class TVal, class TSizeTy >

TSizeTy TVec< TVal, TSizeTy >::Count

(

const TVal &

Val

)

const

Counts the number of occurrences of Val in the vector.

Definition at line 1511 of file ds.h.

                                                        {
  TSizeTy Count = 0;
  for (TSizeTy i = 0; i < Len(); i++){
    if (Val == ValT[i]){Count++;}}
  return Count;
}

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::Del

(

const TSizeTy &

ValN

)

Removes the element at position ValN.

Definition at line 1189 of file ds.h.

                                                {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Assert((0<=ValN)&&(ValN<Vals));
  for (TSizeTy MValN=ValN+1; MValN<Vals; MValN++){
    ValT[MValN-1]=ValT[MValN];}
  ValT[--Vals]=TVal();
}

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::Del	(	const TSizeTy &	MnValN,
		const TSizeTy &	MxValN
	)

Removes the elements at positions MnValN...MxValN.

Definition at line 1199 of file ds.h.

                                                                         {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Assert((0<=MnValN)&&(MnValN<Vals)&&(0<=MxValN)&&(MxValN<Vals));
  Assert(MnValN<=MxValN);
  for (TSizeTy ValN=MxValN+1; ValN<Vals; ValN++){
    ValT[MnValN+ValN-MxValN-1]=ValT[ValN];}
  for (TSizeTy ValN=Vals-MxValN+MnValN-1; ValN<Vals; ValN++){
    ValT[ValN]=TVal();}
  Vals-=MxValN-MnValN+1;
}

template<class TVal, class TSizeTy >

void TVec< TVal, TSizeTy >::DelAll

(

const TVal &

Val

)

Removes all occurrences of element Val.

Definition at line 1221 of file ds.h.

                                               {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN;
  while ((ValN=SearchForw(Val))!=-1){Del(ValN);}
}

template<class TVal, class TSizeTy >

bool TVec< TVal, TSizeTy >::DelIfIn

(

const TVal &

Val

)

Removes the first occurrence of element Val.

Definition at line 1212 of file ds.h.

                                                {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=SearchForw(Val);
  if (ValN!=-1){Del(ValN); return true;}
  else {return false;}
}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::DelLast ( )

inline

Removes the last element of the vector.

Definition at line 665 of file ds.h.

{Del(Len()-1);}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Diff

(

const TVec< TVal, TSizeTy > &

ValV

)

Subtracts ValV from this vector. Assumes the vectors are sorted!

This vector keeps only elements that do not appear in ValV.

Definition at line 1425 of file ds.h.

                                                             {
  TVec<TVal, TSizeTy> DiffVec;
  Diff(ValV, DiffVec);
  MoveFrom(DiffVec);
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Diff	(	const TVec< TVal, TSizeTy > &	ValV,
		TVec< TVal, TSizeTy > &	DstValV
	)		const

Sets DstValV to the difference between this vector and ValV. Assumes the vectors are sorted!

DstValV has all the elements of this vector that do not appear in ValV.

Definition at line 1463 of file ds.h.

                                                                                                  {
  DstValV.Clr();
  TSizeTy ValN1=0, ValN2=0;
  while (ValN1<Len() && ValN2<ValV.Len()) {
    const TVal& Val1 = GetVal(ValN1);
    while (ValN2<ValV.Len() && Val1>ValV.GetVal(ValN2)) ValN2++;
    if (ValN2<ValV.Len()) {
      if (Val1!=ValV.GetVal(ValN2)) { DstValV.Add(Val1); }
      ValN1++;
    }
  }
  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
    DstValV.Add(GetVal(RestValN1));}
}

template<class TVal, class TSizeTy = int>

bool TVec< TVal, TSizeTy >::Empty ( ) const

inline

Tests whether the vector is empty.

This means the vector contains zero elements (while its capacity may be greater than zero).

Definition at line 570 of file ds.h.

{return Vals==0;}

template<class TVal, class TSizeTy = int>

TIter TVec< TVal, TSizeTy >::EndI ( ) const

inline

Returns an iterator referring to the past-the-end element in the vector.

Definition at line 595 of file ds.h.

{return ValT+Vals;}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::Gen ( const TSizeTy &  _Vals )

inline

Constructs a vector (an array) of _Vals elements.

Definition at line 523 of file ds.h.

                                { IAssert(0<=_Vals);
    if (ValT!=NULL && MxVals!=-1){delete[] ValT;} MxVals=Vals=_Vals;
    if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::Gen ( const TSizeTy &  _MxVals, const TSizeTy &  _Vals  )

inline

Constructs a vector (an array) of _Vals elements, while reserving enough memory for _MxVals elements.

Definition at line 527 of file ds.h.

                                                        { IAssert((0<=_Vals)&&(_Vals<=_MxVals));
    if (ValT!=NULL  && MxVals!=-1){delete[] ValT;} MxVals=_MxVals; Vals=_Vals;
    if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::GenExt ( TVal *  _ValT, const TSizeTy &  _Vals  )

inline

Constructs a vector of _Vals elements of memory array _ValT.

The data is not copied and the vector does not own the memory (the vector won't free the memory at destruction).

Definition at line 534 of file ds.h.

                                                {
    if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
    MxVals=-1; Vals=_Vals; ValT=_ValT;}

template<class TVal, class TSizeTy = int>

TVal& TVec< TVal, TSizeTy >::GetAddDat ( const TVal &  Val )

inline

Returns reference to the first occurrence of element Val.

If the element does not exist, we add it at the end of the vector.

Definition at line 842 of file ds.h.

                                  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    const TSizeTy ValN=SearchForw(Val); if (ValN==-1){Add(Val); return Last();} else {return GetVal(ValN);}}

template<class TVal, class TSizeTy = int>

const TVal& TVec< TVal, TSizeTy >::GetDat ( const TVal &  Val ) const

inline

Returns reference to the first occurrence of element Val.

Definition at line 838 of file ds.h.

{ return GetVal(SearchForw(Val));}

template<class TVal, class TSizeTy = int>

TIter TVec< TVal, TSizeTy >::GetI ( const TSizeTy &  ValN ) const

inline

Returns an iterator an element at position ValN.

Definition at line 597 of file ds.h.

{return ValT+ValN;}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::GetMemSize ( ) const

inline

Returns the memory size (the number of bytes) of a binary representation.

Definition at line 514 of file ds.h.

                             {
    return TSizeTy(2*sizeof(TVal)+sizeof(TSizeTy)*Vals);}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::GetMemUsed ( ) const

inline

Returns the memory footprint (the number of bytes) of the vector.

Definition at line 511 of file ds.h.

                             {
    return TSizeTy(2*sizeof(TSizeTy)+sizeof(TVal*)+MxVals*sizeof(TVal));}

template<class TVal , class TSizeTy >

TSizeTy TVec< TVal, TSizeTy >::GetMxValN

(

)

const

Returns the position of the largest element in the vector.

Definition at line 1579 of file ds.h.

                                             {
  if (Vals==0){return -1;}
  TSizeTy MxValN=0;
  for (TSizeTy ValN=1; ValN<Vals; ValN++){
    if (ValT[ValN]>ValT[MxValN]){MxValN=ValN;}
  }
  return MxValN;
}

template<class TVal , class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::GetPivotValN	(	const TSizeTy &	LValN,
		const TSizeTy &	RValN
	)		const

Picks three random elements at positions LValN...RValN and returns the middle one.

Definition at line 1265 of file ds.h.

                                                                                          {
  TSizeTy SubVals=RValN-LValN+1;
  if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
  const TSizeTy ValN1=LValN+TInt::GetRnd(int(SubVals));
  const TSizeTy ValN2=LValN+TInt::GetRnd(int(SubVals));
  const TSizeTy ValN3=LValN+TInt::GetRnd(int(SubVals));
  const TVal& Val1=ValT[ValN1];
  const TVal& Val2=ValT[ValN2];
  const TVal& Val3=ValT[ValN3];
  if (Val1<Val2){
    if (Val2<Val3){return ValN2;}
    else if (Val3<Val1){return ValN1;}
    else {return ValN3;}
  } else {
    if (Val1<Val3){return ValN1;}
    else if (Val3<Val2){return ValN2;}
    else {return ValN3;}
  }
}

template<class TVal, class TSizeTy = int>

template<class TCmp >

static TIter TVec< TVal, TSizeTy >::GetPivotValNCmp ( const TIter &  BI, const TIter &  EI, const TCmp &  Cmp  )

inlinestatic

Picks three random elements at positions BI...EI and returns the middle one under the comparator Cmp.

Definition at line 729 of file ds.h.

                                                                                  {
    TSizeTy SubVals=TSizeTy(EI-BI); if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
    const TSizeTy ValN1=TInt::GetRnd(SubVals), ValN2=TInt::GetRnd(SubVals), ValN3=TInt::GetRnd(SubVals);
    const TVal& Val1 = *(BI+ValN1);  const TVal& Val2 = *(BI+ValN2); const TVal& Val3 = *(BI+ValN3);
    if (Cmp(Val1, Val2)) {
      if (Cmp(Val2, Val3)) return BI+ValN2;
      else if (Cmp(Val3, Val1)) return BI+ValN1;
      else return BI+ValN3;
    } else {
      if (Cmp(Val1, Val3)) return BI+ValN1;
      else if (Cmp(Val3, Val2)) return BI+ValN2;
      else return BI+ValN3; } }

template<class TVal , class TSizeTy >

int TVec< TVal, TSizeTy >::GetPrimHashCd

(

)

const

Returns primary hash code of the vector. Used by THash.

Definition at line 999 of file ds.h.

                                             {
  int hc = 0;
  for (TSizeTy i=0; i<Vals; i++){
    hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetPrimHashCd());
  }
  return hc;
}

template<class TVal, class TSizeTy = int>

const TVal& TVec< TVal, TSizeTy >::GetRndVal ( TRnd &  Rnd = TInt::Rnd ) const

inline

Returns a reference to a random element in the vector.

Definition at line 589 of file ds.h.

{ return GetVal(Rnd.GetUniDevInt(Len())); }

template<class TVal, class TSizeTy = int>

TVal& TVec< TVal, TSizeTy >::GetRndVal ( TRnd &  Rnd = TInt::Rnd )

inline

Returns a reference to a random element in the vector.

Definition at line 591 of file ds.h.

{ return GetVal(Rnd.GetUniDevInt(Len())); }

template<class TVal , class TSizeTy >

int TVec< TVal, TSizeTy >::GetSecHashCd

(

)

const

Returns secondary hash code of the vector. Used by THash.

Definition at line 1011 of file ds.h.

                                            {
  int hc = 0;
  for (TSizeTy i=0; i<Vals; i++){
    hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetSecHashCd());
  }
  if (Vals > 0) {
    hc = TPairHashImpl::GetHashCd(hc, ValT[0].GetSecHashCd()); }
  return hc;
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::GetSubValV	(	const TSizeTy &	BValN,
		const TSizeTy &	EValN,
		TVec< TVal, TSizeTy > &	ValV
	)		const

Fills ValV with elements at positions BValN...EValN.

Definition at line 1170 of file ds.h.

                                                                                                                     {
  const TSizeTy BValN=TInt::GetInRng(_BValN, 0, Len()-1);
  const TSizeTy EValN=TInt::GetInRng(_EValN, 0, Len()-1);
  const TSizeTy SubVals=TInt::GetMx(0, EValN-BValN+1);
  SubValV.Gen(SubVals, 0);
  for (TSizeTy ValN=BValN; ValN<=EValN; ValN++){
    SubValV.Add(GetVal(ValN));}
}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1 )

inlinestatic

Returns a vector on element Val1.

Definition at line 848 of file ds.h.

                                                   {
    TVec<TVal, TSizeTy> V(1, 0); V.Add(Val1); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2  )

inlinestatic

Returns a vector on elements Val1, Val2.

Definition at line 851 of file ds.h.

                                                                     {
    TVec<TVal, TSizeTy> V(2, 0); V.Add(Val1); V.Add(Val2); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2, const TVal &  Val3  )

inlinestatic

Returns a vector on elements Val1...Val3.

Definition at line 854 of file ds.h.

                                                                                       {
    TVec<TVal, TSizeTy> V(3, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2, const TVal &  Val3, const TVal &  Val4  )

inlinestatic

Returns a vector on elements Val1...Val4.

Definition at line 857 of file ds.h.

                                                                                                         {
    TVec<TVal, TSizeTy> V(4, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2, const TVal &  Val3, const TVal &  Val4, const TVal &  Val5  )

inlinestatic

Returns a vector on elements Val1...Val5.

Definition at line 860 of file ds.h.

                                                                                                                           {
    TVec<TVal, TSizeTy> V(5, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2, const TVal &  Val3, const TVal &  Val4, const TVal &  Val5, const TVal &  Val6  )

inlinestatic

Returns a vector on elements Val1...Val6.

Definition at line 863 of file ds.h.

                                                                                                                                             {
    TVec<TVal, TSizeTy> V(6, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2, const TVal &  Val3, const TVal &  Val4, const TVal &  Val5, const TVal &  Val6, const TVal &  Val7  )

inlinestatic

Returns a vector on elements Val1...Val7.

Definition at line 866 of file ds.h.

                                                                                                                                                               {
    TVec<TVal, TSizeTy> V(7, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2, const TVal &  Val3, const TVal &  Val4, const TVal &  Val5, const TVal &  Val6, const TVal &  Val7, const TVal &  Val8  )

inlinestatic

Returns a vector on elements Val1...Val8.

Definition at line 869 of file ds.h.

                                                                                                                                                                                 {
    TVec<TVal, TSizeTy> V(8, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); V.Add(Val8); return V;}

template<class TVal, class TSizeTy = int>

static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1, const TVal &  Val2, const TVal &  Val3, const TVal &  Val4, const TVal &  Val5, const TVal &  Val6, const TVal &  Val7, const TVal &  Val8, const TVal &  Val9  )

inlinestatic

Returns a vector on elements Val1...Val9.

Definition at line 872 of file ds.h.

                                                                                                                                                                                                   {
    TVec<TVal, TSizeTy> V(9, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); V.Add(Val8); V.Add(Val9); return V;}

template<class TVal, class TSizeTy = int>

const TVal& TVec< TVal, TSizeTy >::GetVal ( const TSizeTy &  ValN ) const

inline

Returns a reference to the element at position ValN in the vector.

Definition at line 649 of file ds.h.

{return operator[](ValN);}

template<class TVal, class TSizeTy = int>

TVal& TVec< TVal, TSizeTy >::GetVal ( const TSizeTy &  ValN )

inline

Returns a reference to the element at position ValN in the vector.

Definition at line 651 of file ds.h.

{return operator[](ValN);}

template<class TVal , class TSizeTy>

TStr TVec< TVal, TSizeTy >::GetXOutOfBoundsErrMsg ( const TSizeTy &  ValN ) const

protected

Constructs the out of bounds error message.

Definition at line 913 of file ds.h.

                                                                         {
  return TStr()+
  "Index:"+TInt::GetStr(ValN)+
  " Vals:"+TInt::GetStr(Vals)+
  " MxVals:"+TInt::GetStr(MxVals)+
  " Type:"+GetTypeNm(*this);
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Ins	(	const TSizeTy &	ValN,
		const TVal &	Val
	)

Inserts new element Val before the element at position ValN.

Definition at line 1180 of file ds.h.

                                                                 {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Add();  Assert((0<=ValN)&&(ValN<Vals));
  for (TSizeTy MValN=Vals-2; MValN>=ValN; MValN--){ValT[MValN+1]=ValT[MValN];}
  ValT[ValN]=Val;
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Intrs

(

const TVec< TVal, TSizeTy > &

ValV

)

Sets this vector to its intersection with ValV. Assumes the vectors are sorted!

Definition at line 1411 of file ds.h.

                                                              {
  TVec<TVal, TSizeTy> IntrsVec;
  Intrs(ValV, IntrsVec);
  MoveFrom(IntrsVec);
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Intrs	(	const TVec< TVal, TSizeTy > &	ValV,
		TVec< TVal, TSizeTy > &	DstValV
	)		const

Sets DstValV to the intersection of this vector and ValV. Assumes the vectors are sorted!

Definition at line 1432 of file ds.h.

                                                                                                   {
  DstValV.Clr();
  TSizeTy ValN1=0, ValN2=0;
  while ((ValN1<Len())&&(ValN2<ValV.Len())){
    const TVal& Val1=GetVal(ValN1);
    while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
      ValN2++;}
    if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
      DstValV.Add(Val1); ValN2++;}
    ValN1++;
  }
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::IntrsLen

(

const TVec< TVal, TSizeTy > &

ValV

)

const

Returns the size of the intersection of vectors this and ValV. Assumes the vectors are sorted!

Definition at line 1479 of file ds.h.

                                                                           {
  TSizeTy Cnt=0, ValN1=0, ValN2=0;
  while ((ValN1<Len())&&(ValN2<ValV.Len())){
    const TVal& Val1=GetVal(ValN1);
    while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
      ValN2++;}
    if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
      ValN2++; Cnt++;}
    ValN1++;
  }
  return Cnt;
}

template<class TVal, class TSizeTy = int>

bool TVec< TVal, TSizeTy >::IsExt ( ) const

inline

Returns true if the vector was created using the GenExt().

In this case the vector does not own the memory (and won't free the memory at destruction).

Definition at line 541 of file ds.h.

{return MxVals==-1;}

template<class TVal, class TSizeTy = int>

bool TVec< TVal, TSizeTy >::IsIn ( const TVal &  Val ) const

inline

Checks whether element Val is a member of the vector.

Definition at line 828 of file ds.h.

{return SearchForw(Val)!=-1;}

template<class TVal, class TSizeTy = int>

bool TVec< TVal, TSizeTy >::IsIn ( const TVal &  Val, TSizeTy &  ValN  ) const

inline

Checks whether element Val is a member of the vector.

Position of Val is returned in ValN.

Definition at line 832 of file ds.h.

{ ValN=SearchForw(Val); return ValN!=-1;}

template<class TVal, class TSizeTy = int>

bool TVec< TVal, TSizeTy >::IsInBin ( const TVal &  Val ) const

inline

Checks whether element Val is a member of the vector.

Uses binary search and thus assumes the vector is sorted.

Definition at line 836 of file ds.h.

{return SearchBin(Val)!=-1;}

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::ISort	(	const TSizeTy &	MnLValN,
		const TSizeTy &	MxRValN,
		const bool &	Asc
	)

Insertion sorts the values between positions MnLValN...MxLValN.

Parameters

Asc	Sorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1248 of file ds.h.

                                                                                              {
  if (MnLValN<MxRValN){
    for (TSizeTy ValN1=MnLValN+1; ValN1<=MxRValN; ValN1++){
      TVal Val=ValT[ValN1]; TSizeTy ValN2=ValN1;
      if (Asc){
        while ((ValN2>MnLValN)&&(ValT[ValN2-1]>Val)){
          ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
      } else {
        while ((ValN2>MnLValN)&&(ValT[ValN2-1]<Val)){
          ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
      }
      ValT[ValN2]=Val;
    }
  }
}

template<class TVal, class TSizeTy = int>

template<class TCmp >

static void TVec< TVal, TSizeTy >::ISortCmp ( TIter  BI, TIter  EI, const TCmp &  Cmp  )

inlinestatic

Insertion sorts the values between positions BI...EI under the comparator Cmp.

Definition at line 756 of file ds.h.

                                                            {
    if (BI + 1 < EI) {
      for (TIter i = BI, j; i != EI; ++i) { TVal Tmp=*i;  j=i;
        while (j > BI && Cmp(Tmp, *(j-1))) { *j = *(j-1); --j; } *j=Tmp; } } }

template<class TVal , class TSizeTy >

bool TVec< TVal, TSizeTy >::IsSorted

(

const bool &

Asc = true

)

const

Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order.

Definition at line 1323 of file ds.h.

                                                        {
  if (Asc){
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      if (ValT[ValN]>ValT[ValN+1]){return false;}}
  } else {
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      if (ValT[ValN]<ValT[ValN+1]){return false;}}
  }
  return true;
}

template<class TVal, class TSizeTy = int>

template<class TCmp >

bool TVec< TVal, TSizeTy >::IsSortedCmp ( const TCmp &  Cmp ) const

inline

Checks whether the vector is sorted according to the comparator Cmp.

Definition at line 773 of file ds.h.

                                          {
    if (EndI() == BegI()) return true;
    for (TIter i = BegI(); i != EndI()-1; ++i) {
      if (Cmp(*(i+1), *i)){return false;} } return true; }

template<class TVal, class TSizeTy = int>

const TVal& TVec< TVal, TSizeTy >::Last ( ) const

inline

Returns a reference to the last element of the vector.

Definition at line 579 of file ds.h.

{return GetVal(Len()-1);}

template<class TVal, class TSizeTy = int>

TVal& TVec< TVal, TSizeTy >::Last ( )

inline

Returns a reference to the last element of the vector.

Definition at line 581 of file ds.h.

{return GetVal(Len()-1);}

template<class TVal, class TSizeTy = int>

const TVal& TVec< TVal, TSizeTy >::LastLast ( ) const

inline

Returns a reference to the one before last element of the vector.

Definition at line 585 of file ds.h.

{ AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}

template<class TVal, class TSizeTy = int>

TVal& TVec< TVal, TSizeTy >::LastLast ( )

inline

Returns a reference to the one before last element of the vector.

Definition at line 587 of file ds.h.

{ AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::LastValN ( ) const

inline

Returns the position of the last element.

Definition at line 583 of file ds.h.

{return Len()-1;}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::Len ( ) const

inline

Returns the number of elements in the vector.

This is the number of actual objects held in the vector, which is not necessarily equal to its storage capacity.

Definition at line 575 of file ds.h.

{return Vals;}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Load

(

TSIn &

SIn

)

Definition at line 946 of file ds.h.

                                       {
  if ( (ValT!=NULL) && (MxVals!=-1)) {delete[] ValT;}
  SIn.Load(MxVals); SIn.Load(Vals); MxVals=Vals;
  if ( MxVals==0 ){ValT=NULL;} else {ValT=new TVal[MxVals];}
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=TVal(SIn);}
}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::LoadShM

(

TShMIn &

ShMIn

)

Constructs the vector from a shared memory input.

The buffer is mapped straight to memory, so this method should not be used if initialization of the elements is needed. Disallowed operations for shared memory vectors include editing values in the vector directly, copying into the vector, and truncating the vector

Definition at line 932 of file ds.h.

                                               {
  if ((ValT!=NULL) && (MxVals!=-1)) {delete[] ValT;}
  ShMIn.Load(MxVals);
  MxVals = -1;
  ShMIn.Load(Vals);
  if (MxVals == 0) {
    ValT = NULL;
  } else {
      ValT = (TVal*)(ShMIn.AdvanceCursor(Vals*sizeof(TVal)));
      IsShM = true;
  }
}

template<class TVal, class TSizeTy = int>

template<typename TLoadShMElem >

void TVec< TVal, TSizeTy >::LoadShM ( TShMIn &  ShMIn, TLoadShMElem  LoadFromShMFn  )

inline

Constructs vector from shared memory input passing in functor to initialize elements.

Definition at line 472 of file ds.h.

                                                          {
    if ((ValT!=NULL) && (MxVals!=-1)) {delete[] ValT;}
    ShMIn.Load(MxVals);
    ShMIn.Load(Vals);
    if (MxVals == 0) {
      ValT = NULL;
    } else {
        ValT=new TVal[MxVals];
        for (TSizeTy ValN=0; ValN<Vals; ValN++) {
          LoadFromShMFn(ValT+ValN, ShMIn);
        }
    }
    IsShM = false;
  }

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::LoadXml	(	const PXmlTok &	XmlTok,
		const TStr &	Nm = ""
	)

Definition at line 103 of file xmlser.h.

                                                                      {
  XLoadHd(Nm);
  TSizeTy SubToks=XmlTok->GetSubToks(); Gen(SubToks, 0);
  for (TSizeTy SubTokN=0; SubTokN<SubToks; SubTokN++){
    PXmlTok SubTok=XmlTok->GetSubTok(SubTokN);
    TVal Val; Val.LoadXml(SubTok, TStr()); Add(Val);
  }
}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Merge

(

)

Sorts the vector and only keeps a single element of each value.

Definition at line 1356 of file ds.h.

                               {
  IAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TVec<TVal, TSizeTy> SortedVec(*this); SortedVec.Sort();
  Clr();
  for (TSizeTy ValN=0; ValN<SortedVec.Len(); ValN++){
    if ((ValN==0)||(SortedVec[ValN-1]!=SortedVec[ValN])){
      Add(SortedVec[ValN]);}
  }
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::MoveFrom

(

TVec< TVal, TSizeTy > &

Vec

)

Takes over the data and the capacity from Vec.

No memory gets copied and Vec gets destroyed.

Definition at line 1073 of file ds.h.

                                                          {
  if (this!=&Vec){
    if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
    MxVals=Vec.MxVals; Vals=Vec.Vals; ValT=Vec.ValT;
    Vec.MxVals=0; Vec.Vals=0; Vec.ValT=NULL;
  }
}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::MoveLastMP ( const TVal &  Val, int  Inc  )

inline

Reserves space after the current last element in a thread safe manner, returning the old vector size.

The method assumes that the space has been preallocated. It does not perform any checks and it does not resize the vector space. The method is thread-safe.

Definition at line 622 of file ds.h.

                                              { const int Idx = __sync_fetch_and_add(&Vals, Inc);
  return Idx;}

template<class TVal , class TSizeTy >

bool TVec< TVal, TSizeTy >::NextPerm

(

)

Generates next permutation of the elements in the vector.

Assuming we started with a sorted vector repeated calls to NextPerm() will generate all permutations of the elements of the vector. Returns false when the last permutation is reached.

Definition at line 1368 of file ds.h.

                                   {
  // start with a sorted sequence to obtain all permutations
  TSizeTy First = 0, Last = Len(), Next = Len()-1;
  if (Last < 2) return false;
  for(; ; ) {
    // find rightmost element smaller than successor
    TSizeTy Next1 = Next;
    if (GetVal(--Next) < GetVal(Next1)) { // swap with rightmost element that's smaller, flip suffix
      TSizeTy Mid = Last;
      for (; GetVal(Next) >= GetVal(--Mid); ) { }
      Swap(Next, Mid);
      Reverse(Next1, Last-1);
      return true;
    }
    if (Next == First) { // pure descending, flip all
      Reverse();
      return false;
    }
  }
}

template<class TVal, class TSizeTy = int>

TVec<TVal, TSizeTy>& TVec< TVal, TSizeTy >::operator+ ( const TVal &  Val )

inline

Appends value Val to the vector.

Definition at line 495 of file ds.h.

{Add(Val); return *this;}

template<class TVal, class TSizeTy>

bool TVec< TVal, TSizeTy >::operator<

(

const TVec< TVal, TSizeTy > &

Vec

)

const

Lexicographically compares two vectors.

For example, (a,b) < (a',b') if and only if a < a' or (a = a' and b < b').

Definition at line 981 of file ds.h.

                                                                        {
  if (this==&Vec){return false;}
  if (Len()==Vec.Len()){
    for (TSizeTy ValN=0; ValN<Vals; ValN++){
      if (ValT[ValN]<Vec.ValT[ValN]){return true;}
      else if (ValT[ValN]>Vec.ValT[ValN]){return false;}
      else {}
    }
    return false;
  } else {
    return Len()<Vec.Len();
  }
}

template<class TVal, class TSizeTy>

TVec< TVal, TSizeTy > & TVec< TVal, TSizeTy >::operator=

(

const TVec< TVal, TSizeTy > &

Vec

)

Assigns new contents to the vector, replacing its current content.

Definition at line 961 of file ds.h.

                                                                                 {
  if (this!=&Vec){
    if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
    MxVals=Vals=Vec.Vals;
    if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
    for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
  }
  return *this;
}

template<class TVal, class TSizeTy>

bool TVec< TVal, TSizeTy >::operator==

(

const TVec< TVal, TSizeTy > &

Vec

)

const

Checks that the two vectors have the same contents.

Definition at line 972 of file ds.h.

                                                                         {
  if (this==&Vec){return true;}
  if (Len()!=Vec.Len()){return false;}
  for (TSizeTy ValN=0; ValN<Vals; ValN++){
    if (ValT[ValN]!=Vec.ValT[ValN]){return false;}}
  return true;
}

template<class TVal, class TSizeTy = int>

const TVal& TVec< TVal, TSizeTy >::operator[] ( const TSizeTy &  ValN ) const

inline

Returns a reference to the element at position ValN in the vector.

Definition at line 503 of file ds.h.

                                                    {
    AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
    return ValT[ValN];}

template<class TVal, class TSizeTy = int>

TVal& TVec< TVal, TSizeTy >::operator[] ( const TSizeTy &  ValN )

inline

Returns a reference to the element at position ValN in the vector.

Definition at line 507 of file ds.h.

                                       {
    AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
    return ValT[ValN];}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Pack

(

)

Reduces vector capacity (frees memory) to match its size.

Definition at line 1057 of file ds.h.

                              {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot pack accessed shared memory");
  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  if (Vals==0){
    if (ValT!=NULL){delete[] ValT;} ValT=NULL;
  } else
    if (Vals<MxVals){
      MxVals=Vals;
      TVal* NewValT=new TVal[MxVals];
      IAssert(NewValT!=NULL);
      for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
      delete[] ValT; ValT=NewValT;
    }
}

template<class TVal , class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::Partition	(	const TSizeTy &	MnLValN,
		const TSizeTy &	MxRValN,
		const bool &	Asc
	)

Partitions the values between positions MnLValN...MxLValN.

Helper function used by QSort().

Parameters

Asc	Sorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1286 of file ds.h.

                                                                                                     {
  TSizeTy PivotValN=GetPivotValN(MnLValN, MxRValN);
  Swap(PivotValN, MnLValN);
  TVal PivotVal=ValT[MnLValN];
  TSizeTy LValN=MnLValN-1;  TSizeTy RValN=MxRValN+1;
  forever {
    if (Asc){
      do {RValN--;} while (ValT[RValN]>PivotVal);
      do {LValN++;} while (ValT[LValN]<PivotVal);
    } else {
      do {RValN--;} while (ValT[RValN]<PivotVal);
      do {LValN++;} while (ValT[LValN]>PivotVal);
    }
    if (LValN<RValN){Swap(LValN, RValN);}
    else {return RValN;}
  };
}

template<class TVal, class TSizeTy = int>

template<class TCmp >

static TIter TVec< TVal, TSizeTy >::PartitionCmp ( TIter  BI, TIter  EI, const TVal  Pivot, const TCmp &  Cmp  )

inlinestatic

Partitions the values between positions BI...EI under the comparator Cmp.

Definition at line 743 of file ds.h.

                                                                                   {
    forever {
      while (Cmp(*BI, Pivot)){++BI;}  --EI;
      while (Cmp(Pivot, *EI)){--EI;}
      if (!(BI<EI)){return BI;}  SwapI(BI, EI);  ++BI; } }

template<class TVal , class TSizeTy >

bool TVec< TVal, TSizeTy >::PrevPerm

(

)

Generates previous permutation of the elements in the vector.

Returns false when the first permutation is reached.

Definition at line 1390 of file ds.h.

                                   {
  TSizeTy First = 0, Last = Len(), Next = Len()-1;
  if (Last < 2) return false;
  for(; ; ) {
    // find rightmost element not smaller than successor
    TSizeTy Next1 = Next;
    if (GetVal(--Next) >= GetVal(Next1)) { // swap with rightmost element that's not smaller, flip suffix
      TSizeTy Mid = Last;
      for (; GetVal(Next) < GetVal(--Mid); ) { }
      Swap(Next, Mid);
      Reverse(Next1, Last);
      return true;
    }
    if (Next == First) { // pure descending, flip all
      Reverse();
      return false;
    }
  }
}

template<class TVal, class TSizeTy >

void TVec< TVal, TSizeTy >::PutAll

(

const TVal &

Val

)

Sets all elements of the vector to value Val.

Definition at line 1229 of file ds.h.

                                               {
  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=Val;}
}

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::QSort	(	const TSizeTy &	MnLValN,
		const TSizeTy &	MxRValN,
		const bool &	Asc
	)

Quick sorts the values between positions MnLValN...MxLValN.

Helper function used by Sort().

Parameters

Asc	Sorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1305 of file ds.h.

                                                                                              {
  if (MnLValN<MxRValN){
    if (MxRValN-MnLValN<20){
      ISort(MnLValN, MxRValN, Asc);
    } else {
      TSizeTy SplitValN=Partition(MnLValN, MxRValN, Asc);
      QSort(MnLValN, SplitValN, Asc);
      QSort(SplitValN+1, MxRValN, Asc);
    }
  }
}

template<class TVal, class TSizeTy = int>

template<class TCmp >

static void TVec< TVal, TSizeTy >::QSortCmp ( TIter  BI, TIter  EI, const TCmp &  Cmp  )

inlinestatic

Quick sorts the values between positions BI...EI under the comparator Cmp.

Definition at line 762 of file ds.h.

                                                            {
    if (BI + 1 < EI) {
      if (EI - BI < 20) { ISortCmp(BI, EI, Cmp); }
      else { const TVal Val = *GetPivotValNCmp(BI, EI, Cmp);
        TIter Split = PartitionCmp(BI, EI, Val, Cmp);
        QSortCmp(BI, Split, Cmp);  QSortCmp(Split, EI, Cmp); } } }

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::Reduce ( const TSizeTy &  _Vals = -1 )

inline

Reduces the vector's length to _Vals elements, which must be less than the current length.

Definition at line 556 of file ds.h.

{Vals = _Vals;}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::Reserve ( const TSizeTy &  _MxVals )

inline

Reserves enough memory for the vector to store _MxVals elements.

Definition at line 543 of file ds.h.

{Resize(_MxVals);}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::Reserve ( const TSizeTy &  _MxVals, const TSizeTy &  _Vals  )

inline

Reserves enough memory for the vector to store _MxVals elements and sets its length to _Vals.

Definition at line 545 of file ds.h.

{ IAssert((0<=_Vals)&&(_Vals<=_MxVals)); Resize(_MxVals); Vals=_Vals;}

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::Reserved ( ) const

inline

Returns the size of allocated storage capacity.

Definition at line 577 of file ds.h.

{return MxVals;}

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::Resize ( const TSizeTy &  _MxVals = -1 )

protected

Resizes the vector so that it can store at least _MxVals.

Definition at line 877 of file ds.h.

                                                      {
  IAssertR(MxVals!=-1 || IsShM, TStr::Fmt("Can not increase the capacity of the vector. %s. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", GetTypeNm(*this).CStr()).CStr());
  IAssertR(MxVals!=(TInt::Mx-1024), TStr::Fmt("Buffer size at maximum. %s. [Program refuses to allocate more memory. Solution-1: Send your test case to developers.]", GetTypeNm(*this).CStr()).CStr());
  TSizeTy OldMxVals = MxVals;
  if (MxVals == -1) {MxVals = Vals;}
  if (_MxVals==-1){
    if (Vals==0){MxVals=16;} else {MxVals*=2;}
  } else {
    if (_MxVals<=MxVals){return;} else {MxVals=_MxVals;}
  }
  if (MxVals < 0) {
    MxVals = TInt::Mx-1024;
  }
  if (ValT==NULL){
    try {
      ValT=new TVal[MxVals];
    }
    catch (std::exception Ex){
      FailR(TStr::Fmt("TVec::Resize: %s, Length:%s, Capacity:%s, New capacity:%s, Type:%s [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]",
        Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
  } else {
    TVal* NewValT = NULL;
    try {
      NewValT=new TVal[MxVals];
    }
    catch (std::exception Ex){
      FailR(TStr::Fmt("TVec::Resize: %s, Length:%s, Capacity:%s, New capacity:%s, Type:%s [Program failed to allocate more memory. Solution-1: Get a bigger machine and a 64-bit compiler.]",
        Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
    IAssert(NewValT!=NULL);
    for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
    if (OldMxVals != -1) {delete[] ValT;} ValT=NewValT;
  }
  IsShM = false;
}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Reverse

(

)

Reverses the order of the elements in the vector.

Definition at line 1350 of file ds.h.

                                 {
  for (TSizeTy ValN=0; ValN<Vals/2; ValN++){
    Swap(ValN, Vals-ValN-1);}
}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::Reverse ( TSizeTy  LValN, TSizeTy  RValN  )

inline

Reverses the order of elements between LValN...RValN.

Definition at line 723 of file ds.h.

{ Assert(LValN>=0 && RValN<Len()); while (LValN < RValN){Swap(LValN++, RValN--);} }

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Save

(

TSOut &

SOut

)

const

Definition at line 954 of file ds.h.

                                                {
  if (MxVals!=-1){SOut.Save(MxVals);} else {SOut.Save(Vals);}
  SOut.Save(Vals);
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].Save(SOut);}
}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::SaveXml	(	TSOut &	SOut,
		const TStr &	Nm
	)		const

Definition at line 113 of file xmlser.h.

                                                                   {
  XSaveHdArg(Nm, "Vals", TInt::GetStr(Vals));
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].SaveXml(SOut, TStr());}
}

template<class TVal, class TSizeTy >

TSizeTy TVec< TVal, TSizeTy >::SearchBack

(

const TVal &

Val

)

const

Returns the position of an element with value Val.

If the element is not found return value is -1. Uses backward linear search.

Definition at line 1559 of file ds.h.

                                                             {
  for (TSizeTy ValN=Vals-1; ValN>=0; ValN--){
    if (Val==ValT[ValN]){return ValN;}}
  return -1;
}

template<class TVal, class TSizeTy >

TSizeTy TVec< TVal, TSizeTy >::SearchBin

(

const TVal &

Val

)

const

Returns the position of an element with value Val.

If the element is not found return value is -1. Uses binary search and thus assumes the vector is sorted.

Definition at line 1519 of file ds.h.

                                                            {
  TSizeTy LValN=0, RValN=Len()-1;
  while (RValN>=LValN){
    TSizeTy ValN=(LValN+RValN)/2;
    if (Val==ValT[ValN]){return ValN;}
    if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
  }
  return -1;
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::SearchBin	(	const TVal &	Val,
		TSizeTy &	InsValN
	)		const

Returns the position of an element with value Val.

If the element is not found return value is -1. Uses binary search and thus assumes the vector is sorted.

Definition at line 1530 of file ds.h.

                                                                              {
  TSizeTy LValN=0, RValN=Len()-1;
  while (RValN>=LValN){
    TSizeTy ValN=(LValN+RValN)/2;
    if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
    if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
  }
  InsValN=LValN; return -1;
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::SearchBinLeft	(	const TVal &	Val,
		TSizeTy &	InsValN
	)		const

Returns the position of an element with value Val.

If the element is not found return value is -1. Uses binary search and thus assumes the vector is sorted.

Definition at line 1541 of file ds.h.

                                                                                  {
  TSizeTy LValN=0, RValN=Len()-1;
  while (RValN>=LValN){
    TSizeTy ValN=(LValN+RValN)/2;
    if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
    if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
  }
  InsValN=RValN; return -1;
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::SearchForw	(	const TVal &	Val,
		const TSizeTy &	BValN = 0
	)		const

Returns the position of an element with value Val.

If the element is not found return value is -1. Uses linear search starting at position BValN.

Definition at line 1552 of file ds.h.

                                                                                   {
  for (TSizeTy ValN=BValN; ValN<Vals; ValN++){
    if (Val==ValT[ValN]){return ValN;}}
  return -1;
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::SearchVForw	(	const TVec< TVal, TSizeTy > &	ValV,
		const TSizeTy &	BValN = 0
	)		const

Returns the starting position of vector ValV.

If the vector is not found return value is -1.

Definition at line 1566 of file ds.h.

                                                                                                    {
  TSizeTy ValVLen=ValV.Len();
  for (TSizeTy ValN=BValN; ValN<Vals-ValVLen+1; ValN++){
    bool Found=true;
    for (TSizeTy SubValN=0; SubValN<ValVLen; SubValN++){
      if (ValV[SubValN]!=GetVal(ValN+SubValN)){Found=false; break;}
    }
    if (Found){return ValN;}
  }
  return -1;
}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::SetVal ( const TSizeTy &  ValN, const TVal &  Val  )

inline

Sets the value of element at position ValN to Val.

Definition at line 653 of file ds.h.

                                                   {
    EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
    AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN)); ValT[ValN] = Val;}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Shuffle

(

TRnd &

Rnd

)

Randomly shuffles the elements of the vector.

Definition at line 1335 of file ds.h.

                                          {
  if (Len() < TInt::Mx) {
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      const int Range = int(Vals-ValN);
      Swap(ValN, ValN+Rnd.GetUniDevInt(Range));
    }
  } else {
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      const TSizeTy Range = Vals-ValN;
      Swap(ValN, TSizeTy(ValN+Rnd.GetUniDevInt64(Range)));
    }
  }
}

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Sort

(

const bool &

Asc = true

)

Sorts the elements of the vector.

Use a combination if quicksort and insertion sort.

Parameters

Asc	Sorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1318 of file ds.h.

                                             {
  QSort(0, Len()-1, Asc);
}

template<class TVal, class TSizeTy = int>

template<class TCmp >

void TVec< TVal, TSizeTy >::SortCmp ( const TCmp &  Cmp )

inline

Sorts the elements of the vector using the comparator Cmp.

Definition at line 770 of file ds.h.

{ QSortCmp(BegI(), EndI(), Cmp);}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Swap

(

TVec< TVal, TSizeTy > &

Vec

)

Swaps the contents of the vector with Vec.

Definition at line 1101 of file ds.h.

                                                      {
  if (this!=&Vec){
    ::Swap(MxVals, Vec.MxVals);
    ::Swap(Vals, Vec.Vals);
    ::Swap(ValT, Vec.ValT);
  }
}

template<class TVal, class TSizeTy = int>

void TVec< TVal, TSizeTy >::Swap ( const TSizeTy &  ValN1, const TSizeTy &  ValN2  )

inline

Swaps elements at positions ValN1 and ValN2.

Definition at line 674 of file ds.h.

                                                       {EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
    const TVal Val=ValT[ValN1]; ValT[ValN1]=ValT[ValN2]; ValT[ValN2]=Val;}

template<class TVal, class TSizeTy = int>

static void TVec< TVal, TSizeTy >::SwapI ( TIter  LVal, TIter  RVal  )

inlinestatic

Swaps the elements that iterators LVal and RVal point to.

Definition at line 677 of file ds.h.

{const TVal Val=*LVal; *LVal=*RVal; *RVal=Val;}

template<class TVal , class TSizeTy>

void TVec< TVal, TSizeTy >::Trunc

(

const TSizeTy &

_Vals = -1

)

Truncates the vector's length and capacity to _Vals elements.

If _Vals=-1 then the capacity is reduced to match vector's length.

Definition at line 1033 of file ds.h.

                                                   {
  EAssertR(!(MxVals==-1 && IsShM), "Cannot truncate a shared memory vector");
  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  IAssert((_Vals==-1)||(_Vals>=0));
  if ((_Vals!=-1)&&(_Vals>=Vals)){
    return;
  } else
    if (((_Vals==-1)&&(Vals==0))||(_Vals==0)){
      if (ValT!=NULL){delete[] ValT;}
      MxVals=Vals=0; ValT=NULL;
    } else {
      if (_Vals==-1){
        if (MxVals==Vals){return;} else {MxVals=Vals;}
      } else {
        MxVals=Vals=_Vals;
      }
      TVal* NewValT=new TVal[MxVals];
      IAssert(NewValT!=NULL);
      for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
      delete[] ValT; ValT=NewValT;
    }
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Union

(

const TVec< TVal, TSizeTy > &

ValV

)

Sets this vector to its union with ValV. Assumes the vectors are sorted!

Definition at line 1418 of file ds.h.

                                                              {
  TVec<TVal, TSizeTy> UnionVec;
  Union(ValV, UnionVec);
  MoveFrom(UnionVec);
}

template<class TVal, class TSizeTy>

void TVec< TVal, TSizeTy >::Union	(	const TVec< TVal, TSizeTy > &	ValV,
		TVec< TVal, TSizeTy > &	DstValV
	)		const

Sets DstValV to the union of this vector and ValV. Assumes the vectors are sorted!

Definition at line 1446 of file ds.h.

                                                                                                   {
  DstValV.Gen(TInt::GetMx(Len(), ValV.Len()), 0);
  TSizeTy ValN1=0, ValN2=0;
  while ((ValN1<Len())&&(ValN2<ValV.Len())){
    const TVal& Val1=GetVal(ValN1);
    const TVal& Val2=ValV.GetVal(ValN2);
    if (Val1<Val2){DstValV.Add(Val1); ValN1++;}
    else if (Val1>Val2){DstValV.Add(Val2); ValN2++;}
    else {DstValV.Add(Val1); ValN1++; ValN2++;}
  }
  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
    DstValV.Add(GetVal(RestValN1));}
  for (TSizeTy RestValN2=ValN2; RestValN2<ValV.Len(); RestValN2++){
    DstValV.Add(ValV.GetVal(RestValN2));}
}

template<class TVal, class TSizeTy>

TSizeTy TVec< TVal, TSizeTy >::UnionLen

(

const TVec< TVal, TSizeTy > &

ValV

)

const

Returns the size of the union of vectors this and ValV. Assumes the vectors are sorted!

Definition at line 1493 of file ds.h.

                                                                           {
  TSizeTy Cnt = 0, ValN1 = 0, ValN2 = 0;
  while ((ValN1 < Len()) && (ValN2 < ValV.Len())) {
    const TVal& Val1 = GetVal(ValN1);
    const TVal& Val2 = ValV.GetVal(ValN2);
    if (Val1 < Val2) {
      Cnt++; ValN1++;
    } else if (Val1 > Val2) {
      Cnt++; ValN2++;
    } else {
      Cnt++; ValN1++; ValN2++;
    }
  }
  Cnt += (Len() - ValN1) + (ValV.Len() - ValN2);
  return Cnt;
}

Member Data Documentation

template<class TVal, class TSizeTy = int>

bool TVec< TVal, TSizeTy >::IsShM

protected

True if the vector array is in shared memory

Definition at line 437 of file ds.h.

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::MxVals

protected

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by the vector, and it won't free it at destruction.

Definition at line 434 of file ds.h.

template<class TVal, class TSizeTy = int>

TSizeTy TVec< TVal, TSizeTy >::Vals

protected

Vector length. Length is the number of elements stored in the vector.

Definition at line 435 of file ds.h.

template<class TVal, class TSizeTy = int>

TVal* TVec< TVal, TSizeTy >::ValT

protected

Pointer to the memory where the elements of the vector are stored.

Definition at line 436 of file ds.h.

---

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

• glib-core/ds.h
• glib-core/xmlser.h