SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
Public Member Functions | Private Attributes | List of all members
TSnapQueue< TVal > Class Template Reference

Fast Queue used by the TBreathFS (uses memcpy to move objects TVal around). More...

#include <gbase.h>

Collaboration diagram for TSnapQueue< TVal >:
Collaboration graph
[legend]

Public Member Functions

 TSnapQueue ()
 
 TSnapQueue (const int &MxVals)
 Constructor that reserves enough memory for a queue with MxVals elements. More...
 
 TSnapQueue (const int &MxVals, const int &MaxFirst)
 
 TSnapQueue (const TSnapQueue &Queue)
 
 TSnapQueue (TSIn &SIn)
 Constructor that loads the queue from a (binary) stream SIn. More...
 
void Save (TSOut &SOut) const
 Saves the queue to a (binary) stream SOut. More...
 
TSnapQueue & operator= (const TSnapQueue &Queue)
 
const TVal & operator[] (const int &ValN) const
 Returns the value of the ValN element in the queue, but does not remove the element. More...
 
void Clr (const bool &DoDel=true)
 Deletes all elements from the queue. More...
 
void Gen (const int &MxVals, const int &MaxFirst=1024)
 
bool Empty () const
 Tests whether the queue is empty (contains no elements). More...
 
int Len () const
 Returns the number of elements in the queue. More...
 
int GetFirst () const
 Returns the location of the first element in the queue. More...
 
int GetLast () const
 Returns the location of the last element in the queue. More...
 
int Reserved () const
 
const TVal & Top () const
 Returns the value of the first element in the queue, but does not remove the element. More...
 
void Pop ()
 Removes the first element from the queue. More...
 
void Push (const TVal &Val)
 Adds an element at the end of the queue. More...
 

Private Attributes

TInt MxFirst
 
TInt First
 
TInt Last
 
TVec< TVal > ValV
 

Detailed Description

template<class TVal>
class TSnapQueue< TVal >

Fast Queue used by the TBreathFS (uses memcpy to move objects TVal around).

Definition at line 158 of file gbase.h.

Constructor & Destructor Documentation

template<class TVal>
TSnapQueue< TVal >::TSnapQueue ( )
inline

Definition at line 164 of file gbase.h.

164 : MxFirst(1024), First(0), Last(0), ValV(MxFirst, 0) { }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
template<class TVal>
TSnapQueue< TVal >::TSnapQueue ( const int &  MxVals)
inline

Constructor that reserves enough memory for a queue with MxVals elements.

Definition at line 166 of file gbase.h.

166 : MxFirst(1024+MxVals/10), First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TInt::GetMx
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1182
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
template<class TVal>
TSnapQueue< TVal >::TSnapQueue ( const int &  MxVals,
const int &  MaxFirst 
)
inline

Definition at line 167 of file gbase.h.

167  : MxFirst(MaxFirst),
168  First(0), Last(0), ValV(TInt::GetMx(MxFirst, MxVals), 0) { }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TInt::GetMx
static int GetMx(const int &Int1, const int &Int2)
Definition: dt.h:1182
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
template<class TVal>
TSnapQueue< TVal >::TSnapQueue ( const TSnapQueue< TVal > &  Queue)
inline

Definition at line 169 of file gbase.h.

169 : MxFirst(Queue.MxFirst), First(Queue.First), Last(Queue.Last), ValV(Queue.ValV) { }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
template<class TVal>
TSnapQueue< TVal >::TSnapQueue ( TSIn &  SIn)
inlineexplicit

Constructor that loads the queue from a (binary) stream SIn.

Definition at line 171 of file gbase.h.

171 : MxFirst(SIn), First(SIn), Last(SIn), ValV(SIn) { }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160

Member Function Documentation

template<class TVal>
void TSnapQueue< TVal >::Clr ( const bool &  DoDel = true)
inline

Deletes all elements from the queue.

Definition at line 181 of file gbase.h.

181 { ValV.Clr(DoDel); First=Last=0; }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
template<class TVal>
bool TSnapQueue< TVal >::Empty ( ) const
inline

Tests whether the queue is empty (contains no elements).

Definition at line 186 of file gbase.h.

Referenced by TSnap::CascFind(), TSnap::CascFindMP(), and MAPPR::computeAPPR().

186 {return First==Last;}
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161

Here is the caller graph for this function:

template<class TVal>
void TSnapQueue< TVal >::Gen ( const int &  MxVals,
const int &  MaxFirst = 1024 
)
inline

Definition at line 182 of file gbase.h.

182  {
183  MxFirst=MaxFirst; First=Last=0; ValV.Gen(MxVals, 0); }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
template<class TVal>
int TSnapQueue< TVal >::GetFirst ( ) const
inline

Returns the location of the first element in the queue.

Definition at line 190 of file gbase.h.

190 { return First; }
TSnapQueue::First
TInt First
Definition: gbase.h:161
template<class TVal>
int TSnapQueue< TVal >::GetLast ( ) const
inline

Returns the location of the last element in the queue.

Definition at line 192 of file gbase.h.

192 { return Last; }
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
template<class TVal>
int TSnapQueue< TVal >::Len ( ) const
inline

Returns the number of elements in the queue.

Definition at line 188 of file gbase.h.

Referenced by TSnapQueue< int >::Push().

188 {return Last-First;}
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161

Here is the caller graph for this function:

template<class TVal>
TSnapQueue& TSnapQueue< TVal >::operator= ( const TSnapQueue< TVal > &  Queue)
inline

Definition at line 175 of file gbase.h.

175  { if (this != &Queue) { MxFirst=Queue.MxFirst;
176  First=Queue.First; Last=Queue.Last; ValV=Queue.ValV; } return *this; }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
template<class TVal>
const TVal& TSnapQueue< TVal >::operator[] ( const int &  ValN) const
inline

Returns the value of the ValN element in the queue, but does not remove the element.

Definition at line 178 of file gbase.h.

178 { return ValV[First+ValN]; }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
template<class TVal>
void TSnapQueue< TVal >::Pop ( )
inline

Removes the first element from the queue.

Definition at line 198 of file gbase.h.

Referenced by TSnap::CascFind(), TSnap::CascFindMP(), and MAPPR::computeAPPR().

198  { First++;
199  if (First==Last) { ValV.Clr(false); First=Last=0; } }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022

Here is the caller graph for this function:

template<class TVal>
void TSnapQueue< TVal >::Push ( const TVal &  Val)
inline

Adds an element at the end of the queue.

Definition at line 201 of file gbase.h.

Referenced by TSnap::CascFind(), TSnap::CascFindMP(), MAPPR::computeAPPR(), TSnap::GetNodeWcc(), TSnap::GetTreeSig(), and TSnap::IsWeaklyConn().

201  {
202  if (First>0 && (First > MxFirst || ValV.Len() == ValV.Reserved()) && ! ValV.Empty()) {
203  //printf("[move cc queue.Len:%d-->%d]", ValV.Len(),Len()); TExeTm Tm;
204  memmove(ValV.BegI(), ValV.GetI(First), sizeof(TVal)*Len());
205  ValV.Del(Len(), ValV.Len()-1); Last-=First; First=0;
206  //printf("[%s]\n", Tm.GetStr()); fflush(stdout);
207  }
208  //if (ValV.Len() == ValV.Reserved()){ printf("[resizeCCQ]"); fflush(stdout); }
209  Last++; ValV.Add(Val);
210  }
TVec::Reserved
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TVec::Del
void Del(const TSizeTy &ValN)
Removes the element at position ValN.
Definition: ds.h:1189
TSnapQueue::First
TInt First
Definition: gbase.h:161
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
TSnapQueue::Len
int Len() const
Returns the number of elements in the queue.
Definition: gbase.h:188
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TVec::GetI
TIter GetI(const TSizeTy &ValN) const
Returns an iterator an element at position ValN.
Definition: ds.h:597

Here is the caller graph for this function:

template<class TVal>
int TSnapQueue< TVal >::Reserved ( ) const
inline

Definition at line 193 of file gbase.h.

193 { return ValV.Reserved(); }
TVec::Reserved
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
template<class TVal>
void TSnapQueue< TVal >::Save ( TSOut &  SOut) const
inline

Saves the queue to a (binary) stream SOut.

Definition at line 173 of file gbase.h.

173 { MxFirst.Save(SOut); First.Save(SOut); Last.Save(SOut); ValV.Save(SOut); }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1150
TSnapQueue::Last
TInt Last
Definition: gbase.h:161
TVec::Save
void Save(TSOut &SOut) const
Definition: ds.h:954
TSnapQueue::MxFirst
TInt MxFirst
Definition: gbase.h:160
template<class TVal>
const TVal& TSnapQueue< TVal >::Top ( ) const
inline

Returns the value of the first element in the queue, but does not remove the element.

Definition at line 196 of file gbase.h.

Referenced by TSnap::CascFind(), TSnap::CascFindMP(), and MAPPR::computeAPPR().

196 { return ValV[First]; }
TSnapQueue::ValV
TVec< TVal > ValV
Definition: gbase.h:162
TSnapQueue::First
TInt First
Definition: gbase.h:161

Here is the caller graph for this function:

Member Data Documentation

template<class TVal>
TInt TSnapQueue< TVal >::First
private

Definition at line 161 of file gbase.h.

Referenced by TSnapQueue< int >::Clr(), TSnapQueue< int >::Empty(), TSnapQueue< int >::Gen(), TSnapQueue< int >::GetFirst(), TSnapQueue< int >::Len(), TSnapQueue< int >::operator=(), TSnapQueue< int >::operator[](), TSnapQueue< int >::Pop(), TSnapQueue< int >::Push(), TSnapQueue< int >::Save(), and TSnapQueue< int >::Top().

template<class TVal>
TInt TSnapQueue< TVal >::Last
private

Definition at line 161 of file gbase.h.

Referenced by TSnapQueue< int >::Clr(), TSnapQueue< int >::Empty(), TSnapQueue< int >::Gen(), TSnapQueue< int >::GetLast(), TSnapQueue< int >::Len(), TSnapQueue< int >::operator=(), TSnapQueue< int >::Pop(), TSnapQueue< int >::Push(), and TSnapQueue< int >::Save().

template<class TVal>
TInt TSnapQueue< TVal >::MxFirst
private

Definition at line 160 of file gbase.h.

Referenced by TSnapQueue< int >::Gen(), TSnapQueue< int >::operator=(), TSnapQueue< int >::Push(), and TSnapQueue< int >::Save().

template<class TVal>
TVec<TVal> TSnapQueue< TVal >::ValV
private

Definition at line 162 of file gbase.h.

Referenced by TSnapQueue< int >::Clr(), TSnapQueue< int >::Gen(), TSnapQueue< int >::operator=(), TSnapQueue< int >::operator[](), TSnapQueue< int >::Pop(), TSnapQueue< int >::Push(), TSnapQueue< int >::Reserved(), TSnapQueue< int >::Save(), and TSnapQueue< int >::Top().

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