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 Types | Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes
TSparseTable< TVal, GroupSize > Class Template Reference

#include <shash.h>

Collaboration diagram for TSparseTable< TVal, GroupSize >:
Collaboration graph
[legend]

List of all members.

Public Types

typedef TSparseGroup< TVal,
GroupSize > 		TSGroup
typedef TSparseTableI< TVal,
GroupSize > 		TIter

Public Member Functions

 TSparseTable (const int &MaxVals=0)
 TSparseTable (const TSparseTable &ST)
 TSparseTable (TSIn &SIn)
void Load (TSIn &SIn)
void Save (TSOut &SOut) const
TSparseTable & operator= (const TSparseTable &ST)
bool operator== (const TSparseTable &ST) const
bool operator< (const TSparseTable &ST) const
::TSize GetMemUsed () const
TIter BegI () const
TIter EndI () const
TIter GetI (const int &ValN) const
int Len () const
int Reserved () const
int Groups () const
bool Empty () const
uint GetDiskSz () const
void Clr (const bool &DoDel=true)
void Reserve (const int NewVals)
void Resize (const int &NewVals)
void Swap (TSparseTable &ST)
bool IsEmpty (const int &ValN) const
const TVal & Get (const int &ValN) const
TVal & Set (const int &ValN, const TVal &Val)
TVal & Set (const int &ValN)
void Del (const int &ValN)
TSGroup & GetGroup (const int &GroupN)
const TSGroup & GetGroup (const int &GroupN) const

Private Member Functions

int PosInGroup (const int &ValN) const
int GroupNum (const int &ValN) const
const TSGroup & GetGrp1 (const int &ValN) const
TSGroup & GetGrp1 (const int &ValN)

Static Private Member Functions

static int GetGroups (const int &Vals)

Private Attributes

TInt MxVals
TInt Vals
TVec< TSGroup > GroupV

Detailed Description

template<class TVal, uint16 GroupSize = 48>
class TSparseTable< TVal, GroupSize >

Definition at line 310 of file shash.h.

Member Typedef Documentation

template<class TVal, uint16 GroupSize = 48>
typedef TSparseTableI<TVal, GroupSize> TSparseTable< TVal, GroupSize >::TIter

Definition at line 313 of file shash.h.

template<class TVal, uint16 GroupSize = 48>
typedef TSparseGroup<TVal, GroupSize> TSparseTable< TVal, GroupSize >::TSGroup

Definition at line 312 of file shash.h.

Constructor & Destructor Documentation

template<class TVal, uint16 GroupSize = 48>
TSparseTable< TVal, GroupSize >::TSparseTable ( const int &  MaxVals = 0) [inline]

Definition at line 324 of file shash.h.

                                       : MxVals(MaxVals),
    Vals(0), GroupV(GetGroups(MaxVals), GetGroups(MaxVals)) { }
template<class TVal, uint16 GroupSize = 48>
TSparseTable< TVal, GroupSize >::TSparseTable ( const TSparseTable< TVal, GroupSize > &  ST) [inline]

Definition at line 326 of file shash.h.

: MxVals(ST.MxVals), Vals(ST.Vals), GroupV(ST.GroupV) { }
template<class TVal, uint16 GroupSize = 48>
TSparseTable< TVal, GroupSize >::TSparseTable ( TSIn &  SIn) [inline]

Definition at line 327 of file shash.h.

: MxVals(SIn), Vals(SIn), GroupV(SIn) { }

Member Function Documentation

template<class TVal, uint16 GroupSize = 48>
TIter TSparseTable< TVal, GroupSize >::BegI ( ) const [inline]

Definition at line 336 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::BegI(), and TSparseSet< TKey, GroupSize >::BegI().

                     {
    if (Len() > 0) { int B = 0;
      while (B < Groups() && GroupV[B].Empty()) { B++; }
      return TIter(GroupV.BegI(), GroupV.BegI()+B, GroupV.EndI()); }
    return TIter(GroupV.BegI(), GroupV.EndI(), GroupV.EndI());
  }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
void TSparseTable< TVal, GroupSize >::Clr ( const bool &  DoDel = true)

Definition at line 392 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::Clr(), and TSparseSet< TKey, GroupSize >::Clr().

                                                         {
  if (! DoDel) {
    for (int g = 0; g < GroupV.Len(); g++) GroupV[g].Clr(false);
  } else {
    MxVals = 0;
    GroupV.Clr(true);
  }
  Vals = 0;
}

Here is the caller graph for this function:

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

Definition at line 440 of file shash.h.

References Assert, TSparseGroup< TVal, GroupSize >::Del(), and TSparseGroup< TVal, GroupSize >::Len().

                                                       {
  Assert(ValN < MxVals);
  TSGroup& Group = GetGrp1(ValN);
  const int OldVals = Group.Len();
  Group.Del(PosInGroup(ValN));
  Vals += Group.Len() - OldVals;
}

Here is the call graph for this function:

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

Definition at line 352 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::BegI().

{ return Vals == 0; }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
TIter TSparseTable< TVal, GroupSize >::EndI ( ) const [inline]

Definition at line 342 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::EndI(), and TSparseSet< TKey, GroupSize >::EndI().

{ return TIter(GroupV.BegI(), GroupV.EndI(), GroupV.EndI()); }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
const TVal& TSparseTable< TVal, GroupSize >::Get ( const int &  ValN) const [inline]

Definition at line 362 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetDatKeyId(), TSparseHash< TKey, TDat, GroupSize >::GetKey(), and TSparseSet< TKey, GroupSize >::GetKey().

{ return GroupV[GroupNum(ValN)].Get(PosInGroup(ValN)); }

Here is the caller graph for this function:

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

Definition at line 353 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetDiskSz(), and TSparseSet< TKey, GroupSize >::GetDiskSz().

                         {
    return sizeof(TInt)*4 + ((GroupSize+16)/8)*Groups() + sizeof(TVal)*Vals; }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
TSGroup& TSparseTable< TVal, GroupSize >::GetGroup ( const int &  GroupN) [inline]

Definition at line 367 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::CopyFrom(), TSparseSet< TKey, GroupSize >::CopyFrom(), TSparseHash< TKey, TDat, GroupSize >::MoveFrom(), and TSparseSet< TKey, GroupSize >::MoveFrom().

{ return GroupV[GroupN]; }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
const TSGroup& TSparseTable< TVal, GroupSize >::GetGroup ( const int &  GroupN) const [inline]

Definition at line 368 of file shash.h.

{ return GroupV[GroupN]; }
template<class TVal, uint16 GroupSize = 48>
static int TSparseTable< TVal, GroupSize >::GetGroups ( const int &  Vals) [inline, static, private]

Definition at line 318 of file shash.h.

{ return Vals == 0 ? 0 : ((Vals-1) / GroupSize) + 1; }
template<class TVal, uint16 GroupSize = 48>
const TSGroup& TSparseTable< TVal, GroupSize >::GetGrp1 ( const int &  ValN) const [inline, private]

Definition at line 321 of file shash.h.

{ return GroupV[GroupNum(ValN)]; }
template<class TVal, uint16 GroupSize = 48>
TSGroup& TSparseTable< TVal, GroupSize >::GetGrp1 ( const int &  ValN) [inline, private]

Definition at line 322 of file shash.h.

{ return GroupV[GroupNum(ValN)]; }
template<class TVal, uint16 GroupSize = 48>
TIter TSparseTable< TVal, GroupSize >::GetI ( const int &  ValN) const [inline]

Definition at line 343 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetI(), and TSparseSet< TKey, GroupSize >::GetI().

                                    { Assert(! IsEmpty(ValN));
    typedef typename TVec<TSGroup>::TIter TVIter;
    const TVIter GI = GroupV.GetI(GroupNum(ValN));
    return TIter(GroupV.BegI(), GI, GroupV.EndI(), GI->PosToOffset(PosInGroup(ValN)));
  }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
::TSize TSparseTable< TVal, GroupSize >::GetMemUsed ( ) const [inline]

Definition at line 334 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetMemUsed(), and TSparseSet< TKey, GroupSize >::GetMemUsed().

{ return 2*sizeof(TInt)+Vals*sizeof(TVal)+GroupV.GetMemUsed(); }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
int TSparseTable< TVal, GroupSize >::GroupNum ( const int &  ValN) const [inline, private]

Definition at line 320 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::Get(), TSparseTable< THashKeyDat, GroupSize >::GetGrp1(), TSparseTable< THashKeyDat, GroupSize >::GetI(), and TSparseTable< THashKeyDat, GroupSize >::IsEmpty().

{ return ValN / GroupSize; }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
int TSparseTable< TVal, GroupSize >::Groups ( ) const [inline]

Definition at line 351 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::BegI(), TSparseHash< TKey, TDat, GroupSize >::CopyFrom(), TSparseSet< TKey, GroupSize >::CopyFrom(), TSparseTable< THashKeyDat, GroupSize >::GetDiskSz(), TSparseHash< TKey, TDat, GroupSize >::MoveFrom(), and TSparseSet< TKey, GroupSize >::MoveFrom().

{ return GroupV.Len(); }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
bool TSparseTable< TVal, GroupSize >::IsEmpty ( const int &  ValN) const [inline]

Definition at line 361 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::GetI(), TSparseHash< TKey, TDat, GroupSize >::IsKeyId(), and TSparseSet< TKey, GroupSize >::IsKeyId().

{ return GroupV[GroupNum(ValN)].IsEmpty(PosInGroup(ValN)); }

Here is the caller graph for this function:

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

Definition at line 349 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::BegI(), TSparseHash< TKey, TDat, GroupSize >::Len(), and TSparseSet< TKey, GroupSize >::Len().

{ return Vals; }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
void TSparseTable< TVal, GroupSize >::Load ( TSIn &  SIn) [inline]

Definition at line 328 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::Load(), and TSparseSet< TKey, GroupSize >::Load().

{ MxVals.Load(SIn);  Vals.Load(SIn);  GroupV.Load(SIn); }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
bool TSparseTable< TVal, GroupSize >::operator< ( const TSparseTable< TVal, GroupSize > &  ST) const

Definition at line 387 of file shash.h.

References TSparseTable< TVal, GroupSize >::GroupV, and TSparseTable< TVal, GroupSize >::Vals.

                                                                            {
  return Vals < ST.Vals || (Vals == ST.Vals && GroupV < ST.GroupV);
}
template<class TVal , uint16 GroupSize>
TSparseTable< TVal, GroupSize > & TSparseTable< TVal, GroupSize >::operator= ( const TSparseTable< TVal, GroupSize > &  ST)

Definition at line 372 of file shash.h.

References TSparseTable< TVal, GroupSize >::GroupV, TSparseTable< TVal, GroupSize >::MxVals, and TSparseTable< TVal, GroupSize >::Vals.

                                                                                                {
  if (this != &ST) {
    MxVals = ST.MxVals;
    Vals = ST.Vals;
    GroupV = ST.GroupV;
  }
  return *this;
}
template<class TVal , uint16 GroupSize>
bool TSparseTable< TVal, GroupSize >::operator== ( const TSparseTable< TVal, GroupSize > &  ST) const

Definition at line 382 of file shash.h.

References TSparseTable< TVal, GroupSize >::GroupV, TSparseTable< TVal, GroupSize >::MxVals, and TSparseTable< TVal, GroupSize >::Vals.

                                                                             {
  return Vals == ST.Vals && MxVals == ST.MxVals && GroupV == ST.GroupV;
}
template<class TVal, uint16 GroupSize = 48>
int TSparseTable< TVal, GroupSize >::PosInGroup ( const int &  ValN) const [inline, private]

Definition at line 319 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::Get(), TSparseTable< THashKeyDat, GroupSize >::GetI(), and TSparseTable< THashKeyDat, GroupSize >::IsEmpty().

{ return ValN % GroupSize; }

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
void TSparseTable< TVal, GroupSize >::Reserve ( const int  NewVals) [inline]

Definition at line 357 of file shash.h.

{ Resize(NewVals); }
template<class TVal, uint16 GroupSize = 48>
int TSparseTable< TVal, GroupSize >::Reserved ( ) const [inline]

Definition at line 350 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::Reserved(), and TSparseSet< TKey, GroupSize >::Reserved().

{ return MxVals; }

Here is the caller graph for this function:

template<class TVal , uint16 GroupSize>
void TSparseTable< TVal, GroupSize >::Resize ( const int &  NewVals)

Definition at line 403 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::Reserve().

                                                             {
  // only allow to grow
  if (NewVals > MxVals) {
    const int Groups = GetGroups(NewVals);
    GroupV.Reserve(Groups, Groups);
    MxVals = NewVals;
  }
}

Here is the caller graph for this function:

template<class TVal, uint16 GroupSize = 48>
void TSparseTable< TVal, GroupSize >::Save ( TSOut &  SOut) const [inline]

Definition at line 329 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::Save(), and TSparseSet< TKey, GroupSize >::Save().

{ MxVals.Save(SOut);  Vals.Save(SOut);  GroupV.Save(SOut); }

Here is the caller graph for this function:

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

Definition at line 420 of file shash.h.

References Assert, TSparseGroup< TVal, GroupSize >::Len(), and TSparseGroup< TVal, GroupSize >::Set().

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetDatKeyId().

                                                                         {
  Assert(ValN < MxVals);
  TSGroup& Group = GetGrp1(ValN);
  const int OldVals = Group.Len();
  TVal& ValRef = Group.Set(PosInGroup(ValN), Val);
  Vals += Group.Len() - OldVals;
  return ValRef;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 430 of file shash.h.

References Assert, TSparseGroup< TVal, GroupSize >::Len(), and TSparseGroup< TVal, GroupSize >::Set().

                                                        {
  Assert(ValN < MxVals);
  TSGroup& Group = GetGrp1(ValN);
  const int OldVals = Group.Len();
  TVal& ValRef = Group.Set(PosInGroup(ValN));
  Vals += Group.Len() - OldVals;
  return ValRef;
}

Here is the call graph for this function:

template<class TVal , uint16 GroupSize>
void TSparseTable< TVal, GroupSize >::Swap ( TSparseTable< TVal, GroupSize > &  ST)

Definition at line 413 of file shash.h.

References TSparseTable< TVal, GroupSize >::GroupV, TSparseTable< TVal, GroupSize >::MxVals, Swap(), and TSparseTable< TVal, GroupSize >::Vals.

                                                         {
  ::Swap(MxVals, ST.MxVals);
  ::Swap(Vals, ST.Vals);
  GroupV.Swap(ST.GroupV);
}

Here is the call graph for this function:

Member Data Documentation

template<class TVal, uint16 GroupSize = 48>
TVec<TSGroup> TSparseTable< TVal, GroupSize >::GroupV [private]

Definition at line 316 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::BegI(), TSparseTable< THashKeyDat, GroupSize >::EndI(), TSparseTable< THashKeyDat, GroupSize >::Get(), TSparseTable< THashKeyDat, GroupSize >::GetGroup(), TSparseTable< THashKeyDat, GroupSize >::GetGrp1(), TSparseTable< THashKeyDat, GroupSize >::GetI(), TSparseTable< THashKeyDat, GroupSize >::GetMemUsed(), TSparseTable< THashKeyDat, GroupSize >::Groups(), TSparseTable< THashKeyDat, GroupSize >::IsEmpty(), TSparseTable< THashKeyDat, GroupSize >::Load(), TSparseTable< TVal, GroupSize >::operator<(), TSparseTable< TVal, GroupSize >::operator=(), TSparseTable< TVal, GroupSize >::operator==(), TSparseTable< THashKeyDat, GroupSize >::Save(), and TSparseTable< TVal, GroupSize >::Swap().

template<class TVal, uint16 GroupSize = 48>
TInt TSparseTable< TVal, GroupSize >::MxVals [private]

Definition at line 315 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::Load(), TSparseTable< TVal, GroupSize >::operator=(), TSparseTable< TVal, GroupSize >::operator==(), TSparseTable< THashKeyDat, GroupSize >::Reserved(), TSparseTable< THashKeyDat, GroupSize >::Save(), and TSparseTable< TVal, GroupSize >::Swap().

template<class TVal, uint16 GroupSize = 48>
TInt TSparseTable< TVal, GroupSize >::Vals [private]

Definition at line 315 of file shash.h.

Referenced by TSparseTable< THashKeyDat, GroupSize >::Empty(), TSparseTable< THashKeyDat, GroupSize >::GetDiskSz(), TSparseTable< THashKeyDat, GroupSize >::GetMemUsed(), TSparseTable< THashKeyDat, GroupSize >::Len(), TSparseTable< THashKeyDat, GroupSize >::Load(), TSparseTable< TVal, GroupSize >::operator<(), TSparseTable< TVal, GroupSize >::operator=(), TSparseTable< TVal, GroupSize >::operator==(), TSparseTable< THashKeyDat, GroupSize >::Save(), and TSparseTable< TVal, GroupSize >::Swap().

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