SNAP Library 2.0, Developer Reference  2013-05-13 16:33:57
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
Public Types | Public Member Functions | Static Public Attributes | Private Member Functions | Private Attributes
TSparseSet< TKey, GroupSize > Class Template Reference

#include <shash.h>

Collaboration diagram for TSparseSet< TKey, GroupSize >:
Collaboration graph
[legend]

List of all members.

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
TSparseSet & operator= (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.

References TSparseSet< TKey, GroupSize >::ResetThresh().

: Table(GetMinSize(0, WantedVals)) { ResetThresh(); }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
TSparseSet< TKey, GroupSize >::TSparseSet ( TSIn &  SIn) [inline]

Definition at line 792 of file shash.h.

: ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }

Member Function Documentation

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

Definition at line 960 of file shash.h.

                                                       {
  ResizeDelta(1);
  int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
  if (Pos != -1) { return Pos; } // key exists
  else {
    Table.Set(PosToIns, Key);
    return PosToIns;
  }
}
template<class TKey , uint16 GroupSize = 48>
TIter TSparseSet< TKey, GroupSize >::BegI ( ) const [inline]

Definition at line 801 of file shash.h.

References TSparseTable< TVal, GroupSize >::BegI(), and TSparseSet< TKey, GroupSize >::Table.

{ return Table.BegI(); }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Clr ( const bool &  DoDel = true) [inline]

Definition at line 811 of file shash.h.

References TSparseTable< TVal, GroupSize >::Clr(), TSparseSet< TKey, GroupSize >::ResetThresh(), and TSparseSet< TKey, GroupSize >::Table.

{ Table.Clr(DoDel);  ResetThresh(); }

Here is the call graph for this function:

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.

References Assert, TSparseTable< TVal, GroupSize >::GetGroup(), TSparseTable< TVal, GroupSize >::Groups(), TSparseSet< TKey, GroupSize >::Reserved(), and TSparseSet< TKey, GroupSize >::Table.

                                                                                      {
  Clr(false);
  const int NewSize = GetMinSize(SSet.Reserved(), MnWanted);
  if (NewSize > Reserved()) {
    Table.Resize(NewSize);
    ResetThresh();
  }
  const uint BuckM1 = Reserved() - 1;
  for (int g = 0; g < SSet.Table.Groups(); g++) {
    const TSGroup& Group = SSet.Table.GetGroup(g);
    for (int b = 0; b < Group.Len(); b++) {
      int Tries = 0; uint BuckNum;
      for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
       ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
        Tries++;
        Assert(Tries < Reserved());
      }
      Table.Set(BuckNum, Group.Offset(b));
    }
  }
}

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
bool TSparseSet< TKey, GroupSize >::Empty ( ) const [inline]

Definition at line 805 of file shash.h.

References TSparseSet< TKey, GroupSize >::Len().

{ return Len() == 0; }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
TIter TSparseSet< TKey, GroupSize >::EndI ( ) const [inline]

Definition at line 802 of file shash.h.

References TSparseTable< TVal, GroupSize >::EndI(), and TSparseSet< TKey, GroupSize >::Table.

{ return Table.EndI(); }

Here is the call graph for this function:

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.

References Assert.

Referenced by TSparseSet< TKey, GroupSize >::GetKeyId().

                                                                                        {
  const uint BuckM1 = Reserved() - 1;
  uint BuckNum = Key.GetPrimHashCd() & BuckM1;
  int Tries = 0;
  while (true) {
    if (Table.IsEmpty(BuckNum)) {
      Pos = -1;  PosToIns = BuckNum;  return;
    }
    else if (Key == Table.Get(BuckNum)) {
      Pos = BuckNum;  PosToIns = -1;  return;
    }
    Tries++;
    BuckNum = (BuckNum + Tries) & BuckM1;
    Assert(Tries < Reserved());
  }
}

Here is the caller graph for this function:

template<class TKey , uint16 GroupSize = 48>
uint TSparseSet< TKey, GroupSize >::GetDiskSz ( ) const [inline]

Definition at line 808 of file shash.h.

References TSparseTable< TVal, GroupSize >::GetDiskSz(), and TSparseSet< TKey, GroupSize >::Table.

{ return 2*sizeof(TInt) + Table.GetDiskSz(); }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
TIter TSparseSet< TKey, GroupSize >::GetI ( const int &  KeyId) const [inline]

Definition at line 803 of file shash.h.

References Assert, TSparseTable< TVal, GroupSize >::GetI(), TSparseSet< TKey, GroupSize >::IsKeyId(), and TSparseSet< TKey, GroupSize >::Table.

{ Assert(IsKeyId(KeyId));  return Table.GetI(KeyId); }

Here is the call graph for this function:

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.

References TSparseTable< TVal, GroupSize >::Get(), and TSparseSet< TKey, GroupSize >::Table.

{ return Table.Get(KeyId); }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
int TSparseSet< TKey, GroupSize >::GetKeyId ( const TKey &  Key) const [inline]

Definition at line 816 of file shash.h.

References TSparseSet< TKey, GroupSize >::FindPos().

Referenced by TSparseSet< TKey, GroupSize >::IsKey().

                                      { int Pos, PosToIns;
    FindPos(Key, Pos, PosToIns);  return Pos; }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::GetKeyV ( TVec< TKey > &  KeyV) const

Definition at line 971 of file shash.h.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Gen().

                                                                {
  KeyV.Gen(Len(), 0);
  for (TIter I = BegI(); I < EndI(); I++) {
    KeyV.Add(I()); }
}

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
::TSize TSparseSet< TKey, GroupSize >::GetMemUsed ( ) const [inline]

Definition at line 799 of file shash.h.

References TSparseTable< TVal, GroupSize >::GetMemUsed(), and TSparseSet< TKey, GroupSize >::Table.

{ return 2*sizeof(TInt)+Table.GetMemUsed(); }

Here is the call graph for this function:

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.

                                                                                           {
  int Size = MinBuckets;
  while (Size*MxOccupancy <= WantedVals || CurVals > Size * MxOccupancy) Size *= 2;
  return Size;
}
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.

References Assert, TSparseSet< TKey, GroupSize >::IsKeyId(), TSparseSet< TKey, GroupSize >::Len(), and TSparseSet< TKey, GroupSize >::Reserved().

                                             { Assert(Len()>0);
    int KeyId = Rnd.GetUniDevInt(Reserved());
    while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
bool TSparseSet< TKey, GroupSize >::IsKey ( const TKey &  Key) const [inline]

Definition at line 818 of file shash.h.

References TSparseSet< TKey, GroupSize >::GetKeyId().

{ return GetKeyId(Key) != -1; }

Here is the call graph for this function:

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.

References TSparseSet< TKey, GroupSize >::GetKeyId().

                                                {
    KeyId = GetKeyId(Key);  return KeyId != -1; }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
bool TSparseSet< TKey, GroupSize >::IsKeyId ( const int &  KeyId) const [inline]

Definition at line 821 of file shash.h.

References TSparseTable< TVal, GroupSize >::IsEmpty(), and TSparseSet< TKey, GroupSize >::Table.

Referenced by TSparseSet< TKey, GroupSize >::GetI(), and TSparseSet< TKey, GroupSize >::GetRndKeyId().

{ return ! Table.IsEmpty(KeyId); }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , uint16 GroupSize = 48>
int TSparseSet< TKey, GroupSize >::Len ( ) const [inline]

Definition at line 806 of file shash.h.

References TSparseTable< TVal, GroupSize >::Len(), and TSparseSet< TKey, GroupSize >::Table.

Referenced by TSparseSet< TKey, GroupSize >::Empty(), TSparseSet< TKey, GroupSize >::GetRndKeyId(), and TSparseSet< TKey, GroupSize >::Reserve().

{ return Table.Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Load ( TSIn &  SIn) [inline]

Definition at line 793 of file shash.h.

References TSparseSet< TKey, GroupSize >::ExpandThresh, TSparseTable< TVal, GroupSize >::Load(), TInt::Load(), TSparseSet< TKey, GroupSize >::ShrinkThresh, and TSparseSet< TKey, GroupSize >::Table.

{ ShrinkThresh.Load(SIn);  ExpandThresh.Load(SIn);  Table.Load(SIn); }

Here is the call graph for this function:

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.

References Assert, TSparseTable< TVal, GroupSize >::GetGroup(), TSparseTable< TVal, GroupSize >::Groups(), TSparseSet< TKey, GroupSize >::Reserved(), and TSparseSet< TKey, GroupSize >::Table.

Referenced by TSparseSet< TKey, GroupSize >::ResizeDelta().

                                                                                {
  Clr(false);
  int NewSize;
  if (MnWanted == 0) NewSize = SSet.Reserved();
  else NewSize = GetMinSize(SSet.Reserved(), MnWanted);
  if (NewSize > Reserved()) {
    Table.Resize(NewSize);
    ResetThresh();
  }
  const uint BuckM1 = Reserved() - 1;
  for (int g = 0; g < SSet.Table.Groups(); g++) {
    TSGroup& Group = SSet.Table.GetGroup(g);
    for (int b = 0; b < Group.Len(); b++) {
      int Tries = 0; uint BuckNum;
      for (BuckNum = Group.Offset(b).GetPrimHashCd() & BuckM1;
       ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
        Tries++;
        Assert(Tries < Reserved());
      }
      Assert(Table.IsEmpty(BuckNum));
      Table.Set(BuckNum, Group.Offset(b));
    }
    Group.Clr(true); // delete
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , uint16 GroupSize>
bool TSparseSet< TKey, GroupSize >::operator< ( const TSparseSet< TKey, GroupSize > &  SSet) const

Definition at line 948 of file shash.h.

References TSparseSet< TKey, GroupSize >::Table.

                                                                          {
  return Table < SSet.Table;
}
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.

References TSparseSet< TKey, GroupSize >::ExpandThresh, TSparseSet< TKey, GroupSize >::ShrinkThresh, and TSparseSet< TKey, GroupSize >::Table.

                                                                                            {
  if (this != &SSet) {
    ShrinkThresh = SSet.ShrinkThresh;
    ExpandThresh = SSet.ExpandThresh;
    Table = SSet.Table;
  }
  return *this;
}
template<class TKey , uint16 GroupSize>
bool TSparseSet< TKey, GroupSize >::operator== ( const TSparseSet< TKey, GroupSize > &  SSet) const

Definition at line 943 of file shash.h.

References TSparseSet< TKey, GroupSize >::Table.

                                                                           {
  return Table == SSet.Table;
}
template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Reserve ( const int &  MxVals) [inline]

Definition at line 810 of file shash.h.

References TSparseSet< TKey, GroupSize >::Len(), and TSparseSet< TKey, GroupSize >::ResizeDelta().

{ if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize = 48>
int TSparseSet< TKey, GroupSize >::Reserved ( ) const [inline]

Definition at line 807 of file shash.h.

References TSparseTable< TVal, GroupSize >::Reserved(), and TSparseSet< TKey, GroupSize >::Table.

Referenced by TSparseSet< TKey, GroupSize >::CopyFrom(), TSparseSet< TKey, GroupSize >::GetRndKeyId(), and TSparseSet< TKey, GroupSize >::MoveFrom().

{ return Table.Reserved(); }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::ResetThresh ( ) [private]

Definition at line 839 of file shash.h.

Referenced by TSparseSet< TKey, GroupSize >::Clr(), TSparseSet< TKey, GroupSize >::ResizeDelta(), and TSparseSet< TKey, GroupSize >::TSparseSet().

                                              {
  ExpandThresh = int(Table.Reserved() * MxOccupancy);
  ShrinkThresh = int(Table.Reserved() * MnOccupancy);
}

Here is the caller graph for this function:

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.

References TSparseSet< TKey, GroupSize >::MoveFrom(), TSparseSet< TKey, GroupSize >::ResetThresh(), and Swap().

Referenced by TSparseSet< TKey, GroupSize >::Reserve().

                                                                                       {
  if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
  const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
  if (NewSize > Reserved()) {
    printf("***Resize SparseSet: %d->%d\n", Reserved(), NewSize);
    TSparseSet TmpSSet(Len()+ValsToAdd);
    TmpSSet.ResetThresh();
    TmpSSet.MoveFrom(*this, Len());
    Swap(TmpSSet);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , uint16 GroupSize = 48>
void TSparseSet< TKey, GroupSize >::Save ( TSOut &  SOut) const [inline]

Definition at line 794 of file shash.h.

References TSparseSet< TKey, GroupSize >::ExpandThresh, TSparseTable< TVal, GroupSize >::Save(), TInt::Save(), TSparseSet< TKey, GroupSize >::ShrinkThresh, and TSparseSet< TKey, GroupSize >::Table.

{ ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }

Here is the call graph for this function:

template<class TKey , uint16 GroupSize>
void TSparseSet< TKey, GroupSize >::Swap ( TSparseSet< TKey, GroupSize > &  SSet)

Definition at line 953 of file shash.h.

References TSparseSet< TKey, GroupSize >::ExpandThresh, TSparseSet< TKey, GroupSize >::ShrinkThresh, Swap(), and TSparseSet< TKey, GroupSize >::Table.

                                                       {
  ::Swap(ShrinkThresh, SSet.ShrinkThresh);
  ::Swap(ExpandThresh, SSet.ExpandThresh);
  Table.Swap(SSet.Table);
}

Here is the call graph for this function:

Member Data Documentation

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

Definition at line 788 of file shash.h.

Referenced by TSparseSet< TKey, GroupSize >::Load(), TSparseSet< TKey, GroupSize >::operator=(), TSparseSet< TKey, GroupSize >::Save(), and TSparseSet< TKey, GroupSize >::Swap().

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.

Referenced by TSparseSet< TKey, GroupSize >::Load(), TSparseSet< TKey, GroupSize >::operator=(), TSparseSet< TKey, GroupSize >::Save(), and TSparseSet< TKey, GroupSize >::Swap().

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

Definition at line 789 of file shash.h.

Referenced by TSparseSet< TKey, GroupSize >::BegI(), TSparseSet< TKey, GroupSize >::Clr(), TSparseSet< TKey, GroupSize >::CopyFrom(), TSparseSet< TKey, GroupSize >::EndI(), TSparseSet< TKey, GroupSize >::GetDiskSz(), TSparseSet< TKey, GroupSize >::GetI(), TSparseSet< TKey, GroupSize >::GetKey(), TSparseSet< TKey, GroupSize >::GetMemUsed(), TSparseSet< TKey, GroupSize >::IsKeyId(), TSparseSet< TKey, GroupSize >::Len(), TSparseSet< TKey, GroupSize >::Load(), TSparseSet< TKey, GroupSize >::MoveFrom(), TSparseSet< TKey, GroupSize >::operator<(), TSparseSet< TKey, GroupSize >::operator=(), TSparseSet< TKey, GroupSize >::operator==(), TSparseSet< TKey, GroupSize >::Reserved(), TSparseSet< TKey, GroupSize >::Save(), and TSparseSet< TKey, GroupSize >::Swap().

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