source: trunk/gsdl/src/phind/generate/phrase.h@ 2498

/**********************************************************************
 *
 * phrase.h -- definition of the phrase object used by suffix.cpp
 *
 * Copyright 2000 Gordon W. Paynter
 * Copyright 2000 The New Zealand Digital Library Project
 *
 * A component of the Greenstone digital library software
 * from the New Zealand Digital Library Project at the
 * University of Waikato, New Zealand.
 *
 * 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.
 *
 *********************************************************************/

#ifndef PHRASE_H
#define PHRASE_H

// use the standard namespace
#if !defined (GSDL_NAMESPACE_BROKEN)
#if defined(GSDL_USE_OBJECTSPACE)
using namespace ospace::std;
#else
using namespace std;
#endif
#endif

#if defined(GSDL_USE_STL_H)
#  include <vector.h>
#else
#  include <vector>
#endif

#include "suffix.h"

class Phrase {

public:

  // The phrase itself is stored with two pointers: forward 
  // points to its first cell, back points to its last.
  // The length is always stored in length.
  // If one of these is set, all must be set, and it must 
  // be true that (forward + length - 1) = back
  symbol *forward;
  symbol *back;
  cellcount length;
  
  // Phrase location in the suffix array
  int suffixFound;
  symbol *firstSuffix;
  symbol *lastSuffix;
  cellindex firstSuffixIndex;
  cellindex lastSuffixIndex;
  cellcount suffixFrequency;

  // Phrase location in the prefix array
  int prefixFound;
  symbol* firstPrefix;
  symbol* lastPrefix;
  cellindex firstPrefixIndex;
  cellindex lastPrefixIndex;
  cellcount prefixFrequency;

  // Constructor function
  // First argument is an array of words, second is the length of
  // the phrase, third is the direction (SUFFIX of PREFIX) in
  // which the words should be read (defaults to forwards).
  Phrase(symbol *words, cellcount size, int direction);

  // An empty phrase can be created without arguments, but is 
  // good for nothing and may not be used with any public fuctions.
  // We therefore only use it internally.
  Phrase();

  // Represent the phrase as  a string
  char *toString();

  // Find an initial set of candidate phrases in the suffix/prefix array
  int initialSuffixCandidates(vector<Phrase> &results);
  int initialPrefixCandidates(vector<Phrase> &results);
  
  // Does the phrase have a unique extension?
  int hasUniqueSuffixExtension();
  int hasUniquePrefixExtension();
  
  // Extend a phrase by exactly one symbol
  int expandUniquePrefixExtensionByOne();
  int expandUniqueSuffixExtensionByOne();

  // Find the phrase in the suffix/prefix array
  int findFirstAndLastSuffix();
  int findFirstAndLastPrefix();
  int findFirstAndLastSuffix(cellindex begin, cellindex end);
  int findFirstAndLastPrefix(cellindex begin, cellindex end);

  // Make sure the phrase location in the suffix/prefix array is known
  int ensureSuffixFound();
  int ensurePrefixFound();

private:

  // Does the phrase have a unique suffix/prefix extension?
  // if yes, then 1; if no then 0; if unknown then -1;
  int uniqueSuffixExtension;
  int uniquePrefixExtension;

  // reset a phrase
  int empty();

  // reset phrase information relating to location in suffix/prefix array
  int clearSuffix();
  int clearPrefix();

  // increase the length of a phrase "in place"
  int Phrase::increaseSuffixLength(cellcount l);
  int Phrase::increasePrefixLength(cellcount l);
    
  // Compare the phrase to a given array of symbols
  int compareSuffix(symbol *words, cellcount length);
  int comparePrefix(symbol *words, cellcount length);

  // Create a new phrase that is longer than this one, yet as short as possible.
  Phrase Phrase::newPhraseShortestSuffixExpansion(cellindex i);
  Phrase Phrase::newPhraseShortestPrefixExpansion(cellindex i);

  // Extend a phrase until it no longer has a unique extanesion
  int expandWhileUniqueSuffixExtension();
  int expandWhileUniquePrefixExtension();
};


bool isShorter(Phrase p1, Phrase p2);
bool isLonger(Phrase p1, Phrase p2);

#endif