<?PHP
#
#   FILE:  SearchFacetUI_Base.php
#
#   Part of the Collection Workflow Integration System (CWIS)
#   Copyright 2015-2025 Edward Almasy and Internet Scout Research Group
#   http://scout.wisc.edu/cwis/
#
# @scout:phpstan

namespace Metavus;
use Exception;
use ScoutLib\ApplicationFramework;
use ScoutLib\DataCache;
use ScoutLib\Database;

/**
 * SearchFacetUI supports the generation of a user interface for faceted
 * search, by taking the search parameters and search results and generating
 * the data needed to lay out the HTML.This is the UI-independent facet
 * generating portion; HTML should be generated by a SearchFacetUI that
 * extends this class.
 */
class SearchFacetUI_Base
{
    # ---- PUBLIC INTERFACE --------------------------------------------------

    /**
     * Constructor, that accepts the search parameters and results and
     *   prepares the facet UI data to be retrieved.
     * @param SearchParameterSet $SearchParams Current search parameter set.
     * @param array $SearchResults Search results as an array where keys give
     *   ItemIds and values give search scores (so the same format SearchEngine
     *   uses to return per-schema results)
     */
    public function __construct(
        SearchParameterSet $SearchParams,
        array $SearchResults
    ) {
        $this->SearchParams = $SearchParams;
        $this->SearchResults = $SearchResults;
        $this->MaxFacetsPerField =
                SystemConfiguration::getInstance()->getInt("MaxFacetsPerField");
        $this->User = User::getCurrentUser();

        $this->ShowCounts = count($SearchResults) <= SearchEngine::numResourcesForFacets();

        $SchemaIds = array_unique(
            Record::getSchemasForRecords(array_keys($SearchResults))
        );

        if (count($SchemaIds) > 1) {
            throw new Exception(
                "SearchFacetUI cannot generate facets for "
                ."multiple schemas at a time."
            );
        }

        $this->SchemaId = reset($SchemaIds);
        $this->DataCache = new DataCache(self::CACHE_KEY_PREFIX);
    }

    /**
     * Get/set the user used for permission checks when generating search
     *   facets.If no user is explicitly set, it defaults to User::getCurrentUser().
     * @param User $NewValue User value to set (OPTIONAL)
     * @return User Current value.
     */
    public function user(?User $NewValue = null): User
    {
        if (!is_null($NewValue)) {
            $this->User = $NewValue;
        }

        return $this->User;
    }

    /**
     * Set the base link used when generating search URLs that add a
     * search facet.  If not set, it defaults to "index.php?P=SearchResults".
     * @param string $NewValue New value to set.
     */
    public function setBaseLink(string $NewValue): void
    {
        $this->BaseLink = $NewValue;
    }

    /**
     * Get the current base link value (used when generating search URLs that
     * add a search facet).
     * @return string Current value.
     */
    public function getBaseLink(): string
    {
        return $this->BaseLink;
    }

    /**
     * Set facets to be open by default.
     */
    public function setAllFacetsOpenByDefault(): void
    {
        $this->OpenFieldsByDefault = true;
    }

    /**
     * Restrict the list of fields displayed as facets to a subset of those
     * set for inclusion in faceted search. In order to appear a field must
     * both be configured for faceted search and be in the list of FieldIds
     * given.
     * @param array $FieldIds Fields to allow.
     * @return void
     */
    public function setFacetFieldIds(array $FieldIds): void
    {
        $this->FacetFieldIds = $FieldIds;
    }

    /**
     * Clear search facet caches.
     * @return void
     */
    public static function clearCaches(): void
    {
        $DataCache = new DataCache(self::CACHE_KEY_PREFIX);
        $DataCache->clear();
    }

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

    protected $OpenFieldsByDefault = false;
    protected $User;
    protected $SchemaId;
    protected $FacetFieldIds = null;

    private $DataCache;
    private static $CacheTTL = 120 * 60; # seconds
    private static $SlowGenerationThreshold = 0.2; # seconds

    ##
    # Facet generation functions

    /**
     * Load search facets from cache or generate them if necessary.
     * @return void
     * @see generateFacets()
     */
    protected function loadFacets(): void
    {
        $DB = new Database();
        $Schema = new MetadataSchema($this->SchemaId);

        $CacheKey = __FUNCTION__."-".hash(
            'sha256',
            implode(
                "/",
                [
                    $Schema->computeUserClass($this->User),
                    serialize($this->SearchResults),
                    $this->SearchParams->data(),
                ]
            )
        );

        $CacheData = $this->DataCache->get($CacheKey);
        if (!is_null($CacheData)) {
            $CacheData = unserialize($CacheData);
            $this->TreeSuggestionsByFieldName = $CacheData["TreeSuggestionsByFieldName"];
            $this->SuggestionsByFieldName = $CacheData["SuggestionsByFieldName"];
            return;
        }

        $StartTime = microtime(true);
        $this->generateFacets();
        $StopTime = microtime(true);

        # if facets took a long time to compute, cache them
        if ($StopTime - $StartTime > self::$SlowGenerationThreshold) {
            $Data = serialize([
                "TreeSuggestionsByFieldName" => $this->TreeSuggestionsByFieldName,
                "SuggestionsByFieldName" => $this->SuggestionsByFieldName,
            ]);

            $this->DataCache->set($CacheKey, $Data, self::$CacheTTL);
        }
    }

    /**
     * Generate (i.e. bring into existence) a list of search facets
     *   (i.e. suggested terms that can be added to a search) that can be
     *   later displayed. Internally, these facets are stored as modified
     *   search URLs in the SuggestionsByFieldName and
     *   TreeSuggestionsByFieldName data members. The former stores
     *   suggestions for Controlled Name and Option fields, the latter
     *   suggestions for Classification fields.
     * @return void
     */
    protected function generateFacets(): void
    {
        $Schema = new MetadataSchema($this->SchemaId);
        $Fields = $Schema->getFields(
            MetadataSchema::MDFTYPE_OPTION |
            MetadataSchema::MDFTYPE_CONTROLLEDNAME |
            MetadataSchema::MDFTYPE_TREE
        );

        $ResultFacets = SearchEngine::getResultFacets(
            $this->SearchResults,
            $this->User
        );

        foreach ($Fields as $Field) {
            if (!$Field->includeInFacetedSearch()) {
                continue;
            }

            if (!$Field->userCanView($this->User)) {
                continue;
            }

            if (!is_null($this->FacetFieldIds) &&
                !in_array($Field->id(), $this->FacetFieldIds)) {
                continue;
            }

            $FieldName = $Field->name();

            $Suggestions = isset($ResultFacets[$FieldName]) ?
                $ResultFacets[$FieldName] : [];

            if (count($Suggestions)) {
                # filter suggestions
                foreach ($Suggestions as $ValueId => $ValueData) {
                    # only display fields with non-empty value
                    $NewVal = $this->filterFieldValue($Field, $ValueData["Name"]);
                    if (empty($NewVal)) {
                        unset($Suggestions[$ValueId]);
                    } else {
                        $Suggestions[$ValueId]["Name"] = $NewVal;
                    }
                }
            }

            # foreach field, generate a list of suggested facets
            # and determine if the field should be open by default
            if ($Field->type() == MetadataSchema::MDFTYPE_TREE) {
                $this->populateFacetsForTreeField($Field, $Suggestions);
            } else {
                $this->populateFacetsForNameField($Field, $Suggestions);
            }
        }
    }

    /**
     * Populate TreeSuggestionsByFieldName for a specified Tree Field based on
     * a list of suggested Classification IDs.
     * @param MetadataField $Field Metadata field to process
     * @param array $Suggestions Search suggestions from SearchEngine::getResultFacets()
     * @return void
     */
    private function populateFacetsForTreeField(
        MetadataField $Field,
        array $Suggestions
    ): void {
        # build up a nested array of suggestions where each level of the array
        # is keyed by the termid
        $Facets = $this->convertSuggestionsToNestedArray($Suggestions);

        $CurrentValues = $this->SearchParams->getSearchStringsForField($Field);

        # Determine the search logic to use when adding a facet to this field.
        # If we have any terms for this field from the current search, then adding
        # another (in the form of an additional term for this facet)
        # will employ the field's search group logic. Otherwise, it will be
        # the top-level logic of our params
        $Logic = count($CurrentValues) > 0
            ? $Field->searchGroupLogic()
            : ($this->SearchParams->logic() == "OR"
               ? SearchEngine::LOGIC_OR
               : SearchEngine::LOGIC_AND);

        # if this field should show top-level classifications, add those
        if ($Logic == SearchEngine::LOGIC_OR
            && !$Field->facetsShowOnlyTermsUsedInResults()) {
            $Facets = $this->addTopLevelClassifications($Facets, $Field);
        }

        # get current selections
        $CurrentValues = $this->normalizeTreeValues(
            $this->SearchParams->getSearchStringsForField($Field),
            $Field
        );

        # and add them to our nested array of suggestions
        $Facets = $this->addSelectionsToNestedArray(
            $Facets,
            $Field,
            $CurrentValues
        );

        # prune each branch of the tree down to the highest level that should
        # be shown (root terms and children of selected terms)
        $Facets = $this->pruneChildrenOfUnselectedFacets($Facets);

        # if necessary, add child classifications
        if ($Logic == SearchEngine::LOGIC_OR
            && !$Field->facetsShowOnlyTermsUsedInResults()) {
            $Facets = $this->addChildrenOfSelectedTerms($Facets, $Field);
        }

        # determine how many facets we're about to suggest
        $FacetCount = $this->countFacets($Facets);

        # if there are too many suggestions, reduce to just the selected terms
        if ($FacetCount > $this->MaxFacetsPerField) {
            $Facets = $this->pruneUnselectedFacets($Facets);
        }

        # if no facets remain, nothing to do
        if (count($Facets) == 0) {
            return;
        }

        # append Add/Remove links, normalize names, and sort facets
        $this->prepareFacetsForDisplay($Facets, $Field);

        $this->TreeSuggestionsByFieldName[$Field->name()] = $Facets;
        if (count($CurrentValues) > 0) {
            $this->FieldsOpenByDefault[$Field->name()] = true;
        }
    }

    /**
     * Populate SuggestionsByFieldName for a specified Controlled Name or
     * Option field based on a list of suggested Controlled Name IDs.
     * @param MetadataField $Field Metadata field to process
     * @param array $Suggestions Search suggestions from
     *   SearchEngine::getResultFacets()
     * @return void
     */
    private function populateFacetsForNameField(
        MetadataField $Field,
        array $Suggestions
    ): void {
        # retrieve current search parameter values for field
        $CurrentValues = $this->SearchParams->getSearchStringsForField($Field);

        # if a field is required, and we have only one suggestion and
        # there is no current value, then we don't want to display this
        # facet because the search results will be identical
        if (($Field->optional() == false) && (count($Suggestions) == 1) &&
            !count($CurrentValues)) {
            return;
        }

        $Facets = [];

        # populate facets with terms derived from the search results
        foreach ($Suggestions as $TermId => $TermData) {
            $Facets[$TermId]["TermInfo"] = $TermData;
        }

        # add other terms if needed
        if (!$Field->facetsShowOnlyTermsUsedInResults()) {
            $Facets = $this->addFacetsFromCName($Facets, $Field);
        }

        # mark facets for terms included in the current search as selected
        $Facets = $this->markSearchTermsSelectedForCNameFacet(
            $Facets,
            $Field,
            $CurrentValues
        );

        # for CNames, prune terms that will not help the user refine their search
        # (retaining them for Option fields so that the facets can indicate to
        # the user when there are no resources for a given option value)
        if ($Field->type() == MetadataSchema::MDFTYPE_CONTROLLEDNAME) {
            # remove facets for terms that are not associated with any resources
            # the user can see; these are useless as search suggestions because
            # adding them to an OR search will do nothing at all and adding them
            # to an AND search will produce no results
            $Facets = $this->pruneUselessCNamesFromFacet(
                $Facets,
                $Field
            );
        }

        # determine how many facets we're about to suggest
        $FacetCount = $this->countFacets($Facets);

        # if there are too many suggestions, reduce to just the selected terms
        if ($FacetCount > $this->MaxFacetsPerField) {
            $Facets = $this->pruneUnselectedFacets($Facets);
        }

        # if no facets remain, nothing to do
        if (count($Facets) == 0) {
            return;
        }

        # append Add/Remove links and sort
        $this->prepareFacetsForDisplay($Facets, $Field);

        $this->SuggestionsByFieldName[$Field->name()] = $Facets;
        if (count($CurrentValues) > 0) {
            $this->FieldsOpenByDefault[$Field->name()] = true;
        }
    }

    ##
    # Functions to manipulate search suggestions in nested array format.
    #
    # The format used is:
    # [
    #    TermId => [
    #        "TermInfo" => [...],
    #        ChildId => [...],
    #        ChildId => [...],
    #...
    #    ],
    #    TermId => [...],
    #...
    # ]
    #
    # Each array keyed by a ChildId recursively uses the same structure.The
    # "TermInfo" item is supplied by searchEngine::getResultFacets() and
    # starts off with keys "Id", "Name", and "Count" where the Count gives
    # the number of items in the SearchResults that have the given term
    # (i.e.the number we'd get by ANDing that term in to the current
    # search). Before display, we'll also be adding keys IsSelected (bool)
    # and one of AddLink or RemoveLink.

    /**
     * Convert a flat list of search suggestions to nested array format.
     * @param array $Suggestions Suggested search terms.
     * @return array nested array of suggestions.
     */
    private function convertSuggestionsToNestedArray(array $Suggestions): array
    {
        # build up a nested array of suggestions where each level of the array
        # is keyed by the termid
        $Facets = [];

        # pre-load our ancestor cache
        $this->AncestorCache = ClassificationFactory::getAncestorMap(
            array_keys($Suggestions)
        );

        # iterate over the suggestions, adding each to our nested array
        foreach ($Suggestions as $TermId => $TermInfo) {
            $TargetLocation = &$Facets;
            foreach ($this->getAncestorList($TermId) as $Id) {
                $TargetLocation = &$TargetLocation[$Id];
            }

            $TargetLocation[$TermId]["TermInfo"] = $TermInfo;
        }

        return $Facets;
    }

    /**
     * Add the current search terms for a field in to a nested array of
     *   search suggestions if they were absent and mark these terms selected.
     * @param array $Facets Nested array of search suggestions that will be
     *   modified.
     * @param MetadataField $Field Field we are suggesting terms for.
     * @param array $CurrentValues Current list of search strings.
     */
    private function addSelectionsToNestedArray(
        array $Facets,
        MetadataField $Field,
        array $CurrentValues
    ): array {
        # mark each level of the tree for the current selections as selected
        foreach ($CurrentValues as $SelectedValue) {
            $TargetLocation = &$Facets;

            # strip enclosing quotes
            if (preg_match('%^\"(.*)\"$%', $SelectedValue, $Matches)) {
                 $SelectedValue = $Matches[1];
            }

            $CurrentTerm = "";
            # remove "--" and whitespace from segments before looking up
            # terms IDs by name
            $Segments = explode("--", $SelectedValue);
            foreach ($Segments as $Segment) {
                $Segment = trim($Segment);
                $CurrentTerm .= (strlen($CurrentTerm) ? " -- " : "").$Segment;

                $TermId = $Field->getFactory()->getItemIdByName($CurrentTerm);

                # if term is not valid, nothing to do
                if ($TermId === false) {
                    break;
                }

                # add this classification to our facets if it was absent
                if (!isset($TargetLocation[$TermId])) {
                    $Classification = new Classification($TermId);
                    $TargetLocation[$TermId] = [
                        "TermInfo" => [
                            "Id" => $Classification->id(),
                            "Name" => $Classification->name(),
                            "Count" => 0,
                        ]
                    ];
                }

                $TargetLocation = &$TargetLocation[$TermId];

                $TargetLocation["TermInfo"]["IsSelected"] = true;
            }
        }

        return $Facets;
    }

    /**
     * Add all top-level classifications for a given tree field to the list of
     *   facets.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to use
     * @return array updated facets
     */
    private function addTopLevelClassifications(
        array $Facets,
        MetadataField $Field
    ): array {
        $ClassIds = $Field->getFactory()->getItemIds(
            "Depth = 0 AND FullResourceCount > 0"
        );

        foreach ($ClassIds as $Id) {
            if (isset($Facets[$Id])) {
                continue;
            }

            $Facets[$Id] = [
                "TermInfo" => [
                    "Id" => $Id,
                    "Name" => (new Classification($Id))->name(),
                    "Count" => 0,
                ],
            ];
        }
        return $Facets;
    }

    /**
     * Add to a given list of facets any children of selected terms.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field to use
     * @erutn array updated facets
     */
    private function addChildrenOfSelectedTerms(
        array $Facets,
        MetadataField $Field
    ): array {
        foreach ($Facets as $TermId => &$SubFacets) {
            # nothing to do for terminfo entries
            if ($TermId == "TermInfo") {
                continue;
            }

            # nothing to do for non-selected terms
            if (!isset($SubFacets["TermInfo"]["IsSelected"])) {
                continue;
            }

            # assume we won't have any selected children
            $HasSelectedChildren = false;

            # iterate over child terms
            foreach ($Field->getFactory()->getChildIds($TermId) as $Id) {
                # if term is already present in our list of facets then we do not need to add it
                # but we will want to track if any such terms were selected
                if (isset($SubFacets[$Id])) {
                    $HasSelectedChildren |= isset($SubFacets[$Id]["TermInfo"]["IsSelcted"]);
                    continue;
                }

                # get classification
                $Classification = new Classification($Id);

                # if classification is not used on any records, nothing to do
                if ($Classification->fullResourceCount() == 0) {
                    continue;
                }

                # otherwise, add it into the list
                $SubFacets[$Id] = [
                    "TermInfo" => [
                        "Id" => $Id,
                        "Name" => $Classification->name(),
                        "Count" => 0,
                    ],
                ];
            }

            # if this set of subfacets contains a selected child, recurse into them as well
            # to add their children as needed
            if ($HasSelectedChildren) {
                $SubFacets = $this->addChildrenOfSelectedTerms(
                    $SubFacets,
                    $Field
                );
            }
        }

        return $Facets;
    }

    /**
     * Add entries for each selected term within a controlled name field.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to add terms for
     * @param array $CurrentValues Search strings for specified field
     * @return array Modified list of facets
     */
    private function markSearchTermsSelectedForCNameFacet(
        array $Facets,
        MetadataField $Field,
        array $CurrentValues
    ): array {
        $Factory = $Field->getFactory();

        # be sure that we have a facet for every selected term
        foreach ($CurrentValues as $Value) {
            # if this isn't an "is" condition, move to the next one
            if ($Value[0] !== "=") {
                continue;
            }

            # trim "=" operator off beginning of value
            $Value = substr($Value, 1);

            # if value appears to be a valid controlled name ID
            if (is_numeric($Value) && $Factory->itemExists($Value)) {
                $CName = new ControlledName($Value);
            } else {
                $CName = $Factory->getItemByName($Value);
            }

            # if none was found, move to the next one
            if (is_null($CName)) {
                continue;
            }

            # if needed, add information for this term to our facets
            if (!isset($Facets[$CName->id()])) {
                $Facets[$CName->id()] = [
                    "TermInfo" => [
                        "Id" => $CName->id(),
                        "Name" => $CName->name(),
                        "Count" => 0
                    ],
                ];
            }

            # mark this term selected
            $Facets[$CName->id()]["TermInfo"]["IsSelected"] = true;
        }

        return $Facets;
    }

    /**
     * Add all the terms from a given controlled vocabulary to a list of facets.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to use
     * @return array updated facets
     */
    private function addFacetsFromCName(
        array $Facets,
        MetadataField $Field
    ): array {
        $Factory = $Field->getFactory();

        $CacheKey = __FUNCTION__."-".$Field->id();
        $ItemCount = $this->DataCache->get($CacheKey);
        if ($ItemCount === null) {
            $ItemCount = $Factory->getItemCount();
            $this->DataCache->set($CacheKey, $ItemCount, self::$CacheTTL);
        }

        # refuse to add facets if vocabulary is too large
        if ($ItemCount > $this->MaxFacetsPerField) {
            return [];
        }

        foreach ($Factory->getItemIds() as $Id) {
            if (isset($Facets[$Id])) {
                continue;
            }

            $Facets[$Id] = [
                "TermInfo" => [
                    "Id" => $Id,
                    "Name" => (new ControlledName($Id))->name(),
                    "Count" => 0,
                ],
            ];
        }

        return $Facets;
    }

    /**
     * Remove from a set of search facets entries for any controlled names
     *   where adding that name will reduce the results to zero or will not
     *   add any new results.
     * @param array $Facets Current list of facets
     * @param MetadataField $Field Field to use
     * @return array updated facets
     */
    private function pruneUselessCNamesFromFacet(
        $Facets,
        $Field
    ): array {
        $RFactory = new RecordFactory($Field->schemaId());

        $CurrentValues = $this->SearchParams->getSearchStringsForField($Field);

        # Determine the search logic to use when adding a facet to this field.
        # If we have any terms for this field from the current search, then adding
        # another (in the form of an additional term for this facet)
        # will employ the field's search group logic. Otherwise, it will be
        # the top-level logic of our params
        $Logic = count($CurrentValues) > 0
            ? $Field->searchGroupLogic()
            : ($this->SearchParams->logic() == "OR"
               ? SearchEngine::LOGIC_OR
               : SearchEngine::LOGIC_AND);

        foreach (array_keys($Facets) as $Id) {
            $RecordCount = ($Logic == SearchEngine::LOGIC_AND) ?
                $Facets[$Id]["TermInfo"]["Count"] :
                $RFactory->associatedVisibleRecordCount(
                    $Id,
                    $this->User
                );

            if ($RecordCount == 0) {
                unset($Facets[$Id]);
            }
        }

        return $Facets;
    }

    /**
     * Remove children of facets that are not selected from a nested array of
     *   search suggestions.
     * @param array $Facets Facets to prune.
     * @return array pruned facet
     */
    private function pruneChildrenOfUnselectedFacets(array $Facets)
    {
        foreach ($Facets as $Id => $Item) {
            if ($Id == "TermInfo") {
                continue;
            }

            # if this item is a term that is not selected
            if (isset($Item["TermInfo"])) {
                if (!isset($Item["TermInfo"]["IsSelected"])) {
                    # reduce this facet down to just the term
                    $Facets[$Id] = [
                        "TermInfo" => $Item["TermInfo"],
                    ];
                    continue;
                }
            }

            $Facets[$Id] = $this->pruneChildrenOfUnselectedFacets($Item);
        }

        return $Facets;
    }

    /**
     * Remove any facets that are not selected in the current search
     * @param array $Facets Facets to prune
     * @return array Pruned facets
     */
    private function pruneUnselectedFacets(array $Facets): array
    {
        foreach ($Facets as $Id => $Item) {
            if ($Id == "TermInfo") {
                continue;
            }

            # if this item is an unselected term
            if (isset($Item["TermInfo"])) {
                if (!isset($Item["TermInfo"]["IsSelected"])) {
                    unset($Facets[$Id]);
                    continue;
                }
            }

            $Facets[$Id] = $this->pruneUnselectedFacets($Item);
        }

        return $Facets;
    }

    /**
     * Count the number of suggestions being made in a given set of facets
     * @param array $Facets Facets to count
     * @return int number of suggestions
     */
    private function countFacets(array $Facets): int
    {
        $Count = 0;
        foreach ($Facets as $Id => $Item) {
            if ($Id == "TermInfo") {
                if (!isset($Item["IsSelected"])) {
                    $Count++;
                }
            } else {
                $Count += $this->countFacets($Item);
            }
        }
        return $Count;
    }

    /**
     * Iterate over a nested array of search facets to prepare them for
     *   display. This will append AddLink and RemoveLink entries to each
     *   TermInfo that can be used to modify the current search by
     *   adding/removing the term, normalize the "Name" entries for display,
     *   and put terms in alphabetical order.
     * @param array $Facets Facets to annotate.
     * @param MetadataField $Field Field to add/remove search terms.
     * @return void
     */
    private function prepareFacetsForDisplay(
        array &$Facets,
        MetadataField $Field
    ): void {
        foreach ($Facets as $Id => &$Item) {
            if ($Id == "TermInfo") {
                # generate the appropriate updated url
                if (isset($Item["IsSelected"])) {
                    $Item["RemoveLink"] = $this->removeTermFromSearchURL(
                        $Field,
                        $Item["Name"]
                    );
                } else {
                    $Item["AddLink"] = $this->addTermToSearchURL(
                        $Field,
                        $Item["Name"]
                    );

                    # can skip processing children if the current term cannot
                    # be added
                    if ($Item["AddLink"] === null) {
                        break;
                    }
                }

                # set the name that should be displayed
                if ($Field->type() == MetadataSchema::MDFTYPE_TREE) {
                    $Segments = explode(" -- ", $Item["Name"]);
                    $Item["Name"] = end($Segments);
                }
            } else {
                $this->prepareFacetsForDisplay($Item, $Field);
            }
        }

        # if this facet cannot be added, clear all its info
        if (isset($Facets["TermInfo"]) &&
            array_key_exists("AddLink", $Facets["TermInfo"]) &&
            $Facets["TermInfo"]["AddLink"] === null) {
            $Facets = [];
            return;
        }

        # remove any empty facets
        $Facets = array_filter(
            $Facets,
            function ($Value) {
                return count($Value) > 0;
            }
        );

        # alphabetize the facets at this level of the tree
        uasort(
            $Facets,
            function ($A, $B) {
                if (isset($A["TermInfo"]) && isset($B["TermInfo"])) {
                    return $A["TermInfo"]["Name"] <=> $B["TermInfo"]["Name"];
                } elseif (isset($A["TermInfo"]) && !isset($B["TermInfo"])) {
                    return -1;
                } elseif (!isset($A["TermInfo"]) && isset($B["TermInfo"])) {
                    return 1;
                } else {
                    return 0;
                }
            }
        );
    }

    ##
    # functions to manipulate search URLs

    /**
     * Add a specified term to our search URL.
     * @param MetadataField $Field Metadata field for this term.
     * @param string $Term Search term to add.
     * @return string|null URL with search parameters including new term or NULL
     *    when adding the term will exceed the max search complexity.
     */
    private function addTermToSearchURL(
        MetadataField $Field,
        string $Term
    ): ?string {
        if ($Field->type() == MetadataSchema::MDFTYPE_TREE) {
            $TreeArray = $this->addTermToTreeArray(
                $this->getSearchTermsAsTreeArray($Field),
                $Term
            );

            $Factory = $Field->getFactory();
            $SearchStrings = [];
            foreach ($this->treeArrayToSearchStrings($TreeArray) as $NewTerm) {
                $ItemId = $Factory->getItemIdByName($NewTerm);
                $SearchStrings[] = "^".$ItemId;
            }
        } else {
            $SearchStrings = $this->SearchParams->getSearchStringsForField($Field);
            $SearchStrings[] = "=".$Term;
        }

        if (count($SearchStrings) >= 26) {
            return null;
        }

        # create our own copy of search parameters
        $OurSearchParams = clone $this->SearchParams;

        # clear any current search strings for this field
        $OurSearchParams->removeParameter(null, $Field);

        # create a new subgroup with our new search strings
        $Subgroup = new SearchParameterSet();
        $Subgroup->logic($Field->searchGroupLogic());
        $Subgroup->addParameter($SearchStrings, $Field);

        # add it to our search
        $OurSearchParams->addSet($Subgroup);

        # build new URL with revised search parameters
        $Url = implode("&amp;", array_filter([
            $this->BaseLink,
            $OurSearchParams->UrlParameterString()
        ]));

        # return new URL to caller
        return $Url;
    }

    /**
     * Remove a specified term from our search URL.
     * @param MetadataField $Field Metadata field for this term
     * @param string $Term Term or array of Terms to remove
     * @return string URL with search parameters with term removed.
     */
    private function removeTermFromSearchURL(
        MetadataField $Field,
        string $Term
    ): string {
        # create our own copy of search parameters with specified parameter removed
        $OurSearchParams = clone $this->SearchParams;

        if ($Field->type() == MetadataSchema::MDFTYPE_TREE) {
            $TreeArray = $this->removeTermFromTreeArray(
                $this->getSearchTermsAsTreeArray($Field),
                $Term
            );
            $NewTerms = $this->treeArrayToSearchStrings($TreeArray);

            # clear existing settings
            $OurSearchParams->removeParameter(null, $Field);

            $Factory = $Field->getFactory();
            # create a subgroup and populate it with revised search
            $Subgroup = new SearchParameterSet();
            $Subgroup->logic($Field->searchGroupLogic());
            foreach ($NewTerms as $NewTerm) {
                $ItemId = $Factory->getItemIdByName($NewTerm);
                $Subgroup->addParameter("^".$ItemId, $Field);
            }

            # add it to our search
            $OurSearchParams->addSet($Subgroup);
        } else {
            $OurSearchParams->removeParameter(
                "=".$Term,
                $Field
            );
        }

        # build new URL with revised search parameters
        $Url = implode("&amp;", array_filter([
            $this->BaseLink,
            $OurSearchParams->UrlParameterString()
        ]));

        # return new URL to caller
        return $Url;
    }

    ##
    # Functions to manipulate a nested array representation of a search terms
    # for a tree field.
    #
    # If the selections for a field are:
    #   Mathematics
    #   Science -- Biology
    #   Science -- Physics
    #
    # Then this will be represented as:
    # [
    #     "Mathematics" => [],
    #     "Science" => [
    #         "Biology" => [],
    #         "Physics" => [],
    #      ]
    # ]

    /**
     * Get the search terms for a given field as a nested array suitable for
     *   easy manipulation of multiple selections within a given tree.
     * @param MetadataField $Field Field to fetch terms for.
     * @return array nested array of search terms
     */
    private function getSearchTermsAsTreeArray(
        MetadataField $Field
    ): array {
        static $TreeArrays;
        if (!isset($TreeArrays[$Field->id()])) {
            $Factory = $Field->getFactory();

            $CurrentTerms = $this->normalizeTreeValues(
                $this->SearchParams->getSearchStringsForField($Field),
                $Field
            );

            $TreeArray = [];
            foreach ($CurrentTerms as $CurrentTerm) {
                $TreeArray = $this->addTermToTreeArray($TreeArray, $CurrentTerm);
            }

            $TreeArrays[$Field->id()] = $TreeArray;
        }

        return $TreeArrays[$Field->id()];
    }

    /**
     * Convert a nested array of terms to a list of search strings.
     * @param array $TreeArray Tree array to convert.
     * @param string $ParentPrefix Parent prefix for recursive calls (DO NOT USE).
     * @return array List of search strings.
     */
    private function treeArrayToSearchStrings(
        array $TreeArray,
        string $ParentPrefix = ""
    ): array {
        $Result = [];

        foreach ($TreeArray as $ChildPrefix => $Children) {
            if (count($Children) == 0) {
                $Result[] = (strlen($ParentPrefix) ? $ParentPrefix." -- " : "").$ChildPrefix;
            } else {
                $Leaves = $this->treeArrayToSearchStrings($Children, $ChildPrefix);
                foreach ($Leaves as $Leaf) {
                    $Result[] = (strlen($ParentPrefix) ? $ParentPrefix." -- " : "").$Leaf;
                }
            }
        }

        return $Result;
    }

    /**
     * Add new terms to the nested array representation of a tree.
     * @param array $TreeArray Array representation to modify.
     * @param string $Term New search term to add.
     * @return array Modified array.
     */
    private function addTermToTreeArray(
        array $TreeArray,
        string $Term
    ) {
        if (is_numeric($Term)) {
            # if ClassificationId provided that does not (any longer?) exist,
            # nothing to do
            if (!Classification::itemExists((int)$Term)) {
                return $TreeArray;
            }

            $Term = (new Classification($Term))->fullName();
        }

        $Segments = explode(" -- ", $Term);

        $TargetLocation = &$TreeArray;
        foreach ($Segments as $Segment) {
            if (!isset($TargetLocation[$Segment])) {
                $TargetLocation[$Segment] = [];
            }
            $TargetLocation = &$TargetLocation[$Segment];
        }

        return $TreeArray;
    }

    /**
     * Remove a search term and all its children for the nested array
     *   representation of a tree.
     * @param array $TreeArray Array representation to modify.
     * @param string $Term Search term to remove.
     * @return array Modified array.
     */
    private function removeTermFromTreeArray(
        array $TreeArray,
        string $Term
    ): array {
        if (is_numeric($Term)) {
            $Term = (new Classification($Term))->fullName();
        }
        $Segments = explode(" -- ", $Term);

        $CurLocation = &$TreeArray;
        $TargetLocation = null;
        $TargetIndex = null;

        foreach ($Segments as $Segment) {
            # if the given term isn't actually in our tree array, then there's
            # nothing to do
            if (!isset($CurLocation[$Segment])) {
                break;
            }

            $TargetLocation = &$CurLocation;
            $TargetIndex = $Segment;
            $CurLocation = &$TargetLocation[$Segment];
        }

        if (!is_null($TargetLocation)) {
            unset($TargetLocation[$TargetIndex]);
        }

        return $TreeArray;
    }

    ##
    # Misc utility functions

    /**
     * Signal event to allow other code to modify the field value.
     * @param MetadataField $Field Metadata field to process
     * @param array|string $Value Value of the field.
     * @return mixed Possibly modified field value.
     */
    private function filterFieldValue(
        MetadataField $Field,
        $Value
    ) {
        $SignalResult = ApplicationFramework::getInstance()->signalEvent(
            "EVENT_FIELD_DISPLAY_FILTER",
            [
                "Field" => $Field,
                "Resource" => null,
                "Value" => $Value
            ]
        );

        return $SignalResult["Value"];
    }

    /**
     * Normalize the various formats used for a 'begins with' search for a tree field
     *   to the Full Name of the Classification being searched for.
     * @param array $Values Search values for a tree field.
     * @param MetadataField $Field Field being searched.
     * @return array Possibly modified Values.
     */
    private function normalizeTreeValues(
        array $Values,
        MetadataField $Field
    ): array {
        sort($Values);

        # look for legacy, 2-element 'is or begins with' searches, convert those
        # to '^XYZ' form
        if (count($Values) == 2
                && preg_match('/^=(.*)$/', $Values[0], $FirstMatch)
                && preg_match('/^\^(.*) -- *$/', $Values[1], $SecondMatch)
                && $FirstMatch[1] == $SecondMatch[1]) {
            $Values = ["^".$FirstMatch[1] ];
        }

        # iterate over values
        $Factory = $Field->getFactory();
        foreach ($Values as &$Value) {
            if (preg_match('%\^([0-9]+)$%', $Value, $Matches) &&
                $Factory->itemExists($Matches[1])) {
                $Classification = new Classification($Matches[1]);
                $Value = "^".$Classification->fullName();
            # convert '^XYZ --' or '^XYZ" form to XYZ
            } elseif (preg_match('%\^(.+)( -- *)?$%', $Value, $Matches)) {
                $Value = $Matches[1];
            }
        }

        return $Values;
    }

    /**
     * Get the list of ancestor terms for a given classification ID.
     * @param int $Id Classification to look up.
     * @return array Ancestor IDs in order from the root id till the immediate
     *   parent of the provided Classification.
     */
    private function getAncestorList(int $Id): array
    {
        $Result = [];
        while (($Id = $this->getAncestor($Id)) >= 0) {
            array_unshift($Result, $Id);
        }

        return $Result;
    }

    /**
     * Get the ancestor of a given classification, using a cache for
     *   performance when generating facets.
     * @param int $Id Classification to look up.
     * @return int Parent classification id.
     */
    private function getAncestor(int $Id): int
    {
        if (!isset($this->AncestorCache[$Id])) {
            $this->AncestorCache[$Id] = (new Classification($Id))->parentId();
        }

        return $this->AncestorCache[$Id];
    }

    protected $FieldsOpenByDefault = [];
    protected $SuggestionsByFieldName = [];
    protected $TreeSuggestionsByFieldName = [];
    protected $ShowCounts = true;

    private $BaseLink = "index.php?P=SearchResults";
    private $MaxFacetsPerField;
    private $SearchParams;
    private $SearchResults;
    private $AncestorCache = [];

    private const CACHE_KEY_PREFIX = "Metavus-SearchFacetUI-";
}
