TSparseSet< TKey, GroupSize > Class Template Reference

#include <shash.h>

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.

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

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.

{ return Table.BegI(); }

template<class TKey , uint16 GroupSize = 48>

void TSparseSet< TKey, GroupSize >::Clr

(

const bool &

DoDel = true

)

[inline]

Definition at line 811 of file shash.h.

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

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.

                                                                                      {
  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));
    }
  }
}

template<class TKey , uint16 GroupSize = 48>

bool TSparseSet< TKey, GroupSize >::Empty

(

)

const [inline]

Definition at line 805 of file shash.h.

{ return Len() == 0; }

template<class TKey , uint16 GroupSize = 48>

TIter TSparseSet< TKey, GroupSize >::EndI

(

)

const [inline]

Definition at line 802 of file shash.h.

{ return Table.EndI(); }

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.

                                                                                        {
  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());
  }
}

template<class TKey , uint16 GroupSize = 48>

uint TSparseSet< TKey, GroupSize >::GetDiskSz

(

)

const [inline]

Definition at line 808 of file shash.h.

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

template<class TKey , uint16 GroupSize = 48>

TIter TSparseSet< TKey, GroupSize >::GetI

(

const int &

KeyId

)

const [inline]

Definition at line 803 of file shash.h.

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

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.

{ return Table.Get(KeyId); }

template<class TKey , uint16 GroupSize = 48>

int TSparseSet< TKey, GroupSize >::GetKeyId

(

const TKey &

Key

)

const [inline]

Definition at line 816 of file shash.h.

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

template<class TKey , uint16 GroupSize>

void TSparseSet< TKey, GroupSize >::GetKeyV

(

TVec< TKey > &

KeyV

)

const

Definition at line 971 of file shash.h.

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

template<class TKey , uint16 GroupSize = 48>

::TSize TSparseSet< TKey, GroupSize >::GetMemUsed

(

)

const [inline]

Definition at line 799 of file shash.h.

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

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.

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

template<class TKey , uint16 GroupSize = 48>

bool TSparseSet< TKey, GroupSize >::IsKey

(

const TKey &

Key

)

const [inline]

Definition at line 818 of file shash.h.

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

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.

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

template<class TKey , uint16 GroupSize = 48>

bool TSparseSet< TKey, GroupSize >::IsKeyId

(

const int &

KeyId

)

const [inline]

Definition at line 821 of file shash.h.

{ return ! Table.IsEmpty(KeyId); }

template<class TKey , uint16 GroupSize = 48>

int TSparseSet< TKey, GroupSize >::Len

(

)

const [inline]

Definition at line 806 of file shash.h.

{ return Table.Len(); }

template<class TKey , uint16 GroupSize = 48>

void TSparseSet< TKey, GroupSize >::Load

(

TSIn &

SIn

)

[inline]

Definition at line 793 of file shash.h.

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

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.

                                                                                {
  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
  }
}

template<class TKey , uint16 GroupSize>

bool TSparseSet< TKey, GroupSize >::operator<

(

const TSparseSet< TKey, GroupSize > &

SSet

)

const

Definition at line 948 of file shash.h.

                                                                          {
  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.

                                                                                            {
  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.

                                                                           {
  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.

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

template<class TKey , uint16 GroupSize = 48>

int TSparseSet< TKey, GroupSize >::Reserved

(

)

const [inline]

Definition at line 807 of file shash.h.

{ return Table.Reserved(); }

template<class TKey , uint16 GroupSize>

void TSparseSet< TKey, GroupSize >::ResetThresh

(

)

[private]

Definition at line 839 of file shash.h.

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

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.

                                                                                       {
  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);
  }
}

template<class TKey , uint16 GroupSize = 48>

void TSparseSet< TKey, GroupSize >::Save

(

TSOut &

SOut

)

const [inline]

Definition at line 794 of file shash.h.

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

template<class TKey , uint16 GroupSize>

void TSparseSet< TKey, GroupSize >::Swap

(

TSparseSet< TKey, GroupSize > &

SSet

)

Definition at line 953 of file shash.h.

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

---

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:

• glib-core/shash.h