SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
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 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
 

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

Constructor & Destructor Documentation

template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( )
inline

Definition at line 441 of file ds.h.

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

Definition at line 888 of file ds.h.

888  {
889  MxVals=Vec.MxVals; Vals=Vec.Vals;
890  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
891  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
892 }
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 444 of file ds.h.

444  {
445  IAssert(0<=_Vals); MxVals=Vals=_Vals;
446  if (_Vals==0){ValT=NULL;} else {ValT=new TVal[_Vals];}}
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 448 of file ds.h.

448  {
449  IAssert((0<=_Vals)&&(_Vals<=_MxVals)); MxVals=_MxVals; Vals=_Vals;
450  if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 455 of file ds.h.

455  :
456  MxVals(-1), Vals(_Vals), ValT(_ValT){}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::~TVec ( )
inline

Definition at line 457 of file ds.h.

457 {if ((ValT!=NULL) && (MxVals!=-1)){delete[] ValT;}}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( TSIn &  SIn)
inlineexplicit

Definition at line 458 of file ds.h.

458 : MxVals(0), Vals(0), ValT(NULL){Load(SIn);}
TVec::Load
void Load(TSIn &SIn)
Definition: ds.h:895
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435

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

574  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
575  if (Vals==MxVals){Resize();} return Vals++;}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Resize
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:846
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
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 580 of file ds.h.

580  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
581  if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Resize
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:846
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Add ( TVal &  Val)
inline

Definition at line 582 of file ds.h.

582  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
583  if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Resize
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:846
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 585 of file ds.h.

585  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
586  if (Vals==MxVals){Resize(MxVals+ResizeLen);} ValT[Vals]=Val; return Vals++;}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Resize
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:846
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1078 of file ds.h.

1078  {
1079  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1080  Add();
1081  TSizeTy ValN=Vals-2;
1082  while ((ValN>=0)&&((Asc&&(Val<ValT[ValN]))||(!Asc&&(Val>ValT[ValN])))){
1083  ValT[ValN+1]=ValT[ValN]; ValN--;}
1084  ValT[ValN+1]=Val;
1085  return ValN+1;
1086 }
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1089 of file ds.h.

1089  {
1090  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1091  TSizeTy ValN=SearchBin(Val);
1092  if (ValN==-1){return AddSorted(Val);}
1093  else {GetVal(ValN)=Val; return -1;}
1094 }
TVec::AddSorted
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1063
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::SearchBin
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1454
AssertR
#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 589 of file ds.h.

589  { const int Idx = __sync_fetch_and_add(&Vals, 1);
590  ValT[Idx]=Val; return Idx;}
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1063 of file ds.h.

1063  {
1064  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1065  TSizeTy ValN=Add(Val);
1066  if (Asc){
1067  while ((ValN>0)&&(ValT[ValN]<ValT[ValN-1])){
1068  Swap(ValN, ValN-1); ValN--;}
1069  } else {
1070  while ((ValN>0)&&(ValT[ValN]>ValT[ValN-1])){
1071  Swap(ValN, ValN-1); ValN--;}
1072  }
1073  if ((_MxVals!=-1)&&(Len()>_MxVals)){Del(_MxVals, Len()-1);}
1074  return ValN;
1075 }
TVec::Del
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1130
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1104 of file ds.h.

1104  {
1105  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1106  TSizeTy ValN=SearchForw(Val);
1107  if (ValN==-1){return Add(Val);}
1108  else {GetVal(ValN)=Val; return -1;}
1109 }
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::SearchForw
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1487
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
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 1056 of file ds.h.

1056  {
1057  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1058  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){Add(ValV[ValN]);}
1059  return Len();
1060 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
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 1097 of file ds.h.

1097  {
1098  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1099  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){AddMerged(ValV[ValN]);}
1100  return Len();
1101 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::AddMerged
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:1089
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
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 565 of file ds.h.

565 {return ValT;}
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1171 of file ds.h.

1171  {
1172  for (TSizeTy ValN1=MnLValN; ValN1<=MxRValN; ValN1++){
1173  for (TSizeTy ValN2=MxRValN; ValN2>ValN1; ValN2--){
1174  if (Asc){
1175  if (ValT[ValN2]<ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
1176  } else {
1177  if (ValT[ValN2]>ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
1178  }
1179  }
1180  }
1181 }
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 719 of file ds.h.

719  {
720  for (TIter i = BI; i != EI; ++i) {
721  for (TIter j = EI-1; j != i; --j) {
722  if (Cmp(*j, *(j-1))) { SwapI(j, j-1); } } } }
TVec::TIter
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:431
Cmp
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
TVec::SwapI
static void SwapI(TIter LVal, TIter RVal)
Swaps the elements that iterators LVal and RVal point to.
Definition: ds.h:646
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 971 of file ds.h.

971  {
972  if ((DoDel)||((!DoDel)&&(NoDelLim!=-1)&&(MxVals>NoDelLim))){
973  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
974  MxVals=Vals=0; ValT=NULL;
975  } else {
976  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
977  Vals=0;
978  }
979 }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1029 of file ds.h.

1029  {
1030  if (this!=&Vec){
1031  if (ValT!=NULL && MxVals!=-1 && MxVals < Sz){
1032  delete[] ValT;
1033  ValT=new TVal[Sz];
1034  }
1035  if (Sz == 0) { Vals = 0; return; }
1036  ValT[0] = Vec.ValT[Offset];
1037  Vals = 1;
1038  for (TSizeTy ValN=1; ValN<Sz; ValN++){
1039  if (ValT[Vals-1] != Vec.ValT[Offset+ValN]) {
1040  ValT[Vals++] = Vec.ValT[Offset+ValN];
1041  }
1042  }
1043  }
1044 }
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1446 of file ds.h.

1446  {
1447  TSizeTy Count = 0;
1448  for (TSizeTy i = 0; i < Len(); i++){
1449  if (Val == ValT[i]){Count++;}}
1450  return Count;
1451 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Count
TSizeTy Count(const TVal &Val) const
Counts the number of occurrences of Val in the vector.
Definition: ds.h:1446
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Del ( const TSizeTy &  ValN)

Removes the element at position ValN.

Definition at line 1130 of file ds.h.

1130  {
1131  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1132  Assert((0<=ValN)&&(ValN<Vals));
1133  for (TSizeTy MValN=ValN+1; MValN<Vals; MValN++){
1134  ValT[MValN-1]=ValT[MValN];}
1135  ValT[--Vals]=TVal();
1136 }
Assert
#define Assert(Cond)
Definition: bd.h:251
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1139 of file ds.h.

1139  {
1140  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1141  Assert((0<=MnValN)&&(MnValN<Vals)&&(0<=MxValN)&&(MxValN<Vals));
1142  Assert(MnValN<=MxValN);
1143  for (TSizeTy ValN=MxValN+1; ValN<Vals; ValN++){
1144  ValT[MnValN+ValN-MxValN-1]=ValT[ValN];}
1145  for (TSizeTy ValN=Vals-MxValN+MnValN-1; ValN<Vals; ValN++){
1146  ValT[ValN]=TVal();}
1147  Vals-=MxValN-MnValN+1;
1148 }
Assert
#define Assert(Cond)
Definition: bd.h:251
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal, class TSizeTy >
void TVec< TVal, TSizeTy >::DelAll ( const TVal &  Val)

Removes all occurrences of element Val.

Definition at line 1159 of file ds.h.

1159  {
1160  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1161  TSizeTy ValN;
1162  while ((ValN=SearchForw(Val))!=-1){Del(ValN);}
1163 }
TVec::Del
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1130
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::SearchForw
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1487
AssertR
#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 1151 of file ds.h.

1151  {
1152  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1153  TSizeTy ValN=SearchForw(Val);
1154  if (ValN!=-1){Del(ValN); return true;}
1155  else {return false;}
1156 }
TVec::Del
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1130
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::SearchForw
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1487
AssertR
#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 635 of file ds.h.

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

1360  {
1361  TVec<TVal, TSizeTy> DiffVec;
1362  Diff(ValV, DiffVec);
1363  MoveFrom(DiffVec);
1364 }
TVec::Diff
void Diff(const TVec< TVal, TSizeTy > &ValV)
Subtracts ValV from this vector. Assumes the vectors are sorted!
Definition: ds.h:1360
TVec::MoveFrom
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1020
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 1398 of file ds.h.

1398  {
1399  DstValV.Clr();
1400  TSizeTy ValN1=0, ValN2=0;
1401  while (ValN1<Len() && ValN2<ValV.Len()) {
1402  const TVal& Val1 = GetVal(ValN1);
1403  while (ValN2<ValV.Len() && Val1>ValV.GetVal(ValN2)) ValN2++;
1404  if (ValN2<ValV.Len()) {
1405  if (Val1!=ValV.GetVal(ValN2)) { DstValV.Add(Val1); }
1406  ValN1++;
1407  }
1408  }
1409  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
1410  DstValV.Add(GetVal(RestValN1));}
1411 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
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 542 of file ds.h.

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

567 {return ValT+Vals;}
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 495 of file ds.h.

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

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

506  {
507  if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
508  MxVals=-1; Vals=_Vals; ValT=_ValT;}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 811 of file ds.h.

811  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
812  const TSizeTy ValN=SearchForw(Val); if (ValN==-1){Add(Val); return Last();} else {return GetVal(ValN);}}
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::SearchForw
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1487
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
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 807 of file ds.h.

807 { return GetVal(SearchForw(Val));}
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::SearchForw
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1487
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 569 of file ds.h.

569 {return ValT+ValN;}
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 486 of file ds.h.

486  {
487  return TSizeTy(2*sizeof(TVal)+sizeof(TSizeTy)*Vals);}
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
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 483 of file ds.h.

483  {
484  return TSizeTy(2*sizeof(TSizeTy)+sizeof(TVal*)+MxVals*sizeof(TVal));}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
template<class TVal , class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::GetMxValN ( ) const

Returns the position of the largest element in the vector.

Definition at line 1514 of file ds.h.

1514  {
1515  if (Vals==0){return -1;}
1516  TSizeTy MxValN=0;
1517  for (TSizeTy ValN=1; ValN<Vals; ValN++){
1518  if (ValT[ValN]>ValT[MxValN]){MxValN=ValN;}
1519  }
1520  return MxValN;
1521 }
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1201 of file ds.h.

1201  {
1202  TSizeTy SubVals=RValN-LValN+1;
1203  if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
1204  const TSizeTy ValN1=LValN+TInt::GetRnd(int(SubVals));
1205  const TSizeTy ValN2=LValN+TInt::GetRnd(int(SubVals));
1206  const TSizeTy ValN3=LValN+TInt::GetRnd(int(SubVals));
1207  const TVal& Val1=ValT[ValN1];
1208  const TVal& Val2=ValT[ValN2];
1209  const TVal& Val3=ValT[ValN3];
1210  if (Val1<Val2){
1211  if (Val2<Val3){return ValN2;}
1212  else if (Val3<Val1){return ValN1;}
1213  else {return ValN3;}
1214  } else {
1215  if (Val1<Val3){return ValN1;}
1216  else if (Val3<Val2){return ValN2;}
1217  else {return ValN3;}
1218  }
1219 }
TInt::Mx
static const int Mx
Definition: dt.h:1049
TInt::GetRnd
static int GetRnd(const int &Range=0)
Definition: dt.h:1085
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 698 of file ds.h.

698  {
699  TSizeTy SubVals=TSizeTy(EI-BI); if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
700  const TSizeTy ValN1=TInt::GetRnd(SubVals), ValN2=TInt::GetRnd(SubVals), ValN3=TInt::GetRnd(SubVals);
701  const TVal& Val1 = *(BI+ValN1); const TVal& Val2 = *(BI+ValN2); const TVal& Val3 = *(BI+ValN3);
702  if (Cmp(Val1, Val2)) {
703  if (Cmp(Val2, Val3)) return BI+ValN2;
704  else if (Cmp(Val3, Val1)) return BI+ValN1;
705  else return BI+ValN3;
706  } else {
707  if (Cmp(Val1, Val3)) return BI+ValN1;
708  else if (Cmp(Val3, Val2)) return BI+ValN2;
709  else return BI+ValN3; } }
TInt::Mx
static const int Mx
Definition: dt.h:1049
TInt::GetRnd
static int GetRnd(const int &Range=0)
Definition: dt.h:1085
Cmp
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 948 of file ds.h.

948  {
949  int hc = 0;
950  for (TSizeTy i=0; i<Vals; i++){
951  hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetPrimHashCd());
952  }
953  return hc;
954 }
TVec::GetPrimHashCd
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:948
TPairHashImpl2::GetHashCd
static int GetHashCd(const int hc1, const int hc2)
Definition: bd.h:590
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 561 of file ds.h.

561 { return GetVal(Rnd.GetUniDevInt(Len())); }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TRnd::GetUniDevInt
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 563 of file ds.h.

563 { return GetVal(Rnd.GetUniDevInt(Len())); }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TRnd::GetUniDevInt
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 960 of file ds.h.

960  {
961  int hc = 0;
962  for (TSizeTy i=0; i<Vals; i++){
963  hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetSecHashCd());
964  }
965  if (Vals > 0) {
966  hc = TPairHashImpl::GetHashCd(hc, ValT[0].GetSecHashCd()); }
967  return hc;
968 }
TVec::GetSecHashCd
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:960
TPairHashImpl2::GetHashCd
static int GetHashCd(const int hc1, const int hc2)
Definition: bd.h:590
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1112 of file ds.h.

1112  {
1113  const TSizeTy BValN=TInt::GetInRng(_BValN, 0, Len()-1);
1114  const TSizeTy EValN=TInt::GetInRng(_EValN, 0, Len()-1);
1115  const TSizeTy SubVals=TInt::GetMx(0, EValN-BValN+1);
1116  SubValV.Gen(SubVals, 0);
1117  for (TSizeTy ValN=BValN; ValN<=EValN; ValN++){
1118  SubValV.Add(GetVal(ValN));}
1119 }
TInt::GetInRng
static int GetInRng(const int &Val, const int &Mn, const int &Mx)
Definition: dt.h:1104
TInt::GetMx
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1092
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
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 817 of file ds.h.

817  {
818  TVec<TVal, TSizeTy> V(1, 0); V.Add(Val1); return V;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 820 of file ds.h.

820  {
821  TVec<TVal, TSizeTy> V(2, 0); V.Add(Val1); V.Add(Val2); return V;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 823 of file ds.h.

823  {
824  TVec<TVal, TSizeTy> V(3, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); return V;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 826 of file ds.h.

826  {
827  TVec<TVal, TSizeTy> V(4, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); return V;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 829 of file ds.h.

829  {
830  TVec<TVal, TSizeTy> V(5, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); return V;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 832 of file ds.h.

832  {
833  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;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 835 of file ds.h.

835  {
836  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;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 838 of file ds.h.

838  {
839  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;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 841 of file ds.h.

841  {
842  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;}
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 621 of file ds.h.

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

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

879  {
880  return TStr()+
881  "Index:"+TInt::GetStr(ValN)+
882  " Vals:"+TInt::GetStr(Vals)+
883  " MxVals:"+TInt::GetStr(MxVals)+
884  " Type:"+GetTypeNm(*this);
885 }
GetTypeNm
TStr GetTypeNm(const Type &Var)
Definition: ut.h:16
TInt::GetStr
TStr GetStr() const
Definition: dt.h:1107
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TStr
Definition: dt.h:412
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
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 1122 of file ds.h.

1122  {
1123  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1124  Add(); Assert((0<=ValN)&&(ValN<Vals));
1125  for (TSizeTy MValN=Vals-2; MValN>=ValN; MValN--){ValT[MValN+1]=ValT[MValN];}
1126  ValT[ValN]=Val;
1127 }
Assert
#define Assert(Cond)
Definition: bd.h:251
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1346 of file ds.h.

1346  {
1347  TVec<TVal, TSizeTy> IntrsVec;
1348  Intrs(ValV, IntrsVec);
1349  MoveFrom(IntrsVec);
1350 }
TVec::Intrs
void Intrs(const TVec< TVal, TSizeTy > &ValV)
Sets this vector to its intersection with ValV. Assumes the vectors are sorted!
Definition: ds.h:1346
TVec::MoveFrom
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1020
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 1367 of file ds.h.

1367  {
1368  DstValV.Clr();
1369  TSizeTy ValN1=0, ValN2=0;
1370  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1371  const TVal& Val1=GetVal(ValN1);
1372  while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
1373  ValN2++;}
1374  if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
1375  DstValV.Add(Val1); ValN2++;}
1376  ValN1++;
1377  }
1378 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
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 1414 of file ds.h.

1414  {
1415  TSizeTy Cnt=0, ValN1=0, ValN2=0;
1416  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1417  const TVal& Val1=GetVal(ValN1);
1418  while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
1419  ValN2++;}
1420  if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
1421  ValN2++; Cnt++;}
1422  ValN1++;
1423  }
1424  return Cnt;
1425 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
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 513 of file ds.h.

513 {return MxVals==-1;}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
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 797 of file ds.h.

797 {return SearchForw(Val)!=-1;}
TVec::SearchForw
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1487
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 801 of file ds.h.

801 { ValN=SearchForw(Val); return ValN!=-1;}
TVec::SearchForw
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1487
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 805 of file ds.h.

805 {return SearchBin(Val)!=-1;}
TVec::SearchBin
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1454
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 1184 of file ds.h.

1184  {
1185  if (MnLValN<MxRValN){
1186  for (TSizeTy ValN1=MnLValN+1; ValN1<=MxRValN; ValN1++){
1187  TVal Val=ValT[ValN1]; TSizeTy ValN2=ValN1;
1188  if (Asc){
1189  while ((ValN2>MnLValN)&&(ValT[ValN2-1]>Val)){
1190  ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
1191  } else {
1192  while ((ValN2>MnLValN)&&(ValT[ValN2-1]<Val)){
1193  ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
1194  }
1195  ValT[ValN2]=Val;
1196  }
1197  }
1198 }
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 725 of file ds.h.

725  {
726  if (BI + 1 < EI) {
727  for (TIter i = BI, j; i != EI; ++i) { TVal Tmp=*i; j=i;
728  while (j > BI && Cmp(Tmp, *(j-1))) { *j = *(j-1); --j; } *j=Tmp; } } }
TVec::TIter
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:431
Cmp
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 1259 of file ds.h.

1259  {
1260  if (Asc){
1261  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1262  if (ValT[ValN]>ValT[ValN+1]){return false;}}
1263  } else {
1264  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1265  if (ValT[ValN]<ValT[ValN+1]){return false;}}
1266  }
1267  return true;
1268 }
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 742 of file ds.h.

742  {
743  if (EndI() == BegI()) return true;
744  for (TIter i = BegI(); i != EndI()-1; ++i) {
745  if (Cmp(*(i+1), *i)){return false;} } return true; }
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:567
TVec::TIter
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:431
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:565
Cmp
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 551 of file ds.h.

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

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

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

559 { AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::GetXOutOfBoundsErrMsg
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:879
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::LastValN ( ) const
inline

Returns the position of the last element.

Definition at line 555 of file ds.h.

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

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

Definition at line 895 of file ds.h.

895  {
896  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
897  SIn.Load(MxVals); SIn.Load(Vals); MxVals=Vals;
898  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
899  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=TVal(SIn);}
900 }
TSIn::Load
void Load(bool &Bool)
Definition: fl.h:84
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 }
XLoadHd
#define XLoadHd(Nm)
Definition: bd.h:312
TStr
Definition: dt.h:412
TPt
Definition: bd.h:196
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TPt::LoadXml
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 1292 of file ds.h.

1292  {
1293  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1294  TVec<TVal, TSizeTy> SortedVec(*this); SortedVec.Sort();
1295  Clr();
1296  for (TSizeTy ValN=0; ValN<SortedVec.Len(); ValN++){
1297  if ((ValN==0)||(SortedVec[ValN-1]!=SortedVec[ValN])){
1298  Add(SortedVec[ValN]);}
1299  }
1300 }
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 1020 of file ds.h.

1020  {
1021  if (this!=&Vec){
1022  if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
1023  MxVals=Vec.MxVals; Vals=Vec.Vals; ValT=Vec.ValT;
1024  Vec.MxVals=0; Vec.Vals=0; Vec.ValT=NULL;
1025  }
1026 }
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 594 of file ds.h.

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

1303  {
1304  // start with a sorted sequence to obtain all permutations
1305  TSizeTy First = 0, Last = Len(), Next = Len()-1;
1306  if (Last < 2) return false;
1307  for(; ; ) {
1308  // find rightmost element smaller than successor
1309  TSizeTy Next1 = Next;
1310  if (GetVal(--Next) < GetVal(Next1)) { // swap with rightmost element that's smaller, flip suffix
1311  TSizeTy Mid = Last;
1312  for (; GetVal(Next) >= GetVal(--Mid); ) { }
1313  Swap(Next, Mid);
1314  Reverse(Next1, Last-1);
1315  return true;
1316  }
1317  if (Next == First) { // pure descending, flip all
1318  Reverse();
1319  return false;
1320  }
1321  }
1322 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1286
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 467 of file ds.h.

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

930  {
931  if (this==&Vec){return false;}
932  if (Len()==Vec.Len()){
933  for (TSizeTy ValN=0; ValN<Vals; ValN++){
934  if (ValT[ValN]<Vec.ValT[ValN]){return true;}
935  else if (ValT[ValN]>Vec.ValT[ValN]){return false;}
936  else {}
937  }
938  return false;
939  } else {
940  return Len()<Vec.Len();
941  }
942 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 910 of file ds.h.

910  {
911  if (this!=&Vec){
912  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
913  MxVals=Vals=Vec.Vals;
914  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
915  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
916  }
917  return *this;
918 }
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 921 of file ds.h.

921  {
922  if (this==&Vec){return true;}
923  if (Len()!=Vec.Len()){return false;}
924  for (TSizeTy ValN=0; ValN<Vals; ValN++){
925  if (ValT[ValN]!=Vec.ValT[ValN]){return false;}}
926  return true;
927 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 475 of file ds.h.

475  {
476  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
477  return ValT[ValN];}
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::GetXOutOfBoundsErrMsg
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:879
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 479 of file ds.h.

479  {
480  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
481  return ValT[ValN];}
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::GetXOutOfBoundsErrMsg
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:879
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Pack ( )

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

Definition at line 1005 of file ds.h.

1005  {
1006  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1007  if (Vals==0){
1008  if (ValT!=NULL){delete[] ValT;} ValT=NULL;
1009  } else
1010  if (Vals<MxVals){
1011  MxVals=Vals;
1012  TVal* NewValT=new TVal[MxVals];
1013  IAssert(NewValT!=NULL);
1014  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
1015  delete[] ValT; ValT=NewValT;
1016  }
1017 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1222 of file ds.h.

1222  {
1223  TSizeTy PivotValN=GetPivotValN(MnLValN, MxRValN);
1224  Swap(PivotValN, MnLValN);
1225  TVal PivotVal=ValT[MnLValN];
1226  TSizeTy LValN=MnLValN-1; TSizeTy RValN=MxRValN+1;
1227  forever {
1228  if (Asc){
1229  do {RValN--;} while (ValT[RValN]>PivotVal);
1230  do {LValN++;} while (ValT[LValN]<PivotVal);
1231  } else {
1232  do {RValN--;} while (ValT[RValN]<PivotVal);
1233  do {LValN++;} while (ValT[LValN]>PivotVal);
1234  }
1235  if (LValN<RValN){Swap(LValN, RValN);}
1236  else {return RValN;}
1237  };
1238 }
forever
#define forever
Definition: bd.h:6
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TVec::GetPivotValN
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:1201
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 712 of file ds.h.

712  {
713  forever {
714  while (Cmp(*BI, Pivot)){++BI;} --EI;
715  while (Cmp(Pivot, *EI)){--EI;}
716  if (!(BI<EI)){return BI;} SwapI(BI, EI); ++BI; } }
forever
#define forever
Definition: bd.h:6
Cmp
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
TVec::SwapI
static void SwapI(TIter LVal, TIter RVal)
Swaps the elements that iterators LVal and RVal point to.
Definition: ds.h:646
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 1325 of file ds.h.

1325  {
1326  TSizeTy First = 0, Last = Len(), Next = Len()-1;
1327  if (Last < 2) return false;
1328  for(; ; ) {
1329  // find rightmost element not smaller than successor
1330  TSizeTy Next1 = Next;
1331  if (GetVal(--Next) >= GetVal(Next1)) { // swap with rightmost element that's not smaller, flip suffix
1332  TSizeTy Mid = Last;
1333  for (; GetVal(Next) < GetVal(--Mid); ) { }
1334  Swap(Next, Mid);
1335  Reverse(Next1, Last);
1336  return true;
1337  }
1338  if (Next == First) { // pure descending, flip all
1339  Reverse();
1340  return false;
1341  }
1342  }
1343 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::Last
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:551
TVec::Reverse
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1286
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 1166 of file ds.h.

1166  {
1167  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=Val;}
1168 }
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1241 of file ds.h.

1241  {
1242  if (MnLValN<MxRValN){
1243  if (MxRValN-MnLValN<20){
1244  ISort(MnLValN, MxRValN, Asc);
1245  } else {
1246  TSizeTy SplitValN=Partition(MnLValN, MxRValN, Asc);
1247  QSort(MnLValN, SplitValN, Asc);
1248  QSort(SplitValN+1, MxRValN, Asc);
1249  }
1250  }
1251 }
TVec::QSort
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1241
TVec::ISort
void ISort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Insertion sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1184
TVec::Partition
TSizeTy Partition(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Partitions the values between positions MnLValN...MxLValN.
Definition: ds.h:1222
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 731 of file ds.h.

731  {
732  if (BI + 1 < EI) {
733  if (EI - BI < 20) { ISortCmp(BI, EI, Cmp); }
734  else { const TVal Val = *GetPivotValNCmp(BI, EI, Cmp);
735  TIter Split = PartitionCmp(BI, EI, Val, Cmp);
736  QSortCmp(BI, Split, Cmp); QSortCmp(Split, EI, Cmp); } } }
TVec::GetPivotValNCmp
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:698
TVec::TIter
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:431
TVec::PartitionCmp
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:712
TVec::QSortCmp
static void QSortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Quick sorts the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:731
TVec::ISortCmp
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:725
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 528 of file ds.h.

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

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

517 { IAssert((0<=_Vals)&&(_Vals<=_MxVals)); Resize(_MxVals); Vals=_Vals;}
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Resize
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:846
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Reserved ( ) const
inline

Returns the size of allocated storage capacity.

Definition at line 549 of file ds.h.

549 {return MxVals;}
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
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 846 of file ds.h.

846  {
847  IAssertR(MxVals!=-1, TStr::Fmt("Can not increase the capacity of the vector. %s. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", GetTypeNm(*this).CStr()).CStr());
848  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());
849  if (_MxVals==-1){
850  if (Vals==0){MxVals=16;} else {MxVals*=2;}
851  } else {
852  if (_MxVals<=MxVals){return;} else {MxVals=_MxVals;}
853  }
854  if (MxVals < 0) {
855  MxVals = TInt::Mx-1024;
856  }
857  if (ValT==NULL){
858  try {
859  ValT=new TVal[MxVals];
860  }
861  catch (std::exception Ex){
862  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.]",
863  Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
864  } else {
865  TVal* NewValT = NULL;
866  try {
867  NewValT=new TVal[MxVals];
868  }
869  catch (std::exception Ex){
870  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.]",
871  Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
872  IAssert(NewValT!=NULL);
873  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
874  delete[] ValT; ValT=NewValT;
875  }
876 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
GetTypeNm
TStr GetTypeNm(const Type &Var)
Definition: ut.h:16
TInt::GetStr
TStr GetStr() const
Definition: dt.h:1107
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TInt::Mx
static const int Mx
Definition: dt.h:1049
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
FailR
#define FailR(Reason)
Definition: bd.h:240
TStr::Fmt
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TStr::CStr
char * CStr()
Definition: dt.h:476
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Reverse ( )

Reverses the order of the elements in the vector.

Definition at line 1286 of file ds.h.

1286  {
1287  for (TSizeTy ValN=0; ValN<Vals/2; ValN++){
1288  Swap(ValN, Vals-ValN-1);}
1289 }
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
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 692 of file ds.h.

692 { Assert(LValN>=0 && RValN<Len()); while (LValN < RValN){Swap(LValN++, RValN--);} }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
Assert
#define Assert(Cond)
Definition: bd.h:251
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Save ( TSOut &  SOut) const

Definition at line 903 of file ds.h.

903  {
904  if (MxVals!=-1){SOut.Save(MxVals);} else {SOut.Save(Vals);}
905  SOut.Save(Vals);
906  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].Save(SOut);}
907 }
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TSOut::Save
void Save(const bool &Bool)
Definition: fl.h:173
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 }
TInt::GetStr
TStr GetStr() const
Definition: dt.h:1107
XSaveHdArg
#define XSaveHdArg(Nm, ArgNm, ArgVal)
Definition: bd.h:321
TStr
Definition: dt.h:412
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1494 of file ds.h.

1494  {
1495  for (TSizeTy ValN=Vals-1; ValN>=0; ValN--){
1496  if (Val==ValT[ValN]){return ValN;}}
1497  return -1;
1498 }
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1454 of file ds.h.

1454  {
1455  TSizeTy LValN=0, RValN=Len()-1;
1456  while (RValN>=LValN){
1457  TSizeTy ValN=(LValN+RValN)/2;
1458  if (Val==ValT[ValN]){return ValN;}
1459  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1460  }
1461  return -1;
1462 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1465 of file ds.h.

1465  {
1466  TSizeTy LValN=0, RValN=Len()-1;
1467  while (RValN>=LValN){
1468  TSizeTy ValN=(LValN+RValN)/2;
1469  if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
1470  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1471  }
1472  InsValN=LValN; return -1;
1473 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1476 of file ds.h.

1476  {
1477  TSizeTy LValN=0, RValN=Len()-1;
1478  while (RValN>=LValN){
1479  TSizeTy ValN=(LValN+RValN)/2;
1480  if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
1481  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1482  }
1483  InsValN=RValN; return -1;
1484 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1487 of file ds.h.

1487  {
1488  for (TSizeTy ValN=BValN; ValN<Vals; ValN++){
1489  if (Val==ValT[ValN]){return ValN;}}
1490  return -1;
1491 }
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1501 of file ds.h.

1501  {
1502  TSizeTy ValVLen=ValV.Len();
1503  for (TSizeTy ValN=BValN; ValN<Vals-ValVLen+1; ValN++){
1504  bool Found=true;
1505  for (TSizeTy SubValN=0; SubValN<ValVLen; SubValN++){
1506  if (ValV[SubValN]!=GetVal(ValN+SubValN)){Found=false; break;}
1507  }
1508  if (Found){return ValN;}
1509  }
1510  return -1;
1511 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
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 625 of file ds.h.

625 {AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN)); ValT[ValN] = Val;}
AssertR
#define AssertR(Cond, Reason)
Definition: bd.h:258
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::GetXOutOfBoundsErrMsg
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:879
TVec::ValT
TVal * ValT
Definition: ds.h:435
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Shuffle ( TRnd &  Rnd)

Randomly shuffles the elements of the vector.

Definition at line 1271 of file ds.h.

1271  {
1272  if (Len() < TInt::Mx) {
1273  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1274  const int Range = int(Vals-ValN);
1275  Swap(ValN, ValN+Rnd.GetUniDevInt(Range));
1276  }
1277  } else {
1278  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1279  const TSizeTy Range = Vals-ValN;
1280  Swap(ValN, TSizeTy(ValN+Rnd.GetUniDevInt64(Range)));
1281  }
1282  }
1283 }
TRnd::GetUniDevInt64
int64 GetUniDevInt64(const int64 &Range=0)
Definition: dt.cpp:51
TInt::Mx
static const int Mx
Definition: dt.h:1049
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
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 1254 of file ds.h.

1254  {
1255  QSort(0, Len()-1, Asc);
1256 }
TVec::QSort
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1241
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
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 739 of file ds.h.

739 { QSortCmp(BegI(), EndI(), Cmp);}
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:567
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:565
TVec::QSortCmp
static void QSortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Quick sorts the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:731
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 1047 of file ds.h.

1047  {
1048  if (this!=&Vec){
1049  ::Swap(MxVals, Vec.MxVals);
1050  ::Swap(Vals, Vec.Vals);
1051  ::Swap(ValT, Vec.ValT);
1052  }
1053 }
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 644 of file ds.h.

644 { const TVal Val=ValT[ValN1]; ValT[ValN1]=ValT[ValN2]; ValT[ValN2]=Val;}
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 646 of file ds.h.

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

982  {
983  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
984  IAssert((_Vals==-1)||(_Vals>=0));
985  if ((_Vals!=-1)&&(_Vals>=Vals)){
986  return;
987  } else
988  if (((_Vals==-1)&&(Vals==0))||(_Vals==0)){
989  if (ValT!=NULL){delete[] ValT;}
990  MxVals=Vals=0; ValT=NULL;
991  } else {
992  if (_Vals==-1){
993  if (MxVals==Vals){return;} else {MxVals=Vals;}
994  } else {
995  MxVals=Vals=_Vals;
996  }
997  TVal* NewValT=new TVal[MxVals];
998  IAssert(NewValT!=NULL);
999  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
1000  delete[] ValT; ValT=NewValT;
1001  }
1002 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec::MxVals
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:433
TVec::Vals
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:434
TVec::ValT
TVal * ValT
Definition: ds.h:435
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 1353 of file ds.h.

1353  {
1354  TVec<TVal, TSizeTy> UnionVec;
1355  Union(ValV, UnionVec);
1356  MoveFrom(UnionVec);
1357 }
TVec::Union
void Union(const TVec< TVal, TSizeTy > &ValV)
Sets this vector to its union with ValV. Assumes the vectors are sorted!
Definition: ds.h:1353
TVec::MoveFrom
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1020
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
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 1381 of file ds.h.

1381  {
1382  DstValV.Gen(TInt::GetMx(Len(), ValV.Len()), 0);
1383  TSizeTy ValN1=0, ValN2=0;
1384  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1385  const TVal& Val1=GetVal(ValN1);
1386  const TVal& Val2=ValV.GetVal(ValN2);
1387  if (Val1<Val2){DstValV.Add(Val1); ValN1++;}
1388  else if (Val1>Val2){DstValV.Add(Val2); ValN2++;}
1389  else {DstValV.Add(Val1); ValN1++; ValN2++;}
1390  }
1391  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
1392  DstValV.Add(GetVal(RestValN1));}
1393  for (TSizeTy RestValN2=ValN2; RestValN2<ValV.Len(); RestValN2++){
1394  DstValV.Add(ValV.GetVal(RestValN2));}
1395 }
TInt::GetMx
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1092
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
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 1428 of file ds.h.

1428  {
1429  TSizeTy Cnt = 0, ValN1 = 0, ValN2 = 0;
1430  while ((ValN1 < Len()) && (ValN2 < ValV.Len())) {
1431  const TVal& Val1 = GetVal(ValN1);
1432  const TVal& Val2 = ValV.GetVal(ValN2);
1433  if (Val1 < Val2) {
1434  Cnt++; ValN1++;
1435  } else if (Val1 > Val2) {
1436  Cnt++; ValN2++;
1437  } else {
1438  Cnt++; ValN1++; ValN2++;
1439  }
1440  }
1441  Cnt += (Len() - ValN1) + (ValV.Len() - ValN2);
1442  return Cnt;
1443 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetVal
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:621

Member Data Documentation

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

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