Context algorithm
Semi-predictive context algorithm implementation
 All Data Structures Files Functions Variables Typedefs Macros Pages
fsmTree.h
Go to the documentation of this file.
1 /* Copyright 2013 Jorge Merlino
2 
3  This file is part of Context.
4 
5  Context is free software: you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation, either version 3 of the License, or
8  (at your option) any later version.
9 
10  Context is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with Context. If not, see <http://www.gnu.org/licenses/>.
17 */
18 
19 #ifndef FSM_TREE_H
20 #define FSM_TREE_H
21 
22 #ifndef WIN32
23 #include <obstack.h>
24 #endif
25 #include "types.h"
26 
28 typedef struct fsmTree {
30  right,
31  length,
32  *count,
33  totalSyms,
34  totalCount; /*suma de counts*/
35  /*numEscapes;*/ /*suma de escapes*/
36 
37  Uchar *symbols; /* simbolo en cada posicion */
38 
39  struct fsmTree *tail,
40  *origin,
41  *parent,
42  **children,
43  **transitions;
46  used;
48 #ifndef WIN32
49  struct obstack nodeStack;
50 #endif
51 } *fsmTree_t;
52 
55 
58 
60 void addSymbol(fsmTree_t, const Uchar);
61 
63 void makeFsm(fsmTree_t);
64 
66 void writeFsmTree(const fsmTree_t, FILE *);
67 
70 
71 Uint getHeight (const fsmTree_t);
72 
73 void printContext (fsmTree_t);
74 
75 void compareTrees (const fsmTree_t, const fsmTree_t);
76 
77 void copyStatistics (const fsmTree_t orig, fsmTree_t dest, const Uchar * text2);
78 
79 #ifdef DEBUG
80 
82 void printFsmTree(const fsmTree_t);
83 
84 #endif
85 
86 #endif
void addSymbol(fsmTree_t tree, const Uchar sym)
Adds a new symbol to this tree node.
Definition: fsmTree.c:543
fsmTree_t initFsmTree()
Creates and initializes a new fsm tree structure instance.
Definition: fsmTree.c:487
void printContext(fsmTree_t tree)
Definition: fsmTree.c:619
struct fsmTree ** transitions
List of FSM transitions from this state.
Definition: fsmTree.h:39
BOOL isRootFsmTree(const fsmTree_t tree)
Indicates if the parameter node is the root of the tree.
Definition: fsmTree.c:602
Uint getHeight(const fsmTree_t tree)
Definition: fsmTree.c:606
Uint totalCount
Definition: fsmTree.h:29
unsigned char Uchar
Unsigned char type.
Definition: types.h:48
BOOL used
Flag that indicates if this node has been used to encode a symbol.
Definition: fsmTree.h:45
BOOL * traversed
List of flags indicating an attempt was made to traverse each child edge.
Definition: fsmTree.h:45
Uchar * symbols
Definition: fsmTree.h:37
struct fsmTree * origin
Pointer to the original node this one descends from.
Definition: fsmTree.h:39
unsigned long Uint
Unsigned int type.
Definition: types.h:54
#define BOOL
Boolean data type.
Definition: types.h:92
Uint * count
List containing the number of occurrences of each character in this state.
Definition: fsmTree.h:29
Encoder context tree structure.
Definition: fsmTree.h:28
void writeFsmTree(const fsmTree_t tree, FILE *file)
Writes this tree into a file.
Definition: fsmTree.c:572
struct obstack nodeStack
Obstack used to allocate memory for this tree.
Definition: fsmTree.h:49
Uint right
Index of the rightmost character of this node label in the input string.
Definition: fsmTree.h:29
struct fsmTree * fsmTree_t
Encoder context tree structure.
Uint left
Index of the leftmost character of this node label in the input string.
Definition: fsmTree.h:29
Uint totalSyms
Total number of symbols occuring at this state.
Definition: fsmTree.h:29
void makeFsm(fsmTree_t tree)
Calculates the FSM closure of this tree.
Definition: fsmTree.c:553
struct fsmTree ** children
List of pointers to all the children of this node.
Definition: fsmTree.h:39
void copyStatistics(const fsmTree_t orig, fsmTree_t dest, const Uchar *text2)
Definition: fsmTree.c:664
struct fsmTree * tail
Pointer to the node whose label is the tail of this one.
Definition: fsmTree.h:39
struct fsmTree * parent
Pointer to the parent of this node.
Definition: fsmTree.h:39
void freeFsmTree(fsmTree_t tree)
Deletes a fsm tree structure instance.
Definition: fsmTree.c:530
Uint length
Distance from this node to the root of the tree.
Definition: fsmTree.h:29
void compareTrees(const fsmTree_t treeA, const fsmTree_t treeB)
Definition: fsmTree.c:659