SNAP Library 2.4, Developer Reference  2015-05-11 19:40:56
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
ds.h
Go to the documentation of this file.
1 // Address-Pointer
3 template <class TRec>
4 class TAPt{
5 private:
6  TRec* Addr;
7 public:
8  TAPt(): Addr(NULL){}
9  TAPt(const TAPt& Pt): Addr(Pt.Addr){}
10  TAPt(TRec* _Addr): Addr(_Addr){}
12  void Save(TSOut&) const {Fail;}
13 
14  TAPt& operator=(const TAPt& Pt){Addr=Pt.Addr; return *this;}
15  TAPt& operator=(TRec* _Addr){Addr=_Addr; return *this;}
16  bool operator==(const TAPt& Pt) const {return *Addr==*Pt.Addr;}
17  bool operator!=(const TAPt& Pt) const {return *Addr!=*Pt.Addr;}
18  bool operator<(const TAPt& Pt) const {return *Addr<*Pt.Addr;}
19 
20  TRec* operator->() const {Assert(Addr!=NULL); return Addr;}
21  TRec& operator*() const {Assert(Addr!=NULL); return *Addr;}
22  TRec& operator[](const int& RecN) const {
23  Assert(Addr!=NULL); return Addr[RecN];}
24  TRec* operator()() const {return Addr;}
25 
26  bool Empty() const {return Addr==NULL;}
27 };
28 
30 // Pair
31 template <class TVal1, class TVal2>
32 class TPair{
33 public:
34  TVal1 Val1;
35  TVal2 Val2;
36 public:
37  TPair(): Val1(), Val2(){}
38  TPair(const TPair& Pair): Val1(Pair.Val1), Val2(Pair.Val2){}
39  TPair(const TVal1& _Val1, const TVal2& _Val2): Val1(_Val1), Val2(_Val2){}
40  explicit TPair(TSIn& SIn): Val1(SIn), Val2(SIn){}
41  void Save(TSOut& SOut) const {
42  Val1.Save(SOut); Val2.Save(SOut);}
43  void Load(TSIn& SIn) {Val1.Load(SIn); Val2.Load(SIn);}
44  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
45  void SaveXml(TSOut& SOut, const TStr& Nm) const;
46 
47  TPair& operator=(const TPair& Pair){
48  if (this!=&Pair){Val1=Pair.Val1; Val2=Pair.Val2;} return *this;}
49  bool operator==(const TPair& Pair) const {
50  return (Val1==Pair.Val1)&&(Val2==Pair.Val2);}
51  bool operator<(const TPair& Pair) const {
52  return (Val1<Pair.Val1)||((Val1==Pair.Val1)&&(Val2<Pair.Val2));}
53 
54  int GetMemUsed() const {return Val1.GetMemUsed()+Val2.GetMemUsed();}
55 
56  int GetPrimHashCd() const {return TPairHashImpl::GetHashCd(Val1.GetPrimHashCd(), Val2.GetPrimHashCd()); }
57  int GetSecHashCd() const {return TPairHashImpl::GetHashCd(Val2.GetSecHashCd(), Val1.GetSecHashCd()); }
58 
59  void GetVal(TVal1& _Val1, TVal2& _Val2) const {_Val1=Val1; _Val2=Val2;}
60  const TVal1& GetVal1() const { return Val1;}
61  const TVal2& GetVal2() const { return Val2;}
62  TStr GetStr() const {
63  return TStr("Pair(")+Val1.GetStr()+", "+Val2.GetStr()+")";}
64 };
65 
66 template <class TVal1, class TVal2, class TSizeTy>
67 void GetSwitchedPrV(const TVec<TPair<TVal1, TVal2>, TSizeTy>& SrcPrV, TVec<TPair<TVal2, TVal1>, TSizeTy>& DstPrV){
68  const TSizeTy Prs = SrcPrV.Len();
69  DstPrV.Gen(Prs, 0);
70  for (TSizeTy PrN=0; PrN<Prs; PrN++){
71  const TPair<TVal1, TVal2>& SrcPr=SrcPrV[PrN];
72  DstPrV.Add(TPair<TVal2, TVal1>(SrcPr.Val2, SrcPr.Val1));
73  }
74 }
75 
113 
115 template <class TVal1, class TVal2>
117 private:
118  bool IsAsc;
119 public:
120  TCmpPairByVal2(const bool& AscSort=true) : IsAsc(AscSort) { }
121  bool operator () (const TPair<TVal1, TVal2>& P1, const TPair<TVal1, TVal2>& P2) const {
122  if (IsAsc) { return P1.Val2 < P2.Val2; } else { return P2.Val2 < P1.Val2; }
123  }
124 };
125 
127 // Triple
128 template <class TVal1, class TVal2, class TVal3>
129 class TTriple{
130 public:
131  TVal1 Val1;
132  TVal2 Val2;
133  TVal3 Val3;
134 public:
135  TTriple(): Val1(), Val2(), Val3(){}
136  TTriple(const TTriple& Triple):
137  Val1(Triple.Val1), Val2(Triple.Val2), Val3(Triple.Val3){}
138  TTriple(const TVal1& _Val1, const TVal2& _Val2, const TVal3& _Val3):
139  Val1(_Val1), Val2(_Val2), Val3(_Val3){}
140  explicit TTriple(TSIn& SIn): Val1(SIn), Val2(SIn), Val3(SIn){}
141  void Save(TSOut& SOut) const {
142  Val1.Save(SOut); Val2.Save(SOut); Val3.Save(SOut);}
143  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
144  void SaveXml(TSOut& SOut, const TStr& Nm) const;
145 
146  TTriple& operator=(const TTriple& Triple){
147  if (this!=&Triple){Val1=Triple.Val1; Val2=Triple.Val2; Val3=Triple.Val3;}
148  return *this;}
149  bool operator==(const TTriple& Triple) const {
150  return (Val1==Triple.Val1)&&(Val2==Triple.Val2)&&(Val3==Triple.Val3);}
151  bool operator<(const TTriple& Triple) const {
152  return (Val1<Triple.Val1)||((Val1==Triple.Val1)&&(Val2<Triple.Val2))||
153  ((Val1==Triple.Val1)&&(Val2==Triple.Val2)&&(Val3<Triple.Val3));}
154 
155  int GetPrimHashCd() const {return TPairHashImpl::GetHashCd(TPairHashImpl::GetHashCd(Val1.GetPrimHashCd(), Val2.GetPrimHashCd()), Val3.GetPrimHashCd()); }
156  int GetSecHashCd() const {return TPairHashImpl::GetHashCd(TPairHashImpl::GetHashCd(Val2.GetSecHashCd(), Val3.GetSecHashCd()), Val1.GetSecHashCd()); }
157  int GetMemUsed() const {return Val1.GetMemUsed()+Val2.GetMemUsed()+Val3.GetMemUsed();}
158 
159  void GetVal(TVal1& _Val1, TVal2& _Val2, TVal3& _Val3) const {
160  _Val1=Val1; _Val2=Val2; _Val3=Val3;}
161 };
162 
185 
187 template <class TVal1, class TVal2, class TVal3>
189 private:
190  bool IsAsc;
191 public:
192  TCmpTripleByVal2(const bool& AscSort=true) : IsAsc(AscSort) { }
194  if (IsAsc) { return T1.Val2 < T2.Val2; } else { return T2.Val2 < T1.Val2; }
195  }
196 };
197 
199 template <class TVal1, class TVal2, class TVal3>
201 private:
202  bool IsAsc;
203 public:
204  TCmpTripleByVal3(const bool& AscSort=true) : IsAsc(AscSort) { }
206  if (IsAsc) { return T1.Val3 < T2.Val3; } else { return T2.Val3 < T1.Val3; }
207  }
208 };
209 
211 // Quad
212 template <class TVal1, class TVal2, class TVal3, class TVal4>
213 class TQuad{
214 public:
215  TVal1 Val1;
216  TVal2 Val2;
217  TVal3 Val3;
218  TVal4 Val4;
219 public:
220  TQuad():
221  Val1(), Val2(), Val3(), Val4(){}
222  TQuad(const TQuad& Quad):
223  Val1(Quad.Val1), Val2(Quad.Val2), Val3(Quad.Val3), Val4(Quad.Val4){}
224  TQuad(const TVal1& _Val1, const TVal2& _Val2, const TVal3& _Val3, const TVal4& _Val4):
225  Val1(_Val1), Val2(_Val2), Val3(_Val3), Val4(_Val4){}
226  explicit TQuad(TSIn& SIn):
227  Val1(SIn), Val2(SIn), Val3(SIn), Val4(SIn){}
228  void Save(TSOut& SOut) const {
229  Val1.Save(SOut); Val2.Save(SOut); Val3.Save(SOut); Val4.Save(SOut);}
230  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
231  void SaveXml(TSOut& SOut, const TStr& Nm) const;
232 
233  TQuad& operator=(const TQuad& Quad){
234  if (this!=&Quad){
235  Val1=Quad.Val1; Val2=Quad.Val2; Val3=Quad.Val3; Val4=Quad.Val4;}
236  return *this;}
237  bool operator==(const TQuad& Quad) const {
238  return (Val1==Quad.Val1)&&(Val2==Quad.Val2)&&(Val3==Quad.Val3)&&(Val4==Quad.Val4);}
239  bool operator<(const TQuad& Quad) const {
240  return (Val1<Quad.Val1)||((Val1==Quad.Val1)&&(Val2<Quad.Val2))||
241  ((Val1==Quad.Val1)&&(Val2==Quad.Val2)&&(Val3<Quad.Val3))||
242  ((Val1==Quad.Val1)&&(Val2==Quad.Val2)&&(Val3==Quad.Val3)&&(Val4<Quad.Val4));}
243 
244  int GetPrimHashCd() const {return TPairHashImpl::GetHashCd(TPairHashImpl::GetHashCd(Val1.GetPrimHashCd(), Val2.GetPrimHashCd()), TPairHashImpl::GetHashCd(Val3.GetPrimHashCd(), Val4.GetPrimHashCd())); }
245  int GetSecHashCd() const {return TPairHashImpl::GetHashCd(TPairHashImpl::GetHashCd(Val2.GetSecHashCd(), Val3.GetSecHashCd()), TPairHashImpl::GetHashCd(Val4.GetSecHashCd(), Val1.GetSecHashCd())); }
246 
247  void GetVal(TVal1& _Val1, TVal2& _Val2, TVal3& _Val3, TVal4& _Val4) const {
248  _Val1=Val1; _Val2=Val2; _Val3=Val3; _Val4=Val4;}
249 };
250 
258 
260 // Tuple
261 template<class TVal, int NVals>
262 class TTuple {
263 private:
264  TVal ValV [NVals];
265 public:
266  TTuple(){}
267  TTuple(const TVal& InitVal) { for (int i=0; i<Len(); i++) ValV[i]=InitVal; }
268  TTuple(const TTuple& Tup) { for (int i=0; i<Len(); i++) ValV[i]=Tup[i]; }
269  TTuple(TSIn& SIn) { for (int i=0; i<Len(); i++) ValV[i].Load(SIn); }
270  void Save(TSOut& SOut) const { for (int i=0; i<Len(); i++) ValV[i].Save(SOut); }
271  void Load(TSIn& SIn) { for (int i=0; i<Len(); i++) ValV[i].Load(SIn); }
272 
273  int Len() const { return NVals; }
274  TVal& operator[] (const int& ValN) { return ValV[ValN]; }
275  const TVal& operator[] (const int& ValN) const { return ValV[ValN]; }
276  TTuple& operator = (const TTuple& Tup) { if (this != & Tup) {
277  for (int i=0; i<Len(); i++) ValV[i]=Tup[i]; } return *this; }
278  bool operator == (const TTuple& Tup) const {
279  if (Len()!=Tup.Len()) { return false; } if (&Tup==this) { return true; }
280  for (int i=0; i<Len(); i++) if(ValV[i]!=Tup[i]){return false;} return true; }
281  bool operator < (const TTuple& Tup) const {
282  if (Len() == Tup.Len()) { for (int i=0; i<Len(); i++) {
283  if(ValV[i]<Tup[i]){return true;} else if(ValV[i]>Tup[i]){return false;} } return false; }
284  else { return Len() < Tup.Len(); } }
285  void Sort(const bool& Asc=true);
286  int FindMx() const;
287  int FindMn() const;
288  int GetPrimHashCd() const { int hc = 0;
289  for (int i = 0; i < NVals; i++) { hc = TPairHashImpl::GetHashCd(hc, ValV[i].GetPrimHashCd()); }
290  return hc; }
291  int GetSecHashCd() const { int hc = 0;
292  for (int i = 1; i < NVals; i++) { hc = TPairHashImpl::GetHashCd(hc, ValV[i].GetSecHashCd()); }
293  if (NVals > 0) { hc = TPairHashImpl::GetHashCd(hc, ValV[0].GetSecHashCd()); }
294  return hc; }
295 
296  TStr GetStr() const { TChA ValsStr;
297  for (int i=0; i<Len(); i++) { ValsStr+=" "+ValV[i].GetStr(); }
298  return TStr::Fmt("Tuple(%d):", Len())+ValsStr; }
299 };
300 
301 template<class TVal, int NVals>
302 void TTuple<TVal, NVals>::Sort(const bool& Asc) {
303  TVec<TVal, int> V(NVals);
304  for (int i=0; i<NVals; i++) { V.Add(ValV[i]); }
305  V.Sort(Asc);
306  for (int i=0; i<NVals; i++) { ValV[i] = V[i]; }
307 }
308 
309 template<class TVal, int NVals>
311  TVal MxVal = ValV[0];
312  int ValN = 0;
313  for (int i = 1; i < NVals; i++) {
314  if (MxVal<ValV[i]) {
315  MxVal=ValV[i]; ValN=i;
316  }
317  }
318  return ValN;
319 }
320 
321 template<class TVal, int NVals>
323  TVal MnVal = ValV[0];
324  int ValN = 0;
325  for (int i = 1; i < NVals; i++) {
326  if (MnVal>ValV[i]) {
327  MnVal=ValV[i]; ValN=i;
328  }
329  }
330  return ValN;
331 }
332 
334 // Key-Data
335 template <class TKey, class TDat>
336 class TKeyDat{
337 public:
338  TKey Key;
339  TDat Dat;
340 public:
341  TKeyDat(): Key(), Dat(){}
342  TKeyDat(const TKeyDat& KeyDat): Key(KeyDat.Key), Dat(KeyDat.Dat){}
343  explicit TKeyDat(const TKey& _Key): Key(_Key), Dat(){}
344  TKeyDat(const TKey& _Key, const TDat& _Dat): Key(_Key), Dat(_Dat){}
345  explicit TKeyDat(TSIn& SIn): Key(SIn), Dat(SIn){}
346  void Save(TSOut& SOut) const {Key.Save(SOut); Dat.Save(SOut);}
347  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
348  void SaveXml(TSOut& SOut, const TStr& Nm) const;
349 
350  TKeyDat& operator=(const TKeyDat& KeyDat){
351  if (this!=&KeyDat){Key=KeyDat.Key; Dat=KeyDat.Dat;} return *this;}
352  bool operator==(const TKeyDat& KeyDat) const {return Key==KeyDat.Key;}
353  bool operator<(const TKeyDat& KeyDat) const {return Key<KeyDat.Key;}
354 
355  int GetPrimHashCd() const {return Key.GetPrimHashCd();}
356  int GetSecHashCd() const {return Key.GetSecHashCd();}
357 };
358 
359 template <class TKey, class TDat>
360 void GetSwitchedKdV(const TVec<TKeyDat<TKey, TDat>, int>& SrcKdV, TVec<TKeyDat<TDat, TKey>, int>& DstKdV){
361  const int Kds=SrcKdV.Len();
362  DstKdV.Gen(Kds, 0);
363  for (int KdN=0; KdN<Kds; KdN++){
364  const TKeyDat<TKey, TDat>& SrcKd=SrcKdV[KdN];
365  DstKdV.Add(TKeyDat<TDat, TKey>(SrcKd.Dat, SrcKd.Key));
366  }
367 }
368 
396 
397 // Key-Data comparator
398 
399 template <class TVal1, class TVal2>
401 private:
402  bool IsAsc;
403 public:
404  TCmpKeyDatByDat(const bool& AscSort=true) : IsAsc(AscSort) { }
405  bool operator () (const TKeyDat<TVal1, TVal2>& P1, const TKeyDat<TVal1, TVal2>& P2) const {
406  if (IsAsc) { return P1.Dat < P2.Dat; } else { return P2.Dat < P1.Dat; }
407  }
408 };
409 
410 //#//////////////////////////////////////////////
412 
419 template <class TVal, class TSizeTy = int>
420 class TVec{
421 public:
422  typedef TVal* TIter;
423 protected:
424  TSizeTy MxVals;
425  TSizeTy Vals;
426  TVal* ValT;
427  void Resize(const TSizeTy& _MxVals=-1);
430  TStr GetXOutOfBoundsErrMsg(const TSizeTy& ValN) const;
431 public:
432  TVec(): MxVals(0), Vals(0), ValT(NULL){}
433  TVec(const TVec<TVal, TSizeTy>& Vec);
435  explicit TVec(const TSizeTy& _Vals){
436  IAssert(0<=_Vals); MxVals=Vals=_Vals;
437  if (_Vals==0){ValT=NULL;} else {ValT=new TVal[_Vals];}}
439  TVec(const TSizeTy& _MxVals, const TSizeTy& _Vals){
440  IAssert((0<=_Vals)&&(_Vals<=_MxVals)); MxVals=_MxVals; Vals=_Vals;
441  if (_MxVals==0){ValT=NULL;} else {ValT=new TVal[_MxVals];}}
443 
446  explicit TVec(TVal *_ValT, const TSizeTy& _Vals):
447  MxVals(-1), Vals(_Vals), ValT(_ValT){}
448  ~TVec(){if ((ValT!=NULL) && (MxVals!=-1)){delete[] ValT;}}
449  explicit TVec(TSIn& SIn): MxVals(0), Vals(0), ValT(NULL){Load(SIn);}
450  void Load(TSIn& SIn);
451  void Save(TSOut& SOut) const;
452  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
453  void SaveXml(TSOut& SOut, const TStr& Nm) const;
454 
458  TVec<TVal, TSizeTy>& operator+(const TVal& Val){Add(Val); return *this;}
460  bool operator==(const TVec<TVal, TSizeTy>& Vec) const;
462 
464  bool operator<(const TVec<TVal, TSizeTy>& Vec) const;
466  const TVal& operator[](const TSizeTy& ValN) const {
467  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
468  return ValT[ValN];}
470  TVal& operator[](const TSizeTy& ValN){
471  AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN));
472  return ValT[ValN];}
474  TSizeTy GetMemUsed() const {
475  return TSizeTy(2*sizeof(TSizeTy)+sizeof(TVal*)+MxVals*sizeof(TVal));}
477  TSizeTy GetMemSize() const {
478  return TSizeTy(2*sizeof(TVal)+sizeof(TSizeTy)*Vals);}
479 
481  int GetPrimHashCd() const;
483  int GetSecHashCd() const;
484 
486  void Gen(const TSizeTy& _Vals){ 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];}}
490  void Gen(const TSizeTy& _MxVals, const TSizeTy& _Vals){ 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];}}
494 
497  void GenExt(TVal *_ValT, const TSizeTy& _Vals){
498  if (ValT!=NULL && MxVals!=-1){delete[] ValT;}
499  MxVals=-1; Vals=_Vals; ValT=_ValT;}
501 
504  bool IsExt() const {return MxVals==-1;}
506  void Reserve(const TSizeTy& _MxVals){Resize(_MxVals);}
508  void Reserve(const TSizeTy& _MxVals, const TSizeTy& _Vals){ IAssert((0<=_Vals)&&(_Vals<=_MxVals)); Resize(_MxVals); Vals=_Vals;}
510 
513  void Clr(const bool& DoDel=true, const TSizeTy& NoDelLim=-1);
515 
517  void Trunc(const TSizeTy& _Vals=-1);
519  void Pack();
521 
523  void MoveFrom(TVec<TVal, TSizeTy>& Vec);
525  void Swap(TVec<TVal, TSizeTy>& Vec);
526 
528 
530  bool Empty() const {return Vals==0;}
532 
535  TSizeTy Len() const {return Vals;}
537  TSizeTy Reserved() const {return MxVals;}
539  const TVal& Last() const {return GetVal(Len()-1);}
541  TVal& Last(){return GetVal(Len()-1);}
543  TSizeTy LastValN() const {return Len()-1;}
545  const TVal& LastLast() const { AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}
547  TVal& LastLast(){ AssertR(1<Vals, GetXOutOfBoundsErrMsg(Vals-2)); return ValT[Vals-2];}
548 
550  TIter BegI() const {return ValT;}
552  TIter EndI() const {return ValT+Vals;}
554  TIter GetI(const TSizeTy& ValN) const {return ValT+ValN;}
555 
557 
559  TSizeTy Add(){ AssertR(MxVals!=-1, "This vector was obtained from TVecPool. Such vectors cannot change its size!");
560  if (Vals==MxVals){Resize();} return Vals++;}
562 
564  TSizeTy Add(const TVal& Val){ 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++;}
566  TSizeTy Add(TVal& Val){ 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++;}
569  TSizeTy Add(const TVal& Val, const TSizeTy& ResizeLen){ 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++;}
572  TSizeTy AddV(const TVec<TVal, TSizeTy>& ValV);
574 
576  TSizeTy AddSorted(const TVal& Val, const bool& Asc=true, const TSizeTy& _MxVals=-1);
578 
580  TSizeTy AddBackSorted(const TVal& Val, const bool& Asc);
582 
584  TSizeTy AddMerged(const TVal& Val);
586 
588  TSizeTy AddVMerged(const TVec<TVal, TSizeTy>& ValV);
590 
593  TSizeTy AddUnique(const TVal& Val);
595  const TVal& GetVal(const TSizeTy& ValN) const {return operator[](ValN);}
597  TVal& GetVal(const TSizeTy& ValN){return operator[](ValN);}
599  void SetVal(const TSizeTy& ValN, const TVal& Val){AssertR((0<=ValN)&&(ValN<Vals), GetXOutOfBoundsErrMsg(ValN)); ValT[ValN] = Val;}
601  void GetSubValV(const TSizeTy& BValN, const TSizeTy& EValN, TVec<TVal, TSizeTy>& ValV) const;
603  void Ins(const TSizeTy& ValN, const TVal& Val);
605  void Del(const TSizeTy& ValN);
607  void Del(const TSizeTy& MnValN, const TSizeTy& MxValN);
609  void DelLast(){Del(Len()-1);}
611  bool DelIfIn(const TVal& Val);
613  void DelAll(const TVal& Val);
615  void PutAll(const TVal& Val);
616 
618  void Swap(const TSizeTy& ValN1, const TSizeTy& ValN2){ const TVal Val=ValT[ValN1]; ValT[ValN1]=ValT[ValN2]; ValT[ValN2]=Val;}
620  static void SwapI(TIter LVal, TIter RVal){ const TVal Val=*LVal; *LVal=*RVal; *RVal=Val;}
621 
623 
627  bool NextPerm();
629 
631  bool PrevPerm();
632 
633  // Sorting functions
635  TSizeTy GetPivotValN(const TSizeTy& LValN, const TSizeTy& RValN) const;
637 
639  void BSort(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc);
641 
643  void ISort(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc);
645 
648  TSizeTy Partition(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc);
650 
653  void QSort(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc);
655 
658  void Sort(const bool& Asc=true);
660  bool IsSorted(const bool& Asc=true) const;
662  void Shuffle(TRnd& Rnd);
664  void Reverse();
666  void Reverse(TSizeTy LValN, TSizeTy RValN){ Assert(LValN>=0 && RValN<Len()); while (LValN < RValN){Swap(LValN++, RValN--);} }
668  void Merge();
669 
671  template <class TCmp>
672  static TIter GetPivotValNCmp(const TIter& BI, const TIter& EI, const TCmp& Cmp) {
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; } }
685  template <class TCmp>
686  static TIter PartitionCmp(TIter BI, TIter EI, const TVal Pivot, const TCmp& Cmp) {
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; } }
692  template <class TCmp>
693  static void BSortCmp(TIter BI, TIter EI, const TCmp& Cmp) {
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); } } } }
698  template <class TCmp>
699  static void ISortCmp(TIter BI, TIter EI, const TCmp& Cmp) {
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; } } }
704  template <class TCmp>
705  static void QSortCmp(TIter BI, TIter EI, const TCmp& Cmp) {
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); } } }
712  template <class TCmp>
713  void SortCmp(const TCmp& Cmp){ QSortCmp(BegI(), EndI(), Cmp);}
715  template <class TCmp>
716  bool IsSortedCmp(const TCmp& Cmp) const {
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; }
720 
722 
724  void Intrs(const TVec<TVal, TSizeTy>& ValV);
726 
728  void Union(const TVec<TVal, TSizeTy>& ValV);
730 
733  void Diff(const TVec<TVal, TSizeTy>& ValV);
735 
737  void Intrs(const TVec<TVal, TSizeTy>& ValV, TVec<TVal, TSizeTy>& DstValV) const;
739 
741  void Union(const TVec<TVal, TSizeTy>& ValV, TVec<TVal, TSizeTy>& DstValV) const;
743 
746  void Diff(const TVec<TVal, TSizeTy>& ValV, TVec<TVal, TSizeTy>& DstValV) const;
748 
750  TSizeTy IntrsLen(const TVec<TVal, TSizeTy>& ValV) const;
752 
754  TSizeTy UnionLen(const TVec<TVal, TSizeTy>& ValV) const;
755 
757  TSizeTy Count(const TVal& Val) const;
759 
762  TSizeTy SearchBin(const TVal& Val) const;
764 
766  TSizeTy SearchBin(const TVal& Val, TSizeTy& InsValN) const;
768 
771  TSizeTy SearchForw(const TVal& Val, const TSizeTy& BValN=0) const;
773 
775  TSizeTy SearchBack(const TVal& Val) const;
777 
779  TSizeTy SearchVForw(const TVec<TVal, TSizeTy>& ValV, const TSizeTy& BValN=0) const;
780 
782  bool IsIn(const TVal& Val) const {return SearchForw(Val)!=-1;}
784 
786  bool IsIn(const TVal& Val, TSizeTy& ValN) const { ValN=SearchForw(Val); return ValN!=-1;}
788 
790  bool IsInBin(const TVal& Val) const {return SearchBin(Val)!=-1;}
792  const TVal& GetDat(const TVal& Val) const { return GetVal(SearchForw(Val));}
794 
796  TVal& GetAddDat(const TVal& Val){ 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);}}
799  TSizeTy GetMxValN() const;
800 
802  static TVec<TVal, TSizeTy> GetV(const TVal& Val1){
803  TVec<TVal, TSizeTy> V(1, 0); V.Add(Val1); return V;}
805  static TVec<TVal, TSizeTy> GetV(const TVal& Val1, const TVal& Val2){
806  TVec<TVal, TSizeTy> V(2, 0); V.Add(Val1); V.Add(Val2); return V;}
808  static TVec<TVal, TSizeTy> GetV(const TVal& Val1, const TVal& Val2, const TVal& Val3){
809  TVec<TVal, TSizeTy> V(3, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); return V;}
811  static TVec<TVal, TSizeTy> GetV(const TVal& Val1, const TVal& Val2, const TVal& Val3, const TVal& Val4){
812  TVec<TVal, TSizeTy> V(4, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); return V;}
814  static TVec<TVal, TSizeTy> GetV(const TVal& Val1, const TVal& Val2, const TVal& Val3, const TVal& Val4, const TVal& Val5){
815  TVec<TVal, TSizeTy> V(5, 0); V.Add(Val1); V.Add(Val2); V.Add(Val3); V.Add(Val4); V.Add(Val5); return V;}
817  static TVec<TVal, TSizeTy> GetV(const TVal& Val1, const TVal& Val2, const TVal& Val3, const TVal& Val4, const TVal& Val5, const TVal& Val6){
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;}
820  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){
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;}
823  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){
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;}
826  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){
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;}
828 };
829 
830 template <class TVal, class TSizeTy>
831 void TVec<TVal, TSizeTy>::Resize(const TSizeTy& _MxVals){
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 }
859 
860 template <class TVal, class TSizeTy>
862  return TStr()+
863  "Index:"+TInt::GetStr(ValN)+
864  " Vals:"+TInt::GetStr(Vals)+
865  " MxVals:"+TInt::GetStr(MxVals)+
866  " Type:"+GetTypeNm(*this);
867 }
868 
869 template <class TVal, class TSizeTy>
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 }
875 
876 template <class TVal, class TSizeTy>
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 }
883 
884 template <class TVal, class TSizeTy>
885 void TVec<TVal, TSizeTy>::Save(TSOut& SOut) const {
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 }
890 
891 template <class TVal, class TSizeTy>
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 }
901 
902 template <class TVal, class TSizeTy>
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 }
910 
911 template <class TVal, class TSizeTy>
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 }
925 
926 // Improved hashing of vectors (Jure Apr 20 2013)
927 // This change makes binary representation of vectors incompatible with previous code.
928 // Previous hash functions are available for compatibility in class TVecHashF_OldGLib
929 template <class TVal, class TSizeTy>
931  int hc = 0;
932  for (TSizeTy i=0; i<Vals; i++){
933  hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetPrimHashCd());
934  }
935  return hc;
936 }
937 
938 // Improved hashing of vectors (Jure Apr 20 2013)
939 // This change makes binary representation of vectors incompatible with previous code.
940 // Previous hash functions are available for compatibility in class TVecHashF_OldGLib
941 template <class TVal, class TSizeTy>
943  int hc = 0;
944  for (TSizeTy i=0; i<Vals; i++){
945  hc = TPairHashImpl::GetHashCd(hc, ValT[i].GetSecHashCd());
946  }
947  if (Vals > 0) {
948  hc = TPairHashImpl::GetHashCd(hc, ValT[0].GetSecHashCd()); }
949  return hc;
950 }
951 
952 template <class TVal, class TSizeTy>
953 void TVec<TVal, TSizeTy>::Clr(const bool& DoDel, const TSizeTy& NoDelLim){
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 }
962 
963 template <class TVal, class TSizeTy>
964 void TVec<TVal, TSizeTy>::Trunc(const TSizeTy& _Vals){
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 }
985 
986 template <class TVal, class TSizeTy>
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 }
1000 
1001 template <class TVal, class TSizeTy>
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 }
1009 
1010 template <class TVal, class TSizeTy>
1012  if (this!=&Vec){
1013  ::Swap(MxVals, Vec.MxVals);
1014  ::Swap(Vals, Vec.Vals);
1015  ::Swap(ValT, Vec.ValT);
1016  }
1017 }
1018 
1019 template <class TVal, class TSizeTy>
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 }
1025 
1026 template <class TVal, class TSizeTy>
1027 TSizeTy TVec<TVal, TSizeTy>::AddSorted(const TVal& Val, const bool& Asc, const TSizeTy& _MxVals){
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 }
1040 
1041 template <class TVal, class TSizeTy>
1042 TSizeTy TVec<TVal, TSizeTy>::AddBackSorted(const TVal& Val, const bool& Asc){
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 }
1051 
1052 template <class TVal, class TSizeTy>
1053 TSizeTy TVec<TVal, TSizeTy>::AddMerged(const TVal& Val){
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 }
1059 
1060 template <class TVal, class TSizeTy>
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 }
1066 
1067 template <class TVal, class TSizeTy>
1068 TSizeTy TVec<TVal, TSizeTy>::AddUnique(const TVal& Val){
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 }
1074 
1075 template <class TVal, class TSizeTy>
1076 void TVec<TVal, TSizeTy>::GetSubValV(const TSizeTy& _BValN, const TSizeTy& _EValN, TVec<TVal, TSizeTy>& SubValV) const {
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 }
1084 
1085 template <class TVal, class TSizeTy>
1086 void TVec<TVal, TSizeTy>::Ins(const TSizeTy& ValN, const TVal& Val){
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 }
1092 
1093 template <class TVal, class TSizeTy>
1094 void TVec<TVal, TSizeTy>::Del(const TSizeTy& ValN){
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 }
1101 
1102 template <class TVal, class TSizeTy>
1103 void TVec<TVal, TSizeTy>::Del(const TSizeTy& MnValN, const TSizeTy& MxValN){
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 }
1113 
1114 template <class TVal, class TSizeTy>
1115 bool TVec<TVal, TSizeTy>::DelIfIn(const TVal& Val){
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 }
1121 
1122 template <class TVal, class TSizeTy>
1123 void TVec<TVal, TSizeTy>::DelAll(const TVal& Val){
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 }
1128 
1129 template <class TVal, class TSizeTy>
1130 void TVec<TVal, TSizeTy>::PutAll(const TVal& Val){
1131  for (TSizeTy ValN=0; ValN<Vals; ValN++){ValT[ValN]=Val;}
1132 }
1133 
1134 template <class TVal, class TSizeTy>
1135 void TVec<TVal, TSizeTy>::BSort(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc){
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 }
1146 
1147 template <class TVal, class TSizeTy>
1148 void TVec<TVal, TSizeTy>::ISort(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc){
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 }
1163 
1164 template <class TVal, class TSizeTy>
1165 TSizeTy TVec<TVal, TSizeTy>::GetPivotValN(const TSizeTy& LValN, const TSizeTy& RValN) const {
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 }
1184 
1185 template <class TVal, class TSizeTy>
1186 TSizeTy TVec<TVal, TSizeTy>::Partition(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc){
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 }
1203 
1204 template <class TVal, class TSizeTy>
1205 void TVec<TVal, TSizeTy>::QSort(const TSizeTy& MnLValN, const TSizeTy& MxRValN, const bool& Asc){
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 }
1216 
1217 template <class TVal, class TSizeTy>
1218 void TVec<TVal, TSizeTy>::Sort(const bool& Asc){
1219  QSort(0, Len()-1, Asc);
1220 }
1221 
1222 template <class TVal, class TSizeTy>
1223 bool TVec<TVal, TSizeTy>::IsSorted(const bool& Asc) const {
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 }
1233 
1234 template <class TVal, class TSizeTy>
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 }
1248 
1249 template <class TVal, class TSizeTy>
1251  for (TSizeTy ValN=0; ValN<Vals/2; ValN++){
1252  Swap(ValN, Vals-ValN-1);}
1253 }
1254 
1255 template <class TVal, class TSizeTy>
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 }
1265 
1266 template <class TVal, class TSizeTy>
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 }
1287 
1288 template <class TVal, class TSizeTy>
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 }
1308 
1309 template <class TVal, class TSizeTy>
1311  TVec<TVal, TSizeTy> IntrsVec;
1312  Intrs(ValV, IntrsVec);
1313  MoveFrom(IntrsVec);
1314 }
1315 
1316 template <class TVal, class TSizeTy>
1318  TVec<TVal, TSizeTy> UnionVec;
1319  Union(ValV, UnionVec);
1320  MoveFrom(UnionVec);
1321 }
1322 
1323 template <class TVal, class TSizeTy>
1325  TVec<TVal, TSizeTy> DiffVec;
1326  Diff(ValV, DiffVec);
1327  MoveFrom(DiffVec);
1328 }
1329 
1330 template <class TVal, class TSizeTy>
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 }
1343 
1344 template <class TVal, class TSizeTy>
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 }
1360 
1361 template <class TVal, class TSizeTy>
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 }
1376 
1377 template <class TVal, class TSizeTy>
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 }
1390 
1391 template <class TVal, class TSizeTy>
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 }
1408 
1409 template <class TVal, class TSizeTy>
1410 TSizeTy TVec<TVal, TSizeTy>::Count(const TVal& Val) const {
1411  TSizeTy Count = 0;
1412  for (TSizeTy i = 0; i < Len(); i++){
1413  if (Val == ValT[i]){Count++;}}
1414  return Count;
1415 }
1416 
1417 template <class TVal, class TSizeTy>
1418 TSizeTy TVec<TVal, TSizeTy>::SearchBin(const TVal& Val) const {
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 }
1427 
1428 template <class TVal, class TSizeTy>
1429 TSizeTy TVec<TVal, TSizeTy>::SearchBin(const TVal& Val, TSizeTy& InsValN) const {
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 }
1438 
1439 template <class TVal, class TSizeTy>
1440 TSizeTy TVec<TVal, TSizeTy>::SearchForw(const TVal& Val, const TSizeTy& BValN) const {
1441  for (TSizeTy ValN=BValN; ValN<Vals; ValN++){
1442  if (Val==ValT[ValN]){return ValN;}}
1443  return -1;
1444 }
1445 
1446 template <class TVal, class TSizeTy>
1447 TSizeTy TVec<TVal, TSizeTy>::SearchBack(const TVal& Val) const {
1448  for (TSizeTy ValN=Vals-1; ValN>=0; ValN--){
1449  if (Val==ValT[ValN]){return ValN;}}
1450  return -1;
1451 }
1452 
1453 template <class TVal, class TSizeTy>
1454 TSizeTy TVec<TVal, TSizeTy>::SearchVForw(const TVec<TVal, TSizeTy>& ValV, const TSizeTy& BValN) const {
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 }
1465 
1466 template <class TVal, class TSizeTy>
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 }
1475 
1477 // Common-Vector-Types
1479 typedef TVec<TCh> TChV;
1510 typedef TVec<TIntKd> TIntKdV;
1552 
1553 //#//////////////////////////////////////////////
1555 
1558 template <class TVal, class TSizeTy=int>
1559 class TVecPool {
1560 public:
1563 private:
1567  TVal EmptyVal; // Empty value/vector
1568  TVal *ValBf; // Buffer for storing all the values
1569  TVec<uint64, int> IdToOffV; // Id to one past last (Vector starts at [id-1]). Vector length is IdToOff[id]-IdToOff[id-1]
1570 private:
1571  void Resize(const TSize& _MxVals);
1572 public:
1574 
1579  TVecPool(const TSize& ExpectVals=0, const TSize& _GrowBy=1000000, const bool& _FastCopy=false, const TVal& _EmptyVal=TVal());
1580  TVecPool(const TVecPool<TVal, TSizeTy>& Pool);
1581  TVecPool(TSIn& SIn);
1582  ~TVecPool() { if (ValBf != NULL) { delete [] ValBf; } ValBf=NULL; }
1583  static PVecPool New(const TSize& ExpectVals=0, const TSize& GrowBy=1000000, const bool& FastCopy=false) {
1584  return new TVecPool(ExpectVals, GrowBy, FastCopy); }
1585  static PVecPool Load(TSIn& SIn) { return new TVecPool(SIn); }
1586  static PVecPool Load(const TStr& FNm) { TFIn FIn(FNm); return Load(FIn); }
1587  void Save(TSOut& SOut) const;
1588  TVecPool& operator = (const TVecPool& Pool);
1589 
1591  int GetVecs() const { return IdToOffV.Len(); }
1593  TSize GetVals() const { return Vals; }
1595  bool IsVId(const int& VId) const { return (0 <= VId) && (VId < IdToOffV.Len()); }
1597  uint64 Reserved() const { return MxVals; }
1599  void Reserve(const TSize& MxVals) { Resize(MxVals); }
1601  const TVal& GetEmptyVal() const { return EmptyVal; }
1603  void SetEmptyVal(const TVal& _EmptyVal) { EmptyVal = _EmptyVal; }
1605  uint64 GetMemUsed() const {
1606  return sizeof(TCRef)+sizeof(TBool)+3*sizeof(TSize)+sizeof(TVal*)+MxVals*sizeof(TVal);}
1607 
1609  int AddV(const TValV& ValV);
1611 
1613  int AddEmptyV(const int& ValVLen);
1615  int GetVLen(const int& VId) const { if (VId==0){return 0;} else {return int(IdToOffV[VId]-IdToOffV[VId-1]);}}
1617  TVal* GetValVPt(const int& VId) const {
1618  if (GetVLen(VId)==0){return (TVal*)&EmptyVal;}
1619  else {return ValBf+IdToOffV[VId-1];}}
1621 
1623  void GetV(const int& VId, TValV& ValV) const {
1624  if (GetVLen(VId)==0){ValV.Clr();}
1625  else { ValV.GenExt(GetValVPt(VId), GetVLen(VId)); } }
1627  void PutV(const int& VId, const TValV& ValV) {
1628  IAssert(IsVId(VId) && GetVLen(VId) == ValV.Len());
1629  if (FastCopy) {
1630  memcpy(GetValVPt(VId), ValV.BegI(), sizeof(TVal)*ValV.Len()); }
1631  else { TVal* ValPt = GetValVPt(VId);
1632  for (::TSize ValN=0; ValN < ::TSize(ValV.Len()); ValN++, ValPt++) { *ValPt=ValV[ValN]; }
1633  } }
1635 
1637  void CompactPool(const TVal& DelVal);
1639 
1641  void ShuffleAll(TRnd& Rnd=TInt::Rnd);
1642 
1644 
1646  void Clr(bool DoDel = true) {
1647  IdToOffV.Clr(DoDel); MxVals=0; Vals=0;
1648  if (DoDel && ValBf!=NULL) { delete [] ValBf; ValBf=NULL;}
1649  if (! DoDel) { PutAll(EmptyVal); } }
1651  void PutAll(const TVal& Val) {
1652  for (TSize ValN = 0; ValN < MxVals; ValN++) { ValBf[ValN]=Val; } }
1653  friend class TPt<TVecPool<TVal> >;
1654 };
1655 
1656 template <class TVal, class TSizeTy>
1658  if (_MxVals <= MxVals){ return; } else { MxVals = _MxVals; }
1659  if (ValBf == NULL) {
1660  try { ValBf = new TVal [MxVals]; }
1661  catch (std::exception Ex) {
1662  FailR(TStr::Fmt("TVecPool::Resize 1: %s, MxVals: %s. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(_MxVals)).CStr()).CStr()); }
1663  IAssert(ValBf != NULL);
1664  if (EmptyVal != TVal()) { PutAll(EmptyVal); }
1665  } else {
1666  // printf("*** Resize vector pool: %llu -> %llu\n", uint64(Vals), uint64(MxVals));
1667  TVal* NewValBf = NULL;
1668  try { NewValBf = new TVal [MxVals]; }
1669  catch (std::exception Ex) {
1670  FailR(TStr::Fmt("TVecPool::Resize 1: %s, MxVals: %s. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(_MxVals)).CStr()).CStr()); }
1671  IAssert(NewValBf != NULL);
1672  if (FastCopy) {
1673  memcpy(NewValBf, ValBf, Vals*sizeof(TVal)); }
1674  else {
1675  for (TSize ValN = 0; ValN < Vals; ValN++){ NewValBf[ValN] = ValBf[ValN]; } }
1676  if (EmptyVal != TVal()) { // init empty values
1677  for (TSize ValN = Vals; ValN < MxVals; ValN++) { NewValBf[ValN] = EmptyVal; }
1678  }
1679  delete [] ValBf;
1680  ValBf = NewValBf;
1681  }
1682 }
1683 
1684 template <class TVal, class TSizeTy>
1685 TVecPool<TVal, TSizeTy>::TVecPool(const TSize& ExpectVals, const TSize& _GrowBy, const bool& _FastCopy, const TVal& _EmptyVal) : GrowBy(_GrowBy), MxVals(0), Vals(0), EmptyVal(_EmptyVal), ValBf(NULL) {
1686  IdToOffV.Add(0);
1687  Resize(ExpectVals);
1688 }
1689 
1690 template <class TVal, class TSizeTy>
1691 TVecPool<TVal, TSizeTy>::TVecPool(const TVecPool& Pool) : FastCopy(Pool.FastCopy), GrowBy(Pool.GrowBy), MxVals(Pool.MxVals), Vals(Pool.Vals), EmptyVal(Pool.EmptyVal), IdToOffV(Pool.IdToOffV) {
1692  try {
1693  ValBf = new TVal [MxVals]; }
1694  catch (std::exception Ex) {
1695  FailR(TStr::Fmt("TVecPool::TVecPool: %s, MxVals: %s. [Program failed to allocate memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(MxVals)).CStr()).CStr()); }
1696  IAssert(ValBf != NULL);
1697  if (FastCopy) {
1698  memcpy(ValBf, Pool.ValBf, MxVals*sizeof(TVal)); }
1699  else {
1700  for (TSize ValN = 0; ValN < MxVals; ValN++){ ValBf[ValN] = Pool.ValBf[ValN]; } }
1701 }
1702 
1703 template <class TVal, class TSizeTy>
1705  uint64 _GrowBy, _MxVals, _Vals;
1706  SIn.Load(_GrowBy); SIn.Load(_MxVals); SIn.Load(_Vals);
1707  IAssertR(_GrowBy<TSizeMx && _MxVals<TSizeMx && _Vals<TSizeMx, "This is a 64-bit vector pool. Use a 64-bit compiler.");
1708  GrowBy=TSize(_GrowBy); MxVals=TSize(_Vals); Vals=TSize(_Vals); //note MxVals==Vals
1709  EmptyVal = TVal(SIn);
1710  if (MxVals==0) { ValBf = NULL; } else { ValBf = new TVal [MxVals]; }
1711  for (TSize ValN = 0; ValN < Vals; ValN++) { ValBf[ValN] = TVal(SIn); }
1712  { TInt MxVals(SIn), Vals(SIn);
1713  IdToOffV.Gen(Vals);
1714  for (int ValN = 0; ValN < Vals; ValN++) {
1715  uint64 Offset; SIn.Load(Offset); IAssert(Offset < TSizeMx);
1716  IdToOffV[ValN]=TSize(Offset);
1717  } }
1718 }
1719 
1720 template <class TVal, class TSizeTy>
1722  SOut.Save(FastCopy);
1723  uint64 _GrowBy=GrowBy, _MxVals=MxVals, _Vals=Vals;
1724  SOut.Save(_GrowBy); SOut.Save(_MxVals); SOut.Save(_Vals);
1725  SOut.Save(EmptyVal);
1726  for (TSize ValN = 0; ValN < Vals; ValN++) { ValBf[ValN].Save(SOut); }
1727  { SOut.Save(IdToOffV.Len()); SOut.Save(IdToOffV.Len());
1728  for (int ValN = 0; ValN < IdToOffV.Len(); ValN++) {
1729  const uint64 Offset=IdToOffV[ValN]; SOut.Save(Offset);
1730  } }
1731 }
1732 
1733 template <class TVal, class TSizeTy>
1735  if (this!=&Pool) {
1736  FastCopy = Pool.FastCopy;
1737  GrowBy = Pool.GrowBy;
1738  MxVals = Pool.MxVals;
1739  Vals = Pool.Vals;
1740  EmptyVal = Pool.EmptyVal;
1741  IdToOffV=Pool.IdToOffV;
1742  try {
1743  ValBf = new TVal [MxVals]; }
1744  catch (std::exception Ex) {
1745  FailR(TStr::Fmt("TVecPool::operator=: %s, MxVals: %s. [Program failed to allocate memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), TInt::GetStr(uint64(MxVals)).CStr()).CStr()); }
1746  IAssert(ValBf != NULL);
1747  if (FastCopy) {
1748  memcpy(ValBf, Pool.ValBf, Vals*sizeof(TVal)); }
1749  else {
1750  for (TSize ValN = 0; ValN < Vals; ValN++){ ValBf[ValN] = Pool.ValBf[ValN]; } }
1751  }
1752  return *this;
1753 }
1754 
1755 template <class TVal, class TSizeTy>
1757  const TSizeTy ValVLen = ValV.Len();
1758  if (ValVLen == 0) { return 0; }
1759  if (MxVals < Vals+ValVLen) { Resize(Vals+max(ValVLen, GrowBy)); }
1760  if (FastCopy) { memcpy(ValBf+Vals, ValV.BegI(), sizeof(TVal)*ValV.Len()); }
1761  else { for (uint ValN=0; ValN < ValVLen; ValN++) { ValBf[Vals+ValN]=ValV[ValN]; } }
1762  Vals+=ValVLen; IdToOffV.Add(Vals);
1763  return IdToOffV.Len()-1;
1764 }
1765 
1766 template <class TVal, class TSizeTy>
1767 int TVecPool<TVal, TSizeTy>::AddEmptyV(const int& ValVLen) {
1768  if (ValVLen==0){return 0;}
1769  if (MxVals < Vals+ValVLen){Resize(Vals+max(TSize(ValVLen), GrowBy)); }
1770  Vals+=ValVLen; IdToOffV.Add(Vals);
1771  return IdToOffV.Len()-1;
1772 }
1773 
1774 // Delete all elements of value DelVal from all vectors. Empty space is left at the end of the pool.
1775 template <class TVal, class TSizeTy>
1776 void TVecPool<TVal, TSizeTy>::CompactPool(const TVal& DelVal) {
1777  ::TSize TotalDel=0, NDel=0;
1778  // printf("Compacting %d vectors\n", IdToOffV.Len());
1779  for (int vid = 1; vid < IdToOffV.Len(); vid++) {
1780  // if (vid % 10000000 == 0) { printf(" %dm", vid/1000000); fflush(stdout); }
1781  const uint Len = GetVLen(vid);
1782  TVal* ValV = GetValVPt(vid);
1783  if (TotalDel > 0) { IdToOffV[vid-1] -= TotalDel; } // update end of vector
1784  if (Len == 0) { continue; }
1785  NDel = 0;
1786  for (TVal* v = ValV; v < ValV+Len-NDel; v++) {
1787  if (*v == DelVal) {
1788  TVal* Beg = v;
1789  while (*v == DelVal && v < ValV+Len) { v++; NDel++; }
1790  memcpy(Beg, v, sizeof(TVal)*int(Len - ::TSize(v - ValV)));
1791  v -= NDel;
1792  }
1793  }
1794  memcpy(ValV-TotalDel, ValV, sizeof(TVal)*Len); // move data
1795  TotalDel += NDel;
1796  }
1797  IdToOffV.Last() -= TotalDel;
1798  for (::TSize i = Vals-TotalDel; i < Vals; i++) { ValBf[i] = EmptyVal; }
1799  Vals -= TotalDel;
1800  // printf(" deleted %llu elements from the pool\n", TotalDel);
1801 }
1802 
1803 // shuffles all the order of elements in the pool (does not respect vector boundaries)
1804 template <class TVal, class TSizeTy>
1806  for (::TSize n = Vals-1; n > 0; n--) {
1807  const ::TSize k = ::TSize(((uint64(Rnd.GetUniDevInt())<<32) | uint64(Rnd.GetUniDevInt())) % (n+1));
1808  const TVal Tmp = ValBf[n];
1809  ValBf[n] = ValBf[k];
1810  ValBf[k] = Tmp;
1811  }
1812 }
1813 
1814 
1816 // Below are old 32-bit implementations of TVec and other classes.
1817 // Old TVec takes at most 2G elements.
1818 // The new vector class supports 64-bits for the number of elements,
1819 // but also allows 32-bits for backward compatibility.
1820 // by Jure (Jan 2013)
1821 namespace TGLib_OLD {
1823 // Vector Pool
1824 template<class TVal>
1825 class TVecPool {
1826 public:
1829 private:
1833  TVal EmptyVal; // empty vector
1834  TVal *ValBf; // buffer storing all the values
1835  TVec< ::TSize> IdToOffV; // id to one past last (vector starts at [id-1])
1836 private:
1837  void Resize(const ::TSize& _MxVals);
1838 public:
1839  TVecPool(const ::TSize& ExpectVals=0, const ::TSize& _GrowBy=1000000, const bool& _FastCopy=false, const TVal& _EmptyVal=TVal());
1840  TVecPool(const TVecPool& Pool);
1841  TVecPool(TSIn& SIn);
1842  ~TVecPool() { if (ValBf != NULL) { delete [] ValBf; } ValBf=NULL; }
1843  static PVecPool New(const ::TSize& ExpectVals=0, const ::TSize& GrowBy=1000000, const bool& FastCopy=false) {
1844  return new TVecPool(ExpectVals, GrowBy, FastCopy); }
1845  static PVecPool Load(TSIn& SIn) { return new TVecPool(SIn); }
1846  static PVecPool Load(const TStr& FNm) { TFIn FIn(FNm); return Load(FIn); }
1847  void Save(TSOut& SOut) const;
1848 
1849  TVecPool& operator = (const TVecPool& Pool);
1850 
1851  ::TSize GetVals() const { return Vals; }
1852  ::TSize GetVecs() const { return IdToOffV.Len(); }
1853  bool IsVId(const int& VId) const { return (0 <= VId) && (VId < IdToOffV.Len()); }
1854  ::TSize Reserved() const { return MxVals; }
1855  void Reserve(const ::TSize& MxVals) { Resize(MxVals); }
1856  const TVal& GetEmptyVal() const { return EmptyVal; }
1857  void SetEmptyVal(const TVal& _EmptyVal) { EmptyVal = _EmptyVal; }
1859  return sizeof(TCRef)+sizeof(TBool)+3*sizeof(TSize)+sizeof(TVal*)+MxVals*sizeof(TVal);}
1860 
1861  int AddV(const TValV& ValV);
1862  int AddEmptyV(const int& ValVLen);
1863  uint GetVLen(const int& VId) const {
1864  if (VId==0){return 0;}
1865  else {return uint(IdToOffV[VId]-IdToOffV[VId-1]);}}
1866  TVal* GetValVPt(const int& VId) const {
1867  if (GetVLen(VId)==0){return (TVal*)&EmptyVal;}
1868  else {return ValBf+IdToOffV[VId-1];}}
1869  void GetV(const int& VId, TValV& ValV) const {
1870  if (GetVLen(VId)==0){ValV.Clr();}
1871  else { ValV.GenExt(GetValVPt(VId), GetVLen(VId)); } }
1872  void PutV(const int& VId, const TValV& ValV) {
1873  IAssert(IsVId(VId) && GetVLen(VId) == ValV.Len());
1874  if (FastCopy) {
1875  memcpy(GetValVPt(VId), ValV.BegI(), sizeof(TVal)*ValV.Len()); }
1876  else { TVal* ValPt = GetValVPt(VId);
1877  for (uint ValN=0; ValN < uint(ValV.Len()); ValN++, ValPt++) { *ValPt=ValV[ValN]; }
1878  }
1879  }
1880  void CompactPool(const TVal& DelVal); // delete all elements of value DelVal from all vectors
1881  void ShuffleAll(TRnd& Rnd=TInt::Rnd); // shuffles all the order of elements in the Pool (does not respect vector boundaries)
1882 
1883  //bool HasIdMap() const { return ! IdToOffV.Empty(); }
1884  //void ClrIdMap() { IdToOffV.Clr(true); }
1885  void Clr(bool DoDel = true) {
1886  IdToOffV.Clr(DoDel); MxVals=0; Vals=0;
1887  if (DoDel && ValBf!=NULL) { delete [] ValBf; ValBf=NULL;}
1888  if (! DoDel) { PutAll(EmptyVal); }
1889  }
1890  void PutAll(const TVal& Val) {
1891  for (TSize ValN = 0; ValN < MxVals; ValN++) { ValBf[ValN]=Val; } }
1892 
1893  friend class TPt<TVecPool<TVal> >;
1894 };
1895 
1896 template <class TVal>
1898  if (_MxVals <= MxVals){ return; } else { MxVals = _MxVals; }
1899  if (ValBf == NULL) {
1900  try { ValBf = new TVal [MxVals]; }
1901  catch (std::exception Ex) {
1902  FailR(TStr::Fmt("TVecPool::Resize 1: %s, MxVals: %d. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), _MxVals).CStr()); }
1903  IAssert(ValBf != NULL);
1904  if (EmptyVal != TVal()) { PutAll(EmptyVal); }
1905  } else {
1906  // printf("*** Resize vector pool: %llu -> %llu\n", uint64(Vals), uint64(MxVals));
1907  TVal* NewValBf = NULL;
1908  try { NewValBf = new TVal [MxVals]; }
1909  catch (std::exception Ex) { FailR(TStr::Fmt("TVecPool::Resize 2: %s, MxVals: %d. [Program failed to allocate more memory. Solution: Get a bigger machine and a 64-bit compiler.]", Ex.what(), _MxVals).CStr()); }
1910  IAssert(NewValBf != NULL);
1911  if (FastCopy) {
1912  memcpy(NewValBf, ValBf, Vals*sizeof(TVal)); }
1913  else {
1914  for (TSize ValN = 0; ValN < Vals; ValN++){ NewValBf[ValN] = ValBf[ValN]; } }
1915  if (EmptyVal != TVal()) { // init empty values
1916  for (TSize ValN = Vals; ValN < MxVals; ValN++) { NewValBf[ValN] = EmptyVal; }
1917  }
1918  delete [] ValBf;
1919  ValBf = NewValBf;
1920  }
1921 }
1922 
1923 template <class TVal>
1924 TVecPool<TVal>::TVecPool(const ::TSize& ExpectVals, const ::TSize& _GrowBy, const bool& _FastCopy, const TVal& _EmptyVal) :
1925  GrowBy(_GrowBy), MxVals(0), Vals(0), EmptyVal(_EmptyVal), ValBf(NULL) {
1926  IdToOffV.Add(0);
1927  Resize(ExpectVals);
1928 }
1929 
1930 template <class TVal>
1932  FastCopy(Pool.FastCopy), GrowBy(Pool.GrowBy),
1933  MxVals(Pool.MxVals), Vals(Pool.Vals), EmptyVal(Pool.EmptyVal), IdToOffV(Pool.IdToOffV) {
1934  try { ValBf = new TVal [MxVals]; }
1935  catch (std::exception Ex) { FailR(TStr::Fmt("TVecPool::TVecPool: %s, MxVals: %d", Ex.what(), MxVals).CStr()); }
1936  IAssert(ValBf != NULL);
1937  if (FastCopy) {
1938  memcpy(ValBf, Pool.ValBf, MxVals*sizeof(TVal)); }
1939  else {
1940  for (TSize ValN = 0; ValN < MxVals; ValN++){ ValBf[ValN] = Pool.ValBf[ValN]; } }
1941 }
1942 
1943 template <class TVal>
1945  FastCopy(SIn) {
1946  uint64 _GrowBy, _MxVals, _Vals;
1947  SIn.Load(_GrowBy); SIn.Load(_MxVals); SIn.Load(_Vals);
1948  IAssert(_GrowBy<TSizeMx && _MxVals<TSizeMx && _Vals<TSizeMx);
1949  GrowBy=TSize(_GrowBy); MxVals=TSize(_Vals); Vals=TSize(_Vals); //note MxVals==Vals
1950  EmptyVal = TVal(SIn);
1951  if (MxVals==0) { ValBf = NULL; } else { ValBf = new TVal [MxVals]; }
1952  for (TSize ValN = 0; ValN < Vals; ValN++) { ValBf[ValN] = TVal(SIn); }
1953  { TInt MxVals(SIn), Vals(SIn);
1954  IdToOffV.Gen(Vals);
1955  for (int ValN = 0; ValN < Vals; ValN++) {
1956  uint64 Offset; SIn.Load(Offset); IAssert(Offset < TSizeMx);
1957  IdToOffV[ValN]=TSize(Offset);
1958  } }
1959 }
1960 
1961 template <class TVal>
1962 void TVecPool<TVal>::Save(TSOut& SOut) const {
1963  SOut.Save(FastCopy);
1964  uint64 _GrowBy=GrowBy, _MxVals=MxVals, _Vals=Vals;
1965  SOut.Save(_GrowBy); SOut.Save(_MxVals); SOut.Save(_Vals);
1966  SOut.Save(EmptyVal);
1967  for (TSize ValN = 0; ValN < Vals; ValN++) { ValBf[ValN].Save(SOut); }
1968  { SOut.Save(IdToOffV.Len()); SOut.Save(IdToOffV.Len());
1969  for (int ValN = 0; ValN < IdToOffV.Len(); ValN++) {
1970  const uint64 Offset=IdToOffV[ValN]; SOut.Save(Offset);
1971  } }
1972 }
1973 
1974 template <class TVal>
1976  if (this!=&Pool) {
1977  FastCopy = Pool.FastCopy;
1978  GrowBy = Pool.GrowBy;
1979  MxVals = Pool.MxVals;
1980  Vals = Pool.Vals;
1981  EmptyVal = Pool.EmptyVal;
1982  IdToOffV=Pool.IdToOffV;
1983  try { ValBf = new TVal [MxVals]; }
1984  catch (std::exception Ex) { FailR(TStr::Fmt("TVec::operator= : %s, MxVals: %d", Ex.what(), MxVals).CStr()); }
1985  IAssert(ValBf != NULL);
1986  if (FastCopy) {
1987  memcpy(ValBf, Pool.ValBf, Vals*sizeof(TVal)); }
1988  else {
1989  for (uint64 ValN = 0; ValN < Vals; ValN++){ ValBf[ValN] = Pool.ValBf[ValN]; } }
1990  }
1991  return *this;
1992 }
1993 
1994 template<class TVal>
1995 int TVecPool<TVal>::AddV(const TValV& ValV) {
1996  const ::TSize ValVLen = ValV.Len();
1997  if (ValVLen == 0) { return 0; }
1998  if (MxVals < Vals+ValVLen) { Resize(Vals+max(ValVLen, GrowBy)); }
1999  if (FastCopy) { memcpy(ValBf+Vals, ValV.BegI(), sizeof(TVal)*ValV.Len()); }
2000  else { for (uint ValN=0; ValN < ValVLen; ValN++) { ValBf[Vals+ValN]=ValV[ValN]; } }
2001  Vals+=ValVLen; IdToOffV.Add(Vals);
2002  return IdToOffV.Len()-1;
2003 }
2004 
2005 template<class TVal>
2006 int TVecPool<TVal>::AddEmptyV(const int& ValVLen) {
2007  if (ValVLen==0){return 0;}
2008  if (MxVals < Vals+ValVLen){Resize(Vals+max(TSize(ValVLen), GrowBy)); }
2009  Vals+=ValVLen; IdToOffV.Add(Vals);
2010  return IdToOffV.Len()-1;
2011 }
2012 
2013 // delete all elements of value DelVal from all vectors
2014 // empty space is left at the end of the pool
2015 template<class TVal>
2016 void TVecPool<TVal>::CompactPool(const TVal& DelVal) {
2017  ::TSize TotalDel=0, NDel=0;
2018  // printf("Compacting %d vectors\n", IdToOffV.Len());
2019  for (int vid = 1; vid < IdToOffV.Len(); vid++) {
2020  // if (vid % 10000000 == 0) { printf(" %dm", vid/1000000); fflush(stdout); }
2021  const uint Len = GetVLen(vid);
2022  TVal* ValV = GetValVPt(vid);
2023  if (TotalDel > 0) { IdToOffV[vid-1] -= TotalDel; } // update end of vector
2024  if (Len == 0) { continue; }
2025  NDel = 0;
2026  for (TVal* v = ValV; v < ValV+Len-NDel; v++) {
2027  if (*v == DelVal) {
2028  TVal* Beg = v;
2029  while (*v == DelVal && v < ValV+Len) { v++; NDel++; }
2030  memcpy(Beg, v, sizeof(TVal)*int(Len - ::TSize(v - ValV)));
2031  v -= NDel;
2032  }
2033  }
2034  memcpy(ValV-TotalDel, ValV, sizeof(TVal)*Len); // move data
2035  TotalDel += NDel;
2036  }
2037  IdToOffV.Last() -= TotalDel;
2038  for (::TSize i = Vals-TotalDel; i < Vals; i++) { ValBf[i] = EmptyVal; }
2039  Vals -= TotalDel;
2040  // printf(" deleted %llu elements from the pool\n", TotalDel);
2041 }
2042 
2043 // shuffles all the order of elements in the pool (does not respect vector boundaries)
2044 template<class TVal>
2046  for (::TSize n = Vals-1; n > 0; n--) {
2047  const ::TSize k = ::TSize(((uint64(Rnd.GetUniDevInt())<<32) | uint64(Rnd.GetUniDevInt())) % (n+1));
2048  const TVal Tmp = ValBf[n];
2049  ValBf[n] = ValBf[k];
2050  ValBf[k] = Tmp;
2051  }
2052 }
2053 
2054 }; // namespace TGLib_OLD
2055 
2056 typedef TVecPool<TInt> TIntVecPool;
2058 
2060 // Vector-Pointer
2061 template <class TVal>
2062 class PVec{
2063 private:
2065 public:
2067 public:
2068  PVec<TVal>(): V(){}
2069  PVec<TVal>(const PVec<TVal>& Vec): V(Vec.V){}
2070  static TPt<PVec<TVal> > New(){
2071  return new PVec<TVal>();}
2072  PVec<TVal>(const int& MxVals, const int& Vals): V(MxVals, Vals){}
2073  static TPt<PVec<TVal> > New(const int& MxVals, const int& Vals){
2074  return new PVec<TVal>(MxVals, Vals);}
2075  PVec<TVal>(const TVec<TVal>& _V): V(_V){}
2076  static TPt<PVec<TVal> > New(const TVec<TVal>& V){
2077  return new PVec<TVal>(V);}
2078  explicit PVec<TVal>(TSIn& SIn): V(SIn){}
2079  static TPt<PVec<TVal> > Load(TSIn& SIn){return new PVec<TVal>(SIn);}
2080  void Save(TSOut& SOut) const {V.Save(SOut);}
2081 
2083  if (this!=&Vec){V=Vec.V;} return *this;}
2084  bool operator==(const PVec<TVal>& Vec) const {return V==Vec.V;}
2085  bool operator<(const PVec<TVal>& Vec) const {return V<Vec.V;}
2086  TVal& operator[](const int& ValN) const {return V[ValN];}
2087 
2088  bool Empty() const {return V.Empty();}
2089  int Len() const {return V.Len();}
2090  TVal GetVal(const int& ValN) const {return V[ValN];}
2091 
2092  int Add(const TVal& Val){return V.Add(Val);}
2093 
2094  friend class TPt<PVec<TVal> >;
2095 };
2096 
2098 // Common-Vector-Pointer-Types
2105 
2107 // 2D-Vector
2108 template <class TVal>
2109 class TVVec{
2110 private:
2113 public:
2114  TVVec(): XDim(), YDim(), ValV(){}
2115  TVVec(const TVVec& Vec):
2116  XDim(Vec.XDim), YDim(Vec.YDim), ValV(Vec.ValV){}
2117  TVVec(const int& _XDim, const int& _YDim):
2118  XDim(), YDim(), ValV(){Gen(_XDim, _YDim);}
2119  explicit TVVec(const TVec<TVal>& _ValV, const int& _XDim, const int& _YDim):
2120  XDim(_XDim), YDim(_YDim), ValV(_ValV){ IAssert(ValV.Len()==XDim*YDim); }
2121  explicit TVVec(TSIn& SIn) {Load(SIn);}
2122  void Load(TSIn& SIn){XDim.Load(SIn); YDim.Load(SIn); ValV.Load(SIn);}
2123  void Save(TSOut& SOut) const {
2124  XDim.Save(SOut); YDim.Save(SOut); ValV.Save(SOut);}
2125 
2127  if (this!=&Vec){XDim=Vec.XDim; YDim=Vec.YDim; ValV=Vec.ValV;} return *this;}
2128  bool operator==(const TVVec& Vec) const {
2129  return (XDim==Vec.XDim)&&(YDim==Vec.YDim)&&(ValV==Vec.ValV);}
2130 
2131  bool Empty() const {return ValV.Len()==0;}
2132  void Clr(){XDim=0; YDim=0; ValV.Clr();}
2133  void Gen(const int& _XDim, const int& _YDim){
2134  Assert((_XDim>=0)&&(_YDim>=0));
2135  XDim=_XDim; YDim=_YDim; ValV.Gen(XDim*YDim);}
2136  int GetXDim() const {return XDim;}
2137  int GetYDim() const {return YDim;}
2138  int GetRows() const {return XDim;}
2139  int GetCols() const {return YDim;}
2141 
2142  const TVal& At(const int& X, const int& Y) const {
2143  Assert((0<=X)&&(X<int(XDim))&&(0<=Y)&&(Y<int(YDim)));
2144  return ValV[X*YDim+Y];}
2145  TVal& At(const int& X, const int& Y){
2146  Assert((0<=X)&&(X<int(XDim))&&(0<=Y)&&(Y<int(YDim)));
2147  return ValV[X*YDim+Y];}
2148  TVal& operator()(const int& X, const int& Y){
2149  return At(X, Y);}
2150  const TVal& operator()(const int& X, const int& Y) const {
2151  return At(X, Y);}
2152 
2153  void PutXY(const int& X, const int& Y, const TVal& Val){At(X, Y)=Val;}
2154  void PutAll(const TVal& Val){ValV.PutAll(Val);}
2155  void PutX(const int& X, const TVal& Val){
2156  for (int Y=0; Y<int(YDim); Y++){At(X, Y)=Val;}}
2157  void PutY(const int& Y, const TVal& Val){
2158  for (int X=0; X<int(XDim); X++){At(X, Y)=Val;}}
2159  TVal GetXY(const int& X, const int& Y) const {
2160  Assert((0<=X)&&(X<int(XDim))&&(0<=Y)&&(Y<int(YDim)));
2161  return ValV[X*YDim+Y];}
2162  void GetRow(const int& RowN, TVec<TVal>& Vec) const;
2163  void GetCol(const int& ColN, TVec<TVal>& Vec) const;
2164 
2165  void SwapX(const int& X1, const int& X2);
2166  void SwapY(const int& Y1, const int& Y2);
2167  void Swap(TVVec<TVal>& Vec);
2168 
2169  void ShuffleX(TRnd& Rnd);
2170  void ShuffleY(TRnd& Rnd);
2171  void GetMxValXY(int& X, int& Y) const;
2172 
2173  void CopyFrom(const TVVec<TVal>& VVec);
2174  void AddXDim();
2175  void AddYDim();
2176  void DelX(const int& X);
2177  void DelY(const int& Y);
2178 };
2179 
2180 template <class TVal>
2181 void TVVec<TVal>::SwapX(const int& X1, const int& X2){
2182  for (int Y=0; Y<int(YDim); Y++){
2183  TVal Val=At(X1, Y); At(X1, Y)=At(X2, Y); At(X2, Y)=Val;}
2184 }
2185 
2186 template <class TVal>
2187 void TVVec<TVal>::SwapY(const int& Y1, const int& Y2){
2188  for (int X=0; X<int(XDim); X++){
2189  TVal Val=At(X, Y1); At(X, Y1)=At(X, Y2); At(X, Y2)=Val;}
2190 }
2191 
2192 template <class TVal>
2194  if (this!=&Vec){
2195  ::Swap(XDim, Vec.XDim);
2196  ::Swap(YDim, Vec.YDim);
2197  ValV.Swap(Vec.ValV);
2198  }
2199 }
2200 
2201 template <class TVal>
2203  for (int X=0; X<XDim-1; X++){SwapX(X, X+Rnd.GetUniDevInt(XDim-X));}
2204 }
2205 
2206 template <class TVal>
2208  for (int Y=0; Y<YDim-1; Y++){SwapY(Y, Y+Rnd.GetUniDevInt(YDim-Y));}
2209 }
2210 
2211 template <class TVal>
2212 void TVVec<TVal>::GetMxValXY(int& X, int& Y) const {
2213  int MxValN=ValV.GetMxValN();
2214  Y=MxValN%YDim;
2215  X=MxValN/YDim;
2216 }
2217 
2218 template <class TVal>
2220  int CopyXDim=TInt::GetMn(GetXDim(), VVec.GetXDim());
2221  int CopyYDim=TInt::GetMn(GetYDim(), VVec.GetYDim());
2222  for (int X=0; X<CopyXDim; X++){
2223  for (int Y=0; Y<CopyYDim; Y++){
2224  At(X, Y)=VVec.At(X, Y);
2225  }
2226  }
2227 }
2228 
2229 template <class TVal>
2231  TVVec<TVal> NewVVec(XDim+1, YDim);
2232  NewVVec.CopyFrom(*this);
2233  *this=NewVVec;
2234 }
2235 
2236 template <class TVal>
2238  TVVec<TVal> NewVVec(XDim, YDim+1);
2239  NewVVec.CopyFrom(*this);
2240  *this=NewVVec;
2241 }
2242 
2243 template <class TVal>
2244 void TVVec<TVal>::DelX(const int& X){
2245  TVVec<TVal> NewVVec(XDim-1, YDim);
2246  for (int Y=0; Y<YDim; Y++){
2247  for (int LX=0; LX<X; LX++){
2248  NewVVec.At(LX, Y)=At(LX, Y);}
2249  for (int RX=X+1; RX<XDim; RX++){
2250  NewVVec.At(RX-1, Y)=At(RX, Y);}
2251  }
2252  *this=NewVVec;
2253 }
2254 
2255 template <class TVal>
2256 void TVVec<TVal>::DelY(const int& Y){
2257  TVVec<TVal> NewVVec(XDim, YDim-1);
2258  for (int X=0; X<XDim; X++){
2259  for (int LY=0; LY<Y; LY++){
2260  NewVVec.At(X, LY)=At(X, LY);}
2261  for (int RY=Y+1; RY<YDim; RY++){
2262  NewVVec.At(X, RY-1)=At(X, RY);}
2263  }
2264  *this=NewVVec;
2265 }
2266 
2267 template <class TVal>
2268 void TVVec<TVal>::GetRow(const int& RowN, TVec<TVal>& Vec) const {
2269  Vec.Gen(GetCols(), 0);
2270  for (int col = 0; col < GetCols(); col++) {
2271  Vec.Add(At(RowN, col));
2272  }
2273 }
2274 
2275 template <class TVal>
2276 void TVVec<TVal>::GetCol(const int& ColN, TVec<TVal>& Vec) const {
2277  Vec.Gen(GetRows(), 0);
2278  for (int row = 0; row < GetRows(); row++) {
2279  Vec.Add(At(row, ColN));
2280  }
2281 }
2282 
2284 // Common-2D-Vector-Types
2292 
2294 // 3D-Vector
2295 template <class TVal>
2296 class TVVVec{
2297 private:
2300 public:
2301  TVVVec(): XDim(), YDim(), ZDim(), ValV(){}
2302  TVVVec(const TVVVec& Vec):
2303  XDim(Vec.XDim), YDim(Vec.YDim), ZDim(Vec.ZDim), ValV(Vec.ValV){}
2304  TVVVec(const int& _XDim, const int& _YDim, const int& _ZDim):
2305  XDim(), YDim(), ZDim(), ValV(){Gen(_XDim, _YDim, _ZDim);}
2306  explicit TVVVec(TSIn& SIn):
2307  XDim(SIn), YDim(SIn), ZDim(SIn), ValV(SIn){}
2308  void Save(TSOut& SOut) const {
2309  XDim.Save(SOut); YDim.Save(SOut); ZDim.Save(SOut); ValV.Save(SOut);}
2310 
2312  XDim=Vec.XDim; YDim=Vec.YDim; ZDim=Vec.ZDim; ValV=Vec.ValV;
2313  return *this;
2314  }
2315  bool operator==(const TVVVec& Vec) const {
2316  return (XDim==Vec.XDim)&&(YDim==Vec.YDim)&&(ZDim==Vec.ZDim)&&
2317  (ValV==Vec.ValV);}
2318 
2319  bool Empty() const {return ValV.Len()==0;}
2320  void Clr(){XDim=0; YDim=0; ZDim=0; ValV.Clr();}
2321  void Gen(const int& _XDim, const int& _YDim, const int& _ZDim){
2322  Assert((_XDim>=0)&&(_YDim>=0)&&(_ZDim>=0));
2323  XDim=_XDim; YDim=_YDim; ZDim=_ZDim; ValV.Gen(XDim*YDim*ZDim);}
2324  TVal& At(const int& X, const int& Y, const int& Z){
2325  Assert((0<=X)&&(X<int(XDim))&&(0<=Y)&&(Y<int(YDim))&&(0<=Z)&&(Z<int(ZDim)));
2326  return ValV[X*YDim*ZDim+Y*ZDim+Z];}
2327  const TVal& At(const int& X, const int& Y, const int& Z) const {
2328  Assert((0<=X)&&(X<int(XDim))&&(0<=Y)&&(Y<int(YDim))&&(0<=Z)&&(Z<int(ZDim)));
2329  return ValV[X*YDim*ZDim+Y*ZDim+Z];}
2330  TVal& operator()(const int& X, const int& Y, const int& Z){
2331  return At(X, Y, Z);}
2332  const TVal& operator()(const int& X, const int& Y, const int& Z) const {
2333  return At(X, Y, Z);}
2334  int GetXDim() const {return XDim;}
2335  int GetYDim() const {return YDim;}
2336  int GetZDim() const {return ZDim;}
2337 };
2338 
2340 // Common-3D-Vector-Types
2343 
2345 // Tree
2346 template <class TVal>
2347 class TTree{
2348 private:
2349  TVec<TTriple<TInt, TIntV, TVal> > NodeV; // (ParentNodeId, ChildNodeIdV, NodeVal)
2350 public:
2351  TTree(): NodeV(){}
2352  TTree(const TTree& Tree): NodeV(Tree.NodeV){}
2353  explicit TTree(TSIn& SIn): NodeV(SIn){}
2354  void Save(TSOut& SOut) const {NodeV.Save(SOut);}
2355  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
2356  void SaveXml(TSOut& SOut, const TStr& Nm) const;
2357 
2358  TTree& operator=(const TTree& Tree){if (this!=&Tree){NodeV=Tree.NodeV;} return *this;}
2359  bool operator==(const TTree& Tree) const {return NodeV==Tree.NodeV;}
2360  bool operator<(const TTree& Tree) const {return false;}
2361 
2362  int GetPrimHashCd() const {return NodeV.GetPrimHashCd();}
2363  int GetSecHashCd() const {return NodeV.GetSecHashCd();}
2364 
2365  int GetMemUsed() const {return NodeV.GetMemUsed();}
2366 
2367  void Clr(){NodeV.Clr();}
2368 
2369  int AddNode(const int& ParentNodeId, const TVal& NodeVal=TVal()){
2370  IAssert(((ParentNodeId==-1)&&(NodeV.Len()==0))||(NodeV.Len()>0));
2371  if (ParentNodeId!=-1){NodeV[ParentNodeId].Val2.Add(NodeV.Len());}
2372  return NodeV.Add(TTriple<TInt, TIntV, TVal>(ParentNodeId, TIntV(), NodeVal));}
2373  int AddRoot(const TVal& NodeVal=TVal()){
2374  return AddNode(-1, NodeVal);}
2375 
2376  int GetNodes() const {return NodeV.Len();}
2377  void GetNodeIdV(TIntV& NodeIdV, const int& NodeId=0);
2378  int GetParentNodeId(const int& NodeId) const {return NodeV[NodeId].Val1;}
2379  int GetChildren(const int& NodeId) const {return NodeV[NodeId].Val2.Len();}
2380  int GetChildNodeId(const int& NodeId, const int& ChildN) const {return NodeV[NodeId].Val2[ChildN];}
2381  TVal& GetNodeVal(const int& NodeId){return NodeV[NodeId].Val3;}
2382 
2383  void GenRandomTree(const int& Nodes, TRnd& Rnd);
2384 
2385  void DelNode(const int& NodeId);
2386  void CopyTree(const int& SrcNodeId, TTree& DstTree, const int& DstParentNodeId=-1);
2387 
2388  void WrTree(const int& NodeId=0, const int& Lev=0);
2389 };
2390 
2391 template <class TVal>
2392 void TTree<TVal>::GetNodeIdV(TIntV& NodeIdV, const int& NodeId){
2393  if (NodeId==0){NodeIdV.Clr(); if (GetNodes()==0){return;}}
2394  else if (GetParentNodeId(NodeId)==-1){return;}
2395  NodeIdV.Add(NodeId);
2396  for (int ChildN=0; ChildN<GetChildren(NodeId); ChildN++){
2397  int ChildNodeId=GetChildNodeId(NodeId, ChildN);
2398  if (ChildNodeId!=-1){
2399  GetNodeIdV(NodeIdV, ChildNodeId);
2400  }
2401  }
2402 }
2403 
2404 template <class TVal>
2405 void TTree<TVal>::GenRandomTree(const int& Nodes, TRnd& Rnd){
2406  Clr();
2407  if (Nodes>0){
2408  AddRoot(TVal());
2409  for (int NodeN=1; NodeN<Nodes; NodeN++){
2410  int ParentNodeId=Rnd.GetUniDevInt(0, GetNodes()-1);
2411  AddNode(ParentNodeId, TVal());
2412  }
2413  }
2414 }
2415 
2416 template <class TVal>
2417 void TTree<TVal>::DelNode(const int& NodeId){
2418  if (NodeId==0){
2419  Clr();
2420  } else {
2421  TIntV& ChildNodeIdV=NodeV[GetParentNodeId(NodeId)].Val2;
2422  int ChildNodeIdN=ChildNodeIdV.SearchForw(NodeId);
2423  ChildNodeIdV[ChildNodeIdN]=-1;
2424  }
2425 }
2426 
2427 template <class TVal>
2428 void TTree<TVal>::CopyTree(const int& SrcNodeId, TTree& DstTree, const int& DstParentNodeId){
2429  int DstNodeId=DstTree.AddNode(DstParentNodeId, GetNodeVal(SrcNodeId));
2430  for (int ChildN=0; ChildN<GetChildren(SrcNodeId); ChildN++){
2431  int ChildNodeId=GetChildNodeId(SrcNodeId, ChildN);
2432  if (ChildNodeId!=-1){
2433  CopyTree(ChildNodeId, DstTree, DstNodeId);
2434  }
2435  }
2436 }
2437 
2438 template <class TVal>
2439 void TTree<TVal>::WrTree(const int& NodeId, const int& Lev){
2440  for (int LevN=0; LevN<Lev; LevN++){printf("| ");}
2441  printf("%d (%d)\n", NodeId, GetChildren(NodeId));
2442  for (int ChildN=0; ChildN<GetChildren(NodeId); ChildN++){
2443  int ChildNodeId=GetChildNodeId(NodeId, ChildN);
2444  if (ChildNodeId!=-1){
2445  WrTree(ChildNodeId, Lev+1);
2446  }
2447  }
2448 }
2449 
2451 // Common-Tree-Types
2457 
2459 // Stack
2460 template <class TVal>
2461 class TSStack{
2462 private:
2464 public:
2465  TSStack(): ValV(){}
2466  TSStack(const int& MxVals): ValV(MxVals, 0){}
2467  TSStack(const TSStack& Stack): ValV(Stack.ValV){}
2468  explicit TSStack(TSIn& SIn): ValV(SIn){}
2469  void Save(TSOut& SOut) const {ValV.Save(SOut);}
2470 
2471  TSStack& operator=(const TSStack& Stack){
2472  if (this!=&Stack){ValV=Stack.ValV;} return *this;}
2473  bool operator==(const TSStack& Stack) const {return this==&Stack;}
2474  const TVal& operator[](const int& ValN) const {return ValV[ValV.Len()-ValN-1];}
2475  TVal& operator[](const int& ValN) {return ValV[ValV.Len()-ValN-1];}
2476 
2477  bool Empty(){return ValV.Len()==0;}
2478  void Clr(const bool& DoDel=false) {ValV.Clr(DoDel);}
2479  bool IsIn(const TVal& Val) const {return ValV.IsIn(Val);}
2480  int Len(){return ValV.Len();}
2481  TVal& Top(){Assert(0<ValV.Len()); return ValV.Last();}
2482  const TVal& Top() const {Assert(0<ValV.Len()); return ValV.Last();}
2483  void Push(){ValV.Add();}
2484  void Push(const TVal& Val){ValV.Add(Val);}
2485  void Pop(){Assert(0<ValV.Len()); ValV.DelLast();}
2486 };
2487 
2489 // Common-Stack-Types
2492 
2494 // Queue
2495 template <class TVal>
2496 class TQQueue{
2497 private:
2501 public:
2502  TQQueue(const int& _MxLast=64, const int& _MxLen=-1):
2503  MxLast(_MxLast), MxLen(_MxLen), First(0), Last(0), ValV(){
2504  Assert(int(MxLast)>0); Assert((MxLen==-1)||(int(MxLen)>0));}
2505  TQQueue(const TQQueue& Queue):
2506  MxLast(Queue.MxLast), MxLen(Queue.MxLen),
2507  First(Queue.First), Last(Queue.Last), ValV(Queue.ValV){}
2508  explicit TQQueue(TSIn& SIn):
2509  MxLast(SIn), MxLen(SIn), First(SIn), Last(SIn), ValV(SIn){}
2510  void Save(TSOut& SOut) const {
2511  MxLast.Save(SOut); MxLen.Save(SOut);
2512  First.Save(SOut); Last.Save(SOut); ValV.Save(SOut);}
2513 
2514  TQQueue& operator=(const TQQueue& Queue){
2515  if (this!=&Queue){MxLast=Queue.MxLast; MxLen=Queue.MxLen;
2516  First=Queue.First; Last=Queue.Last; ValV=Queue.ValV;}
2517  return *this;}
2518  const TVal& operator[](const int& ValN) const {Assert((0<=ValN)&&(ValN<Len()));
2519  return ValV[Last+ValN];}
2520 
2521  void Clr(const bool& DoDel=true){ValV.Clr(DoDel); First=Last=0;}
2522  void Gen(const int& _MxLast=64, const int& _MxLen=-1){
2523  MxLast=_MxLast; MxLen=_MxLen; First=0; Last=0; ValV.Clr();}
2524  void GetSubValV(const int& _BValN, const int& _EValN, TVec<TVal>& SubValV) const {
2525  int BValN=TInt::GetMx(0, _BValN);
2526  int EValN=TInt::GetMn(Len()-1, _EValN);
2527  SubValV.Gen(EValN-BValN+1);
2528  for (int ValN=BValN; ValN<=EValN; ValN++){
2529  SubValV[ValN-BValN]=ValV[Last+ValN];}
2530  }
2531 
2532  bool Empty() const {return First==Last;}
2533  int Len() const {return First-Last;}
2534  const TVal& Top() const {
2535  Assert(First!=Last); return ValV[Last];}
2536  void Pop(){
2537  IAssert(First!=Last); Last++;
2538  if (First==Last){ValV.Clr(); First=Last=0;}}
2539  void Push(const TVal& Val){
2540  if (Last>MxLast){ValV.Del(0, Last-1); First-=Last; Last=0;}
2541  if ((MxLen!=-1)&&(MxLen==Len())){Pop();}
2542  First++; ValV.Add(Val);}
2543 
2544  void Shuffle(TRnd& Rnd){
2545  TVec<TVal> ValV(Len(), 0); while (!Empty()){ValV.Add(Top()); Pop();}
2546  ValV.Shuffle(Rnd); Clr();
2547  for (int ValN=0; ValN<ValV.Len(); ValN++){Push(ValV[ValN]);}}
2548 };
2549 
2551 // Common-Queue-Types
2560 
2562 // List-Node
2563 template <class TVal>
2564 class TLstNd{
2565 public:
2568  TVal Val;
2569 public:
2570  TLstNd(): PrevNd(NULL), NextNd(NULL), Val(){}
2571  TLstNd(const TLstNd&);
2572  TLstNd(TLstNd* _PrevNd, TLstNd* _NextNd, const TVal& _Val):
2573  PrevNd(_PrevNd), NextNd(_NextNd), Val(_Val){}
2574 
2575  TLstNd& operator=(const TLstNd&);
2576 
2577  bool IsPrev() const {return (PrevNd != NULL); }
2578  bool IsNext() const {return (NextNd != NULL); }
2579  TLstNd* Prev() const {Assert(this!=NULL); return PrevNd;}
2580  TLstNd* Next() const {Assert(this!=NULL); return NextNd;}
2581  TVal& GetVal(){Assert(this!=NULL); return Val;}
2582  const TVal& GetVal() const {Assert(this!=NULL); return Val;}
2583 };
2584 
2586 // List
2587 template <class TVal>
2588 class TLst{
2589 public:
2591 private:
2592  int Nds;
2595 public:
2596  TLst(): Nds(0), FirstNd(NULL), LastNd(NULL){}
2597  TLst(const TLst&);
2598  ~TLst(){Clr();}
2599  explicit TLst(TSIn& SIn);
2600  void Save(TSOut& SOut) const;
2601 
2602  TLst& operator=(const TLst&);
2603 
2604  void Clr(){
2605  PLstNd Nd=FirstNd;
2606  while (Nd!=NULL){PLstNd NextNd=Nd->NextNd; delete Nd; Nd=NextNd;}
2607  Nds=0; FirstNd=NULL; LastNd=NULL;}
2608 
2609  bool Empty() const {return Nds==0;}
2610  int Len() const {return Nds;}
2611  PLstNd First() const {return FirstNd;}
2612  PLstNd Last() const {return LastNd;}
2613  TVal& FirstVal() const {return FirstNd->GetVal();}
2614  TVal& LastVal() const {return LastNd->GetVal();}
2615 
2616  PLstNd AddFront(const TVal& Val);
2617  PLstNd AddBack(const TVal& Val);
2618  PLstNd AddFrontSorted(const TVal& Val, const bool& Asc=true);
2619  PLstNd AddBackSorted(const TVal& Val, const bool& Asc=true);
2620  void PutFront(const PLstNd& Nd);
2621  void PutBack(const PLstNd& Nd);
2622  PLstNd Ins(const PLstNd& Nd, const TVal& Val);
2623  void Del(const TVal& Val);
2624  void Del(const PLstNd& Nd);
2625  void DelFirst() { PLstNd DelNd = FirstNd; Del(DelNd); }
2626  void DelLast() { PLstNd DelNd = LastNd; Del(DelNd); }
2627 
2628  PLstNd SearchForw(const TVal& Val);
2629  PLstNd SearchBack(const TVal& Val);
2630 
2631  friend class TLstNd<TVal>;
2632 };
2633 
2634 template <class TVal>
2636  Nds(0), FirstNd(NULL), LastNd(NULL){
2637  int CheckNds=0; SIn.Load(CheckNds);
2638  for (int NdN=0; NdN<CheckNds; NdN++){AddBack(TVal(SIn));}
2639  Assert(Nds==CheckNds);
2640 }
2641 
2642 template <class TVal>
2643 void TLst<TVal>::Save(TSOut& SOut) const {
2644  SOut.Save(Nds);
2645  PLstNd Nd=FirstNd; int CheckNds=0;
2646  while (Nd!=NULL){
2647  Nd->Val.Save(SOut); Nd=Nd->NextNd; CheckNds++;}
2648  IAssert(Nds==CheckNds);
2649 }
2650 
2651 template <class TVal>
2653  PLstNd Nd=new TLstNd<TVal>(NULL, FirstNd, Val);
2654  if (FirstNd!=NULL){FirstNd->PrevNd=Nd; FirstNd=Nd;}
2655  else {FirstNd=Nd; LastNd=Nd;}
2656  Nds++; return Nd;
2657 }
2658 
2659 template <class TVal>
2661  PLstNd Nd=new TLstNd<TVal>(LastNd, NULL, Val);
2662  if (LastNd!=NULL){LastNd->NextNd=Nd; LastNd=Nd;}
2663  else {FirstNd=Nd; LastNd=Nd;}
2664  Nds++; return Nd;
2665 }
2666 
2667 template <class TVal>
2668 TLstNd<TVal>* TLst<TVal>::AddFrontSorted(const TVal& Val, const bool& Asc){
2669  PLstNd Nd=First();
2670  if (Nd==NULL){
2671  return Ins(Nd, Val);
2672  } else {
2673  while ((Nd!=NULL)&&((Asc&&(Val>Nd()))||(!Asc&&(Val<Nd())))){
2674  Nd=Nd->Next();}
2675  if (Nd==NULL){return Ins(Nd->Last(), Val);}
2676  else {return Ins(Nd->Prev(), Val);}
2677  }
2678 }
2679 
2680 template <class TVal>
2681 TLstNd<TVal>* TLst<TVal>::AddBackSorted(const TVal& Val, const bool& Asc){
2682  PLstNd Nd=Last();
2683  while ((Nd!=NULL)&&((Asc&&(Val<Nd->Val))||(!Asc&&(Val>Nd->Val)))){
2684  Nd=Nd->Prev();}
2685  return Ins(Nd, Val);
2686 }
2687 
2688 template <class TVal>
2690  Assert(Nd!=NULL);
2691  // unchain
2692  if (Nd->PrevNd==NULL){FirstNd=Nd->NextNd;}
2693  else {Nd->PrevNd->NextNd=Nd->NextNd;}
2694  if (Nd->NextNd==NULL){LastNd=Nd->PrevNd;}
2695  else {Nd->NextNd->PrevNd=Nd->PrevNd;}
2696  // add to front
2697  Nd->PrevNd=NULL; Nd->NextNd=FirstNd;
2698  if (FirstNd!=NULL){FirstNd->PrevNd=Nd; FirstNd=Nd;}
2699  else {FirstNd=Nd; LastNd=Nd;}
2700 }
2701 
2702 template <class TVal>
2703 void TLst<TVal>::PutBack(const PLstNd& Nd){
2704  Assert(Nd!=NULL);
2705  // unchain
2706  if (Nd->PrevNd==NULL){FirstNd=Nd->NextNd;}
2707  else {Nd->PrevNd->NextNd=Nd->NextNd;}
2708  if (Nd->NextNd==NULL){LastNd=Nd->PrevNd;}
2709  else {Nd->NextNd->PrevNd=Nd->PrevNd;}
2710  // add to back
2711  Nd->PrevNd=LastNd; Nd->NextNd=NULL;
2712  if (LastNd!=NULL){LastNd->NextNd=Nd; LastNd=Nd;}
2713  else {FirstNd=Nd; LastNd=Nd;}
2714 }
2715 
2716 template <class TVal>
2717 TLstNd<TVal>* TLst<TVal>::Ins(const PLstNd& Nd, const TVal& Val){
2718  if (Nd==NULL){return AddFront(Val);}
2719  else if (Nd->NextNd==NULL){return AddBack(Val);}
2720  else {
2721  PLstNd NewNd=new TLstNd<TVal>(Nd, Nd->NextNd, Val);
2722  Nd->NextNd=NewNd; NewNd->NextNd->PrevNd=Nd;
2723  Nds++; return Nd;
2724  }
2725 }
2726 
2727 template <class TVal>
2728 void TLst<TVal>::Del(const TVal& Val){
2729  PLstNd Nd=SearchForw(Val);
2730  if (Nd!=NULL){Del(Nd);}
2731 }
2732 
2733 template <class TVal>
2734 void TLst<TVal>::Del(const PLstNd& Nd){
2735  Assert(Nd!=NULL);
2736  if (Nd->PrevNd==NULL){FirstNd=Nd->NextNd;}
2737  else {Nd->PrevNd->NextNd=Nd->NextNd;}
2738  if (Nd->NextNd==NULL){LastNd=Nd->PrevNd;}
2739  else {Nd->NextNd->PrevNd=Nd->PrevNd;}
2740  Nds--; delete Nd;
2741 }
2742 
2743 template <class TVal>
2745  PLstNd Nd=First();
2746  while (Nd!=NULL){
2747  if (Nd->GetVal()==Val){return Nd;}
2748  Nd=Nd->Next();
2749  }
2750  return NULL;
2751 }
2752 
2753 template <class TVal>
2755  PLstNd Nd=Last();
2756  while (Nd!=NULL){
2757  if (Nd->GetVal()==Val){return Nd;}
2758  Nd=Nd->Prev();
2759  }
2760  return NULL;
2761 }
2762 
2764 // Common-List-Types
2777 
2779 // Record-File
2780 template <class THd, class TRec>
2781 class TFRec{
2782 private:
2784 public:
2785  TFRec(const TStr& FNm, const TFAccess& FAccess, const bool& CreateIfNo):
2786  FRnd(PFRnd(new TFRnd(FNm, FAccess, CreateIfNo, sizeof(THd), sizeof(TRec)))){}
2787  TFRec(const TFRec&);
2788 
2789  TFRec& operator=(const TFRec&);
2790 
2791  void SetRecN(const int& RecN){FRnd->SetRecN(RecN);}
2792  int GetRecN(){return FRnd->GetRecN();}
2793  int GetRecs(){return FRnd->GetRecs();}
2794 
2795  void GetHd(THd& Hd){FRnd->GetHd(&Hd);}
2796  void PutHd(const THd& Hd){FRnd->PutHd(&Hd);}
2797  void GetRec(TRec& Rec, const int& RecN=-1){FRnd->GetRec(&Rec, RecN);}
2798  void PutRec(const TRec& Rec, const int& RecN=-1){FRnd->PutRec(&Rec, RecN);}
2799 };
2800 
2802 // Function
2803 template <class TFuncPt>
2804 class TFunc{
2805 private:
2806  TFuncPt FuncPt;
2807 public:
2808  TFunc(): FuncPt(NULL){}
2809  TFunc(const TFunc& Func): FuncPt(Func.FuncPt){}
2810  TFunc(const TFuncPt& _FuncPt): FuncPt(_FuncPt){}
2812  void Save(TSOut&) const {Fail;}
2813 
2814  TFunc& operator=(const TFunc& Func){
2815  if (this!=&Func){FuncPt=Func.FuncPt;} return *this;}
2816  bool operator==(const TFunc& Func) const {
2817  return FuncPt==Func.FuncPt;}
2818  bool operator<(const TFunc&) const {
2819  Fail; return false;}
2820  TFuncPt operator()() const {return FuncPt;}
2821 };
Definition: ds.h:336
TSizeTy AddUnique(const TVal &Val)
Adds element Val to a vector only if the element Val is not already in the vector.
Definition: ds.h:1068
~TVec()
Definition: ds.h:448
void Save(TSOut &SOut) const
Definition: ds.h:1962
bool operator==(const TTree &Tree) const
Definition: ds.h:2359
Definition: bd.h:440
#define IAssert(Cond)
Definition: bd.h:262
TQuad< TStr, TStr, TStr, TStr > TStrQu
Definition: ds.h:252
TVec< TFltIntKd > TFltIntKdV
Definition: ds.h:1526
TFuncPt FuncPt
Definition: ds.h:2806
TVec< TVal > V
Definition: ds.h:2066
bool operator==(const TVVec &Vec) const
Definition: ds.h:2128
void SaveXml(TSOut &SOut, const TStr &Nm) const
Definition: xmlser.h:113
void GetV(const int &VId, TValV &ValV) const
Returns ValV which is a reference (not a copy) to vector with id VId.
Definition: ds.h:1623
const TVal & GetVal() const
Definition: ds.h:2582
TQQueue< TAscFltV > TAscFltVQ
Definition: ds.h:2558
TPair< TInt, TInt > TIntPr
Definition: ds.h:83
TStr GetTypeNm(const Type &Var)
Definition: ut.h:16
bool operator==(const PVec< TVal > &Vec) const
Definition: ds.h:2084
::TSize GetVecs() const
Definition: ds.h:1852
TTriple(const TTriple &Triple)
Definition: ds.h:136
TPair(const TPair &Pair)
Definition: ds.h:38
TVec< TUInt64IntPr > TUInt64IntPrV
Definition: ds.h:1519
::TSize Vals
Definition: ds.h:1832
bool DelIfIn(const TVal &Val)
Removes the first occurrence of element Val.
Definition: ds.h:1115
TTree< TStrIntStrVTr > TStrIntStrVTrTree
Definition: ds.h:2456
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:552
TStr GetStr() const
Definition: ds.h:62
TPair< TUCh, TStr > TUChStrPr
Definition: ds.h:80
TVec< TSFlt > TSFltV
Definition: ds.h:1485
TVec< TUInt > TUIntV
Definition: ds.h:1481
TTriple(TSIn &SIn)
Definition: ds.h:140
bool operator()(const TTriple< TVal1, TVal2, TVal3 > &T1, const TTriple< TVal1, TVal2, TVal3 > &T2) const
Definition: ds.h:205
bool Empty()
Definition: ds.h:2477
TTriple< TStr, TStr, TInt > TStrStrIntTr
Definition: ds.h:183
TPair(const TVal1 &_Val1, const TVal2 &_Val2)
Definition: ds.h:39
TVal & operator()(const int &X, const int &Y)
Definition: ds.h:2148
TVVec< TCh > TChVV
Definition: ds.h:2286
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:537
TVec< TIntIntVIntTr > TIntIntVIntTrV
Definition: ds.h:1517
TStr GetStr() const
Definition: dt.h:1105
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TPair< TUInt, TUInt > TUIntUIntPr
Definition: ds.h:91
TVec< TFltIntIntTr > TFltIntIntTrV
Definition: ds.h:1532
TVec< TIntIntFltTr > TIntIntFltTrV
Definition: ds.h:1507
void Save(TSOut &) const
Definition: ds.h:2812
TPair< TFlt, TInt > TFltIntPr
Definition: ds.h:97
PVec< TStr > TStrVP
Definition: ds.h:2103
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:930
TTriple< TInt, TStr, TInt > TIntStrIntTr
Definition: ds.h:168
void PutX(const int &X, const TVal &Val)
Definition: ds.h:2155
bool operator<(const TFunc &) const
Definition: ds.h:2818
void SaveXml(TSOut &SOut, const TStr &Nm) const
Definition: xmlser.h:99
bool operator==(const TQuad &Quad) const
Definition: ds.h:237
PLstNd Ins(const PLstNd &Nd, const TVal &Val)
Definition: ds.h:2717
TPair()
Definition: ds.h:37
bool operator()(const TPair< TVal1, TVal2 > &P1, const TPair< TVal1, TVal2 > &P2) const
Definition: ds.h:121
void Save(TSOut &SOut) const
Definition: ds.h:41
void Merge()
Sorts the vector and only keeps a single element of each value.
Definition: ds.h:1256
TVec< TAscFltIntKd > TAscFltIntKdV
Definition: ds.h:1535
TInt Last
Definition: ds.h:2499
TTree()
Definition: ds.h:2351
Definition: ds.h:2062
TTuple & operator=(const TTuple &Tup)
Definition: ds.h:276
int64 GetUniDevInt64(const int64 &Range=0)
Definition: dt.cpp:51
void Save(TSOut &SOut) const
Definition: ds.h:2123
static int GetInRng(const int &Val, const int &Mn, const int &Mx)
Definition: dt.h:1102
bool operator==(const TVVVec &Vec) const
Definition: ds.h:2315
TVec< TAscFlt > TAscFltV
Definition: ds.h:1486
TQQueue & operator=(const TQQueue &Queue)
Definition: ds.h:2514
Definition: ds.h:262
TLstNd< TFlt > * PFltLN
Definition: ds.h:2770
TTriple< TStr, TInt, TStrV > TStrIntStrVTr
Definition: ds.h:184
bool Empty() const
Definition: ds.h:2532
TPair< TStr, TStr > TStrPr
Definition: ds.h:107
TVVec< TVal > & operator=(const TVVec< TVal > &Vec)
Definition: ds.h:2126
TPair< TStr, TFlt > TStrFltPr
Definition: ds.h:106
TVal & At(const int &X, const int &Y)
Definition: ds.h:2145
PLstNd SearchBack(const TVal &Val)
Definition: ds.h:2754
Definition: dt.h:11
TSStack(const TSStack &Stack)
Definition: ds.h:2467
uint64 Reserved() const
Returns the total capacity of the pool.
Definition: ds.h:1597
TPair< TUInt64, TFlt > TUInt64FltPr
Definition: ds.h:95
void DelNode(const int &NodeId)
Definition: ds.h:2417
static PVecPool New(const TSize &ExpectVals=0, const TSize &GrowBy=1000000, const bool &FastCopy=false)
Definition: ds.h:1583
TFunc(TSIn &)
Definition: ds.h:2811
TInt YDim
Definition: ds.h:2111
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: xmlser.h:95
Definition: ds.h:129
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1094
int GetYDim() const
Definition: ds.h:2335
TTuple(TSIn &SIn)
Definition: ds.h:269
TVec< TStrPr > TStrPrV
Definition: ds.h:1536
void Save(TSOut &SOut) const
Definition: ds.h:2080
TVec< TStrFltKd > TStrFltKdV
Definition: ds.h:1540
TVec< TVal > ValV
Definition: ds.h:2299
int AddV(const TValV &ValV)
Adds vector ValV to the pool and returns its id.
Definition: ds.h:1756
int AddNode(const int &ParentNodeId, const TVal &NodeVal=TVal())
Definition: ds.h:2369
TVVVec(TSIn &SIn)
Definition: ds.h:2306
TKeyDat< TFlt, TBool > TFltBoolKd
Definition: ds.h:381
TTree< TStr > TStrTree
Definition: ds.h:2454
TVec< TIntIntStrTr > TIntIntStrTrV
Definition: ds.h:1506
void Push(const TVal &Val)
Definition: ds.h:2484
TVal & FirstVal() const
Definition: ds.h:2613
void Save(TSOut &SOut) const
Definition: dt.h:1058
bool operator()(const TKeyDat< TVal1, TVal2 > &P1, const TKeyDat< TVal1, TVal2 > &P2) const
Definition: ds.h:405
bool operator==(const TSStack &Stack) const
Definition: ds.h:2473
bool IsIn(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:782
bool operator<(const TVec< TVal, TSizeTy > &Vec) const
Lexicographically compares two vectors.
Definition: ds.h:912
void GetHd(THd &Hd)
Definition: ds.h:2795
TVecPool & operator=(const TVecPool &Pool)
Definition: ds.h:1975
#define forever
Definition: bd.h:6
void Reserve(const ::TSize &MxVals)
Definition: ds.h:1855
int Nds
Definition: ds.h:2592
TKeyDat(const TKey &_Key)
Definition: ds.h:343
unsigned int uint
Definition: bd.h:11
TVec< TIntStrKd > TIntStrKdV
Definition: ds.h:1514
int GetParentNodeId(const int &NodeId) const
Definition: ds.h:2378
void Save(TSOut &) const
Definition: ds.h:12
int GetChildNodeId(const int &NodeId, const int &ChildN) const
Definition: ds.h:2380
TFunc(const TFuncPt &_FuncPt)
Definition: ds.h:2810
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1090
TVal & Top()
Definition: ds.h:2481
TVVVec(const int &_XDim, const int &_YDim, const int &_ZDim)
Definition: ds.h:2304
static const int Mx
Definition: dt.h:1047
#define Fail
Definition: bd.h:238
void QSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Quick sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1205
PLstNd AddBackSorted(const TVal &Val, const bool &Asc=true)
Definition: ds.h:2681
void Load(TSIn &SIn)
Definition: ds.h:2122
::TSize GetVals() const
Definition: ds.h:1851
const TVal1 & GetVal1() const
Definition: ds.h:60
TVal * ValBf
Definition: ds.h:1568
uint64 GetMemUsed() const
Returns the total memory footprint (in bytes) of the pool.
Definition: ds.h:1605
bool IsSortedCmp(const TCmp &Cmp) const
Checks whether the vector is sorted according to the comparator Cmp.
Definition: ds.h:716
TKeyDat< TUInt64, TFlt > TUInt64FltKd
Definition: ds.h:379
void SetEmptyVal(const TVal &_EmptyVal)
Definition: ds.h:1857
PVec< TAscFlt > TAscFltVP
Definition: ds.h:2101
TVal2 Val2
Definition: ds.h:216
TFunc(const TFunc &Func)
Definition: ds.h:2809
TVal & LastVal() const
Definition: ds.h:2614
TVec< TVal > TValV
Definition: ds.h:1828
int Len() const
Definition: ds.h:2610
void CopyFrom(const TVVec< TVal > &VVec)
Definition: ds.h:2219
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TKeyDat< TInt, TFlt > TIntFltKd
Definition: ds.h:371
TVec< TIntIntIntVTr > TIntIntIntVTrV
Definition: ds.h:1518
TVec< TFltTr > TFltTrV
Definition: ds.h:1493
void PutRec(const void *Rec, const int &RecN=-1)
Definition: fl.h:536
TLstNd * Prev() const
Definition: ds.h:2579
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:942
TVVec(const int &_XDim, const int &_YDim)
Definition: ds.h:2117
void GetSwitchedKdV(const TVec< TKeyDat< TKey, TDat >, int > &SrcKdV, TVec< TKeyDat< TDat, TKey >, int > &DstKdV)
Definition: ds.h:360
void Diff(const TVec< TVal, TSizeTy > &ValV)
Subtracts ValV from this vector.
Definition: ds.h:1324
void Save(TSOut &SOut) const
Definition: ds.h:2643
void GenExt(TVal *_ValT, const TSizeTy &_Vals)
Constructs a vector of _Vals elements of memory array _ValT.
Definition: ds.h:497
TTriple< TInt, TInt, TFlt > TIntIntFltTr
Definition: ds.h:170
Definition: ds.h:2588
TVec< TIntKd > TIntKdV
Definition: ds.h:1494
void GetVal(TVal1 &_Val1, TVal2 &_Val2) const
Definition: ds.h:59
TKeyDat< TInt, TFltPr > TIntFltPrKd
Definition: ds.h:373
TVec< TFltStrPr > TFltStrPrV
Definition: ds.h:1503
TKeyDat< TUInt64, TStr > TUInt64StrKd
Definition: ds.h:380
TTree(TSIn &SIn)
Definition: ds.h:2353
TInt ZDim
Definition: ds.h:2298
TVec< TIntFltPrKd > TIntFltPrKdV
Definition: ds.h:1500
TLstNd * NextNd
Definition: ds.h:2567
TVec< TStrTr > TStrTrV
Definition: ds.h:1542
TTriple(const TVal1 &_Val1, const TVal2 &_Val2, const TVal3 &_Val3)
Definition: ds.h:138
TRec * operator->() const
Definition: ds.h:20
TKeyDat< TFlt, TStr > TFltStrKd
Definition: ds.h:387
TVal & operator()(const int &X, const int &Y, const int &Z)
Definition: ds.h:2330
void Save(TSOut &SOut) const
Definition: ds.h:141
bool IsVId(const int &VId) const
Definition: ds.h:1853
TVal3 Val3
Definition: ds.h:217
void Save(TSOut &SOut) const
Definition: ds.h:2510
void PutRec(const TRec &Rec, const int &RecN=-1)
Definition: ds.h:2798
int AddV(const TValV &ValV)
Definition: ds.h:1995
TVec< TFltPr > TFltPrV
Definition: ds.h:1492
void SetEmptyVal(const TVal &_EmptyVal)
Sets the empty value.
Definition: ds.h:1603
TVec< TStrQu > TStrQuV
Definition: ds.h:1543
Vector Pool.
Definition: ds.h:1559
void Save(TSOut &SOut) const
Definition: ds.h:1721
TCRef CRef
Definition: ds.h:2064
TVec< TStrAscFltKd > TStrAscFltKdV
Definition: ds.h:1541
TDat Dat
Definition: ds.h:339
TKeyDat< TStr, TInt > TStrIntKd
Definition: ds.h:392
void SetRecN(const int &RecN)
Definition: ds.h:2791
TTriple< TInt, TFlt, TInt > TIntFltIntTr
Definition: ds.h:171
int GetXDim() const
Definition: ds.h:2136
TVec< TIntIntPrPr > TIntIntPrPrV
Definition: ds.h:1551
Definition: ds.h:2564
TPair< TStrV, TInt > TStrVIntPr
Definition: ds.h:109
int GetSecHashCd() const
Definition: ds.h:291
TVec< ::TSize > IdToOffV
Definition: ds.h:1835
TQQueue< TIntPr > TIntPrQ
Definition: ds.h:2555
const TVal2 & GetVal2() const
Definition: ds.h:61
TVal1 Val1
Definition: ds.h:131
void Load(TSIn &SIn)
Definition: ds.h:271
TSizeTy Add(const TVal &Val, const TSizeTy &ResizeLen)
Adds element Val at the end of the vector. #TVec::Add2.
Definition: ds.h:569
PLstNd LastNd
Definition: ds.h:2594
TVec< TVal > ValV
Definition: ds.h:2500
void Clr(const bool &DoDel=false)
Definition: ds.h:2478
bool operator==(const TKeyDat &KeyDat) const
Definition: ds.h:352
int GetSecHashCd() const
Definition: ds.h:245
void Swap(const TSizeTy &ValN1, const TSizeTy &ValN2)
Swaps elements at positions ValN1 and ValN2.
Definition: ds.h:618
TKeyDat< TFlt, TFlt > TFltKd
Definition: ds.h:386
TVec< TStrStrVPr > TStrStrVPrV
Definition: ds.h:1547
TTriple< TStr, TInt, TInt > TStrIntIntTr
Definition: ds.h:181
void CompactPool(const TVal &DelVal)
Deletes all elements of value DelVal from all vectors.
Definition: ds.h:1776
TVal & At(const int &X, const int &Y, const int &Z)
Definition: ds.h:2324
TSStack()
Definition: ds.h:2465
TPair< TUInt, TInt > TUIntIntPr
Definition: ds.h:92
void Load(TSIn &SIn)
Definition: ds.h:877
PLstNd AddFront(const TVal &Val)
Definition: ds.h:2652
TQQueue(TSIn &SIn)
Definition: ds.h:2508
void Resize(const TSize &_MxVals)
Definition: ds.h:1657
static TRnd Rnd
Definition: dt.h:1051
int FindMx() const
Definition: ds.h:310
TVec(TVal *_ValT, const TSizeTy &_Vals)
Constructs a vector of _Vals elements of memory array _ValT.
Definition: ds.h:446
TPair< TInt, TVec< TInt, int > > TIntIntVPr
Definition: ds.h:86
::TSize GrowBy
Definition: ds.h:1832
TVal & LastLast()
Returns a reference to the one before last element of the vector.
Definition: ds.h:547
TRec * operator()() const
Definition: ds.h:24
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:474
TVal & operator[](const int &ValN)
Definition: ds.h:2475
void PutFront(const PLstNd &Nd)
Definition: ds.h:2689
Definition: fl.h:275
TVec< TIntTr > TIntTrV
Definition: ds.h:1490
TPair(TSIn &SIn)
Definition: ds.h:40
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...
Definition: ds.h:1061
TVal1 Val1
Definition: ds.h:215
TLst & operator=(const TLst &)
bool operator<(const TKeyDat &KeyDat) const
Definition: ds.h:353
static PVecPool Load(const TStr &FNm)
Definition: ds.h:1846
TPt< TVecPool< TVal, TSizeTy > > PVecPool
Definition: ds.h:1561
void GetCol(const int &ColN, TVec< TVal > &Vec) const
Definition: ds.h:2276
bool operator()(const TTriple< TVal1, TVal2, TVal3 > &T1, const TTriple< TVal1, TVal2, TVal3 > &T2) const
Definition: ds.h:193
TPair< TInt, TUInt64 > TIntUInt64Pr
Definition: ds.h:84
void GetNodeIdV(TIntV &NodeIdV, const int &NodeId=0)
Definition: ds.h:2392
TSize GetVals() const
Returns the total number of values stored in the vector pool.
Definition: ds.h:1593
void PutAll(const TVal &Val)
Definition: ds.h:1890
TVec< TStrKd > TStrKdV
Definition: ds.h:1546
TInt XDim
Definition: ds.h:2111
TVecPool & operator=(const TVecPool &Pool)
Definition: ds.h:1734
TSize GrowBy
Definition: ds.h:1566
TKeyDat< TFlt, TIntBoolPr > TFltIntBoolPrKd
Definition: ds.h:389
const TVal & GetEmptyVal() const
Definition: ds.h:1856
bool operator==(const TAPt &Pt) const
Definition: ds.h:16
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1027
void DelLast()
Definition: ds.h:2626
TPair< TAscFlt, TInt > TAscFltIntPr
Definition: ds.h:101
TInt First
Definition: ds.h:2499
TKeyDat< TInt, TStr > TIntStrKd
Definition: ds.h:375
int GetSecHashCd() const
Definition: ds.h:156
void PutXY(const int &X, const int &Y, const TVal &Val)
Definition: ds.h:2153
int AddEmptyV(const int &ValVLen)
Adds a vector of length ValVLen to the pool and returns its id.
Definition: ds.h:1767
TQuad< TInt, TInt, TInt, TInt > TIntQu
Definition: ds.h:253
void Clr(bool DoDel=true)
Definition: ds.h:1885
TSStack(TSIn &SIn)
Definition: ds.h:2468
bool Empty() const
Definition: ds.h:2609
TPair< TInt, TBool > TIntBoolPr
Definition: ds.h:81
TVal & operator[](const int &ValN)
Definition: ds.h:274
TVVec(TSIn &SIn)
Definition: ds.h:2121
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:885
const TVal & Top() const
Definition: ds.h:2482
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
int GetRecs()
Definition: ds.h:2793
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: xmlser.h:87
void Save(TSOut &SOut) const
Definition: ds.h:228
TPair< TInt, TStrV > TIntStrVPr
Definition: ds.h:89
void Reverse(TSizeTy LValN, TSizeTy RValN)
Reverses the order of elements between LValN...RValN.
Definition: ds.h:666
TTriple< TFlt, TFlt, TStr > TFltFltStrTr
Definition: ds.h:178
void PutV(const int &VId, const TValV &ValV)
Sets the values of vector VId with those in ValV.
Definition: ds.h:1627
void DelAll(const TVal &Val)
Removes all occurrences of element Val.
Definition: ds.h:1123
void Intrs(const TVec< TVal, TSizeTy > &ValV)
Result is the intersection of this vector with ValV.
Definition: ds.h:1310
TVec< TIntUInt64Pr > TIntUInt64PrV
Definition: ds.h:1497
int GetRecN()
Definition: ds.h:2792
TKeyDat< TStr, TFlt > TStrFltKd
Definition: ds.h:393
const TVal & operator[](const int &ValN) const
Definition: ds.h:2474
void Clr()
Definition: ds.h:2320
TLstNd & operator=(const TLstNd &)
int GetNodes() const
Definition: ds.h:2376
TPair< TInt, TFlt > TIntFltPr
Definition: ds.h:87
uint GetVLen(const int &VId) const
Definition: ds.h:1863
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1011
TVal Val
Definition: ds.h:2568
TVec< TIntFltPr > TIntFltPrV
Definition: ds.h:1499
void GetVal(TVal1 &_Val1, TVal2 &_Val2, TVal3 &_Val3, TVal4 &_Val4) const
Definition: ds.h:247
void Shuffle(TRnd &Rnd)
Definition: ds.h:2544
int Len() const
Definition: ds.h:2089
TVec< TFltIntPrKd > TFltIntPrKdV
Definition: ds.h:1528
void Clr()
Definition: ds.h:2132
TSStack(const int &MxVals)
Definition: ds.h:2466
int FindMn() const
Definition: ds.h:322
TTree & operator=(const TTree &Tree)
Definition: ds.h:2358
TQQueue< TInt > TIntQ
Definition: ds.h:2552
TSizeTy Add(TVal &Val)
Definition: ds.h:566
void Pop()
Definition: ds.h:2536
TVec< TStrFltPr > TStrFltPrV
Definition: ds.h:1538
TQuad< TStr, TStr, TInt, TInt > TStrStrIntIntQu
Definition: ds.h:251
int GetMemUsed() const
Definition: ds.h:54
TKeyDat()
Definition: ds.h:341
int GetPrimHashCd() const
Definition: ds.h:244
TVec< TVal, TSizeTy > TValV
Definition: ds.h:1562
TVal2 Val2
Definition: ds.h:132
TVal EmptyVal
Definition: ds.h:1567
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
const TVal & GetVal(const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:595
TTriple< TFlt, TFlt, TInt > TFltFltIntTr
Definition: ds.h:177
void Gen(const int &_MxLast=64, const int &_MxLen=-1)
Definition: ds.h:2522
TVec< TStrFltFltTr > TStrFltFltTrV
Definition: ds.h:1544
TAPt(TSIn &)
Definition: ds.h:11
void Save(TSOut &SOut) const
Definition: ds.h:2308
TKeyDat< TAscFlt, TInt > TAscFltIntKd
Definition: ds.h:390
void SaveXml(TSOut &SOut, const TStr &Nm) const
Definition: xmlser.h:83
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
PLstNd FirstNd
Definition: ds.h:2593
TAPt()
Definition: ds.h:8
bool IsAsc
Definition: ds.h:202
::TSize MxVals
Definition: ds.h:1832
void PutHd(const void *Hd)
Definition: fl.h:532
TVec< TUInt64IntKd > TUInt64IntKdV
Definition: ds.h:1522
TPair< TFlt, TStrPr > TFltStrPrPr
Definition: ds.h:112
bool operator==(const TFunc &Func) const
Definition: ds.h:2816
TVec< TIntPrFltKd > TIntPrFltKdV
Definition: ds.h:1513
TTriple< TCh, TCh, TCh > TChTr
Definition: ds.h:163
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1617
TVec< TAscFltStrPr > TAscFltStrPrV
Definition: ds.h:1504
TVec< TStrVIntPr > TStrVIntPrV
Definition: ds.h:1548
static int GetMn(const int &Int1, const int &Int2)
Definition: dt.h:1088
TTree< TStrIntPr > TStrIntPrTree
Definition: ds.h:2455
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1218
bool operator==(const TTuple &Tup) const
Definition: ds.h:278
bool NextPerm()
Generates next permutation of the elements in the vector.
Definition: ds.h:1267
TVVec(const TVVec &Vec)
Definition: ds.h:2115
TVec< TIntPr > TIntPrV
Definition: ds.h:1489
TVec< TVal, TSizeTy > & operator=(const TVec< TVal, TSizeTy > &Vec)
Assigns new contents to the vector, replacing its current content.
Definition: ds.h:892
TVec< TUIntIntKd > TUIntIntKdV
Definition: ds.h:1511
Definition: ds.h:2109
TAPt(TRec *_Addr)
Definition: ds.h:10
TPt< TVecPool< TVal > > PVecPool
Definition: ds.h:1827
TPt< TFltVP > PFltV
Definition: ds.h:2100
~TLst()
Definition: ds.h:2598
int GetSecHashCd() const
Definition: ds.h:2363
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1130
TVec< TStrStrIntTr > TStrStrIntTrV
Definition: ds.h:1545
TFRec(const TStr &FNm, const TFAccess &FAccess, const bool &CreateIfNo)
Definition: ds.h:2785
unsigned long long uint64
Definition: bd.h:38
void GetHd(void *Hd)
Definition: fl.h:530
TLst< TFlt > TFltL
Definition: ds.h:2769
TVal & operator[](const int &ValN) const
Definition: ds.h:2086
const TVal & LastLast() const
Returns a reference to the one before last element of the vector.
Definition: ds.h:545
TVec< TFltFltStrTr > TFltFltStrTrV
Definition: ds.h:1533
bool operator==(const TPair &Pair) const
Definition: ds.h:49
TPair< TInt, TIntPr > TIntIntPrPr
Definition: ds.h:85
TInt MxLen
Definition: ds.h:2498
void SaveXml(TSOut &SOut, const TStr &Nm) const
Definition: xmlser.h:91
void Load(bool &Bool)
Definition: fl.h:84
TQuad< TFlt, TInt, TInt, TInt > TFltIntIntIntQu
Definition: ds.h:255
static PVecPool Load(TSIn &SIn)
Definition: ds.h:1845
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1615
TLstNd()
Definition: ds.h:2570
bool IsInBin(const TVal &Val) const
Checks whether element Val is a member of the vector.
Definition: ds.h:790
TInt XDim
Definition: ds.h:2298
bool IsExt() const
Returns true if the vector was created using the GenExt().
Definition: ds.h:504
void CopyTree(const int &SrcNodeId, TTree &DstTree, const int &DstParentNodeId=-1)
Definition: ds.h:2428
TVec< TUInt64FltKd > TUInt64FltKdV
Definition: ds.h:1523
const TVal & GetDat(const TVal &Val) const
Returns reference to the first occurrence of element Val.
Definition: ds.h:792
bool Empty() const
Definition: ds.h:2131
TQuad< TInt, TInt, TFlt, TFlt > TIntIntFltFltQu
Definition: ds.h:257
TPair< TBool, TCh > TBoolChPr
Definition: ds.h:76
TVec< TFltUInt64Kd > TFltUInt64KdV
Definition: ds.h:1527
#define TSizeMx
Definition: bd.h:59
void Clr(bool DoDel=true)
Clears the contents of the pool.
Definition: ds.h:1646
TCmpTripleByVal2(const bool &AscSort=true)
Definition: ds.h:192
TVVec< TFlt > TFltVV
Definition: ds.h:2289
int GetSecHashCd() const
Definition: ds.h:356
TCmpTripleByVal3(const bool &AscSort=true)
Definition: ds.h:204
bool IsNext() const
Definition: ds.h:2578
TVVVec< TFlt > TFltVVV
Definition: ds.h:2342
Definition: bd.h:402
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
void Resize(const ::TSize &_MxVals)
Definition: ds.h:1897
static TVec< TVal, TSizeTy > GetV(const TVal &Val1, const TVal &Val2, const TVal &Val3)
Returns a vector on elements Val1...Val3.
Definition: ds.h:808
void Save(TSOut &SOut) const
Definition: ds.h:346
void Load(TSIn &SIn)
Definition: dt.h:1057
size_t TSize
Definition: bd.h:58
#define Assert(Cond)
Definition: bd.h:251
TTree< TFlt > TFltTree
Definition: ds.h:2453
TSStack< TInt > TIntS
Definition: ds.h:2490
TInt YDim
Definition: ds.h:2298
int GetPrimHashCd() const
Definition: ds.h:2362
TVal & Last()
Returns a reference to the last element of the vector.
Definition: ds.h:541
TVec< TUInt64StrKd > TUInt64StrKdV
Definition: ds.h:1524
TSizeTy SearchVForw(const TVec< TVal, TSizeTy > &ValV, const TSizeTy &BValN=0) const
Returns the starting position of vector ValV.
Definition: ds.h:1454
static void BSortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Bubble sorts the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:693
PVec< TVal > & operator=(const PVec< TVal > &Vec)
Definition: ds.h:2082
void SwapY(const int &Y1, const int &Y2)
Definition: ds.h:2187
bool IsAsc
Definition: ds.h:118
const TVal & GetEmptyVal() const
Returns the reference to an empty value.
Definition: ds.h:1601
void Save(TSOut &SOut) const
Definition: ds.h:2469
TPair< TUInt64, TUInt64 > TUInt64Pr
Definition: ds.h:94
TVecPool< TInt > TIntVecPool
Definition: ds.h:2054
TVal4 Val4
Definition: ds.h:218
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.
Definition: ds.h:814
void PutAll(const TVal &Val)
Sets the values of all elements in the pool to Val.
Definition: ds.h:1651
int Len() const
Definition: ds.h:2533
Compares the triple by the second value.
Definition: ds.h:188
const TVal & Last() const
Returns a reference to the last element of the vector.
Definition: ds.h:539
TQQueue< TFlt > TFltQ
Definition: ds.h:2553
TPt< TAscFltVP > PAscFltV
Definition: ds.h:2102
static int GetHashCd(const int hc1, const int hc2)
Definition: bd.h:590
static PVecPool Load(TSIn &SIn)
Definition: ds.h:1585
void Clr()
Definition: ds.h:2604
TLst< TStr > TStrL
Definition: ds.h:2775
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 LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: xmlser.h:71
Definition: ds.h:4
TVec< TCh > TChV
Definition: ds.h:1479
TTriple< TInt, TInt, TVec< TInt, int > > TIntIntIntVTr
Definition: ds.h:174
bool operator<(const TTuple &Tup) const
Definition: ds.h:281
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
TQuad< TFlt, TFlt, TFlt, TFlt > TFltQu
Definition: ds.h:254
TRec * Addr
Definition: ds.h:6
TTriple< TFlt, TFlt, TFlt > TFltTr
Definition: ds.h:175
const TVal & operator()(const int &X, const int &Y, const int &Z) const
Definition: ds.h:2332
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: xmlser.h:103
TQQueue(const TQQueue &Queue)
Definition: ds.h:2505
::TSize Reserved() const
Definition: ds.h:1854
TPair< TInt, TStr > TIntStrPr
Definition: ds.h:88
TVec< TStrIntKd > TStrIntKdV
Definition: ds.h:1539
TVVec()
Definition: ds.h:2114
void AddXDim()
Definition: ds.h:2230
void Gen(const int &_XDim, const int &_YDim)
Definition: ds.h:2133
const TVal & operator[](const TSizeTy &ValN) const
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:466
int Len()
Definition: ds.h:2480
void GetMxValXY(int &X, int &Y) const
Definition: ds.h:2212
Definition: fl.h:491
TAPt & operator=(TRec *_Addr)
Definition: ds.h:15
TTriple< TUInt64, TUInt64, TUInt64 > TUInt64Tr
Definition: ds.h:167
#define FailR(Reason)
Definition: bd.h:240
PVec< TFlt > TFltVP
Definition: ds.h:2099
TLstNd< TVal > * PLstNd
Definition: ds.h:2590
TSizeTy IntrsLen(const TVec< TVal, TSizeTy > &ValV) const
Returns the size of the intersection of vectors this and ValV.
Definition: ds.h:1378
TFRec & operator=(const TFRec &)
TVal GetVal(const int &ValN) const
Definition: ds.h:2090
TVVec(const TVec< TVal > &_ValV, const int &_XDim, const int &_YDim)
Definition: ds.h:2119
TVVec< TBool > TBoolVV
Definition: ds.h:2285
const TVal & Top() const
Definition: ds.h:2534
TPair< TInt, TCh > TIntChPr
Definition: ds.h:82
TPair< TIntPr, TInt > TIntPrIntPr
Definition: ds.h:90
const TVal & operator()(const int &X, const int &Y) const
Definition: ds.h:2150
void PutHd(const THd &Hd)
Definition: ds.h:2796
Definition: ds.h:2496
TPair< TFlt, TFlt > TFltPr
Definition: ds.h:99
Compares the triple by the third value.
Definition: ds.h:200
void GetRow(const int &RowN, TVec< TVal > &Vec) const
Definition: ds.h:2268
Definition: ds.h:2461
Definition: fl.h:128
TVec< TAscFltIntPr > TAscFltIntPrV
Definition: ds.h:1534
TVec< TFltUInt64Pr > TFltUInt64PrV
Definition: ds.h:1502
TPair< TBool, TFlt > TBoolFltPr
Definition: ds.h:77
TVVVec(const TVVVec &Vec)
Definition: ds.h:2302
int GetRecs()
Definition: fl.cpp:830
void DelY(const int &Y)
Definition: ds.h:2256
PLstNd AddFrontSorted(const TVal &Val, const bool &Asc=true)
Definition: ds.h:2668
TVal & GetNodeVal(const int &NodeId)
Definition: ds.h:2381
TKeyDat< TUInt, TInt > TUIntIntKd
Definition: ds.h:376
TSizeTy SearchBin(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1418
TTriple()
Definition: ds.h:135
TVal & GetAddDat(const TVal &Val)
Returns reference to the first occurrence of element Val.
Definition: ds.h:796
void SetVal(const TSizeTy &ValN, const TVal &Val)
Sets the value of element at position ValN to Val.
Definition: ds.h:599
int GetRecN()
Definition: fl.cpp:823
TFunc()
Definition: ds.h:2808
void Save(const bool &Bool)
Definition: fl.h:173
static TPt< PVec< TVal > > Load(TSIn &SIn)
Definition: ds.h:2079
TPair< TStr, TStrV > TStrStrVPr
Definition: ds.h:108
TPair< TAscFlt, TAscFlt > TAscFltPr
Definition: ds.h:102
TVec< TIntStrIntIntQu > TIntStrIntIntQuV
Definition: ds.h:1550
TVec< TVal > ValV
Definition: ds.h:2112
#define max(a, b)
Definition: bd.h:350
TLstNd< TAscFltIntKd > * PAscFltIntKdLN
Definition: ds.h:2774
TPair< TUCh, TUInt64 > TUChUInt64Pr
Definition: ds.h:79
~TVecPool()
Definition: ds.h:1582
TTriple< TInt, TFlt, TFlt > TIntFltFltTr
Definition: ds.h:172
Definition: dt.h:1042
TQuad()
Definition: ds.h:220
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:422
TVVec< TInt > TIntVV
Definition: ds.h:2287
PLstNd Last() const
Definition: ds.h:2612
int GetPrimHashCd() const
Definition: ds.h:155
TFuncPt operator()() const
Definition: ds.h:2820
static TPt< PVec< TVal > > New(const int &MxVals, const int &Vals)
Definition: ds.h:2073
TVec< TFltIntIntIntQu > TFltIntIntIntQuV
Definition: ds.h:1549
TVec< TUChIntPr > TUChIntPrV
Definition: ds.h:1495
void Gen(const int &_XDim, const int &_YDim, const int &_ZDim)
Definition: ds.h:2321
TVec< TStrIntPr > TStrIntPrV
Definition: ds.h:1537
const TVal & operator[](const int &ValN) const
Definition: ds.h:2518
void ShuffleAll(TRnd &Rnd=TInt::Rnd)
Definition: ds.h:2045
TVec< TChA > TChAV
Definition: ds.h:1488
TPair< TAscFlt, TStr > TAscFltStrPr
Definition: ds.h:104
TLstNd< TStr > * PStrLN
Definition: ds.h:2776
const TVal & At(const int &X, const int &Y, const int &Z) const
Definition: ds.h:2327
static TVec< TVal, TSizeTy > GetV(const TVal &Val1, const TVal &Val2, const TVal &Val3, const TVal &Val4)
Returns a vector on elements Val1...Val4.
Definition: ds.h:811
TVVec< TStr > TStrVV
Definition: ds.h:2290
TTriple< TInt, TVec< TInt, int >, TInt > TIntIntVIntTr
Definition: ds.h:173
TVec< TIntStrVPr > TIntStrVPrV
Definition: ds.h:1516
TQQueue< TIntStrPr > TIntStrPrQ
Definition: ds.h:2556
bool PrevPerm()
Generates previous permutation of the elements in the vector.
Definition: ds.h:1289
Definition: dt.h:201
TSizeTy Add(const TVal &Val)
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:564
void SaveXml(TSOut &SOut, const TStr &Nm) const
Definition: xmlser.h:75
Definition: ds.h:2296
TVal & GetVal(const TSizeTy &ValN)
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:597
int GetSecHashCd() const
Definition: ds.h:57
void ISort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Insertion sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1148
TKeyDat(const TKey &_Key, const TDat &_Dat)
Definition: ds.h:344
void Ins(const TSizeTy &ValN, const TVal &Val)
Inserts new element Val before the element at position ValN.
Definition: ds.h:1086
int GetPrimHashCd() const
Definition: ds.h:355
TVec< TStr > TStrV
Definition: ds.h:1487
void Save(TSOut &SOut) const
Definition: ds.h:2354
void Push()
Definition: ds.h:2483
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.
Definition: ds.h:817
TKeyDat< TFlt, TIntPr > TFltIntPrKd
Definition: ds.h:384
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 int GetRnd(const int &Range=0)
Definition: dt.h:1083
void Reserve(const TSize &MxVals)
Reserves enough capacity for the pool to store MxVals elements.
Definition: ds.h:1599
void DelFirst()
Definition: ds.h:2625
TLstNd< TIntKd > * PIntKdLN
Definition: ds.h:2768
TQuad(const TQuad &Quad)
Definition: ds.h:222
TKeyDat & operator=(const TKeyDat &KeyDat)
Definition: ds.h:350
Definition: ds.h:32
TKeyDat< TUInt64, TInt > TUInt64IntKd
Definition: ds.h:378
void GetRec(void *Rec, const int &RecN=-1)
Definition: fl.h:534
TVec< TFltBoolKd > TFltBoolKdV
Definition: ds.h:1525
TSizeTy LastValN() const
Returns the position of the last element.
Definition: ds.h:543
TVec< TUInt64StrPr > TUInt64StrPrV
Definition: ds.h:1521
PLstNd AddBack(const TVal &Val)
Definition: ds.h:2660
bool Empty() const
Definition: ds.h:2088
void ShuffleY(TRnd &Rnd)
Definition: ds.h:2207
TVec< TIntStrPrPr > TIntStrPrPrV
Definition: ds.h:1515
void PutV(const int &VId, const TValV &ValV)
Definition: ds.h:1872
static PVecPool New(const ::TSize &ExpectVals=0, const ::TSize &GrowBy=1000000, const bool &FastCopy=false)
Definition: ds.h:1843
TKeyDat< TIntPr, TFlt > TIntPrFltKd
Definition: ds.h:372
void AddYDim()
Definition: ds.h:2237
TKeyDat< TStr, TBool > TStrBoolKd
Definition: ds.h:391
TStr GetStr() const
Definition: ds.h:296
TVec(const TSizeTy &_Vals)
Constructs a vector (an array) of length _Vals.
Definition: ds.h:435
bool Empty() const
Definition: ds.h:26
TKey Key
Definition: ds.h:338
TPt< TStrVP > PStrV
Definition: ds.h:2104
void GetSwitchedPrV(const TVec< TPair< TVal1, TVal2 >, TSizeTy > &SrcPrV, TVec< TPair< TVal2, TVal1 >, TSizeTy > &DstPrV)
Definition: ds.h:67
TTree< TInt > TIntTree
Definition: ds.h:2452
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.
Definition: ds.h:820
void Load(TSIn &SIn)
Definition: ds.h:43
TVec< TUInt64 > TUInt64V
Definition: ds.h:1483
TVec< TFlt > TFltV
Definition: ds.h:1484
bool Empty() const
Definition: ds.h:2319
int AddRoot(const TVal &NodeVal=TVal())
Definition: ds.h:2373
PFRnd FRnd
Definition: ds.h:2783
TVec< TTriple< TInt, TIntV, TVal > > NodeV
Definition: ds.h:2349
TVal GetXY(const int &X, const int &Y) const
Definition: ds.h:2159
int GetPrimHashCd() const
Definition: ds.h:56
TVal & operator[](const TSizeTy &ValN)
Returns a reference to the element at position ValN in the vector.
Definition: ds.h:470
TSizeTy UnionLen(const TVec< TVal, TSizeTy > &ValV) const
Returns the size of the union of vectors this and ValV.
Definition: ds.h:1392
void Del(const TVal &Val)
Definition: ds.h:2728
TVVec< TSFlt > TSFltVV
Definition: ds.h:2288
TLst()
Definition: ds.h:2596
TVec< TIntQu > TIntQuV
Definition: ds.h:1491
void Union(const TVec< TVal, TSizeTy > &ValV)
Result is the union of this vector with ValV.
Definition: ds.h:1317
void Pop()
Definition: ds.h:2485
TLstNd(TLstNd *_PrevNd, TLstNd *_NextNd, const TVal &_Val)
Definition: ds.h:2572
TKeyDat< TUInt, TUInt > TUIntKd
Definition: ds.h:377
TVec< TUChUInt64Pr > TUChUInt64PrV
Definition: ds.h:1496
Definition: dt.h:412
Definition: ds.h:213
void PutBack(const PLstNd &Nd)
Definition: ds.h:2703
TSizeTy Partition(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Partitions the values between positions MnLValN...MxLValN.
Definition: ds.h:1186
TSStack< TBoolChPr > TBoolChS
Definition: ds.h:2491
TTriple< TStr, TStr, TStr > TStrTr
Definition: ds.h:180
TKeyDat(const TKeyDat &KeyDat)
Definition: ds.h:342
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:550
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
TQuad & operator=(const TQuad &Quad)
Definition: ds.h:233
bool IsSorted(const bool &Asc=true) const
Checks whether the vector is sorted in ascending (if Asc=true) or descending (if Asc=false) order...
Definition: ds.h:1223
void Pack()
The vector reduces its capacity (frees memory) to match its size.
Definition: ds.h:987
TCRef CRef
Definition: ds.h:1564
bool IsPrev() const
Definition: ds.h:2577
bool operator<(const TAPt &Pt) const
Definition: ds.h:18
TQQueue(const int &_MxLast=64, const int &_MxLen=-1)
Definition: ds.h:2502
TVec< TFltStrPrPr > TFltStrPrPrV
Definition: ds.h:1531
TAPt & operator=(const TAPt &Pt)
Definition: ds.h:14
int Add(const TVal &Val)
Definition: ds.h:2092
TVec< TVal, TSizeTy > & operator+(const TVal &Val)
Appends value Val to the vector.
Definition: ds.h:458
int GetVecs() const
Returns the total number of vectors stored in the vector pool.
Definition: ds.h:1591
TPair< TInt, TStrPr > TIntStrPrPr
Definition: ds.h:111
int Len() const
Definition: ds.h:273
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
void DelX(const int &X)
Definition: ds.h:2244
TCmpPairByVal2(const bool &AscSort=true)
Definition: ds.h:120
void Shuffle(TRnd &Rnd)
Randomly shuffles the elements of the vector.
Definition: ds.h:1235
TSizeTy SearchForw(const TVal &Val, const TSizeTy &BValN=0) const
Returns the position of an element with value Val.
Definition: ds.h:1440
int GetXDim() const
Definition: ds.h:2334
static PVecPool Load(const TStr &FNm)
Definition: ds.h:1586
TPair< TStr, TInt > TStrIntPr
Definition: ds.h:105
TQQueue< TStr > TStrQ
Definition: ds.h:2554
void ShuffleAll(TRnd &Rnd=TInt::Rnd)
Shuffles the order of all elements in the pool.
Definition: ds.h:1805
TBool FastCopy
Definition: ds.h:1565
TKeyDat< TFlt, TUInt > TFltUIntKd
Definition: ds.h:385
TTuple(const TVal &InitVal)
Definition: ds.h:267
TVecPool(const ::TSize &ExpectVals=0, const ::TSize &_GrowBy=1000000, const bool &_FastCopy=false, const TVal &_EmptyVal=TVal())
Definition: ds.h:1924
TKeyDat< TInt, TInt > TIntKd
Definition: ds.h:369
bool IsIn(const TVal &Val, TSizeTy &ValN) const
Checks whether element Val is a member of the vector.
Definition: ds.h:786
TTriple< TCh, TInt, TInt > TChIntIntTr
Definition: ds.h:164
void GetV(const int &VId, TValV &ValV) const
Definition: ds.h:1869
TVal * ValBf
Definition: ds.h:1834
TVec< uint64, int > IdToOffV
Definition: ds.h:1569
TSStack & operator=(const TSStack &Stack)
Definition: ds.h:2471
TVecPool(const TSize &ExpectVals=0, const TSize &_GrowBy=1000000, const bool &_FastCopy=false, const TVal &_EmptyVal=TVal())
Vector pool constructor.
Definition: ds.h:1685
static TVec< TVal, TSizeTy > GetV(const TVal &Val1, const TVal &Val2)
Returns a vector on elements Val1, Val2.
Definition: ds.h:805
TVal1 Val1
Definition: ds.h:34
TVec< TInt > TIntV
Definition: ds.h:1482
TVal2 Val2
Definition: ds.h:35
TKeyDat< TInt, TSFlt > TIntSFltKd
Definition: ds.h:374
TAPt(const TAPt &Pt)
Definition: ds.h:9
TVal ValV[NVals]
Definition: ds.h:264
int GetYDim() const
Definition: ds.h:2137
Definition: bd.h:196
TKeyDat(TSIn &SIn)
Definition: ds.h:345
void Push(const TVal &Val)
Definition: ds.h:2539
void Sort(const bool &Asc=true)
Definition: ds.h:302
TCmpKeyDatByDat(const bool &AscSort=true)
Definition: ds.h:404
void Reverse()
Reverses the order of the elements in the vector.
Definition: ds.h:1250
bool operator<(const TPair &Pair) const
Definition: ds.h:51
#define AssertR(Cond, Reason)
Definition: bd.h:258
void SwapX(const int &X1, const int &X2)
Definition: ds.h:2181
TQuad< TInt, TStr, TInt, TInt > TIntStrIntIntQu
Definition: ds.h:256
void GenRandomTree(const int &Nodes, TRnd &Rnd)
Definition: ds.h:2405
int GetZDim() const
Definition: ds.h:2336
void Swap(TVVec< TVal > &Vec)
Definition: ds.h:2193
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
int GetChildren(const int &NodeId) const
Definition: ds.h:2379
TInt MxLast
Definition: ds.h:2498
void ShuffleX(TRnd &Rnd)
Definition: ds.h:2202
TVec()
Definition: ds.h:432
TTriple< TInt, TInt, TInt > TIntTr
Definition: ds.h:166
TSizeTy AddBackSorted(const TVal &Val, const bool &Asc)
Adds element Val to a sorted vector.
Definition: ds.h:1042
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVal & GetVal()
Definition: ds.h:2581
TRec & operator[](const int &RecN) const
Definition: ds.h:22
TPair< TFlt, TStr > TFltStrPr
Definition: ds.h:100
void SetRecN(const int &RecN)
Definition: fl.cpp:818
Definition: ds.h:2804
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TSizeTy Count(const TVal &Val) const
Counts the number of occurrences of Val in the vector.
Definition: ds.h:1410
bool operator==(const TVec< TVal, TSizeTy > &Vec) const
Checks that the two vectors have the same contents.
Definition: ds.h:903
TQQueue< TFltV > TFltVQ
Definition: ds.h:2557
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:506
void MoveFrom(TVec< TVal, TSizeTy > &Vec)
Takes over the data and the capacity from Vec.
Definition: ds.h:1002
bool operator==(const TTriple &Triple) const
Definition: ds.h:149
bool Cmp(const int &RelOp, const TRec &Rec1, const TRec &Rec2)
Definition: bd.h:426
void SaveXml(TSOut &SOut, const TStr &Nm) const
TLst< TIntKd > TIntKdL
Definition: ds.h:2767
TVec(const TSizeTy &_MxVals, const TSizeTy &_Vals)
Constructs a vector (an array) of length _Vals, while reserving enough memory to store _MxVals elemen...
Definition: ds.h:439
TVec< TIntFltIntTr > TIntFltIntTrV
Definition: ds.h:1508
static TPt< PVec< TVal > > New()
Definition: ds.h:2070
Definition: ds.h:2781
TTuple()
Definition: ds.h:266
void Clr(const bool &DoDel=true)
Definition: ds.h:2521
TLst< TFltIntKd > TFltIntKdL
Definition: ds.h:2771
TFunc & operator=(const TFunc &Func)
Definition: ds.h:2814
TVVec< TIntPr > TIntPrVV
Definition: ds.h:2291
void Resize(const TSizeTy &_MxVals=-1)
Resizes the vector so that it can store at least _MxVals.
Definition: ds.h:831
int GetMemUsed() const
Definition: ds.h:2365
static TVec< TVal, TSizeTy > GetV(const TVal &Val1)
Returns a vector on element Val1.
Definition: ds.h:802
TRec & operator*() const
Definition: ds.h:21
TVec< TUInt64FltPr > TUInt64FltPrV
Definition: ds.h:1520
TVec< TBool > TBoolV
Definition: ds.h:1478
TVVVec< TVal > & operator=(const TVVVec< TVal > &Vec)
Definition: ds.h:2311
static TPt< PVec< TVal > > New(const TVec< TVal > &V)
Definition: ds.h:2076
TKeyDat< TFlt, TInt > TFltIntKd
Definition: ds.h:382
void SortCmp(const TCmp &Cmp)
Sorts the elements of the vector using the comparator Cmp.
Definition: ds.h:713
TPair< TFlt, TUInt64 > TFltUInt64Pr
Definition: ds.h:98
char * CStr()
Definition: dt.h:476
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: xmlser.h:79
bool operator<(const TQuad &Quad) const
Definition: ds.h:239
void Gen(const TSizeTy &_MxVals, const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements, while reserving enough memory for _MxVals elements...
Definition: ds.h:490
Definition: ds.h:2347
void GetVal(TVal1 &_Val1, TVal2 &_Val2, TVal3 &_Val3) const
Definition: ds.h:159
void BSort(const TSizeTy &MnLValN, const TSizeTy &MxRValN, const bool &Asc)
Bubble sorts the values between positions MnLValN...MxLValN.
Definition: ds.h:1135
TKeyDat< TInt, TUInt64 > TIntUInt64Kd
Definition: ds.h:370
TSizeTy Vals
Vector length. Length is the number of elements stored in the vector.
Definition: ds.h:425
TVec(TSIn &SIn)
Definition: ds.h:449
TVec< TVal > & Get1DVec()
Definition: ds.h:2140
TVec< TFltIntPr > TFltIntPrV
Definition: ds.h:1501
bool IsVId(const int &VId) const
Tests whether vector of id VId is in the pool.
Definition: ds.h:1595
void Clr()
Definition: ds.h:2367
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
TTuple(const TTuple &Tup)
Definition: ds.h:268
TSizeTy GetMemSize() const
Returns the memory size (the number of bytes) of a binary representation.
Definition: ds.h:477
TPt< TIntVecPool > PIntVecPool
Definition: ds.h:2057
void CompactPool(const TVal &DelVal)
Definition: ds.h:2016
TLstNd< TInt > * PIntLN
Definition: ds.h:2766
TVVVec< TInt > TIntVVV
Definition: ds.h:2341
Definition: dt.h:881
TVec< TFltKd > TFltKdV
Definition: ds.h:1529
void DelLast()
Removes the last element of the vector.
Definition: ds.h:609
bool IsAsc
Definition: ds.h:402
TTree(const TTree &Tree)
Definition: ds.h:2352
PLstNd SearchForw(const TVal &Val)
Definition: ds.h:2744
TTriple< TInt, TInt, TStr > TIntIntStrTr
Definition: ds.h:169
void Trunc(const TSizeTy &_Vals=-1)
Truncates the vector's length and capacity to _Vals elements.
Definition: ds.h:964
static void SwapI(TIter LVal, TIter RVal)
Swaps the elements that iterators LVal and RVal point to.
Definition: ds.h:620
bool IsAsc
Definition: ds.h:190
TVec< TIntFltKd > TIntFltKdV
Definition: ds.h:1512
TPair & operator=(const TPair &Pair)
Definition: ds.h:47
TKeyDat< TStr, TAscFlt > TStrAscFltKd
Definition: ds.h:394
TVec< TQQueue< TInt > > TIntQV
Definition: ds.h:2559
int GetCols() const
Definition: ds.h:2139
TBool FastCopy
Definition: ds.h:1831
bool operator<(const TTree &Tree) const
Definition: ds.h:2360
TFAccess
Definition: fl.h:347
TIter GetI(const TSizeTy &ValN) const
Returns an iterator an element at position ValN.
Definition: ds.h:554
int GetRows() const
Definition: ds.h:2138
TVal * GetValVPt(const int &VId) const
Definition: ds.h:1866
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.
Definition: ds.h:826
TPair< TUCh, TInt > TUChIntPr
Definition: ds.h:78
TLstNd * PrevNd
Definition: ds.h:2566
TLst< TAscFltIntKd > TAscFltIntKdL
Definition: ds.h:2773
TPair< TUInt64, TInt > TUInt64IntPr
Definition: ds.h:93
const TVal & At(const int &X, const int &Y) const
Definition: ds.h:2142
TSize Vals
Definition: ds.h:1566
TSize MxVals
Definition: ds.h:1566
void GetRec(TRec &Rec, const int &RecN=-1)
Definition: ds.h:2797
TQuad(TSIn &SIn)
Definition: ds.h:226
void PutY(const int &Y, const TVal &Val)
Definition: ds.h:2157
int GetPrimHashCd() const
Definition: ds.h:288
TVec< TIntStrIntTr > TIntStrIntTrV
Definition: ds.h:1509
void PutAll(const TVal &Val)
Definition: ds.h:2154
TLstNd< TFltIntKd > * PFltIntKdLN
Definition: ds.h:2772
void GetSubValV(const int &_BValN, const int &_EValN, TVec< TVal > &SubValV) const
Definition: ds.h:2524
TStr GetXOutOfBoundsErrMsg(const TSizeTy &ValN) const
Constructs the out of bounds error message.
Definition: ds.h:861
TSizeTy SearchBack(const TVal &Val) const
Returns the position of an element with value Val.
Definition: ds.h:1447
TKeyDat< TFlt, TUInt64 > TFltUInt64Kd
Definition: ds.h:383
::TSize GetMemUsed() const
Definition: ds.h:1858
TVal * ValT
Definition: ds.h:426
TLst< TInt > TIntL
Definition: ds.h:2765
void Reserve(const TSizeTy &_MxVals, const TSizeTy &_Vals)
Reserves enough memory for the vector to store _MxVals elements and sets its length to _Vals...
Definition: ds.h:508
TTriple< TFlt, TInt, TInt > TFltIntIntTr
Definition: ds.h:176
TQuad(const TVal1 &_Val1, const TVal2 &_Val2, const TVal3 &_Val3, const TVal4 &_Val4)
Definition: ds.h:224
bool operator!=(const TAPt &Pt) const
Definition: ds.h:17
bool IsIn(const TVal &Val) const
Definition: ds.h:2479
TVec< TIntStrPr > TIntStrPrV
Definition: ds.h:1505
TVal3 Val3
Definition: ds.h:133
PLstNd First() const
Definition: ds.h:2611
Compares the pair by the second value.
Definition: ds.h:116
TVec< TIntUInt64Kd > TIntUInt64KdV
Definition: ds.h:1498
TVVVec()
Definition: ds.h:2301
void Save(TSOut &SOut) const
Definition: ds.h:270
TSizeTy GetMxValN() const
Returns the position of the largest element in the vector.
Definition: ds.h:1467
TVec< TUCh > TUChV
Definition: ds.h:1480
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568
TKeyDat< TStr, TStr > TStrKd
Definition: ds.h:395
TTriple & operator=(const TTriple &Triple)
Definition: ds.h:146
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:420
TTriple< TUCh, TInt, TInt > TUChIntIntTr
Definition: ds.h:165
int AddEmptyV(const int &ValVLen)
Definition: ds.h:2006
TVec< TFltStrKd > TFltStrKdV
Definition: ds.h:1530
int GetMemUsed() const
Definition: ds.h:157
TPair< TUInt64, TStr > TUInt64StrPr
Definition: ds.h:96
void WrTree(const int &NodeId=0, const int &Lev=0)
Definition: ds.h:2439
TTriple< TStr, TFlt, TFlt > TStrFltFltTr
Definition: ds.h:182
TTriple< TChA, TChA, TChA > TChATr
Definition: ds.h:179
TVec< TVal > ValV
Definition: ds.h:2463
TSizeTy AddV(const TVec< TVal, TSizeTy > &ValV)
Adds the elements of the vector ValV to the to end of the vector.
Definition: ds.h:1020
void GetSubValV(const TSizeTy &BValN, const TSizeTy &EValN, TVec< TVal, TSizeTy > &ValV) const
Returns a vector on elements at positions BValN...EValN.
Definition: ds.h:1076
bool operator<(const TTriple &Triple) const
Definition: ds.h:151
TLstNd * Next() const
Definition: ds.h:2580
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
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.
Definition: ds.h:823