SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
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.

443 : MxVals(0), Vals(0), ValT(NULL), IsShM(false) {}
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
template<class TVal, class TSizeTy>
TVec< TVal, TSizeTy >::TVec ( const TVec< TVal, TSizeTy > &  Vec)

Definition at line 922 of file ds.h.

922  {
923  MxVals=Vec.MxVals;
924  Vals=Vec.Vals;
925  if (MxVals==0) {ValT=NULL;} else {ValT=new TVal[MxVals];}
926  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
927  IsShM = false;
928 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

446  {
447  IsShM = false;
448  IAssert(0<=_Vals); MxVals=Vals=_Vals;
449  if (_Vals==0){ValT=NULL;} else {ValT=new TVal[_Vals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

451  {
452  IsShM = false;
453  IAssert((0<=_Vals)&&(_Vals<=_MxVals)); MxVals=_MxVals; Vals=_Vals;
454  if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

459  :
460  MxVals(-1), Vals(_Vals), ValT(_ValT), IsShM(false){}
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::~TVec ( )
inline

Definition at line 461 of file ds.h.

461 {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:434
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( TSIn SIn)
inlineexplicit

Definition at line 462 of file ds.h.

462 : MxVals(0), Vals(0), ValT(NULL), IsShM(false) {Load(SIn);}
void Load(TSIn &SIn)
Definition: ds.h:946
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436

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.

602  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
603  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:434
#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:877
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

608  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
609  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:434
#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:877
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Add ( TVal &  Val)
inline

Definition at line 610 of file ds.h.

610  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
611  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:434
#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:877
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

613  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
614  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:434
#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:877
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::AddBackSorted ( const TVal &  Val,
const bool &  Asc 
)

Adds element Val to a sorted vector.

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

Definition at line 1133 of file ds.h.

1133  {
1134  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1135  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1136  Add();
1137  TSizeTy ValN=Vals-2;
1138  while ((ValN>=0)&&((Asc&&(Val<ValT[ValN]))||(!Asc&&(Val>ValT[ValN])))){
1139  ValT[ValN+1]=ValT[ValN]; ValN--;}
1140  ValT[ValN+1]=Val;
1141  return ValN+1;
1142 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1145  {
1146  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1147  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1148  TSizeTy ValN=SearchBin(Val);
1149  if (ValN==-1){return AddSorted(Val);}
1150  else {GetVal(ValN)=Val; return -1;}
1151 }
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
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.

617  { const int Idx = __sync_fetch_and_add(&Vals, 1);
618  ValT[Idx]=Val; return Idx;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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
AscAdds the element so that ascending (if true) or descending (if false) order is maintained.

Definition at line 1117 of file ds.h.

1117  {
1118  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1119  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1120  TSizeTy ValN=Add(Val);
1121  if (Asc){
1122  while ((ValN>0)&&(ValT[ValN]<ValT[ValN-1])){
1123  Swap(ValN, ValN-1); ValN--;}
1124  } else {
1125  while ((ValN>0)&&(ValT[ValN]>ValT[ValN-1])){
1126  Swap(ValN, ValN-1); ValN--;}
1127  }
1128  if ((_MxVals!=-1)&&(Len()>_MxVals)){Del(_MxVals, Len()-1);}
1129  return ValN;
1130 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1162  {
1163  AssertR(MxVals!=-1 || IsShM, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1164  TSizeTy ValN=SearchForw(Val);
1165  if (ValN==-1){return Add(Val);}
1166  else {GetVal(ValN)=Val; return -1;}
1167 }
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1552
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

1110  {
1111  AssertR(MxVals!=-1 || IsShM, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1112  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){Add(ValV[ValN]);}
1113  return Len();
1114 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

1154  {
1155  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1156  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1157  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){AddMerged(ValV[ValN]);}
1158  return Len();
1159 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy AddMerged(const TVal &Val)
Adds element Val to a sorted vector only if the element Val is not already in the vector...
Definition: ds.h:1145
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

593 {return ValT;}
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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
AscSorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1235 of file ds.h.

1235  {
1236  for (TSizeTy ValN1=MnLValN; ValN1<=MxRValN; ValN1++){
1237  for (TSizeTy ValN2=MxRValN; ValN2>ValN1; ValN2--){
1238  if (Asc){
1239  if (ValT[ValN2]<ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
1240  } else {
1241  if (ValT[ValN2]>ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
1242  }
1243  }
1244  }
1245 }
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

750  {
751  for (TIter i = BI; i != EI; ++i) {
752  for (TIter j = EI-1; j != i; --j) {
753  if (Cmp(*j, *(j-1))) { SwapI(j, j-1); } } } }
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:432
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
static void SwapI(TIter LVal, TIter RVal)
Swaps the elements that iterators LVal and RVal point to.
Definition: ds.h:677
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.

1022  {
1023  if ((DoDel)||((!DoDel)&&(NoDelLim!=-1)&&(MxVals>NoDelLim))){
1024  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
1025  MxVals=Vals=0; ValT=NULL;
1026  } else {
1027  IAssertR(MxVals!=-1 || IsShM, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1028  Vals=0;
1029  }
1030 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1082  {
1083  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1084  if (this!=&Vec){
1085  if (ValT!=NULL && MxVals!=-1 && MxVals < Sz){
1086  delete[] ValT;
1087  ValT=new TVal[Sz];
1088  }
1089  if (Sz == 0) { Vals = 0; return; }
1090  ValT[0] = Vec.ValT[Offset];
1091  Vals = 1;
1092  for (TSizeTy ValN=1; ValN<Sz; ValN++){
1093  if (ValT[Vals-1] != Vec.ValT[Offset+ValN]) {
1094  ValT[Vals++] = Vec.ValT[Offset+ValN];
1095  }
1096  }
1097  }
1098 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1511  {
1512  TSizeTy Count = 0;
1513  for (TSizeTy i = 0; i < Len(); i++){
1514  if (Val == ValT[i]){Count++;}}
1515  return Count;
1516 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy Count(const TVal &Val) const
Counts the number of occurrences of Val in the vector.
Definition: ds.h:1511
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1189  {
1190  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1191  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1192  Assert((0<=ValN)&&(ValN<Vals));
1193  for (TSizeTy MValN=ValN+1; MValN<Vals; MValN++){
1194  ValT[MValN-1]=ValT[MValN];}
1195  ValT[--Vals]=TVal();
1196 }
#define Assert(Cond)
Definition: bd.h:251
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1199  {
1200  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1201  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1202  Assert((0<=MnValN)&&(MnValN<Vals)&&(0<=MxValN)&&(MxValN<Vals));
1203  Assert(MnValN<=MxValN);
1204  for (TSizeTy ValN=MxValN+1; ValN<Vals; ValN++){
1205  ValT[MnValN+ValN-MxValN-1]=ValT[ValN];}
1206  for (TSizeTy ValN=Vals-MxValN+MnValN-1; ValN<Vals; ValN++){
1207  ValT[ValN]=TVal();}
1208  Vals-=MxValN-MnValN+1;
1209 }
#define Assert(Cond)
Definition: bd.h:251
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1221  {
1222  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1223  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1224  TSizeTy ValN;
1225  while ((ValN=SearchForw(Val))!=-1){Del(ValN);}
1226 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1552
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
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.

1212  {
1213  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1214  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1215  TSizeTy ValN=SearchForw(Val);
1216  if (ValN!=-1){Del(ValN); return true;}
1217  else {return false;}
1218 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1552
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
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.

665 {Del(Len()-1);}
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
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.

1425  {
1426  TVec<TVal, TSizeTy> DiffVec;
1427  Diff(ValV, DiffVec);
1428  MoveFrom(DiffVec);
1429 }
void Diff(const TVec< TVal, TSizeTy > &ValV)
Subtracts ValV from this vector. Assumes the vectors are sorted!
Definition: ds.h:1425
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1073
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
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.

1463  {
1464  DstValV.Clr();
1465  TSizeTy ValN1=0, ValN2=0;
1466  while (ValN1<Len() && ValN2<ValV.Len()) {
1467  const TVal& Val1 = GetVal(ValN1);
1468  while (ValN2<ValV.Len() && Val1>ValV.GetVal(ValN2)) ValN2++;
1469  if (ValN2<ValV.Len()) {
1470  if (Val1!=ValV.GetVal(ValN2)) { DstValV.Add(Val1); }
1471  ValN1++;
1472  }
1473  }
1474  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
1475  DstValV.Add(GetVal(RestValN1));}
1476 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

570 {return Vals==0;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

595 {return ValT+Vals;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

523  { IAssert(0<=_Vals);
524  if (ValT!=NULL && MxVals!=-1){delete[] ValT;} MxVals=Vals=_Vals;
525  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

527  { IAssert((0<=_Vals)&&(_Vals<=_MxVals));
528  if (ValT!=NULL && MxVals!=-1){delete[] ValT;} MxVals=_MxVals; Vals=_Vals;
529  if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

534  {
535  if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
536  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:434
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

842  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
843  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:649
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1552
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

838 { 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:649
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1552
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.

597 {return ValT+ValN;}
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

514  {
515  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:435
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.

511  {
512  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:434
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.

1579  {
1580  if (Vals==0){return -1;}
1581  TSizeTy MxValN=0;
1582  for (TSizeTy ValN=1; ValN<Vals; ValN++){
1583  if (ValT[ValN]>ValT[MxValN]){MxValN=ValN;}
1584  }
1585  return MxValN;
1586 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1265  {
1266  TSizeTy SubVals=RValN-LValN+1;
1267  if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
1268  const TSizeTy ValN1=LValN+TInt::GetRnd(int(SubVals));
1269  const TSizeTy ValN2=LValN+TInt::GetRnd(int(SubVals));
1270  const TSizeTy ValN3=LValN+TInt::GetRnd(int(SubVals));
1271  const TVal& Val1=ValT[ValN1];
1272  const TVal& Val2=ValT[ValN2];
1273  const TVal& Val3=ValT[ValN3];
1274  if (Val1<Val2){
1275  if (Val2<Val3){return ValN2;}
1276  else if (Val3<Val1){return ValN1;}
1277  else {return ValN3;}
1278  } else {
1279  if (Val1<Val3){return ValN1;}
1280  else if (Val3<Val2){return ValN2;}
1281  else {return ValN3;}
1282  }
1283 }
static const int Mx
Definition: dt.h:1142
static int GetRnd(const int &Range=0)
Definition: dt.h:1178
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

729  {
730  TSizeTy SubVals=TSizeTy(EI-BI); if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
731  const TSizeTy ValN1=TInt::GetRnd(SubVals), ValN2=TInt::GetRnd(SubVals), ValN3=TInt::GetRnd(SubVals);
732  const TVal& Val1 = *(BI+ValN1); const TVal& Val2 = *(BI+ValN2); const TVal& Val3 = *(BI+ValN3);
733  if (Cmp(Val1, Val2)) {
734  if (Cmp(Val2, Val3)) return BI+ValN2;
735  else if (Cmp(Val3, Val1)) return BI+ValN1;
736  else return BI+ValN3;
737  } else {
738  if (Cmp(Val1, Val3)) return BI+ValN1;
739  else if (Cmp(Val3, Val2)) return BI+ValN2;
740  else return BI+ValN3; } }
static const int Mx
Definition: dt.h:1142
static int GetRnd(const int &Range=0)
Definition: dt.h:1178
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
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.

999  {
1000  int hc = 0;
1001  for (TSizeTy i=0; i<Vals; i++){
1003  }
1004  return hc;
1005 }
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:999
static int GetHashCd(const int hc1, const int hc2)
Definition: bd.h:590
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

589 { return GetVal(Rnd.GetUniDevInt(Len())); }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
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.

591 { return GetVal(Rnd.GetUniDevInt(Len())); }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
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.

1011  {
1012  int hc = 0;
1013  for (TSizeTy i=0; i<Vals; i++){
1015  }
1016  if (Vals > 0) {
1017  hc = TPairHashImpl::GetHashCd(hc, ValT[0].GetSecHashCd()); }
1018  return hc;
1019 }
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:1011
static int GetHashCd(const int hc1, const int hc2)
Definition: bd.h:590
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1170  {
1171  const TSizeTy BValN=TInt::GetInRng(_BValN, 0, Len()-1);
1172  const TSizeTy EValN=TInt::GetInRng(_EValN, 0, Len()-1);
1173  const TSizeTy SubVals=TInt::GetMx(0, EValN-BValN+1);
1174  SubValV.Gen(SubVals, 0);
1175  for (TSizeTy ValN=BValN; ValN<=EValN; ValN++){
1176  SubValV.Add(GetVal(ValN));}
1177 }
static int GetInRng(const int &Val, const int &Mn, const int &Mx)
Definition: dt.h:1197
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1185
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
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.

848  {
849  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:430
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.

851  {
852  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:430
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.

854  {
855  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:430
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.

857  {
858  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:430
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.

860  {
861  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:430
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.

863  {
864  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:430
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.

866  {
867  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:430
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.

869  {
870  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:430
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.

872  {
873  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:430
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.

649 {return operator[](ValN);}
const TVal & operator[](const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:503
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.

651 {return operator[](ValN);}
const TVal & operator[](const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:503
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.

913  {
914  return TStr()+
915  "Index:"+TInt::GetStr(ValN)+
916  " Vals:"+TInt::GetStr(Vals)+
917  " MxVals:"+TInt::GetStr(MxVals)+
918  " Type:"+GetTypeNm(*this);
919 }
TStr GetTypeNm(const Type &Var)
Definition: ut.h:16
TStr GetStr() const
Definition: dt.h:1200
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
Definition: dt.h:412
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

1180  {
1181  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1182  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1183  Add(); Assert((0<=ValN)&&(ValN<Vals));
1184  for (TSizeTy MValN=Vals-2; MValN>=ValN; MValN--){ValT[MValN+1]=ValT[MValN];}
1185  ValT[ValN]=Val;
1186 }
#define Assert(Cond)
Definition: bd.h:251
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1411  {
1412  TVec<TVal, TSizeTy> IntrsVec;
1413  Intrs(ValV, IntrsVec);
1414  MoveFrom(IntrsVec);
1415 }
void Intrs(const TVec< TVal, TSizeTy > &ValV)
Sets this vector to its intersection with ValV. Assumes the vectors are sorted!
Definition: ds.h:1411
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1073
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
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.

1432  {
1433  DstValV.Clr();
1434  TSizeTy ValN1=0, ValN2=0;
1435  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1436  const TVal& Val1=GetVal(ValN1);
1437  while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
1438  ValN2++;}
1439  if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
1440  DstValV.Add(Val1); ValN2++;}
1441  ValN1++;
1442  }
1443 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

1479  {
1480  TSizeTy Cnt=0, ValN1=0, ValN2=0;
1481  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1482  const TVal& Val1=GetVal(ValN1);
1483  while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
1484  ValN2++;}
1485  if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
1486  ValN2++; Cnt++;}
1487  ValN1++;
1488  }
1489  return Cnt;
1490 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
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.

541 {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:434
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.

828 {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:1552
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.

832 { 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:1552
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.

836 {return SearchBin(Val)!=-1;}
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1519
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
AscSorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1248 of file ds.h.

1248  {
1249  if (MnLValN<MxRValN){
1250  for (TSizeTy ValN1=MnLValN+1; ValN1<=MxRValN; ValN1++){
1251  TVal Val=ValT[ValN1]; TSizeTy ValN2=ValN1;
1252  if (Asc){
1253  while ((ValN2>MnLValN)&&(ValT[ValN2-1]>Val)){
1254  ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
1255  } else {
1256  while ((ValN2>MnLValN)&&(ValT[ValN2-1]<Val)){
1257  ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
1258  }
1259  ValT[ValN2]=Val;
1260  }
1261  }
1262 }
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

756  {
757  if (BI + 1 < EI) {
758  for (TIter i = BI, j; i != EI; ++i) { TVal Tmp=*i; j=i;
759  while (j > BI && Cmp(Tmp, *(j-1))) { *j = *(j-1); --j; } *j=Tmp; } } }
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:432
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
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.

1323  {
1324  if (Asc){
1325  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1326  if (ValT[ValN]>ValT[ValN+1]){return false;}}
1327  } else {
1328  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1329  if (ValT[ValN]<ValT[ValN+1]){return false;}}
1330  }
1331  return true;
1332 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

773  {
774  if (EndI() == BegI()) return true;
775  for (TIter i = BegI(); i != EndI()-1; ++i) {
776  if (Cmp(*(i+1), *i)){return false;} } return true; }
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:432
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
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.

579 {return GetVal(Len()-1);}
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
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.

581 {return GetVal(Len()-1);}
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
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.

585 { AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:913
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

587 { AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:913
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

583 {return Len()-1;}
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
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.

575 {return Vals;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Load ( TSIn SIn)

Definition at line 946 of file ds.h.

946  {
947  if ( (ValT!=NULL) && (MxVals!=-1)) {delete[] ValT;}
948  SIn.Load(MxVals); SIn.Load(Vals); MxVals=Vals;
949  if ( MxVals==0 ){ValT=NULL;} else {ValT=new TVal[MxVals];}
950  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=TVal(SIn);}
951 }
void Load(bool &Bool)
Definition: fl.h:84
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

932  {
933  if ((ValT!=NULL) && (MxVals!=-1)) {delete[] ValT;}
934  ShMIn.Load(MxVals);
935  MxVals = -1;
936  ShMIn.Load(Vals);
937  if (MxVals == 0) {
938  ValT = NULL;
939  } else {
940  ValT = (TVal*)(ShMIn.AdvanceCursor(Vals*sizeof(TVal)));
941  IsShM = true;
942  }
943 }
char * AdvanceCursor(TSize N)
Return the current pointer and advance the cursor.
Definition: fl.h:425
void Load(bool &Bool)
Definition: fl.h:84
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

472  {
473  if ((ValT!=NULL) && (MxVals!=-1)) {delete[] ValT;}
474  ShMIn.Load(MxVals);
475  ShMIn.Load(Vals);
476  if (MxVals == 0) {
477  ValT = NULL;
478  } else {
479  ValT=new TVal[MxVals];
480  for (TSizeTy ValN=0; ValN<Vals; ValN++) {
481  LoadFromShMFn(ValT+ValN, ShMIn);
482  }
483  }
484  IsShM = false;
485  }
void Load(bool &Bool)
Definition: fl.h:84
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::LoadXml ( const PXmlTok XmlTok,
const TStr Nm = "" 
)

Definition at line 103 of file xmlser.h.

103  {
104  XLoadHd(Nm);
105  TSizeTy SubToks=XmlTok->GetSubToks(); Gen(SubToks, 0);
106  for (TSizeTy SubTokN=0; SubTokN<SubToks; SubTokN++){
107  PXmlTok SubTok=XmlTok->GetSubTok(SubTokN);
108  TVal Val; Val.LoadXml(SubTok, TStr()); Add(Val);
109  }
110 }
#define XLoadHd(Nm)
Definition: bd.h:312
Definition: dt.h:412
Definition: bd.h:196
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
void LoadXml(const TPt< TXmlTok > &XmlTok, const TStr &Nm)
Definition: xmlser.h:21
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.

1356  {
1357  IAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1358  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1359  TVec<TVal, TSizeTy> SortedVec(*this); SortedVec.Sort();
1360  Clr();
1361  for (TSizeTy ValN=0; ValN<SortedVec.Len(); ValN++){
1362  if ((ValN==0)||(SortedVec[ValN-1]!=SortedVec[ValN])){
1363  Add(SortedVec[ValN]);}
1364  }
1365 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
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.

1073  {
1074  if (this!=&Vec){
1075  if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
1076  MxVals=Vec.MxVals; Vals=Vec.Vals; ValT=Vec.ValT;
1077  Vec.MxVals=0; Vec.Vals=0; Vec.ValT=NULL;
1078  }
1079 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

622  { const int Idx = __sync_fetch_and_add(&Vals, Inc);
623  return Idx;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

1368  {
1369  // start with a sorted sequence to obtain all permutations
1370  TSizeTy First = 0, Last = Len(), Next = Len()-1;
1371  if (Last < 2) return false;
1372  for(; ; ) {
1373  // find rightmost element smaller than successor
1374  TSizeTy Next1 = Next;
1375  if (GetVal(--Next) < GetVal(Next1)) { // swap with rightmost element that's smaller, flip suffix
1376  TSizeTy Mid = Last;
1377  for (; GetVal(Next) >= GetVal(--Mid); ) { }
1378  Swap(Next, Mid);
1379  Reverse(Next1, Last-1);
1380  return true;
1381  }
1382  if (Next == First) { // pure descending, flip all
1383  Reverse();
1384  return false;
1385  }
1386  }
1387 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1350
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.

495 {Add(Val); return *this;}
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

981  {
982  if (this==&Vec){return false;}
983  if (Len()==Vec.Len()){
984  for (TSizeTy ValN=0; ValN<Vals; ValN++){
985  if (ValT[ValN]<Vec.ValT[ValN]){return true;}
986  else if (ValT[ValN]>Vec.ValT[ValN]){return false;}
987  else {}
988  }
989  return false;
990  } else {
991  return Len()<Vec.Len();
992  }
993 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

961  {
962  if (this!=&Vec){
963  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
964  MxVals=Vals=Vec.Vals;
965  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
966  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
967  }
968  return *this;
969 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

972  {
973  if (this==&Vec){return true;}
974  if (Len()!=Vec.Len()){return false;}
975  for (TSizeTy ValN=0; ValN<Vals; ValN++){
976  if (ValT[ValN]!=Vec.ValT[ValN]){return false;}}
977  return true;
978 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

503  {
504  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
505  return ValT[ValN];}
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:913
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

507  {
508  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
509  return ValT[ValN];}
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:913
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1057  {
1058  EAssertR(!(IsShM && (MxVals == -1)), "Cannot pack accessed shared memory");
1059  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1060  if (Vals==0){
1061  if (ValT!=NULL){delete[] ValT;} ValT=NULL;
1062  } else
1063  if (Vals<MxVals){
1064  MxVals=Vals;
1065  TVal* NewValT=new TVal[MxVals];
1066  IAssert(NewValT!=NULL);
1067  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
1068  delete[] ValT; ValT=NewValT;
1069  }
1070 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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
AscSorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1286 of file ds.h.

1286  {
1287  TSizeTy PivotValN=GetPivotValN(MnLValN, MxRValN);
1288  Swap(PivotValN, MnLValN);
1289  TVal PivotVal=ValT[MnLValN];
1290  TSizeTy LValN=MnLValN-1; TSizeTy RValN=MxRValN+1;
1291  forever {
1292  if (Asc){
1293  do {RValN--;} while (ValT[RValN]>PivotVal);
1294  do {LValN++;} while (ValT[LValN]<PivotVal);
1295  } else {
1296  do {RValN--;} while (ValT[RValN]<PivotVal);
1297  do {LValN++;} while (ValT[LValN]>PivotVal);
1298  }
1299  if (LValN<RValN){Swap(LValN, RValN);}
1300  else {return RValN;}
1301  };
1302 }
#define forever
Definition: bd.h:6
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TSizeTy GetPivotValN(const TSizeTy &LValN, const TSizeTy &RValN) const
Picks three random elements at positions LValN...RValN and returns the middle one.
Definition: ds.h:1265
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

743  {
744  forever {
745  while (Cmp(*BI, Pivot)){++BI;} --EI;
746  while (Cmp(Pivot, *EI)){--EI;}
747  if (!(BI<EI)){return BI;} SwapI(BI, EI); ++BI; } }
#define forever
Definition: bd.h:6
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
static void SwapI(TIter LVal, TIter RVal)
Swaps the elements that iterators LVal and RVal point to.
Definition: ds.h:677
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.

1390  {
1391  TSizeTy First = 0, Last = Len(), Next = Len()-1;
1392  if (Last < 2) return false;
1393  for(; ; ) {
1394  // find rightmost element not smaller than successor
1395  TSizeTy Next1 = Next;
1396  if (GetVal(--Next) >= GetVal(Next1)) { // swap with rightmost element that's not smaller, flip suffix
1397  TSizeTy Mid = Last;
1398  for (; GetVal(Next) < GetVal(--Mid); ) { }
1399  Swap(Next, Mid);
1400  Reverse(Next1, Last);
1401  return true;
1402  }
1403  if (Next == First) { // pure descending, flip all
1404  Reverse();
1405  return false;
1406  }
1407  }
1408 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:579
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1350
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.

1229  {
1230  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
1231  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=Val;}
1232 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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
AscSorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1305 of file ds.h.

1305  {
1306  if (MnLValN<MxRValN){
1307  if (MxRValN-MnLValN<20){
1308  ISort(MnLValN, MxRValN, Asc);
1309  } else {
1310  TSizeTy SplitValN=Partition(MnLValN, MxRValN, Asc);
1311  QSort(MnLValN, SplitValN, Asc);
1312  QSort(SplitValN+1, MxRValN, Asc);
1313  }
1314  }
1315 }
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1305
void ISort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Insertion sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1248
TSizeTy Partition(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Partitions the values between positions MnLValN...MxLValN.
Definition: ds.h:1286
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.

762  {
763  if (BI + 1 < EI) {
764  if (EI - BI < 20) { ISortCmp(BI, EI, Cmp); }
765  else { const TVal Val = *GetPivotValNCmp(BI, EI, Cmp);
766  TIter Split = PartitionCmp(BI, EI, Val, Cmp);
767  QSortCmp(BI, Split, Cmp); QSortCmp(Split, EI, Cmp); } } }
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...
Definition: ds.h:729
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:432
static TIter PartitionCmp(TIter BI, TIter EI, const TVal Pivot, const TCmp &Cmp)
Partitions the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:743
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:762
static void ISortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Insertion sorts the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:756
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.

556 {Vals = _Vals;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

543 {Resize(_MxVals);}
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:877
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.

545 { IAssert((0<=_Vals)&&(_Vals<=_MxVals)); Resize(_MxVals); Vals=_Vals;}
#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:877
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

577 {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:434
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.

877  {
878  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());
879  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());
880  TSizeTy OldMxVals = MxVals;
881  if (MxVals == -1) {MxVals = Vals;}
882  if (_MxVals==-1){
883  if (Vals==0){MxVals=16;} else {MxVals*=2;}
884  } else {
885  if (_MxVals<=MxVals){return;} else {MxVals=_MxVals;}
886  }
887  if (MxVals < 0) {
888  MxVals = TInt::Mx-1024;
889  }
890  if (ValT==NULL){
891  try {
892  ValT=new TVal[MxVals];
893  }
894  catch (std::exception Ex){
895  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.]",
896  Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
897  } else {
898  TVal* NewValT = NULL;
899  try {
900  NewValT=new TVal[MxVals];
901  }
902  catch (std::exception Ex){
903  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.]",
904  Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
905  IAssert(NewValT!=NULL);
906  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
907  if (OldMxVals != -1) {delete[] ValT;} ValT=NewValT;
908  }
909  IsShM = false;
910 }
#define IAssert(Cond)
Definition: bd.h:262
TStr GetTypeNm(const Type &Var)
Definition: ut.h:16
TStr GetStr() const
Definition: dt.h:1200
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const int Mx
Definition: dt.h:1142
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define FailR(Reason)
Definition: bd.h:240
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsShM
Definition: ds.h:437
char * CStr()
Definition: dt.h:479
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1350  {
1351  for (TSizeTy ValN=0; ValN<Vals/2; ValN++){
1352  Swap(ValN, Vals-ValN-1);}
1353 }
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

723 { 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:575
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
#define Assert(Cond)
Definition: bd.h:251
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Save ( TSOut SOut) const

Definition at line 954 of file ds.h.

954  {
955  if (MxVals!=-1){SOut.Save(MxVals);} else {SOut.Save(Vals);}
956  SOut.Save(Vals);
957  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].Save(SOut);}
958 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
void Save(const bool &Bool)
Definition: fl.h:173
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::SaveXml ( TSOut SOut,
const TStr Nm 
) const

Definition at line 113 of file xmlser.h.

113  {
114  XSaveHdArg(Nm, "Vals", TInt::GetStr(Vals));
115  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].SaveXml(SOut, TStr());}
116 }
TStr GetStr() const
Definition: dt.h:1200
#define XSaveHdArg(Nm, ArgNm, ArgVal)
Definition: bd.h:321
Definition: dt.h:412
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1559  {
1560  for (TSizeTy ValN=Vals-1; ValN>=0; ValN--){
1561  if (Val==ValT[ValN]){return ValN;}}
1562  return -1;
1563 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1519  {
1520  TSizeTy LValN=0, RValN=Len()-1;
1521  while (RValN>=LValN){
1522  TSizeTy ValN=(LValN+RValN)/2;
1523  if (Val==ValT[ValN]){return ValN;}
1524  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1525  }
1526  return -1;
1527 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1530  {
1531  TSizeTy LValN=0, RValN=Len()-1;
1532  while (RValN>=LValN){
1533  TSizeTy ValN=(LValN+RValN)/2;
1534  if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
1535  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1536  }
1537  InsValN=LValN; return -1;
1538 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1541  {
1542  TSizeTy LValN=0, RValN=Len()-1;
1543  while (RValN>=LValN){
1544  TSizeTy ValN=(LValN+RValN)/2;
1545  if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
1546  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1547  }
1548  InsValN=RValN; return -1;
1549 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1552  {
1553  for (TSizeTy ValN=BValN; ValN<Vals; ValN++){
1554  if (Val==ValT[ValN]){return ValN;}}
1555  return -1;
1556 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1566  {
1567  TSizeTy ValVLen=ValV.Len();
1568  for (TSizeTy ValN=BValN; ValN<Vals-ValVLen+1; ValN++){
1569  bool Found=true;
1570  for (TSizeTy SubValN=0; SubValN<ValVLen; SubValN++){
1571  if (ValV[SubValN]!=GetVal(ValN+SubValN)){Found=false; break;}
1572  }
1573  if (Found){return ValN;}
1574  }
1575  return -1;
1576 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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.

653  {
654  EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
655  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN)); ValT[ValN] = Val;}
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:913
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1335  {
1336  if (Len() < TInt::Mx) {
1337  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1338  const int Range = int(Vals-ValN);
1339  Swap(ValN, ValN+Rnd.GetUniDevInt(Range));
1340  }
1341  } else {
1342  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1343  const TSizeTy Range = Vals-ValN;
1344  Swap(ValN, TSizeTy(ValN+Rnd.GetUniDevInt64(Range)));
1345  }
1346  }
1347 }
int64 GetUniDevInt64(const int64 &Range=0)
Definition: dt.cpp:51
static const int Mx
Definition: dt.h:1142
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
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
AscSorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1318 of file ds.h.

1318  {
1319  QSort(0, Len()-1, Asc);
1320 }
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1305
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
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.

770 { QSortCmp(BegI(), EndI(), Cmp);}
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
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:762
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.

1101  {
1102  if (this!=&Vec){
1103  ::Swap(MxVals, Vec.MxVals);
1104  ::Swap(Vals, Vec.Vals);
1105  ::Swap(ValT, Vec.ValT);
1106  }
1107 }
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

674  {EAssertR(!(IsShM && (MxVals == -1)), "Cannot write to shared memory");
675  const TVal Val=ValT[ValN1]; ValT[ValN1]=ValT[ValN2]; ValT[ValN2]=Val;}
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

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

1033  {
1034  EAssertR(!(MxVals==-1 && IsShM), "Cannot truncate a shared memory vector");
1035  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1036  IAssert((_Vals==-1)||(_Vals>=0));
1037  if ((_Vals!=-1)&&(_Vals>=Vals)){
1038  return;
1039  } else
1040  if (((_Vals==-1)&&(Vals==0))||(_Vals==0)){
1041  if (ValT!=NULL){delete[] ValT;}
1042  MxVals=Vals=0; ValT=NULL;
1043  } else {
1044  if (_Vals==-1){
1045  if (MxVals==Vals){return;} else {MxVals=Vals;}
1046  } else {
1047  MxVals=Vals=_Vals;
1048  }
1049  TVal* NewValT=new TVal[MxVals];
1050  IAssert(NewValT!=NULL);
1051  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
1052  delete[] ValT; ValT=NewValT;
1053  }
1054 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:434
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsShM
Definition: ds.h:437
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:435
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
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.

1418  {
1419  TVec<TVal, TSizeTy> UnionVec;
1420  Union(ValV, UnionVec);
1421  MoveFrom(UnionVec);
1422 }
void Union(const TVec< TVal, TSizeTy > &ValV)
Sets this vector to its union with ValV. Assumes the vectors are sorted!
Definition: ds.h:1418
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1073
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
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.

1446  {
1447  DstValV.Gen(TInt::GetMx(Len(), ValV.Len()), 0);
1448  TSizeTy ValN1=0, ValN2=0;
1449  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1450  const TVal& Val1=GetVal(ValN1);
1451  const TVal& Val2=ValV.GetVal(ValN2);
1452  if (Val1<Val2){DstValV.Add(Val1); ValN1++;}
1453  else if (Val1>Val2){DstValV.Add(Val2); ValN2++;}
1454  else {DstValV.Add(Val1); ValN1++; ValN2++;}
1455  }
1456  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
1457  DstValV.Add(GetVal(RestValN1));}
1458  for (TSizeTy RestValN2=ValN2; RestValN2<ValV.Len(); RestValN2++){
1459  DstValV.Add(ValV.GetVal(RestValN2));}
1460 }
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1185
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
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.

1493  {
1494  TSizeTy Cnt = 0, ValN1 = 0, ValN2 = 0;
1495  while ((ValN1 < Len()) && (ValN2 < ValV.Len())) {
1496  const TVal& Val1 = GetVal(ValN1);
1497  const TVal& Val2 = ValV.GetVal(ValN2);
1498  if (Val1 < Val2) {
1499  Cnt++; ValN1++;
1500  } else if (Val1 > Val2) {
1501  Cnt++; ValN2++;
1502  } else {
1503  Cnt++; ValN1++; ValN2++;
1504  }
1505  }
1506  Cnt += (Len() - ValN1) + (ValV.Len() - ValN2);
1507  return Cnt;
1508 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:649

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: