indexer_JPIP/tgt.c

   1 /*
   2  * Copyright (c) 2001-2002, David Janssens
   3  * Copyright (c) 2003, Yannick Verschueren
   4  * Copyright (c) 2003, Communications and remote sensing Laboratory, Universite catholique de Louvain, Belgium
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "tgt.h"
  30 #include "bio.h"
  31 #include <stdlib.h>
  32 #include <stdio.h>
  33
  34 /// <summary>
  35 /// Reset tag-tree.
  36 /// </summary>
  37 void tgt_reset(tgt_tree_t *tree)
  38 {
  39     int i;
  40     for (i=0; i<tree->numnodes; i++) {
  41         tree->nodes[i].value=999;
  42         tree->nodes[i].low=0;
  43         tree->nodes[i].known=0;
  44     }
  45 }
  46
  47 /// <summary>
  48 /// Create tag-tree.
  49 /// </summary>
  50 tgt_tree_t *tgt_create(int numleafsh, int numleafsv)
  51 {
  52     int nplh[32];
  53     int nplv[32];
  54     tgt_node_t *node;
  55     tgt_node_t *parentnode;
  56     tgt_node_t *parentnode0;
  57     tgt_tree_t *tree;
  58     int i, j, k;
  59     int numlvls;
  60     int n;
  61
  62     tree=(tgt_tree_t*)malloc(sizeof(tgt_tree_t));
  63     tree->numleafsh=numleafsh;
  64     tree->numleafsv=numleafsv;
  65
  66     numlvls=0;
  67     nplh[0]=numleafsh;
  68     nplv[0]=numleafsv;
  69     tree->numnodes=0;
  70     do {
  71         n=nplh[numlvls]*nplv[numlvls];
  72         nplh[numlvls+1]=(nplh[numlvls]+1)/2;
  73         nplv[numlvls+1]=(nplv[numlvls]+1)/2;
  74         tree->numnodes+=n;
  75         ++numlvls;
  76     } while (n>1);
  77
  78     tree->nodes=(tgt_node_t*)malloc(tree->numnodes*sizeof(tgt_node_t));
  79
  80     node=tree->nodes;
  81     parentnode=&tree->nodes[tree->numleafsh*tree->numleafsv];
  82     parentnode0=parentnode;
  83
  84     for (i=0; i<numlvls-1; ++i) {
  85         for (j=0; j<nplv[i]; ++j) {
  86             k=nplh[i];
  87             while (--k>=0) {
  88                 node->parent=parentnode;
  89                 ++node;
  90                 if (--k >= 0) {
  91                     node->parent=parentnode;
  92                     ++node;
  93                 }
  94                 ++parentnode;
  95             }
  96             if ((j&1)||j==nplv[i]-1) {
  97                 parentnode0=parentnode;
  98             } else {
  99                 parentnode=parentnode0;
 100                 parentnode0+=nplh[i];
 101             }
 102         }
 103     }
 104     node->parent=0;
 105
 106     tgt_reset(tree);
 107
 108     return tree;
 109 }
 110
 111 /// <summary>
 112 /// Destroy tag-tree.
 113 /// </summary>
 114 void tgt_destroy(tgt_tree_t *t) {
 115     free(t->nodes);
 116     free(t);
 117 }
 118
 119 /// <summary>
 120 /// Set the value of a leaf of the tag-tree.
 121 /// </summary>
 122 void tgt_setvalue(tgt_tree_t *tree, int leafno, int value) {
 123     tgt_node_t *node;
 124     node=&tree->nodes[leafno];
 125     while (node && node->value>value) {
 126         node->value=value;
 127         node=node->parent;
 128     }
 129 }
 130
 131 /// <summary>
 132 /// Decode the value of a leaf of the tag-tree.
 133 /// </summary>
 134 int tgt_decode(tgt_tree_t *tree, int leafno, int threshold)
 135 {
 136     tgt_node_t *stk[31];
 137     tgt_node_t **stkptr;
 138     tgt_node_t *node;
 139     int low;
 140
 141     stkptr=stk;
 142     node=&tree->nodes[leafno];
 143     while (node->parent) {
 144         *stkptr++=node;
 145         node=node->parent;
 146     }
 147
 148     low=0;
 149     for (;;) {
 150         if (low>node->low) {
 151             node->low=low;
 152         } else {
 153             low=node->low;
 154         }
 155         while (low<threshold && low<node->value) {
 156             if (bio_read(1)) {
 157                 node->value=low;
 158             } else {
 159                 ++low;
 160             }
 161         }
 162         node->low=low;
 163         if (stkptr==stk) {
 164             break;
 165         }
 166         node=*--stkptr;
 167     }
 168
 169     return (node->value<threshold)?1:0;
 170 }