SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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
 
TSparseGroupoperator= (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.

74 : Buckets(0), Group(NULL) { memset(BitSet, 0, sizeof(BitSet)); }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
TSparseGroup< TVal, GroupSize >::TSparseGroup ( TSIn SIn)
inline

Definition at line 75 of file shash.h.

75 : Buckets(0), Group(NULL) { Load(SIn); }
TVal * Group
Definition: shash.h:65
void Load(TSIn &SIn)
Definition: shash.h:150
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
TSparseGroup< TVal, GroupSize >::TSparseGroup ( const TSparseGroup< TVal, GroupSize > &  SG)

Definition at line 141 of file shash.h.

141  : Buckets(SG.Buckets), Group(NULL) {
142  memcpy(BitSet, SG.BitSet, sizeof(BitSet));
143  if (Buckets > 0) {
144  Group = new TVal [Buckets];
145  for (int b = 0; b < Buckets; b++) { Group[b] = SG.Group[b]; }
146  }
147 }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
TSparseGroup< TVal, GroupSize >::~TSparseGroup ( )
inline

Definition at line 77 of file shash.h.

77 { if (Group != NULL) delete [] Group; }
TVal * Group
Definition: shash.h:65

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.

71 { BitSet[CharBit(ValN)] &= ~ModBit(ValN); }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
static int ModBit(const int &ValN)
Definition: shash.h:68
static int CharBit(const int &ValN)
Definition: shash.h:67
template<class TVal , uint16 GroupSize>
void TSparseGroup< TVal, GroupSize >::BMSet ( const int &  ValN)
inlineprivate

Definition at line 70 of file shash.h.

70 { BitSet[CharBit(ValN)] |= ModBit(ValN); }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
static int ModBit(const int &ValN)
Definition: shash.h:68
static int CharBit(const int &ValN)
Definition: shash.h:67
template<class TVal , uint16 GroupSize>
bool TSparseGroup< TVal, GroupSize >::BMTest ( const int &  ValN) const
inlineprivate

Definition at line 69 of file shash.h.

69 { return (BitSet[CharBit(ValN)] & ModBit(ValN)) != 0; }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
static int ModBit(const int &ValN)
Definition: shash.h:68
static int CharBit(const int &ValN)
Definition: shash.h:67
template<class TVal , uint16 GroupSize>
static int TSparseGroup< TVal, GroupSize >::CharBit ( const int &  ValN)
inlinestaticprivate

Definition at line 67 of file shash.h.

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

221  {
222  if (DoDel && Group != NULL) {
223  delete [] Group;
224  Group = 0;
225  }
226  memset(BitSet, 0, sizeof(BitSet));
227  Buckets = 0;
228 }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
const TVal& TSparseGroup< TVal, GroupSize >::DefVal ( ) const
inline

Definition at line 99 of file shash.h.

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

247  {
248  if (BMTest(ValN)) {
249  const int Offset = PosToOffset(BitSet, ValN);
250  if (--Buckets == 0) {
251  delete [] Group;
252  Group = 0;
253  } else {
254  const TVal *OldGroup = Group;
255  Group = new TVal [Buckets];
256  for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
257  for (int b = Offset+1; b <= Buckets; b++) Group[b-1] = OldGroup[b];
258  if (OldGroup != NULL) delete [] OldGroup;
259  }
260  BMClear(ValN);
261  }
262 }
const TVal & Offset(const int &Pos) const
Definition: shash.h:94
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
static int PosToOffset(const unsigned char *BitSet, int Pos)
Definition: shash.h:113
bool BMTest(const int &ValN) const
Definition: shash.h:69
void BMClear(const int &ValN)
Definition: shash.h:71
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
bool TSparseGroup< TVal, GroupSize >::Empty ( ) const
inline

Definition at line 88 of file shash.h.

88 { return Buckets == 0; }
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
const TVal& TSparseGroup< TVal, GroupSize >::Get ( const int &  ValN) const
inline

Definition at line 100 of file shash.h.

100  {
101  if (BMTest(ValN)) return Group[PosToOffset(BitSet, ValN)]; else return DefVal(); }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
const TVal & DefVal() const
Definition: shash.h:99
static int PosToOffset(const unsigned char *BitSet, int Pos)
Definition: shash.h:113
bool BMTest(const int &ValN) const
Definition: shash.h:69
TVal * Group
Definition: shash.h:65
template<class TVal , uint16 GroupSize>
uint TSparseGroup< TVal, GroupSize >::GetDiskSz ( ) const
inline

Definition at line 91 of file shash.h.

91 { return sizeof(BitSet) + sizeof(uint16) + Buckets*sizeof(TVal); }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
unsigned short uint16
Definition: bd.h:31
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::GetGroupSize ( ) const
inline

Definition at line 90 of file shash.h.

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

93 { return ! BMTest(ValN); }
bool BMTest(const int &ValN) const
Definition: shash.h:69
template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::Len ( ) const
inline

Definition at line 85 of file shash.h.

85 { return Buckets; }
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
void TSparseGroup< TVal, GroupSize >::Load ( TSIn SIn)

Definition at line 150 of file shash.h.

150  {
151  SIn.LoadBf(BitSet, sizeof(BitSet));
152  SIn.Load(Buckets);
153  if (Group != NULL) delete [] Group;
154  Group = new TVal [Buckets];
155  for (int b = 0; b < Buckets; b++) { Group[b] = TVal(SIn); }
156 }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
void Load(bool &Bool)
Definition: fl.h:84
void LoadBf(const void *Bf, const TSize &BfL)
Definition: fl.h:81
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
static int TSparseGroup< TVal, GroupSize >::ModBit ( const int &  ValN)
inlinestaticprivate

Definition at line 68 of file shash.h.

68 { return 1 << (ValN&7); }
template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::MxLen ( ) const
inline

Definition at line 86 of file shash.h.

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

94 { return Group[Pos]; }
TVal * Group
Definition: shash.h:65
template<class TVal , uint16 GroupSize>
TVal& TSparseGroup< TVal, GroupSize >::Offset ( const int &  Pos)
inline

Definition at line 95 of file shash.h.

95 { return Group[Pos]; }
TVal * Group
Definition: shash.h:65
template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::OffsetToPos ( int  Offset) const

Definition at line 206 of file shash.h.

206  {
207  Assert(Offset < Buckets);
208  for (int i = 0; i < sizeof(BitSet); i++) {
209  for (int b = 0; b < 8; b++) {
210  if (TB1Def::GetBit(b, BitSet[i])) {
211  if (Offset == 0) return i*8 + b;
212  Offset--;
213  }
214  }
215  }
216  Fail;
217  return -1;
218 }
const TVal & Offset(const int &Pos) const
Definition: shash.h:94
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
#define Fail
Definition: bd.h:238
static bool GetBit(const int &BitN, const uchar &Val)
Definition: bits.cpp:33
#define Assert(Cond)
Definition: bd.h:251
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
bool TSparseGroup< TVal, GroupSize >::operator< ( const TSparseGroup< TVal, GroupSize > &  SG) const

Definition at line 196 of file shash.h.

196  {
197  if (Buckets < SG.Buckets) return true;
198  if (memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == -1) return true;
199  for (int b = 0; b < Buckets; b++) {
200  if (Group[b] < SG.Group[b]) return true;
201  }
202  return false;
203 }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
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.

166  {
167  if (this != &SG) {
168  if (SG.Buckets == 0 && Group != NULL) {
169  delete [] Group;
170  Group = 0;
171  } else {
172  if (Buckets != SG.Buckets) {
173  if (Group != NULL) delete [] Group;
174  Group = new TVal [SG.Buckets];
175  }
176  for (int b = 0; b < SG.Buckets; b++) { Group[b] = SG.Group[b]; }
177  }
178  Buckets = SG.Buckets;
179  memcpy(BitSet, SG.BitSet, sizeof(BitSet));
180  }
181  return *this;
182 }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
bool TSparseGroup< TVal, GroupSize >::operator== ( const TSparseGroup< TVal, GroupSize > &  SG) const

Definition at line 185 of file shash.h.

185  {
186  if (Buckets == SG.Buckets && memcmp(BitSet, SG.BitSet, sizeof(BitSet)) == 0) {
187  for (int b = 0; b < Buckets; b++) {
188  if (Group[b] != SG.Group[b]) return false;
189  }
190  return true;
191  }
192  return false;
193 }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
const TVal& TSparseGroup< TVal, GroupSize >::operator[] ( const int  ValN) const
inline

Definition at line 102 of file shash.h.

102 { return Get(ValN); }
const TVal & Get(const int &ValN) const
Definition: shash.h:100
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.

113  {
114  static const int bits_in [256] = { // # of bits set in one char
115  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
116  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
117  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
118  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
119  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
120  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
121  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
122  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
123  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
124  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
125  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
126  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
127  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
128  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
129  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
130  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
131  };
132  // [Note: condition pos > 8 is an optimization; convince yourself we
133  // give exactly the same result as if we had pos >= 8 here instead.]
134  int Offset = 0;
135  for ( ; Pos > 8; Pos -= 8 ) // bm[0..pos/8-1]
136  Offset += bits_in[*BitSet++]; // chars we want *all* bits in
137  return Offset + bits_in[*BitSet & ((1 << Pos)-1)]; // the char that includes pos
138 }
const TVal & Offset(const int &Pos) const
Definition: shash.h:94
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::PosToOffset ( int  Pos) const
inline

Definition at line 97 of file shash.h.

97 { return PosToOffset(BitSet, Pos); }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
static int PosToOffset(const unsigned char *BitSet, int Pos)
Definition: shash.h:113
template<class TVal , uint16 GroupSize>
int TSparseGroup< TVal, GroupSize >::Reserved ( ) const
inline

Definition at line 87 of file shash.h.

87 { return GroupSize; }
template<class TVal , uint16 GroupSize>
void TSparseGroup< TVal, GroupSize >::Save ( TSOut SOut) const

Definition at line 159 of file shash.h.

159  {
160  SOut.SaveBf(BitSet, sizeof(BitSet));
161  SOut.Save(Buckets);
162  for (int b = 0; b < Buckets; b++) { Group[b].Save(SOut); }
163 }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
void SaveBf(const void *Bf, const TSize &BfL)
Definition: fl.h:172
void Save(const bool &Bool)
Definition: fl.h:173
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
TVal & TSparseGroup< TVal, GroupSize >::Set ( const int &  ValN,
const TVal &  Val 
)

Definition at line 231 of file shash.h.

231  {
232  const int Offset = PosToOffset(BitSet, ValN);
233  if (! BMTest(ValN)) {
234  const TVal *OldGroup = Group;
235  Group = new TVal [Buckets+1];
236  for (int b = 0; b < Offset; b++) Group[b] = OldGroup[b];
237  for (int b = Offset+1; b <= Buckets; b++) Group[b] = OldGroup[b-1];
238  if (OldGroup != NULL) delete [] OldGroup;
239  Buckets++;
240  BMSet(ValN);
241  }
242  Group[Offset] = Val;
243  return Group[Offset];
244 }
const TVal & Offset(const int &Pos) const
Definition: shash.h:94
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
void BMSet(const int &ValN)
Definition: shash.h:70
static int PosToOffset(const unsigned char *BitSet, int Pos)
Definition: shash.h:113
bool BMTest(const int &ValN) const
Definition: shash.h:69
TVal * Group
Definition: shash.h:65
uint16 Buckets
Definition: shash.h:64
template<class TVal , uint16 GroupSize>
TVal& TSparseGroup< TVal, GroupSize >::Set ( const int &  ValN)
inline

Definition at line 105 of file shash.h.

105  {
106  if (! BMTest(ValN)) Set(ValN, DefVal());
107  return Group[PosToOffset(BitSet, ValN)];
108  }
unsigned char BitSet[(GroupSize-1)/8+1]
Definition: shash.h:63
const TVal & DefVal() const
Definition: shash.h:99
static int PosToOffset(const unsigned char *BitSet, int Pos)
Definition: shash.h:113
bool BMTest(const int &ValN) const
Definition: shash.h:69
TVal & Set(const int &ValN, const TVal &Val)
Definition: shash.h:231
TVal * Group
Definition: shash.h:65

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: