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
TSparseSet< TKey, GroupSize > Class Template Reference

#include <shash.h>

Public Types

typedef TSparseTable< TKey,
GroupSize >::TIter 
TIter
 
typedef TSparseTable< TKey,
GroupSize >::TSGroup 
TSGroup
 

Public Member Functions

 TSparseSet (const int &WantedVals=0)
 
 TSparseSet (TSIn &SIn)
 
void Load (TSIn &SIn)
 
void Save (TSOut &SOut) const
 
TSparseSetoperator= (const TSparseSet &SSet)
 
bool operator== (const TSparseSet &SSet) const
 
bool operator< (const TSparseSet &SSet) const
 
::TSize GetMemUsed () const
 
TIter BegI () const
 
TIter EndI () const
 
TIter GetI (const int &KeyId) const
 
bool Empty () const
 
int Len () const
 
int Reserved () const
 
uint GetDiskSz () const
 
void Reserve (const int &MxVals)
 
void Clr (const bool &DoDel=true)
 
void Swap (TSparseSet &SSet)
 
int AddKey (const TKey &Key)
 
const TKey & GetKey (const int &KeyId) const
 
int GetKeyId (const TKey &Key) const
 
bool IsKey (const TKey &Key) const
 
bool IsKey (const TKey &Key, int &KeyId) const
 
bool IsKeyId (const int &KeyId) const
 
int GetRndKeyId (TRnd &Rnd=TInt::Rnd) const
 
void GetKeyV (TVec< TKey > &KeyV) const
 

Static Public Attributes

static const float MxOccupancy = 0.8f
 
static const float MnOccupancy = 0.4f * 0.8f
 
static const int MinBuckets = 32
 

Private Member Functions

void ResetThresh ()
 
int GetMinSize (const int &CurVals, const int &WantedVals) const
 
void CopyFrom (const TSparseSet &SSet, const int &MnWanted)
 
void MoveFrom (TSparseSet &SSet, const int &MnWanted)
 
void ResizeDelta (const int &ValsToAdd, const int &MnWanted=0)
 
void FindPos (const TKey &Key, int &Pos, int &PosToIns) const
 

Private Attributes

TInt ShrinkThresh
 
TInt ExpandThresh
 
TSparseTable< TKey, GroupSize > Table
 

Detailed Description

template<class TKey, uint16 GroupSize = 48>
class TSparseSet< TKey, GroupSize >

Definition at line 772 of file shash.h.

Member Typedef Documentation

template<class TKey , uint16 GroupSize = 48>
typedef TSparseTable<TKey, GroupSize>::TIter TSparseSet< TKey, GroupSize >::TIter

Definition at line 774 of file shash.h.

template<class TKey , uint16 GroupSize = 48>
typedef TSparseTable<TKey, GroupSize>::TSGroup TSparseSet< TKey, GroupSize >::TSGroup

Definition at line 775 of file shash.h.

Constructor & Destructor Documentation

template<class TKey , uint16 GroupSize = 48>
TSparseSet< TKey, GroupSize >::TSparseSet ( const int &  WantedVals = 0)
inline

Definition at line 791 of file shash.h.

791 : Table(GetMinSize(0, WantedVals)) { ResetThresh(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
void ResetThresh()
Definition: shash.h:839
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:845
template<class TKey , uint16 GroupSize = 48>
TSparseSet< TKey, GroupSize >::TSparseSet ( TSIn SIn)
inline

Definition at line 792 of file shash.h.

792 : ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TInt ShrinkThresh
Definition: shash.h:788
TInt ExpandThresh
Definition: shash.h:788

Member Function Documentation

template<class TKey , uint16 GroupSize>
int TSparseSet< TKey, GroupSize >::AddKey ( const TKey &  Key)

Definition at line 960 of file shash.h.

960  {
961  ResizeDelta(1);
962  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
963  if (Pos != -1) { return Pos; } // key exists
964  else {
965  Table.Set(PosToIns, Key);
966  return PosToIns;
967  }
968 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:902
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:915
TVal & Set(const int &ValN, const TVal &Val)
Definition: shash.h:420
template<class TKey , uint16 GroupSize = 48>
TIter TSparseSet< TKey, GroupSize >::BegI ( ) const
inline

Definition at line 801 of file shash.h.

801 { return Table.BegI(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TIter BegI() const
Definition: shash.h:336
template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Clr ( const bool &  DoDel = true)
inline

Definition at line 811 of file shash.h.

811 { Table.Clr(DoDel); ResetThresh(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
void Clr(const bool &DoDel=true)
Definition: shash.h:392
void ResetThresh()
Definition: shash.h:839
template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::CopyFrom ( const TSparseSet< TKey, GroupSize > &  SSet,
const int &  MnWanted 
)
private

Definition at line 852 of file shash.h.

852  {
853  Clr(false);
854  const int NewSize = GetMinSize(SSet.Reserved(), MnWanted);
855  if (NewSize > Reserved()) {
856  Table.Resize(NewSize);
857  ResetThresh();
858  }
859  const uint BuckM1 = Reserved() - 1;
860  for (int g = 0; g < SSet.Table.Groups(); g++) {
861  const TSGroup& Group = SSet.Table.GetGroup(g);
862  for (int b = 0; b < Group.Len(); b++) {
863  int Tries = 0; uint BuckNum;
864  for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
865  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
866  Tries++;
867  Assert(Tries < Reserved());
868  }
869  Table.Set(BuckNum, Group.Offset(b));
870  }
871  }
872 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
unsigned int uint
Definition: bd.h:11
void Clr(const bool &DoDel=true)
Definition: shash.h:811
TSGroup & GetGroup(const int &GroupN)
Definition: shash.h:367
int Groups() const
Definition: shash.h:351
#define Assert(Cond)
Definition: bd.h:251
void ResetThresh()
Definition: shash.h:839
int Reserved() const
Definition: shash.h:807
TVal & Set(const int &ValN, const TVal &Val)
Definition: shash.h:420
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:845
TSparseTable< TKey, GroupSize >::TSGroup TSGroup
Definition: shash.h:775
bool IsEmpty(const int &ValN) const
Definition: shash.h:361
void Resize(const int &NewVals)
Definition: shash.h:403
template<class TKey , uint16 GroupSize = 48>
bool TSparseSet< TKey, GroupSize >::Empty ( ) const
inline

Definition at line 805 of file shash.h.

805 { return Len() == 0; }
int Len() const
Definition: shash.h:806
template<class TKey , uint16 GroupSize = 48>
TIter TSparseSet< TKey, GroupSize >::EndI ( ) const
inline

Definition at line 802 of file shash.h.

802 { return Table.EndI(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TIter EndI() const
Definition: shash.h:342
template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::FindPos ( const TKey &  Key,
int &  Pos,
int &  PosToIns 
) const
private

Definition at line 915 of file shash.h.

915  {
916  const uint BuckM1 = Reserved() - 1;
917  uint BuckNum = Key.GetPrimHashCd() & BuckM1;
918  int Tries = 0;
919  while (true) {
920  if (Table.IsEmpty(BuckNum)) {
921  Pos = -1; PosToIns = BuckNum; return;
922  }
923  else if (Key == Table.Get(BuckNum)) {
924  Pos = BuckNum; PosToIns = -1; return;
925  }
926  Tries++;
927  BuckNum = (BuckNum + Tries) & BuckM1;
928  Assert(Tries < Reserved());
929  }
930 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
unsigned int uint
Definition: bd.h:11
#define Assert(Cond)
Definition: bd.h:251
int Reserved() const
Definition: shash.h:807
const TVal & Get(const int &ValN) const
Definition: shash.h:362
bool IsEmpty(const int &ValN) const
Definition: shash.h:361
template<class TKey , uint16 GroupSize = 48>
uint TSparseSet< TKey, GroupSize >::GetDiskSz ( ) const
inline

Definition at line 808 of file shash.h.

808 { return 2*sizeof(TInt) + Table.GetDiskSz(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
uint GetDiskSz() const
Definition: shash.h:353
Definition: dt.h:1044
template<class TKey , uint16 GroupSize = 48>
TIter TSparseSet< TKey, GroupSize >::GetI ( const int &  KeyId) const
inline

Definition at line 803 of file shash.h.

803 { Assert(IsKeyId(KeyId)); return Table.GetI(KeyId); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TIter GetI(const int &ValN) const
Definition: shash.h:343
#define Assert(Cond)
Definition: bd.h:251
bool IsKeyId(const int &KeyId) const
Definition: shash.h:821
template<class TKey , uint16 GroupSize = 48>
const TKey& TSparseSet< TKey, GroupSize >::GetKey ( const int &  KeyId) const
inline

Definition at line 815 of file shash.h.

815 { return Table.Get(KeyId); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
const TVal & Get(const int &ValN) const
Definition: shash.h:362
template<class TKey , uint16 GroupSize = 48>
int TSparseSet< TKey, GroupSize >::GetKeyId ( const TKey &  Key) const
inline

Definition at line 816 of file shash.h.

816  { int Pos, PosToIns;
817  FindPos(Key, Pos, PosToIns); return Pos; }
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:915
template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::GetKeyV ( TVec< TKey > &  KeyV) const

Definition at line 971 of file shash.h.

971  {
972  KeyV.Gen(Len(), 0);
973  for (TIter I = BegI(); I < EndI(); I++) {
974  KeyV.Add(I()); }
975 }
TSparseTable< TKey, GroupSize >::TIter TIter
Definition: shash.h:774
int Len() const
Definition: shash.h:806
TIter EndI() const
Definition: shash.h:802
TIter BegI() const
Definition: shash.h:801
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
template<class TKey , uint16 GroupSize = 48>
::TSize TSparseSet< TKey, GroupSize >::GetMemUsed ( ) const
inline

Definition at line 799 of file shash.h.

799 { return 2*sizeof(TInt)+Table.GetMemUsed(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
Definition: dt.h:1044
::TSize GetMemUsed() const
Definition: shash.h:334
template<class TKey , uint16 GroupSize>
int TSparseSet< TKey, GroupSize >::GetMinSize ( const int &  CurVals,
const int &  WantedVals 
) const
private

Definition at line 845 of file shash.h.

845  {
846  int Size = MinBuckets;
847  while (Size*MxOccupancy <= WantedVals || CurVals > Size * MxOccupancy) Size *= 2;
848  return Size;
849 }
static const int MinBuckets
Definition: shash.h:779
static const float MxOccupancy
Definition: shash.h:777
template<class TKey , uint16 GroupSize = 48>
int TSparseSet< TKey, GroupSize >::GetRndKeyId ( TRnd Rnd = TInt::Rnd) const
inline

Definition at line 822 of file shash.h.

822  { Assert(Len()>0);
823  int KeyId = Rnd.GetUniDevInt(Reserved());
824  while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }
int Len() const
Definition: shash.h:806
#define Assert(Cond)
Definition: bd.h:251
bool IsKeyId(const int &KeyId) const
Definition: shash.h:821
int Reserved() const
Definition: shash.h:807
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
template<class TKey , uint16 GroupSize = 48>
bool TSparseSet< TKey, GroupSize >::IsKey ( const TKey &  Key) const
inline

Definition at line 818 of file shash.h.

818 { return GetKeyId(Key) != -1; }
int GetKeyId(const TKey &Key) const
Definition: shash.h:816
template<class TKey , uint16 GroupSize = 48>
bool TSparseSet< TKey, GroupSize >::IsKey ( const TKey &  Key,
int &  KeyId 
) const
inline

Definition at line 819 of file shash.h.

819  {
820  KeyId = GetKeyId(Key); return KeyId != -1; }
int GetKeyId(const TKey &Key) const
Definition: shash.h:816
template<class TKey , uint16 GroupSize = 48>
bool TSparseSet< TKey, GroupSize >::IsKeyId ( const int &  KeyId) const
inline

Definition at line 821 of file shash.h.

821 { return ! Table.IsEmpty(KeyId); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
bool IsEmpty(const int &ValN) const
Definition: shash.h:361
template<class TKey , uint16 GroupSize = 48>
int TSparseSet< TKey, GroupSize >::Len ( ) const
inline

Definition at line 806 of file shash.h.

806 { return Table.Len(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
int Len() const
Definition: shash.h:349
template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Load ( TSIn SIn)
inline

Definition at line 793 of file shash.h.

793 { ShrinkThresh.Load(SIn); ExpandThresh.Load(SIn); Table.Load(SIn); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
void Load(TSIn &SIn)
Definition: shash.h:328
TInt ShrinkThresh
Definition: shash.h:788
TInt ExpandThresh
Definition: shash.h:788
void Load(TSIn &SIn)
Definition: dt.h:1059
template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::MoveFrom ( TSparseSet< TKey, GroupSize > &  SSet,
const int &  MnWanted 
)
private

Definition at line 875 of file shash.h.

875  {
876  Clr(false);
877  int NewSize;
878  if (MnWanted == 0) NewSize = SSet.Reserved();
879  else NewSize = GetMinSize(SSet.Reserved(), MnWanted);
880  if (NewSize > Reserved()) {
881  Table.Resize(NewSize);
882  ResetThresh();
883  }
884  const uint BuckM1 = Reserved() - 1;
885  for (int g = 0; g < SSet.Table.Groups(); g++) {
886  TSGroup& Group = SSet.Table.GetGroup(g);
887  for (int b = 0; b < Group.Len(); b++) {
888  int Tries = 0; uint BuckNum;
889  for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
890  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
891  Tries++;
892  Assert(Tries < Reserved());
893  }
894  Assert(Table.IsEmpty(BuckNum));
895  Table.Set(BuckNum, Group.Offset(b));
896  }
897  Group.Clr(true); // delete
898  }
899 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
unsigned int uint
Definition: bd.h:11
void Clr(const bool &DoDel=true)
Definition: shash.h:811
TSGroup & GetGroup(const int &GroupN)
Definition: shash.h:367
int Groups() const
Definition: shash.h:351
#define Assert(Cond)
Definition: bd.h:251
void ResetThresh()
Definition: shash.h:839
int Reserved() const
Definition: shash.h:807
TVal & Set(const int &ValN, const TVal &Val)
Definition: shash.h:420
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:845
TSparseTable< TKey, GroupSize >::TSGroup TSGroup
Definition: shash.h:775
bool IsEmpty(const int &ValN) const
Definition: shash.h:361
void Resize(const int &NewVals)
Definition: shash.h:403
template<class TKey , uint16 GroupSize>
bool TSparseSet< TKey, GroupSize >::operator< ( const TSparseSet< TKey, GroupSize > &  SSet) const

Definition at line 948 of file shash.h.

948  {
949  return Table < SSet.Table;
950 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
template<class TKey , uint16 GroupSize>
TSparseSet< TKey, GroupSize > & TSparseSet< TKey, GroupSize >::operator= ( const TSparseSet< TKey, GroupSize > &  SSet)

Definition at line 933 of file shash.h.

933  {
934  if (this != &SSet) {
935  ShrinkThresh = SSet.ShrinkThresh;
936  ExpandThresh = SSet.ExpandThresh;
937  Table = SSet.Table;
938  }
939  return *this;
940 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TInt ShrinkThresh
Definition: shash.h:788
TInt ExpandThresh
Definition: shash.h:788
template<class TKey , uint16 GroupSize>
bool TSparseSet< TKey, GroupSize >::operator== ( const TSparseSet< TKey, GroupSize > &  SSet) const

Definition at line 943 of file shash.h.

943  {
944  return Table == SSet.Table;
945 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Reserve ( const int &  MxVals)
inline

Definition at line 810 of file shash.h.

810 { if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }
int Len() const
Definition: shash.h:806
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:902
template<class TKey , uint16 GroupSize = 48>
int TSparseSet< TKey, GroupSize >::Reserved ( ) const
inline

Definition at line 807 of file shash.h.

807 { return Table.Reserved(); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
int Reserved() const
Definition: shash.h:350
template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::ResetThresh ( )
private

Definition at line 839 of file shash.h.

839  {
842 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TInt ShrinkThresh
Definition: shash.h:788
TInt ExpandThresh
Definition: shash.h:788
static const float MnOccupancy
Definition: shash.h:778
static const float MxOccupancy
Definition: shash.h:777
int Reserved() const
Definition: shash.h:350
template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::ResizeDelta ( const int &  ValsToAdd,
const int &  MnWanted = 0 
)
private

Definition at line 902 of file shash.h.

902  {
903  if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
904  const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
905  if (NewSize > Reserved()) {
906  printf("***Resize SparseSet: %d->%d\n", Reserved(), NewSize);
907  TSparseSet TmpSSet(Len()+ValsToAdd);
908  TmpSSet.ResetThresh();
909  TmpSSet.MoveFrom(*this, Len());
910  Swap(TmpSSet);
911  }
912 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TInt ExpandThresh
Definition: shash.h:788
int Len() const
Definition: shash.h:806
void Swap(TSparseSet &SSet)
Definition: shash.h:953
int Reserved() const
Definition: shash.h:807
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:845
int Len() const
Definition: shash.h:349
template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Save ( TSOut SOut) const
inline

Definition at line 794 of file shash.h.

794 { ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
void Save(TSOut &SOut) const
Definition: dt.h:1060
TInt ShrinkThresh
Definition: shash.h:788
TInt ExpandThresh
Definition: shash.h:788
void Save(TSOut &SOut) const
Definition: shash.h:329
template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::Swap ( TSparseSet< TKey, GroupSize > &  SSet)

Definition at line 953 of file shash.h.

953  {
956  Table.Swap(SSet.Table);
957 }
TSparseTable< TKey, GroupSize > Table
Definition: shash.h:789
TInt ShrinkThresh
Definition: shash.h:788
TInt ExpandThresh
Definition: shash.h:788
void Swap(TSparseSet &SSet)
Definition: shash.h:953
void Swap(TSparseTable &ST)
Definition: shash.h:413

Member Data Documentation

template<class TKey , uint16 GroupSize = 48>
TInt TSparseSet< TKey, GroupSize >::ExpandThresh
private

Definition at line 788 of file shash.h.

template<class TKey , uint16 GroupSize = 48>
const int TSparseSet< TKey, GroupSize >::MinBuckets = 32
static

Definition at line 779 of file shash.h.

template<class TKey , uint16 GroupSize = 48>
const float TSparseSet< TKey, GroupSize >::MnOccupancy = 0.4f * 0.8f
static

Definition at line 778 of file shash.h.

template<class TKey , uint16 GroupSize = 48>
const float TSparseSet< TKey, GroupSize >::MxOccupancy = 0.8f
static

Definition at line 777 of file shash.h.

template<class TKey , uint16 GroupSize = 48>
TInt TSparseSet< TKey, GroupSize >::ShrinkThresh
private

Definition at line 788 of file shash.h.

template<class TKey , uint16 GroupSize = 48>
TSparseTable<TKey, GroupSize> TSparseSet< TKey, GroupSize >::Table
private

Definition at line 789 of file shash.h.


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