Main Page   Compound List   File List   Compound Members   File Members  

short_indices.c

Go to the documentation of this file.
00001 
00002 /*=====================================================================
00003                 =======   COPYRIGHT NOTICE   =======
00004 Copyright (C) 1996, Carnegie Mellon University, Cambridge University,
00005 Ronald Rosenfeld and Philip Clarkson.
00006 
00007 All rights reserved.
00008 
00009 This software is made available for research purposes only.  It may be
00010 redistributed freely for this purpose, in full or in part, provided
00011 that this entire copyright notice is included on any copies of this
00012 software and applications and derivations thereof.
00013 
00014 This software is provided on an "as is" basis, without warranty of any
00015 kind, either expressed or implied, as to any matter including, but not
00016 limited to warranty of fitness of purpose, or merchantability, or
00017 results obtained from use of this software.
00018 ======================================================================*/
00019 
00048 #include "rr_libs/general.h"
00049 #include "ngram.h"
00050 
00051 unsigned short new_index(int full_index,
00052                          int *ind_table,
00053                          unsigned short *ind_table_size,
00054                          int position_in_list) {
00055 
00056   
00057   if (full_index - (((*ind_table_size)-1)*KEY) >= KEY) {
00058     ind_table[*ind_table_size] = position_in_list;
00059     (*ind_table_size)++;
00060   }
00061 
00062   return (full_index % KEY);
00063 
00064 }
00065 
00066 int get_full_index(unsigned short short_index,
00067                    int *ind_table,
00068                    unsigned short ind_table_size,
00069                    int position_in_list) {
00070 
00071   int lower_bound;
00072   int upper_bound;
00073   int new_try;
00074 
00075   /* Binary search for position_in_list */
00076 
00077   lower_bound = 0;
00078   upper_bound = ind_table_size-1;
00079   
00080   /* Search range is inclusive */
00081 
00082   if (ind_table_size > 0) {
00083   
00084     if (position_in_list >= ind_table[upper_bound]) {
00085       lower_bound = upper_bound;
00086     }
00087 
00088     while (upper_bound-lower_bound > 1) {
00089       new_try = (upper_bound + lower_bound) / 2;
00090       if (ind_table[new_try] > position_in_list) {
00091         upper_bound = new_try;
00092       }
00093       else {
00094         lower_bound = new_try;
00095       }
00096     }
00097   }
00098 
00099   /* Return the appropriate value */
00100 
00101 
00102   return((lower_bound*KEY)+short_index);
00103 
00104 }
00105 

Generated on Tue Dec 21 13:54:46 2004 by doxygen1.2.18