SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
THashSet< TKey, THashFunc > Class Template Reference

#include <shash.h>

Public Types

typedef THashSetKeyI< TKey > TIter
 

Public Member Functions

 THashSet ()
 
 THashSet (const THashSet &Set)
 
 THashSet (const int &ExpectVals, const bool &_AutoSizeP=false)
 
 THashSet (const TVec< TKey > &KeyV)
 
 THashSet (TSIn &SIn)
 
void Load (TSIn &SIn)
 
void Save (TSOut &SOut) const
 
void LoadXml (const PXmlTok &XmlTok, const TStr &Nm="")
 
void SaveXml (TSOut &SOut, const TStr &Nm)
 
THashSetoperator= (const THashSet &Set)
 
bool operator== (const THashSet &Set) const
 
const TKey & operator[] (const int &KeyId) const
 
TKey & operator[] (const int &KeyId)
 
::TSize GetMemUsed () const
 
TIter BegI () const
 
TIter EndI () const
 
TIter GetI (const TKey &Key) const
 
void Gen (const int &ExpectVals)
 
void Clr (const bool &DoDel=true, const int &NoDelLim=-1)
 
bool Empty () const
 
int Len () const
 
int GetPorts () const
 
bool IsAutoSize () const
 
int GetMxKeyIds () const
 
int GetReservedKeyIds () const
 
bool IsKeyIdEqKeyN () const
 
int AddKey (const TKey &Key)
 
void AddKeyV (const TVec< TKey > &KeyV)
 
void DelKey (const TKey &Key)
 
bool DelIfKey (const TKey &Key)
 
void DelKeyId (const int &KeyId)
 
void DelKeyIdV (const TIntV &KeyIdV)
 
void MarkDelKey (const TKey &Key)
 
void MarkDelKeyId (const int &KeyId)
 
const TKey & GetKey (const int &KeyId) const
 
int GetKeyId (const TKey &Key) const
 
int GetRndKeyId (TRnd &Rnd) const
 
bool IsKey (const TKey &Key) const
 
bool IsKey (const TKey &Key, int &KeyId) const
 
bool IsKeyId (const int &KeyId) const
 
int FFirstKeyId () const
 
bool FNextKeyId (int &KeyId) const
 
void GetKeyV (TVec< TKey > &KeyV) const
 
void Swap (THashSet &Set)
 
void Defrag ()
 
void Pack ()
 

Static Public Member Functions

static THashSet< TKey > GetSet (const TKey &Key1)
 
static THashSet< TKey > GetSet (const TKey &Key1, const TKey &Key2)
 
static THashSet< TKey > GetSet (const TKey &Key1, const TKey &Key2, const TKey &Key3)
 
static THashSet< TKey > GetSet (const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4)
 
static THashSet< TKey > GetSet (const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5)
 
static THashSet< TKey > GetSet (const TKey &Key1, const TKey &Key2, const TKey &Key3, const TKey &Key4, const TKey &Key5, const TKey &Key6)
 
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)
 
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)
 
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)
 

Private Types

typedef THashSetKey< TKey > TSetKey
 

Private Member Functions

TSetKeyGetSetKey (const int &KeyId)
 
const TSetKeyGetSetKey (const int &KeyId) const
 
uint GetNextPrime (const uint &Val) const
 
void Resize ()
 

Private Attributes

TIntV PortV
 
TVec< TSetKeyKeyV
 
TBool AutoSizeP
 
TInt FFreeKeyId
 
TInt FreeKeys
 

Detailed Description

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
class THashSet< TKey, THashFunc >

Definition at line 1047 of file shash.h.

Member Typedef Documentation

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
typedef THashSetKeyI<TKey> THashSet< TKey, THashFunc >::TIter

Definition at line 1049 of file shash.h.

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
typedef THashSetKey<TKey> THashSet< TKey, THashFunc >::TSetKey
private

Definition at line 1051 of file shash.h.

Constructor & Destructor Documentation

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
THashSet< TKey, THashFunc >::THashSet ( )
inline

Definition at line 1066 of file shash.h.

1066  :
1067  PortV(), KeyV(),
1068  AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0) { }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
THashSet< TKey, THashFunc >::THashSet ( const THashSet< TKey, THashFunc > &  Set)
inline

Definition at line 1069 of file shash.h.

1069  :
1070  PortV(Set.PortV), KeyV(Set.KeyV), AutoSizeP(Set.AutoSizeP),
1071  FFreeKeyId(Set.FFreeKeyId), FreeKeys(Set.FreeKeys) { }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052
template<class TKey , class THashFunc >
THashSet< TKey, THashFunc >::THashSet ( const int &  ExpectVals,
const bool &  _AutoSizeP = false 
)

Definition at line 1217 of file shash.h.

1217  :
1218  PortV(GetNextPrime(ExpectVals/2+1)), KeyV(ExpectVals, 0),
1219  AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0) {
1220  PortV.PutAll(TInt(-1));
1221 }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
uint GetNextPrime(const uint &Val) const
Definition: shash.h:1184
template<class TKey, class THashFunc >
THashSet< TKey, THashFunc >::THashSet ( const TVec< TKey > &  KeyV)
explicit

Definition at line 1224 of file shash.h.

1224  :
1225  PortV(GetNextPrime(_KeyV.Len()/2+1)), KeyV(_KeyV.Len(), 0),
1226  AutoSizeP(false), FFreeKeyId(-1), FreeKeys(0) {
1227  PortV.PutAll(TInt(-1));
1228  for (int i = 0; i < _KeyV.Len(); i++) {
1229  AddKey(_KeyV[i]);
1230  }
1231 }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TBool AutoSizeP
Definition: shash.h:1054
int AddKey(const TKey &Key)
Definition: shash.h:1254
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
uint GetNextPrime(const uint &Val) const
Definition: shash.h:1184
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
THashSet< TKey, THashFunc >::THashSet ( TSIn SIn)
inlineexplicit

Definition at line 1074 of file shash.h.

1074  :
1075  PortV(SIn), KeyV(SIn),
1076  AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn) {
1077  SIn.LoadCs(); }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
void LoadCs()
Definition: fl.cpp:28
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052

Member Function Documentation

template<class TKey, class THashFunc >
int THashSet< TKey, THashFunc >::AddKey ( const TKey &  Key)

Definition at line 1254 of file shash.h.

1254  {
1255  if ((KeyV.Len()>2*PortV.Len())||PortV.Empty()) {Resize(); }
1256  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1257  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1258  int PrevKeyId=-1;
1259  int KeyId=PortV[PortN];
1260 
1261  while ((KeyId!=-1) &&
1262  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1263  PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
1264 
1265  if (KeyId==-1) {
1266  if (FFreeKeyId==-1) {
1267  KeyId=KeyV.Add(TSetKey(-1, HashCd, Key));
1268  } else {
1269  KeyId=FFreeKeyId; FFreeKeyId=KeyV[FFreeKeyId].Next; FreeKeys--;
1270  KeyV[KeyId].Next = -1;
1271  KeyV[KeyId].HashCd = HashCd;
1272  KeyV[KeyId].Key = Key;
1273  }
1274  if (PrevKeyId==-1) {
1275  PortV[PortN]=KeyId;
1276  } else {
1277  KeyV[PrevKeyId].Next=KeyId;
1278  }
1279  }
1280  return KeyId;
1281 }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TInt FreeKeys
Definition: shash.h:1055
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
void Resize()
Definition: shash.h:1196
THashSetKey< TKey > TSetKey
Definition: shash.h:1051
TIntV PortV
Definition: shash.h:1052
template<class TKey, class THashFunc >
void THashSet< TKey, THashFunc >::AddKeyV ( const TVec< TKey > &  KeyV)

Definition at line 1284 of file shash.h.

1284  {
1285  for (int i = 0; i < KeyV.Len(); i++) { AddKey(KeyV[i]); }
1286 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
int AddKey(const TKey &Key)
Definition: shash.h:1254
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TIter THashSet< TKey, THashFunc >::BegI ( ) const
inline

Definition at line 1105 of file shash.h.

1105  {
1106  if (Len()>0) {
1107  if (IsKeyIdEqKeyN()) { return TIter(KeyV.BegI(), KeyV.EndI()); }
1108  int FKeyId=-1; FNextKeyId(FKeyId);
1109  return TIter(KeyV.BegI()+FKeyId, KeyV.EndI()); }
1110  return TIter(KeyV.EndI(), KeyV.EndI());
1111  }
TVec< TSetKey > KeyV
Definition: shash.h:1053
bool IsKeyIdEqKeyN() const
Definition: shash.h:1126
int Len() const
Definition: shash.h:1121
bool FNextKeyId(int &KeyId) const
Definition: shash.h:1341
THashSetKeyI< TKey > TIter
Definition: shash.h:1049
template<class TKey , class THashFunc >
void THashSet< TKey, THashFunc >::Clr ( const bool &  DoDel = true,
const int &  NoDelLim = -1 
)

Definition at line 1243 of file shash.h.

1243  {
1244  if (DoDel) {
1245  PortV.Clr(); KeyV.Clr();
1246  } else {
1247  PortV.PutAll(TInt(-1));
1248  KeyV.Clr(DoDel, NoDelLim);
1249  }
1250  FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
1251 }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
template<class TKey , class THashFunc >
void THashSet< TKey, THashFunc >::Defrag ( )

Definition at line 1366 of file shash.h.

1366  {
1367  if (!IsKeyIdEqKeyN()) {
1368  THashSet<TKey> Set(PortV.Len());
1369  int KeyId=FFirstKeyId();
1370  while (FNextKeyId(KeyId)) {
1371  Set.AddKey(GetKey(KeyId));
1372  }
1373  Pack();
1374  operator=(Set);
1376  }
1377 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
bool IsKeyIdEqKeyN() const
Definition: shash.h:1126
TIntV PortV
Definition: shash.h:1052
THashSet & operator=(const THashSet &Set)
Definition: shash.h:1093
bool FNextKeyId(int &KeyId) const
Definition: shash.h:1341
void Pack()
Definition: shash.h:1160
int FFirstKeyId() const
Definition: shash.h:1154
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
bool THashSet< TKey, THashFunc >::DelIfKey ( const TKey &  Key)
inline

Definition at line 1132 of file shash.h.

1132  {
1133  int KeyId; if (IsKey(Key, KeyId)) {DelKeyId(KeyId); return true;} return false;}
void DelKeyId(const int &KeyId)
Definition: shash.h:1134
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
template<class TKey, class THashFunc >
void THashSet< TKey, THashFunc >::DelKey ( const TKey &  Key)

Definition at line 1289 of file shash.h.

1289  {
1290  IAssert(!PortV.Empty());
1291  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1292  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1293  int PrevKeyId=-1;
1294  int KeyId=PortV[PortN];
1295 
1296  while ((KeyId!=-1) &&
1297  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1298  PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
1299 
1300  IAssertR(KeyId!=-1, Key.GetStr());
1301  if (PrevKeyId==-1) {PortV[PortN]=KeyV[KeyId].Next; }
1302  else {KeyV[PrevKeyId].Next=KeyV[KeyId].Next; }
1303  KeyV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
1304  KeyV[KeyId].HashCd=TInt(-1);
1305  KeyV[KeyId].Key=TKey();
1306 }
#define IAssert(Cond)
Definition: bd.h:262
TInt FFreeKeyId
Definition: shash.h:1055
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec< TSetKey > KeyV
Definition: shash.h:1053
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TInt FreeKeys
Definition: shash.h:1055
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::DelKeyId ( const int &  KeyId)
inline

Definition at line 1134 of file shash.h.

1134 {DelKey(GetKey(KeyId)); }
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
void DelKey(const TKey &Key)
Definition: shash.h:1289
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::DelKeyIdV ( const TIntV KeyIdV)
inline

Definition at line 1135 of file shash.h.

1135  {
1136  for (int KeyIdN=0; KeyIdN<KeyIdV.Len(); KeyIdN++) {DelKeyId(KeyIdV[KeyIdN]); }}
void DelKeyId(const int &KeyId)
Definition: shash.h:1134
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
bool THashSet< TKey, THashFunc >::Empty ( ) const
inline

Definition at line 1120 of file shash.h.

1120 {return Len()==0; }
int Len() const
Definition: shash.h:1121
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TIter THashSet< TKey, THashFunc >::EndI ( ) const
inline

Definition at line 1112 of file shash.h.

1112 {return TIter(KeyV.EndI(), KeyV.EndI()); }
TVec< TSetKey > KeyV
Definition: shash.h:1053
THashSetKeyI< TKey > TIter
Definition: shash.h:1049
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
int THashSet< TKey, THashFunc >::FFirstKeyId ( ) const
inline

Definition at line 1154 of file shash.h.

1154 {return 0-1; }
template<class TKey , class THashFunc >
bool THashSet< TKey, THashFunc >::FNextKeyId ( int &  KeyId) const

Definition at line 1341 of file shash.h.

1341  {
1342  do {KeyId++; } while ((KeyId<KeyV.Len())&&(KeyV[KeyId].HashCd==-1));
1343  return KeyId<KeyV.Len();
1344 }
TVec< TSetKey > KeyV
Definition: shash.h:1053
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::Gen ( const int &  ExpectVals)
inline

Definition at line 1115 of file shash.h.

1115  {
1116  PortV.Gen(GetNextPrime(ExpectVals/2)); KeyV.Gen(ExpectVals, 0);
1117  FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1)); }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
uint GetNextPrime(const uint &Val) const
Definition: shash.h:1184
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TIter THashSet< TKey, THashFunc >::GetI ( const TKey &  Key) const
inline

Definition at line 1113 of file shash.h.

1113 {return TIter(&KeyV[GetKeyId(Key)], KeyV.EndI()); }
TVec< TSetKey > KeyV
Definition: shash.h:1053
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
THashSetKeyI< TKey > TIter
Definition: shash.h:1049
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
const TKey& THashSet< TKey, THashFunc >::GetKey ( const int &  KeyId) const
inline

Definition at line 1141 of file shash.h.

1141  {
1142  return GetSetKey(KeyId).Key; }
TKey Key
Definition: shash.h:985
TSetKey & GetSetKey(const int &KeyId)
Definition: shash.h:1057
template<class TKey, class THashFunc >
int THashSet< TKey, THashFunc >::GetKeyId ( const TKey &  Key) const

Definition at line 1328 of file shash.h.

1328  {
1329  if (PortV.Empty()) {return -1; }
1330  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1331  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1332  int KeyId=PortV[PortN];
1333 
1334  while ((KeyId!=-1) &&
1335  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1336  KeyId=KeyV[KeyId].Next; }
1337  return KeyId;
1338 }
TVec< TSetKey > KeyV
Definition: shash.h:1053
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TIntV PortV
Definition: shash.h:1052
template<class TKey, class THashFunc >
void THashSet< TKey, THashFunc >::GetKeyV ( TVec< TKey > &  KeyV) const

Definition at line 1347 of file shash.h.

1347  {
1348  KeyV.Clr();
1349  int KeyId=FFirstKeyId();
1350  while (FNextKeyId(KeyId)) {
1351  KeyV.Add(GetKey(KeyId)); }
1352 }
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
bool FNextKeyId(int &KeyId) const
Definition: shash.h:1341
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
int FFirstKeyId() const
Definition: shash.h:1154
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
::TSize THashSet< TKey, THashFunc >::GetMemUsed ( ) const
inline

Definition at line 1102 of file shash.h.

1102  {
1103  return PortV.GetMemUsed() + KeyV.GetMemUsed() + sizeof(bool) + 2*sizeof(int); }
TVec< TSetKey > KeyV
Definition: shash.h:1053
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:483
TIntV PortV
Definition: shash.h:1052
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
int THashSet< TKey, THashFunc >::GetMxKeyIds ( ) const
inline

Definition at line 1124 of file shash.h.

1124 {return KeyV.Len(); }
TVec< TSetKey > KeyV
Definition: shash.h:1053
template<class TKey , class THashFunc >
uint THashSet< TKey, THashFunc >::GetNextPrime ( const uint Val) const
private

Definition at line 1184 of file shash.h.

1184  {
1186  int h, len = (int)TIntH::HashPrimes;
1187  while (len > 0) {
1188  h = len >> 1; m = f + h;
1189  if (*m < Val) { f = m; f++; len = len - h - 1; }
1190  else len = h;
1191  }
1192  return f == l ? *(l - 1) : *f;
1193 }
unsigned int uint
Definition: bd.h:11
static const unsigned int HashPrimeT[HashPrimes]
Definition: hash.h:91
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
int THashSet< TKey, THashFunc >::GetPorts ( ) const
inline

Definition at line 1122 of file shash.h.

1122 {return PortV.Len(); }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TIntV PortV
Definition: shash.h:1052
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
int THashSet< TKey, THashFunc >::GetReservedKeyIds ( ) const
inline

Definition at line 1125 of file shash.h.

1125 { return KeyV.Reserved(); }
TVec< TSetKey > KeyV
Definition: shash.h:1053
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
int THashSet< TKey, THashFunc >::GetRndKeyId ( TRnd Rnd) const
inline

Definition at line 1144 of file shash.h.

1144  {
1146  IAssert(Len()>0);
1147  return Rnd.GetUniDevInt(Len()); }
#define IAssert(Cond)
Definition: bd.h:262
bool IsKeyIdEqKeyN() const
Definition: shash.h:1126
int Len() const
Definition: shash.h:1121
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::GetSet ( const TKey &  Key1)
inlinestatic

Definition at line 1162 of file shash.h.

1162  {
1163  THashSet<TKey> Set(1); Set.AddKey(Key1); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::GetSet ( const TKey &  Key1,
const TKey &  Key2 
)
inlinestatic

Definition at line 1164 of file shash.h.

1164  {
1165  THashSet<TKey> Set(2); Set.AddKey(Key1); Set.AddKey(Key2); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::GetSet ( const TKey &  Key1,
const TKey &  Key2,
const TKey &  Key3 
)
inlinestatic

Definition at line 1166 of file shash.h.

1166  {
1167  THashSet<TKey> Set(3); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::GetSet ( const TKey &  Key1,
const TKey &  Key2,
const TKey &  Key3,
const TKey &  Key4 
)
inlinestatic

Definition at line 1168 of file shash.h.

1168  {
1169  THashSet<TKey> Set(4); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::GetSet ( const TKey &  Key1,
const TKey &  Key2,
const TKey &  Key3,
const TKey &  Key4,
const TKey &  Key5 
)
inlinestatic

Definition at line 1170 of file shash.h.

1170  {
1171  THashSet<TKey> Set(5); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::GetSet ( const TKey &  Key1,
const TKey &  Key2,
const TKey &  Key3,
const TKey &  Key4,
const TKey &  Key5,
const TKey &  Key6 
)
inlinestatic

Definition at line 1172 of file shash.h.

1172  {
1173  THashSet<TKey> Set(6); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::GetSet ( const TKey &  Key1,
const TKey &  Key2,
const TKey &  Key3,
const TKey &  Key4,
const TKey &  Key5,
const TKey &  Key6,
const TKey &  Key7 
)
inlinestatic

Definition at line 1174 of file shash.h.

1174  {
1175  THashSet<TKey> Set(7); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); Set.AddKey(Key7); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::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 
)
inlinestatic

Definition at line 1176 of file shash.h.

1176  {
1177  THashSet<TKey> Set(8); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); Set.AddKey(Key7); Set.AddKey(Key8); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
static THashSet<TKey> THashSet< TKey, THashFunc >::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 
)
inlinestatic

Definition at line 1178 of file shash.h.

1178  {
1179  THashSet<TKey> Set(9); Set.AddKey(Key1); Set.AddKey(Key2); Set.AddKey(Key3); Set.AddKey(Key4); Set.AddKey(Key5); Set.AddKey(Key6); Set.AddKey(Key7); Set.AddKey(Key8); Set.AddKey(Key9); return Set;}
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TSetKey& THashSet< TKey, THashFunc >::GetSetKey ( const int &  KeyId)
inlineprivate

Definition at line 1057 of file shash.h.

1057  {
1058  TSetKey& SetKey=KeyV[KeyId];
1059  Assert(SetKey.HashCd!=-1); return SetKey; }
TVec< TSetKey > KeyV
Definition: shash.h:1053
THashSetKey< TKey > TSetKey
Definition: shash.h:1051
#define Assert(Cond)
Definition: bd.h:251
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
const TSetKey& THashSet< TKey, THashFunc >::GetSetKey ( const int &  KeyId) const
inlineprivate

Definition at line 1060 of file shash.h.

1060  {
1061  const TSetKey& SetKey=KeyV[KeyId];
1062  Assert(SetKey.HashCd!=-1); return SetKey; }
TVec< TSetKey > KeyV
Definition: shash.h:1053
THashSetKey< TKey > TSetKey
Definition: shash.h:1051
#define Assert(Cond)
Definition: bd.h:251
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
bool THashSet< TKey, THashFunc >::IsAutoSize ( ) const
inline

Definition at line 1123 of file shash.h.

1123 {return AutoSizeP; }
TBool AutoSizeP
Definition: shash.h:1054
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
bool THashSet< TKey, THashFunc >::IsKey ( const TKey &  Key) const
inline

Definition at line 1148 of file shash.h.

1148 {return GetKeyId(Key)!=-1; }
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
bool THashSet< TKey, THashFunc >::IsKey ( const TKey &  Key,
int &  KeyId 
) const
inline

Definition at line 1149 of file shash.h.

1149  {
1150  KeyId=GetKeyId(Key); return KeyId!=-1; }
int GetKeyId(const TKey &Key) const
Definition: shash.h:1328
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
bool THashSet< TKey, THashFunc >::IsKeyId ( const int &  KeyId) const
inline

Definition at line 1151 of file shash.h.

1151  {
1152  return (0<=KeyId)&&(KeyId<KeyV.Len())&&(KeyV[KeyId].HashCd!=-1); }
TVec< TSetKey > KeyV
Definition: shash.h:1053
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
bool THashSet< TKey, THashFunc >::IsKeyIdEqKeyN ( ) const
inline

Definition at line 1126 of file shash.h.

1126 {return FreeKeys==0; }
TInt FreeKeys
Definition: shash.h:1055
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
int THashSet< TKey, THashFunc >::Len ( ) const
inline

Definition at line 1121 of file shash.h.

1121 {return KeyV.Len()-FreeKeys; }
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::Load ( TSIn SIn)
inline

Definition at line 1078 of file shash.h.

1078  {
1079  PortV.Load(SIn); KeyV.Load(SIn);
1080  AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
1081  SIn.LoadCs(); }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
void Load(TSIn &SIn)
Definition: ds.h:895
void LoadCs()
Definition: fl.cpp:28
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
Definition: dt.h:881
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::LoadXml ( const PXmlTok XmlTok,
const TStr Nm = "" 
)
inline

Definition at line 1086 of file shash.h.

1086  {
1088  for (int KeyN=0; KeyN<KeyV.Len(); KeyN++) {
1089  AddKey(KeyV[KeyN].Key); }}
#define XLoadHd(Nm)
Definition: bd.h:312
TVec< TSetKey > KeyV
Definition: shash.h:1053
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
#define XLoad(Nm)
Definition: bd.h:315
TBool AutoSizeP
Definition: shash.h:1054
int AddKey(const TKey &Key)
Definition: shash.h:1254
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
template<class TKey, class THashFunc >
void THashSet< TKey, THashFunc >::MarkDelKey ( const TKey &  Key)

Definition at line 1309 of file shash.h.

1309  {
1310  IAssert(!PortV.Empty());
1311  int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
1312  int HashCd=abs(THashFunc::GetSecHashCd(Key));
1313  int PrevKeyId=-1;
1314  int KeyId=PortV[PortN];
1315 
1316  while ((KeyId!=-1) &&
1317  !((KeyV[KeyId].HashCd==HashCd) && (KeyV[KeyId].Key==Key))) {
1318  PrevKeyId=KeyId; KeyId=KeyV[KeyId].Next; }
1319 
1320  IAssertR(KeyId!=-1, Key.GetStr());
1321  if (PrevKeyId==-1) {PortV[PortN]=KeyV[KeyId].Next; }
1322  else {KeyV[PrevKeyId].Next=KeyV[KeyId].Next; }
1323  KeyV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
1324  KeyV[KeyId].HashCd=TInt(-1);
1325 }
#define IAssert(Cond)
Definition: bd.h:262
TInt FFreeKeyId
Definition: shash.h:1055
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec< TSetKey > KeyV
Definition: shash.h:1053
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TInt FreeKeys
Definition: shash.h:1055
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::MarkDelKeyId ( const int &  KeyId)
inline

Definition at line 1139 of file shash.h.

1139 {MarkDelKey(GetKey(KeyId)); }
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
void MarkDelKey(const TKey &Key)
Definition: shash.h:1309
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
THashSet& THashSet< TKey, THashFunc >::operator= ( const THashSet< TKey, THashFunc > &  Set)
inline

Definition at line 1093 of file shash.h.

1093  {
1094  if (this!=&Set) {
1095  PortV=Set.PortV; KeyV=Set.KeyV; AutoSizeP=Set.AutoSizeP;
1097  return *this; }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052
template<class TKey , class THashFunc >
bool THashSet< TKey, THashFunc >::operator== ( const THashSet< TKey, THashFunc > &  Set) const

Definition at line 1234 of file shash.h.

1234  {
1235  if (Len() != Set.Len()) { return false; }
1236  for (int k = FFirstKeyId(); FNextKeyId(k); k++) {
1237  if (! Set.IsKey(GetKey(k))) { return false; }
1238  }
1239  return true;
1240 }
bool IsKey(const TKey &Key) const
Definition: shash.h:1148
const TKey & GetKey(const int &KeyId) const
Definition: shash.h:1141
int Len() const
Definition: shash.h:1121
bool FNextKeyId(int &KeyId) const
Definition: shash.h:1341
int FFirstKeyId() const
Definition: shash.h:1154
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
const TKey& THashSet< TKey, THashFunc >::operator[] ( const int &  KeyId) const
inline

Definition at line 1099 of file shash.h.

1099 {return GetSetKey(KeyId).Key; }
TKey Key
Definition: shash.h:985
TSetKey & GetSetKey(const int &KeyId)
Definition: shash.h:1057
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TKey& THashSet< TKey, THashFunc >::operator[] ( const int &  KeyId)
inline

Definition at line 1100 of file shash.h.

1100 {return GetSetKey(KeyId).Key; }
TKey Key
Definition: shash.h:985
TSetKey & GetSetKey(const int &KeyId)
Definition: shash.h:1057
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::Pack ( )
inline

Definition at line 1160 of file shash.h.

1160 {KeyV.Pack(); }
TVec< TSetKey > KeyV
Definition: shash.h:1053
template<class TKey , class THashFunc >
void THashSet< TKey, THashFunc >::Resize ( )
private

Definition at line 1196 of file shash.h.

1196  {
1197  // resize & initialize port vector
1198  if (PortV.Len()==0) {PortV.Gen(17); }
1199  else if (AutoSizeP&&(KeyV.Len()>2*PortV.Len())) {
1200  PortV.Gen(GetNextPrime(PortV.Len()+1));
1201  } else {
1202  return;
1203  }
1204  PortV.PutAll(TInt(-1));
1205  // reSet keys
1206  for (int KeyId=0; KeyId<KeyV.Len(); KeyId++) {
1207  TSetKey& SetKey=KeyV[KeyId];
1208  if (SetKey.HashCd!=-1) {
1209  int PortN=abs(THashFunc::GetPrimHashCd(SetKey.Key)%PortV.Len());
1210  SetKey.Next=PortV[PortN];
1211  PortV[PortN]=KeyId;
1212  }
1213  }
1214 }
TVec< TSetKey > KeyV
Definition: shash.h:1053
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TBool AutoSizeP
Definition: shash.h:1054
THashSetKey< TKey > TSetKey
Definition: shash.h:1051
TIntV PortV
Definition: shash.h:1052
Definition: dt.h:1044
uint GetNextPrime(const uint &Val) const
Definition: shash.h:1184
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::Save ( TSOut SOut) const
inline

Definition at line 1082 of file shash.h.

1082  {
1083  PortV.Save(SOut); KeyV.Save(SOut);
1084  AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
1085  SOut.SaveCs(); }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
void Save(TSOut &SOut) const
Definition: dt.h:1060
TInt FreeKeys
Definition: shash.h:1055
void Save(TSOut &SOut) const
Definition: dt.h:902
void Save(TSOut &SOut) const
Definition: ds.h:903
void SaveCs()
Definition: fl.h:171
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052
template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
void THashSet< TKey, THashFunc >::SaveXml ( TSOut SOut,
const TStr Nm 
)
inline

Definition at line 1090 of file shash.h.

1090  {
1091  Defrag(); XSaveHd(Nm); XSave(KeyV); XSave(AutoSizeP); }
void Defrag()
Definition: shash.h:1366
TVec< TSetKey > KeyV
Definition: shash.h:1053
#define XSaveHd(Nm)
Definition: bd.h:318
#define XSave(Nm)
Definition: bd.h:333
TBool AutoSizeP
Definition: shash.h:1054
template<class TKey , class THashFunc >
void THashSet< TKey, THashFunc >::Swap ( THashSet< TKey, THashFunc > &  Set)

Definition at line 1355 of file shash.h.

1355  {
1356  if (this!=&Set) {
1357  PortV.Swap(Set.PortV);
1358  KeyV.Swap(Set.KeyV);
1359  ::Swap(AutoSizeP, Set.AutoSizeP);
1361  ::Swap(FreeKeys, Set.FreeKeys);
1362  }
1363 }
TInt FFreeKeyId
Definition: shash.h:1055
TVec< TSetKey > KeyV
Definition: shash.h:1053
TInt FreeKeys
Definition: shash.h:1055
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
TBool AutoSizeP
Definition: shash.h:1054
TIntV PortV
Definition: shash.h:1052
void Swap(THashSet &Set)
Definition: shash.h:1355

Member Data Documentation

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TBool THashSet< TKey, THashFunc >::AutoSizeP
private

Definition at line 1054 of file shash.h.

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TInt THashSet< TKey, THashFunc >::FFreeKeyId
private

Definition at line 1055 of file shash.h.

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TInt THashSet< TKey, THashFunc >::FreeKeys
private

Definition at line 1055 of file shash.h.

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TVec<TSetKey> THashSet< TKey, THashFunc >::KeyV
private

Definition at line 1053 of file shash.h.

template<class TKey, class THashFunc = TDefaultHashFunc<TKey>>
TIntV THashSet< TKey, THashFunc >::PortV
private

Definition at line 1052 of file shash.h.


The documentation for this class was generated from the following file: