source: main/trunk/greenstone2/common-src/indexers/mgpp/text/Terms.cpp@ 29581

/**************************************************************************
 *
 * Terms.cpp -- Query related functions
 * Copyright (C) 1999  Rodger McNab
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 **************************************************************************/

#include "Terms.h"
#include "words.h"
#include "stemmer.h"
#include "bitio_gen.h"
#include "bitio_m_stdio.h"

void QueryInfo::Clear () {
  UCArrayClear (docLevel);
  maxDocs = 0;
  sortByRank = true;
  exactWeights = false;
  needRankInfo = false;
  needTermFreqs = false;
}



void TermFreqData::Clear () {
  UCArrayClear (tag);
  UCArrayClear (term);
  equivTerms.erase(equivTerms.begin(), equivTerms.end());
  stemMethod = 0;
  matchDocs = 0;
  termFreq = 0;
}

ostream &operator<< (ostream &s, const TermFreqData &t) {
  s << "<" << t.tag << ">\"" << t.term << "\"stem("
    << t.stemMethod << ")equiv terms(";
  
  mg_u_long i;
  for (i=0; i<t.equivTerms.size(); ++i) {
    s << t.equivTerms[i] << ", ";
  }
  s <<")docs(" << t.matchDocs << ")"
    << "count("<<t.termFreq<<")";
  return s;
}

bool operator== (const TermFreqData &t1, const TermFreqData &t2) {
  return ((t1.tag == t2.tag) &&
      (t1.term == t2.term) &&
      (t1.stemMethod == t2.stemMethod) &&
      (t1.equivTerms == t2.equivTerms) &&
      (t1.matchDocs == t2.matchDocs) &&
      (t1.termFreq == t2.termFreq));
}


void QueryResult::Clear () {
  docs.erase (docs.begin(), docs.end());
  ranks.erase (ranks.begin(), ranks.end());
  termFreqs.erase (termFreqs.begin(), termFreqs.end());
  actualNumDocs = 0;
}

QueryResult::QueryResult () {
  Clear ();
}

void QueryResult::printShort(ostream &s) {

  s << "termFreqs: ";
  for (mg_u_long i=0; i<termFreqs.size(); ++i)
    s << termFreqs[i] << ", ";
  
  s << "\nactual number of docs found: " << actualNumDocs;
  s << "\n\n";

}


ostream &operator<< (ostream &s, const QueryResult &r) {
  s << "docs: ";
  mg_u_long i;
  for (i=0; i<r.docs.size(); ++i)
    s << r.docs[i] << ", ";
  
  s << "\nranks: ";
  for (i=0; i<r.ranks.size(); ++i)
    s << r.ranks[i] << ", ";

  s << "\ntermFreqs: ";
  for (i=0; i<r.termFreqs.size(); ++i)
    s << r.termFreqs[i] << ", ";

  s << "\nactual number of docs found: " << r.actualNumDocs;
  s << "\n\n";

  return s;
}


bool operator== (const QueryResult &r1, const QueryResult &r2) {
  return ((r1.docs == r2.docs) &&
      (r1.ranks == r2.ranks) &&
      (r1.termFreqs == r2.termFreqs) &&
      (r1.actualNumDocs == r2.actualNumDocs));
}

//---------------------------------------------------
// new ExtQueryResult stuff
void ExtQueryResult::Clear () {
  docs.erase (docs.begin(), docs.end());
  levels.erase (levels.begin(), levels.end());
  ranks.erase (ranks.begin(), ranks.end());
  termFreqs.erase (termFreqs.begin(), termFreqs.end());
  actualNumDocs = 0;
}

ExtQueryResult::ExtQueryResult () {
  Clear ();
}

ostream &operator<< (ostream &s, const ExtQueryResult &r) {
  s << "docs: ";
  mg_u_long i;
  for (i=0; i<r.docs.size(); ++i)
    s << r.docs[i] << ", ";

  s << "\nlevels: ";
  for (i=0; i<r.levels.size(); ++i)
    s << r.levels[i] << ", ";

  
  s << "\nranks: ";
  for (i=0; i<r.ranks.size(); ++i)
    s << r.ranks[i] << ", ";

  s << "\ntermFreqs: ";
  for (i=0; i<r.termFreqs.size(); ++i)
    s << r.termFreqs[i] << ", ";
  s << "\nactual number of docs found: " << r.actualNumDocs;
  s << "\n\n";

  return s;
}


bool operator== (const ExtQueryResult &r1, const ExtQueryResult &r2) {
  return ((r1.docs == r2.docs) &&
      (r1.levels == r2.levels) &&
      (r1.ranks == r2.ranks) &&
      (r1.termFreqs == r2.termFreqs) &&
      (r1.actualNumDocs == r2.actualNumDocs));
}

//-------------------------------------------------------
// new BrowseQueryResult stuff
void BrowseQueryResult::Clear () {
  termFreqs.erase (termFreqs.begin(), termFreqs.end());
}

BrowseQueryResult::BrowseQueryResult () {
  Clear ();
}



ostream &operator<< (ostream &s, const BrowseQueryResult &r) {
  s << "terms: ";
  mg_u_long i;
  for (i=0; i<r.termFreqs.size(); ++i)
    s << r.termFreqs[i] << ", ";
    s << "\n\n";
  return s;
}


bool operator== (const BrowseQueryResult &r1, const BrowseQueryResult &r2) {
  return ((r1.termFreqs == r2.termFreqs));
     
}




//--------------------------------------
void FragData::Clear () {
  matchDocs = 0;
  fragNums.erase (fragNums.begin(), fragNums.end());
  fragFreqs.erase (fragFreqs.begin(), fragFreqs.end());
}


void FindWordNumbers (IndexData &indexData,
              const UCArray &term,
              mg_u_long stemMethod,
              vector<mg_u_long> &equivWords) {
  equivWords.erase (equivWords.begin(), equivWords.end());

  if (!(stemMethod & STEM_PARTIAL_MATCH)) {
    // If we are not doing a partial match then make sure the stemMethod we have
    // specified is valid, ie the stem index has been built. If invalid, set it to 0 ie no stemming/casefolding/accentfolding
    // If we are partial matching then we are not using the stem indexes so
    // this doesn't matter.
    if(stemMethod > STEM_MAX) {
      cerr << "Stem method "<<stemMethod<< " is greater than maximum allowed ("<<STEM_MAX<<"). Not doing stemming\n";
      stemMethod=0;
    }
    else if (stemMethod > 0 && indexData.stemFile[stemMethod-1] == NULL) {
      cerr << "Stem index for method "<<stemMethod<< " was not built, so not doing stemming\n";
      stemMethod = 0;
    }
  }
  /* [JFG - Mar 06: Accent folding patch] */
  /* use flag PARTIAL_MATCH */  
  if (stemMethod == 0 || (stemMethod & STEM_PARTIAL_MATCH)) {
    // don't need to stem the word,
    // find the word number(s) for this term
    mg_u_long wordElNum = 0;
    mg_u_long numLevels = indexData.bdh.num_levels;
    word_block_dict_el wordDictEl;
    wordDictEl.SetNumLevels (numLevels);
    if (stemMethod == 0) {
      if (SearchWordBlockDictEl (indexData.dictFile, indexData.biWords,
                 indexData.bdh.entries_per_wblk,
                 indexData.bdh.word_dict_size,
                 numLevels, term, wordDictEl, wordElNum))
    equivWords.push_back (wordElNum);
      
      return;
    } else {
      // partial matching,
      PartialMatchSearchWordBlockDictEl (indexData.dictFile, indexData.biWords, indexData.bdh.entries_per_wblk, indexData.bdh.word_dict_size, numLevels, term, wordDictEl, equivWords, (stemMethod & STEM_CaseFolding)? true : false);
      // TODO: Accent Folding is not handled here!!
      return;
    }
  }
              
  // need to stem this word and find it in the blocked stem index
  unsigned char mgWord[MAXSTEMLEN + 1];
  UCArray stemTerm;
  mg_u_long stemmerNum = 0;


  stemmerNum = indexData.sih[stemMethod-1].stemmer_num;
  
  // convert the word to an "mg word"
  mgWord[0] = term.size();
  memcpy ((char *)&mgWord[1], &(term[0]), term.size());
  
  // stem the word
  mgpp_stemmer (stemMethod, stemmerNum, mgWord);
  // convert the result back to a UCArray
  stemTerm.insert (stemTerm.end(), &mgWord[1], &mgWord[1] + mgWord[0]);

  // need to look up this term in the appropriate dictionary
  stem_block_dict_el stemDictEl;
  mg_u_long stemElNum;
  bool result = false;
  
  /* [JFG - Mar 06: Accent folding patch] */
  result = SearchStemBlockDictEl (indexData.stemFile[stemMethod-1],
               indexData.sii[stemMethod-1],
               indexData.sih[stemMethod-1].entries_per_block,
               indexData.sih[stemMethod-1].dict_size,
               stemTerm,
               stemDictEl,
               stemElNum);
  
  if (result) {
    equivWords = stemDictEl.equivWords;  
  }
}



void ReadTermFragData (IndexData &indexData,
               bool needFragFreqs,
               mg_u_long termNum,
               FragData &fragData,
               FragRangeArray *fragLimits,
               UCArray & termWord) {
  fragData.Clear();

  // look up the word in the dictionary
  mg_u_long numLevels = indexData.bdh.num_levels;
  word_block_dict_el wordDictEl;
  wordDictEl.SetNumLevels (numLevels);
  if (!SearchWordBlockDictElNum (indexData.dictFile,
                 indexData.biWords,
                 indexData.bdh.entries_per_wblk,
                 indexData.bdh.word_dict_size,
                 numLevels,
                 termNum, wordDictEl))
    return; // nothing more to do

  fragData.matchDocs = wordDictEl.levelFreqs[indexData.curLevelNum];
  termWord = wordDictEl.el;
  // seek to the appropriate place in the inverted file
  fseek (indexData.invfFile, wordDictEl.invf_ptr, SEEK_SET);
  stdio_bitio_buffer buffer (indexData.invfFile);
    
  mg_u_long B = BIO_Bblock_Init (indexData.bdh.num_frags,
                     wordDictEl.frag_occur);
  mg_u_long fragNum = 0;
  mg_u_long termFreq = 0;

  mg_u_long fragLimitI = 0;
  mg_u_long i;
  for (i=0; i<wordDictEl.frag_occur; ++i) {
    fragNum += buffer.bblock_decode (B, NULL);
    if (!indexData.ifh.word_level_index) termFreq = buffer.gamma_decode (NULL);
    else termFreq = 1;

    // get the right fragment range
    if (fragLimits != NULL) {
      while (fragLimitI+1 < (*fragLimits).size() &&
         fragNum > (*fragLimits)[fragLimitI+1].rangeStart) {
    ++fragLimitI;
      }
    }

    // add the entry if it is within the limits
    if ((fragLimits == NULL) ||
    (fragLimitI < (*fragLimits).size() &&
     fragNum > (*fragLimits)[fragLimitI].rangeStart &&
     fragNum <= (*fragLimits)[fragLimitI].rangeEnd)) {
      fragData.fragNums.push_back (fragNum);
      if (needFragFreqs)
    fragData.fragFreqs.push_back (termFreq);
    }
  }

  buffer.done();
}


void CombineFragData (bool needFragFreqs,
              const FragData &f1,
              const FragData &f2,
              FragData &outFragData) {
  outFragData.Clear();

  // the new number of matching documents is the maximum
  // of the two input matching number of documents -- it
  // is assumed that these are at the same document level
  outFragData.matchDocs = (f1.matchDocs > f2.matchDocs) ?
    f1.matchDocs : f2.matchDocs;
  // do or
  mg_u_long f1I = 0, f1Size = f1.fragNums.size();
  mg_u_long f2I = 0, f2Size = f2.fragNums.size();

  while (f1I < f1Size || f2I < f2Size) {
    if (f2I < f2Size &&
    (f1I >= f1Size ||
     f1.fragNums[f1I] > f2.fragNums[f2I])) {
      // output f2I
      outFragData.fragNums.push_back (f2.fragNums[f2I]);
      if (needFragFreqs)
    outFragData.fragFreqs.push_back (f2.fragFreqs[f2I]);
      ++f2I;
      
    } else if (f1I < f1Size &&
           (f2I >= f2Size ||
        f1.fragNums[f1I] < f2.fragNums[f2I])) {
      // output f1I
      outFragData.fragNums.push_back (f1.fragNums[f1I]);
      if (needFragFreqs)
    outFragData.fragFreqs.push_back (f1.fragFreqs[f1I]);
      ++f1I;
      
    } else {
      // must be equal combine f1I and f2I
      outFragData.fragNums.push_back (f1.fragNums[f1I]);
      if (needFragFreqs)
    outFragData.fragFreqs.push_back (f1.fragFreqs[f1I]+f2.fragFreqs[f2I]);
      ++f1I;
      ++f2I;
    }
  }
}


void AndCombineFragData (bool needFragFreqs,
             FragData &fragData,
             const FragData &comFragData,
             mg_s_long startRange,
             mg_s_long endRange,
             const FragRangeArray *fragLimits) {
  // sanity check on range
  if (startRange > endRange) {
    mg_s_long temp = endRange;
    endRange = startRange;
    startRange = temp;
  }

  // get min matchdocs
  if (comFragData.matchDocs < fragData.matchDocs)
    fragData.matchDocs = comFragData.matchDocs;
  
  mg_u_long fragDataI = 0;
  mg_u_long fragDataSize = fragData.fragNums.size();
  mg_u_long comFragDataI = 0;
  mg_u_long comFragDataSize = comFragData.fragNums.size();
  mg_u_long fragLimitI = 0;
  mg_u_long fragLimitSize = (fragLimits==NULL) ? 0 : (*fragLimits).size();
  mg_u_long outI = 0;

  while (fragDataI < fragDataSize &&
     comFragDataI < comFragDataSize) {
    mg_s_long fragNum = (mg_s_long)fragData.fragNums[fragDataI];
    mg_s_long comFragNum = (mg_s_long)comFragData.fragNums[comFragDataI];
    
    // go to the right fragment limit (for the com frag)
    if (fragLimits != NULL) {
      while (fragLimitI+1 < fragLimitSize &&
         comFragNum > (mg_s_long)(*fragLimits)[fragLimitI+1].rangeStart) {
    ++fragLimitI;
      }
    }

    if (fragNum <= comFragNum+startRange ||
    (fragLimits!=NULL &&
     fragNum<=(mg_s_long)(*fragLimits)[fragLimitI].rangeStart)) {
      ++fragDataI;
      
    } else if (fragNum > comFragNum+endRange ||
           (fragLimits!=NULL &&
        fragNum>(mg_s_long)(*fragLimits)[fragLimitI].rangeEnd)) {
      ++comFragDataI;
      
    } else {
      // equal and within tag
      fragData.fragNums[outI] = comFragNum;
      if (needFragFreqs) {
    fragData.fragFreqs[outI] =
      (fragData.fragFreqs[fragDataI] < comFragData.fragFreqs[comFragDataI]) ?
      fragData.fragFreqs[fragDataI] : comFragData.fragFreqs[comFragDataI];
      }
      ++fragDataI;
      ++comFragDataI;
      ++outI;
    }
  }

  // erase unused part of fragData
  fragData.fragNums.erase (fragData.fragNums.begin()+outI,
               fragData.fragNums.end());
  if (needFragFreqs)
    fragData.fragFreqs.erase (fragData.fragFreqs.begin()+outI,
                  fragData.fragFreqs.end());
  else
    fragData.fragFreqs.erase (fragData.fragFreqs.begin(),
                  fragData.fragFreqs.end());
}


void FragsToQueryResult (IndexData &indexData,
             const QueryInfo &queryInfo,
             const FragData &termData,
             const UCArray &tag,
             const UCArray &term,
             mg_u_long stemMethod,
             mg_u_long termWeight,
             UCArrayVector &equivTerms,
             QueryResult &result) {
  bool needRanks = (queryInfo.sortByRank || queryInfo.needRankInfo);
  
  result.Clear();

  // log (N / ft)
  mg_u_long N = indexData.levels.levelInfo[indexData.curLevel].numEntries;
  // termData.matchDocs is not accurate - its just the largest docfreq out of the list of equiv terms. We'll delay calculating ranks until after we have worked out exactly how many docs we have
  //float wordLog = log((double)N / (double)termData.matchDocs);

  // Wqt = fqt * log (N / ft)
  // note: terms are allowed to have a weight of zero so
  // they can be excluded from the ranking
  //float Wqt = termWeight * wordLog;

  // Wdt = fdt * log (N / ft)
  //float Wdt;
  mg_u_long actual_num_match_docs = 0;
  vector<mg_u_long> docFreqsArray;

  mg_u_long termDataI = 0;
  mg_u_long termDataSize = termData.fragNums.size();
  mg_u_long levelDocNum = 0;
  
  mg_u_long termDocFreq = 0;
  mg_u_long lastLevelDocNum = 0;
  mg_u_long overallwordfreq = 0;
  
  while (termDataI < termDataSize) {
    if (indexData.levelConverter.FragToLevel (termData.fragNums[termDataI],
                          levelDocNum)) {
      if (levelDocNum != lastLevelDocNum) {
    if (lastLevelDocNum > 0) {
      // add this doc information
      if (needRanks) {
        //Wdt = termDocFreq * wordLog;
        //result.ranks.push_back (Wqt * Wdt);
        docFreqsArray.push_back(termDocFreq);
      }
      result.docs.push_back (lastLevelDocNum);
      ++actual_num_match_docs;
    }
    
    lastLevelDocNum = levelDocNum;
    termDocFreq = 0;
      }

      if (needRanks){
    termDocFreq += termData.fragFreqs[termDataI];
    overallwordfreq += termData.fragFreqs[termDataI];
      }
    }
    ++termDataI;
  }

  if (lastLevelDocNum > 0) {
    // add the last document information
    if (needRanks) {
      //Wdt = termDocFreq * wordLog;
      //result.ranks.push_back (Wqt * Wdt);
      docFreqsArray.push_back(termDocFreq);
    }
    result.docs.push_back (lastLevelDocNum);
    ++actual_num_match_docs;
  }
  // Now that we know the actual number of docs containing this term, we can calculate ranks
  float wordLog = log((double)N / (double)actual_num_match_docs);
  float Wqt = termWeight * wordLog;
  float factor = wordLog * Wqt;

  mg_u_long docFreqI = 0;
  mg_u_long docFreqSize = docFreqsArray.size();
  
  while (docFreqI < docFreqSize) {
    result.ranks.push_back(docFreqsArray[docFreqI]*factor);
    ++docFreqI;
  }

  // add the term frequency information
  if (queryInfo.needTermFreqs) {
    TermFreqData termFreqData;
    termFreqData.tag = tag;
    termFreqData.term = term;
    termFreqData.stemMethod = stemMethod;
    termFreqData.equivTerms = equivTerms;
    //termFreqData.matchDocs = termData.matchDocs;
    termFreqData.matchDocs = actual_num_match_docs;
    termFreqData.termFreq = overallwordfreq; // will be zero if needRankInfo 
                                              //not true
    result.termFreqs.push_back (termFreqData);
  }
}

void AndFragsToQueryResult (IndexData &indexData,
                const QueryInfo &queryInfo,
                const FragData &termData,
                const UCArray &tag,
                const UCArray &term,
                mg_u_long stemMethod,
                mg_u_long termWeight,
                UCArrayVector &equivTerms,
                QueryResult &result) {
  bool needRanks = (queryInfo.sortByRank || queryInfo.needRankInfo);
  
  // log (N / ft)
  float wordLog =
    log((double)indexData.levels.levelInfo[indexData.curLevel].numEntries/
    (double)termData.matchDocs);

  // Wqt = fqt * log (N / ft)
  // note: terms are allowed to have a weight of zero so
  // they can be excluded from the ranking
  float Wqt = termWeight * wordLog;

  // Wdt = fdt * log (N / ft)
  float Wdt;
  
  mg_u_long termDataI = 0;
  mg_u_long termDataSize = termData.fragNums.size();
  mg_u_long levelDocNum = 0;
  
  mg_u_long termDocFreq = 0;
  mg_u_long lastLevelDocNum = 0;
  mg_u_long overallwordfreq = 0;
  mg_u_long resultI = 0;
  mg_u_long resultSize = result.docs.size();
  mg_u_long resultOutI = 0;
  
  mg_u_long actual_num_term_match_docs = 0;
  
  while (termDataI < termDataSize) {
    if (indexData.levelConverter.FragToLevel (termData.fragNums[termDataI],
                          levelDocNum)) {
      if (levelDocNum != lastLevelDocNum) {
    if (lastLevelDocNum > 0) {
      ++actual_num_term_match_docs;

      Wdt = termDocFreq * wordLog;
      
      // find this document number
      while (resultI < resultSize &&
         result.docs[resultI] < lastLevelDocNum)
        ++resultI;
      
      // store the result
      if (resultI < resultSize && result.docs[resultI] == lastLevelDocNum) {
        result.docs[resultOutI] = lastLevelDocNum;
        if (needRanks)
          result.ranks[resultOutI] = result.ranks[resultI] + Wqt * Wdt;
        ++resultI;
        ++resultOutI;
      }
    }
    
    lastLevelDocNum = levelDocNum;
    termDocFreq = 0;
      }

      if (needRanks)
    termDocFreq += termData.fragFreqs[termDataI];
     overallwordfreq += termData.fragFreqs[termDataI]; 
    }
    
    ++termDataI;
  } // while

  if (lastLevelDocNum > 0) {
    ++actual_num_term_match_docs;
    // add the last document information
    Wdt = termDocFreq * wordLog;

    // find this document number
    while (resultI < resultSize &&
       result.docs[resultI] < lastLevelDocNum)
      ++resultI;
    
    // store the result
    if (resultI < resultSize && result.docs[resultI] == lastLevelDocNum) {
      result.docs[resultOutI] = lastLevelDocNum;
      if (needRanks)
    result.ranks[resultOutI] = result.ranks[resultI] + Wqt * Wdt;
      ++resultI;
      ++resultOutI;
    }
  }

  // remove unneeded entries
  result.docs.erase (result.docs.begin()+resultOutI, result.docs.end());
  if (needRanks)
    result.ranks.erase (result.ranks.begin()+resultOutI, result.ranks.end());
  else
    result.ranks.erase (result.ranks.begin(), result.ranks.end());
  
  // add the term frequency information
  if (queryInfo.needTermFreqs) {
    TermFreqData termFreqData;
    termFreqData.tag = tag;
    termFreqData.term = term;
    termFreqData.stemMethod = stemMethod;
    termFreqData.equivTerms = equivTerms;
    //termFreqData.matchDocs = termData.matchDocs;
    termFreqData.matchDocs = actual_num_term_match_docs;
    termFreqData.termFreq = overallwordfreq;
    result.termFreqs.push_back (termFreqData);
  }
}


void RemoveUnwantedResults (IndexData &indexData,
                const QueryInfo &queryInfo,
                const FragData &termData,
                QueryResult &result) {
  bool needRanks = (queryInfo.sortByRank || queryInfo.needRankInfo);

  mg_u_long termDataI = 0;
  mg_u_long termDataSize = termData.fragNums.size();
  mg_u_long levelDocNum = 0;
  
  mg_u_long lastLevelDocNum = 0;

  mg_u_long resultI = 0;
  mg_u_long resultSize = result.docs.size();
  mg_u_long resultOutI = 0;
  
  while (termDataI < termDataSize) {
    if (indexData.levelConverter.FragToLevel (termData.fragNums[termDataI],
                          levelDocNum)) {
      if (levelDocNum != lastLevelDocNum) {
    if (lastLevelDocNum > 0) {
      // find this document number
      while (resultI < resultSize &&
         result.docs[resultI] < lastLevelDocNum)
        ++resultI;
      
      // store the result
      if (resultI < resultSize && result.docs[resultI] == lastLevelDocNum) {
        result.docs[resultOutI] = lastLevelDocNum;
        if (needRanks)
          result.ranks[resultOutI] = result.ranks[resultI];
        ++resultI;
        ++resultOutI;
      }
    }
    
    lastLevelDocNum = levelDocNum;
      }
    }
    
    ++termDataI;
  }

  if (lastLevelDocNum > 0) {
    // find this document number
    while (resultI < resultSize &&
       result.docs[resultI] < lastLevelDocNum)
      ++resultI;
    
    // store the result
    if (resultI < resultSize && result.docs[resultI] == lastLevelDocNum) {
      result.docs[resultOutI] = lastLevelDocNum;
      if (needRanks) 
    result.ranks[resultOutI] = result.ranks[resultI];
      ++resultI;
      ++resultOutI;
    }
  }

  // remove unneeded entries
  result.docs.erase (result.docs.begin()+resultOutI, result.docs.end());
  if (needRanks)
    result.ranks.erase (result.ranks.begin()+resultOutI, result.ranks.end());
  else
    result.ranks.erase (result.ranks.begin(), result.ranks.end());
}



//--------------------------------------------------------------
// functions to support full text browse

void FindNearestWordNumber (IndexData &indexData,
                const UCArray &term,
                mg_u_long &number) {

    // find the word number for this term
    mg_u_long wordElNum = 0;
    mg_u_long numLevels = indexData.bdh.num_levels;
    word_block_dict_el wordDictEl;
    wordDictEl.SetNumLevels (numLevels);
    if (NearestSearchWordBlockDictEl (indexData.dictFile, indexData.biWords,
                      indexData.bdh.entries_per_wblk,
                      indexData.bdh.word_dict_size,
                      numLevels, term, wordDictEl, wordElNum))
      number = wordElNum;

}

void GetTermList(IndexData &indexData,
         mg_u_long startTerm,
         mg_u_long numTerms,
         TermFreqArray &terms) {

  word_block_dict_el_array wordBlocks; // = new word_block_dict_el_array();
  TermFreqData termdata;

  terms.erase(terms.begin(), terms.end());

  SearchWordBlockDictElNumRange (indexData.dictFile, indexData.biWords,
                 indexData.bdh.entries_per_wblk,
                 indexData.bdh.word_dict_size,
                 indexData.bdh.num_levels, startTerm,
                 numTerms, wordBlocks);

  word_block_dict_el_array::iterator here = wordBlocks.begin();
  word_block_dict_el_array::iterator end = wordBlocks.end();

  while (here != end) {
    termdata.Clear();
    termdata.term = (*here).el;
    termdata.termFreq = (*here).freq;
    terms.push_back(termdata);
    ++here;
  }

}

void GetTermList(IndexData &indexData,
         mg_u_long startTerm,
         mg_u_long numTerms,
         UCArrayVector &terms) {

  
  
  SearchWordBlockDictElNumRange (indexData.dictFile, indexData.biWords,
                 indexData.bdh.entries_per_wblk,
                 indexData.bdh.word_dict_size,
                 indexData.bdh.num_levels, startTerm,
                 numTerms, terms);

}