source: trunk/gsdl/src/phind/generate/check.h@ 2867

// check.h -- manipulate the suffixCheck array
//
// The suffixCheck array is used to prevent a phrase being added to
// the results of getExpansions.  It works by declaring an array that
// has one bit for each entry in the suffix array, which is cleared at
// the start of getExpansions.  As getExpansions adds each phrase to
// the result set, we set the bits in the suffixCheck array that
// correspond to the positions of of the phrase in the suffixArray.

// (The point is that getExpansions can later check whether a phrase
// or its prefix has been seen before by looking up the bit
// corresponding to its first occurence in the suffixCheck array: if
// the bit is set, a subphrase of this phrase is already in the
// results already, and the current phrase can be ignored.)

#include "suffix.h"

// The suffixCheck array
typedef unsigned char check;
check *suffixCheck;

// The length of the suffixCheck array
cellcount checkLength;

// Some useful bitmask constants 
const check ALLBITS = 255;
const check LEFTMOSTBIT = (ALLBITS << 7);
const check LEFTMOSTBITS[] = {0, 
                  (ALLBITS << 7), (ALLBITS << 6), (ALLBITS << 5), (ALLBITS << 4),
                  (ALLBITS << 3), (ALLBITS << 2), (ALLBITS << 1),  ALLBITS};
//const check LEFTMOSTBIT = 128;
//const check LEFTMOSTBITS[] = {0, 128, 192, 224, 240, 248, 252, 254, 255}; 


// Allocate the initial memory for suffixCheck
inline void allocateSuffixCheck(cellcount number_of_symbols) 
{
  checkLength = number_of_symbols / (sizeof(check) * 8) + 1;
  suffixCheck = new check[checkLength];
  if (suffixCheck == NULL) {
    cerr << "Suffix error: out of memory allocating suffixCheck array" << endl; 
    exit(2);
  }
  memset(suffixCheck, 0, sizeof(check) * checkLength);
}


// Set all bits in suffixCheck to 0
inline void clearSuffixCheck() 
{
  memset(suffixCheck, 0, sizeof(check) * checkLength);
}


// Get the value of a particular bit in suffixCheck
inline int getSuffixCheck(cellindex suff) 
{
  cellindex cell = suff >> 3;
  check remainder = suff & 0x07; // the last 3 bits
  if (suffixCheck[cell] & (LEFTMOSTBIT >> remainder)) {
    return 1;
  }
  return 0;
}                                                                               


// Set the value of a bit in suffixCheck to 1
inline void setSuffixCheck(cellindex suff) 
{
  cellindex cell = suff >> 3;
  check remainder = suff & 0x07; // the last 3 bits
  suffixCheck[cell] |= (LEFTMOSTBIT >> remainder);
}  


// Set the value of a range of bits in suffixCheck to 1
void setSuffixCheck(cellindex first, cellindex last) 
{
  for (cellcount i = first; i <= last; ++i)
    setSuffixCheck(i);
}


// Set the bits in a cell in the suffixArray.
// Bits are indexed 0-7.
inline void setCellBits(cellindex cell_offset, unsigned first_bit, unsigned last_bit) 
{
  unsigned number_of_bits = last_bit - first_bit + 1;
  check mask = (LEFTMOSTBITS[number_of_bits] >> first_bit);
  suffixCheck[cell_offset] |= mask;
}


inline void setSuffixCheck_new(cellindex first, cellindex last) 
{
  // If only one bit is set, use simpler function
  // We should be able to remove this case.
  if (first == last) {
    setSuffixCheck(first);
    return;
  }

  // Find the first and last cells in which bits are set
  cellindex first_cell = first >> 3;
  cellindex last_cell = last >> 3;

  // If all the values are in the same cell, set them
  if (first_cell == last_cell) {
    setCellBits(first_cell, (first & 0x07), (last & 0x07));
    return;
  }

  // Set the bits in the first and last cells
  setCellBits(first_cell, (first & 0x07), 7);
  setCellBits(last_cell, 0, (last & 0x07));

  // Set the bits in the intermediate cells
  ++first_cell;
  if(last_cell > first_cell)
    memset(suffixCheck + first_cell, ALLBITS, 
       (last_cell - first_cell) * sizeof(check));
}


// Print the suffixCheck array (for debugging)
void printSuffixCheck() 
{
  for (cellcount i = 0; i < checkLength; ++i) {
    cout << "cell " << i << "  \t";
    cout << "(" << (i * 8) << "-" << (i * 8 + 7) << ")    \t";
    for (cellindex j = 0; j < 8; ++j) {
      cout << getSuffixCheck(i * 8 + j);
      // cout << " (" << (i * 8 + j) << ") "; 
    }
    cout << " (" << (unsigned int) suffixCheck[i] << ")\n";
  }
}


//  To test, put this at the start of main

//  allocateSuffixCheck(300);
//  clearSuffixCheck();
//  setSuffixCheck(20);
//  setSuffixCheck(35,50);
//  setSuffixCheck(68,150);
//  setSuffixCheck(170,174);
//  setSuffixCheck(220,230);
//  setSuffixCheck(247);
//  setSuffixCheck(256);
//  printSuffixCheck();
//  exit(0);