SNAP Library 2.3, User Reference: TVec< TVal, TSizeTy

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

TSizeTy Vals

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

Definition: ds.h:425

TVal * ValT

Definition: ds.h:426

template<class TVal, class TSizeTy>

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

Definition at line 870 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];}
 }

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 435 of file ds.h.

                                      {
     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 439 of file ds.h.

                                                     {
     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 446 of file ds.h.

446 :

447 MxVals(-1), Vals(_Vals), ValT(_ValT){}

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

TSizeTy Vals

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

Definition: ds.h:425

TVal * ValT

Definition: ds.h:426

template<class TVal, class TSizeTy = int>

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

inline

Definition at line 448 of file ds.h.

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

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

TVal * ValT

Definition: ds.h:426

template<class TVal, class TSizeTy = int>

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

inlineexplicit

Definition at line 449 of file ds.h.

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

TVec::Load

void Load(TSIn &SIn)

Definition: ds.h:877

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

TSizeTy Vals

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

Definition: ds.h:425

TVal * ValT

Definition: ds.h:426

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 559 of file ds.h.

559 { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");

560 if (Vals==MxVals){Resize();} return Vals++;}

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

#define AssertR(Cond, Reason)

Definition: bd.h:258

void Resize(const TSizeTy &_MxVals=-1)

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

Definition: ds.h:831

TSizeTy Vals

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

Definition: ds.h:425

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 564 of file ds.h.

564 { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");

565 if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

#define AssertR(Cond, Reason)

Definition: bd.h:258

void Resize(const TSizeTy &_MxVals=-1)

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

Definition: ds.h:831

TSizeTy Vals

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

Definition: ds.h:425

TVal * ValT

Definition: ds.h:426

template<class TVal, class TSizeTy = int>

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

inline

Definition at line 566 of file ds.h.

566 { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");

567 if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

#define AssertR(Cond, Reason)

Definition: bd.h:258

void Resize(const TSizeTy &_MxVals=-1)

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

Definition: ds.h:831

TSizeTy Vals

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

Definition: ds.h:425

TVal * ValT

Definition: ds.h:426

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 569 of file ds.h.

569 { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");

570 if (Vals==MxVals){Resize(MxVals+ResizeLen);} ValT[Vals]=Val; return Vals++;}

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

#define AssertR(Cond, Reason)

Definition: bd.h:258

void Resize(const TSizeTy &_MxVals=-1)

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

Definition: ds.h:831

TSizeTy Vals

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

Definition: ds.h:425

TVal * ValT

Definition: ds.h:426

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 1042 of file ds.h.

                                                                           {
   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 1053 of file ds.h.

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

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 1027 of file ds.h.

                                                                                               {
   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 1068 of file ds.h.

                                                      {
   AssertR(MxVals!=-1, "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 1020 of file ds.h.

                                                                 {
   AssertR(MxVals!=-1, "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 1061 of file ds.h.

                                                                       {
   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 550 of file ds.h.

550 {return ValT;}

TVal * ValT

Definition: ds.h:426

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 1135 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 693 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 953 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, "This vector was obtained from TVecPool. Such vectors cannot change its size!"); 
     Vals=0;
   }
 }

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 1410 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 1094 of file ds.h.

                                                 {
   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 1103 of file ds.h.

                                                                          {
   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 1123 of file ds.h.

                                                {
   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 1115 of file ds.h.

                                                 {
   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 609 of file ds.h.

609 {Del(Len()-1);}

TVec::Del

void Del(const TSizeTy &ValN)

Removes the element at position ValN.

Definition: ds.h:1094

TSizeTy Len() const

Returns the number of elements in the vector.

Definition: ds.h:535

template<class TVal, class TSizeTy>

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

Subtracts ValV from this vector.

This means this vector keeps only the elements that do not appear in ValV. Assumes the vectors are sorted!

Definition at line 1324 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

DstValV is the difference of vectors this and ValV.

This means DstValV has all the elements of this that do not appear in ValV. Assumes the vectors are sorted!

Definition at line 1362 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 530 of file ds.h.

530 {return Vals==0;}

TSizeTy Vals

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

Definition: ds.h:425

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 552 of file ds.h.

552 {return ValT+Vals;}

TSizeTy Vals

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

Definition: ds.h:425

TVal * ValT

Definition: ds.h:426

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 486 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 490 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 497 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 796 of file ds.h.

796 { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");

797 const TSizeTy ValN=SearchForw(Val); if (ValN==-1){Add(Val); return Last();} else {return GetVal(ValN);}}

const TVal & GetVal(const TSizeTy &ValN) const

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

Definition: ds.h:595

TVec::Last

const TVal & Last() const

Returns a reference to the last element of the vector.

Definition: ds.h:539

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const

Returns the position of an element with value Val.

Definition: ds.h:1440

#define AssertR(Cond, Reason)

Definition: bd.h:258

TVec::Add

TSizeTy Add()

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

Definition: ds.h:559

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 792 of file ds.h.

792 { return GetVal(SearchForw(Val));}

const TVal & GetVal(const TSizeTy &ValN) const

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

Definition: ds.h:595

TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const

Returns the position of an element with value Val.

Definition: ds.h:1440

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 554 of file ds.h.

554 {return ValT+ValN;}

TVal * ValT

Definition: ds.h:426

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 477 of file ds.h.

477 {

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

TSizeTy Vals

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

Definition: ds.h:425

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 474 of file ds.h.

474 {

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

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

template<class TVal , class TSizeTy >

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

Returns the position of the largest element in the vector.

Definition at line 1467 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 1165 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 672 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 930 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 TVec< TVal, TSizeTy >::GetSecHashCd ( ) const

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

Definition at line 942 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

Returns a vector on elements at positions BValN...EValN.

Definition at line 1076 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 802 of file ds.h.

802 {

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

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

Definition: ds.h:420

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 805 of file ds.h.

805 {

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

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

Definition: ds.h:420

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 808 of file ds.h.

808 {

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

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

Definition: ds.h:420

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 811 of file ds.h.

811 {

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

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

Definition: ds.h:420

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 814 of file ds.h.

814 {

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

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

Definition: ds.h:420

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 817 of file ds.h.

817 {

818 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;}

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

Definition: ds.h:420

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 820 of file ds.h.

820 {

821 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;}

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

Definition: ds.h:420

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 823 of file ds.h.

823 {

824 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;}

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

Definition: ds.h:420

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 826 of file ds.h.

826 {

827 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;}

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

Definition: ds.h:420

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 595 of file ds.h.

595 {return operator[](ValN);}

TVec::operator[]

const TVal & operator[](const TSizeTy &ValN) const

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

Definition: ds.h:466

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 597 of file ds.h.

597 {return operator[](ValN);}

TVec::operator[]

const TVal & operator[](const TSizeTy &ValN) const

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

Definition: ds.h:466

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 861 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 1086 of file ds.h.

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

Result is the intersection of this vector with ValV.

Assumes the vectors are sorted!

Definition at line 1310 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

DstValV is the intersection of vectors this and ValV.

Assumes the vectors are sorted!

Definition at line 1331 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 both vectors are sorted in ascending order!

Definition at line 1378 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 504 of file ds.h.

504 {return MxVals==-1;}

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

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 782 of file ds.h.

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

TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const

Returns the position of an element with value Val.

Definition: ds.h:1440

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 786 of file ds.h.

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

TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const

Returns the position of an element with value Val.

Definition: ds.h:1440

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 790 of file ds.h.

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

TVec::SearchBin

TSizeTy SearchBin(const TVal &Val) const

Returns the position of an element with value Val.

Definition: ds.h:1418

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 1148 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 699 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 1223 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 716 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 539 of file ds.h.

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

TSizeTy Len() const

Returns the number of elements in the vector.

Definition: ds.h:535

const TVal & GetVal(const TSizeTy &ValN) const

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

Definition: ds.h:595

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 541 of file ds.h.

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

TSizeTy Len() const

Returns the number of elements in the vector.

Definition: ds.h:535

const TVal & GetVal(const TSizeTy &ValN) const

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

Definition: ds.h:595

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 545 of file ds.h.

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

#define AssertR(Cond, Reason)

Definition: bd.h:258

TVec::GetXOutOfBoundsErrMsg

TSizeTy Vals

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

Definition: ds.h:425

TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const

Constructs the out of bounds error message.

Definition: ds.h:861

TVal * ValT

Definition: ds.h:426

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 547 of file ds.h.

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

#define AssertR(Cond, Reason)

Definition: bd.h:258

TVec::GetXOutOfBoundsErrMsg

TSizeTy Vals

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

Definition: ds.h:425

TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const

Constructs the out of bounds error message.

Definition: ds.h:861

TVal * ValT

Definition: ds.h:426

template<class TVal, class TSizeTy = int>

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

inline

Returns the position of the last element.

Definition at line 543 of file ds.h.

543 {return Len()-1;}

TSizeTy Len() const

Returns the number of elements in the vector.

Definition: ds.h:535

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 535 of file ds.h.

535 {return Vals;}

TSizeTy Vals

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

Definition: ds.h:425

template<class TVal , class TSizeTy >

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

Definition at line 877 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 >::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 1256 of file ds.h.

                                {
   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 1002 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 >

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 1267 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 458 of file ds.h.

458 {Add(Val); return *this;}

TVec::Add

TSizeTy Add()

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

Definition: ds.h:559

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 912 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 892 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 903 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 466 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 470 of file ds.h.

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

template<class TVal , class TSizeTy >

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

The vector reduces its capacity (frees memory) to match its size.

Definition at line 987 of file ds.h.

                               {
   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 1186 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 686 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 1289 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 1130 of file ds.h.

                                                {
   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 1205 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 705 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 >::Reserve ( const TSizeTy & _MxVals )

inline

Reserves enough memory for the vector to store _MxVals elements.

Definition at line 506 of file ds.h.

506 {Resize(_MxVals);}

void Resize(const TSizeTy &_MxVals=-1)

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

Definition: ds.h:831

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 508 of file ds.h.

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

IAssert

#define IAssert(Cond)

Definition: bd.h:262

void Resize(const TSizeTy &_MxVals=-1)

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

Definition: ds.h:831

TSizeTy Vals

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

Definition: ds.h:425

template<class TVal, class TSizeTy = int>

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

inline

Returns the size of allocated storage capacity.

Definition at line 537 of file ds.h.

537 {return MxVals;}

TSizeTy MxVals

Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...

Definition: ds.h:424

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 831 of file ds.h.

                                                       {
   IAssertR(MxVals!=-1, 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());
   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: 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];}
     delete[] ValT; ValT=NewValT;
   }
 }

template<class TVal , class TSizeTy >

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

Reverses the order of the elements in the vector.

Definition at line 1250 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 666 of file ds.h.

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

TSizeTy Len() const

Returns the number of elements in the vector.

Definition: ds.h:535

TVec::Swap

void Swap(TVec< TVal, TSizeTy > &Vec)

Swaps the contents of the vector with Vec.

Definition: ds.h:1011

Assert

#define Assert(Cond)

Definition: bd.h:251

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Save ( TSOut & SOut ) const

Definition at line 885 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 1447 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 1418 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 1429 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 >::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 1440 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 1454 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 599 of file ds.h.

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

#define AssertR(Cond, Reason)

Definition: bd.h:258

TVec::GetXOutOfBoundsErrMsg

TSizeTy Vals

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

Definition: ds.h:425

TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const

Constructs the out of bounds error message.

Definition: ds.h:861

TVal * ValT

Definition: ds.h:426

template<class TVal , class TSizeTy >

void TVec< TVal, TSizeTy >::Shuffle ( TRnd & Rnd )

Randomly shuffles the elements of the vector.

Definition at line 1235 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 1218 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 713 of file ds.h.

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

TVec::EndI

TIter EndI() const

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

Definition: ds.h:552

TVec::BegI

TIter BegI() const

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

Definition: ds.h:550

TVec::QSortCmp

static void QSortCmp(TIter BI, TIter EI, const TCmp &Cmp)

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

Definition: ds.h:705

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 1011 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 618 of file ds.h.

618 { const TVal Val=ValT[ValN1]; ValT[ValN1]=ValT[ValN2]; ValT[ValN2]=Val;}