SNAP Library , Developer Reference  2013-01-07 14:03:36
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 Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes
TSparseGroup< TVal, GroupSize > Class Template Reference

#include <shash.h>

List of all members.

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.

References TSparseGroup< TVal, GroupSize >::BitSet.

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

References TSparseGroup< TVal, GroupSize >::Load().

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

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>
TSparseGroup< TVal, GroupSize >::TSparseGroup ( const TSparseGroup< TVal, GroupSize > &  SG)

Definition at line 141 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

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

References TSparseGroup< TVal, GroupSize >::Group.

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

Member Function Documentation

template<class TVal , uint16 GroupSize>
void TSparseGroup< TVal, GroupSize >::BMClear ( const int &  ValN) [inline, private]

Definition at line 71 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::CharBit(), and TSparseGroup< TVal, GroupSize >::ModBit().

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

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>
void TSparseGroup< TVal, GroupSize >::BMSet ( const int &  ValN) [inline, private]

Definition at line 70 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::CharBit(), and TSparseGroup< TVal, GroupSize >::ModBit().

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

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>
bool TSparseGroup< TVal, GroupSize >::BMTest ( const int &  ValN) const [inline, private]

Definition at line 69 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::CharBit(), and TSparseGroup< TVal, GroupSize >::ModBit().

Referenced by TSparseGroup< TVal, GroupSize >::Get(), TSparseGroup< TVal, GroupSize >::IsEmpty(), and TSparseGroup< TVal, GroupSize >::Set().

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

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
static int TSparseGroup< TVal, GroupSize >::CharBit ( const int &  ValN) [inline, static, private]

Definition at line 67 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::BMClear(), TSparseGroup< TVal, GroupSize >::BMSet(), and TSparseGroup< TVal, GroupSize >::BMTest().

{ return ValN >> 3; }

Here is the caller graph for this function:

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.

Referenced by TSparseGroup< TVal, GroupSize >::Get(), and TSparseGroup< TVal, GroupSize >::Set().

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

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
void TSparseGroup< TVal, GroupSize >::Del ( const int &  ValN)

Definition at line 247 of file shash.h.

Referenced by TSparseTable< TVal, GroupSize >::Del().

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

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
bool TSparseGroup< TVal, GroupSize >::Empty ( ) const [inline]

Definition at line 88 of file shash.h.

References TSparseGroup< TVal, GroupSize >::Buckets.

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

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::BMTest(), TSparseGroup< TVal, GroupSize >::DefVal(), TSparseGroup< TVal, GroupSize >::Group, and TSparseGroup< TVal, GroupSize >::PosToOffset().

Referenced by TSparseGroup< TVal, GroupSize >::operator[]().

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

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
uint TSparseGroup< TVal, GroupSize >::GetDiskSz ( ) const [inline]

Definition at line 91 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, and TSparseGroup< TVal, GroupSize >::Buckets.

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

References TSparseGroup< TVal, GroupSize >::BMTest().

{ return ! BMTest(ValN); }

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::Len ( ) const [inline]

Definition at line 85 of file shash.h.

References TSparseGroup< TVal, GroupSize >::Buckets.

Referenced by TSparseTable< TVal, GroupSize >::Del(), and TSparseTable< TVal, GroupSize >::Set().

{ return Buckets; }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
void TSparseGroup< TVal, GroupSize >::Load ( TSIn &  SIn)

Definition at line 150 of file shash.h.

References TSIn::Load(), and TSIn::LoadBf().

Referenced by TSparseGroup< TVal, GroupSize >::TSparseGroup().

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

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
static int TSparseGroup< TVal, GroupSize >::ModBit ( const int &  ValN) [inline, static, private]

Definition at line 68 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::BMClear(), TSparseGroup< TVal, GroupSize >::BMSet(), and TSparseGroup< TVal, GroupSize >::BMTest().

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

Here is the caller graph for this function:

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.

References TSparseGroup< TVal, GroupSize >::Group.

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

References TSparseGroup< TVal, GroupSize >::Group.

{ return Group[Pos]; }
template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::OffsetToPos ( int  Offset) const

Definition at line 206 of file shash.h.

References Assert, Fail, and TB1Def::GetBit().

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

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>
bool TSparseGroup< TVal, GroupSize >::operator< ( const TSparseGroup< TVal, GroupSize > &  SG) const

Definition at line 196 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

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

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

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

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::Buckets, and TSparseGroup< TVal, GroupSize >::Group.

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

References TSparseGroup< TVal, GroupSize >::Get().

{ return Get(ValN); }

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::PosToOffset ( const unsigned char *  BitSet,
int  Pos 
) [static, private]

Definition at line 113 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Get(), and TSparseGroup< TVal, GroupSize >::Set().

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

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::PosToOffset ( int  Pos) const [inline]

Definition at line 97 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, and TSparseGroup< TVal, GroupSize >::PosToOffset().

Referenced by TSparseGroup< TVal, GroupSize >::PosToOffset().

{ return PosToOffset(BitSet, Pos); }

Here is the call graph for this function:

Here is the caller graph for this function:

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.

References TSOut::Save(), and TSOut::SaveBf().

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

Here is the call graph for this function:

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

Definition at line 231 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Set(), and TSparseTable< TVal, GroupSize >::Set().

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

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
TVal& TSparseGroup< TVal, GroupSize >::Set ( const int &  ValN) [inline]

Definition at line 105 of file shash.h.

References TSparseGroup< TVal, GroupSize >::BitSet, TSparseGroup< TVal, GroupSize >::BMTest(), TSparseGroup< TVal, GroupSize >::DefVal(), TSparseGroup< TVal, GroupSize >::Group, TSparseGroup< TVal, GroupSize >::PosToOffset(), and TSparseGroup< TVal, GroupSize >::Set().

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

Here is the call graph for this function:

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.

Referenced by TSparseGroup< TVal, GroupSize >::BMClear(), TSparseGroup< TVal, GroupSize >::BMSet(), TSparseGroup< TVal, GroupSize >::BMTest(), TSparseGroup< TVal, GroupSize >::Get(), TSparseGroup< TVal, GroupSize >::GetDiskSz(), TSparseGroup< TVal, GroupSize >::operator<(), TSparseGroup< TVal, GroupSize >::operator=(), TSparseGroup< TVal, GroupSize >::operator==(), TSparseGroup< TVal, GroupSize >::PosToOffset(), TSparseGroup< TVal, GroupSize >::Set(), and TSparseGroup< TVal, GroupSize >::TSparseGroup().

template<class TVal , uint16 GroupSize>
uint16 TSparseGroup< TVal, GroupSize >::Buckets [private]

Definition at line 64 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Empty(), TSparseGroup< TVal, GroupSize >::GetDiskSz(), TSparseGroup< TVal, GroupSize >::Len(), TSparseGroup< TVal, GroupSize >::operator<(), TSparseGroup< TVal, GroupSize >::operator=(), TSparseGroup< TVal, GroupSize >::operator==(), and TSparseGroup< TVal, GroupSize >::TSparseGroup().

template<class TVal , uint16 GroupSize>
TVal* TSparseGroup< TVal, GroupSize >::Group [private]

Definition at line 65 of file shash.h.

Referenced by TSparseGroup< TVal, GroupSize >::Get(), TSparseGroup< TVal, GroupSize >::Offset(), TSparseGroup< TVal, GroupSize >::operator<(), TSparseGroup< TVal, GroupSize >::operator=(), TSparseGroup< TVal, GroupSize >::operator==(), TSparseGroup< TVal, GroupSize >::Set(), TSparseGroup< TVal, GroupSize >::TSparseGroup(), and TSparseGroup< TVal, GroupSize >::~TSparseGroup().

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