Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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. }
  171.