SNAP Library 2.3, User Reference  2014-06-16 11:58:46
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
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 Pack ()
 The vector reduces its 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 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...
 
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 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
 Returns a vector on 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)
 Result is the intersection of this vector with ValV. More...
 
void Union (const TVec< TVal, TSizeTy > &ValV)
 Result is the union of this vector with ValV. More...
 
void Diff (const TVec< TVal, TSizeTy > &ValV)
 Subtracts ValV from this vector. More...
 
void Intrs (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
 DstValV is the intersection of vectors this and ValV. More...
 
void Union (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
 DstValV is the union of vectors this and ValV. More...
 
void Diff (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
 DstValV is the difference of vectors this and ValV. More...
 
TSizeTy IntrsLen (const TVec< TVal, TSizeTy > &ValV) const
 Returns the size of the intersection of vectors this and ValV. More...
 
TSizeTy UnionLen (const TVec< TVal, TSizeTy > &ValV) const
 Returns the size of the union of vectors this and ValV. 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 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 420 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 422 of file ds.h.

Constructor & Destructor Documentation

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

Definition at line 432 of file ds.h.

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

Definition at line 870 of file ds.h.

870  {
871  MxVals=Vec.MxVals; Vals=Vec.Vals;
872  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
873  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
874 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( const TSizeTy &  _Vals)
inlineexplicit

Constructs a vector (an array) of length _Vals.

Definition at line 435 of file ds.h.

435  {
436  IAssert(0<=_Vals); MxVals=Vals=_Vals;
437  if (_Vals==0){ValT=NULL;} else {ValT=new TVal[_Vals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( const TSizeTy &  _MxVals,
const TSizeTy &  _Vals 
)
inline

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

Definition at line 439 of file ds.h.

439  {
440  IAssert((0<=_Vals)&&(_Vals<=_MxVals)); MxVals=_MxVals; Vals=_Vals;
441  if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( TVal *  _ValT,
const TSizeTy &  _Vals 
)
inlineexplicit

Constructs a vector of _Vals elements of memory array _ValT.

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

Definition at line 446 of file ds.h.

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

Definition at line 448 of file ds.h.

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

Definition at line 449 of file ds.h.

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

Member Function Documentation

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

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

This increases the vector size by one.

Definition at line 559 of file ds.h.

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

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

The content of Val is copied to the new element.

Definition at line 564 of file ds.h.

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

Definition at line 566 of file ds.h.

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

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

Definition at line 569 of file ds.h.

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

Adds element Val to a sorted vector.

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

Definition at line 1042 of file ds.h.

1042  {
1043  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1044  Add();
1045  TSizeTy ValN=Vals-2;
1046  while ((ValN>=0)&&((Asc&&(Val<ValT[ValN]))||(!Asc&&(Val>ValT[ValN])))){
1047  ValT[ValN+1]=ValT[ValN]; ValN--;}
1048  ValT[ValN+1]=Val;
1049  return ValN+1;
1050 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::AddMerged ( const TVal &  Val)

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

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

Definition at line 1053 of file ds.h.

1053  {
1054  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1055  TSizeTy ValN=SearchBin(Val);
1056  if (ValN==-1){return AddSorted(Val);}
1057  else {GetVal(ValN)=Val; return -1;}
1058 }
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1027
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
#define AssertR(Cond, Reason)
Definition: bd.h:258
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 1027 of file ds.h.

1027  {
1028  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1029  TSizeTy ValN=Add(Val);
1030  if (Asc){
1031  while ((ValN>0)&&(ValT[ValN]<ValT[ValN-1])){
1032  Swap(ValN, ValN-1); ValN--;}
1033  } else {
1034  while ((ValN>0)&&(ValT[ValN]>ValT[ValN-1])){
1035  Swap(ValN, ValN-1); ValN--;}
1036  }
1037  if ((_MxVals!=-1)&&(Len()>_MxVals)){Del(_MxVals, Len()-1);}
1038  return ValN;
1039 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::AddUnique ( const TVal &  Val)

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

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

Definition at line 1068 of file ds.h.

1068  {
1069  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1070  TSizeTy ValN=SearchForw(Val);
1071  if (ValN==-1){return Add(Val);}
1072  else {GetVal(ValN)=Val; return -1;}
1073 }
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::AddV ( const TVec< TVal, TSizeTy > &  ValV)

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

Definition at line 1020 of file ds.h.

1020  {
1021  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1022  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){Add(ValV[ValN]);}
1023  return Len();
1024 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::AddVMerged ( const TVec< TVal, TSizeTy > &  ValV)

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

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

Definition at line 1061 of file ds.h.

1061  {
1062  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1063  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){AddMerged(ValV[ValN]);}
1064  return Len();
1065 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
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:1053
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
template<class TVal, class TSizeTy = int>
TIter TVec< TVal, TSizeTy >::BegI ( ) const
inline

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

Definition at line 550 of file ds.h.

550 {return ValT;}
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::BSort ( const TSizeTy &  MnLValN,
const TSizeTy &  MxRValN,
const bool &  Asc 
)

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

Parameters
AscSorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1135 of file ds.h.

1135  {
1136  for (TSizeTy ValN1=MnLValN; ValN1<=MxRValN; ValN1++){
1137  for (TSizeTy ValN2=MxRValN; ValN2>ValN1; ValN2--){
1138  if (Asc){
1139  if (ValT[ValN2]<ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
1140  } else {
1141  if (ValT[ValN2]>ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
1142  }
1143  }
1144  }
1145 }
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
template<class TCmp >
static void TVec< TVal, TSizeTy >::BSortCmp ( TIter  BI,
TIter  EI,
const TCmp Cmp 
)
inlinestatic

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

Definition at line 693 of file ds.h.

693  {
694  for (TIter i = BI; i != EI; ++i) {
695  for (TIter j = EI-1; j != i; --j) {
696  if (Cmp(*j, *(j-1))) { SwapI(j, j-1); } } } }
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:422
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
static void SwapI(TIter LVal, TIter RVal)
Swaps the elements that iterators LVal and RVal point to.
Definition: ds.h:620
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Clr ( const bool &  DoDel = true,
const TSizeTy &  NoDelLim = -1 
)

Clears the contents of the vector.

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

Definition at line 953 of file ds.h.

953  {
954  if ((DoDel)||((!DoDel)&&(NoDelLim!=-1)&&(MxVals>NoDelLim))){
955  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
956  MxVals=Vals=0; ValT=NULL;
957  } else {
958  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
959  Vals=0;
960  }
961 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::Count ( const TVal &  Val) const

Counts the number of occurrences of Val in the vector.

Definition at line 1410 of file ds.h.

1410  {
1411  TSizeTy Count = 0;
1412  for (TSizeTy i = 0; i < Len(); i++){
1413  if (Val == ValT[i]){Count++;}}
1414  return Count;
1415 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TSizeTy Count(const TVal &Val) const
Counts the number of occurrences of Val in the vector.
Definition: ds.h:1410
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Del ( const TSizeTy &  ValN)

Removes the element at position ValN.

Definition at line 1094 of file ds.h.

1094  {
1095  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1096  Assert((0<=ValN)&&(ValN<Vals));
1097  for (TSizeTy MValN=ValN+1; MValN<Vals; MValN++){
1098  ValT[MValN-1]=ValT[MValN];}
1099  ValT[--Vals]=TVal();
1100 }
#define Assert(Cond)
Definition: bd.h:251
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Del ( const TSizeTy &  MnValN,
const TSizeTy &  MxValN 
)

Removes the elements at positions MnValN...MxValN.

Definition at line 1103 of file ds.h.

1103  {
1104  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1105  Assert((0<=MnValN)&&(MnValN<Vals)&&(0<=MxValN)&&(MxValN<Vals));
1106  Assert(MnValN<=MxValN);
1107  for (TSizeTy ValN=MxValN+1; ValN<Vals; ValN++){
1108  ValT[MnValN+ValN-MxValN-1]=ValT[ValN];}
1109  for (TSizeTy ValN=Vals-MxValN+MnValN-1; ValN<Vals; ValN++){
1110  ValT[ValN]=TVal();}
1111  Vals-=MxValN-MnValN+1;
1112 }
#define Assert(Cond)
Definition: bd.h:251
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy >
void TVec< TVal, TSizeTy >::DelAll ( const TVal &  Val)

Removes all occurrences of element Val.

Definition at line 1123 of file ds.h.

1123  {
1124  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1125  TSizeTy ValN;
1126  while ((ValN=SearchForw(Val))!=-1){Del(ValN);}
1127 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
#define AssertR(Cond, Reason)
Definition: bd.h:258
template<class TVal, class TSizeTy >
bool TVec< TVal, TSizeTy >::DelIfIn ( const TVal &  Val)

Removes the first occurrence of element Val.

Definition at line 1115 of file ds.h.

1115  {
1116  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1117  TSizeTy ValN=SearchForw(Val);
1118  if (ValN!=-1){Del(ValN); return true;}
1119  else {return false;}
1120 }
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
#define AssertR(Cond, Reason)
Definition: bd.h:258
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::DelLast ( )
inline

Removes the last element of the vector.

Definition at line 609 of file ds.h.

609 {Del(Len()-1);}
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Diff ( const TVec< TVal, TSizeTy > &  ValV)

Subtracts ValV from this vector.

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

Definition at line 1324 of file ds.h.

1324  {
1325  TVec<TVal, TSizeTy> DiffVec;
1326  Diff(ValV, DiffVec);
1327  MoveFrom(DiffVec);
1328 }
void Diff(const TVec< TVal, TSizeTy > &ValV)
Subtracts ValV from this vector.
Definition: ds.h:1324
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1002
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Diff ( const TVec< TVal, TSizeTy > &  ValV,
TVec< TVal, TSizeTy > &  DstValV 
) const

DstValV is the difference of vectors this and ValV.

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

Definition at line 1362 of file ds.h.

1362  {
1363  DstValV.Clr();
1364  TSizeTy ValN1=0, ValN2=0;
1365  while (ValN1<Len() && ValN2<ValV.Len()) {
1366  const TVal& Val1 = GetVal(ValN1);
1367  while (ValN2<ValV.Len() && Val1>ValV.GetVal(ValN2)) ValN2++;
1368  if (ValN2<ValV.Len()) {
1369  if (Val1!=ValV.GetVal(ValN2)) { DstValV.Add(Val1); }
1370  ValN1++;
1371  }
1372  }
1373  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
1374  DstValV.Add(GetVal(RestValN1));}
1375 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::Empty ( ) const
inline

Tests whether the vector is empty.

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

Definition at line 530 of file ds.h.

530 {return Vals==0;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
template<class TVal, class TSizeTy = int>
TIter TVec< TVal, TSizeTy >::EndI ( ) const
inline

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

Definition at line 552 of file ds.h.

552 {return ValT+Vals;}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Gen ( const TSizeTy &  _Vals)
inline

Constructs a vector (an array) of _Vals elements.

Definition at line 486 of file ds.h.

486  { IAssert(0<=_Vals);
487  if (ValT!=NULL && MxVals!=-1){delete[] ValT;} MxVals=Vals=_Vals;
488  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Gen ( const TSizeTy &  _MxVals,
const TSizeTy &  _Vals 
)
inline

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

Definition at line 490 of file ds.h.

490  { IAssert((0<=_Vals)&&(_Vals<=_MxVals));
491  if (ValT!=NULL && MxVals!=-1){delete[] ValT;} MxVals=_MxVals; Vals=_Vals;
492  if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::GenExt ( TVal *  _ValT,
const TSizeTy &  _Vals 
)
inline

Constructs a vector of _Vals elements of memory array _ValT.

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

Definition at line 497 of file ds.h.

497  {
498  if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
499  MxVals=-1; Vals=_Vals; ValT=_ValT;}
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::GetAddDat ( const TVal &  Val)
inline

Returns reference to the first occurrence of element Val.

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

Definition at line 796 of file ds.h.

796  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
797  const TSizeTy ValN=SearchForw(Val); if (ValN==-1){Add(Val); return Last();} else {return GetVal(ValN);}}
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:539
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::GetDat ( const TVal &  Val) const
inline

Returns reference to the first occurrence of element Val.

Definition at line 792 of file ds.h.

792 { return GetVal(SearchForw(Val));}
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
template<class TVal, class TSizeTy = int>
TIter TVec< TVal, TSizeTy >::GetI ( const TSizeTy &  ValN) const
inline

Returns an iterator an element at position ValN.

Definition at line 554 of file ds.h.

554 {return ValT+ValN;}
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::GetMemSize ( ) const
inline

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

Definition at line 477 of file ds.h.

477  {
478  return TSizeTy(2*sizeof(TVal)+sizeof(TSizeTy)*Vals);}
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::GetMemUsed ( ) const
inline

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

Definition at line 474 of file ds.h.

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

Returns the position of the largest element in the vector.

Definition at line 1467 of file ds.h.

1467  {
1468  if (Vals==0){return -1;}
1469  TSizeTy MxValN=0;
1470  for (TSizeTy ValN=1; ValN<Vals; ValN++){
1471  if (ValT[ValN]>ValT[MxValN]){MxValN=ValN;}
1472  }
1473  return MxValN;
1474 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::GetPivotValN ( const TSizeTy &  LValN,
const TSizeTy &  RValN 
) const

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

Definition at line 1165 of file ds.h.

1165  {
1166  TSizeTy SubVals=RValN-LValN+1;
1167  if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
1168  const TSizeTy ValN1=LValN+TInt::GetRnd(int(SubVals));
1169  const TSizeTy ValN2=LValN+TInt::GetRnd(int(SubVals));
1170  const TSizeTy ValN3=LValN+TInt::GetRnd(int(SubVals));
1171  const TVal& Val1=ValT[ValN1];
1172  const TVal& Val2=ValT[ValN2];
1173  const TVal& Val3=ValT[ValN3];
1174  if (Val1<Val2){
1175  if (Val2<Val3){return ValN2;}
1176  else if (Val3<Val1){return ValN1;}
1177  else {return ValN3;}
1178  } else {
1179  if (Val1<Val3){return ValN1;}
1180  else if (Val3<Val2){return ValN2;}
1181  else {return ValN3;}
1182  }
1183 }
static const int Mx
Definition: dt.h:1046
static int GetRnd(const int &Range=0)
Definition: dt.h:1082
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
template<class TCmp >
static TIter TVec< TVal, TSizeTy >::GetPivotValNCmp ( const TIter BI,
const TIter EI,
const TCmp Cmp 
)
inlinestatic

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

Definition at line 672 of file ds.h.

672  {
673  TSizeTy SubVals=TSizeTy(EI-BI); if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
674  const TSizeTy ValN1=TInt::GetRnd(SubVals), ValN2=TInt::GetRnd(SubVals), ValN3=TInt::GetRnd(SubVals);
675  const TVal& Val1 = *(BI+ValN1); const TVal& Val2 = *(BI+ValN2); const TVal& Val3 = *(BI+ValN3);
676  if (Cmp(Val1, Val2)) {
677  if (Cmp(Val2, Val3)) return BI+ValN2;
678  else if (Cmp(Val3, Val1)) return BI+ValN1;
679  else return BI+ValN3;
680  } else {
681  if (Cmp(Val1, Val3)) return BI+ValN1;
682  else if (Cmp(Val3, Val2)) return BI+ValN2;
683  else return BI+ValN3; } }
static const int Mx
Definition: dt.h:1046
static int GetRnd(const int &Range=0)
Definition: dt.h:1082
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 930 of file ds.h.

930  {
931  int hc = 0;
932  for (TSizeTy i=0; i<Vals; i++){
934  }
935  return hc;
936 }
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:930
static int GetHashCd(const int hc1, const int hc2)
Definition: bd.h:590
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy >
int TVec< TVal, TSizeTy >::GetSecHashCd ( ) const

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

Definition at line 942 of file ds.h.

942  {
943  int hc = 0;
944  for (TSizeTy i=0; i<Vals; i++){
946  }
947  if (Vals > 0) {
948  hc = TPairHashImpl::GetHashCd(hc, ValT[0].GetSecHashCd()); }
949  return hc;
950 }
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:942
static int GetHashCd(const int hc1, const int hc2)
Definition: bd.h:590
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::GetSubValV ( const TSizeTy &  BValN,
const TSizeTy &  EValN,
TVec< TVal, TSizeTy > &  ValV 
) const

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

Definition at line 1076 of file ds.h.

1076  {
1077  const TSizeTy BValN=TInt::GetInRng(_BValN, 0, Len()-1);
1078  const TSizeTy EValN=TInt::GetInRng(_EValN, 0, Len()-1);
1079  const TSizeTy SubVals=TInt::GetMx(0, EValN-BValN+1);
1080  SubValV.Gen(SubVals, 0);
1081  for (TSizeTy ValN=BValN; ValN<=EValN; ValN++){
1082  SubValV.Add(GetVal(ValN));}
1083 }
static int GetInRng(const int &Val, const int &Mn, const int &Mx)
Definition: dt.h:1101
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1089
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1)
inlinestatic

Returns a vector on element Val1.

Definition at line 802 of file ds.h.

802  {
803  TVec<TVal, TSizeTy> V(1, 0); V.Add(Val1); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2 
)
inlinestatic

Returns a vector on elements Val1, Val2.

Definition at line 805 of file ds.h.

805  {
806  TVec<TVal, TSizeTy> V(2, 0); V.Add(Val1); V.Add(Val2); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3 
)
inlinestatic

Returns a vector on elements Val1...Val3.

Definition at line 808 of file ds.h.

808  {
809  TVec<TVal, TSizeTy> V(3, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4 
)
inlinestatic

Returns a vector on elements Val1...Val4.

Definition at line 811 of file ds.h.

811  {
812  TVec<TVal, TSizeTy> V(4, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5 
)
inlinestatic

Returns a vector on elements Val1...Val5.

Definition at line 814 of file ds.h.

814  {
815  TVec<TVal, TSizeTy> V(5, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6 
)
inlinestatic

Returns a vector on elements Val1...Val6.

Definition at line 817 of file ds.h.

817  {
818  TVec<TVal, TSizeTy> V(6, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6,
const TVal &  Val7 
)
inlinestatic

Returns a vector on elements Val1...Val7.

Definition at line 820 of file ds.h.

820  {
821  TVec<TVal, TSizeTy> V(7, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6,
const TVal &  Val7,
const TVal &  Val8 
)
inlinestatic

Returns a vector on elements Val1...Val8.

Definition at line 823 of file ds.h.

823  {
824  TVec<TVal, TSizeTy> V(8, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); V.Add(Val8); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6,
const TVal &  Val7,
const TVal &  Val8,
const TVal &  Val9 
)
inlinestatic

Returns a vector on elements Val1...Val9.

Definition at line 826 of file ds.h.

826  {
827  TVec<TVal, TSizeTy> V(9, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); V.Add(Val8); V.Add(Val9); return V;}
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::GetVal ( const TSizeTy &  ValN) const
inline

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

Definition at line 595 of file ds.h.

595 {return operator[](ValN);}
const TVal & operator[](const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:466
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::GetVal ( const TSizeTy &  ValN)
inline

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

Definition at line 597 of file ds.h.

597 {return operator[](ValN);}
const TVal & operator[](const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:466
template<class TVal , class TSizeTy>
TStr TVec< TVal, TSizeTy >::GetXOutOfBoundsErrMsg ( const TSizeTy &  ValN) const
protected

Constructs the out of bounds error message.

Definition at line 861 of file ds.h.

861  {
862  return TStr()+
863  "Index:"+TInt::GetStr(ValN)+
864  " Vals:"+TInt::GetStr(Vals)+
865  " MxVals:"+TInt::GetStr(MxVals)+
866  " Type:"+GetTypeNm(*this);
867 }
TStr GetTypeNm(const Type &Var)
Definition: ut.h:16
TStr GetStr() const
Definition: dt.h:1104
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
Definition: dt.h:412
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Ins ( const TSizeTy &  ValN,
const TVal &  Val 
)

Inserts new element Val before the element at position ValN.

Definition at line 1086 of file ds.h.

1086  {
1087  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1088  Add(); Assert((0<=ValN)&&(ValN<Vals));
1089  for (TSizeTy MValN=Vals-2; MValN>=ValN; MValN--){ValT[MValN+1]=ValT[MValN];}
1090  ValT[ValN]=Val;
1091 }
#define Assert(Cond)
Definition: bd.h:251
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Intrs ( const TVec< TVal, TSizeTy > &  ValV)

Result is the intersection of this vector with ValV.

Assumes the vectors are sorted!

Definition at line 1310 of file ds.h.

1310  {
1311  TVec<TVal, TSizeTy> IntrsVec;
1312  Intrs(ValV, IntrsVec);
1313  MoveFrom(IntrsVec);
1314 }
void Intrs(const TVec< TVal, TSizeTy > &ValV)
Result is the intersection of this vector with ValV.
Definition: ds.h:1310
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1002
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Intrs ( const TVec< TVal, TSizeTy > &  ValV,
TVec< TVal, TSizeTy > &  DstValV 
) const

DstValV is the intersection of vectors this and ValV.

Assumes the vectors are sorted!

Definition at line 1331 of file ds.h.

1331  {
1332  DstValV.Clr();
1333  TSizeTy ValN1=0, ValN2=0;
1334  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1335  const TVal& Val1=GetVal(ValN1);
1336  while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
1337  ValN2++;}
1338  if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
1339  DstValV.Add(Val1); ValN2++;}
1340  ValN1++;
1341  }
1342 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::IntrsLen ( const TVec< TVal, TSizeTy > &  ValV) const

Returns the size of the intersection of vectors this and ValV.

Assumes both vectors are sorted in ascending order!

Definition at line 1378 of file ds.h.

1378  {
1379  TSizeTy Cnt=0, ValN1=0, ValN2=0;
1380  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1381  const TVal& Val1=GetVal(ValN1);
1382  while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
1383  ValN2++;}
1384  if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
1385  ValN2++; Cnt++;}
1386  ValN1++;
1387  }
1388  return Cnt;
1389 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsExt ( ) const
inline

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

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

Definition at line 504 of file ds.h.

504 {return MxVals==-1;}
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsIn ( const TVal &  Val) const
inline

Checks whether element Val is a member of the vector.

Definition at line 782 of file ds.h.

782 {return SearchForw(Val)!=-1;}
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsIn ( const TVal &  Val,
TSizeTy &  ValN 
) const
inline

Checks whether element Val is a member of the vector.

Position of Val is returned in ValN.

Definition at line 786 of file ds.h.

786 { ValN=SearchForw(Val); return ValN!=-1;}
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsInBin ( const TVal &  Val) const
inline

Checks whether element Val is a member of the vector.

Uses binary search and thus assumes the vector is sorted.

Definition at line 790 of file ds.h.

790 {return SearchBin(Val)!=-1;}
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::ISort ( const TSizeTy &  MnLValN,
const TSizeTy &  MxRValN,
const bool &  Asc 
)

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

Parameters
AscSorts the elements in ascending (if true) or descending (if false) order.

Definition at line 1148 of file ds.h.

1148  {
1149  if (MnLValN<MxRValN){
1150  for (TSizeTy ValN1=MnLValN+1; ValN1<=MxRValN; ValN1++){
1151  TVal Val=ValT[ValN1]; TSizeTy ValN2=ValN1;
1152  if (Asc){
1153  while ((ValN2>MnLValN)&&(ValT[ValN2-1]>Val)){
1154  ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
1155  } else {
1156  while ((ValN2>MnLValN)&&(ValT[ValN2-1]<Val)){
1157  ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
1158  }
1159  ValT[ValN2]=Val;
1160  }
1161  }
1162 }
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
template<class TCmp >
static void TVec< TVal, TSizeTy >::ISortCmp ( TIter  BI,
TIter  EI,
const TCmp Cmp 
)
inlinestatic

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

Definition at line 699 of file ds.h.

699  {
700  if (BI + 1 < EI) {
701  for (TIter i = BI, j; i != EI; ++i) { TVal Tmp=*i; j=i;
702  while (j > BI && Cmp(Tmp, *(j-1))) { *j = *(j-1); --j; } *j=Tmp; } } }
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:422
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 1223 of file ds.h.

1223  {
1224  if (Asc){
1225  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1226  if (ValT[ValN]>ValT[ValN+1]){return false;}}
1227  } else {
1228  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1229  if (ValT[ValN]<ValT[ValN+1]){return false;}}
1230  }
1231  return true;
1232 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
template<class TCmp >
bool TVec< TVal, TSizeTy >::IsSortedCmp ( const TCmp Cmp) const
inline

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

Definition at line 716 of file ds.h.

716  {
717  if (EndI() == BegI()) return true;
718  for (TIter i = BegI(); i != EndI()-1; ++i) {
719  if (Cmp(*(i+1), *i)){return false;} } return true; }
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:552
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:422
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:550
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 539 of file ds.h.

539 {return GetVal(Len()-1);}
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::Last ( )
inline

Returns a reference to the last element of the vector.

Definition at line 541 of file ds.h.

541 {return GetVal(Len()-1);}
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::LastLast ( ) const
inline

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

Definition at line 545 of file ds.h.

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

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

Definition at line 547 of file ds.h.

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

Returns the position of the last element.

Definition at line 543 of file ds.h.

543 {return Len()-1;}
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Len ( ) const
inline

Returns the number of elements in the vector.

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

Definition at line 535 of file ds.h.

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

Definition at line 877 of file ds.h.

877  {
878  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
879  SIn.Load(MxVals); SIn.Load(Vals); MxVals=Vals;
880  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
881  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=TVal(SIn);}
882 }
void Load(bool &Bool)
Definition: fl.h:84
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::LoadXml ( const PXmlTok XmlTok,
const TStr Nm = "" 
)

Definition at line 103 of file xmlser.h.

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

1256  {
1257  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
1258  TVec<TVal, TSizeTy> SortedVec(*this); SortedVec.Sort();
1259  Clr();
1260  for (TSizeTy ValN=0; ValN<SortedVec.Len(); ValN++){
1261  if ((ValN==0)||(SortedVec[ValN-1]!=SortedVec[ValN])){
1262  Add(SortedVec[ValN]);}
1263  }
1264 }
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::MoveFrom ( TVec< TVal, TSizeTy > &  Vec)

Takes over the data and the capacity from Vec.

No memory gets copied and Vec gets destroyed.

Definition at line 1002 of file ds.h.

1002  {
1003  if (this!=&Vec){
1004  if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
1005  MxVals=Vec.MxVals; Vals=Vec.Vals; ValT=Vec.ValT;
1006  Vec.MxVals=0; Vec.Vals=0; Vec.ValT=NULL;
1007  }
1008 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy >
bool TVec< TVal, TSizeTy >::NextPerm ( )

Generates next permutation of the elements in the vector.

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

Definition at line 1267 of file ds.h.

1267  {
1268  // start with a sorted sequence to obtain all permutations
1269  TSizeTy First = 0, Last = Len(), Next = Len()-1;
1270  if (Last < 2) return false;
1271  for(; ; ) {
1272  // find rightmost element smaller than successor
1273  TSizeTy Next1 = Next;
1274  if (GetVal(--Next) < GetVal(Next1)) { // swap with rightmost element that's smaller, flip suffix
1275  TSizeTy Mid = Last;
1276  for (; GetVal(Next) >= GetVal(--Mid); ) { }
1277  Swap(Next, Mid);
1278  Reverse(Next1, Last-1);
1279  return true;
1280  }
1281  if (Next == First) { // pure descending, flip all
1282  Reverse();
1283  return false;
1284  }
1285  }
1286 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:539
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1250
template<class TVal, class TSizeTy = int>
TVec<TVal, TSizeTy>& TVec< TVal, TSizeTy >::operator+ ( const TVal &  Val)
inline

Appends value Val to the vector.

Definition at line 458 of file ds.h.

458 {Add(Val); return *this;}
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<class TVal, class TSizeTy>
bool TVec< TVal, TSizeTy >::operator< ( const TVec< TVal, TSizeTy > &  Vec) const

Lexicographically compares two vectors.

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

Definition at line 912 of file ds.h.

912  {
913  if (this==&Vec){return false;}
914  if (Len()==Vec.Len()){
915  for (TSizeTy ValN=0; ValN<Vals; ValN++){
916  if (ValT[ValN]<Vec.ValT[ValN]){return true;}
917  else if (ValT[ValN]>Vec.ValT[ValN]){return false;}
918  else {}
919  }
920  return false;
921  } else {
922  return Len()<Vec.Len();
923  }
924 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
TVec< TVal, TSizeTy > & TVec< TVal, TSizeTy >::operator= ( const TVec< TVal, TSizeTy > &  Vec)

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

Definition at line 892 of file ds.h.

892  {
893  if (this!=&Vec){
894  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
895  MxVals=Vals=Vec.Vals;
896  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
897  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
898  }
899  return *this;
900 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
bool TVec< TVal, TSizeTy >::operator== ( const TVec< TVal, TSizeTy > &  Vec) const

Checks that the two vectors have the same contents.

Definition at line 903 of file ds.h.

903  {
904  if (this==&Vec){return true;}
905  if (Len()!=Vec.Len()){return false;}
906  for (TSizeTy ValN=0; ValN<Vals; ValN++){
907  if (ValT[ValN]!=Vec.ValT[ValN]){return false;}}
908  return true;
909 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::operator[] ( const TSizeTy &  ValN) const
inline

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

Definition at line 466 of file ds.h.

466  {
467  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
468  return ValT[ValN];}
#define AssertR(Cond, Reason)
Definition: bd.h:258
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:861
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::operator[] ( const TSizeTy &  ValN)
inline

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

Definition at line 470 of file ds.h.

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

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

Definition at line 987 of file ds.h.

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

1186  {
1187  TSizeTy PivotValN=GetPivotValN(MnLValN, MxRValN);
1188  Swap(PivotValN, MnLValN);
1189  TVal PivotVal=ValT[MnLValN];
1190  TSizeTy LValN=MnLValN-1; TSizeTy RValN=MxRValN+1;
1191  forever {
1192  if (Asc){
1193  do {RValN--;} while (ValT[RValN]>PivotVal);
1194  do {LValN++;} while (ValT[LValN]<PivotVal);
1195  } else {
1196  do {RValN--;} while (ValT[RValN]<PivotVal);
1197  do {LValN++;} while (ValT[LValN]>PivotVal);
1198  }
1199  if (LValN<RValN){Swap(LValN, RValN);}
1200  else {return RValN;}
1201  };
1202 }
#define forever
Definition: bd.h:6
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
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:1165
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
template<class TCmp >
static TIter TVec< TVal, TSizeTy >::PartitionCmp ( TIter  BI,
TIter  EI,
const TVal  Pivot,
const TCmp Cmp 
)
inlinestatic

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

Definition at line 686 of file ds.h.

686  {
687  forever {
688  while (Cmp(*BI, Pivot)){++BI;} --EI;
689  while (Cmp(Pivot, *EI)){--EI;}
690  if (!(BI<EI)){return BI;} SwapI(BI, EI); ++BI; } }
#define forever
Definition: bd.h:6
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
static void SwapI(TIter LVal, TIter RVal)
Swaps the elements that iterators LVal and RVal point to.
Definition: ds.h:620
template<class TVal , class TSizeTy >
bool TVec< TVal, TSizeTy >::PrevPerm ( )

Generates previous permutation of the elements in the vector.

Returns false when the first permutation is reached.

Definition at line 1289 of file ds.h.

1289  {
1290  TSizeTy First = 0, Last = Len(), Next = Len()-1;
1291  if (Last < 2) return false;
1292  for(; ; ) {
1293  // find rightmost element not smaller than successor
1294  TSizeTy Next1 = Next;
1295  if (GetVal(--Next) >= GetVal(Next1)) { // swap with rightmost element that's not smaller, flip suffix
1296  TSizeTy Mid = Last;
1297  for (; GetVal(Next) < GetVal(--Mid); ) { }
1298  Swap(Next, Mid);
1299  Reverse(Next1, Last);
1300  return true;
1301  }
1302  if (Next == First) { // pure descending, flip all
1303  Reverse();
1304  return false;
1305  }
1306  }
1307 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:539
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1250
template<class TVal, class TSizeTy >
void TVec< TVal, TSizeTy >::PutAll ( const TVal &  Val)

Sets all elements of the vector to value Val.

Definition at line 1130 of file ds.h.

1130  {
1131  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=Val;}
1132 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy>
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 1205 of file ds.h.

1205  {
1206  if (MnLValN<MxRValN){
1207  if (MxRValN-MnLValN<20){
1208  ISort(MnLValN, MxRValN, Asc);
1209  } else {
1210  TSizeTy SplitValN=Partition(MnLValN, MxRValN, Asc);
1211  QSort(MnLValN, SplitValN, Asc);
1212  QSort(SplitValN+1, MxRValN, Asc);
1213  }
1214  }
1215 }
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1205
void ISort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Insertion sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1148
TSizeTy Partition(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Partitions the values between positions MnLValN...MxLValN.
Definition: ds.h:1186
template<class TVal, class TSizeTy = int>
template<class TCmp >
static void TVec< TVal, TSizeTy >::QSortCmp ( TIter  BI,
TIter  EI,
const TCmp Cmp 
)
inlinestatic

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

Definition at line 705 of file ds.h.

705  {
706  if (BI + 1 < EI) {
707  if (EI - BI < 20) { ISortCmp(BI, EI, Cmp); }
708  else { const TVal Val = *GetPivotValNCmp(BI, EI, Cmp);
709  TIter Split = PartitionCmp(BI, EI, Val, Cmp);
710  QSortCmp(BI, Split, Cmp); QSortCmp(Split, EI, Cmp); } } }
static TIter GetPivotValNCmp(const TIter &BI, const TIter &EI, const TCmp &Cmp)
Picks three random elements at positions BI...EI and returns the middle one under the comparator Cmp...
Definition: ds.h:672
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:422
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:686
static void QSortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Quick sorts the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:705
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:699
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Reserve ( const TSizeTy &  _MxVals)
inline

Reserves enough memory for the vector to store _MxVals elements.

Definition at line 506 of file ds.h.

506 {Resize(_MxVals);}
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:831
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Reserve ( const TSizeTy &  _MxVals,
const TSizeTy &  _Vals 
)
inline

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

Definition at line 508 of file ds.h.

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

Returns the size of allocated storage capacity.

Definition at line 537 of file ds.h.

537 {return MxVals;}
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Resize ( const TSizeTy &  _MxVals = -1)
protected

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

Definition at line 831 of file ds.h.

831  {
832  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());
833  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());
834  if (_MxVals==-1){
835  if (Vals==0){MxVals=16;} else {MxVals*=2;}
836  } else {
837  if (_MxVals<=MxVals){return;} else {MxVals=_MxVals;}
838  }
839  if (MxVals < 0) {
840  MxVals = TInt::Mx-1024;
841  }
842  if (ValT==NULL){
843  try {ValT=new TVal[MxVals];}
844  catch (std::exception Ex){
845  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.]",
846  Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
847  } else {
848  TVal* NewValT = NULL;
849  try {
850  NewValT=new TVal[MxVals];}
851  catch (std::exception Ex){
852  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.]",
853  Ex.what(), TInt::GetStr(Vals).CStr(), TInt::GetStr(MxVals).CStr(), TInt::GetStr(_MxVals).CStr(), GetTypeNm(*this).CStr()).CStr());}
854  IAssert(NewValT!=NULL);
855  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
856  delete[] ValT; ValT=NewValT;
857  }
858 }
#define IAssert(Cond)
Definition: bd.h:262
TStr GetTypeNm(const Type &Var)
Definition: ut.h:16
TStr GetStr() const
Definition: dt.h:1104
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const int Mx
Definition: dt.h:1046
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
#define FailR(Reason)
Definition: bd.h:240
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
char * CStr()
Definition: dt.h:476
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Reverse ( )

Reverses the order of the elements in the vector.

Definition at line 1250 of file ds.h.

1250  {
1251  for (TSizeTy ValN=0; ValN<Vals/2; ValN++){
1252  Swap(ValN, Vals-ValN-1);}
1253 }
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Reverse ( TSizeTy  LValN,
TSizeTy  RValN 
)
inline

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

Definition at line 666 of file ds.h.

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

Definition at line 885 of file ds.h.

885  {
886  if (MxVals!=-1){SOut.Save(MxVals);} else {SOut.Save(Vals);}
887  SOut.Save(Vals);
888  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].Save(SOut);}
889 }
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
void Save(const bool &Bool)
Definition: fl.h:173
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::SaveXml ( TSOut SOut,
const TStr Nm 
) const

Definition at line 113 of file xmlser.h.

113  {
114  XSaveHdArg(Nm, "Vals", TInt::GetStr(Vals));
115  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].SaveXml(SOut, TStr());}
116 }
TStr GetStr() const
Definition: dt.h:1104
#define XSaveHdArg(Nm, ArgNm, ArgVal)
Definition: bd.h:321
Definition: dt.h:412
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::SearchBack ( const TVal &  Val) const

Returns the position of an element with value Val.

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

Definition at line 1447 of file ds.h.

1447  {
1448  for (TSizeTy ValN=Vals-1; ValN>=0; ValN--){
1449  if (Val==ValT[ValN]){return ValN;}}
1450  return -1;
1451 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::SearchBin ( const TVal &  Val) const

Returns the position of an element with value Val.

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

Definition at line 1418 of file ds.h.

1418  {
1419  TSizeTy LValN=0, RValN=Len()-1;
1420  while (RValN>=LValN){
1421  TSizeTy ValN=(LValN+RValN)/2;
1422  if (Val==ValT[ValN]){return ValN;}
1423  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1424  }
1425  return -1;
1426 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::SearchBin ( const TVal &  Val,
TSizeTy &  InsValN 
) const

Returns the position of an element with value Val.

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

Definition at line 1429 of file ds.h.

1429  {
1430  TSizeTy LValN=0, RValN=Len()-1;
1431  while (RValN>=LValN){
1432  TSizeTy ValN=(LValN+RValN)/2;
1433  if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
1434  if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
1435  }
1436  InsValN=LValN; return -1;
1437 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::SearchForw ( const TVal &  Val,
const TSizeTy &  BValN = 0 
) const

Returns the position of an element with value Val.

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

Definition at line 1440 of file ds.h.

1440  {
1441  for (TSizeTy ValN=BValN; ValN<Vals; ValN++){
1442  if (Val==ValT[ValN]){return ValN;}}
1443  return -1;
1444 }
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::SearchVForw ( const TVec< TVal, TSizeTy > &  ValV,
const TSizeTy &  BValN = 0 
) const

Returns the starting position of vector ValV.

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

Definition at line 1454 of file ds.h.

1454  {
1455  TSizeTy ValVLen=ValV.Len();
1456  for (TSizeTy ValN=BValN; ValN<Vals-ValVLen+1; ValN++){
1457  bool Found=true;
1458  for (TSizeTy SubValN=0; SubValN<ValVLen; SubValN++){
1459  if (ValV[SubValN]!=GetVal(ValN+SubValN)){Found=false; break;}
1460  }
1461  if (Found){return ValN;}
1462  }
1463  return -1;
1464 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::SetVal ( const TSizeTy &  ValN,
const TVal &  Val 
)
inline

Sets the value of element at position ValN to Val.

Definition at line 599 of file ds.h.

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

Randomly shuffles the elements of the vector.

Definition at line 1235 of file ds.h.

1235  {
1236  if (Len() < TInt::Mx) {
1237  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1238  const int Range = int(Vals-ValN);
1239  Swap(ValN, ValN+Rnd.GetUniDevInt(Range));
1240  }
1241  } else {
1242  for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
1243  const TSizeTy Range = Vals-ValN;
1244  Swap(ValN, TSizeTy(ValN+Rnd.GetUniDevInt64(Range)));
1245  }
1246  }
1247 }
int64 GetUniDevInt64(const int64 &Range=0)
Definition: dt.cpp:51
static const int Mx
Definition: dt.h:1046
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
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 1218 of file ds.h.

1218  {
1219  QSort(0, Len()-1, Asc);
1220 }
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1205
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
template<class TVal, class TSizeTy = int>
template<class TCmp >
void TVec< TVal, TSizeTy >::SortCmp ( const TCmp Cmp)
inline

Sorts the elements of the vector using the comparator Cmp.

Definition at line 713 of file ds.h.

713 { QSortCmp(BegI(), EndI(), Cmp);}
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:552
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:550
static void QSortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Quick sorts the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:705
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Swap ( TVec< TVal, TSizeTy > &  Vec)

Swaps the contents of the vector with Vec.

Definition at line 1011 of file ds.h.

1011  {
1012  if (this!=&Vec){
1013  ::Swap(MxVals, Vec.MxVals);
1014  ::Swap(Vals, Vec.Vals);
1015  ::Swap(ValT, Vec.ValT);
1016  }
1017 }
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Swap ( const TSizeTy &  ValN1,
const TSizeTy &  ValN2 
)
inline

Swaps elements at positions ValN1 and ValN2.

Definition at line 618 of file ds.h.

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

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

964  {
965  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
966  IAssert((_Vals==-1)||(_Vals>=0));
967  if ((_Vals!=-1)&&(_Vals>=Vals)){
968  return;
969  } else
970  if (((_Vals==-1)&&(Vals==0))||(_Vals==0)){
971  if (ValT!=NULL){delete[] ValT;}
972  MxVals=Vals=0; ValT=NULL;
973  } else {
974  if (_Vals==-1){
975  if (MxVals==Vals){return;} else {MxVals=Vals;}
976  } else {
977  MxVals=Vals=_Vals;
978  }
979  TVal* NewValT=new TVal[MxVals];
980  IAssert(NewValT!=NULL);
981  for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
982  delete[] ValT; ValT=NewValT;
983  }
984 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy MxVals
Vector capacity. Capacity is the size of allocated storage. If MxVals==-1, then ValT is not owned by ...
Definition: ds.h:424
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVal * ValT
Definition: ds.h:426
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Union ( const TVec< TVal, TSizeTy > &  ValV)

Result is the union of this vector with ValV.

Assumes the vectors are sorted!

Definition at line 1317 of file ds.h.

1317  {
1318  TVec<TVal, TSizeTy> UnionVec;
1319  Union(ValV, UnionVec);
1320  MoveFrom(UnionVec);
1321 }
void Union(const TVec< TVal, TSizeTy > &ValV)
Result is the union of this vector with ValV.
Definition: ds.h:1317
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1002
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Union ( const TVec< TVal, TSizeTy > &  ValV,
TVec< TVal, TSizeTy > &  DstValV 
) const

DstValV is the union of vectors this and ValV.

Assumes the vectors are sorted!

Definition at line 1345 of file ds.h.

1345  {
1346  DstValV.Gen(TInt::GetMx(Len(), ValV.Len()), 0);
1347  TSizeTy ValN1=0, ValN2=0;
1348  while ((ValN1<Len())&&(ValN2<ValV.Len())){
1349  const TVal& Val1=GetVal(ValN1);
1350  const TVal& Val2=ValV.GetVal(ValN2);
1351  if (Val1<Val2){DstValV.Add(Val1); ValN1++;}
1352  else if (Val1>Val2){DstValV.Add(Val2); ValN2++;}
1353  else {DstValV.Add(Val1); ValN1++; ValN2++;}
1354  }
1355  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
1356  DstValV.Add(GetVal(RestValN1));}
1357  for (TSizeTy RestValN2=ValN2; RestValN2<ValV.Len(); RestValN2++){
1358  DstValV.Add(ValV.GetVal(RestValN2));}
1359 }
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1089
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::UnionLen ( const TVec< TVal, TSizeTy > &  ValV) const

Returns the size of the union of vectors this and ValV.

Assumes both vectors are sorted in ascending order!

Definition at line 1392 of file ds.h.

1392  {
1393  TSizeTy Cnt = 0, ValN1 = 0, ValN2 = 0;
1394  while ((ValN1 < Len()) && (ValN2 < ValV.Len())) {
1395  const TVal& Val1 = GetVal(ValN1);
1396  const TVal& Val2 = ValV.GetVal(ValN2);
1397  if (Val1 < Val2) {
1398  Cnt++; ValN1++;
1399  } else if (Val1 > Val2) {
1400  Cnt++; ValN2++;
1401  } else {
1402  Cnt++; ValN1++; ValN2++;
1403  }
1404  }
1405  Cnt += (Len() - ValN1) + (ValV.Len() - ValN2);
1406  return Cnt;
1407 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595

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 424 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 425 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 426 of file ds.h.


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