SNAP Library 2.4, User Reference  2015-05-11 19:40:56
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
Classes | Public Types | Public Member Functions | Protected Types | Protected Attributes | List of all members
TUniTrie< TItem_ > Class Template Reference

#include <unicode.h>

Classes

class  TNode
 

Public Types

typedef TItem_ TItem
 

Public Member Functions

 TUniTrie ()
 
void Clr ()
 
bool Empty () const
 
bool Has1Gram (const TItem &item) const
 
bool Has2Gram (const TItem &last, const TItem &butLast) const
 
int Get3GramRoot (const TItem &last, const TItem &butLast, const TItem &butButLast) const
 
int GetChild (const int parentIdx, const TItem &item) const
 
bool IsNodeTerminal (const int nodeIdx) const
 
template<typename TSrcVec >
void Add (const TSrcVec &src, const size_t srcIdx, const size_t srcCount)
 
template<typename TSrcVec >
void Add (const TSrcVec &src)
 

Protected Types

typedef TVec< TNode > TNodeV
 
typedef TPair< TItem, TItem > TItemPr
 
typedef TTriple< TItem, TItem,
TItem > 		TItemTr
 
typedef TUniVecIdx TVecIdx
 

Protected Attributes

THash< TItem, TVoid > singles
 
THash< TItemPr, TVoid > pairs
 
THash< TItemTr, TInt > roots
 
TNodeV nodes
 

Detailed Description

template<typename TItem_>
class TUniTrie< TItem_ >

Definition at line 1177 of file unicode.h.

Member Typedef Documentation

template<typename TItem_>
typedef TItem_ TUniTrie< TItem_ >::TItem

Definition at line 1180 of file unicode.h.

template<typename TItem_>
typedef TPair<TItem, TItem> TUniTrie< TItem_ >::TItemPr
protected

Definition at line 1191 of file unicode.h.

template<typename TItem_>
typedef TTriple<TItem, TItem, TItem> TUniTrie< TItem_ >::TItemTr
protected

Definition at line 1192 of file unicode.h.

template<typename TItem_>
typedef TVec<TNode> TUniTrie< TItem_ >::TNodeV
protected

Definition at line 1190 of file unicode.h.

template<typename TItem_>
typedef TUniVecIdx TUniTrie< TItem_ >::TVecIdx
protected

Definition at line 1193 of file unicode.h.

Constructor & Destructor Documentation

template<typename TItem_>
TUniTrie< TItem_ >::TUniTrie ( )
inline

Definition at line 1199 of file unicode.h.

1199 { }

Member Function Documentation

template<typename TItem_>
template<typename TSrcVec >
void TUniTrie< TItem_ >::Add ( const TSrcVec &  src,
const size_t  srcIdx,
const size_t  srcCount 
)
inline

Definition at line 1220 of file unicode.h.

1221  {
1222  IAssert(srcCount > 0);
1223  if (srcCount == 1) { singles.AddKey(TItem(src[TVecIdx(srcIdx)])); return; }
1224  if (srcCount == 2) { pairs.AddKey(TItemPr(TItem(src[TVecIdx(srcIdx + 1)]), TItem(src[TVecIdx(srcIdx)]))); return; }
1225  size_t srcLast = srcIdx + (srcCount - 1);
1226  TItemTr tr = TItemTr(TItem(src[TVecIdx(srcLast)]), TItem(src[TVecIdx(srcLast - 1)]), TItem(src[TVecIdx(srcLast - 2)]));
1227  int keyId = roots.GetKeyId(tr), curNodeIdx = -1;
1228  if (keyId >= 0) curNodeIdx = roots[keyId];
1229  else { curNodeIdx = nodes.Add(TNode(TItem(0), -1, -1, false)); roots.AddDat(tr, curNodeIdx); }
1230  //
1231  if (srcCount > 3) for (size_t srcPos = srcLast - 3; ; )
1232  {
1233  const TItem curItem = src[TVecIdx(srcPos)];
1234  int childNodeIdx = nodes[curNodeIdx].child;
1235  while (childNodeIdx >= 0) {
1236  TNode &childNode = nodes[childNodeIdx];
1237  if (childNode.item == curItem) break;
1238  childNodeIdx = childNode.sib; }
1239  if (childNodeIdx < 0) {
1240  childNodeIdx = nodes.Add(TNode(curItem, -1, nodes[curNodeIdx].child, false));
1241  nodes[curNodeIdx].child = childNodeIdx; }
1242  curNodeIdx = childNodeIdx;
1243  if (srcPos == srcIdx) break; else srcPos--;
1244  }
1245  nodes[curNodeIdx].terminal = true;
1246  }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TUniTrie::pairs
THash< TItemPr, TVoid > pairs
Definition: unicode.h:1195
TUniTrie::TItemPr
TPair< TItem, TItem > TItemPr
Definition: unicode.h:1191
TUniTrie::singles
THash< TItem, TVoid > singles
Definition: unicode.h:1194
TUniTrie::TItem
TItem_ TItem
Definition: unicode.h:1180
TUniTrie::nodes
TNodeV nodes
Definition: unicode.h:1197
TUniTrie::TVecIdx
TUniVecIdx TVecIdx
Definition: unicode.h:1193
TUniTrie::roots
THash< TItemTr, TInt > roots
Definition: unicode.h:1196
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:327
TUniTrie::TItemTr
TTriple< TItem, TItem, TItem > TItemTr
Definition: unicode.h:1192
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
template<typename TItem_>
template<typename TSrcVec >
void TUniTrie< TItem_ >::Add ( const TSrcVec &  src)
inline

Definition at line 1249 of file unicode.h.

1249 { Add(src, 0, (size_t) src.Len()); }
TUniTrie::Add
void Add(const TSrcVec &src, const size_t srcIdx, const size_t srcCount)
Definition: unicode.h:1220
template<typename TItem_>
void TUniTrie< TItem_ >::Clr ( )
inline

Definition at line 1200 of file unicode.h.

1200 { singles.Clr(); pairs.Clr(); roots.Clr(); nodes.Clr(); }
TUniTrie::pairs
THash< TItemPr, TVoid > pairs
Definition: unicode.h:1195
TUniTrie::singles
THash< TItem, TVoid > singles
Definition: unicode.h:1194
TUniTrie::nodes
TNodeV nodes
Definition: unicode.h:1197
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:953
TUniTrie::roots
THash< TItemTr, TInt > roots
Definition: unicode.h:1196
THash::Clr
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:315
template<typename TItem_>
bool TUniTrie< TItem_ >::Empty ( ) const
inline

Definition at line 1202 of file unicode.h.

1202 { return singles.Empty() && pairs.Empty() && roots.Empty(); }
TUniTrie::pairs
THash< TItemPr, TVoid > pairs
Definition: unicode.h:1195
THash::Empty
bool Empty() const
Definition: hash.h:185
TUniTrie::singles
THash< TItem, TVoid > singles
Definition: unicode.h:1194
TUniTrie::roots
THash< TItemTr, TInt > roots
Definition: unicode.h:1196
template<typename TItem_>
int TUniTrie< TItem_ >::Get3GramRoot ( const TItem &  last,
const TItem &  butLast,
const TItem &  butButLast 
) const
inline

Definition at line 1206 of file unicode.h.

1206  {
1207  int keyId = roots.GetKeyId(TItemTr(last, butLast, butButLast));
1208  if (keyId < 0) return 0; else return roots[keyId]; }
TUniTrie::roots
THash< TItemTr, TInt > roots
Definition: unicode.h:1196
TUniTrie::TItemTr
TTriple< TItem, TItem, TItem > TItemTr
Definition: unicode.h:1192
template<typename TItem_>
int TUniTrie< TItem_ >::GetChild ( const int  parentIdx,
const TItem &  item 
) const
inline

Definition at line 1209 of file unicode.h.

1209  {
1210  for (int childIdx = nodes[parentIdx].child; childIdx >= 0; ) {
1211  const TNode &node = nodes[childIdx];
1212  if (node.item == item) return childIdx;
1213  childIdx = node.sib; }
1214  return -1; }
TUniTrie::nodes
TNodeV nodes
Definition: unicode.h:1197
template<typename TItem_>
bool TUniTrie< TItem_ >::Has1Gram ( const TItem &  item) const
inline

Definition at line 1204 of file unicode.h.

1204 { return singles.IsKey(item); }
TUniTrie::singles
THash< TItem, TVoid > singles
Definition: unicode.h:1194
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
template<typename TItem_>
bool TUniTrie< TItem_ >::Has2Gram ( const TItem &  last,
const TItem &  butLast 
) const
inline

Definition at line 1205 of file unicode.h.

1205 { return pairs.IsKey(TItemPr(last, butLast)); }
TUniTrie::pairs
THash< TItemPr, TVoid > pairs
Definition: unicode.h:1195
TUniTrie::TItemPr
TPair< TItem, TItem > TItemPr
Definition: unicode.h:1191
template<typename TItem_>
bool TUniTrie< TItem_ >::IsNodeTerminal ( const int  nodeIdx) const
inline

Definition at line 1215 of file unicode.h.

1215 { return nodes[nodeIdx].terminal; }
TUniTrie::nodes
TNodeV nodes
Definition: unicode.h:1197

Member Data Documentation

template<typename TItem_>
TNodeV TUniTrie< TItem_ >::nodes
protected

Definition at line 1197 of file unicode.h.

template<typename TItem_>
THash<TItemPr, TVoid> TUniTrie< TItem_ >::pairs
protected

Definition at line 1195 of file unicode.h.

template<typename TItem_>
THash<TItemTr, TInt> TUniTrie< TItem_ >::roots
protected

Definition at line 1196 of file unicode.h.

template<typename TItem_>
THash<TItem, TVoid> TUniTrie< TItem_ >::singles
protected

Definition at line 1194 of file unicode.h.

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