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

/**********************************************************************
 *
 * 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 functions
  Phrase();
  Phrase(const Phrase &p);

  // A "partial" constructor: the first argument is an array of words,
  // second is its length, third is the direction (SUFFIX or PREFIX)
  // in which the words should be read (defaults to SUFFIX).
  Phrase(symbol *words, cellcount size, int direction);

  // Represent the phrase as an arracy of characters
  // You will have to call "delete []" on the array returned. 
  char *toString();

  // Find an initial set of candidate phrases in the suffix/prefix array
  void initialSuffixCandidates(vector<Phrase> &results);
  void 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();

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

  // Shorten a phrase by one symbol
  int shortenByOneAtSuffix();
  int shortenByOneAtPrefix();

  // 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
  inline void Phrase::ensureSuffixFound() {
    if (!suffixFound)
      findFirstAndLastSuffix();
  }
  inline void Phrase::ensurePrefixFound() {
    if (!prefixFound)
      findFirstAndLastPrefix();
  }

  // Output a phrase to a stream
  friend std::ostream &operator<<(std::ostream &stream, const Phrase &phrase);

  int uniqueSuffixExtension;
  int uniquePrefixExtension;

private:

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

  // 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);

};


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

#endif