SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
shash.h
Go to the documentation of this file.
1 #ifndef shash_h
2 #define shash_h
3 
5 // Hash-List-File
6 // saves and loads hash tables into files and allows fast
7 // iteration over the saved hash table file
8 
9 template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey> >
10 class TKeyDatFl {
11 private:
14  TKey Key;
15  TDat Dat;
16 public:
17  TKeyDatFl(const TStr& FNm) : FIn(FNm) { ElemCnt.Load(FIn); }
18  int Len() const { return ElemCnt; }
19  bool Next() { if (FIn.Eof()) { return false; }
20  Key.Load(FIn); Dat.Load(FIn); return true; }
21  const TKey& GetKey() const { return Key; }
22  TKey& GetKey() { return Key; }
23  const TDat& GetDat() const { return Dat; }
24  TDat& GetDat() { return Dat; }
25 
26  static void Save(const TStr& OutFNm, const THash<TKey, TDat, THashFunc>& Hash) {
27  TFOut FOut(OutFNm); Load(FOut, Hash); }
28  static void Save(TSOut& SOut, const THash<TKey, TDat, THashFunc>& Hash) {
29  SOut.Save(Hash.Len());
30  for (int k = Hash.FFirstKeyId(); Hash.FNextKeyId(k); ) {
31  Hash.GetKey(k).Save(SOut); Hash[k].Save(SOut); }
32  }
33  static void LoadHash(const TStr& InFNm, THash<TKey, TDat, THashFunc>& Hash, const int& LoadN=-1) {
34  TFIn FIn(InFNm); Load(FIn, Hash, LoadN); }
35  static void LoadHash(TSIn& SIn, THash<TKey, TDat, THashFunc>& Hash, int LoadN=-1) {
36  TInt ElemCnt(SIn); const int Start=clock();
37  if (ElemCnt < LoadN || LoadN == -1) { LoadN = ElemCnt; }
38  printf("Loading %s: %d elements ... ", SIn.GetSNm().CStr(), LoadN); Hash.Gen(LoadN);
39  for (int i = 0; i < LoadN; i++) { Hash.AddDat(TKey(SIn)).Load(SIn); }
40  printf(" [%ds]\n", int((clock()-Start)/CLOCKS_PER_SEC));
41  }
42  static void LoadKeyV(TSIn& SIn, TVec<TKey>& KeyV, int LoadN=-1) {
43  TInt ElemCnt(SIn); const int Start=clock();
44  if (ElemCnt < LoadN || LoadN == -1) { LoadN = ElemCnt; }
45  printf("Loading %s: %d elements ... ", SIn.GetSNm().CStr(), LoadN); KeyV.Gen(LoadN, 0);
46  for (int i = 0; i < LoadN; i++) { KeyV.Add(TKey(SIn)); TDat D(SIn); }
47  printf(" [%ds]\n", int((clock()-Start)/CLOCKS_PER_SEC));
48  }
49  static void LoadDatV(TSIn& SIn, TVec<TDat>& DatV, int LoadN=-1) {
50  TInt ElemCnt(SIn); const int Start=clock();
51  if (ElemCnt < LoadN || LoadN == -1) { LoadN = ElemCnt; }
52  printf("Loading %s: %d elements ... ", SIn.GetSNm().CStr(), LoadN); DatV.Gen(LoadN, 0);
53  for (int i = 0; i < LoadN; i++) { TKey(SIn); DatV.Add(TDat(SIn)); }
54  printf(" [%ds]\n", int((clock()-Start)/CLOCKS_PER_SEC));
55  }
56 };
57 
59 // Sparse Table Group
60 template <class TVal, uint16 GroupSize> // GroupSize=48; == 32*x+16
61 class TSparseGroup {
62 private:
63  unsigned char BitSet [(GroupSize-1)/8 + 1]; // fancy math is so we round up
64  uint16 Buckets; // limits GroupSize to 64K
65  TVal *Group;
66 private:
67  static int CharBit(const int& ValN) { return ValN >> 3; }
68  static int ModBit(const int& ValN) { return 1 << (ValN&7); }
69  bool BMTest(const int& ValN) const { return (BitSet[CharBit(ValN)] & ModBit(ValN)) != 0; }
70  void BMSet(const int& ValN) { BitSet[CharBit(ValN)] |= ModBit(ValN); }
71  void BMClear(const int& ValN) { BitSet[CharBit(ValN)] &= ~ModBit(ValN); }
72  static int PosToOffset(const unsigned char *BitSet, int Pos);
73 public:
74  TSparseGroup() : Buckets(0), Group(NULL) { memset(BitSet, 0, sizeof(BitSet)); }
75  TSparseGroup(TSIn& SIn) : Buckets(0), Group(NULL) { Load(SIn); }
76  TSparseGroup(const TSparseGroup& SG);
77  ~TSparseGroup() { if (Group != NULL) delete [] Group; }
78  void Load(TSIn& SIn);
79  void Save(TSOut& SOut) const;
80 
82  bool operator == (const TSparseGroup& SG) const;
83  bool operator < (const TSparseGroup& SG) const;
84 
85  int Len() const { return Buckets; }
86  int MxLen() const { return GroupSize; }
87  int Reserved() const { return GroupSize; }
88  bool Empty() const { return Buckets == 0; }
89  void Clr(const bool& DoDel = true);
90  int GetGroupSize() const { return GroupSize; }
91  uint GetDiskSz() const { return sizeof(BitSet) + sizeof(uint16) + Buckets*sizeof(TVal); }
92 
93  bool IsEmpty(const int& ValN) const { return ! BMTest(ValN); }
94  const TVal& Offset(const int& Pos) const { return Group[Pos]; }
95  TVal& Offset(const int& Pos) { return Group[Pos]; }
96  int OffsetToPos(int Offset) const;
97  int PosToOffset(int Pos) const { return PosToOffset(BitSet, Pos); }
98 
99  const TVal& DefVal() const { static TVal DefValue = TVal(); return DefValue; }
100  const TVal& Get(const int& ValN) const {
101  if (BMTest(ValN)) return Group[PosToOffset(BitSet, ValN)]; else return DefVal(); }
102  const TVal& operator [] (const int ValN) const { return Get(ValN); }
103 
104  TVal& Set(const int& ValN, const TVal& Val);
105  TVal& Set(const int& ValN) {
106  if (! BMTest(ValN)) Set(ValN, DefVal());
107  return Group[PosToOffset(BitSet, ValN)];
108  }
109  void Del(const int& ValN);
110 };
111 
112 template <class TVal, uint16 GroupSize>
113 int TSparseGroup<TVal, GroupSize>::PosToOffset(const unsigned char *BitSet, int Pos) {
114  static const int bits_in [256] = { // # of bits set in one char
115  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
116  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
117  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
118  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
119  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
120  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
121  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
122  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
123  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
124  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
125  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
126  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
127  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
128  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
129  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
130  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
131  };
132  // [Note: condition pos > 8 is an optimization; convince yourself we
133  // give exactly the same result as if we had pos >= 8 here instead.]
134  int Offset = 0;
135  for ( ; Pos > 8; Pos -= 8 ) // bm[0..pos/8-1]
136  Offset += bits_in[*BitSet++]; // chars we want *all* bits in
137  return Offset + bits_in[*BitSet & ((1 << Pos)-1)]; // the char that includes pos
138 }
139 
140 template <class TVal, uint16 GroupSize>
141 TSparseGroup<TVal, GroupSize>::TSparseGroup(const TSparseGroup& SG) : Buckets(SG.Buckets), Group(NULL) {
142  memcpy(BitSet, SG.BitSet, sizeof(BitSet));
143  if (Buckets > 0) {
144  Group = new TVal [Buckets];
145  for (int b = 0; b < Buckets; b++) { Group[b] = SG.Group[b]; }
146  }
147 }
148 
149 template <class TVal, uint16 GroupSize>
151  SIn.LoadBf(BitSet, sizeof(BitSet));
152  SIn.Load(Buckets);
153  if (Group != NULL) delete [] Group;
154  Group = new TVal [Buckets];
155  for (int b = 0; b < Buckets; b++) { Group[b] = TVal(SIn); }
156 }
157 
158 template <class TVal, uint16 GroupSize>
160  SOut.SaveBf(BitSet, sizeof(BitSet));
161  SOut.Save(Buckets);
162  for (int b = 0; b < Buckets; b++) { Group[b].Save(SOut); }
163 }
164 
165 template <class TVal, uint16 GroupSize>
167  if (this != &SG) {
168  if (SG.Buckets == 0 && Group != NULL) {
169  delete [] Group;
170  Group = 0;
171  } else {
172  if (Buckets != SG.Buckets) {
173  if (Group != NULL) delete [] Group;
174  Group = new TVal [SG.Buckets];
175  }
176  for (int b = 0; b < SG.Buckets; b++) { Group[b] = SG.Group[b]; }
177  }
178  Buckets = SG.Buckets;
179  memcpy(BitSet, SG.BitSet, sizeof(BitSet));
180  }
181  return *this;
182 }
183 
184 template <class TVal, uint16 GroupSize>
186  if (Buckets == SG.Buckets && memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == 0) {
187  for (int b = 0; b < Buckets; b++) {
188  if (Group[b] != SG.Group[b]) return false;
189  }
190  return true;
191  }
192  return false;
193 }
194 
195 template <class TVal, uint16 GroupSize>
197  if (Buckets < SG.Buckets) return true;
198  if (memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == -1) return true;
199  for (int b = 0; b < Buckets; b++) {
200  if (Group[b] < SG.Group[b]) return true;
201  }
202  return false;
203 }
204 
205 template <class TVal, uint16 GroupSize>
207  Assert(Offset < Buckets);
208  for (int i = 0; i < sizeof(BitSet); i++) {
209  for (int b = 0; b < 8; b++) {
210  if (TB1Def::GetBit(b, BitSet[i])) {
211  if (Offset == 0) return i*8 + b;
212  Offset--;
213  }
214  }
215  }
216  Fail;
217  return -1;
218 }
219 
220 template <class TVal, uint16 GroupSize>
221 void TSparseGroup<TVal, GroupSize>::Clr(const bool& DoDel) {
222  if (DoDel && Group != NULL) {
223  delete [] Group;
224  Group = 0;
225  }
226  memset(BitSet, 0, sizeof(BitSet));
227  Buckets = 0;
228 }
229 
230 template <class TVal, uint16 GroupSize>
231 TVal& TSparseGroup<TVal, GroupSize>::Set(const int& ValN, const TVal& Val) {
232  const int Offset = PosToOffset(BitSet, ValN);
233  if (! BMTest(ValN)) {
234  const TVal *OldGroup = Group;
235  Group = new TVal [Buckets+1];
236  for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
237  for (int b = Offset+1; b <= Buckets; b++) Group[b] = OldGroup[b-1];
238  if (OldGroup != NULL) delete [] OldGroup;
239  Buckets++;
240  BMSet(ValN);
241  }
242  Group[Offset] = Val;
243  return Group[Offset];
244 }
245 
246 template <class TVal, uint16 GroupSize>
247 void TSparseGroup<TVal, GroupSize>::Del(const int& ValN) {
248  if (BMTest(ValN)) {
249  const int Offset = PosToOffset(BitSet, ValN);
250  if (--Buckets == 0) {
251  delete [] Group;
252  Group = 0;
253  } else {
254  const TVal *OldGroup = Group;
255  Group = new TVal [Buckets];
256  for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
257  for (int b = Offset+1; b <= Buckets; b++) Group[b-1] = OldGroup[b];
258  if (OldGroup != NULL) delete [] OldGroup;
259  }
260  BMClear(ValN);
261  }
262 }
263 
265 // Sparse Table Iterator
266 template <class TVal, uint16 GroupSize>
268 private:
271  int CurOff; // Offset in the current group
272  TGroupVI BegI, GroupI, EndI;
273 public:
274  TSparseTableI() : CurOff(0), GroupI(NULL), EndI(NULL) { }
275  TSparseTableI(const TGroupVI& BegIter, const TGroupVI& CurIter, const TGroupVI& EndIter,
276  const int& Offset = 0) : CurOff(Offset), BegI(BegIter), GroupI(CurIter), EndI(EndIter) { }
278  CurOff(STI.CurOff), BegI(STI.BegI), GroupI(STI.GroupI), EndI(STI.EndI) { }
279 
281  CurOff=STI.CurOff; BegI=STI.BegI; GroupI=STI.GroupI; EndI=STI.EndI; return *this; }
282  bool operator == (const TSparseTableI& STI) const {
283  return GroupI == STI.GroupI && CurOff == STI.CurOff; }
284  bool operator < (const TSparseTableI& STI) const {
285  return GroupI < STI.GroupI || (GroupI == STI.GroupI && CurOff < STI.CurOff); }
287  if (CurOff+1 == GroupI->Len()) { CurOff = 0;
288  if (GroupI < EndI) { GroupI++;
289  while (GroupI < EndI && GroupI->Empty()) { GroupI++; } }
290  } else { CurOff++; }
291  return *this;
292  }
294  if (CurOff == 0) {
295  while (GroupI >= BegI && GroupI->Empty()) { GroupI--; }
296  if (GroupI >= BegI) CurOff = GroupI->Len()-1;
297  } else { CurOff--; }
298  return *this;
299  }
300  int GetValN() const { return int(GroupI-BegI)*GroupSize + GroupI->OffsetToPos(CurOff); }
301  bool IsEnd() const { return GroupI==EndI; }
302  TVal& operator*() const { return GroupI->Offset(CurOff); }
303  TVal& operator()() const { return GroupI->Offset(CurOff); }
304  TVal* operator->() const { return &(operator*()); }
305 };
306 
308 // Sparse Table
309 template <class TVal, uint16 GroupSize = 48> // == 32*x+16
311 public:
314 private:
317 private:
318  static int GetGroups(const int& Vals) { return Vals == 0 ? 0 : ((Vals-1) / GroupSize) + 1; }
319  int PosInGroup(const int& ValN) const { return ValN % GroupSize; }
320  int GroupNum(const int& ValN) const { return ValN / GroupSize; }
321  const TSGroup& GetGrp1(const int& ValN) const { return GroupV[GroupNum(ValN)]; }
322  TSGroup& GetGrp1(const int& ValN) { return GroupV[GroupNum(ValN)]; }
323 public:
324  TSparseTable(const int& MaxVals = 0) : MxVals(MaxVals),
325  Vals(0), GroupV(GetGroups(MaxVals), GetGroups(MaxVals)) { }
326  TSparseTable(const TSparseTable& ST) : MxVals(ST.MxVals), Vals(ST.Vals), GroupV(ST.GroupV) { }
327  TSparseTable(TSIn& SIn) : MxVals(SIn), Vals(SIn), GroupV(SIn) { }
328  void Load(TSIn& SIn) { MxVals.Load(SIn); Vals.Load(SIn); GroupV.Load(SIn); }
329  void Save(TSOut& SOut) const { MxVals.Save(SOut); Vals.Save(SOut); GroupV.Save(SOut); }
330 
332  bool operator == (const TSparseTable& ST) const;
333  bool operator < (const TSparseTable& ST) const;
334  ::TSize GetMemUsed() const { return 2*sizeof(TInt)+Vals*sizeof(TVal)+GroupV.GetMemUsed(); }
335 
336  TIter BegI() const {
337  if (Len() > 0) { int B = 0;
338  while (B < Groups() && GroupV[B].Empty()) { B++; }
339  return TIter(GroupV.BegI(), GroupV.BegI()+B, GroupV.EndI()); }
340  return TIter(GroupV.BegI(), GroupV.EndI(), GroupV.EndI());
341  }
342  TIter EndI() const { return TIter(GroupV.BegI(), GroupV.EndI(), GroupV.EndI()); }
343  TIter GetI(const int& ValN) const { Assert(! IsEmpty(ValN));
344  typedef typename TVec<TSGroup>::TIter TVIter;
345  const TVIter GI = GroupV.GetI(GroupNum(ValN));
346  return TIter(GroupV.BegI(), GI, GroupV.EndI(), GI->PosToOffset(PosInGroup(ValN)));
347  }
348 
349  int Len() const { return Vals; }
350  int Reserved() const { return MxVals; }
351  int Groups() const { return GroupV.Len(); }
352  bool Empty() const { return Vals == 0; }
353  uint GetDiskSz() const {
354  return sizeof(TInt)*4 + ((GroupSize+16)/8)*Groups() + sizeof(TVal)*Vals; }
355 
356  void Clr(const bool& DoDel = true);
357  void Reserve(const int NewVals) { Resize(NewVals); }
358  void Resize(const int& NewVals);
359  void Swap(TSparseTable& ST);
360 
361  bool IsEmpty(const int& ValN) const { return GroupV[GroupNum(ValN)].IsEmpty(PosInGroup(ValN)); }
362  const TVal& Get(const int& ValN) const { return GroupV[GroupNum(ValN)].Get(PosInGroup(ValN)); }
363  TVal& Set(const int& ValN, const TVal& Val);
364  TVal& Set(const int& ValN);
365  void Del(const int& ValN);
366 
367  TSGroup& GetGroup(const int& GroupN) { return GroupV[GroupN]; }
368  const TSGroup& GetGroup(const int& GroupN) const { return GroupV[GroupN]; }
369 };
370 
371 template <class TVal, uint16 GroupSize>
373  if (this != &ST) {
374  MxVals = ST.MxVals;
375  Vals = ST.Vals;
376  GroupV = ST.GroupV;
377  }
378  return *this;
379 }
380 
381 template <class TVal, uint16 GroupSize>
383  return Vals == ST.Vals && MxVals == ST.MxVals && GroupV == ST.GroupV;
384 }
385 
386 template <class TVal, uint16 GroupSize>
388  return Vals < ST.Vals || (Vals == ST.Vals && GroupV < ST.GroupV);
389 }
390 
391 template <class TVal, uint16 GroupSize>
392 void TSparseTable<TVal, GroupSize>::Clr(const bool& DoDel) {
393  if (! DoDel) {
394  for (int g = 0; g < GroupV.Len(); g++) GroupV[g].Clr(false);
395  } else {
396  MxVals = 0;
397  GroupV.Clr(true);
398  }
399  Vals = 0;
400 }
401 
402 template <class TVal, uint16 GroupSize>
403 void TSparseTable<TVal, GroupSize>::Resize(const int& NewVals) {
404  // only allow to grow
405  if (NewVals > MxVals) {
406  const int Groups = GetGroups(NewVals);
407  GroupV.Reserve(Groups, Groups);
408  MxVals = NewVals;
409  }
410 }
411 
412 template <class TVal, uint16 GroupSize>
414  ::Swap(MxVals, ST.MxVals);
415  ::Swap(Vals, ST.Vals);
416  GroupV.Swap(ST.GroupV);
417 }
418 
419 template <class TVal, uint16 GroupSize>
420 TVal& TSparseTable<TVal, GroupSize>::Set(const int& ValN, const TVal& Val) {
421  Assert(ValN < MxVals);
422  TSGroup& Group = GetGrp1(ValN);
423  const int OldVals = Group.Len();
424  TVal& ValRef = Group.Set(PosInGroup(ValN), Val);
425  Vals += Group.Len() - OldVals;
426  return ValRef;
427 }
428 
429 template <class TVal, uint16 GroupSize>
430 TVal& TSparseTable<TVal, GroupSize>::Set(const int& ValN) {
431  Assert(ValN < MxVals);
432  TSGroup& Group = GetGrp1(ValN);
433  const int OldVals = Group.Len();
434  TVal& ValRef = Group.Set(PosInGroup(ValN));
435  Vals += Group.Len() - OldVals;
436  return ValRef;
437 }
438 
439 template <class TVal, uint16 GroupSize>
440 void TSparseTable<TVal, GroupSize>::Del(const int& ValN) {
441  Assert(ValN < MxVals);
442  TSGroup& Group = GetGrp1(ValN);
443  const int OldVals = Group.Len();
444  Group.Del(PosInGroup(ValN));
445  Vals += Group.Len() - OldVals;
446 }
447 
449 // Sparse Hash Key Dat
450 #pragma pack(push, 1) // pack class size
451 template <class TKey, class TDat>
453 public:
454  TKey Key;
455  TDat Dat;
456 public:
457  TSHashKeyDat() : Key(), Dat() { }
458  TSHashKeyDat(const TKey& _Key) : Key(_Key), Dat() { }
459  TSHashKeyDat(const TKey& _Key, const TDat& _Dat) : Key(_Key), Dat(_Dat) { }
460  TSHashKeyDat(const TSHashKeyDat& HashKeyDat) : Key(HashKeyDat.Key), Dat(HashKeyDat.Dat) { }
461  explicit TSHashKeyDat(TSIn& SIn) : Key(SIn), Dat(SIn) { }
462  void Save(TSOut& SOut) const { Key.Save(SOut); Dat.Save(SOut); }
463  TSHashKeyDat& operator = (const TSHashKeyDat& HashKeyDat) { if (this != &HashKeyDat) {
464  Key = HashKeyDat.Key; Dat = HashKeyDat.Dat; } return *this; }
465  bool operator == (const TSHashKeyDat& HashKeyDat) const { return Key == HashKeyDat.Key; }
466  bool operator < (const TSHashKeyDat& HashKeyDat) const { return Key < HashKeyDat.Key; }
467  int Hash() const { return Key.GetPrimHashCd(); }
468 };
469 #pragma pack(pop)
470 
472 // Sparse Hash Table
473 template <class TKey, class TDat, uint16 GroupSize=48> // GroupSize= 32*x+16, for some x
474 class TSparseHash {
475 public:
479 public:
480  static const float MxOccupancy; // = 0.7; //was 0.8
481  static const float MnOccupancy; // = 0.4 * MxOccupancy;
482  static const int MinBuckets; // = 32 (must be power of 2)
483 private:
484  void ResetThresh();
485  int GetMinSize(const int& CurVals, const int& WantedVals) const;
486  void CopyFrom(const TSparseHash& HT, const int& MnWanted);
487  void MoveFrom(TSparseHash& HT, const int& MnWanted);
488  void ResizeDelta(const int& ValsToAdd, const int& MnWanted = 0);
489  void FindPos(const TKey& Key, int& Pos, int& PosToIns) const;
490 private:
493 public:
494  TSparseHash(const int& WantedVals = 0) : Table(GetMinSize(0, WantedVals)) { ResetThresh(); }
495  TSparseHash(TSIn& SIn) : ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }
496  void Load(TSIn& SIn) { ShrinkThresh.Load(SIn); ExpandThresh.Load(SIn); Table.Load(SIn); }
497  void Save(TSOut& SOut) const { ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }
498 
499  TSparseHash& operator = (const TSparseHash& SHT);
500  bool operator == (const TSparseHash& SHT) const;
501  bool operator < (const TSparseHash& SHT) const;
502  ::TSize GetMemUsed() const { return 2*sizeof(TInt)+Table.GetMemUsed(); }
503 
504  TIter BegI() const { return Table.BegI(); }
505  TIter EndI() const { return Table.EndI(); }
506  TIter GetI(const TKey& Key) const { Assert(IsKey(Key)); return Table.GetI(GetKeyId(Key)); }
507 
508  bool Empty() const { return Len() == 0; }
509  int Len() const { return Table.Len(); }
510  int Reserved() const { return Table.Reserved(); }
511  uint GetDiskSz() const { return 2*sizeof(TInt) + Table.GetDiskSz(); }
512 
513  void Reserve(const int& MxVals) { if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }
514  void Clr(const bool& DoDel = true) { Table.Clr(DoDel); ResetThresh(); }
515  void Swap(TSparseHash& HT);
516 
517  int AddKey(const TKey& Key);
518  TDat& AddDat(const TKey& Key);
519  TDat& AddDat(const TKey& Key, const TDat& Dat);
520 
521  const TKey& GetKey(const int& KeyId) const { return Table.Get(KeyId).Key; }
522  int GetKeyId(const TKey& Key) const {
523  int Pos, PosToIns; FindPos(Key, Pos, PosToIns); return Pos; }
524  bool IsKey(const TKey& Key) const { return GetKeyId(Key) != -1; }
525  bool IsKey(const TKey& Key, int& KeyId) const {
526  KeyId = GetKeyId(Key); return KeyId != -1; }
527  bool IsKeyId(const int& KeyId) const { return ! Table.IsEmpty(KeyId); }
528  int GetRndKeyId(TRnd& Rnd = TInt::Rnd) const { Assert(Len()>0);
529  int KeyId = Rnd.GetUniDevInt(Reserved());
530  while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }
531 
532  const TDat& GetDat(const TKey& Key) const;
533  TDat& GetDat(const TKey& Key);
534  const TDat& GetDatKeyId(const int& KeyId) const { return Table.Get(KeyId).Dat; }
535  TDat& GetDatKeyId(const int& KeyId) { return Table.Set(KeyId).Dat; }
536  void GetKeyDat(const int& KeyId, TKey& Key, TDat& Dat) const;
537  bool IsKeyGetDat(const TKey& Key, TDat& Dat) const;
538 
539  void GetKeyV(TVec<TKey>& KeyV) const;
540  void GetDatV(TVec<TDat>& DatV) const;
541  void GetKeyDatPrV(TVec<TPair<TKey, TDat> >& KeyDatPrV) const;
542  void GetDatKeyPrV(TVec<TPair<TDat, TKey> >& DatKeyPrV) const;
543 };
544 
545 template <class TKey, class TDat, uint16 GroupSize>
546 const float TSparseHash<TKey, TDat, GroupSize>::MxOccupancy = 0.8f; //0.8f;
547 
548 template <class TKey, class TDat, uint16 GroupSize>
549 const float TSparseHash<TKey, TDat, GroupSize>::MnOccupancy = 0.4f * 0.8f; //0.8f
550 
551 template <class TKey, class TDat, uint16 GroupSize>
553 
554 template <class TKey, class TDat, uint16 GroupSize>
556  ExpandThresh = int(Table.Reserved() * MxOccupancy);
557  ShrinkThresh = int(Table.Reserved() * MnOccupancy);
558 }
559 
560 template <class TKey, class TDat, uint16 GroupSize>
561 int TSparseHash<TKey, TDat, GroupSize>::GetMinSize(const int& CurVals, const int& WantedVals) const {
562  int Size = MinBuckets;
563  while (Size*MxOccupancy < WantedVals || CurVals >= Size * MxOccupancy) Size *= 2;
564  return Size;
565 }
566 
567 template <class TKey, class TDat, uint16 GroupSize>
568 void TSparseHash<TKey, TDat, GroupSize>::CopyFrom(const TSparseHash& HT, const int& MnWanted) {
569  Clr(false);
570  const int NewSize = GetMinSize(HT.Reserved(), MnWanted);
571  if (NewSize > Reserved()) {
572  Table.Resize(NewSize);
573  ResetThresh();
574  }
575  const uint BuckM1 = Reserved() - 1;
576  for (int g = 0; g < HT.Table.Groups(); g++) {
577  const TSGroup& Group = HT.Table.GetGroup(g);
578  for (int b = 0; b < Group.Len(); b++) {
579  int Tries = 0; uint BuckNum;
580  for (BuckNum = Group.Offset(b).Hash() & BuckM1;
581  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
582  Tries++;
583  Assert(Tries < Reserved());
584  }
585  Table.Set(BuckNum, Group.Offset(b));
586  }
587  }
588 }
589 
590 template <class TKey, class TDat, uint16 GroupSize>
592  Clr(false);
593  int NewSize;
594  if (MnWanted == 0) NewSize = HT.Reserved();
595  else NewSize = GetMinSize(HT.Reserved(), MnWanted);
596  if (NewSize > Reserved()) {
597  Table.Resize(NewSize);
598  ResetThresh();
599  }
600  const uint BuckM1 = Reserved() - 1;
601  for (int g = 0; g < HT.Table.Groups(); g++) {
602  TSGroup& Group = HT.Table.GetGroup(g);
603  for (int b = 0; b < Group.Len(); b++) {
604  int Tries = 0; uint BuckNum;
605  for (BuckNum = Group.Offset(b).Hash() & BuckM1;
606  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
607  Tries++;
608  Assert(Tries < Reserved());
609  }
610  Assert(Table.IsEmpty(BuckNum));
611  Table.Set(BuckNum, Group.Offset(b));
612  }
613  Group.Clr(true); // delete
614  }
615 }
616 
617 template <class TKey, class TDat, uint16 GroupSize>
618 void TSparseHash<TKey, TDat, GroupSize>::ResizeDelta(const int& ValsToAdd, const int& MnWanted) {
619  if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
620  const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
621  if (NewSize > Reserved()) {
622  printf("***Resize SparseHash:%d->%d\n", Reserved(), NewSize);
623  TSparseHash TmpHt(ValsToAdd+Len());
624  TmpHt.ResetThresh();
625  TmpHt.MoveFrom(*this, Len());
626  Swap(TmpHt);
627  }
628 }
629 
630 template <class TKey, class TDat, uint16 GroupSize>
631 void TSparseHash<TKey, TDat, GroupSize>::FindPos(const TKey& Key, int& Pos, int& PosToIns) const {
632  const uint BuckM1 = Reserved() - 1;
633  uint BuckNum = Key.GetPrimHashCd() & BuckM1;
634  int Tries = 0;
635  while (true) {
636  if (Table.IsEmpty(BuckNum)) {
637  Pos = -1; PosToIns = BuckNum; return;
638  }
639  else if (Key == Table.Get(BuckNum).Key) {
640  Pos = BuckNum; PosToIns = -1; return;
641  }
642  Tries++;
643  BuckNum = (BuckNum + Tries) & BuckM1;
644  Assert(Tries < Reserved());
645  }
646 }
647 
648 template <class TKey, class TDat, uint16 GroupSize>
650  if (this != &SHT) {
651  ShrinkThresh = SHT.ShrinkThresh;
652  ExpandThresh = SHT.ExpandThresh;
653  Table = SHT.Table;
654  }
655  return *this;
656 }
657 
658 template <class TKey, class TDat, uint16 GroupSize>
660  return Table == SHT.Table;
661 }
662 
663 template <class TKey, class TDat, uint16 GroupSize>
665  return Table < SHT.Table;
666 }
667 
668 template <class TKey, class TDat, uint16 GroupSize>
670  ::Swap(ShrinkThresh, HT.ShrinkThresh);
671  ::Swap(ExpandThresh, HT.ExpandThresh);
672  Table.Swap(HT.Table);
673 }
674 
675 template <class TKey, class TDat, uint16 GroupSize>
677  ResizeDelta(1);
678  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
679  if (Pos != -1) { return Pos; } // key exists
680  else {
681  Table.Set(PosToIns, THashKeyDat(Key));
682  return PosToIns;
683  }
684 }
685 
686 template <class TKey, class TDat, uint16 GroupSize>
688  ResizeDelta(1);
689  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
690  if (PosToIns != -1) {
691  return Table.Set(PosToIns, THashKeyDat(Key)).Dat;
692  } else { return Table.Set(Pos).Dat; }
693 }
694 
695 template <class TKey, class TDat, uint16 GroupSize>
696 TDat& TSparseHash<TKey, TDat, GroupSize>::AddDat(const TKey& Key, const TDat& Dat) {
697  ResizeDelta(1);
698  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
699  if (PosToIns != -1) {
700  return Table.Set(PosToIns, THashKeyDat(Key, Dat)).Dat;
701  } else { return Table.Set(Pos).Dat = Dat; }
702 }
703 
704 template <class TKey, class TDat, uint16 GroupSize>
705 const TDat& TSparseHash<TKey, TDat, GroupSize>::GetDat(const TKey& Key) const {
706  int Pos, PosToIns;
707  FindPos(Key, Pos, PosToIns);
708  Assert(Pos != -1);
709  return Table.Get(Pos).Dat;
710 }
711 
712 template <class TKey, class TDat, uint16 GroupSize>
714  int Pos, PosToIns;
715  FindPos(Key, Pos, PosToIns);
716  Assert(Pos != -1);
717  return Table.Set(Pos).Dat;
718 }
719 
720 template <class TKey, class TDat, uint16 GroupSize>
721 void TSparseHash<TKey, TDat, GroupSize>::GetKeyDat(const int& KeyId, TKey& Key, TDat& Dat) const {
722  Assert(IsKey(KeyId));
723  const THashKeyDat& KeyDat = Table.Get(KeyId);
724  Key = KeyDat.Key;
725  Dat = KeyDat.Dat;
726 }
727 
728 template <class TKey, class TDat, uint16 GroupSize>
729 bool TSparseHash<TKey, TDat, GroupSize>::IsKeyGetDat(const TKey& Key, TDat& Dat) const {
730  int KeyId;
731  if (IsKey(Key, KeyId)) {
732  Dat=Table.Get(KeyId).Dat;
733  return true;
734  } else { return false; }
735 }
736 
737 template <class TKey, class TDat, uint16 GroupSize>
739  KeyV.Gen(Len(), 0);
740  for (TIter i = BegI(); i < EndI(); i++) {
741  KeyV.Add(i->Key);
742  }
743 }
744 
745 template <class TKey, class TDat, uint16 GroupSize>
747  DatV.Gen(Len(), 0);
748  for (TIter i = BegI(); i < EndI(); i++) {
749  DatV.Add(i->Dat);
750  }
751 }
752 
753 template <class TKey, class TDat, uint16 GroupSize>
755  KeyDatPrV.Gen(Len(), 0);
756  for (TIter i = BegI(); i < EndI(); i++) {
757  KeyDatPrV.Add(TPair<TKey, TDat>(i->Key, i->Dat));
758  }
759 }
760 
761 template <class TKey, class TDat, uint16 GroupSize>
763  DatKeyPrV.Gen(Len(), 0);
764  for (TIter i = BegI(); i < EndI(); i++) {
765  DatKeyPrV.Add(TPair<TDat, TKey>(i->Dat, i->Key));
766  }
767 }
768 
770 // Sparse Set
771 template <class TKey, uint16 GroupSize=48> // GroupSize= 32*x+16, for some x
772 class TSparseSet {
773 public:
776 public:
777  static const float MxOccupancy; // = 0.7; //was 0.8
778  static const float MnOccupancy; // = 0.4 * MxOccupancy;
779  static const int MinBuckets; // = 32 (must be power of 2)
780 private:
781  void ResetThresh();
782  int GetMinSize(const int& CurVals, const int& WantedVals) const;
783  void CopyFrom(const TSparseSet& SSet, const int& MnWanted);
784  void MoveFrom(TSparseSet& SSet, const int& MnWanted);
785  void ResizeDelta(const int& ValsToAdd, const int& MnWanted = 0);
786  void FindPos(const TKey& Key, int& Pos, int& PosToIns) const;
787 private:
790 public:
791  TSparseSet(const int& WantedVals = 0) : Table(GetMinSize(0, WantedVals)) { ResetThresh(); }
792  TSparseSet(TSIn& SIn) : ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }
793  void Load(TSIn& SIn) { ShrinkThresh.Load(SIn); ExpandThresh.Load(SIn); Table.Load(SIn); }
794  void Save(TSOut& SOut) const { ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }
795 
796  TSparseSet& operator = (const TSparseSet& SSet);
797  bool operator == (const TSparseSet& SSet) const;
798  bool operator < (const TSparseSet& SSet) const;
799  ::TSize GetMemUsed() const { return 2*sizeof(TInt)+Table.GetMemUsed(); }
800 
801  TIter BegI() const { return Table.BegI(); }
802  TIter EndI() const { return Table.EndI(); }
803  TIter GetI(const int& KeyId) const { Assert(IsKeyId(KeyId)); return Table.GetI(KeyId); }
804 
805  bool Empty() const { return Len() == 0; }
806  int Len() const { return Table.Len(); }
807  int Reserved() const { return Table.Reserved(); }
808  uint GetDiskSz() const { return 2*sizeof(TInt) + Table.GetDiskSz(); }
809 
810  void Reserve(const int& MxVals) { if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }
811  void Clr(const bool& DoDel = true) { Table.Clr(DoDel); ResetThresh(); }
812  void Swap(TSparseSet& SSet);
813 
814  int AddKey(const TKey& Key);
815  const TKey& GetKey(const int& KeyId) const { return Table.Get(KeyId); }
816  int GetKeyId(const TKey& Key) const { int Pos, PosToIns;
817  FindPos(Key, Pos, PosToIns); return Pos; }
818  bool IsKey(const TKey& Key) const { return GetKeyId(Key) != -1; }
819  bool IsKey(const TKey& Key, int& KeyId) const {
820  KeyId = GetKeyId(Key); return KeyId != -1; }
821  bool IsKeyId(const int& KeyId) const { return ! Table.IsEmpty(KeyId); }
822  int GetRndKeyId(TRnd& Rnd = TInt::Rnd) const { Assert(Len()>0);
823  int KeyId = Rnd.GetUniDevInt(Reserved());
824  while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }
825 
826  void GetKeyV(TVec<TKey>& KeyV) const;
827 };
828 
829 template <class TKey, uint16 GroupSize>
831 
832 template <class TKey, uint16 GroupSize>
833 const float TSparseSet<TKey, GroupSize>::MnOccupancy = 0.4f * 0.8f;
834 
835 template <class TKey, uint16 GroupSize>
837 
838 template <class TKey, uint16 GroupSize>
840  ExpandThresh = int(Table.Reserved() * MxOccupancy);
841  ShrinkThresh = int(Table.Reserved() * MnOccupancy);
842 }
843 
844 template <class TKey, uint16 GroupSize>
845 int TSparseSet<TKey, GroupSize>::GetMinSize(const int& CurVals, const int& WantedVals) const {
846  int Size = MinBuckets;
847  while (Size*MxOccupancy <= WantedVals || CurVals > Size * MxOccupancy) Size *= 2;
848  return Size;
849 }
850 
851 template <class TKey, uint16 GroupSize>
852 void TSparseSet<TKey, GroupSize>::CopyFrom(const TSparseSet& SSet, const int& MnWanted) {
853  Clr(false);
854  const int NewSize = GetMinSize(SSet.Reserved(), MnWanted);
855  if (NewSize > Reserved()) {
856  Table.Resize(NewSize);
857  ResetThresh();
858  }
859  const uint BuckM1 = Reserved() - 1;
860  for (int g = 0; g < SSet.Table.Groups(); g++) {
861  const TSGroup& Group = SSet.Table.GetGroup(g);
862  for (int b = 0; b < Group.Len(); b++) {
863  int Tries = 0; uint BuckNum;
864  for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
865  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
866  Tries++;
867  Assert(Tries < Reserved());
868  }
869  Table.Set(BuckNum, Group.Offset(b));
870  }
871  }
872 }
873 
874 template <class TKey, uint16 GroupSize>
875 void TSparseSet<TKey, GroupSize>::MoveFrom(TSparseSet& SSet, const int& MnWanted) {
876  Clr(false);
877  int NewSize;
878  if (MnWanted == 0) NewSize = SSet.Reserved();
879  else NewSize = GetMinSize(SSet.Reserved(), MnWanted);
880  if (NewSize > Reserved()) {
881  Table.Resize(NewSize);
882  ResetThresh();
883  }
884  const uint BuckM1 = Reserved() - 1;
885  for (int g = 0; g < SSet.Table.Groups(); g++) {
886  TSGroup& Group = SSet.Table.GetGroup(g);
887  for (int b = 0; b < Group.Len(); b++) {
888  int Tries = 0; uint BuckNum;
889  for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
890  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
891  Tries++;
892  Assert(Tries < Reserved());
893  }
894  Assert(Table.IsEmpty(BuckNum));
895  Table.Set(BuckNum, Group.Offset(b));
896  }
897  Group.Clr(true); // delete
898  }
899 }
900 
901 template <class TKey, uint16 GroupSize>
902 void TSparseSet<TKey, GroupSize>::ResizeDelta(const int& ValsToAdd, const int& MnWanted) {
903  if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
904  const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
905  if (NewSize > Reserved()) {
906  printf("***Resize SparseSet: %d->%d\n", Reserved(), NewSize);
907  TSparseSet TmpSSet(Len()+ValsToAdd);
908  TmpSSet.ResetThresh();
909  TmpSSet.MoveFrom(*this, Len());
910  Swap(TmpSSet);
911  }
912 }
913 
914 template <class TKey, uint16 GroupSize>
915 void TSparseSet<TKey, GroupSize>::FindPos(const TKey& Key, int& Pos, int& PosToIns) const {
916  const uint BuckM1 = Reserved() - 1;
917  uint BuckNum = Key.GetPrimHashCd() & BuckM1;
918  int Tries = 0;
919  while (true) {
920  if (Table.IsEmpty(BuckNum)) {
921  Pos = -1; PosToIns = BuckNum; return;
922  }
923  else if (Key == Table.Get(BuckNum)) {
924  Pos = BuckNum; PosToIns = -1; return;
925  }
926  Tries++;
927  BuckNum = (BuckNum + Tries) & BuckM1;
928  Assert(Tries < Reserved());
929  }
930 }
931 
932 template <class TKey, uint16 GroupSize>
934  if (this != &SSet) {
935  ShrinkThresh = SSet.ShrinkThresh;
936  ExpandThresh = SSet.ExpandThresh;
937  Table = SSet.Table;
938  }
939  return *this;
940 }
941 
942 template <class TKey, uint16 GroupSize>
944  return Table == SSet.Table;
945 }
946 
947 template <class TKey, uint16 GroupSize>
949  return Table < SSet.Table;
950 }
951 
952 template <class TKey, uint16 GroupSize>
954  ::Swap(ShrinkThresh, SSet.ShrinkThresh);
955  ::Swap(ExpandThresh, SSet.ExpandThresh);
956  Table.Swap(SSet.Table);
957 }
958 
959 template <class TKey, uint16 GroupSize>
961  ResizeDelta(1);
962  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
963  if (Pos != -1) { return Pos; } // key exists
964  else {
965  Table.Set(PosToIns, Key);
966  return PosToIns;
967  }
968 }
969 
970 template <class TKey, uint16 GroupSize>
972  KeyV.Gen(Len(), 0);
973  for (TIter I = BegI(); I < EndI(); I++) {
974  KeyV.Add(I()); }
975 }
976 
978 // Set-Hash-Key
979 #pragma pack(push, 1) // pack class size
980 template <class TKey>
982 public:
985  TKey Key;
986 public:
988  Next(-1), HashCd(-1), Key() {}
989  THashSetKey(const int& _Next, const int& _HashCd, const TKey& _Key):
990  Next(_Next), HashCd(_HashCd), Key(_Key) {}
991  explicit THashSetKey(TSIn& SIn):
992  Next(SIn), HashCd(SIn), Key(SIn) {}
993  void Save(TSOut& SOut) const {
994  Next.Save(SOut); HashCd.Save(SOut); Key.Save(SOut); }
995  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="") {
996  XLoadHd(Nm); XLoad(Key); }
997  void SaveXml(TSOut& SOut, const TStr& Nm) const {
998  XSaveHd(Nm); XSave(Key); }
999 
1001  if (this!=&SetKey) { Next=SetKey.Next; HashCd=SetKey.HashCd; Key=SetKey.Key; }
1002  return *this; }
1003 };
1004 #pragma pack(pop)
1005 
1007 // Set-Hash-Key-Iterator
1008 template <class TKey>
1010 public:
1012 private:
1013  TSetKey* KeyI;
1014  TSetKey* EndI;
1015 public:
1016  THashSetKeyI(): KeyI(NULL), EndI(NULL) { }
1017  THashSetKeyI(const THashSetKeyI& _SetKeyI):
1018  KeyI(_SetKeyI.KeyI), EndI(_SetKeyI.EndI) { }
1019  THashSetKeyI(const TSetKey* _KeyI, const TSetKey* _EndI):
1020  KeyI((TSetKey*)_KeyI), EndI((TSetKey*)_EndI) { }
1021 
1023  KeyI=SetKeyI.KeyI; EndI=SetKeyI.EndI; return *this; }
1024  bool operator==(const THashSetKeyI& SetKeyI) const {
1025  return KeyI==SetKeyI.KeyI; }
1026  bool operator<(const THashSetKeyI& SetKeyI) const {
1027  return KeyI<SetKeyI.KeyI; }
1028  THashSetKeyI& operator++(int) { KeyI++; while (KeyI < EndI && KeyI->HashCd==-1) { KeyI++; } return *this; }
1029  THashSetKeyI& operator--(int) { do { KeyI--; } while (KeyI->HashCd==-1); return *this; }
1030 
1031  const TKey& operator*() const { return KeyI->Key; }
1032  const TKey& operator()() const { return KeyI->Key; }
1033  const TKey* operator->() const { return &KeyI->Key; }
1034  THashSetKeyI& Next() { operator++(1); return *this; }
1035 
1037  bool IsEmpty() const { return KeyI == NULL; }
1039  bool IsEnd() const { return EndI == KeyI; }
1040 
1041  const TKey& GetKey() const {Assert((KeyI!=NULL)&&(KeyI->HashCd!=-1)); return KeyI->Key; }
1042 };
1043 
1045 // Set-Table
1046 template <class TKey, class THashFunc = TDefaultHashFunc<TKey> >
1047 class THashSet{
1048 public:
1050 private:
1056 private:
1057  TSetKey& GetSetKey(const int& KeyId) {
1058  TSetKey& SetKey=KeyV[KeyId];
1059  Assert(SetKey.HashCd!=-1); return SetKey; }
1060  const TSetKey& GetSetKey(const int& KeyId) const {
1061  const TSetKey& SetKey=KeyV[KeyId];
1062  Assert(SetKey.HashCd!=-1); return SetKey; }
1063  uint GetNextPrime(const uint& Val) const;
1064  void Resize();
1065 public:
1067  PortV(), KeyV(),
1068  AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0) { }
1069  THashSet(const THashSet& Set):
1070  PortV(Set.PortV), KeyV(Set.KeyV), AutoSizeP(Set.AutoSizeP),
1071  FFreeKeyId(Set.FFreeKeyId), FreeKeys(Set.FreeKeys) { }
1072  THashSet(const int& ExpectVals, const bool& _AutoSizeP=false);
1073  explicit THashSet(const TVec<TKey>& KeyV);
1074  explicit THashSet(TSIn& SIn):
1075  PortV(SIn), KeyV(SIn),
1076  AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn) {
1077  SIn.LoadCs(); }
1078  void Load(TSIn& SIn) {
1079  PortV.Load(SIn); KeyV.Load(SIn);
1080  AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
1081  SIn.LoadCs(); }
1082  void Save(TSOut& SOut) const {
1083  PortV.Save(SOut); KeyV.Save(SOut);
1084  AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
1085  SOut.SaveCs(); }
1086  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="") {
1087  XLoadHd(Nm); TVec<TSetKey> KeyV; XLoad(KeyV); XLoad(AutoSizeP);
1088  for (int KeyN=0; KeyN<KeyV.Len(); KeyN++) {
1089  AddKey(KeyV[KeyN].Key); }}
1090  void SaveXml(TSOut& SOut, const TStr& Nm) {
1091  Defrag(); XSaveHd(Nm); XSave(KeyV); XSave(AutoSizeP); }
1092 
1093  THashSet& operator=(const THashSet& Set) {
1094  if (this!=&Set) {
1095  PortV=Set.PortV; KeyV=Set.KeyV; AutoSizeP=Set.AutoSizeP;
1096  FFreeKeyId=Set.FFreeKeyId; FreeKeys=Set.FreeKeys; }
1097  return *this; }
1098  bool operator==(const THashSet& Set) const;
1099  const TKey& operator[](const int& KeyId) const {return GetSetKey(KeyId).Key; }
1100  TKey& operator[](const int& KeyId) {return GetSetKey(KeyId).Key; }
1101  //bool operator()(const TKey& Key) {return IsKey(Key); }
1103  return PortV.GetMemUsed() + KeyV.GetMemUsed() + sizeof(bool) + 2*sizeof(int); }
1104 
1105  TIter BegI() const {
1106  if (Len()>0) {
1107  if (IsKeyIdEqKeyN()) { return TIter(KeyV.BegI(), KeyV.EndI()); }
1108  int FKeyId=-1; FNextKeyId(FKeyId);
1109  return TIter(KeyV.BegI()+FKeyId, KeyV.EndI()); }
1110  return TIter(KeyV.EndI(), KeyV.EndI());
1111  }
1112  TIter EndI() const {return TIter(KeyV.EndI(), KeyV.EndI()); }
1113  TIter GetI(const TKey& Key) const {return TIter(&KeyV[GetKeyId(Key)], KeyV.EndI()); }
1114 
1115  void Gen(const int& ExpectVals) {
1116  PortV.Gen(GetNextPrime(ExpectVals/2)); KeyV.Gen(ExpectVals, 0);
1117  FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1)); }
1118 
1119  void Clr(const bool& DoDel=true, const int& NoDelLim=-1);
1120  bool Empty() const {return Len()==0; }
1121  int Len() const {return KeyV.Len()-FreeKeys; }
1122  int GetPorts() const {return PortV.Len(); }
1123  bool IsAutoSize() const {return AutoSizeP; }
1124  int GetMxKeyIds() const {return KeyV.Len(); }
1125  int GetReservedKeyIds() const { return KeyV.Reserved(); }
1126  bool IsKeyIdEqKeyN() const {return FreeKeys==0; }
1127 
1128  int AddKey(const TKey& Key);
1129  void AddKeyV(const TVec<TKey>& KeyV);
1130 
1131  void DelKey(const TKey& Key);
1132  bool DelIfKey(const TKey& Key) {
1133  int KeyId; if (IsKey(Key, KeyId)) {DelKeyId(KeyId); return true;} return false;}
1134  void DelKeyId(const int& KeyId) {DelKey(GetKey(KeyId)); }
1135  void DelKeyIdV(const TIntV& KeyIdV) {
1136  for (int KeyIdN=0; KeyIdN<KeyIdV.Len(); KeyIdN++) {DelKeyId(KeyIdV[KeyIdN]); }}
1137 
1138  void MarkDelKey(const TKey& Key);
1139  void MarkDelKeyId(const int& KeyId) {MarkDelKey(GetKey(KeyId)); }
1140 
1141  const TKey& GetKey(const int& KeyId) const {
1142  return GetSetKey(KeyId).Key; }
1143  int GetKeyId(const TKey& Key) const;
1144  int GetRndKeyId(TRnd& Rnd) const {
1146  IAssert(Len()>0);
1147  return Rnd.GetUniDevInt(Len()); }
1148  bool IsKey(const TKey& Key) const {return GetKeyId(Key)!=-1; }
1149  bool IsKey(const TKey& Key, int& KeyId) const {
1150  KeyId=GetKeyId(Key); return KeyId!=-1; }
1151  bool IsKeyId(const int& KeyId) const {
1152  return (0<=KeyId)&&(KeyId<KeyV.Len())&&(KeyV[KeyId].HashCd!=-1); }
1153 
1154  int FFirstKeyId() const {return 0-1; }
1155  bool FNextKeyId(int& KeyId) const;
1156  void GetKeyV(TVec<TKey>& KeyV) const;
1157  void Swap(THashSet& Set);
1158 
1159  void Defrag();
1160  void Pack() {KeyV.Pack(); }
1161 
1162  static THashSet<TKey> GetSet(const TKey& Key1){
1163  THashSet<TKey> Set(1); Set.AddKey(Key1); return Set;}
1164  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2){
1165  THashSet<TKey> Set(2); Set.AddKey(Key1); Set.AddKey(Key2); return Set;}
1166  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3){
1167  THashSet<TKey> Set(3); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); return Set;}
1168  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4){
1169  THashSet<TKey> Set(4); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); return Set;}
1170  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4, const TKey& Key5){
1171  THashSet<TKey> Set(5); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); return Set;}
1172  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4, const TKey& Key5, const TKey& Key6){
1173  THashSet<TKey> Set(6); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); return Set;}
1174  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4, const TKey& Key5, const TKey& Key6, const TKey& Key7){
1175  THashSet<TKey> Set(7); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); Set.AddKey(Key7); return Set;}
1176  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4, const TKey& Key5, const TKey& Key6, const TKey& Key7, const TKey& Key8){
1177  THashSet<TKey> Set(8); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); Set.AddKey(Key7); Set.AddKey(Key8); return Set;}
1178  static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4, const TKey& Key5, const TKey& Key6, const TKey& Key7, const TKey& Key8, const TKey& Key9){
1179  THashSet<TKey> Set(9); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); Set.AddKey(Key7); Set.AddKey(Key8); Set.AddKey(Key9); return Set;}
1180 
1181 };
1182 
1183 template <class TKey, class THashFunc>
1186  int h, len = (int)TIntH::HashPrimes;
1187  while (len > 0) {
1188  h = len >> 1; m = f + h;
1189  if (*m < Val) { f = m; f++; len = len - h - 1; }
1190  else len = h;
1191  }
1192  return f == l ? *(l - 1) : *f;
1193 }
1194 
1195 template <class TKey, class THashFunc>
1197  // resize & initialize port vector
1198  if (PortV.Len()==0) {PortV.Gen(17); }
1199  else if (AutoSizeP&&(KeyV.Len()>2*PortV.Len())) {
1200  PortV.Gen(GetNextPrime(PortV.Len()+1));
1201  } else {
1202  return;
1203  }
1204  PortV.PutAll(TInt(-1));
1205  // reSet keys
1206  for (int KeyId=0; KeyId<KeyV.Len(); KeyId++) {
1207  TSetKey& SetKey=KeyV[KeyId];
1208  if (SetKey.HashCd!=-1) {
1209  int PortN=abs(THashFunc::GetPrimHashCd(SetKey.Key)%PortV.Len());
1210  SetKey.Next=PortV[PortN];
1211  PortV[PortN]=KeyId;
1212  }
1213  }
1214 }
1215 
1216 template <class TKey, class THashFunc>
1217 THashSet<TKey, THashFunc>::THashSet(const int& ExpectVals, const bool& _AutoSizeP):
1218  PortV(GetNextPrime(ExpectVals/2+1)), KeyV(ExpectVals, 0),
1219  AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0) {
1220  PortV.PutAll(TInt(-1));
1221 }
1222 
1223 template <class TKey, class THashFunc>
1225  PortV(GetNextPrime(_KeyV.Len()/2+1)), KeyV(_KeyV.Len(), 0),
1226  AutoSizeP(false), FFreeKeyId(-1), FreeKeys(0) {
1227  PortV.PutAll(TInt(-1));
1228  for (int i = 0; i < _KeyV.Len(); i++) {
1229  AddKey(_KeyV[i]);
1230  }
1231 }
1232 
1233 template <class TKey, class THashFunc>
1235  if (Len() != Set.Len()) { return false; }
1236  for (int k = FFirstKeyId(); FNextKeyId(k); k++) {
1237  if (! Set.IsKey(GetKey(k))) { return false; }
1238  }
1239  return true;
1240 }
1241 
1242 template <class TKey, class THashFunc>
1243 void THashSet<TKey, THashFunc>::Clr(const bool& DoDel, const int& NoDelLim) {
1244  if (DoDel) {
1245  PortV.Clr(); KeyV.Clr();
1246  } else {
1247  PortV.PutAll(TInt(-1));
1248  KeyV.Clr(DoDel, NoDelLim);
1249  }
1250  FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
1251 }
1252 
1253 template <class TKey, class THashFunc>
1255  if ((KeyV.Len()>2*PortV.Len())||PortV.Empty()) {Resize(); }
1256  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1257  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1258  int PrevKeyId=-1;
1259  int KeyId=PortV[PortN];
1260 
1261  while ((KeyId!=-1) &&
1262  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1263  PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
1264 
1265  if (KeyId==-1) {
1266  if (FFreeKeyId==-1) {
1267  KeyId=KeyV.Add(TSetKey(-1, HashCd, Key));
1268  } else {
1269  KeyId=FFreeKeyId; FFreeKeyId=KeyV[FFreeKeyId].Next; FreeKeys--;
1270  KeyV[KeyId].Next = -1;
1271  KeyV[KeyId].HashCd = HashCd;
1272  KeyV[KeyId].Key = Key;
1273  }
1274  if (PrevKeyId==-1) {
1275  PortV[PortN]=KeyId;
1276  } else {
1277  KeyV[PrevKeyId].Next=KeyId;
1278  }
1279  }
1280  return KeyId;
1281 }
1282 
1283 template <class TKey, class THashFunc>
1285  for (int i = 0; i < KeyV.Len(); i++) { AddKey(KeyV[i]); }
1286 }
1287 
1288 template <class TKey, class THashFunc>
1289 void THashSet<TKey, THashFunc>::DelKey(const TKey& Key) {
1290  IAssert(!PortV.Empty());
1291  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1292  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1293  int PrevKeyId=-1;
1294  int KeyId=PortV[PortN];
1295 
1296  while ((KeyId!=-1) &&
1297  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1298  PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
1299 
1300  IAssertR(KeyId!=-1, Key.GetStr());
1301  if (PrevKeyId==-1) {PortV[PortN]=KeyV[KeyId].Next; }
1302  else {KeyV[PrevKeyId].Next=KeyV[KeyId].Next; }
1303  KeyV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
1304  KeyV[KeyId].HashCd=TInt(-1);
1305  KeyV[KeyId].Key=TKey();
1306 }
1307 
1308 template <class TKey, class THashFunc>
1310  IAssert(!PortV.Empty());
1311  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1312  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1313  int PrevKeyId=-1;
1314  int KeyId=PortV[PortN];
1315 
1316  while ((KeyId!=-1) &&
1317  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1318  PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
1319 
1320  IAssertR(KeyId!=-1, Key.GetStr());
1321  if (PrevKeyId==-1) {PortV[PortN]=KeyV[KeyId].Next; }
1322  else {KeyV[PrevKeyId].Next=KeyV[KeyId].Next; }
1323  KeyV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
1324  KeyV[KeyId].HashCd=TInt(-1);
1325 }
1326 
1327 template <class TKey, class THashFunc>
1328 int THashSet<TKey, THashFunc>::GetKeyId(const TKey& Key) const {
1329  if (PortV.Empty()) {return -1; }
1330  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1331  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1332  int KeyId=PortV[PortN];
1333 
1334  while ((KeyId!=-1) &&
1335  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1336  KeyId=KeyV[KeyId].Next; }
1337  return KeyId;
1338 }
1339 
1340 template <class TKey, class THashFunc>
1342  do {KeyId++; } while ((KeyId<KeyV.Len())&&(KeyV[KeyId].HashCd==-1));
1343  return KeyId<KeyV.Len();
1344 }
1345 
1346 template <class TKey, class THashFunc>
1348  KeyV.Clr();
1349  int KeyId=FFirstKeyId();
1350  while (FNextKeyId(KeyId)) {
1351  KeyV.Add(GetKey(KeyId)); }
1352 }
1353 
1354 template <class TKey, class THashFunc>
1356  if (this!=&Set) {
1357  PortV.Swap(Set.PortV);
1358  KeyV.Swap(Set.KeyV);
1359  ::Swap(AutoSizeP, Set.AutoSizeP);
1360  ::Swap(FFreeKeyId, Set.FFreeKeyId);
1361  ::Swap(FreeKeys, Set.FreeKeys);
1362  }
1363 }
1364 
1365 template <class TKey, class THashFunc>
1367  if (!IsKeyIdEqKeyN()) {
1368  THashSet<TKey> Set(PortV.Len());
1369  int KeyId=FFirstKeyId();
1370  while (FNextKeyId(KeyId)) {
1371  Set.AddKey(GetKey(KeyId));
1372  }
1373  Pack();
1374  operator=(Set);
1375  IAssert(IsKeyIdEqKeyN());
1376  }
1377 }
1378 
1380 // Common Hash Set Types
1389 
1391 // Packed Vec
1392 template<class TVal>
1393 class TPackVec {
1394 public:
1395  typedef TVal* TIter;
1396 private:
1397  int Vals;
1398  TVal* ValT;
1399  void ResizeDelta(const int& ValsToAdd=1);
1400 public:
1401  TPackVec() : Vals(0), ValT(NULL) { }
1402  TPackVec(const TPackVec& Vec) : Vals(0), ValT(NULL) {
1403  Gen(Vec.Len());
1404  memcpy(ValT, Vec.ValT, sizeof(TVal)*Vals);
1405  }
1406  explicit TPackVec(const int& _Vals) : Vals(_Vals) {
1407  if (Vals==0) { ValT=NULL; } else { ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals); } }
1408  ~TPackVec() { if (ValT != NULL) { free(ValT); } }
1409  explicit TPackVec(TSIn& SIn): Vals(0), ValT(NULL) { Load(SIn); }
1410  void Load(TSIn& SIn);
1411  void Save(TSOut& SOut) const;
1412 
1413  const TVal& operator [] (const int& ValN) const { return ValT[ValN]; }
1414  TVal& operator [] (const int& ValN) { return ValT[ValN]; }
1416  memcpy(ValT, Vec.ValT, sizeof(TVal)*Vals); return *this; }
1417  TVec<TVal>& operator = (const TVec<TVal>& Vec) { Gen(Vec.Len());
1418  memcpy(ValT, Vec.ValT, sizeof(TVal)*Vals); return *this; }
1419 
1420  void Gen(const int& _Vals) {
1421  if (ValT != NULL) { free(ValT); } Vals = _Vals;
1422  if (Vals==0) { ValT=NULL; } else { ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals); } }
1423  void Clr() { if (ValT != NULL) { free(ValT); ValT=NULL; } Vals = 0; }
1424 
1425  bool Empty() const {return Vals==0; }
1426  int Len() const {return Vals; }
1427  const TVal& Last() const { return ValT[Len()-1]; }
1428  TVal& Last() { return ValT[Len()-1]; }
1429 
1430  TIter BegI() const {return ValT; }
1431  TIter EndI() const {return ValT+Vals; }
1432  TIter GetI(const int& ValN) const { return ValT+ValN; }
1433 
1434  void Add(const TVal& Val) { ResizeDelta(1); ValT[Vals-1]=Val; }
1435  void AddV(const TPackVec<TVal>& ValV) { ResizeDelta(ValV.Len());
1436  memcpy(ValT+Vals-ValV.Len(), ValV.BegI(), sizeof(TVal)*ValV.Len()); }
1437  void AddV(const TVec<TVal>& ValV) { ResizeDelta(ValV.Len());
1438  memcpy(ValT+Vals-ValV.Len(), ValV.BegI(), sizeof(TVal)*ValV.Len()); }
1439  void AddV(TSIn& FIn) { int NVals; FIn.Load(NVals);
1440  ResizeDelta(NVals); FIn.LoadBf(ValT+Vals-NVals, sizeof(TVal)*NVals); }
1441 
1442  void Sort(const bool& Asc=true) {
1443  if (Asc) { TVec<TVal>::QSortCmp(BegI(), EndI(), TLss<TVal>()); }
1444  else { TVec<TVal>::QSortCmp(BegI(), EndI(), TGtr<TVal>()); }
1445  }
1446 };
1447 
1448 template<class TVal>
1449 void TPackVec<TVal>::ResizeDelta(const int& ValsToAdd) {
1450  if (ValsToAdd == 0) return;
1451  Vals += ValsToAdd;
1452  ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals);
1453  EAssert(ValT != NULL);
1454 }
1455 
1456 template<class TVal>
1458  SIn.Load(Vals);
1459  if (Vals==0) {
1460  if (ValT != NULL) { free(ValT); }
1461  ValT = NULL; }
1462  else {
1463  ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals);
1464  }
1465  SIn.LoadBf(ValT, sizeof(TVal)*Vals);
1466 }
1467 
1468 template<class TVal>
1469 void TPackVec<TVal>::Save(TSOut& SOut) const {
1470  SOut.Save(Vals);
1471  if (Vals != 0) {
1472  SOut.SaveBf(ValT, sizeof(TVal)*Vals); }
1473 }
1474 
1475 #endif
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
Definition: shash.h:1243
bool operator==(const THashSetKeyI &SetKeyI) const
Definition: shash.h:1024
#define IAssert(Cond)
Definition: bd.h:262
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:561
void Del(const int &ValN)
Definition: shash.h:440
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3)
Definition: shash.h:1166
int GetPorts() const
Definition: shash.h:1122
static void LoadHash(const TStr &InFNm, THash< TKey, TDat, THashFunc > &Hash, const int &LoadN=-1)
Definition: shash.h:33
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:971
bool IsKeyId(const int &KeyId) const
Definition: shash.h:527
TInt FFreeKeyId
Definition: shash.h:1055
TKey Key
Definition: shash.h:454
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TVec< TSGroup > GroupV
Definition: shash.h:316
void CopyFrom(const TSparseSet &SSet, const int &MnWanted)
Definition: shash.h:852
void Clr()
Definition: shash.h:1423
~TPackVec()
Definition: shash.h:1408
TSparseTableI< TVal, GroupSize > TIter
Definition: shash.h:313
int GetGroupSize() const
Definition: shash.h:90
const TKey & GetKey() const
Definition: shash.h:21
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
static int GetGroups(const int &Vals)
Definition: shash.h:318
#define IAssertR(Cond, Reason)
Definition: bd.h:265
int Len() const
Definition: shash.h:509
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5, const TKey &Key6, const TKey &Key7)
Definition: shash.h:1174
TDat Dat
Definition: shash.h:15
THashSetKeyI & operator++(int)
Definition: shash.h:1028
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:738
int Reserved() const
Definition: shash.h:510
bool operator==(const TSparseGroup &SG) const
Definition: shash.h:185
void ResetThresh()
Definition: shash.h:555
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: shash.h:995
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5, const TKey &Key6)
Definition: shash.h:1172
void Defrag()
Definition: shash.h:1366
TSGroup & GetGrp1(const int &ValN)
Definition: shash.h:322
#define XLoadHd(Nm)
Definition: bd.h:312
void Swap(TSparseHash &HT)
Definition: shash.h:669
TVec< TSetKey > KeyV
Definition: shash.h:1053
void SaveXml(TSOut &SOut, const TStr &Nm) const
Definition: shash.h:997
int GroupNum(const int &ValN) const
Definition: shash.h:320
int PosToOffset(int Pos) const
Definition: shash.h:97
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:631
const TKey & operator()() const
Definition: shash.h:1032
static void LoadDatV(TSIn &SIn, TVec< TDat > &DatV, int LoadN=-1)
Definition: shash.h:49
void Load(TSIn &SIn)
Definition: shash.h:496
void GetDatKeyPrV(TVec< TPair< TDat, TKey > > &DatKeyPrV) const
Definition: shash.h:762
void DelKeyId(const int &KeyId)
Definition: shash.h:1134
TSparseTable< TKey, GroupSize >::TIter TIter
Definition: shash.h:774
TVal & operator()() const
Definition: shash.h:303
TKey Key
Definition: shash.h:985
bool IsEnd() const
Returns true, if the iterator is pointing to the past-end element.
Definition: shash.h:1039
bool IsEmpty(const int &ValN) const
Definition: shash.h:93
TIter GetI(const int &KeyId) const
Definition: shash.h:803
const TVal & Offset(const int &Pos) const
Definition: shash.h:94
const TSGroup & GetGroup(const int &GroupN) const
Definition: shash.h:368
Definition: dt.h:11
const TSGroup & GetGrp1(const int &ValN) const
Definition: shash.h:321
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
TSparseTableI & operator++(int)
Definition: shash.h:286
void AddKeyV(const TVec< TKey > &KeyV)
Definition: shash.h:1284
TPackVec(const TPackVec &Vec)
Definition: shash.h:1402
static const int MinBuckets
Definition: shash.h:779
void Sort(const bool &Asc=true)
Definition: shash.h:1442
bool operator<(const TSparseGroup &SG) const
Definition: shash.h:196
#define XSaveHd(Nm)
Definition: bd.h:318
void Save(TSOut &SOut) const
Definition: dt.h:1153
bool operator==(const TSHashKeyDat &HashKeyDat) const
Definition: shash.h:465
bool operator<(const TSparseTable &ST) const
Definition: shash.h:387
void Load(TSIn &SIn)
Definition: shash.h:793
bool IsKey(const TKey &Key, int &KeyId) const
Definition: shash.h:1149
unsigned int uint
Definition: bd.h:11
TSparseSet(TSIn &SIn)
Definition: shash.h:792
TIter BegI() const
Definition: shash.h:1105
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
void Load(TSIn &SIn)
Definition: shash.h:328
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:618
void Save(TSOut &SOut) const
Definition: shash.h:159
#define Fail
Definition: bd.h:238
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: shash.h:721
void Clr(const bool &DoDel=true)
Definition: shash.h:811
const TVal & operator[](const int ValN) const
Definition: shash.h:102
bool Empty() const
Definition: shash.h:508
TPackVec< TVal > & operator=(const TPackVec< TVal > &Vec)
Definition: shash.h:1415
bool operator==(const THashSet &Set) const
Definition: shash.h:1234
const TVal & Last() const
Definition: shash.h:1427
int GetValN() const
Definition: shash.h:300
uint GetDiskSz() const
Definition: shash.h:808
Definition: fl.h:319
TInt ShrinkThresh
Definition: shash.h:788
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:521
TIter BegI() const
Definition: shash.h:1430
TSHashKeyDat()
Definition: shash.h:457
void BMSet(const int &ValN)
Definition: shash.h:70
void Save(TSOut &SOut) const
Definition: hash.h:183
TInt FreeKeys
Definition: shash.h:1055
const TVal & DefVal() const
Definition: shash.h:99
static const unsigned int HashPrimeT[HashPrimes]
Definition: hash.h:100
THashSetKeyI()
Definition: shash.h:1016
int PosInGroup(const int &ValN) const
Definition: shash.h:319
TSparseTable(const TSparseTable &ST)
Definition: shash.h:326
void Save(TSOut &SOut) const
Definition: shash.h:993
void GetKeyV(TVec< TKey > &KeyV) const
Definition: shash.h:1347
TInt ExpandThresh
Definition: shash.h:788
void Gen(const int &ExpectVals)
Definition: shash.h:1115
TKey & operator[](const int &KeyId)
Definition: shash.h:1100
void Clr(const bool &DoDel=true)
Definition: shash.h:392
static const float MnOccupancy
Definition: shash.h:778
uint GetDiskSz() const
Definition: shash.h:91
int Len() const
Definition: shash.h:1426
int MxLen() const
Definition: shash.h:86
THashSetKey()
Definition: shash.h:987
bool operator==(const TSparseTable &ST) const
Definition: shash.h:382
void Clr(const bool &DoDel=true)
Definition: shash.h:514
#define XLoad(Nm)
Definition: bd.h:315
void Save(TSOut &SOut) const
Definition: dt.h:995
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:815
static int ModBit(const int &ValN)
Definition: shash.h:68
int AddKey(const TKey &Key)
Definition: shash.h:676
TInt MxVals
Definition: shash.h:315
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5, const TKey &Key6, const TKey &Key7, const TKey &Key8, const TKey &Key9)
Definition: shash.h:1178
TGroupVI EndI
Definition: shash.h:272
THashSetKey(const int &_Next, const int &_HashCd, const TKey &_Key)
Definition: shash.h:989
static void LoadHash(TSIn &SIn, THash< TKey, TDat, THashFunc > &Hash, int LoadN=-1)
Definition: shash.h:35
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5)
Definition: shash.h:1170
TIter EndI() const
Definition: shash.h:505
TInt Next
Definition: shash.h:983
void Load(TSIn &SIn)
Definition: ds.h:946
const TKey * operator->() const
Definition: shash.h:1033
static const int MinBuckets
Definition: shash.h:482
static TRnd Rnd
Definition: dt.h:1146
void Reserve(const int &MxVals)
Definition: shash.h:810
TIter EndI() const
Definition: shash.h:1431
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:511
Definition: fl.h:275
TIter GetI(const int &ValN) const
Definition: shash.h:1432
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
int Len() const
Definition: shash.h:806
bool operator==(const TSparseSet &SSet) const
Definition: shash.h:943
static int PosToOffset(const unsigned char *BitSet, int Pos)
Definition: shash.h:113
virtual void LoadCs()
Definition: fl.cpp:28
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
void Swap(TSparseSet &SSet)
Definition: shash.h:953
TSparseTable(const int &MaxVals=0)
Definition: shash.h:324
#define XSave(Nm)
Definition: bd.h:333
TSparseTableI(const TSparseTableI &STI)
Definition: shash.h:277
const TKey & GetKey() const
Definition: shash.h:1041
void Reserve(const int NewVals)
Definition: shash.h:357
TKeyDatFl(const TStr &FNm)
Definition: shash.h:17
bool IsAutoSize() const
Definition: shash.h:1123
TIter GetI(const TKey &Key) const
Definition: shash.h:1113
const TVal & Get(const int &ValN) const
Definition: shash.h:100
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:902
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
bool BMTest(const int &ValN) const
Definition: shash.h:69
static const float MnOccupancy
Definition: shash.h:481
THashSet(const THashSet &Set)
Definition: shash.h:1069
TVal & Set(const int &ValN)
Definition: shash.h:105
TDat Dat
Definition: shash.h:455
TSGroup & GetGroup(const int &GroupN)
Definition: shash.h:367
TPackVec(const int &_Vals)
Definition: shash.h:1406
void MarkDelKeyId(const int &KeyId)
Definition: shash.h:1139
int GetKeyId(const TKey &Key) const
Definition: shash.h:522
TFIn FIn
Definition: shash.h:13
TIter EndI() const
Definition: shash.h:802
bool Empty() const
Definition: shash.h:1120
TPackVec()
Definition: shash.h:1401
const TDat & GetDat(const TKey &Key) const
Definition: shash.h:705
THashSet< TFlt > TFltSet
Definition: shash.h:1384
int GetRndKeyId(TRnd &Rnd=TInt::Rnd) const
Definition: shash.h:822
TSparseTable< THashKeyDat, GroupSize >::TIter TIter
Definition: shash.h:477
TSparseTable< THashKeyDat, GroupSize >::TSGroup TSGroup
Definition: shash.h:478
void BMClear(const int &ValN)
Definition: shash.h:71
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: shash.h:754
int Groups() const
Definition: shash.h:351
TSparseTableI(const TGroupVI &BegIter, const TGroupVI &CurIter, const TGroupVI &EndIter, const int &Offset=0)
Definition: shash.h:275
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
void SaveCs()
Definition: fl.h:171
bool operator==(const TSparseTableI &STI) const
Definition: shash.h:282
Definition: bd.h:368
bool operator<(const THashSetKeyI &SetKeyI) const
Definition: shash.h:1026
void Resize()
Definition: shash.h:1196
void GetDatV(TVec< TDat > &DatV) const
Definition: shash.h:746
void Gen(const int &ExpectVals)
Definition: hash.h:222
TInt Vals
Definition: shash.h:315
TSparseGroup & operator=(const TSparseGroup &SG)
Definition: shash.h:166
void DelKey(const TKey &Key)
Definition: shash.h:1289
uint GetDiskSz() const
Definition: shash.h:353
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
bool IsKeyIdEqKeyN() const
Definition: shash.h:1126
void SaveXml(TSOut &SOut, const TStr &Nm)
Definition: shash.h:1090
static bool GetBit(const int &BitN, const uchar &Val)
Definition: bits.cpp:33
THashSet< TUChIntPr > TUChIntPrSet
Definition: shash.h:1386
int AddKey(const TKey &Key)
Definition: shash.h:960
void Load(bool &Bool)
Definition: fl.h:84
const TVal & operator[](const int &ValN) const
Definition: shash.h:1413
void CopyFrom(const TSparseHash &HT, const int &MnWanted)
Definition: shash.h:568
THashSetKey(TSIn &SIn)
Definition: shash.h:991
bool Empty() const
Definition: shash.h:805
TSHashKeyDat & operator=(const TSHashKeyDat &HashKeyDat)
Definition: shash.h:463
int Reserved() const
Definition: shash.h:87
THashSetKeyI & operator--(int)
Definition: shash.h:1029
TBool AutoSizeP
Definition: shash.h:1054
int GetRndKeyId(TRnd &Rnd=TInt::Rnd) const
Definition: shash.h:528
::TSize GetMemUsed() const
Definition: shash.h:799
void Reserve(const int &MxVals)
Definition: shash.h:513
TInt ElemCnt
Definition: shash.h:12
THashSetKeyI(const TSetKey *_KeyI, const TSetKey *_EndI)
Definition: shash.h:1019
THashSetKey< TKey > TSetKey
Definition: shash.h:1051
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
TIter GetI(const int &ValN) const
Definition: shash.h:343
size_t TSize
Definition: bd.h:58
void Load(TSIn &SIn)
Definition: dt.h:1152
TVal * operator->() const
Definition: shash.h:304
#define Assert(Cond)
Definition: bd.h:251
void Save(TSOut &SOut) const
Definition: shash.h:462
void AddV(const TPackVec< TVal > &ValV)
Definition: shash.h:1435
int Hash() const
Definition: shash.h:467
THashSet< TStr > TStrSet
Definition: shash.h:1385
~TSparseGroup()
Definition: shash.h:77
TVal & Last()
Definition: shash.h:1428
bool IsKey(const TKey &Key) const
Definition: shash.h:818
TVal & Set(const int &ValN, const TVal &Val)
Definition: shash.h:231
bool IsEmpty() const
Returns true, if the iterator is empty - has not been initialized.
Definition: shash.h:1037
THashSet< TIntPr > TIntPrSet
Definition: shash.h:1388
const TDat & GetDat() const
Definition: shash.h:23
int CurOff
Definition: shash.h:271
THashSetKeyI & Next()
Definition: shash.h:1034
void MarkDelKey(const TKey &Key)
Definition: shash.h:1309
int AddKey(const TKey &Key)
Definition: shash.h:1254
int Len() const
Definition: shash.h:18
int FFirstKeyId() const
Definition: hash.h:278
bool Eof()
Definition: fl.h:298
bool operator<(const TSparseTableI &STI) const
Definition: shash.h:284
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
bool IsKeyId(const int &KeyId) const
Definition: shash.h:821
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4)
Definition: shash.h:1168
static const float MxOccupancy
Definition: shash.h:777
TInt ExpandThresh
Definition: shash.h:491
void MoveFrom(TSparseSet &SSet, const int &MnWanted)
Definition: shash.h:875
bool operator<(const TSparseHash &SHT) const
Definition: shash.h:664
int Vals
Definition: shash.h:1397
void SaveBf(const void *Bf, const TSize &BfL)
Definition: fl.h:172
void Del(const int &ValN)
Definition: shash.h:247
void MoveFrom(TSparseHash &HT, const int &MnWanted)
Definition: shash.h:591
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: shash.h:1086
TIntV PortV
Definition: shash.h:1052
const TDat & GetDatKeyId(const int &KeyId) const
Definition: shash.h:534
Definition: fl.h:128
void ResetThresh()
Definition: shash.h:839
bool operator<(const TSparseSet &SSet) const
Definition: shash.h:948
::TSize GetMemUsed() const
Definition: shash.h:1102
int GetRndKeyId(TRnd &Rnd) const
Definition: shash.h:1144
const TKey & operator[](const int &KeyId) const
Definition: shash.h:1099
void Save(const bool &Bool)
Definition: fl.h:173
THashSet & operator=(const THashSet &Set)
Definition: shash.h:1093
int Reserved() const
Definition: shash.h:807
TInt HashCd
Definition: shash.h:984
void Swap(THashSet &Set)
Definition: shash.h:1355
int GetKeyId(const TKey &Key) const
Definition: shash.h:816
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:915
Definition: dt.h:1137
TVal * TIter
Random access iterator to TVal.
Definition: ds.h:432
THashSet< TUInt64 > TUInt64Set
Definition: shash.h:1383
bool IsKey(const TKey &Key, int &KeyId) const
Definition: shash.h:525
uint GetNextPrime(const uint &Val) const
Definition: shash.h:1184
TVal & Set(const int &ValN, const TVal &Val)
Definition: shash.h:420
TSHashKeyDat(const TKey &_Key, const TDat &_Dat)
Definition: shash.h:459
const TVal & Get(const int &ValN) const
Definition: shash.h:362
TSHashKeyDat(TSIn &SIn)
Definition: shash.h:461
TSparseTableI()
Definition: shash.h:274
const TKey & operator*() const
Definition: shash.h:1031
bool IsEnd() const
Definition: shash.h:301
void Clr(const bool &DoDel=true)
Definition: shash.h:221
TSparseGroup< TVal, GroupSize > TSGroup
Definition: shash.h:312
#define EAssert(Cond)
Definition: bd.h:280
THashSet< TUChUInt64Pr > TUChUInt64PrSet
Definition: shash.h:1387
bool IsKeyId(const int &KeyId) const
Definition: shash.h:1151
TIter EndI() const
Definition: shash.h:1112
TDat & GetDatKeyId(const int &KeyId)
Definition: shash.h:535
const TSetKey & GetSetKey(const int &KeyId) const
Definition: shash.h:1060
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:845
int Len() const
Definition: shash.h:1121
THashSetKeyI(const THashSetKeyI &_SetKeyI)
Definition: shash.h:1017
THashSet< TUCh > TUChSet
Definition: shash.h:1381
int GetMxKeyIds() const
Definition: shash.h:1124
Definition: ds.h:32
TSparseTable< TKey, GroupSize >::TSGroup TSGroup
Definition: shash.h:775
TVal * TIter
Definition: shash.h:1395
TSHashKeyDat< TKey, TDat > THashKeyDat
Definition: shash.h:476
void ResizeDelta(const int &ValsToAdd=1)
Definition: shash.h:1449
void Save(TSOut &SOut) const
Definition: shash.h:794
TGroupVI BegI
Definition: shash.h:272
TSparseGroup(TSIn &SIn)
Definition: shash.h:75
void Load(TSIn &SIn)
Definition: shash.h:1457
Definition: bd.h:385
void Save(TSOut &SOut) const
Definition: shash.h:1469
void Save(TSOut &SOut) const
Definition: shash.h:329
static THashSet< TKey > GetSet(const TKey &Key1)
Definition: shash.h:1162
void Add(const TVal &Val)
Definition: shash.h:1434
static void LoadKeyV(TSIn &SIn, TVec< TKey > &KeyV, int LoadN=-1)
Definition: shash.h:42
void AddV(const TVec< TVal > &ValV)
Definition: shash.h:1437
TDat & AddDat(const TKey &Key)
Definition: shash.h:687
TSparseHash(const int &WantedVals=0)
Definition: shash.h:494
TVal & Offset(const int &Pos)
Definition: shash.h:95
bool FNextKeyId(int &KeyId) const
Definition: shash.h:1341
Definition: dt.h:412
int Reserved() const
Definition: shash.h:350
TVec< TValGroup >::TIter TGroupVI
Definition: shash.h:270
TSparseTable(TSIn &SIn)
Definition: shash.h:327
::TSize GetMemUsed() const
Definition: shash.h:334
static int CharBit(const int &ValN)
Definition: shash.h:67
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
TVal & operator*() const
Definition: shash.h:302
static void QSortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Quick sorts the values between positions BI...EI under the comparator Cmp.
Definition: ds.h:762
TSparseTableI & operator--(int)
Definition: shash.h:293
Definition: hash.h:97
void Gen(const int &_Vals)
Definition: shash.h:1420
void LoadBf(const void *Bf, const TSize &BfL)
Definition: fl.h:81
uint GetDiskSz() const
Definition: shash.h:511
THashSetKey< TKey > TSetKey
Definition: shash.h:1011
void Swap(TSparseTable &ST)
Definition: shash.h:413
int Len() const
Definition: shash.h:349
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2)
Definition: shash.h:1164
TSparseTableI & operator=(const TSparseTableI &STI)
Definition: shash.h:280
bool IsKey(const TKey &Key) const
Definition: shash.h:524
THashSet< TInt > TIntSet
Definition: shash.h:1382
TIter BegI() const
Definition: shash.h:801
TKey Key
Definition: shash.h:14
bool Empty() const
Definition: shash.h:1425
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5, const TKey &Key6, const TKey &Key7, const TKey &Key8)
Definition: shash.h:1176
virtual TStr GetSNm() const
Definition: fl.cpp:20
void Load(TSIn &SIn)
Definition: shash.h:1078
void DelKeyIdV(const TIntV &KeyIdV)
Definition: shash.h:1135
TIter EndI() const
Definition: shash.h:342
int Len() const
Definition: shash.h:85
bool operator<(const TSHashKeyDat &HashKeyDat) const
Definition: shash.h:466
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: shash.h:729
THashSetKeyI< TKey > TIter
Definition: shash.h:1049
void Pack()
Definition: shash.h:1160
TSparseGroup< TVal, GroupSize > TValGroup
Definition: shash.h:269
bool IsEmpty(const int &ValN) const
Definition: shash.h:361
void Save(TSOut &SOut) const
Definition: shash.h:1082
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSparseHash & operator=(const TSparseHash &SHT)
Definition: shash.h:649
TSetKey & GetSetKey(const int &KeyId)
Definition: shash.h:1057
static const float MxOccupancy
Definition: shash.h:480
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
TVal * ValT
Definition: shash.h:1398
static void Save(const TStr &OutFNm, const THash< TKey, TDat, THashFunc > &Hash)
Definition: shash.h:26
TSparseTable & operator=(const TSparseTable &ST)
Definition: shash.h:372
bool Empty() const
Definition: shash.h:88
TIter BegI() const
Definition: shash.h:504
bool Next()
Definition: shash.h:19
char * CStr()
Definition: dt.h:479
unsigned short uint16
Definition: bd.h:31
::TSize GetMemUsed() const
Definition: shash.h:502
TIter BegI() const
Definition: shash.h:336
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int GetReservedKeyIds() const
Definition: shash.h:1125
TSparseHash(TSIn &SIn)
Definition: shash.h:495
TKey & GetKey()
Definition: shash.h:22
Definition: dt.h:974
TPackVec(TSIn &SIn)
Definition: shash.h:1409
TVal * Group
Definition: shash.h:65
TSparseGroup()
Definition: shash.h:74
void Load(TSIn &SIn)
Definition: shash.h:150
int Len() const
Definition: hash.h:228
THashSet()
Definition: shash.h:1066
bool Empty() const
Definition: shash.h:352
THashSetKeyI & operator=(const THashSetKeyI &SetKeyI)
Definition: shash.h:1022
TIter GetI(const TSizeTy &ValN) const
Returns an iterator an element at position ValN.
Definition: ds.h:597
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
void Resize(const int &NewVals)
Definition: shash.h:403
void AddV(TSIn &FIn)
Definition: shash.h:1439
TSparseSet & operator=(const TSparseSet &SSet)
Definition: shash.h:933
uint16 Buckets
Definition: shash.h:64
int FFirstKeyId() const
Definition: shash.h:1154
bool IsKey(const TKey &Key, int &KeyId) const
Definition: shash.h:819
int OffsetToPos(int Offset) const
Definition: shash.h:206
bool DelIfKey(const TKey &Key)
Definition: shash.h:1132
TSHashKeyDat(const TKey &_Key)
Definition: shash.h:458
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
Definition: ds.h:436
TSetKey * KeyI
Definition: shash.h:1013
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
TSetKey * EndI
Definition: shash.h:1014
static void Save(TSOut &SOut, const THash< TKey, TDat, THashFunc > &Hash)
Definition: shash.h:28
TDat & GetDat()
Definition: shash.h:24
TSparseSet(const int &WantedVals=0)
Definition: shash.h:791
bool operator==(const TSparseHash &SHT) const
Definition: shash.h:659
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
TGroupVI GroupI
Definition: shash.h:272
THashSetKey & operator=(const THashSetKey &SetKey)
Definition: shash.h:1000
TSHashKeyDat(const TSHashKeyDat &HashKeyDat)
Definition: shash.h:460
TInt ShrinkThresh
Definition: shash.h:491
THashSet(TSIn &SIn)
Definition: shash.h:1074
void Save(TSOut &SOut) const
Definition: shash.h:497
TIter GetI(const TKey &Key) const
Definition: shash.h:506