SNAP Library 2.2, User Reference  2014-03-11 19:15:55
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes
TVec< TVal, TSizeTy > Class Template Reference

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

#include <ds.h>

List of all members.

Public Types

typedef TVal * TIter
 Random access iterator to TVal.

Public Member Functions

 TVec ()
 TVec (const TVec< TVal, TSizeTy > &Vec)
 TVec (const TSizeTy &_Vals)
 Constructs a vector (an array) of length _Vals.
 TVec (const TSizeTy &_MxVals, const TSizeTy &_Vals)
 Constructs a vector (an array) of length _Vals, while reserving enough memory to store _MxVals elements.
 TVec (TVal *_ValT, const TSizeTy &_Vals)
 Constructs a vector of _Vals elements of memory array _ValT.
 ~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.
TVec< TVal, TSizeTy > & operator+ (const TVal &Val)
 Appends value Val to the vector.
bool operator== (const TVec< TVal, TSizeTy > &Vec) const
 Checks that the two vectors have the same contents.
bool operator< (const TVec< TVal, TSizeTy > &Vec) const
 Lexicographically compares two vectors.
const TVal & operator[] (const TSizeTy &ValN) const
 Returns a reference to the element at position ValN in the vector.
TVal & operator[] (const TSizeTy &ValN)
 Returns a reference to the element at position ValN in the vector.
TSizeTy GetMemUsed () const
 Returns the memory footprint (the number of bytes) of the vector.
TSizeTy GetMemSize () const
 Returns the memory size (the number of bytes) of a binary representation.
int GetPrimHashCd () const
 Returns primary hash code of the vector. Used by THash.
int GetSecHashCd () const
 Returns secondary hash code of the vector. Used by THash.
void Gen (const TSizeTy &_Vals)
 Constructs a vector (an array) of _Vals elements.
void Gen (const TSizeTy &_MxVals, const TSizeTy &_Vals)
 Constructs a vector (an array) of _Vals elements, while reserving enough memory for _MxVals elements.
void GenExt (TVal *_ValT, const TSizeTy &_Vals)
 Constructs a vector of _Vals elements of memory array _ValT.
bool IsExt () const
 Returns true if the vector was created using the GenExt().
void Reserve (const TSizeTy &_MxVals)
 Reserves enough memory for the vector to store _MxVals elements.
void Reserve (const TSizeTy &_MxVals, const TSizeTy &_Vals)
 Reserves enough memory for the vector to store _MxVals elements and sets its length to _Vals.
void Clr (const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
 Clears the contents of the vector.
void Trunc (const TSizeTy &_Vals=-1)
 Truncates the vector's length and capacity to _Vals elements.
void Pack ()
 The vector reduces its capacity (frees memory) to match its size.
void MoveFrom (TVec< TVal, TSizeTy > &Vec)
 Takes over the data and the capacity from Vec.
void Swap (TVec< TVal, TSizeTy > &Vec)
 Swaps the contents of the vector with Vec.
bool Empty () const
 Tests whether the vector is empty.
TSizeTy Len () const
 Returns the number of elements in the vector.
TSizeTy Reserved () const
 Returns the size of allocated storage capacity.
const TVal & Last () const
 Returns a reference to the last element of the vector.
TVal & Last ()
 Returns a reference to the last element of the vector.
TSizeTy LastValN () const
 Returns the position of the last element.
const TVal & LastLast () const
 Returns a reference to the one before last element of the vector.
TVal & LastLast ()
 Returns a reference to the one before last element of the vector.
TIter BegI () const
 Returns an iterator pointing to the first element in the vector.
TIter EndI () const
 Returns an iterator referring to the past-the-end element in the vector.
TIter GetI (const TSizeTy &ValN) const
 Returns an iterator an element at position ValN.
TSizeTy Add ()
 Adds a new element at the end of the vector, after its current last element.
TSizeTy Add (const TVal &Val)
 Adds a new element at the end of the vector, after its current last element.
TSizeTy Add (TVal &Val)
TSizeTy Add (const TVal &Val, const TSizeTy &ResizeLen)
 Adds element Val at the end of the vector. #TVec::Add2.
TSizeTy AddV (const TVec< TVal, TSizeTy > &ValV)
 Adds the elements of the vector ValV to the to end of the vector.
TSizeTy AddSorted (const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
 Adds element Val to a sorted vector.
TSizeTy AddBackSorted (const TVal &Val, const bool &Asc)
 Adds element Val to a sorted vector.
TSizeTy AddMerged (const TVal &Val)
 Adds element Val to a sorted vector only if the element Val is not already in the vector.
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.
TSizeTy AddUnique (const TVal &Val)
 Adds element Val to a vector only if the element Val is not already in the vector.
const TVal & GetVal (const TSizeTy &ValN) const
 Returns a reference to the element at position ValN in the vector.
TVal & GetVal (const TSizeTy &ValN)
 Returns a reference to the element at position ValN in the vector.
void SetVal (const TSizeTy &ValN, const TVal &Val)
 Sets the value of element at position ValN to Val.
void GetSubValV (const TSizeTy &BValN, const TSizeTy &EValN, TVec< TVal, TSizeTy > &ValV) const
 Returns a vector on elements at positions BValN...EValN.
void Ins (const TSizeTy &ValN, const TVal &Val)
 Inserts new element Val before the element at position ValN.
void Del (const TSizeTy &ValN)
 Removes the element at position ValN.
void Del (const TSizeTy &MnValN, const TSizeTy &MxValN)
 Removes the elements at positions MnValN...MxValN.
void DelLast ()
 Removes the last element of the vector.
bool DelIfIn (const TVal &Val)
 Removes the first occurrence of element Val.
void DelAll (const TVal &Val)
 Removes all occurrences of element Val.
void PutAll (const TVal &Val)
 Sets all elements of the vector to value Val.
void Swap (const TSizeTy &ValN1, const TSizeTy &ValN2)
 Swaps elements at positions ValN1 and ValN2.
bool NextPerm ()
 Generates next permutation of the elements in the vector.
bool PrevPerm ()
 Generates previous permutation of the elements in the vector.
TSizeTy GetPivotValN (const TSizeTy &LValN, const TSizeTy &RValN) const
 Picks three random elements at positions LValN...RValN and returns the middle one.
void BSort (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
 Bubble sorts the values between positions MnLValN...MxLValN.
void ISort (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
 Insertion sorts the values between positions MnLValN...MxLValN.
TSizeTy Partition (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
 Partitions the values between positions MnLValN...MxLValN.
void QSort (const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
 Quick sorts the values between positions MnLValN...MxLValN.
void Sort (const bool &Asc=true)
 Sorts the elements of the vector.
bool IsSorted (const bool &Asc=true) const
 Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order.
void Shuffle (TRnd &Rnd)
 Randomly shuffles the elements of the vector.
void Reverse ()
 Reverses the order of the elements in the vector.
void Reverse (TSizeTy LValN, TSizeTy RValN)
 Reverses the order of elements between LValN...RValN.
void Merge ()
 Sorts the vector and only keeps a single element of each value.
template<class TCmp >
void SortCmp (const TCmp &Cmp)
 Sorts the elements of the vector using the comparator Cmp.
template<class TCmp >
bool IsSortedCmp (const TCmp &Cmp) const
 Checks whether the vector is sorted according to the comparator Cmp.
void Intrs (const TVec< TVal, TSizeTy > &ValV)
 Result is the intersection of this vector with ValV.
void Union (const TVec< TVal, TSizeTy > &ValV)
 Result is the union of this vector with ValV.
void Diff (const TVec< TVal, TSizeTy > &ValV)
 Subtracts ValV from this vector.
void Intrs (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
 DstValV is the intersection of vectors this and ValV.
void Union (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
 DstValV is the union of vectors this and ValV.
void Diff (const TVec< TVal, TSizeTy > &ValV, TVec< TVal, TSizeTy > &DstValV) const
 DstValV is the difference of vectors this and ValV.
TSizeTy IntrsLen (const TVec< TVal, TSizeTy > &ValV) const
 Returns the size of the intersection of vectors this and ValV.
TSizeTy UnionLen (const TVec< TVal, TSizeTy > &ValV) const
 Returns the size of the union of vectors this and ValV.
TSizeTy Count (const TVal &Val) const
 Counts the number of occurrences of Val in the vector.
TSizeTy SearchBin (const TVal &Val) const
 Returns the position of an element with value Val.
TSizeTy SearchBin (const TVal &Val, TSizeTy &InsValN) const
 Returns the position of an element with value Val.
TSizeTy SearchForw (const TVal &Val, const TSizeTy &BValN=0) const
 Returns the position of an element with value Val.
TSizeTy SearchBack (const TVal &Val) const
 Returns the position of an element with value Val.
TSizeTy SearchVForw (const TVec< TVal, TSizeTy > &ValV, const TSizeTy &BValN=0) const
 Returns the starting position of vector ValV.
bool IsIn (const TVal &Val) const
 Checks whether element Val is a member of the vector.
bool IsIn (const TVal &Val, TSizeTy &ValN) const
 Checks whether element Val is a member of the vector.
bool IsInBin (const TVal &Val) const
 Checks whether element Val is a member of the vector.
const TVal & GetDat (const TVal &Val) const
 Returns reference to the first occurrence of element Val.
TVal & GetAddDat (const TVal &Val)
 Returns reference to the first occurrence of element Val.
TSizeTy GetMxValN () const
 Returns the position of the largest element in the vector.

Static Public Member Functions

static void SwapI (TIter LVal, TIter RVal)
 Swaps the elements that iterators LVal and RVal point to.
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.
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.
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.
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.
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.
static TVec< TVal, TSizeTy > GetV (const TVal &Val1)
 Returns a vector on element Val1.
static TVec< TVal, TSizeTy > GetV (const TVal &Val1, const TVal &Val2)
 Returns a vector on elements Val1, Val2.
static TVec< TVal, TSizeTy > GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3)
 Returns a vector on elements Val1...Val3.
static TVec< TVal, TSizeTy > GetV (const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4)
 Returns a vector on elements Val1...Val4.
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.
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.
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.
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.
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.

Protected Member Functions

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

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.
TSizeTy Vals
 Vector length. Length is the number of elements stored in the vector.
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.

: MxVals(0), Vals(0), ValT(NULL){}
template<class TVal, class TSizeTy>
TVec< TVal, TSizeTy >::TVec ( const TVec< TVal, TSizeTy > &  Vec)

Definition at line 870 of file ds.h.

                                                       {
  MxVals=Vec.MxVals; Vals=Vec.Vals;
  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
  for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
}
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( const TSizeTy &  _Vals) [inline, explicit]

Constructs a vector (an array) of length _Vals.

Definition at line 435 of file ds.h.

                                     {
    IAssert(0<=_Vals); MxVals=Vals=_Vals;
    if (_Vals==0){ValT=NULL;} else {ValT=new TVal[_Vals];}}
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( const TSizeTy &  _MxVals,
const TSizeTy &  _Vals 
) [inline]

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

Definition at line 439 of file ds.h.

                                                    {
    IAssert((0<=_Vals)&&(_Vals<=_MxVals)); MxVals=_MxVals; Vals=_Vals;
    if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( TVal *  _ValT,
const TSizeTy &  _Vals 
) [inline, explicit]

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.

                                                  :
    MxVals(-1), Vals(_Vals), ValT(_ValT){}
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::~TVec ( ) [inline]

Definition at line 448 of file ds.h.

{if ((ValT!=NULL) && (MxVals!=-1)){delete[] ValT;}}
template<class TVal, class TSizeTy = int>
TVec< TVal, TSizeTy >::TVec ( TSIn &  SIn) [inline, explicit]

Definition at line 449 of file ds.h.

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

Member Function Documentation

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

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

This increases the vector size by one.

Definition at line 559 of file ds.h.

               { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize();} return Vals++;}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Add ( const TVal &  Val) [inline]

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

The content of Val is copied to the new element.

Definition at line 564 of file ds.h.

                              { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Add ( TVal &  Val) [inline]

Definition at line 566 of file ds.h.

                        { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize();} ValT[Vals]=Val; return Vals++;}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Add ( const TVal &  Val,
const TSizeTy &  ResizeLen 
) [inline]

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

Definition at line 569 of file ds.h.

                                                        { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    if (Vals==MxVals){Resize(MxVals+ResizeLen);} ValT[Vals]=Val; return Vals++;}
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::AddBackSorted ( const TVal &  Val,
const bool &  Asc 
)

Adds element Val to a sorted vector.

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

Definition at line 1042 of file ds.h.

                                                                          {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Add();
  TSizeTy ValN=Vals-2;
  while ((ValN>=0)&&((Asc&&(Val<ValT[ValN]))||(!Asc&&(Val>ValT[ValN])))){
    ValT[ValN+1]=ValT[ValN]; ValN--;}
  ValT[ValN+1]=Val;
  return ValN+1;
}
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::AddMerged ( const TVal &  Val)

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

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

Definition at line 1053 of file ds.h.

                                                     {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=SearchBin(Val);
  if (ValN==-1){return AddSorted(Val);}
  else {GetVal(ValN)=Val; return -1;}
}
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::AddSorted ( const TVal &  Val,
const bool &  Asc = true,
const TSizeTy &  _MxVals = -1 
)

Adds element Val to a sorted vector.

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

Definition at line 1027 of file ds.h.

                                                                                              {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=Add(Val);
  if (Asc){
    while ((ValN>0)&&(ValT[ValN]<ValT[ValN-1])){
      Swap(ValN, ValN-1); ValN--;}
  } else {
    while ((ValN>0)&&(ValT[ValN]>ValT[ValN-1])){
      Swap(ValN, ValN-1); ValN--;}
  }
  if ((_MxVals!=-1)&&(Len()>_MxVals)){Del(_MxVals, Len()-1);}
  return ValN;
}
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::AddUnique ( const TVal &  Val)

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

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

Definition at line 1068 of file ds.h.

                                                     {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=SearchForw(Val);
  if (ValN==-1){return Add(Val);}
  else {GetVal(ValN)=Val; return -1;}
}
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::AddV ( const TVec< TVal, TSizeTy > &  ValV)

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

Definition at line 1020 of file ds.h.

                                                                {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){Add(ValV[ValN]);}
  return Len();
}
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::AddVMerged ( const TVec< TVal, TSizeTy > &  ValV)

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

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

Definition at line 1061 of file ds.h.

                                                                      {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  for (TSizeTy ValN=0; ValN<ValV.Vals; ValN++){AddMerged(ValV[ValN]);}
  return Len();
}
template<class TVal, class TSizeTy = int>
TIter TVec< TVal, TSizeTy >::BegI ( ) const [inline]

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

Definition at line 550 of file ds.h.

{return ValT;}
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::BSort ( const TSizeTy &  MnLValN,
const TSizeTy &  MxRValN,
const bool &  Asc 
)

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

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

Definition at line 1135 of file ds.h.

                                                                                              {
  for (TSizeTy ValN1=MnLValN; ValN1<=MxRValN; ValN1++){
    for (TSizeTy ValN2=MxRValN; ValN2>ValN1; ValN2--){
      if (Asc){
        if (ValT[ValN2]<ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
      } else {
        if (ValT[ValN2]>ValT[ValN2-1]){Swap(ValN2, ValN2-1);}
      }
    }
  }
}
template<class TVal, class TSizeTy = int>
template<class TCmp >
static void TVec< TVal, TSizeTy >::BSortCmp ( TIter  BI,
TIter  EI,
const TCmp &  Cmp 
) [inline, static]

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

Definition at line 693 of file ds.h.

                                                            {
    for (TIter i = BI; i != EI; ++i) {
      for (TIter j = EI-1; j != i; --j) {
        if (Cmp(*j, *(j-1))) { SwapI(j, j-1); } } } }
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Clr ( const bool &  DoDel = true,
const TSizeTy &  NoDelLim = -1 
)

Clears the contents of the vector.

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

Definition at line 953 of file ds.h.

                                                                       {
  if ((DoDel)||((!DoDel)&&(NoDelLim!=-1)&&(MxVals>NoDelLim))){
    if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
    MxVals=Vals=0; ValT=NULL;
  } else {
    IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!"); 
    Vals=0;
  }
}
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::Count ( const TVal &  Val) const

Counts the number of occurrences of Val in the vector.

Definition at line 1410 of file ds.h.

                                                        {
  TSizeTy Count = 0;
  for (TSizeTy i = 0; i < Len(); i++){
    if (Val == ValT[i]){Count++;}}
  return Count;
}
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Del ( const TSizeTy &  ValN)

Removes the element at position ValN.

Definition at line 1094 of file ds.h.

                                                {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Assert((0<=ValN)&&(ValN<Vals));
  for (TSizeTy MValN=ValN+1; MValN<Vals; MValN++){
    ValT[MValN-1]=ValT[MValN];}
  ValT[--Vals]=TVal();
}
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Del ( const TSizeTy &  MnValN,
const TSizeTy &  MxValN 
)

Removes the elements at positions MnValN...MxValN.

Definition at line 1103 of file ds.h.

                                                                         {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Assert((0<=MnValN)&&(MnValN<Vals)&&(0<=MxValN)&&(MxValN<Vals));
  Assert(MnValN<=MxValN);
  for (TSizeTy ValN=MxValN+1; ValN<Vals; ValN++){
    ValT[MnValN+ValN-MxValN-1]=ValT[ValN];}
  for (TSizeTy ValN=Vals-MxValN+MnValN-1; ValN<Vals; ValN++){
    ValT[ValN]=TVal();}
  Vals-=MxValN-MnValN+1;
}
template<class TVal, class TSizeTy >
void TVec< TVal, TSizeTy >::DelAll ( const TVal &  Val)

Removes all occurrences of element Val.

Definition at line 1123 of file ds.h.

                                               {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN;
  while ((ValN=SearchForw(Val))!=-1){Del(ValN);}
}
template<class TVal, class TSizeTy >
bool TVec< TVal, TSizeTy >::DelIfIn ( const TVal &  Val)

Removes the first occurrence of element Val.

Definition at line 1115 of file ds.h.

                                                {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TSizeTy ValN=SearchForw(Val);
  if (ValN!=-1){Del(ValN); return true;}
  else {return false;}
}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::DelLast ( ) [inline]

Removes the last element of the vector.

Definition at line 609 of file ds.h.

{Del(Len()-1);}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Diff ( const TVec< TVal, TSizeTy > &  ValV)

Subtracts ValV from this vector.

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

Definition at line 1324 of file ds.h.

                                                             {
  TVec<TVal, TSizeTy> DiffVec;
  Diff(ValV, DiffVec);
  MoveFrom(DiffVec);
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Diff ( const TVec< TVal, TSizeTy > &  ValV,
TVec< TVal, TSizeTy > &  DstValV 
) const

DstValV is the difference of vectors this and ValV.

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

Definition at line 1362 of file ds.h.

                                                                                                  {
  DstValV.Clr();
  TSizeTy ValN1=0, ValN2=0;
  while (ValN1<Len() && ValN2<ValV.Len()) {
    const TVal& Val1 = GetVal(ValN1);
    while (ValN2<ValV.Len() && Val1>ValV.GetVal(ValN2)) ValN2++;
    if (ValN2<ValV.Len()) {
      if (Val1!=ValV.GetVal(ValN2)) { DstValV.Add(Val1); }
      ValN1++;
    }
  }
  for (TSizeTy RestValN1=ValN1; RestValN1<Len(); RestValN1++){
    DstValV.Add(GetVal(RestValN1));}
}
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::Empty ( ) const [inline]

Tests whether the vector is empty.

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

Definition at line 530 of file ds.h.

{return Vals==0;}
template<class TVal, class TSizeTy = int>
TIter TVec< TVal, TSizeTy >::EndI ( ) const [inline]

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

Definition at line 552 of file ds.h.

{return ValT+Vals;}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Gen ( const TSizeTy &  _Vals) [inline]

Constructs a vector (an array) of _Vals elements.

Definition at line 486 of file ds.h.

                                { IAssert(0<=_Vals);
    if (ValT!=NULL && MxVals!=-1){delete[] ValT;} MxVals=Vals=_Vals;
    if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Gen ( const TSizeTy &  _MxVals,
const TSizeTy &  _Vals 
) [inline]

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

Definition at line 490 of file ds.h.

                                                        { IAssert((0<=_Vals)&&(_Vals<=_MxVals));
    if (ValT!=NULL  && MxVals!=-1){delete[] ValT;} MxVals=_MxVals; Vals=_Vals;
    if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::GenExt ( TVal *  _ValT,
const TSizeTy &  _Vals 
) [inline]

Constructs a vector of _Vals elements of memory array _ValT.

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

Definition at line 497 of file ds.h.

                                                {
    if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
    MxVals=-1; Vals=_Vals; ValT=_ValT;}
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::GetAddDat ( const TVal &  Val) [inline]

Returns reference to the first occurrence of element Val.

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

Definition at line 796 of file ds.h.

                                  { AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
    const TSizeTy ValN=SearchForw(Val); if (ValN==-1){Add(Val); return Last();} else {return GetVal(ValN);}}
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::GetDat ( const TVal &  Val) const [inline]

Returns reference to the first occurrence of element Val.

Definition at line 792 of file ds.h.

{ return GetVal(SearchForw(Val));}
template<class TVal, class TSizeTy = int>
TIter TVec< TVal, TSizeTy >::GetI ( const TSizeTy &  ValN) const [inline]

Returns an iterator an element at position ValN.

Definition at line 554 of file ds.h.

{return ValT+ValN;}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::GetMemSize ( ) const [inline]

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

Definition at line 477 of file ds.h.

                             {
    return TSizeTy(2*sizeof(TVal)+sizeof(TSizeTy)*Vals);}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::GetMemUsed ( ) const [inline]

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

Definition at line 474 of file ds.h.

                             {
    return TSizeTy(2*sizeof(TSizeTy)+sizeof(TVal*)+MxVals*sizeof(TVal));}
template<class TVal , class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::GetMxValN ( ) const

Returns the position of the largest element in the vector.

Definition at line 1467 of file ds.h.

                                             {
  if (Vals==0){return -1;}
  TSizeTy MxValN=0;
  for (TSizeTy ValN=1; ValN<Vals; ValN++){
    if (ValT[ValN]>ValT[MxValN]){MxValN=ValN;}
  }
  return MxValN;
}
template<class TVal , class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::GetPivotValN ( const TSizeTy &  LValN,
const TSizeTy &  RValN 
) const

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

Definition at line 1165 of file ds.h.

                                                                                          {
  TSizeTy SubVals=RValN-LValN+1;
  if (SubVals > TInt::Mx-1) { SubVals = TInt::Mx-1; }
  const TSizeTy ValN1=LValN+TInt::GetRnd(int(SubVals));
  const TSizeTy ValN2=LValN+TInt::GetRnd(int(SubVals));
  const TSizeTy ValN3=LValN+TInt::GetRnd(int(SubVals));
  const TVal& Val1=ValT[ValN1];
  const TVal& Val2=ValT[ValN2];
  const TVal& Val3=ValT[ValN3];
  if (Val1<Val2){
    if (Val2<Val3){return ValN2;}
    else if (Val3<Val1){return ValN1;}
    else {return ValN3;}
  } else {
    if (Val1<Val3){return ValN1;}
    else if (Val3<Val2){return ValN2;}
    else {return ValN3;}
  }
}
template<class TVal, class TSizeTy = int>
template<class TCmp >
static TIter TVec< TVal, TSizeTy >::GetPivotValNCmp ( const TIter &  BI,
const TIter &  EI,
const TCmp &  Cmp 
) [inline, static]

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

Definition at line 672 of file ds.h.

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

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

Definition at line 930 of file ds.h.

                                             {
  int hc = 0;
  for (TSizeTy i=0; i<Vals; i++){
    hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetPrimHashCd()); 
  }
  return hc; 
}
template<class TVal , class TSizeTy >
int TVec< TVal, TSizeTy >::GetSecHashCd ( ) const

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

Definition at line 942 of file ds.h.

                                            {
  int hc = 0;
  for (TSizeTy i=0; i<Vals; i++){
    hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetSecHashCd()); 
  }
  if (Vals > 0) { 
    hc = TPairHashImpl::GetHashCd(hc, ValT[0].GetSecHashCd()); }
  return hc; 
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::GetSubValV ( const TSizeTy &  BValN,
const TSizeTy &  EValN,
TVec< TVal, TSizeTy > &  ValV 
) const

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

Definition at line 1076 of file ds.h.

                                                                                                                     {
  const TSizeTy BValN=TInt::GetInRng(_BValN, 0, Len()-1);
  const TSizeTy EValN=TInt::GetInRng(_EValN, 0, Len()-1);
  const TSizeTy SubVals=TInt::GetMx(0, EValN-BValN+1);
  SubValV.Gen(SubVals, 0);
  for (TSizeTy ValN=BValN; ValN<=EValN; ValN++){
    SubValV.Add(GetVal(ValN));}
}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1) [inline, static]

Returns a vector on element Val1.

Definition at line 802 of file ds.h.

                                                   {
    TVec<TVal, TSizeTy> V(1, 0); V.Add(Val1); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2 
) [inline, static]

Returns a vector on elements Val1, Val2.

Definition at line 805 of file ds.h.

                                                                     {
    TVec<TVal, TSizeTy> V(2, 0); V.Add(Val1); V.Add(Val2); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3 
) [inline, static]

Returns a vector on elements Val1...Val3.

Definition at line 808 of file ds.h.

                                                                                       {
    TVec<TVal, TSizeTy> V(3, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4 
) [inline, static]

Returns a vector on elements Val1...Val4.

Definition at line 811 of file ds.h.

                                                                                                         {
    TVec<TVal, TSizeTy> V(4, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5 
) [inline, static]

Returns a vector on elements Val1...Val5.

Definition at line 814 of file ds.h.

                                                                                                                           {
    TVec<TVal, TSizeTy> V(5, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6 
) [inline, static]

Returns a vector on elements Val1...Val6.

Definition at line 817 of file ds.h.

                                                                                                                                             {
    TVec<TVal, TSizeTy> V(6, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6,
const TVal &  Val7 
) [inline, static]

Returns a vector on elements Val1...Val7.

Definition at line 820 of file ds.h.

                                                                                                                                                               {
    TVec<TVal, TSizeTy> V(7, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6,
const TVal &  Val7,
const TVal &  Val8 
) [inline, static]

Returns a vector on elements Val1...Val8.

Definition at line 823 of file ds.h.

                                                                                                                                                                                 {
    TVec<TVal, TSizeTy> V(8, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); V.Add(Val8); return V;}
template<class TVal, class TSizeTy = int>
static TVec<TVal, TSizeTy> TVec< TVal, TSizeTy >::GetV ( const TVal &  Val1,
const TVal &  Val2,
const TVal &  Val3,
const TVal &  Val4,
const TVal &  Val5,
const TVal &  Val6,
const TVal &  Val7,
const TVal &  Val8,
const TVal &  Val9 
) [inline, static]

Returns a vector on elements Val1...Val9.

Definition at line 826 of file ds.h.

                                                                                                                                                                                                   {
    TVec<TVal, TSizeTy> V(9, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); V.Add(Val6); V.Add(Val7); V.Add(Val8); V.Add(Val9); return V;}
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::GetVal ( const TSizeTy &  ValN) const [inline]

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

Definition at line 595 of file ds.h.

{return operator[](ValN);}
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::GetVal ( const TSizeTy &  ValN) [inline]

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

Definition at line 597 of file ds.h.

{return operator[](ValN);}
template<class TVal , class TSizeTy>
TStr TVec< TVal, TSizeTy >::GetXOutOfBoundsErrMsg ( const TSizeTy &  ValN) const [protected]

Constructs the out of bounds error message.

Definition at line 861 of file ds.h.

                                                                         {
  return TStr()+
  "Index:"+TInt::GetStr(ValN)+
  " Vals:"+TInt::GetStr(Vals)+
  " MxVals:"+TInt::GetStr(MxVals)+
  " Type:"+GetTypeNm(*this);
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Ins ( const TSizeTy &  ValN,
const TVal &  Val 
)

Inserts new element Val before the element at position ValN.

Definition at line 1086 of file ds.h.

                                                                 {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  Add();  Assert((0<=ValN)&&(ValN<Vals));
  for (TSizeTy MValN=Vals-2; MValN>=ValN; MValN--){ValT[MValN+1]=ValT[MValN];}
  ValT[ValN]=Val;
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Intrs ( const TVec< TVal, TSizeTy > &  ValV)

Result is the intersection of this vector with ValV.

Assumes the vectors are sorted!

Definition at line 1310 of file ds.h.

                                                              {
  TVec<TVal, TSizeTy> IntrsVec;
  Intrs(ValV, IntrsVec);
  MoveFrom(IntrsVec);
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Intrs ( const TVec< TVal, TSizeTy > &  ValV,
TVec< TVal, TSizeTy > &  DstValV 
) const

DstValV is the intersection of vectors this and ValV.

Assumes the vectors are sorted!

Definition at line 1331 of file ds.h.

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

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

Assumes both vectors are sorted in ascending order!

Definition at line 1378 of file ds.h.

                                                                           {
  TSizeTy Cnt=0, ValN1=0, ValN2=0;
  while ((ValN1<Len())&&(ValN2<ValV.Len())){
    const TVal& Val1=GetVal(ValN1);
    while ((ValN2<ValV.Len())&&(Val1>ValV.GetVal(ValN2))){
      ValN2++;}
    if ((ValN2<ValV.Len())&&(Val1==ValV.GetVal(ValN2))){
      ValN2++; Cnt++;}
    ValN1++;
  }
  return Cnt;
}
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsExt ( ) const [inline]

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

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

Definition at line 504 of file ds.h.

{return MxVals==-1;}
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsIn ( const TVal &  Val) const [inline]

Checks whether element Val is a member of the vector.

Definition at line 782 of file ds.h.

{return SearchForw(Val)!=-1;}
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsIn ( const TVal &  Val,
TSizeTy &  ValN 
) const [inline]

Checks whether element Val is a member of the vector.

Position of Val is returned in ValN.

Definition at line 786 of file ds.h.

{ ValN=SearchForw(Val); return ValN!=-1;}
template<class TVal, class TSizeTy = int>
bool TVec< TVal, TSizeTy >::IsInBin ( const TVal &  Val) const [inline]

Checks whether element Val is a member of the vector.

Uses binary search and thus assumes the vector is sorted.

Definition at line 790 of file ds.h.

{return SearchBin(Val)!=-1;}
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::ISort ( const TSizeTy &  MnLValN,
const TSizeTy &  MxRValN,
const bool &  Asc 
)

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

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

Definition at line 1148 of file ds.h.

                                                                                              {
  if (MnLValN<MxRValN){
    for (TSizeTy ValN1=MnLValN+1; ValN1<=MxRValN; ValN1++){
      TVal Val=ValT[ValN1]; TSizeTy ValN2=ValN1;
      if (Asc){
        while ((ValN2>MnLValN)&&(ValT[ValN2-1]>Val)){
          ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
      } else {
        while ((ValN2>MnLValN)&&(ValT[ValN2-1]<Val)){
          ValT[ValN2]=ValT[ValN2-1]; ValN2--;}
      }
      ValT[ValN2]=Val;
    }
  }
}
template<class TVal, class TSizeTy = int>
template<class TCmp >
static void TVec< TVal, TSizeTy >::ISortCmp ( TIter  BI,
TIter  EI,
const TCmp &  Cmp 
) [inline, static]

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

Definition at line 699 of file ds.h.

                                                            {
    if (BI + 1 < EI) {
      for (TIter i = BI, j; i != EI; ++i) { TVal Tmp=*i;  j=i;
        while (j > BI && Cmp(Tmp, *(j-1))) { *j = *(j-1); --j; } *j=Tmp; } } }
template<class TVal , class TSizeTy >
bool TVec< TVal, TSizeTy >::IsSorted ( const bool &  Asc = true) const

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

Definition at line 1223 of file ds.h.

                                                        {
  if (Asc){
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      if (ValT[ValN]>ValT[ValN+1]){return false;}}
  } else {
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      if (ValT[ValN]<ValT[ValN+1]){return false;}}
  }
  return true;
}
template<class TVal, class TSizeTy = int>
template<class TCmp >
bool TVec< TVal, TSizeTy >::IsSortedCmp ( const TCmp &  Cmp) const [inline]

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

Definition at line 716 of file ds.h.

                                          {
    if (EndI() == BegI()) return true;
    for (TIter i = BegI(); i != EndI()-1; ++i) {
      if (Cmp(*(i+1), *i)){return false;} } return true; }
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::Last ( ) const [inline]

Returns a reference to the last element of the vector.

Definition at line 539 of file ds.h.

{return GetVal(Len()-1);}
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::Last ( ) [inline]

Returns a reference to the last element of the vector.

Definition at line 541 of file ds.h.

{return GetVal(Len()-1);}
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::LastLast ( ) const [inline]

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

Definition at line 545 of file ds.h.

{ AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::LastLast ( ) [inline]

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

Definition at line 547 of file ds.h.

{ AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::LastValN ( ) const [inline]

Returns the position of the last element.

Definition at line 543 of file ds.h.

{return Len()-1;}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Len ( ) const [inline]

Returns the number of elements in the vector.

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

Definition at line 535 of file ds.h.

{return Vals;}
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Load ( TSIn &  SIn)

Definition at line 877 of file ds.h.

                                       {
  if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
  SIn.Load(MxVals); SIn.Load(Vals); MxVals=Vals;
  if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=TVal(SIn);}
}
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::LoadXml ( const PXmlTok &  XmlTok,
const TStr &  Nm = "" 
)

Definition at line 103 of file xmlser.h.

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

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

Definition at line 1256 of file ds.h.

                               {
  AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  TVec<TVal, TSizeTy> SortedVec(*this); SortedVec.Sort();
  Clr();
  for (TSizeTy ValN=0; ValN<SortedVec.Len(); ValN++){
    if ((ValN==0)||(SortedVec[ValN-1]!=SortedVec[ValN])){
      Add(SortedVec[ValN]);}
  }
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::MoveFrom ( TVec< TVal, TSizeTy > &  Vec)

Takes over the data and the capacity from Vec.

No memory gets copied and Vec gets destroyed.

Definition at line 1002 of file ds.h.

                                                          {
  if (this!=&Vec){
    if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
    MxVals=Vec.MxVals; Vals=Vec.Vals; ValT=Vec.ValT;
    Vec.MxVals=0; Vec.Vals=0; Vec.ValT=NULL;
  }
}
template<class TVal , class TSizeTy >
bool TVec< TVal, TSizeTy >::NextPerm ( )

Generates next permutation of the elements in the vector.

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

Definition at line 1267 of file ds.h.

                                   {
  // start with a sorted sequence to obtain all permutations
  TSizeTy First = 0, Last = Len(), Next = Len()-1;
  if (Last < 2) return false;
  for(; ; ) {
    // find rightmost element smaller than successor
    TSizeTy Next1 = Next;
    if (GetVal(--Next) < GetVal(Next1)) { // swap with rightmost element that's smaller, flip suffix
      TSizeTy Mid = Last;
      for (; GetVal(Next) >= GetVal(--Mid); ) { }
      Swap(Next, Mid);
      Reverse(Next1, Last-1);
      return true;
    }
    if (Next == First) { // pure descending, flip all
      Reverse();
      return false;
    }
  }
}
template<class TVal, class TSizeTy = int>
TVec<TVal, TSizeTy>& TVec< TVal, TSizeTy >::operator+ ( const TVal &  Val) [inline]

Appends value Val to the vector.

Definition at line 458 of file ds.h.

{Add(Val); return *this;}
template<class TVal, class TSizeTy>
bool TVec< TVal, TSizeTy >::operator< ( const TVec< TVal, TSizeTy > &  Vec) const

Lexicographically compares two vectors.

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

Definition at line 912 of file ds.h.

                                                                        {
  if (this==&Vec){return false;}
  if (Len()==Vec.Len()){
    for (TSizeTy ValN=0; ValN<Vals; ValN++){
      if (ValT[ValN]<Vec.ValT[ValN]){return true;}
      else if (ValT[ValN]>Vec.ValT[ValN]){return false;}
      else {}
    }
    return false;
  } else {
    return Len()<Vec.Len();
  }
}
template<class TVal, class TSizeTy>
TVec< TVal, TSizeTy > & TVec< TVal, TSizeTy >::operator= ( const TVec< TVal, TSizeTy > &  Vec)

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

Definition at line 892 of file ds.h.

                                                                                 {
  if (this!=&Vec){
    if ((ValT!=NULL)&&(MxVals!=-1)){delete[] ValT;}
    MxVals=Vals=Vec.Vals;
    if (MxVals==0){ValT=NULL;} else {ValT=new TVal[MxVals];}
    for (TSizeTy ValN=0; ValN<Vec.Vals; ValN++){ValT[ValN]=Vec.ValT[ValN];}
  }
  return *this;
}
template<class TVal, class TSizeTy>
bool TVec< TVal, TSizeTy >::operator== ( const TVec< TVal, TSizeTy > &  Vec) const

Checks that the two vectors have the same contents.

Definition at line 903 of file ds.h.

                                                                         {
  if (this==&Vec){return true;}
  if (Len()!=Vec.Len()){return false;}
  for (TSizeTy ValN=0; ValN<Vals; ValN++){
    if (ValT[ValN]!=Vec.ValT[ValN]){return false;}}
  return true;
}
template<class TVal, class TSizeTy = int>
const TVal& TVec< TVal, TSizeTy >::operator[] ( const TSizeTy &  ValN) const [inline]

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

Definition at line 466 of file ds.h.

                                                    {
    AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
    return ValT[ValN];}
template<class TVal, class TSizeTy = int>
TVal& TVec< TVal, TSizeTy >::operator[] ( const TSizeTy &  ValN) [inline]

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

Definition at line 470 of file ds.h.

                                       {
    AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
    return ValT[ValN];}
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Pack ( )

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

Definition at line 987 of file ds.h.

                              {
  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  if (Vals==0){
    if (ValT!=NULL){delete[] ValT;} ValT=NULL;
  } else
    if (Vals<MxVals){
      MxVals=Vals;
      TVal* NewValT=new TVal[MxVals];
      IAssert(NewValT!=NULL);
      for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
      delete[] ValT; ValT=NewValT;
    }
}
template<class TVal , class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::Partition ( const TSizeTy &  MnLValN,
const TSizeTy &  MxRValN,
const bool &  Asc 
)

Partitions the values between positions MnLValN...MxLValN.

Helper function used by QSort().

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

Definition at line 1186 of file ds.h.

                                                                                                     {
  TSizeTy PivotValN=GetPivotValN(MnLValN, MxRValN);
  Swap(PivotValN, MnLValN);
  TVal PivotVal=ValT[MnLValN];
  TSizeTy LValN=MnLValN-1;  TSizeTy RValN=MxRValN+1;
  forever {
    if (Asc){
      do {RValN--;} while (ValT[RValN]>PivotVal);
      do {LValN++;} while (ValT[LValN]<PivotVal);
    } else {
      do {RValN--;} while (ValT[RValN]<PivotVal);
      do {LValN++;} while (ValT[LValN]>PivotVal);
    }
    if (LValN<RValN){Swap(LValN, RValN);}
    else {return RValN;}
  };
}
template<class TVal, class TSizeTy = int>
template<class TCmp >
static TIter TVec< TVal, TSizeTy >::PartitionCmp ( TIter  BI,
TIter  EI,
const TVal  Pivot,
const TCmp &  Cmp 
) [inline, static]

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

Definition at line 686 of file ds.h.

                                                                                   {
    forever {
      while (Cmp(*BI, Pivot)){++BI;}  --EI;
      while (Cmp(Pivot, *EI)){--EI;}
      if (!(BI<EI)){return BI;}  SwapI(BI, EI);  ++BI; } }
template<class TVal , class TSizeTy >
bool TVec< TVal, TSizeTy >::PrevPerm ( )

Generates previous permutation of the elements in the vector.

Returns false when the first permutation is reached.

Definition at line 1289 of file ds.h.

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

Sets all elements of the vector to value Val.

Definition at line 1130 of file ds.h.

                                               {
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=Val;}
}
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::QSort ( const TSizeTy &  MnLValN,
const TSizeTy &  MxRValN,
const bool &  Asc 
)

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

Helper function used by Sort().

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

Definition at line 1205 of file ds.h.

                                                                                              {
  if (MnLValN<MxRValN){
    if (MxRValN-MnLValN<20){
      ISort(MnLValN, MxRValN, Asc);
    } else {
      TSizeTy SplitValN=Partition(MnLValN, MxRValN, Asc);
      QSort(MnLValN, SplitValN, Asc);
      QSort(SplitValN+1, MxRValN, Asc);
    }
  }
}
template<class TVal, class TSizeTy = int>
template<class TCmp >
static void TVec< TVal, TSizeTy >::QSortCmp ( TIter  BI,
TIter  EI,
const TCmp &  Cmp 
) [inline, static]

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

Definition at line 705 of file ds.h.

                                                            {
    if (BI + 1 < EI) {
      if (EI - BI < 20) { ISortCmp(BI, EI, Cmp); }
      else { const TVal Val = *GetPivotValNCmp(BI, EI, Cmp);
        TIter Split = PartitionCmp(BI, EI, Val, Cmp);
        QSortCmp(BI, Split, Cmp);  QSortCmp(Split, EI, Cmp); } } }
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Reserve ( const TSizeTy &  _MxVals) [inline]

Reserves enough memory for the vector to store _MxVals elements.

Definition at line 506 of file ds.h.

{Resize(_MxVals);}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Reserve ( const TSizeTy &  _MxVals,
const TSizeTy &  _Vals 
) [inline]

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

Definition at line 508 of file ds.h.

{ IAssert((0<=_Vals)&&(_Vals<=_MxVals)); Resize(_MxVals); Vals=_Vals;}
template<class TVal, class TSizeTy = int>
TSizeTy TVec< TVal, TSizeTy >::Reserved ( ) const [inline]

Returns the size of allocated storage capacity.

Definition at line 537 of file ds.h.

{return MxVals;}
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Resize ( const TSizeTy &  _MxVals = -1) [protected]

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

Definition at line 831 of file ds.h.

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

Reverses the order of the elements in the vector.

Definition at line 1250 of file ds.h.

                                 {
  for (TSizeTy ValN=0; ValN<Vals/2; ValN++){
    Swap(ValN, Vals-ValN-1);}
}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Reverse ( TSizeTy  LValN,
TSizeTy  RValN 
) [inline]

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

Definition at line 666 of file ds.h.

{ Assert(LValN>=0 && RValN<Len()); while (LValN < RValN){Swap(LValN++, RValN--);} }
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Save ( TSOut &  SOut) const

Definition at line 885 of file ds.h.

                                                {
  if (MxVals!=-1){SOut.Save(MxVals);} else {SOut.Save(Vals);}
  SOut.Save(Vals);
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].Save(SOut);}
}
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::SaveXml ( TSOut &  SOut,
const TStr &  Nm 
) const

Definition at line 113 of file xmlser.h.

                                                                   {
  XSaveHdArg(Nm, "Vals", TInt::GetStr(Vals));
  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN].SaveXml(SOut, TStr());}
}
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::SearchBack ( const TVal &  Val) const

Returns the position of an element with value Val.

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

Definition at line 1447 of file ds.h.

                                                             {
  for (TSizeTy ValN=Vals-1; ValN>=0; ValN--){
    if (Val==ValT[ValN]){return ValN;}}
  return -1;
}
template<class TVal, class TSizeTy >
TSizeTy TVec< TVal, TSizeTy >::SearchBin ( const TVal &  Val) const

Returns the position of an element with value Val.

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

Definition at line 1418 of file ds.h.

                                                            {
  TSizeTy LValN=0, RValN=Len()-1;
  while (RValN>=LValN){
    TSizeTy ValN=(LValN+RValN)/2;
    if (Val==ValT[ValN]){return ValN;}
    if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
  }
  return -1;
}
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::SearchBin ( const TVal &  Val,
TSizeTy &  InsValN 
) const

Returns the position of an element with value Val.

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

Definition at line 1429 of file ds.h.

                                                                              {
  TSizeTy LValN=0, RValN=Len()-1;
  while (RValN>=LValN){
    TSizeTy ValN=(LValN+RValN)/2;
    if (Val==ValT[ValN]){InsValN=ValN; return ValN;}
    if (Val<ValT[ValN]){RValN=ValN-1;} else {LValN=ValN+1;}
  }
  InsValN=LValN; return -1;
}
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::SearchForw ( const TVal &  Val,
const TSizeTy &  BValN = 0 
) const

Returns the position of an element with value Val.

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

Definition at line 1440 of file ds.h.

                                                                                   {
  for (TSizeTy ValN=BValN; ValN<Vals; ValN++){
    if (Val==ValT[ValN]){return ValN;}}
  return -1;
}
template<class TVal, class TSizeTy>
TSizeTy TVec< TVal, TSizeTy >::SearchVForw ( const TVec< TVal, TSizeTy > &  ValV,
const TSizeTy &  BValN = 0 
) const

Returns the starting position of vector ValV.

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

Definition at line 1454 of file ds.h.

                                                                                                    {
  TSizeTy ValVLen=ValV.Len();
  for (TSizeTy ValN=BValN; ValN<Vals-ValVLen+1; ValN++){
    bool Found=true;
    for (TSizeTy SubValN=0; SubValN<ValVLen; SubValN++){
      if (ValV[SubValN]!=GetVal(ValN+SubValN)){Found=false; break;}
    }
    if (Found){return ValN;}
  }
  return -1;
}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::SetVal ( const TSizeTy &  ValN,
const TVal &  Val 
) [inline]

Sets the value of element at position ValN to Val.

Definition at line 599 of file ds.h.

{AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN)); ValT[ValN] = Val;}
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Shuffle ( TRnd &  Rnd)

Randomly shuffles the elements of the vector.

Definition at line 1235 of file ds.h.

                                          {
  if (Len() < TInt::Mx) {
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      const int Range = int(Vals-ValN);
      Swap(ValN, ValN+Rnd.GetUniDevInt(Range));
    }
  } else {
    for (TSizeTy ValN=0; ValN<Vals-1; ValN++){
      const TSizeTy Range = Vals-ValN;
      Swap(ValN, TSizeTy(ValN+Rnd.GetUniDevInt64(Range)));
    }
  }
}
template<class TVal , class TSizeTy >
void TVec< TVal, TSizeTy >::Sort ( const bool &  Asc = true)

Sorts the elements of the vector.

Use a combination if quicksort and insertion sort.

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

Definition at line 1218 of file ds.h.

                                             {
  QSort(0, Len()-1, Asc);
}
template<class TVal, class TSizeTy = int>
template<class TCmp >
void TVec< TVal, TSizeTy >::SortCmp ( const TCmp &  Cmp) [inline]

Sorts the elements of the vector using the comparator Cmp.

Definition at line 713 of file ds.h.

{ QSortCmp(BegI(), EndI(), Cmp);}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Swap ( TVec< TVal, TSizeTy > &  Vec)

Swaps the contents of the vector with Vec.

Definition at line 1011 of file ds.h.

                                                      {
  if (this!=&Vec){
    ::Swap(MxVals, Vec.MxVals);
    ::Swap(Vals, Vec.Vals);
    ::Swap(ValT, Vec.ValT);
  }
}
template<class TVal, class TSizeTy = int>
void TVec< TVal, TSizeTy >::Swap ( const TSizeTy &  ValN1,
const TSizeTy &  ValN2 
) [inline]

Swaps elements at positions ValN1 and ValN2.

Definition at line 618 of file ds.h.

{ const TVal Val=ValT[ValN1]; ValT[ValN1]=ValT[ValN2]; ValT[ValN2]=Val;}
template<class TVal, class TSizeTy = int>
static void TVec< TVal, TSizeTy >::SwapI ( TIter  LVal,
TIter  RVal 
) [inline, static]

Swaps the elements that iterators LVal and RVal point to.

Definition at line 620 of file ds.h.

{ const TVal Val=*LVal; *LVal=*RVal; *RVal=Val;}
template<class TVal , class TSizeTy>
void TVec< TVal, TSizeTy >::Trunc ( const TSizeTy &  _Vals = -1)

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

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

Definition at line 964 of file ds.h.

                                                   {
  IAssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
  IAssert((_Vals==-1)||(_Vals>=0));
  if ((_Vals!=-1)&&(_Vals>=Vals)){
    return;
  } else
    if (((_Vals==-1)&&(Vals==0))||(_Vals==0)){
      if (ValT!=NULL){delete[] ValT;}
      MxVals=Vals=0; ValT=NULL;
    } else {
      if (_Vals==-1){
        if (MxVals==Vals){return;} else {MxVals=Vals;}
      } else {
        MxVals=Vals=_Vals;
      }
      TVal* NewValT=new TVal[MxVals];
      IAssert(NewValT!=NULL);
      for (TSizeTy ValN=0; ValN<Vals; ValN++){NewValT[ValN]=ValT[ValN];}
      delete[] ValT; ValT=NewValT;
    }
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Union ( const TVec< TVal, TSizeTy > &  ValV)

Result is the union of this vector with ValV.

Assumes the vectors are sorted!

Definition at line 1317 of file ds.h.

                                                              {
  TVec<TVal, TSizeTy> UnionVec;
  Union(ValV, UnionVec);
  MoveFrom(UnionVec);
}
template<class TVal, class TSizeTy>
void TVec< TVal, TSizeTy >::Union ( const TVec< TVal, TSizeTy > &  ValV,
TVec< TVal, TSizeTy > &  DstValV 
) const

DstValV is the union of vectors this and ValV.

Assumes the vectors are sorted!

Definition at line 1345 of file ds.h.

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

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

Assumes both vectors are sorted in ascending order!

Definition at line 1392 of file ds.h.

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

Member Data Documentation

template<class TVal, class TSizeTy = int>
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: