2 * Copyright (c) 2001-2002, David Janssens
\r
3 * All rights reserved.
\r
5 * Redistribution and use in source and binary forms, with or without
\r
6 * modification, are permitted provided that the following conditions
\r
8 * 1. Redistributions of source code must retain the above copyright
\r
9 * notice, this list of conditions and the following disclaimer.
\r
10 * 2. Redistributions in binary form must reproduce the above copyright
\r
11 * notice, this list of conditions and the following disclaimer in the
\r
12 * documentation and/or other materials provided with the distribution.
\r
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
\r
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
\r
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
\r
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
\r
18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
\r
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
\r
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
\r
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
\r
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
\r
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
\r
24 * POSSIBILITY OF SUCH DAMAGE.
\r
33 /* Reset tag-tree. */
\r
35 void tgt_reset(tgt_tree_t * tree)
\r
39 if (!tree || tree == NULL)
\r
42 for (i = 0; i < tree->numnodes; i++) {
\r
43 tree->nodes[i].value = 999;
\r
44 tree->nodes[i].low = 0;
\r
45 tree->nodes[i].known = 0;
\r
50 /* Create tag-tree. */
\r
52 tgt_tree_t *tgt_create(int numleafsh, int numleafsv)
\r
57 tgt_node_t *parentnode;
\r
58 tgt_node_t *parentnode0;
\r
64 tree = (tgt_tree_t *) malloc(sizeof(tgt_tree_t));
\r
65 tree->numleafsh = numleafsh;
\r
66 tree->numleafsv = numleafsv;
\r
69 nplh[0] = numleafsh;
\r
70 nplv[0] = numleafsv;
\r
73 n = nplh[numlvls] * nplv[numlvls];
\r
74 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;
\r
75 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;
\r
76 tree->numnodes += n;
\r
81 if (tree->numnodes == 0) {
\r
86 tree->nodes = (tgt_node_t *) malloc(tree->numnodes * sizeof(tgt_node_t));
\r
89 parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv];
\r
90 parentnode0 = parentnode;
\r
92 for (i = 0; i < numlvls - 1; ++i) {
\r
93 for (j = 0; j < nplv[i]; ++j) {
\r
96 node->parent = parentnode;
\r
99 node->parent = parentnode;
\r
104 if ((j & 1) || j == nplv[i] - 1) {
\r
105 parentnode0 = parentnode;
\r
107 parentnode = parentnode0;
\r
108 parentnode0 += nplh[i];
\r
120 /* Destroy tag-tree. */
\r
122 void tgt_destroy(tgt_tree_t * t)
\r
129 /* Set the value of a leaf of the tag-tree. */
\r
131 void tgt_setvalue(tgt_tree_t * tree, int leafno, int value)
\r
134 node = &tree->nodes[leafno];
\r
135 while (node && node->value > value) {
\r
136 node->value = value;
\r
137 node = node->parent;
\r
142 /* Encode the value of a leaf of the tag-tree. */
\r
144 void tgt_encode(tgt_tree_t * tree, int leafno, int threshold)
\r
146 tgt_node_t *stk[31];
\r
147 tgt_node_t **stkptr;
\r
152 node = &tree->nodes[leafno];
\r
153 while (node->parent) {
\r
155 node = node->parent;
\r
160 if (low > node->low) {
\r
166 while (low < threshold) {
\r
167 if (low >= node->value) {
\r
168 if (!node->known) {
\r
187 /* Decode the value of a leaf of the tag-tree. */
\r
189 int tgt_decode(tgt_tree_t * tree, int leafno, int threshold)
\r
191 tgt_node_t *stk[31];
\r
192 tgt_node_t **stkptr;
\r
197 node = &tree->nodes[leafno];
\r
198 while (node->parent) {
\r
200 node = node->parent;
\r
205 if (low > node->low) {
\r
210 while (low < threshold && low < node->value) {
\r
218 if (stkptr == stk) {
\r
224 return (node->value < threshold) ? 1 : 0;
\r