summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/source/fonts/malayalam/preproc/patc/pstree.c
blob: fa7cb8c21d0cb3a52270b89fd291ea780d78b5c9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
/*+

NAME: PSTree.c --- Pattern Search Tree

AUTHOR: Jeroen Hellingman

    PSTree is een verzameling routines om snel patronen in een
    multi-branch tree op te slaan en terug te vinden, zoals gebruikt
    worden voor bijvoorbeeld spellingscheckers. Bij elk patroon
    kunnen we een string opslaan.
    
    De worden worden letter voor letter opgeslagen in de nodes
    van de boom, waarbij de eerste node alle eerste letters,
    bevat, en de tweede node voor elk van die letters, de tweede
    letters van woorden die met die letter beginnen. Elke node
    opzich is ook weer opgebouwd als een boom.

    Per letter gebruikt deze structuur vier pointers en een
    character geheugen ruimte (op een 68000 17 bytes), maar
    als het woord 'automatisch' al is opgeslagen, hoeven we
    maar een extra letter te bewaren om 'automatische' op te
    slaan.
    
    Op deze structuur hebben we de volgende operaties:

    int PSTinsert(PSTree **tree, char *pattern, char *action);
        voeg pattern met action toe aan tree, *tree kan NULL zijn, 
        en zal dan veranderen, resultaat: TRUE als succes, FALSE 
        anders
    
    int PSTretract(PSTree **tree, char *pattern);
        Nog niet geimplementeerd
    
    char *PSTmatch(PSTree *tree, const char *pattern, int *length);
        vind de langste match beginnend bij de pattern[0] van pattern
        met een patroon in tree, resultaat: de actie bij dat patroon,
        NULL als geen actie gevonden, length bevat na afloop de lengte
        van het gematchte patroon, of 0 als geen patroon is gevonden.

HISTORY:
  05-FEB-1992 Creation
  
-*/

#define TEST (0)

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>

#include "PSTree.h"

#define TRUE (1)
#define FALSE (0)

/* private operations */

PSTree *PSTfindelement(PSTree *t, char c);
PSTree *PSTfindinsertelement(PSTree **t, char c);
void PSTpmatch(PSTree *tree, const char *pattern, char **action, int *length, int depth);

/* insert: insert p into the pattern tree:
   TRUE: success
   FALSE: failure (already available pattern, failure to allocate cell);
*/

int PSTinsert(PSTree **t, char *p, char *a)
{   PSTree *first = NULL;

    if(t == NULL || p == NULL || p[0] == '\0') /* sanity check */
        return FALSE;

    first = PSTfindinsertelement(t, p[0]);
    if(first == NULL) /* element could not be added/inserted in PSTree? */
        return FALSE;
    
    if(p[1] == '\0') /* p[0] last element of pattern? */
    {   if(first->a == NULL) /* no action assigned yet */
        {  first->a = a;
           return TRUE;
        } 
        else /* i.e. pattern already in tree */
        {  return FALSE;
        }
    }
    else /* not last element in pattern: insert rest of pattern */
        return PSTinsert(&(first->n), &p[1], a);
}


/* PSTfindinsertelement: search for element c, return its node
   if it can be found, create a new node with element c and all
   pointers at NULL otherwise, and return it.
   return NULL at failure.
*/

static PSTree *PSTfindinsertelement(PSTree **t, char c)
{
    if(t == NULL) /* sanity check */
       return NULL;

    if(*t == NULL) /* empty tree: create new node */
    {   *t = malloc(sizeof(PSTree));
        if(*t == NULL) /* malloc failed */
            return FALSE;
        (*t)->e = c;
        (*t)->l = NULL;
        (*t)->r = NULL;
        (*t)->n = NULL;
        (*t)->a = NULL;
        return *t;
    }
    else
    {   if((*t)->e == c) /* we found it */
            return *t;
        else if((*t)->e < c) /* then go left */
            return PSTfindinsertelement(&((*t)->l), c);
        else /* go right */
            return PSTfindinsertelement(&((*t)->r), c);
    }
}

/* PSTfindelement: search for element c, return its node
   if it can be found return NULL at otherwise.
*/

static PSTree *PSTfindelement(PSTree *t, char c)
{
    if(t == NULL) /* empty tree */
        return NULL;
    else
    {   if(t->e == c) /* we found it */
            return t;
        else if(t->e < c) /* then go left */
            return PSTfindelement(t->l, c);
        else /* go right */
            return PSTfindelement(t->r, c);
    }
}

char *PSTmatch(PSTree *t, const char *p, int *length)
{   char *action = NULL;
    *length = 0;
    PSTpmatch(t, p, &action, length, 1);
    return action;
}

/* remember recursion depth to determine length of match */

static void PSTpmatch(PSTree *t, const char *p, char **action, int *length, int depth)
{   PSTree *first = NULL;

    if(t == NULL || p == NULL || p[0] == '\0') /* sanity check */
        return;

    first = PSTfindelement(t, p[0]);
    if(first == NULL) /* element not found in PSTree? */
        return;
    
    if(first->a != NULL) /* action for pattern so-far? */
    {   *length = depth;
        *action = first->a;
    }
    
    PSTpmatch(first->n, &p[1], action, length, depth + 1);
}


#if TEST

void PSTshow(PSTree *t)
{
    if(t == NULL)
        printf("(null)\n");
    else
    {   putchar(t->e);
        if(t->a != NULL)
        {   putchar('[');
            printf("%s", t->a);
            putchar(']');
        }
        PSTshow(t->n);
        putchar('L'); PSTshow(t->l);
        putchar('R'); PSTshow(t->r);
    }
}


void main()
{

    char *actie = NULL;
    int len = 0;

    PSTree *t = NULL;
    PSTinsert(&t, "aap", "1");
    PSTinsert(&t, "appel", "2");
    PSTinsert(&t, "aapjes", "3");
    PSTinsert(&t, "koe", "4");
    PSTinsert(&t, "kokosnoot", "5");
    PSTinsert(&t, "akker", "6");
    PSTshow(t); puts("------------"); getchar();
    
    actie = PSTmatch(t, "aapjesverhaal", &len);
    if(actie != NULL) { printf("actie: (%s) lengte: %d\n", actie, len); }
    
    actie = PSTmatch(t, "aapjelief", &len);
    if(actie != NULL) { printf("actie: (%s) lengte: %d\n", actie, len); }

    actie = PSTmatch(t, "appelboom", &len);
    if(actie != NULL) { printf("actie: (%s) lengte: %d\n", actie, len); }

    actie = PSTmatch(t, "aster", &len);
    if(actie != NULL) { printf("actie: (%s) lengte: %d\n", actie, len); }
    else { printf("actie: NULL lengte: %d\n", actie, len); }

    exit(0);

}

#endif /* TEST */

/* end of PSTree.c */