diff options
Diffstat (limited to 'indexer_JPIP/tgt.c')
| -rw-r--r-- | indexer_JPIP/tgt.c | 170 |
1 files changed, 170 insertions, 0 deletions
diff --git a/indexer_JPIP/tgt.c b/indexer_JPIP/tgt.c new file mode 100644 index 00000000..4a651935 --- /dev/null +++ b/indexer_JPIP/tgt.c @@ -0,0 +1,170 @@ +/* + * Copyright (c) 2001-2002, David Janssens + * Copyright (c) 2003, Yannick Verschueren + * Copyright (c) 2003, Communications and remote sensing Laboratory, Universite catholique de Louvain, Belgium + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "tgt.h" +#include "bio.h" +#include <stdlib.h> +#include <stdio.h> + +/// <summary> +/// Reset tag-tree. +/// </summary> +void tgt_reset(tgt_tree_t *tree) +{ + int i; + for (i=0; i<tree->numnodes; i++) { + tree->nodes[i].value=999; + tree->nodes[i].low=0; + tree->nodes[i].known=0; + } +} + +/// <summary> +/// Create tag-tree. +/// </summary> +tgt_tree_t *tgt_create(int numleafsh, int numleafsv) +{ + int nplh[32]; + int nplv[32]; + tgt_node_t *node; + tgt_node_t *parentnode; + tgt_node_t *parentnode0; + tgt_tree_t *tree; + int i, j, k; + int numlvls; + int n; + + tree=(tgt_tree_t*)malloc(sizeof(tgt_tree_t)); + tree->numleafsh=numleafsh; + tree->numleafsv=numleafsv; + + numlvls=0; + nplh[0]=numleafsh; + nplv[0]=numleafsv; + tree->numnodes=0; + do { + n=nplh[numlvls]*nplv[numlvls]; + nplh[numlvls+1]=(nplh[numlvls]+1)/2; + nplv[numlvls+1]=(nplv[numlvls]+1)/2; + tree->numnodes+=n; + ++numlvls; + } while (n>1); + + tree->nodes=(tgt_node_t*)malloc(tree->numnodes*sizeof(tgt_node_t)); + + node=tree->nodes; + parentnode=&tree->nodes[tree->numleafsh*tree->numleafsv]; + parentnode0=parentnode; + + for (i=0; i<numlvls-1; ++i) { + for (j=0; j<nplv[i]; ++j) { + k=nplh[i]; + while (--k>=0) { + node->parent=parentnode; + ++node; + if (--k >= 0) { + node->parent=parentnode; + ++node; + } + ++parentnode; + } + if ((j&1)||j==nplv[i]-1) { + parentnode0=parentnode; + } else { + parentnode=parentnode0; + parentnode0+=nplh[i]; + } + } + } + node->parent=0; + + tgt_reset(tree); + + return tree; +} + +/// <summary> +/// Destroy tag-tree. +/// </summary> +void tgt_destroy(tgt_tree_t *t) { + free(t->nodes); + free(t); +} + +/// <summary> +/// Set the value of a leaf of the tag-tree. +/// </summary> +void tgt_setvalue(tgt_tree_t *tree, int leafno, int value) { + tgt_node_t *node; + node=&tree->nodes[leafno]; + while (node && node->value>value) { + node->value=value; + node=node->parent; + } +} + +/// <summary> +/// Decode the value of a leaf of the tag-tree. +/// </summary> +int tgt_decode(tgt_tree_t *tree, int leafno, int threshold) +{ + tgt_node_t *stk[31]; + tgt_node_t **stkptr; + tgt_node_t *node; + int low; + + stkptr=stk; + node=&tree->nodes[leafno]; + while (node->parent) { + *stkptr++=node; + node=node->parent; + } + + low=0; + for (;;) { + if (low>node->low) { + node->low=low; + } else { + low=node->low; + } + while (low<threshold && low<node->value) { + if (bio_read(1)) { + node->value=low; + } else { + ++low; + } + } + node->low=low; + if (stkptr==stk) { + break; + } + node=*--stkptr; + } + + return (node->value<threshold)?1:0; +} |