9 template<
class TKey,
class TDat,
class THashFunc = TDefaultHashFunc<TKey> >
27 TFOut FOut(OutFNm); Load(FOut, Hash); }
31 Hash.
GetKey(k).Save(SOut); Hash[k].
Save(SOut); }
34 TFIn FIn(InFNm); Load(FIn, Hash, LoadN); }
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));
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));
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));
60 template <
class TVal, u
int16 GroupSize>
63 unsigned char BitSet [(GroupSize-1)/8 + 1];
67 static int CharBit(
const int& ValN) {
return ValN >> 3; }
68 static int ModBit(
const int& ValN) {
return 1 << (ValN&7); }
86 int MxLen()
const {
return GroupSize; }
89 void Clr(
const bool& DoDel =
true);
94 const TVal&
Offset(
const int& Pos)
const {
return Group[Pos]; }
99 const TVal&
DefVal()
const {
static TVal DefValue = TVal();
return DefValue; }
100 const TVal&
Get(
const int& ValN)
const {
104 TVal&
Set(
const int& ValN,
const TVal& Val);
105 TVal&
Set(
const int& ValN) {
109 void Del(
const int& ValN);
112 template <
class TVal, u
int16 GroupSize>
114 static const int bits_in [256] = {
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,
135 for ( ; Pos > 8; Pos -= 8 )
136 Offset += bits_in[*BitSet++];
137 return Offset + bits_in[*BitSet & ((1 << Pos)-1)];
140 template <
class TVal, u
int16 GroupSize>
149 template <
class TVal, u
int16 GroupSize>
151 SIn.
LoadBf(BitSet,
sizeof(BitSet));
153 if (Group != NULL)
delete [] Group;
154 Group =
new TVal [Buckets];
155 for (
int b = 0; b < Buckets; b++) { Group[b] = TVal(SIn); }
158 template <
class TVal, u
int16 GroupSize>
160 SOut.
SaveBf(BitSet,
sizeof(BitSet));
162 for (
int b = 0; b < Buckets; b++) { Group[b].Save(SOut); }
165 template <
class TVal, u
int16 GroupSize>
168 if (SG.
Buckets == 0 && Group != NULL) {
173 if (Group != NULL)
delete [] Group;
176 for (
int b = 0; b < SG.
Buckets; b++) { Group[b] = SG.
Group[b]; }
179 memcpy(BitSet, SG.
BitSet,
sizeof(BitSet));
184 template <
class TVal, u
int16 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;
195 template <
class TVal, u
int16 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;
205 template <
class TVal, u
int16 GroupSize>
208 for (
int i = 0; i <
sizeof(BitSet); i++) {
209 for (
int b = 0; b < 8; b++) {
211 if (Offset == 0)
return i*8 + b;
220 template <
class TVal, u
int16 GroupSize>
222 if (DoDel && Group != NULL) {
226 memset(BitSet, 0,
sizeof(BitSet));
230 template <
class TVal, u
int16 GroupSize>
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;
243 return Group[Offset];
246 template <
class TVal, u
int16 GroupSize>
249 const int Offset = PosToOffset(BitSet, ValN);
250 if (--Buckets == 0) {
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;
266 template <
class TVal, u
int16 GroupSize>
289 while (GroupI < EndI && GroupI->Empty()) {
GroupI++; } }
309 template <
class TVal, u
int16 GroupSize = 48>
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; }
337 if (
Len() > 0) {
int B = 0;
354 return sizeof(
TInt)*4 + ((GroupSize+16)/8)*
Groups() +
sizeof(TVal)*
Vals; }
356 void Clr(
const bool& DoDel =
true);
358 void Resize(
const int& NewVals);
363 TVal&
Set(
const int& ValN,
const TVal& Val);
364 TVal&
Set(
const int& ValN);
365 void Del(
const int& ValN);
371 template <
class TVal, u
int16 GroupSize>
381 template <
class TVal, u
int16 GroupSize>
386 template <
class TVal, u
int16 GroupSize>
391 template <
class TVal, u
int16 GroupSize>
394 for (
int g = 0; g < GroupV.Len(); g++) GroupV[g].Clr(
false);
402 template <
class TVal, u
int16 GroupSize>
405 if (NewVals > MxVals) {
406 const int Groups = GetGroups(NewVals);
407 GroupV.Reserve(Groups, Groups);
412 template <
class TVal, u
int16 GroupSize>
419 template <
class TVal, u
int16 GroupSize>
422 TSGroup& Group = GetGrp1(ValN);
423 const int OldVals = Group.
Len();
424 TVal& ValRef = Group.
Set(PosInGroup(ValN), Val);
425 Vals += Group.
Len() - OldVals;
429 template <
class TVal, u
int16 GroupSize>
432 TSGroup& Group = GetGrp1(ValN);
433 const int OldVals = Group.
Len();
434 TVal& ValRef = Group.
Set(PosInGroup(ValN));
435 Vals += Group.
Len() - OldVals;
439 template <
class TVal, u
int16 GroupSize>
442 TSGroup& Group = GetGrp1(ValN);
443 const int OldVals = Group.
Len();
444 Group.
Del(PosInGroup(ValN));
445 Vals += Group.
Len() - OldVals;
450 #pragma pack(push, 1) // pack class size
451 template <
class TKey,
class TDat>
464 Key = HashKeyDat.
Key;
Dat = HashKeyDat.
Dat; }
return *
this; }
467 int Hash()
const {
return Key.GetPrimHashCd(); }
473 template <
class TKey,
class TDat, u
int16 GroupSize=48>
485 int GetMinSize(
const int& CurVals,
const int& WantedVals)
const;
488 void ResizeDelta(
const int& ValsToAdd,
const int& MnWanted = 0);
489 void FindPos(
const TKey& Key,
int& Pos,
int& PosToIns)
const;
517 int AddKey(
const TKey& Key);
518 TDat&
AddDat(
const TKey& Key);
519 TDat&
AddDat(
const TKey& Key,
const TDat& Dat);
521 const TKey&
GetKey(
const int& KeyId)
const {
return Table.Get(KeyId).Key; }
523 int Pos, PosToIns;
FindPos(Key, Pos, PosToIns);
return Pos; }
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); }
529 int KeyId = Rnd.GetUniDevInt(
Reserved());
530 while (!
IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(
Reserved()); }
return KeyId; }
532 const TDat&
GetDat(
const TKey& Key)
const;
533 TDat&
GetDat(
const TKey& Key);
536 void GetKeyDat(
const int& KeyId, TKey& Key, TDat& Dat)
const;
537 bool IsKeyGetDat(
const TKey& Key, TDat& Dat)
const;
545 template <
class TKey,
class TDat, u
int16 GroupSize>
548 template <
class TKey,
class TDat, u
int16 GroupSize>
551 template <
class TKey,
class TDat, u
int16 GroupSize>
554 template <
class TKey,
class TDat, u
int16 GroupSize>
556 ExpandThresh = int(Table.Reserved() * MxOccupancy);
557 ShrinkThresh = int(Table.Reserved() * MnOccupancy);
560 template <
class TKey,
class TDat, u
int16 GroupSize>
562 int Size = MinBuckets;
563 while (Size*MxOccupancy < WantedVals || CurVals >= Size * MxOccupancy) Size *= 2;
567 template <
class TKey,
class TDat, u
int16 GroupSize>
570 const int NewSize = GetMinSize(HT.
Reserved(), MnWanted);
571 if (NewSize > Reserved()) {
572 Table.Resize(NewSize);
575 const uint BuckM1 = Reserved() - 1;
576 for (
int g = 0; g < HT.
Table.Groups(); 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) {
583 Assert(Tries < Reserved());
585 Table.Set(BuckNum, Group.
Offset(b));
590 template <
class TKey,
class TDat, u
int16 GroupSize>
594 if (MnWanted == 0) NewSize = HT.
Reserved();
595 else NewSize = GetMinSize(HT.
Reserved(), MnWanted);
596 if (NewSize > Reserved()) {
597 Table.Resize(NewSize);
600 const uint BuckM1 = Reserved() - 1;
601 for (
int g = 0; g < HT.
Table.Groups(); 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) {
608 Assert(Tries < Reserved());
610 Assert(Table.IsEmpty(BuckNum));
611 Table.Set(BuckNum, Group.
Offset(b));
617 template <
class TKey,
class TDat, u
int16 GroupSize>
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);
630 template <
class TKey,
class TDat, u
int16 GroupSize>
632 const uint BuckM1 = Reserved() - 1;
633 uint BuckNum = Key.GetPrimHashCd() & BuckM1;
636 if (Table.IsEmpty(BuckNum)) {
637 Pos = -1; PosToIns = BuckNum;
return;
639 else if (Key == Table.Get(BuckNum).Key) {
640 Pos = BuckNum; PosToIns = -1;
return;
643 BuckNum = (BuckNum + Tries) & BuckM1;
644 Assert(Tries < Reserved());
648 template <
class TKey,
class TDat, u
int16 GroupSize>
658 template <
class TKey,
class TDat, u
int16 GroupSize>
660 return Table == SHT.
Table;
663 template <
class TKey,
class TDat, u
int16 GroupSize>
665 return Table < SHT.
Table;
668 template <
class TKey,
class TDat, u
int16 GroupSize>
672 Table.Swap(HT.
Table);
675 template <
class TKey,
class TDat, u
int16 GroupSize>
678 int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
679 if (Pos != -1) {
return Pos; }
686 template <
class TKey,
class TDat, u
int16 GroupSize>
689 int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
690 if (PosToIns != -1) {
692 }
else {
return Table.Set(Pos).Dat; }
695 template <
class TKey,
class TDat, u
int16 GroupSize>
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; }
704 template <
class TKey,
class TDat, u
int16 GroupSize>
707 FindPos(Key, Pos, PosToIns);
709 return Table.Get(Pos).Dat;
712 template <
class TKey,
class TDat, u
int16 GroupSize>
715 FindPos(Key, Pos, PosToIns);
717 return Table.Set(Pos).Dat;
720 template <
class TKey,
class TDat, u
int16 GroupSize>
728 template <
class TKey,
class TDat, u
int16 GroupSize>
731 if (IsKey(Key, KeyId)) {
732 Dat=Table.Get(KeyId).Dat;
734 }
else {
return false; }
737 template <
class TKey,
class TDat, u
int16 GroupSize>
740 for (
TIter i = BegI(); i < EndI(); i++) {
745 template <
class TKey,
class TDat, u
int16 GroupSize>
748 for (
TIter i = BegI(); i < EndI(); i++) {
753 template <
class TKey,
class TDat, u
int16 GroupSize>
755 KeyDatPrV.Gen(Len(), 0);
756 for (
TIter i = BegI(); i < EndI(); i++) {
761 template <
class TKey,
class TDat, u
int16 GroupSize>
763 DatKeyPrV.Gen(Len(), 0);
764 for (
TIter i = BegI(); i < EndI(); i++) {
771 template <
class TKey, u
int16 GroupSize=48>
782 int GetMinSize(
const int& CurVals,
const int& WantedVals)
const;
785 void ResizeDelta(
const int& ValsToAdd,
const int& MnWanted = 0);
786 void FindPos(
const TKey& Key,
int& Pos,
int& PosToIns)
const;
814 int AddKey(
const TKey& Key);
816 int GetKeyId(
const TKey& Key)
const {
int Pos, PosToIns;
817 FindPos(Key, Pos, PosToIns);
return Pos; }
819 bool IsKey(
const TKey& Key,
int& KeyId)
const {
820 KeyId =
GetKeyId(Key);
return KeyId != -1; }
823 int KeyId = Rnd.GetUniDevInt(
Reserved());
824 while (!
IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(
Reserved()); }
return KeyId; }
829 template <
class TKey, u
int16 GroupSize>
832 template <
class TKey, u
int16 GroupSize>
835 template <
class TKey, u
int16 GroupSize>
838 template <
class TKey, u
int16 GroupSize>
840 ExpandThresh = int(Table.Reserved() * MxOccupancy);
841 ShrinkThresh = int(Table.Reserved() * MnOccupancy);
844 template <
class TKey, u
int16 GroupSize>
846 int Size = MinBuckets;
847 while (Size*MxOccupancy <= WantedVals || CurVals > Size * MxOccupancy) Size *= 2;
851 template <
class TKey, u
int16 GroupSize>
854 const int NewSize = GetMinSize(SSet.
Reserved(), MnWanted);
855 if (NewSize > Reserved()) {
856 Table.Resize(NewSize);
859 const uint BuckM1 = Reserved() - 1;
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) {
867 Assert(Tries < Reserved());
869 Table.Set(BuckNum, Group.Offset(b));
874 template <
class TKey, u
int16 GroupSize>
878 if (MnWanted == 0) NewSize = SSet.
Reserved();
879 else NewSize = GetMinSize(SSet.
Reserved(), MnWanted);
880 if (NewSize > Reserved()) {
881 Table.Resize(NewSize);
884 const uint BuckM1 = Reserved() - 1;
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) {
892 Assert(Tries < Reserved());
894 Assert(Table.IsEmpty(BuckNum));
895 Table.Set(BuckNum, Group.Offset(b));
901 template <
class TKey, u
int16 GroupSize>
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);
914 template <
class TKey, u
int16 GroupSize>
916 const uint BuckM1 = Reserved() - 1;
917 uint BuckNum = Key.GetPrimHashCd() & BuckM1;
920 if (Table.IsEmpty(BuckNum)) {
921 Pos = -1; PosToIns = BuckNum;
return;
923 else if (Key == Table.Get(BuckNum)) {
924 Pos = BuckNum; PosToIns = -1;
return;
927 BuckNum = (BuckNum + Tries) & BuckM1;
928 Assert(Tries < Reserved());
932 template <
class TKey, u
int16 GroupSize>
942 template <
class TKey, u
int16 GroupSize>
944 return Table == SSet.
Table;
947 template <
class TKey, u
int16 GroupSize>
949 return Table < SSet.
Table;
952 template <
class TKey, u
int16 GroupSize>
956 Table.Swap(SSet.
Table);
959 template <
class TKey, u
int16 GroupSize>
962 int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
963 if (Pos != -1) {
return Pos; }
965 Table.Set(PosToIns, Key);
970 template <
class TKey, u
int16 GroupSize>
973 for (
TIter I = BegI(); I < EndI(); I++) {
979 #pragma pack(push, 1) // pack class size
980 template <
class TKey>
989 THashSetKey(
const int& _Next,
const int& _HashCd,
const TKey& _Key):
1008 template <
class TKey>
1046 template <
class TKey,
class THashFunc = TDefaultHashFunc<TKey> >
1072 THashSet(
const int& ExpectVals,
const bool& _AutoSizeP=
false);
1088 for (
int KeyN=0; KeyN<KeyV.
Len(); KeyN++) {
1089 AddKey(KeyV[KeyN].Key); }}
1115 void Gen(
const int& ExpectVals) {
1119 void Clr(
const bool& DoDel=
true,
const int& NoDelLim=-1);
1128 int AddKey(
const TKey& Key);
1131 void DelKey(
const TKey& Key);
1133 int KeyId;
if (
IsKey(Key, KeyId)) {
DelKeyId(KeyId);
return true;}
return false;}
1136 for (
int KeyIdN=0; KeyIdN<KeyIdV.
Len(); KeyIdN++) {
DelKeyId(KeyIdV[KeyIdN]); }}
1143 int GetKeyId(
const TKey& Key)
const;
1149 bool IsKey(
const TKey& Key,
int& KeyId)
const {
1150 KeyId=
GetKeyId(Key);
return KeyId!=-1; }
1152 return (0<=KeyId)&&(KeyId<
KeyV.Len())&&(
KeyV[KeyId].HashCd!=-1); }
1170 static THashSet<TKey> GetSet(
const TKey& Key1,
const TKey& Key2,
const TKey& Key3,
const TKey& Key4,
const TKey& Key5){
1172 static THashSet<TKey> GetSet(
const TKey& Key1,
const TKey& Key2,
const TKey& Key3,
const TKey& Key4,
const TKey& Key5,
const TKey& Key6){
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){
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){
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){
1183 template <
class TKey,
class THashFunc>
1188 h = len >> 1; m = f + h;
1189 if (*m < Val) { f = m; f++; len = len - h - 1; }
1192 return f == l ? *(l - 1) : *f;
1195 template <
class TKey,
class THashFunc>
1198 if (PortV.Len()==0) {PortV.Gen(17); }
1199 else if (AutoSizeP&&(KeyV.Len()>2*PortV.Len())) {
1200 PortV.Gen(GetNextPrime(PortV.Len()+1));
1204 PortV.PutAll(
TInt(-1));
1206 for (
int KeyId=0; KeyId<KeyV.Len(); KeyId++) {
1209 int PortN=abs(THashFunc::GetPrimHashCd(SetKey.
Key)%PortV.Len());
1210 SetKey.
Next=PortV[PortN];
1216 template <
class TKey,
class THashFunc>
1218 PortV(GetNextPrime(ExpectVals/2+1)), KeyV(ExpectVals, 0),
1219 AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0) {
1223 template <
class TKey,
class THashFunc>
1225 PortV(GetNextPrime(_KeyV.Len()/2+1)), KeyV(_KeyV.Len(), 0),
1226 AutoSizeP(false), FFreeKeyId(-1), FreeKeys(0) {
1228 for (
int i = 0; i < _KeyV.
Len(); i++) {
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; }
1242 template <
class TKey,
class THashFunc>
1245 PortV.Clr(); KeyV.Clr();
1247 PortV.PutAll(
TInt(-1));
1248 KeyV.Clr(DoDel, NoDelLim);
1250 FFreeKeyId=
TInt(-1); FreeKeys=
TInt(0);
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));
1259 int KeyId=PortV[PortN];
1261 while ((KeyId!=-1) &&
1262 !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1263 PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
1266 if (FFreeKeyId==-1) {
1267 KeyId=KeyV.Add(
TSetKey(-1, HashCd, Key));
1269 KeyId=FFreeKeyId; FFreeKeyId=KeyV[FFreeKeyId].Next; FreeKeys--;
1270 KeyV[KeyId].Next = -1;
1271 KeyV[KeyId].HashCd = HashCd;
1272 KeyV[KeyId].Key = Key;
1274 if (PrevKeyId==-1) {
1277 KeyV[PrevKeyId].Next=KeyId;
1283 template <
class TKey,
class THashFunc>
1285 for (
int i = 0; i < KeyV.
Len(); i++) { AddKey(KeyV[i]); }
1288 template <
class TKey,
class THashFunc>
1291 int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1292 int HashCd=abs(THashFunc::GetSecHashCd(Key));
1294 int KeyId=PortV[PortN];
1296 while ((KeyId!=-1) &&
1297 !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1298 PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
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();
1308 template <
class TKey,
class THashFunc>
1311 int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1312 int HashCd=abs(THashFunc::GetSecHashCd(Key));
1314 int KeyId=PortV[PortN];
1316 while ((KeyId!=-1) &&
1317 !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1318 PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
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);
1327 template <
class TKey,
class THashFunc>
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];
1334 while ((KeyId!=-1) &&
1335 !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1336 KeyId=KeyV[KeyId].Next; }
1340 template <
class TKey,
class THashFunc>
1342 do {KeyId++; }
while ((KeyId<KeyV.Len())&&(KeyV[KeyId].HashCd==-1));
1343 return KeyId<KeyV.Len();
1346 template <
class TKey,
class THashFunc>
1349 int KeyId=FFirstKeyId();
1350 while (FNextKeyId(KeyId)) {
1351 KeyV.
Add(GetKey(KeyId)); }
1354 template <
class TKey,
class THashFunc>
1357 PortV.Swap(Set.
PortV);
1358 KeyV.Swap(Set.
KeyV);
1365 template <
class TKey,
class THashFunc>
1367 if (!IsKeyIdEqKeyN()) {
1369 int KeyId=FFirstKeyId();
1370 while (FNextKeyId(KeyId)) {
1371 Set.AddKey(GetKey(KeyId));
1392 template<
class TVal>
1416 memcpy(
ValT, Vec.
ValT,
sizeof(TVal)*
Vals);
return *
this; }
1418 memcpy(
ValT, Vec.
ValT,
sizeof(TVal)*
Vals);
return *
this; }
1448 template<
class TVal>
1450 if (ValsToAdd == 0)
return;
1452 ValT = (TVal *) realloc(ValT,
sizeof(TVal)*Vals);
1456 template<
class TVal>
1460 if (ValT != NULL) { free(ValT); }
1463 ValT = (TVal *) realloc(ValT,
sizeof(TVal)*Vals);
1465 SIn.
LoadBf(ValT,
sizeof(TVal)*Vals);
1468 template<
class TVal>
1472 SOut.
SaveBf(ValT,
sizeof(TVal)*Vals); }
void Clr(const bool &DoDel=true, const int &NoDelLim=-1)
bool operator==(const THashSetKeyI &SetKeyI) const
int GetMinSize(const int &CurVals, const int &WantedVals) const
void Del(const int &ValN)
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3)
static void LoadHash(const TStr &InFNm, THash< TKey, TDat, THashFunc > &Hash, const int &LoadN=-1)
void GetKeyV(TVec< TKey > &KeyV) const
bool IsKeyId(const int &KeyId) const
void CopyFrom(const TSparseSet &SSet, const int &MnWanted)
TSparseTableI< TVal, GroupSize > TIter
const TKey & GetKey() const
static int GetGroups(const int &Vals)
#define IAssertR(Cond, Reason)
TSparseTable< TKey, GroupSize > Table
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)
THashSetKeyI & operator++(int)
void GetKeyV(TVec< TKey > &KeyV) const
bool operator==(const TSparseGroup &SG) const
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5, const TKey &Key6)
TSGroup & GetGrp1(const int &ValN)
void Swap(TSparseHash &HT)
void SaveXml(TSOut &SOut, const TStr &Nm) const
int GroupNum(const int &ValN) const
int PosToOffset(int Pos) const
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
const TKey & operator()() const
static void LoadDatV(TSIn &SIn, TVec< TDat > &DatV, int LoadN=-1)
void GetDatKeyPrV(TVec< TPair< TDat, TKey > > &DatKeyPrV) const
void DelKeyId(const int &KeyId)
TSparseTable< TKey, GroupSize >::TIter TIter
TVal & operator()() const
bool IsEnd() const
Returns true, if the iterator is pointing to the past-end element.
bool IsEmpty(const int &ValN) const
TIter GetI(const int &KeyId) const
const TVal & Offset(const int &Pos) const
const TSGroup & GetGroup(const int &GroupN) const
const TSGroup & GetGrp1(const int &ValN) const
unsigned char BitSet[(GroupSize-1)/8+1]
TSparseTableI & operator++(int)
void AddKeyV(const TVec< TKey > &KeyV)
TPackVec(const TPackVec &Vec)
static const int MinBuckets
void Sort(const bool &Asc=true)
bool operator<(const TSparseGroup &SG) const
void Save(TSOut &SOut) const
bool operator==(const TSHashKeyDat &HashKeyDat) const
bool operator<(const TSparseTable &ST) const
bool IsKey(const TKey &Key, int &KeyId) const
int GetKeyId(const TKey &Key) const
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
void Save(TSOut &SOut) const
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
void Clr(const bool &DoDel=true)
const TVal & operator[](const int ValN) const
TPackVec< TVal > & operator=(const TPackVec< TVal > &Vec)
bool operator==(const THashSet &Set) const
const TVal & Last() const
TSizeTy Len() const
Returns the number of elements in the vector.
const TKey & GetKey(const int &KeyId) const
void BMSet(const int &ValN)
void Save(TSOut &SOut) const
const TVal & DefVal() const
static const unsigned int HashPrimeT[HashPrimes]
int PosInGroup(const int &ValN) const
TSparseTable(const TSparseTable &ST)
void Save(TSOut &SOut) const
void GetKeyV(TVec< TKey > &KeyV) const
void Gen(const int &ExpectVals)
TKey & operator[](const int &KeyId)
void Clr(const bool &DoDel=true)
static const float MnOccupancy
bool operator==(const TSparseTable &ST) const
void Clr(const bool &DoDel=true)
void Save(TSOut &SOut) const
const TKey & GetKey(const int &KeyId) const
static int ModBit(const int &ValN)
int AddKey(const TKey &Key)
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)
THashSetKey(const int &_Next, const int &_HashCd, const TKey &_Key)
static void LoadHash(TSIn &SIn, THash< TKey, TDat, THashFunc > &Hash, int LoadN=-1)
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5)
const TKey * operator->() const
static const int MinBuckets
void Reserve(const int &MxVals)
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
TIter GetI(const int &ValN) const
bool IsKey(const TKey &Key) const
bool operator==(const TSparseSet &SSet) const
static int PosToOffset(const unsigned char *BitSet, int Pos)
const TKey & GetKey(const int &KeyId) const
void Swap(TSparseSet &SSet)
TSparseTable(const int &MaxVals=0)
TSparseTableI(const TSparseTableI &STI)
const TKey & GetKey() const
void Reserve(const int NewVals)
TKeyDatFl(const TStr &FNm)
TIter GetI(const TKey &Key) const
const TVal & Get(const int &ValN) const
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
void Save(TSOut &SOut) const
bool BMTest(const int &ValN) const
static const float MnOccupancy
THashSet(const THashSet &Set)
TVal & Set(const int &ValN)
TSGroup & GetGroup(const int &GroupN)
TPackVec(const int &_Vals)
void MarkDelKeyId(const int &KeyId)
int GetKeyId(const TKey &Key) const
const TDat & GetDat(const TKey &Key) const
int GetRndKeyId(TRnd &Rnd=TInt::Rnd) const
TSparseTable< THashKeyDat, GroupSize >::TIter TIter
TSparseTable< THashKeyDat, GroupSize >::TSGroup TSGroup
void BMClear(const int &ValN)
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
TSparseTableI(const TGroupVI &BegIter, const TGroupVI &CurIter, const TGroupVI &EndIter, const int &Offset=0)
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
bool operator==(const TSparseTableI &STI) const
bool operator<(const THashSetKeyI &SetKeyI) const
void GetDatV(TVec< TDat > &DatV) const
void Gen(const int &ExpectVals)
TSparseGroup & operator=(const TSparseGroup &SG)
void DelKey(const TKey &Key)
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
bool IsKeyIdEqKeyN() const
void SaveXml(TSOut &SOut, const TStr &Nm)
static bool GetBit(const int &BitN, const uchar &Val)
THashSet< TUChIntPr > TUChIntPrSet
int AddKey(const TKey &Key)
const TVal & operator[](const int &ValN) const
void CopyFrom(const TSparseHash &HT, const int &MnWanted)
TSHashKeyDat & operator=(const TSHashKeyDat &HashKeyDat)
THashSetKeyI & operator--(int)
int GetRndKeyId(TRnd &Rnd=TInt::Rnd) const
::TSize GetMemUsed() const
void Reserve(const int &MxVals)
THashSetKeyI(const TSetKey *_KeyI, const TSetKey *_EndI)
THashSetKey< TKey > TSetKey
bool FNextKeyId(int &KeyId) const
TIter GetI(const int &ValN) const
TVal * operator->() const
void Save(TSOut &SOut) const
void AddV(const TPackVec< TVal > &ValV)
bool IsKey(const TKey &Key) const
TVal & Set(const int &ValN, const TVal &Val)
bool IsEmpty() const
Returns true, if the iterator is empty - has not been initialized.
THashSet< TIntPr > TIntPrSet
const TDat & GetDat() const
void MarkDelKey(const TKey &Key)
int AddKey(const TKey &Key)
bool operator<(const TSparseTableI &STI) const
TSparseTable< THashKeyDat, GroupSize > Table
bool IsKeyId(const int &KeyId) const
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4)
static const float MxOccupancy
void MoveFrom(TSparseSet &SSet, const int &MnWanted)
bool operator<(const TSparseHash &SHT) const
void SaveBf(const void *Bf, const TSize &BfL)
void Del(const int &ValN)
void MoveFrom(TSparseHash &HT, const int &MnWanted)
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
const TDat & GetDatKeyId(const int &KeyId) const
bool operator<(const TSparseSet &SSet) const
::TSize GetMemUsed() const
int GetRndKeyId(TRnd &Rnd) const
const TKey & operator[](const int &KeyId) const
void Save(const bool &Bool)
THashSet & operator=(const THashSet &Set)
int GetKeyId(const TKey &Key) const
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
TVal * TIter
Random access iterator to TVal.
THashSet< TUInt64 > TUInt64Set
bool IsKey(const TKey &Key, int &KeyId) const
uint GetNextPrime(const uint &Val) const
TVal & Set(const int &ValN, const TVal &Val)
TSHashKeyDat(const TKey &_Key, const TDat &_Dat)
const TVal & Get(const int &ValN) const
const TKey & operator*() const
void Clr(const bool &DoDel=true)
TSparseGroup< TVal, GroupSize > TSGroup
THashSet< TUChUInt64Pr > TUChUInt64PrSet
bool IsKeyId(const int &KeyId) const
TDat & GetDatKeyId(const int &KeyId)
const TSetKey & GetSetKey(const int &KeyId) const
int GetMinSize(const int &CurVals, const int &WantedVals) const
THashSetKeyI(const THashSetKeyI &_SetKeyI)
TSparseTable< TKey, GroupSize >::TSGroup TSGroup
TSHashKeyDat< TKey, TDat > THashKeyDat
void ResizeDelta(const int &ValsToAdd=1)
void Save(TSOut &SOut) const
void Save(TSOut &SOut) const
void Save(TSOut &SOut) const
static THashSet< TKey > GetSet(const TKey &Key1)
void Add(const TVal &Val)
static void LoadKeyV(TSIn &SIn, TVec< TKey > &KeyV, int LoadN=-1)
void AddV(const TVec< TVal > &ValV)
TDat & AddDat(const TKey &Key)
TSparseHash(const int &WantedVals=0)
TVal & Offset(const int &Pos)
bool FNextKeyId(int &KeyId) const
TVec< TValGroup >::TIter TGroupVI
::TSize GetMemUsed() const
static int CharBit(const int &ValN)
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
static void QSortCmp(TIter BI, TIter EI, const TCmp &Cmp)
Quick sorts the values between positions BI...EI under the comparator Cmp.
TSparseTableI & operator--(int)
void Gen(const int &_Vals)
void LoadBf(const void *Bf, const TSize &BfL)
THashSetKey< TKey > TSetKey
void Swap(TSparseTable &ST)
static THashSet< TKey > GetSet(const TKey &Key1, const TKey &Key2)
TSparseTableI & operator=(const TSparseTableI &STI)
bool IsKey(const TKey &Key) const
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)
virtual TStr GetSNm() const
void DelKeyIdV(const TIntV &KeyIdV)
bool operator<(const TSHashKeyDat &HashKeyDat) const
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
THashSetKeyI< TKey > TIter
TSparseGroup< TVal, GroupSize > TValGroup
bool IsEmpty(const int &ValN) const
void Save(TSOut &SOut) const
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
TSparseHash & operator=(const TSparseHash &SHT)
TSetKey & GetSetKey(const int &KeyId)
static const float MxOccupancy
int GetUniDevInt(const int &Range=0)
static void Save(const TStr &OutFNm, const THash< TKey, TDat, THashFunc > &Hash)
TSparseTable & operator=(const TSparseTable &ST)
::TSize GetMemUsed() const
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
int GetReservedKeyIds() const
THashSetKeyI & operator=(const THashSetKeyI &SetKeyI)
TDat & AddDat(const TKey &Key)
void Resize(const int &NewVals)
TSparseSet & operator=(const TSparseSet &SSet)
bool IsKey(const TKey &Key, int &KeyId) const
int OffsetToPos(int Offset) const
bool DelIfKey(const TKey &Key)
TSHashKeyDat(const TKey &_Key)
TVal * ValT
Pointer to the memory where the elements of the vector are stored.
const TKey & GetKey(const int &KeyId) const
static void Save(TSOut &SOut, const THash< TKey, TDat, THashFunc > &Hash)
TSparseSet(const int &WantedVals=0)
bool operator==(const TSparseHash &SHT) const
void Swap(TRec &Rec1, TRec &Rec2)
Vector is a sequence TVal objects representing an array that can change in size.
THashSetKey & operator=(const THashSetKey &SetKey)
TSHashKeyDat(const TSHashKeyDat &HashKeyDat)
void Save(TSOut &SOut) const
TIter GetI(const TKey &Key) const