TSparseGroup< TVal, GroupSize > Class Template Reference

#include <shash.h>

Public Member Functions
	TSparseGroup ()
	TSparseGroup (TSIn &SIn)
	TSparseGroup (const TSparseGroup &SG)
	~TSparseGroup ()
void	Load (TSIn &SIn)
void	Save (TSOut &SOut) const
TSparseGroup &	operator= (const TSparseGroup &SG)
bool	operator== (const TSparseGroup &SG) const
bool	operator< (const TSparseGroup &SG) const
int	Len () const
int	MxLen () const
int	Reserved () const
bool	Empty () const
void	Clr (const bool &DoDel=true)
int	GetGroupSize () const
uint	GetDiskSz () const
bool	IsEmpty (const int &ValN) const
const TVal &	Offset (const int &Pos) const
TVal &	Offset (const int &Pos)
int	OffsetToPos (int Offset) const
int	PosToOffset (int Pos) const
const TVal &	DefVal () const
const TVal &	Get (const int &ValN) const
const TVal &	operator[] (const int ValN) const
TVal &	Set (const int &ValN, const TVal &Val)
TVal &	Set (const int &ValN)
void	Del (const int &ValN)

Private Member Functions
bool	BMTest (const int &ValN) const
void	BMSet (const int &ValN)
void	BMClear (const int &ValN)

Static Private Member Functions
static int	CharBit (const int &ValN)
static int	ModBit (const int &ValN)
static int	PosToOffset (const unsigned char *BitSet, int Pos)

Private Attributes
unsigned char	BitSet [(GroupSize-1)/8+1]
uint16	Buckets
TVal *	Group

Detailed Description

template<class TVal, uint16 GroupSize>
class TSparseGroup< TVal, GroupSize >

Definition at line 61 of file shash.h.

Constructor & Destructor Documentation

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::TSparseGroup ( )

inline

Definition at line 74 of file shash.h.

: Buckets(0), Group(NULL) { memset(BitSet, 0, sizeof(BitSet)); }

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::TSparseGroup ( TSIn &  SIn )

inline

Definition at line 75 of file shash.h.

: Buckets(0), Group(NULL) { Load(SIn); }

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::TSparseGroup

(

const TSparseGroup< TVal, GroupSize > &

SG

)

Definition at line 141 of file shash.h.

                                                                  : Buckets(SG.Buckets), Group(NULL) {
  memcpy(BitSet, SG.BitSet, sizeof(BitSet));
  if (Buckets > 0) {
    Group = new TVal [Buckets];
    for (int b = 0; b < Buckets; b++) { Group[b] = SG.Group[b]; }
  }
}

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize >::~TSparseGroup ( )

inline

Definition at line 77 of file shash.h.

{ if (Group != NULL) delete [] Group; }

Member Function Documentation

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::BMClear ( const int &  ValN )

inlineprivate

Definition at line 71 of file shash.h.

{ BitSet[CharBit(ValN)] &= ~ModBit(ValN); }

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::BMSet ( const int &  ValN )

inlineprivate

Definition at line 70 of file shash.h.

{ BitSet[CharBit(ValN)] |= ModBit(ValN); }

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::BMTest ( const int &  ValN ) const

inlineprivate

Definition at line 69 of file shash.h.

{ return (BitSet[CharBit(ValN)] & ModBit(ValN)) != 0; }

template<class TVal , uint16 GroupSize>

static int TSparseGroup< TVal, GroupSize >::CharBit ( const int &  ValN )

inlinestaticprivate

Definition at line 67 of file shash.h.

{ return ValN >> 3; }

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Clr

(

const bool &

DoDel = true

)

Definition at line 221 of file shash.h.

                                                         {
  if (DoDel && Group != NULL) {
    delete [] Group;
    Group = 0;
  }
  memset(BitSet, 0, sizeof(BitSet));
  Buckets = 0;
}

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::DefVal ( ) const

inline

Definition at line 99 of file shash.h.

{ static TVal DefValue = TVal();  return DefValue; }

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Del

(

const int &

ValN

)

Definition at line 247 of file shash.h.

                                                       {
  if (BMTest(ValN)) {
    const int Offset = PosToOffset(BitSet, ValN);
    if (--Buckets == 0) {
      delete [] Group;
      Group = 0;
    } else {
      const TVal *OldGroup = Group;
      Group = new TVal [Buckets];
      for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
      for (int b = Offset+1; b <= Buckets; b++) Group[b-1] = OldGroup[b];
      if (OldGroup != NULL) delete [] OldGroup;
    }
    BMClear(ValN);
  }
}

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::Empty ( ) const

inline

Definition at line 88 of file shash.h.

{ return Buckets == 0; }

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::Get ( const int &  ValN ) const

inline

Definition at line 100 of file shash.h.

                                         {
    if (BMTest(ValN)) return Group[PosToOffset(BitSet, ValN)]; else return DefVal(); }

template<class TVal , uint16 GroupSize>

uint TSparseGroup< TVal, GroupSize >::GetDiskSz ( ) const

inline

Definition at line 91 of file shash.h.

{ return sizeof(BitSet) + sizeof(uint16) + Buckets*sizeof(TVal); }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::GetGroupSize ( ) const

inline

Definition at line 90 of file shash.h.

{ return GroupSize; }

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::IsEmpty ( const int &  ValN ) const

inline

Definition at line 93 of file shash.h.

{ return ! BMTest(ValN); }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::Len ( ) const

inline

Definition at line 85 of file shash.h.

{ return Buckets; }

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Load

(

TSIn &

SIn

)

Definition at line 150 of file shash.h.

                                                  {
  SIn.LoadBf(BitSet, sizeof(BitSet));
  SIn.Load(Buckets);
  if (Group != NULL) delete [] Group;
  Group = new TVal [Buckets];
  for (int b = 0; b < Buckets; b++) { Group[b] = TVal(SIn); }
}

template<class TVal , uint16 GroupSize>

static int TSparseGroup< TVal, GroupSize >::ModBit ( const int &  ValN )

inlinestaticprivate

Definition at line 68 of file shash.h.

{ return 1 << (ValN&7); }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::MxLen ( ) const

inline

Definition at line 86 of file shash.h.

{ return GroupSize; }

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::Offset ( const int &  Pos ) const

inline

Definition at line 94 of file shash.h.

{ return Group[Pos]; }

template<class TVal , uint16 GroupSize>

TVal& TSparseGroup< TVal, GroupSize >::Offset ( const int &  Pos )

inline

Definition at line 95 of file shash.h.

{ return Group[Pos]; }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::OffsetToPos

(

int

Offset

)

const

Definition at line 206 of file shash.h.

                                                               {
  Assert(Offset < Buckets);
  for (int i = 0; i < sizeof(BitSet); i++) {
    for (int b = 0; b < 8; b++) {
      if (TB1Def::GetBit(b, BitSet[i])) {
        if (Offset == 0) return i*8 + b;
        Offset--;
      }
    }
  }
  Fail;
  return -1;
}

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::operator<

(

const TSparseGroup< TVal, GroupSize > &

SG

)

const

Definition at line 196 of file shash.h.

                                                                            {
  if (Buckets < SG.Buckets) return true;
  if (memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == -1) return true;
  for (int b = 0; b < Buckets; b++) {
    if (Group[b] < SG.Group[b]) return true;
  }
  return false;
}

template<class TVal , uint16 GroupSize>

TSparseGroup< TVal, GroupSize > & TSparseGroup< TVal, GroupSize >::operator=

(

const TSparseGroup< TVal, GroupSize > &

SG

)

Definition at line 166 of file shash.h.

                                                                                                {
  if (this != &SG) {
    if (SG.Buckets == 0 && Group != NULL) {
      delete [] Group;
      Group = 0;
    } else {
      if (Buckets != SG.Buckets) {
        if (Group != NULL) delete [] Group;
        Group = new TVal [SG.Buckets];
      }
      for (int b = 0; b < SG.Buckets; b++) { Group[b] = SG.Group[b]; }
    }
    Buckets = SG.Buckets;
    memcpy(BitSet, SG.BitSet, sizeof(BitSet));
  }
  return *this;
}

template<class TVal , uint16 GroupSize>

bool TSparseGroup< TVal, GroupSize >::operator==

(

const TSparseGroup< TVal, GroupSize > &

SG

)

const

Definition at line 185 of file shash.h.

                                                                             {
  if (Buckets == SG.Buckets && memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == 0) {
    for (int b = 0; b < Buckets; b++) {
      if (Group[b] != SG.Group[b]) return false;
    }
    return true;
  }
  return false;
}

template<class TVal , uint16 GroupSize>

const TVal& TSparseGroup< TVal, GroupSize >::operator[] ( const int  ValN ) const

inline

Definition at line 102 of file shash.h.

{ return Get(ValN); }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::PosToOffset ( const unsigned char *  BitSet, int  Pos  )

staticprivate

Definition at line 113 of file shash.h.

                                                                                   {
  static const int bits_in [256] = {      // # of bits set in one char
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
  };
  // [Note: condition pos > 8 is an optimization; convince yourself we
  // give exactly the same result as if we had pos >= 8 here instead.]
  int Offset = 0;
  for ( ; Pos > 8; Pos -= 8 )                        // bm[0..pos/8-1]
    Offset += bits_in[*BitSet++];                    // chars we want *all* bits in
  return Offset + bits_in[*BitSet & ((1 << Pos)-1)]; // the char that includes pos
}

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::PosToOffset ( int  Pos ) const

inline

Definition at line 97 of file shash.h.

{ return PosToOffset(BitSet, Pos); }

template<class TVal , uint16 GroupSize>

int TSparseGroup< TVal, GroupSize >::Reserved ( ) const

inline

Definition at line 87 of file shash.h.

{ return GroupSize; }

template<class TVal , uint16 GroupSize>

void TSparseGroup< TVal, GroupSize >::Save

(

TSOut &

SOut

)

const

Definition at line 159 of file shash.h.

                                                          {
  SOut.SaveBf(BitSet, sizeof(BitSet));
  SOut.Save(Buckets);
  for (int b = 0; b < Buckets; b++) { Group[b].Save(SOut); }
}

template<class TVal , uint16 GroupSize>

TVal & TSparseGroup< TVal, GroupSize >::Set	(	const int &	ValN,
		const TVal &	Val
	)

Definition at line 231 of file shash.h.

                                                                         {
  const int Offset = PosToOffset(BitSet, ValN);
  if (! BMTest(ValN)) {
    const TVal *OldGroup = Group;
    Group = new TVal [Buckets+1];
    for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
    for (int b = Offset+1; b <= Buckets; b++) Group[b] = OldGroup[b-1];
    if (OldGroup != NULL) delete [] OldGroup;
    Buckets++;
    BMSet(ValN);
  }
  Group[Offset] = Val;
  return Group[Offset];
}

template<class TVal , uint16 GroupSize>

TVal& TSparseGroup< TVal, GroupSize >::Set ( const int &  ValN )

inline

Definition at line 105 of file shash.h.

                             {
    if (! BMTest(ValN)) Set(ValN, DefVal());
    return Group[PosToOffset(BitSet, ValN)];
  }

Member Data Documentation

template<class TVal , uint16 GroupSize>

unsigned char TSparseGroup< TVal, GroupSize >::BitSet[(GroupSize-1)/8+1]

private

Definition at line 63 of file shash.h.

template<class TVal , uint16 GroupSize>

uint16 TSparseGroup< TVal, GroupSize >::Buckets

private

Definition at line 64 of file shash.h.

template<class TVal , uint16 GroupSize>

TVal* TSparseGroup< TVal, GroupSize >::Group

private

Definition at line 65 of file shash.h.

---

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

• glib-core/shash.h