<?PHP
#
#   FILE:  SearchEngine.php
#
#   Open Source Metadata Archive Search Engine (OSMASE)
#   Copyright 2002-2014 Edward Almasy and Internet Scout Research Group
#   http://scout.wisc.edu
#

/**
* Core metadata archive search engine class.
*/
class SearchEngine
{

    # ---- PUBLIC INTERFACE --------------------------------------------------

    # possible types of logical operators
    const LOGIC_AND = 1;
    const LOGIC_OR = 2;

    # flags used for indicating field types
    const FIELDTYPE_TEXT = 1;
    const FIELDTYPE_NUMERIC = 2;
    const FIELDTYPE_DATE = 3;
    const FIELDTYPE_DATERANGE = 4;

    # flags used for indicating word states
    const WORD_PRESENT = 1;
    const WORD_EXCLUDED = 2;
    const WORD_REQUIRED = 4;

    /**
    * Object constructor.
    * @param string $ItemTableName Name of database table containing items.
    * @param string $ItemIdFieldName Name of column in item database table
    *       containing item IDs.
    * @param string $ItemTypeFieldName Name of column in item database table
    *       containing item types.
    */
    public function __construct(
            $ItemTableName, $ItemIdFieldName, $ItemTypeFieldName)
    {
        # create database object for our use
        $this->DB = new Database();

        # save item access parameters
        $this->ItemTableName = $ItemTableName;
        $this->ItemIdFieldName = $ItemIdFieldName;
        $this->ItemTypeFieldName = $ItemTypeFieldName;

        # set default debug state
        $this->DebugLevel = 0;
    }

    /**
    * Add field to include in searching.
    * @param int $FieldId ID of field.
    * @param int $FieldType Type of field (FIELDTYPE_ constant value).
    * @param mixed $ItemTypes Item type or array of item types to which the
    *       field applies.
    * @param int $Weight Numeric search weight for field.
    * @param bool $UsedInKeywordSearch If TRUE, field is included in keyword
    *       searches.
    */
    public function AddField($FieldId, $FieldType, $ItemTypes,
            $Weight, $UsedInKeywordSearch)
    {
        # save values
        $this->FieldInfo[$FieldId]["FieldType"] = $FieldType;
        $this->FieldInfo[$FieldId]["Weight"] = $Weight;
        $this->FieldInfo[$FieldId]["InKeywordSearch"] =
                $UsedInKeywordSearch ? TRUE : FALSE;
        $this->FieldInfo[$FieldId]["ItemTypes"] = is_array($ItemTypes)
                ? $ItemTypes : array($ItemTypes);
    }

    /**
    * Get type of specified field (text/numeric/date/daterange).
    * @param int $FieldId ID of field.
    * @return int Field type (FIELDTYPE_ constant).
    */
    public function FieldType($FieldId)
    {
        return $this->FieldInfo[$FieldId]["FieldType"];
    }

    /**
    * Get search weight for specified field.
    * @param int $FieldId ID of field.
    * @return int Search weight.
    */
    public function FieldWeight($FieldId)
    {
        return $this->FieldInfo[$FieldId]["Weight"];
    }

    /**
    * Get whether specified field is included in keyword searches.
    * @param int $FieldId ID of field.
    * @return bool TRUE if field is included in keyword search, otherwise FALSE.
    */
    public function FieldInKeywordSearch($FieldId)
    {
        return $this->FieldInfo[$FieldId]["InKeywordSearch"];
    }

    /**
    * Set debug output level.  Values above zero trigger diagnostic output.
    * @param int $NewValue New debugging level.
    */
    public function DebugLevel($NewValue)
    {
        $this->DebugLevel = $NewValue;
    }


    # ---- search functions

    /**
    * Perform search with specified parameters.
    * @param mixed $SearchParams Search parameters as SearchParameterSet
    *       object or keyword search string.
    * @param int $StartingResult Starting index into results.  (OPTIONAL,
    *       defaults to 0)
    * @param int $NumberOfResults Number of results to return.  (OPTIONAL,
    *       defaults to PHP_INT_MAX)
    * @param string $SortByField ID of field or array of IDs of fields
    *       (indexed by item type) to sort results by.  (OPTIONAL, defaults
    *       to NULL, which indicates to sort by relevance score)
    * @param mixed $SortDescending If TRUE, sort in descending order, otherwise
    *       sort in ascending order.  May also be array of boolean values, with
    *       item types for the index.  (OPTIONAL, defaults to TRUE)
    * @return array Array of arrays of search result scores, with the item
    *       type for the first index and the IDs of items found by search
    *       as the second index.
    */
    public function Search(
            $SearchParams, $StartingResult = 0, $NumberOfResults = PHP_INT_MAX,
            $SortByField = NULL, $SortDescending = TRUE)
    {
        # if keyword search string was passed in
        if (is_string($SearchParams))
        {
            # convert string to search parameter set
            $SearchString = $SearchParams;
            $SearchParams = new SearchParameterSet();
            $SearchParams->AddParameter($SearchString);
        }

        # interpret and filter out magic debugging keyword (if any)
        $KeywordStrings = $SearchParams->GetKeywordSearchStrings();
        foreach ($KeywordStrings as $String)
        {
            $FilteredString = $this->ExtractDebugLevel($String);
            if ($FilteredString != $String)
            {
                $SearchParams->RemoveParameter($String);
                $SearchParams->AddParameter($FilteredString);
            }
        }

        # save start time to use in calculating search time
        $StartTime = microtime(TRUE);

        # clear parsed search term list
        $this->SearchTermList = array();

        # perform search
        $Scores = $this->RawSearch($SearchParams);

        # count, sort, and trim search result scores list
        $Scores = $this->CleanScores($Scores, $StartingResult, $NumberOfResults,
                $SortByField, $SortDescending);

        # record search time
        $this->LastSearchTime = microtime(TRUE) - $StartTime;

        # return search results to caller
        $this->DMsg(0, "Ended up with ".$this->NumberOfResultsAvailable." results");
        return $Scores;
    }

    /**
    * Perform search across multiple fields, with different values or
    * comparisons specified for each field.  This method is DEPRECATED --
    * please use SearchEngine::Search() with a SearchParameterSet object instead.
    * @param array $SearchStrings Array of search strings, with field names
    *       for index.
    * @param int $StartingResult Starting index into results.  (OPTIONAL,
    *       defaults to 0)
    * @param int $NumberOfResults Number of results to return.  (OPTIONAL,
    *       defaults to 10)
    * @param string $SortByField Name of field to sort results by.  (OPTIONAL,
    *       defaults to relevance score)
    * @param bool $SortDescending If TRUE, results will be sorted in
    *       descending order, otherwise results will be sorted in
    *       ascending order.  (OPTIONAL, defaults to TRUE)
    * @return array Array of search result scores, with the IDs of items
    *       found by search as the index.
    * @see SearchEngine::Search()
    */
    public function FieldedSearch(
            $SearchStrings, $StartingResult = 0, $NumberOfResults = 10,
            $SortByField = NULL, $SortDescending = TRUE)
    {
        # pass off the request to grouped search (for now) if appropriate
        if ($SearchStrings instanceof SearchParameterSet)
        {
            return $this->GroupedSearch($SearchStrings, $StartingResult,
                    $NumberOfResults, $SortByField, $SortDescending);
        }

        # interpret and filter out magic debugging keyword (if any)
        $SearchStrings = $this->SetDebugLevel($SearchStrings);
        $this->DMsg(0, "In FieldedSearch() with "
                .count($SearchStrings)." search strings");

        # save start time to use in calculating search time
        $StartTime = microtime(TRUE);

        # perform search
        $Scores = $this->SearchAcrossFields($SearchStrings);
        $Scores = ($Scores === NULL) ? array() : $Scores;

        # count, sort, and trim search result scores list
        $Scores = $this->CleanScores($Scores, $StartingResult, $NumberOfResults,
                $SortByField, $SortDescending);

        # record search time
        $this->LastSearchTime = microtime(TRUE) - $StartTime;

        # return list of items to caller
        $this->DMsg(0, "Ended up with ".$this->NumberOfResultsAvailable." results");
        return $Scores;
    }

    /**
    * Add function that will be called to filter search results.
    * @param callable $FunctionName Function to be called.
    */
    public function AddResultFilterFunction($FunctionName)
    {
        # save filter function name
        $this->FilterFuncs[] = $FunctionName;
    }

    /**
    * Get number of results found by most recent search.
    * @param int $ItemType Type of item.  (OPTIONAL, defaults to total
    *       for all items)
    * @return int Result count.
    */
    public function NumberOfResults($ItemType = NULL)
    {
        return ($ItemType === NULL) ? $this->NumberOfResultsAvailable
                : (isset($this->NumberOfResultsPerItemType[$ItemType])
                        ? $this->NumberOfResultsPerItemType[$ItemType] : 0);
    }

    /**
    * Get normalized list of search terms.
    * @return array Array of search terms.
    */
    public function SearchTerms()
    {
        return $this->SearchTermList;
    }

    /**
    * Get time that last search took, in seconds.
    * @return float Time in seconds, with microseconds.
    */
    public function SearchTime()
    {
        return $this->LastSearchTime;
    }

    /**
    * Get total of weights for all fields involved in search, useful for
    * assessing scale of scores in search results.
    * @param object $SearchParams Search parameters (SearchParameterSet).
    * @return int Total of weights.
    */
    public function FieldedSearchWeightScale($SearchParams)
    {
        $Weight = 0;
        $FieldIds = $SearchParams->GetFields();
        foreach ($FieldIds as $FieldId)
        {
            if (array_key_exists($FieldId, $this->FieldInfo))
            {
                $Weight += $this->FieldInfo[$FieldId]["Weight"];
            }
        }
        if (count($SearchParams->GetKeywordSearchStrings()))
        {
            foreach ($this->FieldInfo as $FieldId => $Info)
            {
                if ($Info["InKeywordSearch"])
                {
                    $Weight += $Info["Weight"];
                }
            }
        }
        return $Weight;
    }


    # ---- search database update functions

    /**
    * Update search database for the specified item.
    * @param int $ItemId ID of item.
    * @param int $ItemType Numerical type of item.
    */
    public function UpdateForItem($ItemId, $ItemType)
    {
        # clear word count added flags for this item
        unset($this->WordCountAdded);

        # delete any existing info for this item
        $this->DB->Query("DELETE FROM SearchWordCounts WHERE ItemId = ".$ItemId);
        $this->DB->Query("DELETE FROM SearchItemTypes WHERE ItemId = ".$ItemId);

        # save item type
        $this->DB->Query("INSERT INTO SearchItemTypes (ItemId, ItemType)"
                ." VALUES (".intval($ItemId).", ".intval($ItemType).")");

        # for each metadata field
        foreach ($this->FieldInfo as $FieldId => $Info)
        {
            # if valid search weight for field and field applies to this item
            if (($Info["Weight"] > 0)
                    && in_array($ItemType, $Info["ItemTypes"]))
            {
                # retrieve text for field
                $Text = $this->GetFieldContent($ItemId, $FieldId);

                # if text is array
                if (is_array($Text))
                {
                    # for each text string in array
                    foreach ($Text as $String)
                    {
                        # record search info for text
                        $this->RecordSearchInfoForText($ItemId, $FieldId,
                                                       $Info["Weight"], $String,
                                                       $Info["InKeywordSearch"]);
                    }
                }
                else
                {
                    # record search info for text
                    $this->RecordSearchInfoForText($ItemId, $FieldId,
                                                   $Info["Weight"], $Text,
                                                   $Info["InKeywordSearch"]);
                }
            }
        }
    }

    /**
    * Update search database for the specified range of items.
    * @param int $StartingItemId ID of item to start with.
    * @param int $NumberOfItems Maximum number of items to update.
    * @return int ID of last item updated.
    */
    public function UpdateForItems($StartingItemId, $NumberOfItems)
    {
        # retrieve IDs for specified number of items starting at specified ID
        $this->DB->Query("SELECT ".$this->ItemIdFieldName.", ".$this->ItemTypeFieldName
                ." FROM ".$this->ItemTableName
                ." WHERE ".$this->ItemIdFieldName." >= ".$StartingItemId
                ." ORDER BY ".$this->ItemIdFieldName." LIMIT ".$NumberOfItems);
        $ItemIds = $this->DB->FetchColumn(
                $this->ItemTypeFieldName, $this->ItemIdFieldName);

        # for each retrieved item ID
        foreach ($ItemIds as $ItemId => $ItemType)
        {
            # update search info for item
            $this->UpdateForItem($ItemId, $ItemType);
        }

        # return ID of last item updated to caller
        return $ItemId;
    }

    /**
    * Drop all data pertaining to item from search database.
    * @param int $ItemId ID of item to drop from database.
    */
    public function DropItem($ItemId)
    {
        # drop all entries pertaining to item from word count table
        $this->DB->Query("DELETE FROM SearchWordCounts WHERE ItemId = ".$ItemId);
        $this->DB->Query("DELETE FROM SearchItemTypes WHERE ItemId = ".$ItemId);
    }

    /**
    * Drop all data pertaining to field from search database.
    * @param int $FieldId ID of field to drop.
    */
    public function DropField($FieldId)
    {
        # drop all entries pertaining to field from word counts table
        $this->DB->Query("DELETE FROM SearchWordCounts WHERE FieldId = \'".$FieldId."\'");
    }

    /**
    * Get total number of search terms indexed by search engine.
    * @return int Count of terms.
    */
    public function SearchTermCount()
    {
        return $this->DB->Query("SELECT COUNT(*) AS TermCount"
                ." FROM SearchWords", "TermCount");
    }

    /**
    * Get total number of items indexed by search engine.
    * @return int Count of items.
    */
    public function ItemCount()
    {
        return $this->DB->Query("SELECT COUNT(DISTINCT ItemId) AS ItemCount"
                ." FROM SearchWordCounts", "ItemCount");
    }

    /**
    * Add synonyms.
    * @param string $Word Word for which synonyms should apply.
    * @param array $Synonyms Array of synonyms.
    * @return int Count of new synonyms added.  (May be less than the number
    *       passed in, if some synonyms were already defined.)
    */
    public function AddSynonyms($Word, $Synonyms)
    {
        # asssume no synonyms will be added
        $AddCount = 0;

        # get ID for word
        $WordId = $this->GetWordId($Word, TRUE);

        # for each synonym passed in
        foreach ($Synonyms as $Synonym)
        {
            # get ID for synonym
            $SynonymId = $this->GetWordId($Synonym, TRUE);

            # if synonym is not already in database
            $this->DB->Query("SELECT * FROM SearchWordSynonyms"
                    ." WHERE (WordIdA = ".$WordId
                        ." AND WordIdB = ".$SynonymId.")"
                    ." OR (WordIdB = ".$WordId
                        ." AND WordIdA = ".$SynonymId.")");
            if ($this->DB->NumRowsSelected() == 0)
            {
                # add synonym entry to database
                $this->DB->Query("INSERT INTO SearchWordSynonyms"
                        ." (WordIdA, WordIdB)"
                        ." VALUES (".$WordId.", ".$SynonymId.")");
                $AddCount++;
            }
        }

        # report to caller number of new synonyms added
        return $AddCount;
    }

    /**
    * Remove synonym(s).
    * @param string $Word Word for which synonyms should apply.
    * @param array $Synonyms Array of synonyms to remove.  If not
    *       specified, all synonyms for word will be removed.  (OPTIONAL)
    */
    public function RemoveSynonyms($Word, $Synonyms = NULL)
    {
        # find ID for word
        $WordId = $this->GetWordId($Word);

        # if ID found
        if ($WordId !== NULL)
        {
            # if no specific synonyms provided
            if ($Synonyms === NULL)
            {
                # remove all synonyms for word
                $this->DB->Query("DELETE FROM SearchWordSynonyms"
                        ." WHERE WordIdA = '".$WordId."'"
                        ." OR WordIdB = '".$WordId."'");
            }
            else
            {
                # for each specified synonym
                foreach ($Synonyms as $Synonym)
                {
                    # look up ID for synonym
                    $SynonymId = $this->GetWordId($Synonym);

                    # if synonym ID was found
                    if ($SynonymId !== NULL)
                    {
                        # delete synonym entry
                        $this->DB->Query("DELETE FROM SearchWordSynonyms"
                                ." WHERE (WordIdA = '".$WordId."'"
                                    ." AND WordIdB = '".$SynonymId."')"
                                ." OR (WordIdB = '".$WordId."'"
                                    ." AND WordIdA = '".$SynonymId."')");
                    }
                }
            }
        }
    }

    /**
    * Remove all synonyms.
    */
    public function RemoveAllSynonyms()
    {
        $this->DB->Query("DELETE FROM SearchWordSynonyms");
    }

    /**
    * Get synonyms for word.
    * @param string $Word Word for which synonyms should apply.
    * @return array Array of synonyms.
    */
    public function GetSynonyms($Word)
    {
        # assume no synonyms will be found
        $Synonyms = array();

        # look up ID for word
        $WordId = $this->GetWordId($Word);

        # if word ID was found
        if ($WordId !== NULL)
        {
            # look up IDs of all synonyms for this word
            $this->DB->Query("SELECT WordIdA, WordIdB FROM SearchWordSynonyms"
                    ." WHERE WordIdA = ".$WordId
                    ." OR WordIdB = ".$WordId);
            $SynonymIds = array();
            while ($Record = $this->DB->FetchRow)
            {
                $SynonymIds[] = ($Record["WordIdA"] == $WordId)
                        ? $Record["WordIdB"] : $Record["WordIdA"];
            }

            # for each synonym ID
            foreach ($SynonymIds as $SynonymId)
            {
                # look up synonym word and add to synonym list
                $Synonyms[] = $this->GetWord($SynonymId);
            }
        }

        # return synonyms to caller
        return $Synonyms;
    }

    /**
    * Get all synonyms.
    * @return array Array of arrays of synonyms, with words for index.
    */
    public function GetAllSynonyms()
    {
        # assume no synonyms will be found
        $SynonymList = array();

        # for each synonym ID pair
        $OurDB = new Database();
        $OurDB->Query("SELECT WordIdA, WordIdB FROM SearchWordSynonyms");
        while ($Record = $OurDB->FetchRow())
        {
            # look up words
            $Word = $this->GetWord($Record["WordIdA"]);
            $Synonym = $this->GetWord($Record["WordIdB"]);

            # if we do not already have an entry for the word
            #       or synonym is not listed for this word
            if (!isset($SynonymList[$Word])
                    || !in_array($Synonym, $SynonymList[$Word]))
            {
                # add entry for synonym
                $SynonymList[$Word][] = $Synonym;
            }

            # if we do not already have an entry for the synonym
            #       or word is not listed for this synonym
            if (!isset($SynonymList[$Synonym])
                    || !in_array($Word, $SynonymList[$Synonym]))
            {
                # add entry for word
                $SynonymList[$Synonym][] = $Word;
            }
        }

        # for each word
        # (this loop removes reciprocal duplicates)
        foreach ($SynonymList as $Word => $Synonyms)
        {
            # for each synonym for that word
            foreach ($Synonyms as $Synonym)
            {
                # if synonym has synonyms and word is one of them
                if (isset($SynonymList[$Synonym])
                        && isset($SynonymList[$Word])
                        && in_array($Word, $SynonymList[$Synonym])
                        && in_array($Synonym, $SynonymList[$Word]))
                {
                    # if word has less synonyms than synonym
                    if (count($SynonymList[$Word])
                            < count($SynonymList[$Synonym]))
                    {
                        # remove synonym from synonym list for word
                        $SynonymList[$Word] = array_diff(
                                $SynonymList[$Word], array($Synonym));

                        # if no synonyms left for word
                        if (!count($SynonymList[$Word]))
                        {
                            # remove empty synonym list for word
                            unset($SynonymList[$Word]);
                        }
                    }
                    else
                    {
                        # remove word from synonym list for synonym
                        $SynonymList[$Synonym] = array_diff(
                                $SynonymList[$Synonym], array($Word));

                        # if no synonyms left for word
                        if (!count($SynonymList[$Synonym]))
                        {
                            # remove empty synonym list for word
                            unset($SynonymList[$Synonym]);
                        }
                    }
                }
            }
        }

        # sort array alphabetically (just for convenience)
        foreach ($SynonymList as $Word => $Synonyms)
        {
            asort($SynonymList[$Word]);
        }
        ksort($SynonymList);

        # return 2D array of synonyms to caller
        return $SynonymList;
    }

    /**
    * Set all synonyms.  This removes any existing synonyms and replaces
    * them with the synonyms passed in.
    * @param array $SynonymList Array of arrays of synonyms, with words for index.
    */
    public function SetAllSynonyms($SynonymList)
    {
        # remove all existing synonyms
        $this->RemoveAllSynonyms();

        # for each synonym entry passed in
        foreach ($SynonymList as $Word => $Synonyms)
        {
            # add synonyms for word
            $this->AddSynonyms($Word, $Synonyms);
        }
    }

    /**
    * Load synonyms from a file.  Each line of file should contain one word
    * at the beginning of the line, followed by one or more synonyms
    * separated by spaces or commas.  Blank lines or lines beginning with
    * "#" (i.e. comments) will be ignored.
    * @param string $FileName Name of file containing synonyms (with path if needed).
    * @return Number of new synonyms added.
    */
    public function LoadSynonymsFromFile($FileName)
    {
        # asssume no synonyms will be added
        $AddCount = 0;

        # read in contents of file
        $Lines = file($FileName, FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);

        # if file contained lines
        if (count($Lines))
        {
            # for each line of file
            foreach ($Lines as $Line)
            {
                # if line is not a comment
                if (!preg_match("/[\s]*#/", $Line))
                {
                    # split line into words
                    $Words = preg_split("/[\s,]+/", $Line);

                    # if synonyms found
                    if (count($Words) > 1)
                    {
                        # separate out word and synonyms
                        $Word = array_shift($Words);

                        # add synonyms
                        $AddCount += $this->AddSynonyms($Word, $Words);
                    }
                }
            }
        }

        # return count of synonyms added to caller
        return $AddCount;
    }


    # ---- PRIVATE INTERFACE -------------------------------------------------

    protected $DB;
    protected $DebugLevel;
    protected $FilterFuncs;
    protected $ItemIdFieldName;
    protected $ItemTableName;
    protected $ItemTypeFieldName;
    protected $LastSearchTime;
    protected $NumberOfResultsAvailable;
    protected $StemmingEnabled = TRUE;
    protected $SynonymsEnabled = TRUE;

    private $ExcludedTermCount;
    private $FieldIds;
    private $FieldInfo;
    private $InclusiveTermCount;
    private $RequiredTermCount;
    private $RequiredTermCounts;
    private $SearchTermList;
    private $WordCountAdded;

    const KEYWORD_FIELD_ID = -100;
    const STEM_ID_OFFSET = 1000000;


    # ---- private methods (searching)

    /**
    * Perform search based on supplied parameters.  This is an internal
    * method, with no timing or result score cleaning or other trappings,
    * suitable for recursively searching subgroups.
    * @param object $SearchParams Search parameter set.
    * @return array Result scores, with item IDs for the index.
    */
    private function RawSearch($SearchParams)
    {
        # retrieve search strings
        $SearchStrings = $SearchParams->GetSearchStrings();
        $KeywordSearchStrings = $SearchParams->GetKeywordSearchStrings();

        # add keyword searches (if any) to fielded searches
        if (count($KeywordSearchStrings))
        {
            $SearchStrings[self::KEYWORD_FIELD_ID] = $KeywordSearchStrings;
        }

        # normalize search strings
        $NormalizedSearchStrings = array();
        foreach ($SearchStrings as $FieldId => $SearchStringArray)
        {
            if (!is_array($SearchStringArray))
            {
                $SearchStringArray = array($SearchStringArray);
            }
            foreach ($SearchStringArray as $String)
            {
                $String = trim($String);
                if (strlen($String))
                {
                    $NormalizedSearchStrings[$FieldId][] = $String;
                }
            }
        }
        $SearchStrings = $NormalizedSearchStrings;

        # if we have strings to search for
        if (count($SearchStrings))
        {
            # perform search
            $Scores = $this->SearchAcrossFields(
                    $SearchStrings, $SearchParams->Logic());
        }

        # for each subgroup
        foreach ($SearchParams->GetSubgroups() as $Subgroup)
        {
            # perform subgroup search
            $NewScores = $this->RawSearch($Subgroup);

            # added subgroup search scores to previous scores as appropriate
            if (isset($Scores))
            {
                $Scores = $this->CombineScores(
                        $Scores, $NewScores, $SearchParams->Logic());
            }
            else
            {
                $Scores = $NewScores;
            }
        }
        if (isset($NewScores))
        {
            $this->DMsg(2, "Have ".count($Scores)
                    ." results after subgroup processing");
        }

        # pare down results to just allowed item types (if specified)
        if ($SearchParams->ItemTypes())
        {
            $AllowedItemTypes = $SearchParams->ItemTypes();
            foreach ($Scores as $ItemId => $Score)
            {
                if (!in_array($this->GetItemType($ItemId), $AllowedItemTypes))
                {
                    unset($Scores[$ItemId]);
                }
            }
            $this->DMsg(3, "Have ".count($Scores)
                    ." results after paring to allowed item types");
        }

        # return search results to caller
        return isset($Scores) ? $Scores : array();
    }

    /**
    * Combine two sets of search result scores, based on specified logic.
    * @param array $ScoresA First set of scores.
    * @param array $ScoresB Second set of scores.
    * @param string $Logic Logic to use ("AND" or "OR").
    * @return array Resulting combined scores.
    */
    private function CombineScores($ScoresA, $ScoresB, $Logic)
    {
        if ($Logic == "OR")
        {
            $Scores = $ScoresA;
            foreach ($ScoresB as $ItemId => $Score)
            {
                if (isset($Scores[$ItemId]))
                {
                    $Scores[$ItemId] += $Score;
                }
                else
                {
                    $Scores[$ItemId] = $Score;
                }
            }
        }
        else
        {
            $Scores = array();
            foreach ($ScoresA as $ItemId => $Score)
            {
                if (isset($ScoresB[$ItemId]))
                {
                    $Scores[$ItemId] = $Score + $ScoresB[$ItemId];
                }
            }
        }
        return $Scores;
    }

    /**
    * Perform search across multiple fields and return raw (untrimmed)
    * results to caller.
    * @param array $SearchStrings Array of search strings, with field IDs
    *       for index.
    * @param string $Logic Search logic ("AND" or "OR").
    * @return array Array of search result scores, with the IDs of items
    *       found by search as the index.
    */
    private function SearchAcrossFields($SearchStrings, $Logic)
    {
        # start by assuming no search will be done
        $Scores = array();

        # clear word counts
        $this->ExcludedTermCount = 0;
        $this->InclusiveTermCount = 0;
        $this->RequiredTermCount = 0;
        $this->RequiredTermCounts = array();

        # for each field
        $NeedComparisonSearch = FALSE;
        foreach ($SearchStrings as $FieldId => $SearchStringArray)
        {
            # for each search string for this field
            foreach ($SearchStringArray as $SearchString)
            {
                # if field is keyword or field is text and does not look
                #       like comparison match
                $NotComparisonSearch = !preg_match("/^[><!]=./", $SearchString)
                        && !preg_match('/^[><=^$]./', $SearchString);
                if (($FieldId == self::KEYWORD_FIELD_ID)
                        || (isset($this->FieldInfo[$FieldId])
                                && ($this->FieldInfo[$FieldId]["FieldType"]
                                        == self::FIELDTYPE_TEXT)
                                && $NotComparisonSearch))
                {
                    $this->DMsg(0, "Searching text field \""
                            .$FieldId."\" for string \"$SearchString\"");

                    # normalize text and split into words
                    $Words[$FieldId] =
                            $this->ParseSearchStringForWords($SearchString, $Logic);

                    # calculate scores for matching items
                    if (count($Words[$FieldId]))
                    {
                        $Scores = $this->SearchForWords(
                                $Words[$FieldId], $FieldId, $Scores);
                        $this->DMsg(3, "Have "
                                .count($Scores)." results after word search");
                    }

                    # split into phrases
                    $Phrases[$FieldId] = $this->ParseSearchStringForPhrases(
                            $SearchString, $Logic);

                    # handle any phrases
                    if (count($Phrases[$FieldId]))
                    {
                        $Scores = $this->SearchForPhrases(
                                $Phrases[$FieldId], $Scores, $FieldId, TRUE, FALSE);
                        $this->DMsg(3, "Have "
                                .count($Scores)." results after phrase search");
                    }
                }
                else
                {
                    # set flag to indicate possible comparison search candidate found
                    $NeedComparisonSearch = TRUE;
                }
            }
        }

        # perform comparison searches
        if ($NeedComparisonSearch)
        {
            $Scores = $this->SearchForComparisonMatches(
                    $SearchStrings, $Logic, $Scores);
            $this->DMsg(3, "Have ".count($Scores)." results after comparison search");
        }

        # if no results found and exclusions specified
        if (!count($Scores) && $this->ExcludedTermCount)
        {
            # load all records
            $Scores = $this->LoadScoresForAllRecords();
        }

        # if search results found
        if (count($Scores))
        {
            # for each search text string
            foreach ($SearchStrings as $FieldId => $SearchStringArray)
            {
                # for each search string for this field
                foreach ($SearchStringArray as $SearchString)
                {
                    # if field is text
                    if (($FieldId == self::KEYWORD_FIELD_ID)
                            || (isset($this->FieldInfo[$FieldId])
                                && ($this->FieldInfo[$FieldId]["FieldType"]
                                        == self::FIELDTYPE_TEXT)))
                    {
                        # if there are words in search text
                        if (isset($Words[$FieldId]))
                        {
                            # handle any excluded words
                            $Scores = $this->FilterOnExcludedWords(
                                    $Words[$FieldId], $Scores, $FieldId);
                        }

                        # handle any excluded phrases
                        if (isset($Phrases[$FieldId]))
                        {
                            $Scores = $this->SearchForPhrases(
                                    $Phrases[$FieldId], $Scores,
                                    $FieldId, FALSE, TRUE);
                        }
                    }
                }
                $this->DMsg(3, "Have ".count($Scores)
                        ." results after processing exclusions");
            }

            # strip off any results that don't contain required words
            $Scores = $this->FilterOnRequiredWords($Scores);
        }

        # return search result scores to caller
        return $Scores;
    }

    /**
    * Search for words in specified field.
    * @param array $Words Terms to search for.
    * @param string $FieldId ID of field to search.
    * @param array $Scores Existing array of search result scores to build
    *       on, with item IDs for the index and scores for the values.
    * @return array Array of search result scores, with item IDs for the
    *       index and scores for the values.
    */
    private function SearchForWords($Words, $FieldId, $Scores = NULL)
    {
        $DB = $this->DB;

        # start with empty search result scores list if none passed in
        if ($Scores == NULL)
        {
            $Scores = array();
        }

        # for each word
        foreach ($Words as $Word => $Flags)
        {
            unset($Counts);
            $this->DMsg(2, "Searching for word '${Word}' in field ".$FieldId);

            # if word is not excluded
            if (!($Flags & self::WORD_EXCLUDED))
            {
                # look up record ID for word
                $this->DMsg(2, "Looking up word \"".$Word."\"");
                $WordId = $this->GetWordId($Word);

                # if word is in DB
                if ($WordId !== NULL)
                {
                    # look up counts for word
                    $DB->Query("SELECT ItemId,Count FROM SearchWordCounts "
                            ."WHERE WordId = ".$WordId
                            ." AND FieldId = ".$FieldId);
                    $Counts = $DB->FetchColumn("Count", "ItemId");

                    # if synonym support is enabled
                    if ($this->SynonymsEnabled)
                    {
                        # look for any synonyms
                        $DB->Query("SELECT WordIdA, WordIdB"
                                ." FROM SearchWordSynonyms"
                                ." WHERE WordIdA = ".$WordId
                                ." OR WordIdB = ".$WordId);

                        # if synonyms were found
                        if ($DB->NumRowsSelected())
                        {
                            # retrieve synonym IDs
                            $SynonymIds = array();
                            while ($Record = $DB->FetchRow())
                            {
                                $SynonymIds[] = ($Record["WordIdA"] == $WordId)
                                        ? $Record["WordIdB"]
                                        : $Record["WordIdA"];
                            }

                            # for each synonym
                            foreach ($SynonymIds as $SynonymId)
                            {
                                # retrieve counts for synonym
                                $DB->Query("SELECT ItemId,Count"
                                        ." FROM SearchWordCounts"
                                        ." WHERE WordId = ".$SynonymId
                                        ." AND FieldId = ".$FieldId);
                                $SynonymCounts = $DB->FetchColumn("Count", "ItemId");

                                # for each count
                                foreach ($SynonymCounts as $ItemId => $Count)
                                {
                                    # adjust count because it's a synonym
                                    $AdjustedCount = ceil($Count / 2);

                                    # add count to existing counts
                                    if (isset($Counts[$ItemId]))
                                    {
                                        $Counts[$ItemId] += $AdjustedCount;
                                    }
                                    else
                                    {
                                        $Counts[$ItemId] = $AdjustedCount;
                                    }
                                }
                            }
                        }
                    }
                }

                # if stemming is enabled
                if ($this->StemmingEnabled)
                {
                    # retrieve stem ID
                    $Stem = PorterStemmer::Stem($Word);
                    $this->DMsg(2, "Looking up stem \"".$Stem."\"");
                    $StemId = $this->GetStemId($Stem);

                    # if ID found for stem
                    if ($StemId !== NULL)
                    {
                        # retrieve counts for stem
                        $DB->Query("SELECT ItemId,Count"
                                ." FROM SearchWordCounts"
                                ." WHERE WordId = ".$StemId
                                ." AND FieldId = ".$FieldId);
                        $StemCounts = $DB->FetchColumn("Count", "ItemId");

                        # for each count
                        foreach ($StemCounts as $ItemId => $Count)
                        {
                            # adjust count because it's a stem
                            $AdjustedCount = ceil($Count / 2);

                            # add count to existing counts
                            if (isset($Counts[$ItemId]))
                            {
                                $Counts[$ItemId] += $AdjustedCount;
                            }
                            else
                            {
                                $Counts[$ItemId] = $AdjustedCount;
                            }
                        }
                    }
                }

                # if counts were found
                if (isset($Counts))
                {
                    # for each count
                    foreach ($Counts as $ItemId => $Count)
                    {
                        # if word flagged as required
                        if ($Flags & self::WORD_REQUIRED)
                        {
                            # increment required word count for record
                            if (isset($this->RequiredTermCounts[$ItemId]))
                            {
                                $this->RequiredTermCounts[$ItemId]++;
                            }
                            else
                            {
                                $this->RequiredTermCounts[$ItemId] = 1;
                            }
                        }

                        # add to item record score
                        if (isset($Scores[$ItemId]))
                        {
                            $Scores[$ItemId] += $Count;
                        }
                        else
                        {
                            $Scores[$ItemId] = $Count;
                        }
                    }
                }
            }
        }

        # return basic scores to caller
        return $Scores;
    }

    /**
    * Extract phrases (terms surrounded by quotes) from search string.
    * @param string $SearchString Search string.
    * @param string $Logic Search logic ("AND" or "OR").
    * @return array Array with phrases for the index and word states
    *       (WORD_PRESENT, WORD_EXCLUDED, WORD_REQUIRED) for values.
    */
    private function ParseSearchStringForPhrases($SearchString, $Logic)
    {
        # split into chunks delimited by double quote marks
        $Pieces = explode("\"", $SearchString);   # "

        # for each pair of chunks
        $Index = 2;
        $Phrases = array();
        while ($Index < count($Pieces))
        {
            # grab phrase from chunk
            $Phrase = trim(addslashes($Pieces[$Index - 1]));
            $Flags = self::WORD_PRESENT;

            # grab first character of phrase
            $FirstChar = substr($Pieces[$Index - 2], -1);

            # set flags to reflect any option characters
            if ($FirstChar == "-")
            {
                $Flags |= self::WORD_EXCLUDED;
                if (!isset($Phrases[$Phrase]))
                {
                    $this->ExcludedTermCount++;
                }
            }
            else
            {
                if ((($Logic == "AND")
                                && ($FirstChar != "~"))
                        || ($FirstChar == "+"))
                {
                    $Flags |= self::WORD_REQUIRED;
                    if (!isset($Phrases[$Phrase]))
                    {
                        $this->RequiredTermCount++;
                    }
                }
                if (!isset($Phrases[$Phrase]))
                {
                    $this->InclusiveTermCount++;
                    $this->SearchTermList[] = $Phrase;
                }
            }
            $Phrases[$Phrase] = $Flags;

            # move to next pair of chunks
            $Index += 2;
        }

        # return phrases to caller
        return $Phrases;
    }

    /**
    * Search for phrase in specified field.
    * @param string $FieldId ID of field to search.
    * @param string $Phrase Phrase to search for.
    */
    protected function SearchFieldForPhrases($FieldId, $Phrase)
    {
        # error out
        exit("<br>SE - ERROR:  SearchFieldForPhrases() not implemented<br>\n");
    }

    /**
    * Search for specified phrases in specified field.
    * @param array $Phrases List of phrases to search for.
    * @param array $Scores Current search result scores.
    * @param string $FieldId ID of field to search.
    * @param bool $ProcessNonExcluded If TRUE, non-excluded search terms
    *       will be searched for.
    * @param bool $ProcessExcluded If TRUE, excluded search terms will be
    *       searched for.
    * @return array Updated search result scores.
    */
    private function SearchForPhrases($Phrases, $Scores, $FieldId,
            $ProcessNonExcluded = TRUE, $ProcessExcluded = TRUE)
    {
        # if phrases are found
        if (count($Phrases) > 0)
        {
            # if this is a keyword search
            if ($FieldId == self::KEYWORD_FIELD_ID)
            {
                # for each field
                foreach ($this->FieldInfo as $KFieldId => $Info)
                {
                    # if field is marked to be included in keyword searches
                    if ($Info["InKeywordSearch"])
                    {
                        # call ourself with that field
                        $Scores = $this->SearchForPhrases(
                                $Phrases, $Scores, $KFieldId,
                                $ProcessNonExcluded, $ProcessExcluded);
                    }
                }
            }
            else
            {
                # for each phrase
                foreach ($Phrases as $Phrase => $Flags)
                {
                    $this->DMsg(2, "Searching for phrase '".$Phrase
                            ."' in field ".$FieldId);

                    # if phrase flagged as excluded and we are doing excluded
                    #       phrases or phrase flagged as non-excluded and we
                    #       are doing non-excluded phrases
                    if (($ProcessExcluded && ($Flags & self::WORD_EXCLUDED))
                            || ($ProcessNonExcluded && !($Flags & self::WORD_EXCLUDED)))
                    {
                        # initialize score list if necessary
                        if ($Scores === NULL) {  $Scores = array();  }

                        # retrieve list of items that contain phrase
                        $ItemIds = $this->SearchFieldForPhrases(
                                $FieldId, $Phrase);

                        # for each item that contains phrase
                        foreach ($ItemIds as $ItemId)
                        {
                            # if we are doing excluded phrases and phrase
                            #       is flagged as excluded
                            if ($ProcessExcluded && ($Flags & self::WORD_EXCLUDED))
                            {
                                # knock item off of list
                                unset($Scores[$ItemId]);
                            }
                            elseif ($ProcessNonExcluded)
                            {
                                # calculate phrase value based on number of
                                #       words and field weight
                                $PhraseScore = count(preg_split("/[\s]+/",
                                                $Phrase, -1, PREG_SPLIT_NO_EMPTY))
                                        * $this->FieldInfo[$FieldId]["Weight"];
                                $this->DMsg(2, "Phrase score is ".$PhraseScore);

                                # bump up item record score
                                if (isset($Scores[$ItemId]))
                                {
                                    $Scores[$ItemId] += $PhraseScore;
                                }
                                else
                                {
                                    $Scores[$ItemId] = $PhraseScore;
                                }

                                # if phrase flagged as required
                                if ($Flags & self::WORD_REQUIRED)
                                {
                                    # increment required word count for record
                                    if (isset($this->RequiredTermCounts[$ItemId]))
                                    {
                                        $this->RequiredTermCounts[$ItemId]++;
                                    }
                                    else
                                    {
                                        $this->RequiredTermCounts[$ItemId] = 1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        # return updated scores to caller
        return $Scores;
    }

    /**
    * Filter scores to remove results that contain excluded terms in specified
    * field.
    * @param array $Words Terms as the index with word flags for the values.
    * @param array $Scores Current search result scores.
    * @param string $FieldId ID of field.
    * @return array Filtered search result scores.
    */
    private function FilterOnExcludedWords($Words, $Scores, $FieldId)
    {
        $DB = $this->DB;

        # for each word
        foreach ($Words as $Word => $Flags)
        {
            # if word flagged as excluded
            if ($Flags & self::WORD_EXCLUDED)
            {
                # look up record ID for word
                $WordId = $this->GetWordId($Word);

                # if word is in DB
                if ($WordId !== NULL)
                {
                    # look up counts for word
                    $DB->Query("SELECT ItemId FROM SearchWordCounts "
                            ."WHERE WordId=${WordId} AND FieldId=${FieldId}");

                    # for each count
                    while ($Record = $DB->FetchRow())
                    {
                        # if item record is in score list
                        $ItemId = $Record["ItemId"];
                        if (isset($Scores[$ItemId]))
                        {
                            # remove item record from score list
                            $this->DMsg(3, "Filtering out item ".$ItemId
                                    ." because it contained word \"".$Word."\"");
                            unset($Scores[$ItemId]);
                        }
                    }
                }
            }
        }

        # returned filtered score list to caller
        return $Scores;
    }

    /**
    * Filter scores to remove results that do not meet required term counts.
    * @param array $Scores Current search result scores.
    * @return array Filtered search result scores.
    */
    private function FilterOnRequiredWords($Scores)
    {
        # if there were required words
        if ($this->RequiredTermCount > 0)
        {
            # for each item
            foreach ($Scores as $ItemId => $Score)
            {
                # if item does not meet required word count
                if (!isset($this->RequiredTermCounts[$ItemId])
                        || ($this->RequiredTermCounts[$ItemId]
                                < $this->RequiredTermCount))
                {
                    # filter out item
                    $this->DMsg(4, "Filtering out item ".$ItemId
                            ." because it didn't have required word count of "
                            .$this->RequiredTermCount
                            .(isset($this->RequiredTermCounts[$ItemId])
                                    ? " (only had "
                                    .$this->RequiredTermCounts[$ItemId]
                                    : " (had none")
                            .")");
                    unset($Scores[$ItemId]);
                }
            }
        }

        # return filtered list to caller
        return $Scores;
    }

    /**
    * Count, sort, and trim search result scores list.
    * @param array $Scores Current set of search scores.
    * @param int $StartingResult Starting offset into scores.
    * @param int $NumberOfResults Number of scores to pare down to.
    * @param mixed $SortByField ID of field or array of IDs of fields
    *       (indexed by item type) to sort results by.
    * @param mixed $SortDescending If TRUE, sort in descending order, otherwise
    *       sort in ascending order.  May also be array of boolean values, with
    *       item types for the index.
    * @return array New set of search scores.
    */
    private function CleanScores($Scores, $StartingResult, $NumberOfResults,
            $SortByField, $SortDescending)
    {
        # perform any requested filtering
        $this->DMsg(0, "Have ".count($Scores)." results before filter callbacks");
        $Scores = $this->FilterOnSuppliedFunctions($Scores);

        # save total number of results available
        $this->NumberOfResultsAvailable = count($Scores);

        # sort search scores into item type bins
        $NewScores = array();
        foreach ($Scores as $Id => $Score)
        {
            $ItemType = $this->GetItemType($Id);
            if ($ItemType !== NULL)
            {
                $NewScores[$ItemType][$Id] = $Score;
            }
        }
        $Scores = $NewScores;

        # for each item type
        $NewSortByField = array();
        $NewSortDescending = array();
        foreach ($Scores as $ItemType => $TypeScores)
        {
            # normalize sort field parameter
            $NewSortByField[$ItemType] = !is_array($SortByField) ? $SortByField
                    : (isset($SortByField[$ItemType])
                            ? $SortByField[$ItemType] : NULL);

            # normalize sort direction parameter
            $NewSortDescending[$ItemType] = !is_array($SortDescending) ? $SortDescending
                    : (isset($SortDescending[$ItemType])
                            ? $SortDescending[$ItemType] : TRUE);
        }
        $SortByField = $NewSortByField;
        $SortDescending = $NewSortDescending;

        # for each item type
        foreach ($Scores as $ItemType => $TypeScores)
        {
            # save number of results
            $this->NumberOfResultsPerItemType[$ItemType] = count($TypeScores);

            # if no sorting field specified
            if ($SortByField[$ItemType] === NULL)
            {
                # sort result list by score
                if ($SortDescending[$ItemType])
                {
                    arsort($Scores[$ItemType], SORT_NUMERIC);
                }
                else
                {
                    asort($Scores[$ItemType], SORT_NUMERIC);
                }
            }
            else
            {
                # get list of item IDs in sorted order
                $SortedIds = $this->GetItemIdsSortedByField($ItemType,
                        $SortByField[$ItemType], $SortDescending[$ItemType]);

                # if we have sorted item IDs
                if (count($SortedIds) && count($TypeScores))
                {
                    # strip sorted ID list down to those that appear in search results
                    $SortedIds = array_intersect($SortedIds,
                            array_keys($TypeScores));

                    # rebuild score list in sorted order
                    $NewScores = array();
                    foreach ($SortedIds as $Id)
                    {
                        $NewScores[$Id] = $TypeScores[$Id];
                    }
                    $Scores[$ItemType] = $NewScores;
                }
                else
                {
                    # sort result list by score
                    arsort($Scores[$ItemType], SORT_NUMERIC);
                }
            }

            # if subset of scores requested
            if (($StartingResult > 0) || ($NumberOfResults < PHP_INT_MAX))
            {
                # trim scores back to requested subset
                $ScoresKeys = array_slice(array_keys($Scores[$ItemType]),
                        $StartingResult, $NumberOfResults);
                $NewScores = array();
                foreach ($ScoresKeys as $Key)
                {
                    $NewScores[$Key] = $Scores[$ItemType][$Key];
                }
                $Scores[$ItemType] = $NewScores;
            }
        }

        # returned cleaned search result scores list to caller
        return $Scores;
    }

    /**
    * Filter search scores through any supplied functions.
    * @param array $Scores Current set of search scores.
    * @return array An possibly pared-down set of search scores.
    */
    protected function FilterOnSuppliedFunctions($Scores)
    {
        # if filter functions have been set
        if (isset($this->FilterFuncs))
        {
            # for each result
            foreach ($Scores as $ItemId => $Score)
            {
                # for each filter function
                foreach ($this->FilterFuncs as $FuncName)
                {
                    # if filter function return TRUE for item
                    if (call_user_func($FuncName, $ItemId))
                    {
                        # discard result
                        $this->DMsg(2, "Filter callback <i>".$FuncName
                                ."</i> rejected item ".$ItemId);
                        unset($Scores[$ItemId]);

                        # bail out of filter func loop
                        continue 2;
                    }
                }
            }
        }

        # return filtered list to caller
        return $Scores;
    }

    /**
    * Scan through incoming search strings for comparison searches (e.g. "X<Y")
    * perform the appropriate searches, and update the search scores accordingly.
    * @param array $SearchStrings Array of search string arrays, with field names
    *       for the index.
    * @param string $Logic Search logic ("AND" or "OR").
    * @param array $Scores Current search scores, with item IDs for the index.
    * @return array An updated set of search scores.
    */
    private function SearchForComparisonMatches($SearchStrings, $Logic, $Scores)
    {
        # for each field
        $Index = 0;
        foreach ($SearchStrings as $SearchFieldId => $SearchStringArray)
        {
            # if field is not keyword
            if ($SearchFieldId != self::KEYWORD_FIELD_ID)
            {
                # for each search string for this field
                foreach ($SearchStringArray as $SearchString)
                {
                    # if search string looks like comparison search
                    $FoundOperator = preg_match("/^[><!]=./", $SearchString)
                            || preg_match('/^[><=^$]./', $SearchString);
                    if ($FoundOperator
                            || (isset($this->FieldInfo[$SearchFieldId]["FieldType"])
                            && ($this->FieldInfo[$SearchFieldId]["FieldType"]
                                    != self::FIELDTYPE_TEXT)))
                    {
                        # determine value
                        $Patterns = array("/^[><!]=/", '/^[><=^$]/');
                        $Replacements = array("", "");
                        $Value = trim(preg_replace(
                                $Patterns, $Replacements, $SearchString));

                        # determine and save operator
                        if (!$FoundOperator)
                        {
                            $Operators[$Index] = "=";
                        }
                        else
                        {
                            $Term = trim($SearchString);
                            $FirstChar = $Term{0};
                            $FirstTwoChars = $FirstChar.$Term{1};
                            if (($FirstTwoChars == ">=")
                                    || ($FirstTwoChars == "<=")
                                    || ($FirstTwoChars == "!="))
                            {
                                $Operators[$Index] = $FirstTwoChars;
                            }
                            else
                            {
                                $Operators[$Index] = $FirstChar;
                            }
                        }

                        # if operator was found
                        if (isset($Operators[$Index]))
                        {
                            # save value
                            $Values[$Index] = $Value;

                            # save field name
                            $FieldIds[$Index] = $SearchFieldId;
                            $this->DMsg(3, "Added comparison (field = <i>"
                                    .$FieldIds[$Index]."</i>  op = <i>"
                                    .$Operators[$Index]."</i>  val = <i>"
                                    .$Values[$Index]."</i>)");

                            # move to next comparison array entry
                            $Index++;
                        }
                    }
                }
            }
        }

        # if comparisons found
        if (isset($Operators))
        {
            # perform comparisons on fields and gather results
            $Results = $this->SearchFieldsForComparisonMatches(
                    $FieldIds, $Operators, $Values, $Logic);

            # if search logic is set to AND
            if ($Logic == "AND")
            {
                # if results were found
                if (count($Results))
                {
                    # if there were no prior results and no terms for keyword search
                    if ((count($Scores) == 0) && ($this->InclusiveTermCount == 0))
                    {
                        # add all results to scores
                        foreach ($Results as $ItemId)
                        {
                            $Scores[$ItemId] = 1;
                        }
                    }
                    else
                    {
                        # remove anything from scores that is not part of results
                        foreach ($Scores as $ItemId => $Score)
                        {
                            if (in_array($ItemId, $Results) == FALSE)
                            {
                                unset($Scores[$ItemId]);
                            }
                        }
                    }
                }
                else
                {
                    # clear scores
                    $Scores = array();
                }
            }
            else
            {
                # add result items to scores
                if ($Scores === NULL) {  $Scores = array();  }
                foreach ($Results as $ItemId)
                {
                    if (isset($Scores[$ItemId]))
                    {
                        $Scores[$ItemId] += 1;
                    }
                    else
                    {
                        $Scores[$ItemId] = 1;
                    }
                }
            }
        }

        # return results to caller
        return $Scores;
    }

    /**
    * Scan incoming search strings for debug level magic keyword, set debug
    * level if found, and remove keyword from strings.
    * @param array $SearchStrings Incoming search strings.
    * @return array Arry of search strings with any debug level magic keywords
    *       removed.
    */
    private function SetDebugLevel($SearchStrings)
    {
        # if search info is an array
        if (is_array($SearchStrings))
        {
            # for each array element
            foreach ($SearchStrings as $FieldId => $SearchStringArray)
            {
                # if element is an array
                if (is_array($SearchStringArray))
                {
                    # for each array element
                    foreach ($SearchStringArray as $Index => $SearchString)
                    {
                        # pull out search string if present
                        $SearchStrings[$FieldId][$Index] =
                                $this->ExtractDebugLevel($SearchString);
                    }
                }
                else
                {
                    # pull out search string if present
                    $SearchStrings[$FieldId] =
                            $this->ExtractDebugLevel($SearchStringArray);
                }
            }
        }
        else
        {
            # pull out search string if present
            $SearchStrings = $this->ExtractDebugLevel($SearchStrings);
        }

        # return new search info to caller
        return $SearchStrings;
    }

    /**
    * Scan incoming search string for debug level magic keyword, set debug
    * level if found, and remove keyword from string.
    * @param string $SearchString Incoming search string.
    * @return string Search string with any debug level magic keyword removed.
    */
    private function ExtractDebugLevel($SearchString)
    {
        # if search string contains debug level indicator
        if (strstr($SearchString, "DBUGLVL="))
        {
            # remove indicator and set debug level
            $Level = preg_replace("/^\\s*DBUGLVL=([1-9]{1,2}).*/", "\\1", $SearchString);
            if ($Level > 0)
            {
                $this->DebugLevel = $Level;
                $this->DMsg(0, "Setting debug level to ".$Level);
                $SearchString = preg_replace("/\s*DBUGLVL=${Level}\s*/", "",
                        $SearchString);
            }
        }

        # return (possibly) modified search string to caller
        return $SearchString;
    }

    /**
    * Load and return search result scores array containing all possible records.
    * @return array Scores with item IDs for the index.
    */
    private function LoadScoresForAllRecords()
    {
        # start with empty list
        $Scores = array();

        # for every item
        $this->DB->Query("SELECT ".$this->ItemIdFieldName
                         ." FROM ".$this->ItemTableName);
        while ($Record = $this->DB->FetchRow())
        {
            # set score for item to 1
            $Scores[$Record[$this->ItemIdFieldName]] = 1;
        }

        # return array with all scores to caller
        return $Scores;
    }


    # ---- private methods (search DB building)

    /**
    * Update weighted count for term/item/field combination in DB.
    * @param string $Word Word for which count should be updated.
    * @param int $ItemId ID of item for which count applies.
    * @param int $FieldId ID of field for which count applies.
    * @param int $Weight Numeric weight to apply to count.  (OPTIONAL - defaults to 1)
    */
    private function UpdateWordCount($Word, $ItemId, $FieldId, $Weight = 1)
    {
        # retrieve ID for word
        $WordIds[] = $this->GetWordId($Word, TRUE);

        # if stemming is enabled and word looks appropriate for stemming
        if ($this->StemmingEnabled && !is_numeric($Word))
        {
            # retrieve stem of word
            $Stem = PorterStemmer::Stem($Word, TRUE);

            # if stem is different
            if ($Stem != $Word)
            {
                # retrieve ID for stem of word
                $WordIds[] = $this->GetStemId($Stem, TRUE);
            }
        }

        # for word and stem of word
        foreach ($WordIds as $WordId)
        {
            # if word count already added to database
            if (isset($this->WordCountAdded[$WordId][$FieldId]))
            {
                # update word count
                $this->DB->Query("UPDATE SearchWordCounts SET Count=Count+".$Weight
                        ." WHERE WordId=".$WordId
                                ." AND ItemId=".$ItemId
                                ." AND FieldId=".$FieldId);
            }
            else
            {
                # add word count to DB
                $this->DB->Query("INSERT INTO SearchWordCounts"
                        ." (WordId, ItemId, FieldId, Count) VALUES"
                        ." (".$WordId.", ".$ItemId.", ".$FieldId.", ".$Weight.")");

                # remember that we added count for this word
                $this->WordCountAdded[$WordId][$FieldId] = TRUE;
            }

            # decrease weight for stem
            $Weight = ceil($Weight / 2);
        }
    }

    /**
    * Retrieve content for specified field for specified item.
    * @param int $ItemId ID of item.
    * @param int $FieldId ID of field.
    */
    protected function GetFieldContent($ItemId, $FieldId)
    {
        # error out
        throw Exception("GetFieldContent() not implemented.");
    }

    /**
    * Update word counts for indicated field for indicated item.
    * @param int $ItemId ID of item.
    * @param int $FieldId ID of field.
    * @param int $Weight Weight of field.
    * @param string $Text Text to parse.
    * @param bool $IncludeInKeyword Whether this field should be included
    *       in keyword searching.
    */
    private function RecordSearchInfoForText(
            $ItemId, $FieldId, $Weight, $Text, $IncludeInKeyword)
    {
        # normalize text
        $Words = $this->ParseSearchStringForWords($Text, TRUE);

        # if there was text left after parsing
        if (count($Words) > 0)
        {
            # for each word
            foreach ($Words as $Word => $Flags)
            {
                # update count for word
                $this->UpdateWordCount($Word, $ItemId, $FieldId);

                # if text should be included in keyword searches
                if ($IncludeInKeyword)
                {
                    # update keyword field count for word
                    $this->UpdateWordCount(
                            $Word, $ItemId, self::KEYWORD_FIELD_ID, $Weight);
                }
            }
        }
    }

    # ---- common private methods (used in both searching and DB build)

    /**
    * Normalize and parse search string into list of search terms.
    * @param string $SearchString Search string.
    * @param string $Logic Search logic ("AND" or "OR").
    * @param bool $IgnorePhrases Whether to ignore phrases and groups and
    *       treat the words within them as regular search terms.  (OPTIONAL,
    *       defaults to FALSE)
    * @return array Array with search terms for the index and word states
    *       (WORD_PRESENT, WORD_EXCLUDED, WORD_REQUIRED) for values.
    */
    private function ParseSearchStringForWords(
            $SearchString, $Logic, $IgnorePhrases = FALSE)
    {
        # strip off any surrounding whitespace
        $Text = trim($SearchString);

        # set up normalization replacement strings
        $Patterns = array(
                "/'s[^a-z0-9\\-+~]+/i", # get rid of possessive plurals
                "/'/",                  # get rid of single quotes / apostrophes
                "/\"[^\"]*\"/",         # get rid of phrases  (NOTE: HARD-CODED
                                        #       INDEX BELOW!!!)  "
                "/\\([^)]*\\)/",        # get rid of groups  (NOTE: HARD-CODED
                                        #       INDEX BELOW!!!)
                "/[^a-z0-9\\-+~]+/i",   # convert non-alphanumerics
                                        #       / non-minus/plus to a space
                "/([^\\s])-+/i",        # convert minus preceded by anything
                                        #       but whitespace to a space
                "/([^\\s])\\++/i",      # convert plus preceded by anything
                                        #       but whitespace to a space
                "/-\\s/i",              # convert minus followed by whitespace to a space
                "/\\+\\s/i",            # convert plus followed by whitespace to a space
                "/~\\s/i",              # convert tilde followed by whitespace to a space
                "/[ ]+/"                # convert multiple spaces to one space
                );
        $Replacements = array(
                " ",
                "",
                " ",
                " ",
                "\\1 ",
                "\\1 ",
                " ",
                " ",
                " ",
                " ",
                " "
                );

        # if we are supposed to ignore phrases and groups (series of words
        #       in quotes or surrounded by parens)
        if ($IgnorePhrases)
        {
            # switch phrase removal to double quote removal  (HARD-CODED
            #       INDEX INTO PATTERN LIST!!)
            $Patterns[2] = "/\"/";

            # switch group removal to paren removal  (HARD-CODED INDEX
            #       INTO PATTERN LIST!!)
            $Patterns[3] = "/[\(\)]+/";
        }

        # remove punctuation from text and normalize whitespace
        $Text = preg_replace($Patterns, $Replacements, $Text);
        $this->DMsg(2, "Normalized search string is '".$Text."'");

        # convert text to lower case
        $Text = strtolower($Text);

        # strip off any extraneous whitespace
        $Text = trim($Text);

        # start with an empty array
        $Words = array();

        # if we have no words left after parsing
        if (strlen($Text) != 0)
        {
            # for each word
            foreach (explode(" ", $Text) as $Word)
            {
                # grab first character of word
                $FirstChar = substr($Word, 0, 1);

                # strip off option characters and set flags appropriately
                $Flags = self::WORD_PRESENT;
                if ($FirstChar == "-")
                {
                    $Word = substr($Word, 1);
                    $Flags |= self::WORD_EXCLUDED;
                    if (!isset($Words[$Word]))
                    {
                        $this->ExcludedTermCount++;
                    }
                }
                else
                {
                    if ($FirstChar == "~")
                    {
                        $Word = substr($Word, 1);
                    }
                    elseif (($Logic == "AND")
                            || ($FirstChar == "+"))
                    {
                        if ($FirstChar == "+")
                        {
                            $Word = substr($Word, 1);
                        }
                        $Flags |= self::WORD_REQUIRED;
                        if (!isset($Words[$Word]))
                        {
                            $this->RequiredTermCount++;
                        }
                    }
                    if (!isset($Words[$Word]))
                    {
                        $this->InclusiveTermCount++;
                        $this->SearchTermList[] = $Word;
                    }
                }

                # store flags to indicate word found
                $Words[$Word] = $Flags;
                $this->DMsg(3, "Word identified (".$Word.")");
            }
        }

        # return normalized words to caller
        return $Words;
    }

    /**
    * Get ID for specified word.
    * @param string $Word Word to look up ID for.
    * @param bool $AddIfNotFound If TRUE, word will be added to database
    *       if not found.  (OPTIONAL, defaults to FALSE)
    * @return int ID for word or NULL if word was not found.
    */
    private function GetWordId($Word, $AddIfNotFound = FALSE)
    {
        static $WordIdCache;

        # if word was in ID cache
        if (isset($WordIdCache[$Word]))
        {
            # use ID from cache
            $WordId = $WordIdCache[$Word];
        }
        else
        {
            # look up ID in database
            $WordId = $this->DB->Query("SELECT WordId"
                    ." FROM SearchWords"
                    ." WHERE WordText='".addslashes($Word)."'",
                    "WordId");

            # if ID was not found and caller requested it be added
            if (($WordId === NULL) && $AddIfNotFound)
            {
                # add word to database
                $this->DB->Query("INSERT INTO SearchWords (WordText)"
                        ." VALUES ('".addslashes(strtolower($Word))."')");

                # get ID for newly added word
                $WordId = $this->DB->LastInsertId();
            }

            # save ID to cache
            $WordIdCache[$Word] = $WordId;
        }

        # return ID to caller
        return $WordId;
    }

    /**
    * Get ID for specified word stem.
    * @param string $Stem Word stem to look up ID for.
    * @param bool $AddIfNotFound If TRUE, word stem will be added to database
    *       if not found.  (OPTIONAL, defaults to FALSE)
    * @return int ID for word stem or NULL if word stem was not found.
    */
    private function GetStemId($Stem, $AddIfNotFound = FALSE)
    {
        static $StemIdCache;

        # if stem was in ID cache
        if (isset($StemIdCache[$Stem]))
        {
            # use ID from cache
            $StemId = $StemIdCache[$Stem];
        }
        else
        {
            # look up ID in database
            $StemId = $this->DB->Query("SELECT WordId"
                    ." FROM SearchStems"
                    ." WHERE WordText='".addslashes($Stem)."'",
                    "WordId");

            # if ID was not found and caller requested it be added
            if (($StemId === NULL) && $AddIfNotFound)
            {
                # add stem to database
                $this->DB->Query("INSERT INTO SearchStems (WordText)"
                        ." VALUES ('".addslashes(strtolower($Stem))."')");

                # get ID for newly added stem
                $StemId = $this->DB->LastInsertId();
            }

            # adjust from DB ID value to stem ID value
            $StemId += self::STEM_ID_OFFSET;

            # save ID to cache
            $StemIdCache[$Stem] = $StemId;
        }

        # return ID to caller
        return $StemId;
    }

    /**
    * Get word for specified word ID.
    * @param int $WordId ID to look up.
    * @return string Word for specified ID, or FALSE if ID was not found.
    */
    private function GetWord($WordId)
    {
        static $WordCache;

        # if word was in cache
        if (isset($WordCache[$WordId]))
        {
            # use word from cache
            $Word = $WordCache[$WordId];
        }
        else
        {
            # adjust search location and word ID if word is stem
            $TableName = "SearchWords";
            if ($WordId >= self::STEM_ID_OFFSET)
            {
                $TableName = "SearchStems";
                $WordId -= self::STEM_ID_OFFSET;
            }

            # look up word in database
            $Word = $this->DB->Query("SELECT WordText"
                    ." FROM ".$TableName
                    ." WHERE WordId='".$WordId."'",
                    "WordText");

            # save word to cache
            $WordCache[$WordId] = $Word;
        }

        # return word to caller
        return $Word;
    }

    /**
    * Get type of specified item.
    * @param int $ItemId ID for item.
    * @return int Item type, or NULL if item type is unknown.
    */
    private function GetItemType($ItemId)
    {
        static $ItemTypeCache;
        if (!isset($ItemTypeCache))
        {
            $this->DB->Query("SELECT * FROM SearchItemTypes");
            $ItemTypeCache = $this->DB->FetchColumn("ItemType", "ItemId");
        }
        return isset($ItemTypeCache[$ItemId])
                ? (int)$ItemTypeCache[$ItemId] : NULL;
    }

    /**
    * Print debug message if level set high enough.
    * @param int $Level Level of message.
    * @param string $Msg Message to print.
    */
    protected function DMsg($Level, $Msg)
    {
        if ($this->DebugLevel > $Level)
        {
            print "SE:  ".$Msg."<br>\n";
        }
    }

    # ---- BACKWARD COMPATIBILITY --------------------------------------------

    # possible types of logical operators
    const SEARCHLOGIC_AND = 1;
    const SEARCHLOGIC_OR = 2;
}
