SNAP Library 2.1, User Reference  2013-09-25 10:47:25
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
Classes | Public Types | Public Member Functions | Protected Types | Protected Attributes
TUniTrie< TItem_ > Class Template Reference

#include <unicode.h>

List of all members.

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.

{ }

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.

        {
                IAssert(srcCount > 0);
                if (srcCount == 1) { singles.AddKey(TItem(src[TVecIdx(srcIdx)])); return; }
                if (srcCount == 2) { pairs.AddKey(TItemPr(TItem(src[TVecIdx(srcIdx + 1)]), TItem(src[TVecIdx(srcIdx)]))); return; }
                size_t srcLast = srcIdx + (srcCount - 1);
                TItemTr tr = TItemTr(TItem(src[TVecIdx(srcLast)]), TItem(src[TVecIdx(srcLast - 1)]), TItem(src[TVecIdx(srcLast - 2)]));
                int keyId = roots.GetKeyId(tr), curNodeIdx = -1;
                if (keyId >= 0) curNodeIdx = roots[keyId];
                else { curNodeIdx = nodes.Add(TNode(TItem(0), -1, -1, false)); roots.AddDat(tr, curNodeIdx); }
                //
                if (srcCount > 3) for (size_t srcPos = srcLast - 3; ; )
                {
                        const TItem curItem = src[TVecIdx(srcPos)];
                        int childNodeIdx = nodes[curNodeIdx].child;
                        while (childNodeIdx >= 0) {
                                TNode &childNode = nodes[childNodeIdx];
                                if (childNode.item == curItem) break;
                                childNodeIdx = childNode.sib; }
                        if (childNodeIdx < 0) {
                                childNodeIdx = nodes.Add(TNode(curItem, -1, nodes[curNodeIdx].child, false));
                                nodes[curNodeIdx].child = childNodeIdx; }
                        curNodeIdx = childNodeIdx;
                        if (srcPos == srcIdx) break; else srcPos--;
                }
                nodes[curNodeIdx].terminal = true;
        }
template<typename TItem_>
template<typename TSrcVec >
void TUniTrie< TItem_ >::Add ( const TSrcVec &  src) [inline]

Definition at line 1249 of file unicode.h.

{ Add(src, 0, (size_t) src.Len()); }
template<typename TItem_>
void TUniTrie< TItem_ >::Clr ( ) [inline]

Definition at line 1200 of file unicode.h.

{ singles.Clr(); pairs.Clr(); roots.Clr(); nodes.Clr(); }
template<typename TItem_>
bool TUniTrie< TItem_ >::Empty ( ) const [inline]

Definition at line 1202 of file unicode.h.

{ return singles.Empty() && pairs.Empty() && roots.Empty(); }
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.

                                                                                                 {
                int keyId = roots.GetKeyId(TItemTr(last, butLast, butButLast));
                if (keyId < 0) return 0; else return roots[keyId]; }
template<typename TItem_>
int TUniTrie< TItem_ >::GetChild ( const int  parentIdx,
const TItem &  item 
) const [inline]

Definition at line 1209 of file unicode.h.

                                                                   {
                for (int childIdx = nodes[parentIdx].child; childIdx >= 0; ) {
                        const TNode &node = nodes[childIdx];
                        if (node.item == item) return childIdx;
                        childIdx = node.sib; }
                return -1; }
template<typename TItem_>
bool TUniTrie< TItem_ >::Has1Gram ( const TItem &  item) const [inline]

Definition at line 1204 of file unicode.h.

{ return singles.IsKey(item); }
template<typename TItem_>
bool TUniTrie< TItem_ >::Has2Gram ( const TItem &  last,
const TItem &  butLast 
) const [inline]

Definition at line 1205 of file unicode.h.

{ return pairs.IsKey(TItemPr(last, butLast)); }
template<typename TItem_>
bool TUniTrie< TItem_ >::IsNodeTerminal ( const int  nodeIdx) const [inline]

Definition at line 1215 of file unicode.h.

{ return nodes[nodeIdx].terminal; }

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: