TSparseSet< TKey, GroupSize > Class Template Reference

#include <shash.h>

Collaboration diagram for TSparseSet< TKey, GroupSize >:

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:

• glib-core/shash.h