SNAP Library , Developer Reference  2013-01-07 14:03:36
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
shash.h
Go to the documentation of this file.
00001 #ifndef shash_h
00002 #define shash_h
00003 
00005 // Hash-List-File
00006 // saves and loads hash tables into files and allows fast
00007 // iteration over the saved hash table file
00008 
00009 template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey> >
00010 class TKeyDatFl {
00011 private:
00012   TInt ElemCnt;
00013   TFIn FIn;
00014   TKey Key;
00015   TDat Dat;
00016 public:
00017   TKeyDatFl(const TStr& FNm) : FIn(FNm) { ElemCnt.Load(FIn); }
00018   int Len() const { return ElemCnt; }
00019   bool Next() { if (FIn.Eof()) { return false; }
00020     Key.Load(FIn);  Dat.Load(FIn); return true; }
00021   const TKey& GetKey() const { return Key; }
00022   TKey& GetKey() { return Key; }
00023   const TDat& GetDat() const { return Dat; }
00024   TDat& GetDat() { return Dat; }
00025 
00026   static void Save(const TStr& OutFNm, const THash<TKey, TDat, THashFunc>& Hash) {
00027     TFOut FOut(OutFNm);  Load(FOut, Hash); }
00028   static void Save(TSOut& SOut, const THash<TKey, TDat, THashFunc>& Hash) {
00029     SOut.Save(Hash.Len());
00030     for (int k = Hash.FFirstKeyId(); Hash.FNextKeyId(k); ) {
00031       Hash.GetKey(k).Save(SOut);  Hash[k].Save(SOut); }
00032   }
00033   static void LoadHash(const TStr& InFNm, THash<TKey, TDat, THashFunc>& Hash, const int& LoadN=-1) {
00034     TFIn FIn(InFNm);  Load(FIn, Hash, LoadN); }
00035   static void LoadHash(TSIn& SIn, THash<TKey, TDat, THashFunc>& Hash, int LoadN=-1) {
00036     TInt ElemCnt(SIn);  const int Start=clock();
00037     if (ElemCnt < LoadN || LoadN == -1) { LoadN = ElemCnt; }
00038     printf("Loading %s: %d elements ... ", SIn.GetSNm().CStr(), LoadN);  Hash.Gen(LoadN);
00039     for (int i = 0; i < LoadN; i++) { Hash.AddDat(TKey(SIn)).Load(SIn); }
00040     printf(" [%ds]\n", int((clock()-Start)/CLOCKS_PER_SEC));
00041   }
00042   static void LoadKeyV(TSIn& SIn, TVec<TKey>& KeyV, int LoadN=-1) {
00043     TInt ElemCnt(SIn);  const int Start=clock();
00044     if (ElemCnt < LoadN || LoadN == -1) { LoadN = ElemCnt; }
00045     printf("Loading %s: %d elements ... ", SIn.GetSNm().CStr(), LoadN);  KeyV.Gen(LoadN, 0);
00046     for (int i = 0; i < LoadN; i++) { KeyV.Add(TKey(SIn));  TDat D(SIn); }
00047     printf(" [%ds]\n", int((clock()-Start)/CLOCKS_PER_SEC));
00048   }
00049   static void LoadDatV(TSIn& SIn, TVec<TDat>& DatV, int LoadN=-1) {
00050     TInt ElemCnt(SIn);  const int Start=clock();
00051     if (ElemCnt < LoadN || LoadN == -1) { LoadN = ElemCnt; }
00052     printf("Loading %s: %d elements ... ", SIn.GetSNm().CStr(), LoadN);  DatV.Gen(LoadN, 0);
00053     for (int i = 0; i < LoadN; i++) { TKey(SIn);  DatV.Add(TDat(SIn)); }
00054     printf(" [%ds]\n", int((clock()-Start)/CLOCKS_PER_SEC));
00055   }
00056 };
00057 
00059 // Sparse Table Group
00060 template <class TVal, uint16 GroupSize> // GroupSize=48; == 32*x+16
00061 class TSparseGroup {
00062 private:
00063   unsigned char BitSet [(GroupSize-1)/8 + 1];   // fancy math is so we round up
00064   uint16 Buckets;                               // limits GroupSize to 64K
00065   TVal *Group;
00066 private:
00067   static int CharBit(const int&  ValN) { return ValN >> 3; }
00068   static int ModBit(const int&  ValN) { return 1 << (ValN&7); }
00069   bool BMTest(const int&  ValN) const { return (BitSet[CharBit(ValN)] & ModBit(ValN)) != 0; }
00070   void BMSet(const int&  ValN) { BitSet[CharBit(ValN)] |= ModBit(ValN); }
00071   void BMClear(const int&  ValN) { BitSet[CharBit(ValN)] &= ~ModBit(ValN); }
00072   static int PosToOffset(const unsigned char *BitSet, int Pos);
00073 public:
00074   TSparseGroup() : Buckets(0), Group(NULL) { memset(BitSet, 0, sizeof(BitSet)); }
00075   TSparseGroup(TSIn& SIn) : Buckets(0), Group(NULL) { Load(SIn); }
00076   TSparseGroup(const TSparseGroup& SG);
00077   ~TSparseGroup() { if (Group != NULL) delete [] Group; }
00078   void Load(TSIn& SIn);
00079   void Save(TSOut& SOut) const;
00080 
00081   TSparseGroup& operator = (const TSparseGroup& SG);
00082   bool operator == (const TSparseGroup& SG) const;
00083   bool operator < (const TSparseGroup& SG) const;
00084 
00085   int Len() const { return Buckets; }
00086   int MxLen() const { return GroupSize; }
00087   int Reserved() const { return GroupSize; }
00088   bool Empty() const { return Buckets == 0; }
00089   void Clr(const bool& DoDel = true);
00090   int GetGroupSize() const { return GroupSize; }
00091   uint GetDiskSz() const { return sizeof(BitSet) + sizeof(uint16) + Buckets*sizeof(TVal); }
00092 
00093   bool IsEmpty(const int& ValN) const { return ! BMTest(ValN); }
00094   const TVal& Offset(const int& Pos) const { return Group[Pos]; }
00095   TVal& Offset(const int& Pos) { return Group[Pos]; }
00096   int OffsetToPos(int Offset) const;
00097   int PosToOffset(int Pos) const { return PosToOffset(BitSet, Pos); }
00098 
00099   const TVal& DefVal() const { static TVal DefValue = TVal();  return DefValue; }
00100   const TVal& Get(const int& ValN) const {
00101     if (BMTest(ValN)) return Group[PosToOffset(BitSet, ValN)]; else return DefVal(); }
00102   const TVal& operator [] (const int ValN) const { return Get(ValN); }
00103 
00104   TVal& Set(const int& ValN, const TVal& Val);
00105   TVal& Set(const int& ValN) {
00106     if (! BMTest(ValN)) Set(ValN, DefVal());
00107     return Group[PosToOffset(BitSet, ValN)];
00108   }
00109   void Del(const int& ValN);
00110 };
00111 
00112 template <class TVal, uint16 GroupSize>
00113 int TSparseGroup<TVal, GroupSize>::PosToOffset(const unsigned char *BitSet, int Pos) {
00114   static const int bits_in [256] = {      // # of bits set in one char
00115     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
00116     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00117     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00118     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00119     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00120     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00121     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00122     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00123     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00124     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00125     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00126     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00127     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00128     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00129     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00130     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
00131   };
00132   // [Note: condition pos > 8 is an optimization; convince yourself we
00133   // give exactly the same result as if we had pos >= 8 here instead.]
00134   int Offset = 0;
00135   for ( ; Pos > 8; Pos -= 8 )                        // bm[0..pos/8-1]
00136     Offset += bits_in[*BitSet++];                    // chars we want *all* bits in
00137   return Offset + bits_in[*BitSet & ((1 << Pos)-1)]; // the char that includes pos
00138 }
00139 
00140 template <class TVal, uint16 GroupSize>
00141 TSparseGroup<TVal, GroupSize>::TSparseGroup(const TSparseGroup& SG) : Buckets(SG.Buckets), Group(NULL) {
00142   memcpy(BitSet, SG.BitSet, sizeof(BitSet));
00143   if (Buckets > 0) {
00144     Group = new TVal [Buckets];
00145     for (int b = 0; b < Buckets; b++) { Group[b] = SG.Group[b]; }
00146   }
00147 }
00148 
00149 template <class TVal, uint16 GroupSize>
00150 void TSparseGroup<TVal, GroupSize>::Load(TSIn& SIn) {
00151   SIn.LoadBf(BitSet, sizeof(BitSet));
00152   SIn.Load(Buckets);
00153   if (Group != NULL) delete [] Group;
00154   Group = new TVal [Buckets];
00155   for (int b = 0; b < Buckets; b++) { Group[b] = TVal(SIn); }
00156 }
00157 
00158 template <class TVal, uint16 GroupSize>
00159 void TSparseGroup<TVal, GroupSize>::Save(TSOut& SOut) const {
00160   SOut.SaveBf(BitSet, sizeof(BitSet));
00161   SOut.Save(Buckets);
00162   for (int b = 0; b < Buckets; b++) { Group[b].Save(SOut); }
00163 }
00164 
00165 template <class TVal, uint16 GroupSize>
00166 TSparseGroup<TVal, GroupSize>& TSparseGroup<TVal, GroupSize>::operator = (const TSparseGroup& SG) {
00167   if (this != &SG) {
00168     if (SG.Buckets == 0 && Group != NULL) {
00169       delete [] Group;
00170       Group = 0;
00171     } else {
00172       if (Buckets != SG.Buckets) {
00173         if (Group != NULL) delete [] Group;
00174         Group = new TVal [SG.Buckets];
00175       }
00176       for (int b = 0; b < SG.Buckets; b++) { Group[b] = SG.Group[b]; }
00177     }
00178     Buckets = SG.Buckets;
00179     memcpy(BitSet, SG.BitSet, sizeof(BitSet));
00180   }
00181   return *this;
00182 }
00183 
00184 template <class TVal, uint16 GroupSize>
00185 bool TSparseGroup<TVal, GroupSize>::operator == (const TSparseGroup& SG) const {
00186   if (Buckets == SG.Buckets && memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == 0) {
00187     for (int b = 0; b < Buckets; b++) {
00188       if (Group[b] != SG.Group[b]) return false;
00189     }
00190     return true;
00191   }
00192   return false;
00193 }
00194 
00195 template <class TVal, uint16 GroupSize>
00196 bool TSparseGroup<TVal, GroupSize>::operator < (const TSparseGroup& SG) const {
00197   if (Buckets < SG.Buckets) return true;
00198   if (memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == -1) return true;
00199   for (int b = 0; b < Buckets; b++) {
00200     if (Group[b] < SG.Group[b]) return true;
00201   }
00202   return false;
00203 }
00204 
00205 template <class TVal, uint16 GroupSize>
00206 int TSparseGroup<TVal, GroupSize>::OffsetToPos(int Offset) const {
00207   Assert(Offset < Buckets);
00208   for (int i = 0; i < sizeof(BitSet); i++) {
00209     for (int b = 0; b < 8; b++) {
00210       if (TB1Def::GetBit(b, BitSet[i])) {
00211         if (Offset == 0) return i*8 + b;
00212         Offset--;
00213       }
00214     }
00215   }
00216   Fail;
00217   return -1;
00218 }
00219 
00220 template <class TVal, uint16 GroupSize>
00221 void TSparseGroup<TVal, GroupSize>::Clr(const bool& DoDel) {
00222   if (DoDel && Group != NULL) {
00223     delete [] Group;
00224     Group = 0;
00225   }
00226   memset(BitSet, 0, sizeof(BitSet));
00227   Buckets = 0;
00228 }
00229 
00230 template <class TVal, uint16 GroupSize>
00231 TVal& TSparseGroup<TVal, GroupSize>::Set(const int& ValN, const TVal& Val) {
00232   const int Offset = PosToOffset(BitSet, ValN);
00233   if (! BMTest(ValN)) {
00234     const TVal *OldGroup = Group;
00235     Group = new TVal [Buckets+1];
00236     for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
00237     for (int b = Offset+1; b <= Buckets; b++) Group[b] = OldGroup[b-1];
00238     if (OldGroup != NULL) delete [] OldGroup;
00239     Buckets++;
00240     BMSet(ValN);
00241   }
00242   Group[Offset] = Val;
00243   return Group[Offset];
00244 }
00245 
00246 template <class TVal, uint16 GroupSize>
00247 void TSparseGroup<TVal, GroupSize>::Del(const int& ValN) {
00248   if (BMTest(ValN)) {
00249     const int Offset = PosToOffset(BitSet, ValN);
00250     if (--Buckets == 0) {
00251       delete [] Group;
00252       Group = 0;
00253     } else {
00254       const TVal *OldGroup = Group;
00255       Group = new TVal [Buckets];
00256       for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
00257       for (int b = Offset+1; b <= Buckets; b++) Group[b-1] = OldGroup[b];
00258       if (OldGroup != NULL) delete [] OldGroup;
00259     }
00260     BMClear(ValN);
00261   }
00262 }
00263 
00265 // Sparse Table Iterator
00266 template <class TVal, uint16 GroupSize>
00267 class TSparseTableI {
00268 private:
00269   typedef TSparseGroup<TVal, GroupSize> TValGroup;
00270   typedef typename TVec<TValGroup>::TIter TGroupVI;
00271   int CurOff; // Offset in the current group
00272   TGroupVI BegI, GroupI, EndI;
00273 public:
00274   TSparseTableI() : CurOff(0), GroupI(NULL), EndI(NULL) { }
00275   TSparseTableI(const TGroupVI& BegIter, const TGroupVI& CurIter, const TGroupVI& EndIter,
00276     const int& Offset = 0) : CurOff(Offset), BegI(BegIter), GroupI(CurIter), EndI(EndIter) { }
00277   TSparseTableI(const TSparseTableI& STI) :
00278     CurOff(STI.CurOff), BegI(STI.BegI), GroupI(STI.GroupI), EndI(STI.EndI) { }
00279 
00280   TSparseTableI& operator = (const TSparseTableI& STI) {
00281     CurOff=STI.CurOff;  BegI=STI.BegI;  GroupI=STI.GroupI;  EndI=STI.EndI;  return *this; }
00282   bool operator == (const TSparseTableI& STI) const {
00283     return GroupI == STI.GroupI && CurOff == STI.CurOff; }
00284   bool operator < (const TSparseTableI& STI) const {
00285     return GroupI < STI.GroupI || (GroupI == STI.GroupI && CurOff < STI.CurOff); }
00286   TSparseTableI& operator++ (int) {
00287     if (CurOff+1 == GroupI->Len()) { CurOff = 0;
00288       if (GroupI < EndI) { GroupI++;
00289         while (GroupI < EndI && GroupI->Empty()) { GroupI++; } }
00290     } else { CurOff++; }
00291     return *this;
00292   }
00293   TSparseTableI& operator-- (int) {
00294     if (CurOff == 0) {
00295       while (GroupI >= BegI && GroupI->Empty()) { GroupI--; }
00296       if (GroupI >= BegI) CurOff = GroupI->Len()-1;
00297     } else { CurOff--; }
00298     return *this;
00299   }
00300   int GetValN() const { return int(GroupI-BegI)*GroupSize + GroupI->OffsetToPos(CurOff); }
00301   bool IsEnd() const { return GroupI==EndI; }
00302   TVal& operator*() const { return GroupI->Offset(CurOff); }
00303   TVal& operator()() const { return GroupI->Offset(CurOff); }
00304   TVal* operator->() const { return &(operator*()); }
00305 };
00306 
00308 // Sparse Table
00309 template <class TVal, uint16 GroupSize = 48> // == 32*x+16
00310 class TSparseTable {
00311 public:
00312   typedef TSparseGroup<TVal, GroupSize> TSGroup;
00313   typedef TSparseTableI<TVal, GroupSize> TIter;
00314 private:
00315   TInt MxVals, Vals;
00316   TVec<TSGroup> GroupV;
00317 private:
00318   static int GetGroups(const int& Vals) { return Vals == 0 ? 0 : ((Vals-1) / GroupSize) + 1; }
00319   int PosInGroup(const int& ValN) const { return ValN % GroupSize; }
00320   int GroupNum(const int& ValN) const { return ValN / GroupSize; }
00321   const TSGroup& GetGrp1(const int& ValN) const { return GroupV[GroupNum(ValN)]; }
00322   TSGroup& GetGrp1(const int& ValN) { return GroupV[GroupNum(ValN)]; }
00323 public:
00324   TSparseTable(const int& MaxVals = 0) : MxVals(MaxVals),
00325     Vals(0), GroupV(GetGroups(MaxVals), GetGroups(MaxVals)) { }
00326   TSparseTable(const TSparseTable& ST) : MxVals(ST.MxVals), Vals(ST.Vals), GroupV(ST.GroupV) { }
00327   TSparseTable(TSIn& SIn) : MxVals(SIn), Vals(SIn), GroupV(SIn) { }
00328   void Load(TSIn& SIn) { MxVals.Load(SIn);  Vals.Load(SIn);  GroupV.Load(SIn); }
00329   void Save(TSOut& SOut) const { MxVals.Save(SOut);  Vals.Save(SOut);  GroupV.Save(SOut); }
00330 
00331   TSparseTable& operator = (const TSparseTable& ST);
00332   bool operator == (const TSparseTable& ST) const;
00333   bool operator < (const TSparseTable& ST) const;
00334   ::TSize GetMemUsed() const { return 2*sizeof(TInt)+Vals*sizeof(TVal)+GroupV.GetMemUsed(); }
00335 
00336   TIter BegI() const {
00337     if (Len() > 0) { int B = 0;
00338       while (B < Groups() && GroupV[B].Empty()) { B++; }
00339       return TIter(GroupV.BegI(), GroupV.BegI()+B, GroupV.EndI()); }
00340     return TIter(GroupV.BegI(), GroupV.EndI(), GroupV.EndI());
00341   }
00342   TIter EndI() const { return TIter(GroupV.BegI(), GroupV.EndI(), GroupV.EndI()); }
00343   TIter GetI(const int& ValN) const { Assert(! IsEmpty(ValN));
00344     typedef typename TVec<TSGroup>::TIter TVIter;
00345     const TVIter GI = GroupV.GetI(GroupNum(ValN));
00346     return TIter(GroupV.BegI(), GI, GroupV.EndI(), GI->PosToOffset(PosInGroup(ValN)));
00347   }
00348 
00349   int Len() const { return Vals; }
00350   int Reserved() const { return MxVals; }
00351   int Groups() const { return GroupV.Len(); }
00352   bool Empty() const { return Vals == 0; }
00353   uint GetDiskSz() const {
00354     return sizeof(TInt)*4 + ((GroupSize+16)/8)*Groups() + sizeof(TVal)*Vals; }
00355 
00356   void Clr(const bool& DoDel = true);
00357   void Reserve(const int NewVals) { Resize(NewVals); }
00358   void Resize(const int& NewVals);
00359   void Swap(TSparseTable& ST);
00360 
00361   bool IsEmpty(const int& ValN) const { return GroupV[GroupNum(ValN)].IsEmpty(PosInGroup(ValN)); }
00362   const TVal& Get(const int& ValN) const { return GroupV[GroupNum(ValN)].Get(PosInGroup(ValN)); }
00363   TVal& Set(const int& ValN, const TVal& Val);
00364   TVal& Set(const int& ValN);
00365   void Del(const int& ValN);
00366 
00367   TSGroup& GetGroup(const int& GroupN) { return GroupV[GroupN]; }
00368   const TSGroup& GetGroup(const int& GroupN) const { return GroupV[GroupN]; }
00369 };
00370 
00371 template <class TVal, uint16 GroupSize>
00372 TSparseTable<TVal, GroupSize>& TSparseTable<TVal, GroupSize>::operator = (const TSparseTable& ST) {
00373   if (this != &ST) {
00374     MxVals = ST.MxVals;
00375     Vals = ST.Vals;
00376     GroupV = ST.GroupV;
00377   }
00378   return *this;
00379 }
00380 
00381 template <class TVal, uint16 GroupSize>
00382 bool TSparseTable<TVal, GroupSize>::operator == (const TSparseTable& ST) const {
00383   return Vals == ST.Vals && MxVals == ST.MxVals && GroupV == ST.GroupV;
00384 }
00385 
00386 template <class TVal, uint16 GroupSize>
00387 bool TSparseTable<TVal, GroupSize>::operator < (const TSparseTable& ST) const {
00388   return Vals < ST.Vals || (Vals == ST.Vals && GroupV < ST.GroupV);
00389 }
00390 
00391 template <class TVal, uint16 GroupSize>
00392 void TSparseTable<TVal, GroupSize>::Clr(const bool& DoDel) {
00393   if (! DoDel) {
00394     for (int g = 0; g < GroupV.Len(); g++) GroupV[g].Clr(false);
00395   } else {
00396     MxVals = 0;
00397     GroupV.Clr(true);
00398   }
00399   Vals = 0;
00400 }
00401 
00402 template <class TVal, uint16 GroupSize>
00403 void TSparseTable<TVal, GroupSize>::Resize(const int& NewVals) {
00404   // only allow to grow
00405   if (NewVals > MxVals) {
00406     const int Groups = GetGroups(NewVals);
00407     GroupV.Reserve(Groups, Groups);
00408     MxVals = NewVals;
00409   }
00410 }
00411 
00412 template <class TVal, uint16 GroupSize>
00413 void TSparseTable<TVal, GroupSize>::Swap(TSparseTable& ST) {
00414   ::Swap(MxVals, ST.MxVals);
00415   ::Swap(Vals, ST.Vals);
00416   GroupV.Swap(ST.GroupV);
00417 }
00418 
00419 template <class TVal, uint16 GroupSize>
00420 TVal& TSparseTable<TVal, GroupSize>::Set(const int& ValN, const TVal& Val) {
00421   Assert(ValN < MxVals);
00422   TSGroup& Group = GetGrp1(ValN);
00423   const int OldVals = Group.Len();
00424   TVal& ValRef = Group.Set(PosInGroup(ValN), Val);
00425   Vals += Group.Len() - OldVals;
00426   return ValRef;
00427 }
00428 
00429 template <class TVal, uint16 GroupSize>
00430 TVal& TSparseTable<TVal, GroupSize>::Set(const int& ValN) {
00431   Assert(ValN < MxVals);
00432   TSGroup& Group = GetGrp1(ValN);
00433   const int OldVals = Group.Len();
00434   TVal& ValRef = Group.Set(PosInGroup(ValN));
00435   Vals += Group.Len() - OldVals;
00436   return ValRef;
00437 }
00438 
00439 template <class TVal, uint16 GroupSize>
00440 void TSparseTable<TVal, GroupSize>::Del(const int& ValN) {
00441   Assert(ValN < MxVals);
00442   TSGroup& Group = GetGrp1(ValN);
00443   const int OldVals = Group.Len();
00444   Group.Del(PosInGroup(ValN));
00445   Vals += Group.Len() - OldVals;
00446 }
00447 
00449 // Sparse Hash Key Dat
00450 #pragma pack(push, 1) // pack class size
00451 template <class TKey, class TDat>
00452 class TSHashKeyDat {
00453 public:
00454   TKey Key;
00455   TDat Dat;
00456 public:
00457   TSHashKeyDat() : Key(), Dat() { }
00458   TSHashKeyDat(const TKey& _Key) : Key(_Key), Dat() { }
00459   TSHashKeyDat(const TKey& _Key, const TDat& _Dat) : Key(_Key), Dat(_Dat) { }
00460   TSHashKeyDat(const TSHashKeyDat& HashKeyDat) : Key(HashKeyDat.Key), Dat(HashKeyDat.Dat) { }
00461   explicit TSHashKeyDat(TSIn& SIn) : Key(SIn), Dat(SIn) { }
00462   void Save(TSOut& SOut) const { Key.Save(SOut);  Dat.Save(SOut); }
00463   TSHashKeyDat& operator = (const TSHashKeyDat& HashKeyDat) { if (this != &HashKeyDat) {
00464     Key = HashKeyDat.Key;  Dat = HashKeyDat.Dat; }  return *this; }
00465   bool operator == (const TSHashKeyDat& HashKeyDat) const { return Key == HashKeyDat.Key; }
00466   bool operator < (const TSHashKeyDat& HashKeyDat) const { return Key < HashKeyDat.Key; }
00467   int Hash() const { return Key.GetPrimHashCd(); }
00468 };
00469 #pragma pack(pop)
00470 
00472 // Sparse Hash Table
00473 template <class TKey, class TDat, uint16 GroupSize=48> // GroupSize= 32*x+16, for some x
00474 class TSparseHash {
00475 public:
00476   typedef TSHashKeyDat<TKey, TDat> THashKeyDat;
00477   typedef typename TSparseTable<THashKeyDat, GroupSize>::TIter TIter;
00478   typedef typename TSparseTable<THashKeyDat, GroupSize>::TSGroup TSGroup;
00479 public:
00480   static const float MxOccupancy; // = 0.7; //was 0.8
00481   static const float MnOccupancy; // = 0.4 * MxOccupancy;
00482   static const int MinBuckets;    // = 32 (must be power of 2)
00483 private:
00484   void ResetThresh();
00485   int GetMinSize(const int& CurVals, const int& WantedVals) const;
00486   void CopyFrom(const TSparseHash& HT, const int& MnWanted);
00487   void MoveFrom(TSparseHash& HT, const int& MnWanted);
00488   void ResizeDelta(const int& ValsToAdd, const int& MnWanted = 0);
00489   void FindPos(const TKey& Key, int& Pos, int& PosToIns) const;
00490 private:
00491   TInt ShrinkThresh, ExpandThresh;
00492   TSparseTable<THashKeyDat, GroupSize> Table;
00493 public:
00494   TSparseHash(const int& WantedVals = 0) : Table(GetMinSize(0, WantedVals)) { ResetThresh(); }
00495   TSparseHash(TSIn& SIn) : ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }
00496   void Load(TSIn& SIn) { ShrinkThresh.Load(SIn);  ExpandThresh.Load(SIn);  Table.Load(SIn); }
00497   void Save(TSOut& SOut) const { ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }
00498 
00499   TSparseHash& operator = (const TSparseHash& SHT);
00500   bool operator == (const TSparseHash& SHT) const;
00501   bool operator < (const TSparseHash& SHT) const;
00502   ::TSize GetMemUsed() const { return 2*sizeof(TInt)+Table.GetMemUsed(); }
00503 
00504   TIter BegI() const { return Table.BegI(); }
00505   TIter EndI() const { return Table.EndI(); }
00506   TIter GetI(const TKey& Key) const { Assert(IsKey(Key));  return Table.GetI(GetKeyId(Key)); }
00507 
00508   bool Empty() const { return Len() == 0; }
00509   int Len() const { return Table.Len(); }
00510   int Reserved() const  { return Table.Reserved(); }
00511   uint GetDiskSz() const { return 2*sizeof(TInt) + Table.GetDiskSz(); }
00512 
00513   void Reserve(const int& MxVals) { if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }
00514   void Clr(const bool& DoDel = true) { Table.Clr(DoDel);  ResetThresh(); }
00515   void Swap(TSparseHash& HT);
00516 
00517   int AddKey(const TKey& Key);
00518   TDat& AddDat(const TKey& Key);
00519   TDat& AddDat(const TKey& Key, const TDat& Dat);
00520 
00521   const TKey& GetKey(const int& KeyId) const { return Table.Get(KeyId).Key; }
00522   int GetKeyId(const TKey& Key) const {
00523     int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);  return Pos; }
00524   bool IsKey(const TKey& Key) const { return GetKeyId(Key) != -1; }
00525   bool IsKey(const TKey& Key, int& KeyId) const {
00526     KeyId = GetKeyId(Key);  return KeyId != -1; }
00527   bool IsKeyId(const int& KeyId) const { return ! Table.IsEmpty(KeyId); }
00528   int GetRndKeyId(TRnd& Rnd = TInt::Rnd) const { Assert(Len()>0);
00529     int KeyId = Rnd.GetUniDevInt(Reserved());
00530     while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }
00531 
00532   const TDat& GetDat(const TKey& Key) const;
00533   TDat& GetDat(const TKey& Key);
00534   const TDat& GetDatKeyId(const int& KeyId) const { return Table.Get(KeyId).Dat; }
00535   TDat& GetDatKeyId(const int& KeyId) { return Table.Set(KeyId).Dat; }
00536   void GetKeyDat(const int& KeyId, TKey& Key, TDat& Dat) const;
00537   bool IsKeyGetDat(const TKey& Key, TDat& Dat) const;
00538 
00539   void GetKeyV(TVec<TKey>& KeyV) const;
00540   void GetDatV(TVec<TDat>& DatV) const;
00541   void GetKeyDatPrV(TVec<TPair<TKey, TDat> >& KeyDatPrV) const;
00542   void GetDatKeyPrV(TVec<TPair<TDat, TKey> >& DatKeyPrV) const;
00543 };
00544 
00545 template <class TKey, class TDat, uint16 GroupSize>
00546 const float TSparseHash<TKey, TDat, GroupSize>::MxOccupancy = 0.8f; //0.8f;
00547 
00548 template <class TKey, class TDat, uint16 GroupSize>
00549 const float TSparseHash<TKey, TDat, GroupSize>::MnOccupancy = 0.4f * 0.8f; //0.8f
00550 
00551 template <class TKey, class TDat, uint16 GroupSize>
00552 const int TSparseHash<TKey, TDat, GroupSize>::MinBuckets = 32;
00553 
00554 template <class TKey, class TDat, uint16 GroupSize>
00555 void TSparseHash<TKey, TDat, GroupSize>::ResetThresh() {
00556   ExpandThresh = int(Table.Reserved() * MxOccupancy);
00557   ShrinkThresh = int(Table.Reserved() * MnOccupancy);
00558 }
00559 
00560 template <class TKey, class TDat, uint16 GroupSize>
00561 int TSparseHash<TKey, TDat, GroupSize>::GetMinSize(const int& CurVals, const int& WantedVals) const {
00562   int Size = MinBuckets;
00563   while (Size*MxOccupancy < WantedVals || CurVals >= Size * MxOccupancy) Size *= 2;
00564   return Size;
00565 }
00566 
00567 template <class TKey, class TDat, uint16 GroupSize>
00568 void TSparseHash<TKey, TDat, GroupSize>::CopyFrom(const TSparseHash& HT, const int& MnWanted) {
00569   Clr(false);
00570   const int NewSize = GetMinSize(HT.Reserved(), MnWanted);
00571   if (NewSize > Reserved()) {
00572     Table.Resize(NewSize);
00573     ResetThresh();
00574   }
00575   const uint BuckM1 = Reserved() - 1;
00576   for (int g = 0; g < HT.Table.Groups(); g++) {
00577     const TSGroup& Group = HT.Table.GetGroup(g);
00578     for (int b = 0; b < Group.Len(); b++) {
00579       int Tries = 0; uint BuckNum;
00580       for (BuckNum = Group.Offset(b).Hash() & BuckM1;
00581        ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
00582         Tries++;
00583         Assert(Tries < Reserved());
00584       }
00585       Table.Set(BuckNum, Group.Offset(b));
00586     }
00587   }
00588 }
00589 
00590 template <class TKey, class TDat, uint16 GroupSize>
00591 void TSparseHash<TKey, TDat, GroupSize>::MoveFrom(TSparseHash& HT, const int& MnWanted) {
00592   Clr(false);
00593   int NewSize;
00594   if (MnWanted == 0) NewSize = HT.Reserved();
00595   else NewSize = GetMinSize(HT.Reserved(), MnWanted);
00596   if (NewSize > Reserved()) {
00597     Table.Resize(NewSize);
00598     ResetThresh();
00599   }
00600   const uint BuckM1 = Reserved() - 1;
00601   for (int g = 0; g < HT.Table.Groups(); g++) {
00602     TSGroup& Group = HT.Table.GetGroup(g);
00603     for (int b = 0; b < Group.Len(); b++) {
00604       int Tries = 0; uint BuckNum;
00605       for (BuckNum = Group.Offset(b).Hash() & BuckM1;
00606        ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
00607         Tries++;
00608         Assert(Tries < Reserved());
00609       }
00610       Assert(Table.IsEmpty(BuckNum));
00611       Table.Set(BuckNum, Group.Offset(b));
00612     }
00613     Group.Clr(true); // delete
00614   }
00615 }
00616 
00617 template <class TKey, class TDat, uint16 GroupSize>
00618 void TSparseHash<TKey, TDat, GroupSize>::ResizeDelta(const int& ValsToAdd, const int& MnWanted) {
00619   if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
00620   const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
00621   if (NewSize > Reserved()) {
00622     printf("***Resize SparseHash:%d->%d\n", Reserved(), NewSize);
00623     TSparseHash TmpHt(ValsToAdd+Len());
00624     TmpHt.ResetThresh();
00625     TmpHt.MoveFrom(*this, Len());
00626     Swap(TmpHt);
00627   }
00628 }
00629 
00630 template <class TKey, class TDat, uint16 GroupSize>
00631 void TSparseHash<TKey, TDat, GroupSize>::FindPos(const TKey& Key, int& Pos, int& PosToIns) const {
00632   const uint BuckM1 = Reserved() - 1;
00633   uint BuckNum = Key.GetPrimHashCd() & BuckM1;
00634   int Tries = 0;
00635   while (true) {
00636     if (Table.IsEmpty(BuckNum)) {
00637       Pos = -1;  PosToIns = BuckNum;  return;
00638     }
00639     else if (Key == Table.Get(BuckNum).Key) {
00640       Pos = BuckNum;  PosToIns = -1;  return;
00641     }
00642     Tries++;
00643     BuckNum = (BuckNum + Tries) & BuckM1;
00644     Assert(Tries < Reserved());
00645   }
00646 }
00647 
00648 template <class TKey, class TDat, uint16 GroupSize>
00649 TSparseHash<TKey, TDat, GroupSize>& TSparseHash<TKey, TDat, GroupSize>::operator = (const TSparseHash& SHT) {
00650   if (this != &SHT) {
00651     ShrinkThresh = SHT.ShrinkThresh;
00652     ExpandThresh = SHT.ExpandThresh;
00653     Table = SHT.Table;
00654   }
00655   return *this;
00656 }
00657 
00658 template <class TKey, class TDat, uint16 GroupSize>
00659 bool TSparseHash<TKey, TDat, GroupSize>::operator == (const TSparseHash& SHT) const {
00660   return Table == SHT.Table;
00661 }
00662 
00663 template <class TKey, class TDat, uint16 GroupSize>
00664 bool TSparseHash<TKey, TDat, GroupSize>::operator < (const TSparseHash& SHT) const {
00665   return Table < SHT.Table;
00666 }
00667 
00668 template <class TKey, class TDat, uint16 GroupSize>
00669 void TSparseHash<TKey, TDat, GroupSize>::Swap(TSparseHash& HT) {
00670   ::Swap(ShrinkThresh, HT.ShrinkThresh);
00671   ::Swap(ExpandThresh, HT.ExpandThresh);
00672   Table.Swap(HT.Table);
00673 }
00674 
00675 template <class TKey, class TDat, uint16 GroupSize>
00676 int TSparseHash<TKey, TDat, GroupSize>::AddKey(const TKey& Key) {
00677   ResizeDelta(1);
00678   int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
00679   if (Pos != -1) { return Pos; } // key exists
00680   else {
00681     Table.Set(PosToIns, THashKeyDat(Key));
00682     return PosToIns;
00683   }
00684 }
00685 
00686 template <class TKey, class TDat, uint16 GroupSize>
00687 TDat& TSparseHash<TKey, TDat, GroupSize>::AddDat(const TKey& Key) {
00688   ResizeDelta(1);
00689   int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
00690   if (PosToIns != -1) {
00691     return Table.Set(PosToIns, THashKeyDat(Key)).Dat;
00692   } else { return Table.Set(Pos).Dat; }
00693 }
00694 
00695 template <class TKey, class TDat, uint16 GroupSize>
00696 TDat& TSparseHash<TKey, TDat, GroupSize>::AddDat(const TKey& Key, const TDat& Dat) {
00697   ResizeDelta(1);
00698   int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
00699   if (PosToIns != -1) {
00700     return Table.Set(PosToIns, THashKeyDat(Key, Dat)).Dat;
00701   } else { return Table.Set(Pos).Dat = Dat; }
00702 }
00703 
00704 template <class TKey, class TDat, uint16 GroupSize>
00705 const TDat& TSparseHash<TKey, TDat, GroupSize>::GetDat(const TKey& Key) const {
00706   int Pos, PosToIns;
00707   FindPos(Key, Pos, PosToIns);
00708   Assert(Pos != -1);
00709   return Table.Get(Pos).Dat;
00710 }
00711 
00712 template <class TKey, class TDat, uint16 GroupSize>
00713 TDat& TSparseHash<TKey, TDat, GroupSize>::GetDat(const TKey& Key) {
00714   int Pos, PosToIns;
00715   FindPos(Key, Pos, PosToIns);
00716   Assert(Pos != -1);
00717   return Table.Set(Pos).Dat;
00718 }
00719 
00720 template <class TKey, class TDat, uint16 GroupSize>
00721 void TSparseHash<TKey, TDat, GroupSize>::GetKeyDat(const int& KeyId, TKey& Key, TDat& Dat) const {
00722   Assert(IsKey(KeyId));
00723   const THashKeyDat& KeyDat = Table.Get(KeyId);
00724   Key = KeyDat.Key;
00725   Dat = KeyDat.Dat;
00726 }
00727 
00728 template <class TKey, class TDat, uint16 GroupSize>
00729 bool TSparseHash<TKey, TDat, GroupSize>::IsKeyGetDat(const TKey& Key, TDat& Dat) const {
00730   int KeyId;
00731   if (IsKey(Key, KeyId)) {
00732     Dat=Table.Get(KeyId).Dat;
00733     return true;
00734   } else { return false; }
00735 }
00736 
00737 template <class TKey, class TDat, uint16 GroupSize>
00738 void TSparseHash<TKey, TDat, GroupSize>::GetKeyV(TVec<TKey>& KeyV) const {
00739   KeyV.Gen(Len(), 0);
00740   for (TIter i = BegI(); i < EndI(); i++) {
00741     KeyV.Add(i->Key);
00742   }
00743 }
00744 
00745 template <class TKey, class TDat, uint16 GroupSize>
00746 void TSparseHash<TKey, TDat, GroupSize>::GetDatV(TVec<TDat>& DatV) const {
00747   DatV.Gen(Len(), 0);
00748   for (TIter i = BegI(); i < EndI(); i++) {
00749     DatV.Add(i->Dat);
00750   }
00751 }
00752 
00753 template <class TKey, class TDat, uint16 GroupSize>
00754 void TSparseHash<TKey, TDat, GroupSize>::GetKeyDatPrV(TVec<TPair<TKey, TDat> >& KeyDatPrV) const {
00755   KeyDatPrV.Gen(Len(), 0);
00756   for (TIter i = BegI(); i < EndI(); i++) {
00757     KeyDatPrV.Add(TPair<TKey, TDat>(i->Key, i->Dat));
00758   }
00759 }
00760 
00761 template <class TKey, class TDat, uint16 GroupSize>
00762 void TSparseHash<TKey, TDat, GroupSize>::GetDatKeyPrV(TVec<TPair<TDat, TKey> >& DatKeyPrV) const {
00763   DatKeyPrV.Gen(Len(), 0);
00764   for (TIter i = BegI(); i < EndI(); i++) {
00765     DatKeyPrV.Add(TPair<TDat, TKey>(i->Dat, i->Key));
00766   }
00767 }
00768 
00770 // Sparse Set
00771 template <class TKey, uint16 GroupSize=48> // GroupSize= 32*x+16, for some x
00772 class TSparseSet {
00773 public:
00774   typedef typename TSparseTable<TKey, GroupSize>::TIter TIter;
00775   typedef typename TSparseTable<TKey, GroupSize>::TSGroup TSGroup;
00776 public:
00777   static const float MxOccupancy; // = 0.7; //was 0.8
00778   static const float MnOccupancy; // = 0.4 * MxOccupancy;
00779   static const int MinBuckets;    // = 32 (must be power of 2)
00780 private:
00781   void ResetThresh();
00782   int GetMinSize(const int& CurVals, const int& WantedVals) const;
00783   void CopyFrom(const TSparseSet& SSet, const int& MnWanted);
00784   void MoveFrom(TSparseSet& SSet, const int& MnWanted);
00785   void ResizeDelta(const int& ValsToAdd, const int& MnWanted = 0);
00786   void FindPos(const TKey& Key, int& Pos, int& PosToIns) const;
00787 private:
00788   TInt ShrinkThresh, ExpandThresh;
00789   TSparseTable<TKey, GroupSize> Table;
00790 public:
00791   TSparseSet(const int& WantedVals = 0) : Table(GetMinSize(0, WantedVals)) { ResetThresh(); }
00792   TSparseSet(TSIn& SIn) : ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }
00793   void Load(TSIn& SIn) { ShrinkThresh.Load(SIn);  ExpandThresh.Load(SIn);  Table.Load(SIn); }
00794   void Save(TSOut& SOut) const { ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }
00795 
00796   TSparseSet& operator = (const TSparseSet& SSet);
00797   bool operator == (const TSparseSet& SSet) const;
00798   bool operator < (const TSparseSet& SSet) const;
00799   ::TSize GetMemUsed() const { return 2*sizeof(TInt)+Table.GetMemUsed(); }
00800 
00801   TIter BegI() const { return Table.BegI(); }
00802   TIter EndI() const { return Table.EndI(); }
00803   TIter GetI(const int& KeyId) const { Assert(IsKeyId(KeyId));  return Table.GetI(KeyId); }
00804 
00805   bool Empty() const { return Len() == 0; }
00806   int Len() const { return Table.Len(); }
00807   int Reserved() const  { return Table.Reserved(); }
00808   uint GetDiskSz() const { return 2*sizeof(TInt) + Table.GetDiskSz(); }
00809 
00810   void Reserve(const int& MxVals) { if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }
00811   void Clr(const bool& DoDel = true) { Table.Clr(DoDel);  ResetThresh(); }
00812   void Swap(TSparseSet& SSet);
00813 
00814   int AddKey(const TKey& Key);
00815   const TKey& GetKey(const int& KeyId) const { return Table.Get(KeyId); }
00816   int GetKeyId(const TKey& Key) const { int Pos, PosToIns;
00817     FindPos(Key, Pos, PosToIns);  return Pos; }
00818   bool IsKey(const TKey& Key) const { return GetKeyId(Key) != -1; }
00819   bool IsKey(const TKey& Key, int& KeyId) const {
00820     KeyId = GetKeyId(Key);  return KeyId != -1; }
00821   bool IsKeyId(const int& KeyId) const { return ! Table.IsEmpty(KeyId); }
00822   int GetRndKeyId(TRnd& Rnd = TInt::Rnd) const { Assert(Len()>0);
00823     int KeyId = Rnd.GetUniDevInt(Reserved());
00824     while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }
00825 
00826   void GetKeyV(TVec<TKey>& KeyV) const;
00827 };
00828 
00829 template <class TKey, uint16 GroupSize>
00830 const float TSparseSet<TKey, GroupSize>::MxOccupancy = 0.8f;
00831 
00832 template <class TKey, uint16 GroupSize>
00833 const float TSparseSet<TKey, GroupSize>::MnOccupancy = 0.4f * 0.8f;
00834 
00835 template <class TKey, uint16 GroupSize>
00836 const int TSparseSet<TKey, GroupSize>::MinBuckets = 32;
00837 
00838 template <class TKey, uint16 GroupSize>
00839 void TSparseSet<TKey, GroupSize>::ResetThresh() {
00840   ExpandThresh = int(Table.Reserved() * MxOccupancy);
00841   ShrinkThresh = int(Table.Reserved() * MnOccupancy);
00842 }
00843 
00844 template <class TKey, uint16 GroupSize>
00845 int TSparseSet<TKey, GroupSize>::GetMinSize(const int& CurVals, const int& WantedVals) const {
00846   int Size = MinBuckets;
00847   while (Size*MxOccupancy <= WantedVals || CurVals > Size * MxOccupancy) Size *= 2;
00848   return Size;
00849 }
00850 
00851 template <class TKey, uint16 GroupSize>
00852 void TSparseSet<TKey, GroupSize>::CopyFrom(const TSparseSet& SSet, const int& MnWanted) {
00853   Clr(false);
00854   const int NewSize = GetMinSize(SSet.Reserved(), MnWanted);
00855   if (NewSize > Reserved()) {
00856     Table.Resize(NewSize);
00857     ResetThresh();
00858   }
00859   const uint BuckM1 = Reserved() - 1;
00860   for (int g = 0; g < SSet.Table.Groups(); g++) {
00861     const TSGroup& Group = SSet.Table.GetGroup(g);
00862     for (int b = 0; b < Group.Len(); b++) {
00863       int Tries = 0; uint BuckNum;
00864       for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
00865        ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
00866         Tries++;
00867         Assert(Tries < Reserved());
00868       }
00869       Table.Set(BuckNum, Group.Offset(b));
00870     }
00871   }
00872 }
00873 
00874 template <class TKey, uint16 GroupSize>
00875 void TSparseSet<TKey, GroupSize>::MoveFrom(TSparseSet& SSet, const int& MnWanted) {
00876   Clr(false);
00877   int NewSize;
00878   if (MnWanted == 0) NewSize = SSet.Reserved();
00879   else NewSize = GetMinSize(SSet.Reserved(), MnWanted);
00880   if (NewSize > Reserved()) {
00881     Table.Resize(NewSize);
00882     ResetThresh();
00883   }
00884   const uint BuckM1 = Reserved() - 1;
00885   for (int g = 0; g < SSet.Table.Groups(); g++) {
00886     TSGroup& Group = SSet.Table.GetGroup(g);
00887     for (int b = 0; b < Group.Len(); b++) {
00888       int Tries = 0; uint BuckNum;
00889       for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
00890        ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
00891         Tries++;
00892         Assert(Tries < Reserved());
00893       }
00894       Assert(Table.IsEmpty(BuckNum));
00895       Table.Set(BuckNum, Group.Offset(b));
00896     }
00897     Group.Clr(true); // delete
00898   }
00899 }
00900 
00901 template <class TKey, uint16 GroupSize>
00902 void TSparseSet<TKey, GroupSize>::ResizeDelta(const int& ValsToAdd, const int& MnWanted) {
00903   if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
00904   const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
00905   if (NewSize > Reserved()) {
00906     printf("***Resize SparseSet: %d->%d\n", Reserved(), NewSize);
00907     TSparseSet TmpSSet(Len()+ValsToAdd);
00908     TmpSSet.ResetThresh();
00909     TmpSSet.MoveFrom(*this, Len());
00910     Swap(TmpSSet);
00911   }
00912 }
00913 
00914 template <class TKey, uint16 GroupSize>
00915 void TSparseSet<TKey, GroupSize>::FindPos(const TKey& Key, int& Pos, int& PosToIns) const {
00916   const uint BuckM1 = Reserved() - 1;
00917   uint BuckNum = Key.GetPrimHashCd() & BuckM1;
00918   int Tries = 0;
00919   while (true) {
00920     if (Table.IsEmpty(BuckNum)) {
00921       Pos = -1;  PosToIns = BuckNum;  return;
00922     }
00923     else if (Key == Table.Get(BuckNum)) {
00924       Pos = BuckNum;  PosToIns = -1;  return;
00925     }
00926     Tries++;
00927     BuckNum = (BuckNum + Tries) & BuckM1;
00928     Assert(Tries < Reserved());
00929   }
00930 }
00931 
00932 template <class TKey, uint16 GroupSize>
00933 TSparseSet<TKey, GroupSize>& TSparseSet<TKey, GroupSize>::operator = (const TSparseSet& SSet) {
00934   if (this != &SSet) {
00935     ShrinkThresh = SSet.ShrinkThresh;
00936     ExpandThresh = SSet.ExpandThresh;
00937     Table = SSet.Table;
00938   }
00939   return *this;
00940 }
00941 
00942 template <class TKey, uint16 GroupSize>
00943 bool TSparseSet<TKey, GroupSize>::operator == (const TSparseSet& SSet) const {
00944   return Table == SSet.Table;
00945 }
00946 
00947 template <class TKey, uint16 GroupSize>
00948 bool TSparseSet<TKey, GroupSize>::operator < (const TSparseSet& SSet) const {
00949   return Table < SSet.Table;
00950 }
00951 
00952 template <class TKey, uint16 GroupSize>
00953 void TSparseSet<TKey, GroupSize>::Swap(TSparseSet& SSet) {
00954   ::Swap(ShrinkThresh, SSet.ShrinkThresh);
00955   ::Swap(ExpandThresh, SSet.ExpandThresh);
00956   Table.Swap(SSet.Table);
00957 }
00958 
00959 template <class TKey, uint16 GroupSize>
00960 int TSparseSet<TKey, GroupSize>::AddKey(const TKey& Key) {
00961   ResizeDelta(1);
00962   int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
00963   if (Pos != -1) { return Pos; } // key exists
00964   else {
00965     Table.Set(PosToIns, Key);
00966     return PosToIns;
00967   }
00968 }
00969 
00970 template <class TKey, uint16 GroupSize>
00971 void TSparseSet<TKey, GroupSize>::GetKeyV(TVec<TKey>& KeyV) const {
00972   KeyV.Gen(Len(), 0);
00973   for (TIter I = BegI(); I < EndI(); I++) {
00974     KeyV.Add(I()); }
00975 }
00976 
00978 // Set-Hash-Key
00979 #pragma pack(push, 1) // pack class size
00980 template <class TKey>
00981 class THashSetKey{
00982 public:
00983   TInt Next;
00984   TInt HashCd;
00985   TKey Key;
00986 public:
00987   THashSetKey():
00988     Next(-1), HashCd(-1), Key() {}
00989   THashSetKey(const int& _Next, const int& _HashCd, const TKey& _Key):
00990     Next(_Next), HashCd(_HashCd), Key(_Key) {}
00991   explicit THashSetKey(TSIn& SIn):
00992     Next(SIn), HashCd(SIn), Key(SIn) {}
00993   void Save(TSOut& SOut) const {
00994     Next.Save(SOut); HashCd.Save(SOut); Key.Save(SOut); }
00995   void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="") {
00996     XLoadHd(Nm); XLoad(Key); }
00997   void SaveXml(TSOut& SOut, const TStr& Nm) const {
00998     XSaveHd(Nm); XSave(Key); }
00999 
01000   THashSetKey& operator=(const THashSetKey& SetKey) {
01001     if (this!=&SetKey) { Next=SetKey.Next; HashCd=SetKey.HashCd; Key=SetKey.Key; }
01002     return *this; }
01003 };
01004 #pragma pack(pop)
01005 
01007 // Set-Hash-Key-Iterator
01008 template <class TKey>
01009 class THashSetKeyI{
01010 private:
01011   typedef THashSetKey<TKey> TSetKey;
01012   TSetKey* KeyI;
01013   TSetKey* EndI;
01014 public:
01015   THashSetKeyI(): KeyI(NULL), EndI(NULL) { }
01016   THashSetKeyI(const THashSetKeyI& _SetKeyI):
01017     KeyI(_SetKeyI.KeyI), EndI(_SetKeyI.EndI) { }
01018   THashSetKeyI(const TSetKey* _KeyI, const TSetKey* _EndI):
01019     KeyI((TSetKey*)_KeyI), EndI((TSetKey*)_EndI) { }
01020 
01021   THashSetKeyI& operator=(const THashSetKeyI& SetKeyI) {
01022     KeyI=SetKeyI.KeyI; EndI=SetKeyI.EndI; return *this; }
01023   bool operator==(const THashSetKeyI& SetKeyI) const {
01024     return KeyI==SetKeyI.KeyI; }
01025   bool operator<(const THashSetKeyI& SetKeyI) const {
01026     return KeyI<SetKeyI.KeyI; }
01027   THashSetKeyI& operator++(int) { KeyI++; while (KeyI < EndI && KeyI->HashCd==-1) { KeyI++; } return *this; }
01028   THashSetKeyI& operator--(int) { do { KeyI--; } while (KeyI->HashCd==-1); return *this; }
01029 
01030   const TKey& operator*() const { return KeyI->Key; }
01031   const TKey& operator()() const { return KeyI->Key; }
01032   const TKey* operator->() const { return KeyI->Key; }
01033 
01034   const TKey& GetKey() const {Assert((KeyI!=NULL)&&(KeyI->HashCd!=-1)); return KeyI->Key; }
01035 };
01036 
01038 // Set-Table
01039 template <class TKey, class THashFunc = TDefaultHashFunc<TKey> >
01040 class THashSet{
01041 public:
01042   typedef THashSetKeyI<TKey> TIter;
01043 private:
01044   typedef THashSetKey<TKey> TSetKey;
01045   TIntV PortV;
01046   TVec<TSetKey> KeyV;
01047   TBool AutoSizeP;
01048   TInt FFreeKeyId, FreeKeys;
01049 private:
01050   TSetKey& GetSetKey(const int& KeyId) {
01051     TSetKey& SetKey=KeyV[KeyId];
01052     Assert(SetKey.HashCd!=-1); return SetKey; }
01053   const TSetKey& GetSetKey(const int& KeyId) const {
01054     const TSetKey& SetKey=KeyV[KeyId];
01055     Assert(SetKey.HashCd!=-1); return SetKey; }
01056   uint GetNextPrime(const uint& Val) const;
01057   void Resize();
01058 public:
01059   THashSet():
01060     PortV(), KeyV(),
01061     AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0) { }
01062   THashSet(const THashSet& Set):
01063     PortV(Set.PortV), KeyV(Set.KeyV), AutoSizeP(Set.AutoSizeP),
01064     FFreeKeyId(Set.FFreeKeyId), FreeKeys(Set.FreeKeys) { }
01065   THashSet(const int& ExpectVals, const bool& _AutoSizeP=false);
01066   explicit THashSet(const TVec<TKey>& KeyV);
01067   explicit THashSet(TSIn& SIn):
01068     PortV(SIn), KeyV(SIn),
01069     AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn) {
01070     SIn.LoadCs(); }
01071   void Load(TSIn& SIn) {
01072     PortV.Load(SIn); KeyV.Load(SIn);
01073     AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
01074     SIn.LoadCs(); }
01075   void Save(TSOut& SOut) const {
01076     PortV.Save(SOut); KeyV.Save(SOut);
01077     AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
01078     SOut.SaveCs(); }
01079   void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="") {
01080     XLoadHd(Nm); TVec<TSetKey> KeyV; XLoad(KeyV); XLoad(AutoSizeP);
01081     for (int KeyN=0; KeyN<KeyV.Len(); KeyN++) {
01082       AddKey(KeyV[KeyN].Key); }}
01083   void SaveXml(TSOut& SOut, const TStr& Nm) {
01084     Defrag(); XSaveHd(Nm); XSave(KeyV); XSave(AutoSizeP); }
01085 
01086   THashSet& operator=(const THashSet& Set) {
01087     if (this!=&Set) {
01088       PortV=Set.PortV; KeyV=Set.KeyV; AutoSizeP=Set.AutoSizeP;
01089       FFreeKeyId=Set.FFreeKeyId; FreeKeys=Set.FreeKeys; }
01090     return *this; }
01091   bool operator==(const THashSet& Set) const;
01092   const TKey& operator[](const int& KeyId) const {return GetSetKey(KeyId).Key; }
01093   TKey& operator[](const int& KeyId) {return GetSetKey(KeyId).Key; }
01094   //bool operator()(const TKey& Key) {return IsKey(Key); }
01095   ::TSize GetMemUsed() const {
01096     return PortV.GetMemUsed() + KeyV.GetMemUsed() + sizeof(bool) + 2*sizeof(int); }
01097 
01098   TIter BegI() const {
01099     if (Len()>0) {
01100       if (IsKeyIdEqKeyN()) { return TIter(KeyV.BegI(), KeyV.EndI()); }
01101       int FKeyId=-1;  FNextKeyId(FKeyId);
01102       return TIter(KeyV.BegI()+FKeyId, KeyV.EndI()); }
01103     return TIter(KeyV.EndI(), KeyV.EndI());
01104   }
01105   TIter EndI() const {return TIter(KeyV.EndI(), KeyV.EndI()); }
01106   TIter GetI(const TKey& Key) const {return TIter(&KeyV[GetKeyId(Key)], KeyV.EndI()); }
01107 
01108   void Gen(const int& ExpectVals) {
01109     PortV.Gen(GetNextPrime(ExpectVals/2)); KeyV.Gen(ExpectVals, 0);
01110     FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1)); }
01111 
01112   void Clr(const bool& DoDel=true, const int& NoDelLim=-1);
01113   bool Empty() const {return Len()==0; }
01114   int Len() const {return KeyV.Len()-FreeKeys; }
01115   int GetPorts() const {return PortV.Len(); }
01116   bool IsAutoSize() const {return AutoSizeP; }
01117   int GetMxKeyIds() const {return KeyV.Len(); }
01118   int GetReservedKeyIds() const { return KeyV.Reserved(); }
01119   bool IsKeyIdEqKeyN() const {return FreeKeys==0; }
01120 
01121   int AddKey(const TKey& Key);
01122   void AddKeyV(const TVec<TKey>& KeyV);
01123 
01124   void DelKey(const TKey& Key);
01125   void DelIfKey(const TKey& Key) {
01126     int KeyId; if (IsKey(Key, KeyId)) {DelKeyId(KeyId); }}
01127   void DelKeyId(const int& KeyId) {DelKey(GetKey(KeyId)); }
01128   void DelKeyIdV(const TIntV& KeyIdV) {
01129     for (int KeyIdN=0; KeyIdN<KeyIdV.Len(); KeyIdN++) {DelKeyId(KeyIdV[KeyIdN]); }}
01130 
01131   void MarkDelKey(const TKey& Key);
01132   void MarkDelKeyId(const int& KeyId) {MarkDelKey(GetKey(KeyId)); }
01133 
01134   const TKey& GetKey(const int& KeyId) const {
01135     return GetSetKey(KeyId).Key; }
01136   int GetKeyId(const TKey& Key) const;
01137   int GetRndKeyId(TRnd& Rnd) const {
01138     IAssert(IsKeyIdEqKeyN());
01139     IAssert(Len()>0);
01140     return Rnd.GetUniDevInt(Len()); }
01141   bool IsKey(const TKey& Key) const {return GetKeyId(Key)!=-1; }
01142   bool IsKey(const TKey& Key, int& KeyId) const {
01143     KeyId=GetKeyId(Key); return KeyId!=-1; }
01144   bool IsKeyId(const int& KeyId) const {
01145     return (0<=KeyId)&&(KeyId<KeyV.Len())&&(KeyV[KeyId].HashCd!=-1); }
01146 
01147   int FFirstKeyId() const {return 0-1; }
01148   bool FNextKeyId(int& KeyId) const;
01149   void GetKeyV(TVec<TKey>& KeyV) const;
01150   void Swap(THashSet& Set);
01151 
01152   void Defrag();
01153   void Pack() {KeyV.Pack(); }
01154 
01155   static THashSet<TKey> GetSet(const TKey& Key1){
01156         THashSet<TKey> Set(1); Set.AddKey(Key1); return Set;}
01157   static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2){
01158     THashSet<TKey> Set(2); Set.AddKey(Key1); Set.AddKey(Key2); return Set;}
01159   static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3){
01160     THashSet<TKey> Set(3); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); return Set;}
01161   static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4){
01162     THashSet<TKey> Set(4); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); return Set;}
01163   static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4, const TKey& Key5){
01164     THashSet<TKey> Set(5); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); return Set;}
01165   static THashSet<TKey> GetSet(const TKey& Key1, const TKey& Key2, const TKey& Key3, const TKey& Key4, const TKey& Key5, const TKey& Key6){
01166     THashSet<TKey> Set(6); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); return Set;}
01167   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){
01168     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;}
01169   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){
01170     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;}
01171   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){
01172     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;}
01173 
01174 };
01175 
01176 template <class TKey, class THashFunc>
01177 uint THashSet<TKey, THashFunc>::GetNextPrime(const uint& Val) const {
01178   uint* f=(uint*)TIntH::HashPrimeT, *m, *l=(uint*)TIntH::HashPrimeT + (int)TIntH::HashPrimes;
01179   int h, len = (int)TIntH::HashPrimes;
01180   while (len > 0) {
01181     h = len >> 1;  m = f + h;
01182     if (*m < Val) { f = m;  f++;  len = len - h - 1; }
01183     else len = h;
01184   }
01185   return f == l ? *(l - 1) : *f;
01186 }
01187 
01188 template <class TKey, class THashFunc>
01189 void THashSet<TKey, THashFunc>::Resize() {
01190   // resize & initialize port vector
01191   if (PortV.Len()==0) {PortV.Gen(17); }
01192   else if (AutoSizeP&&(KeyV.Len()>2*PortV.Len())) {
01193     PortV.Gen(GetNextPrime(PortV.Len()+1));
01194   } else {
01195     return;
01196   }
01197   PortV.PutAll(TInt(-1));
01198   // reSet keys
01199   for (int KeyId=0; KeyId<KeyV.Len(); KeyId++) {
01200     TSetKey& SetKey=KeyV[KeyId];
01201     if (SetKey.HashCd!=-1) {
01202       int PortN=abs(THashFunc::GetPrimHashCd(SetKey.Key)%PortV.Len());
01203       SetKey.Next=PortV[PortN];
01204       PortV[PortN]=KeyId;
01205     }
01206   }
01207 }
01208 
01209 template <class TKey, class THashFunc>
01210 THashSet<TKey, THashFunc>::THashSet(const int& ExpectVals, const bool& _AutoSizeP):
01211   PortV(GetNextPrime(ExpectVals/2+1)), KeyV(ExpectVals, 0),
01212   AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0) {
01213   PortV.PutAll(TInt(-1));
01214 }
01215 
01216 template <class TKey, class THashFunc>
01217 THashSet<TKey, THashFunc>::THashSet(const TVec<TKey>& _KeyV) :
01218  PortV(GetNextPrime(_KeyV.Len()/2+1)), KeyV(_KeyV.Len(), 0),
01219  AutoSizeP(false), FFreeKeyId(-1), FreeKeys(0) {
01220   PortV.PutAll(TInt(-1));
01221   for (int i = 0; i < _KeyV.Len(); i++) {
01222     AddKey(_KeyV[i]);
01223   }
01224 }
01225 
01226 template <class TKey, class THashFunc>
01227 bool THashSet<TKey, THashFunc>::operator==(const THashSet& Set) const {
01228   if (Len() != Set.Len()) { return false; }
01229   for (int k = FFirstKeyId(); FNextKeyId(k); k++) {
01230     if (! Set.IsKey(GetKey(k))) { return false; }
01231   }
01232   return true;
01233 }
01234 
01235 template <class TKey, class THashFunc>
01236 void THashSet<TKey, THashFunc>::Clr(const bool& DoDel, const int& NoDelLim) {
01237   if (DoDel) {
01238     PortV.Clr(); KeyV.Clr();
01239   } else {
01240     PortV.PutAll(TInt(-1));
01241     KeyV.Clr(DoDel, NoDelLim);
01242   }
01243   FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
01244 }
01245 
01246 template <class TKey, class THashFunc>
01247 int THashSet<TKey, THashFunc>::AddKey(const TKey& Key) {
01248   if ((KeyV.Len()>2*PortV.Len())||PortV.Empty()) {Resize(); }
01249   int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
01250   int HashCd=abs(THashFunc::GetSecHashCd(Key));
01251   int PrevKeyId=-1;
01252   int KeyId=PortV[PortN];
01253 
01254   while ((KeyId!=-1) &&
01255    !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
01256     PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
01257 
01258   if (KeyId==-1) {
01259     if (FFreeKeyId==-1) {
01260       KeyId=KeyV.Add(TSetKey(-1, HashCd, Key));
01261     } else {
01262       KeyId=FFreeKeyId; FFreeKeyId=KeyV[FFreeKeyId].Next; FreeKeys--;
01263       KeyV[KeyId].Next = -1;
01264       KeyV[KeyId].HashCd = HashCd;
01265       KeyV[KeyId].Key = Key;
01266     }
01267     if (PrevKeyId==-1) {
01268       PortV[PortN]=KeyId;
01269     } else {
01270       KeyV[PrevKeyId].Next=KeyId;
01271     }
01272   }
01273   return KeyId;
01274 }
01275 
01276 template <class TKey, class THashFunc>
01277 void THashSet<TKey, THashFunc>::AddKeyV(const TVec<TKey>& KeyV) {
01278   for (int i = 0; i < KeyV.Len(); i++) { AddKey(KeyV[i]); }
01279 }
01280 
01281 template <class TKey, class THashFunc>
01282 void THashSet<TKey, THashFunc>::DelKey(const TKey& Key) {
01283   IAssert(!PortV.Empty());
01284   int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
01285   int HashCd=abs(THashFunc::GetSecHashCd(Key));
01286   int PrevKeyId=-1;
01287   int KeyId=PortV[PortN];
01288 
01289   while ((KeyId!=-1) &&
01290    !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
01291     PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
01292 
01293   IAssertR(KeyId!=-1, Key.GetStr());
01294   if (PrevKeyId==-1) {PortV[PortN]=KeyV[KeyId].Next; }
01295   else {KeyV[PrevKeyId].Next=KeyV[KeyId].Next; }
01296   KeyV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
01297   KeyV[KeyId].HashCd=TInt(-1);
01298   KeyV[KeyId].Key=TKey();
01299 }
01300 
01301 template <class TKey, class THashFunc>
01302 void THashSet<TKey, THashFunc>::MarkDelKey(const TKey& Key) {
01303   IAssert(!PortV.Empty());
01304   int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
01305   int HashCd=abs(THashFunc::GetSecHashCd(Key));
01306   int PrevKeyId=-1;
01307   int KeyId=PortV[PortN];
01308 
01309   while ((KeyId!=-1) &&
01310    !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
01311     PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
01312 
01313   IAssertR(KeyId!=-1, Key.GetStr());
01314   if (PrevKeyId==-1) {PortV[PortN]=KeyV[KeyId].Next; }
01315   else {KeyV[PrevKeyId].Next=KeyV[KeyId].Next; }
01316   KeyV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
01317   KeyV[KeyId].HashCd=TInt(-1);
01318 }
01319 
01320 template <class TKey, class THashFunc>
01321 int THashSet<TKey, THashFunc>::GetKeyId(const TKey& Key) const {
01322   if (PortV.Empty()) {return -1; }
01323   int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
01324   int HashCd=abs(THashFunc::GetSecHashCd(Key));
01325   int KeyId=PortV[PortN];
01326 
01327   while ((KeyId!=-1) &&
01328    !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
01329     KeyId=KeyV[KeyId].Next; }
01330   return KeyId;
01331 }
01332 
01333 template <class TKey, class THashFunc>
01334 bool THashSet<TKey, THashFunc>::FNextKeyId(int& KeyId) const {
01335   do {KeyId++; } while ((KeyId<KeyV.Len())&&(KeyV[KeyId].HashCd==-1));
01336   return KeyId<KeyV.Len();
01337 }
01338 
01339 template <class TKey, class THashFunc>
01340 void THashSet<TKey, THashFunc>::GetKeyV(TVec<TKey>& KeyV) const {
01341   KeyV.Clr();
01342   int KeyId=FFirstKeyId();
01343   while (FNextKeyId(KeyId)) {
01344     KeyV.Add(GetKey(KeyId)); }
01345 }
01346 
01347 template <class TKey, class THashFunc>
01348 void THashSet<TKey, THashFunc>::Swap(THashSet& Set) {
01349   if (this!=&Set) {
01350     PortV.Swap(Set.PortV);
01351     KeyV.Swap(Set.KeyV);
01352     ::Swap(AutoSizeP, Set.AutoSizeP);
01353     ::Swap(FFreeKeyId, Set.FFreeKeyId);
01354     ::Swap(FreeKeys, Set.FreeKeys);
01355   }
01356 }
01357 
01358 template <class TKey, class THashFunc>
01359 void THashSet<TKey, THashFunc>::Defrag() {
01360   if (!IsKeyIdEqKeyN()) {
01361     THashSet<TKey> Set(PortV.Len());
01362     int KeyId=FFirstKeyId(); TKey Key;
01363     while (FNextKeyId(KeyId)) {
01364       GetKey(KeyId, Key);
01365       Set.AddKey(Key);
01366     }
01367     Pack();
01368     operator=(Set);
01369     IAssert(IsKeyIdEqKeyN());
01370   }
01371 }
01372 
01374 // Common Hash Set Types
01375 typedef THashSet<TUCh> TUChSet;
01376 typedef THashSet<TInt> TIntSet;
01377 typedef THashSet<TUInt64> TUInt64Set;
01378 typedef THashSet<TFlt> TFltSet;
01379 typedef THashSet<TStr> TStrSet;
01380 typedef THashSet<TUChIntPr> TUChIntPrSet;
01381 typedef THashSet<TUChUInt64Pr> TUChUInt64PrSet;
01382 typedef THashSet<TIntPr> TIntPrSet;
01383 
01385 // Packed Vec
01386 template<class TVal>
01387 class TPackVec {
01388 public:
01389   typedef TVal* TIter;
01390 private:
01391   int Vals;
01392   TVal* ValT;
01393   void ResizeDelta(const int& ValsToAdd=1);
01394 public:
01395   TPackVec() : Vals(0), ValT(NULL) { }
01396   TPackVec(const TPackVec& Vec) : Vals(0), ValT(NULL) {
01397     Gen(Vec.Len());
01398     memcpy(ValT, Vec.ValT, sizeof(TVal)*Vals);
01399   }
01400   explicit TPackVec(const int& _Vals) : Vals(_Vals) {
01401     if (Vals==0) { ValT=NULL; } else { ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals); } }
01402   ~TPackVec() { if (ValT != NULL) { free(ValT); } }
01403   explicit TPackVec(TSIn& SIn): Vals(0), ValT(NULL) { Load(SIn); }
01404   void Load(TSIn& SIn);
01405   void Save(TSOut& SOut) const;
01406 
01407   const TVal& operator [] (const int& ValN) const { return ValT[ValN]; }
01408   TVal& operator [] (const int& ValN) { return ValT[ValN]; }
01409   TPackVec<TVal>& operator = (const TPackVec<TVal>& Vec) { Gen(Vec.Len());
01410     memcpy(ValT, Vec.ValT, sizeof(TVal)*Vals); return *this; }
01411   TVec<TVal>& operator = (const TVec<TVal>& Vec) { Gen(Vec.Len());
01412     memcpy(ValT, Vec.ValT, sizeof(TVal)*Vals); return *this; }
01413 
01414   void Gen(const int& _Vals) {
01415     if (ValT != NULL) { free(ValT); } Vals = _Vals;
01416     if (Vals==0) { ValT=NULL; } else { ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals); } }
01417   void Clr() { if (ValT != NULL) { free(ValT); ValT=NULL; } Vals = 0; }
01418 
01419   bool Empty() const {return Vals==0; }
01420   int Len() const {return Vals; }
01421   const TVal& Last() const { return ValT[Len()-1]; }
01422   TVal& Last() { return ValT[Len()-1]; }
01423 
01424   TIter BegI() const {return ValT; }
01425   TIter EndI() const {return ValT+Vals; }
01426   TIter GetI(const int& ValN) const { return ValT+ValN; }
01427 
01428   void Add(const TVal& Val) { ResizeDelta(1); ValT[Vals-1]=Val; }
01429   void AddV(const TPackVec<TVal>& ValV) { ResizeDelta(ValV.Len());
01430     memcpy(ValT+Vals-ValV.Len(), ValV.BegI(), sizeof(TVal)*ValV.Len()); }
01431   void AddV(const TVec<TVal>& ValV) { ResizeDelta(ValV.Len());
01432     memcpy(ValT+Vals-ValV.Len(), ValV.BegI(), sizeof(TVal)*ValV.Len()); }
01433   void AddV(TSIn& FIn) { int NVals;  FIn.Load(NVals);
01434     ResizeDelta(NVals);  FIn.LoadBf(ValT+Vals-NVals, sizeof(TVal)*NVals); }
01435 
01436   void Sort(const bool& Asc=true) {
01437     if (Asc) { TVec<TVal>::QSortCmp(BegI(), EndI(), TLss<TVal>()); }
01438     else { TVec<TVal>::QSortCmp(BegI(), EndI(), TGtr<TVal>()); }
01439   }
01440 };
01441 
01442 template<class TVal>
01443 void TPackVec<TVal>::ResizeDelta(const int& ValsToAdd) {
01444   if (ValsToAdd == 0) return;
01445   Vals += ValsToAdd;
01446   ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals);
01447   EAssert(ValT != NULL);
01448 }
01449 
01450 template<class TVal>
01451 void TPackVec<TVal>::Load(TSIn& SIn) {
01452   SIn.Load(Vals);
01453   if (Vals==0) {
01454     if (ValT != NULL) { free(ValT); }
01455     ValT = NULL; }
01456   else {
01457     ValT = (TVal *) realloc(ValT, sizeof(TVal)*Vals);
01458   }
01459   SIn.LoadBf(ValT, sizeof(TVal)*Vals);
01460 }
01461 
01462 template<class TVal>
01463 void TPackVec<TVal>::Save(TSOut& SOut) const {
01464   SOut.Save(Vals);
01465   if (Vals != 0) {
01466     SOut.SaveBf(ValT, sizeof(TVal)*Vals); }
01467 }
01468 
01469 #endif