Subversion Repositories cheapmusic

<?php namespace Fuse;

use Fuse\Bitap\Bitap;
use function Fuse\Helpers\deep_value;
use function Fuse\Helpers\is_list;

class Fuse
{
    public $options;

    public function __construct($list, $options = [])
    {
        $this->options = array_merge([
            'location' => 0,
            'distance' => 100,
            'threshold' => 0.6,
            'maxPatternLength' => 32,
            'caseSensitive' => false,
            'tokenSeparator' => ' +',
            'findAllMatches' => false,
            'minMatchCharLength' => 1,
            'id' => null,
            'keys' => [],
            'shouldSort' => true,
            'getFn' => '\Fuse\Helpers\deep_value',
            'sortFn' => function ($a, $b) {
                if ($a['score'] === $b['score']) {
                    return $a['index'] === $b['index']
                        ? 0
                        : (
                            $a['index'] < $b['index']
                            ? -1
                            : 1
                        );
                } elseif ($a['score'] < $b['score']) {
                    return -1;
                } else {
                    return 1;
                }
            },
            'tokenize' => false,
            'matchAllTokens' => false,
            'includeMatches' => false,
            'includeScore' => false,
            'verbose' => false
        ], $options);
        $this->options['isCaseSensitive'] = $this->options['caseSensitive'];

        $this->setCollection($list);
    }

    public function setCollection($list)
    {
        $list = array_values($list);
        $this->list = $list;
        return $list;
    }

    public function search($pattern, $opts = [ 'limit' => false ])
    {
        $this->log("---------\nSearch pattern: \"$pattern\"");

        $searchers = $this->prepareSearchers($pattern);

        $search = $this->innerSearch($searchers['tokenSearchers'], $searchers['fullSearcher']);

        $this->computeScore($search['weights'], $search['results']);

        if ($this->options['shouldSort']) {
            $this->sort($search['results']);
        }

        if (is_int($opts['limit'])) {
            $search['results'] = array_slice($search['results'], 0, $opts['limit']);
        }

        return $this->format($search['results']);
    }

    protected function prepareSearchers($pattern = '')
    {
        $tokenSearchers = [];

        if ($this->options['tokenize']) {
            // Tokenize on the separator
            $tokens = mb_split($this->options['tokenSeparator'], $pattern);

            for ($i = 0, $len = sizeof($tokens); $i < $len; $i++) {
                $tokenSearchers[] = new Bitap($tokens[$i], $this->options);
            }
        }

        $fullSearcher = new Bitap($pattern, $this->options);

        return [
            'tokenSearchers' => $tokenSearchers,
            'fullSearcher' => $fullSearcher
        ];
    }

    protected function innerSearch($tokenSearchers = [], $fullSearcher = null)
    {
        $list = $this->list;
        $resultMap = [];
        $results = [];

        // Check the first item in the list, if it's a string, then we assume
        // that every item in the list is also a string, and thus it's a flattened array.
        if (is_string($list[0])) {
            // Iterate over every item
            for ($i = 0, $len = sizeof($list); $i < $len; $i++) {
                $this->analyze(
                    [
                        'key' => '',
                        'value' => $list[$i],
                        'record' => $i,
                        'index' => $i
                    ],
                    $resultMap,
                    $results,
                    $tokenSearchers,
                    $fullSearcher
                );
            }

            return [
                'weights' => null,
                'results' => $results
            ];
        }

        // Otherwise, the first item is an Object (hopefully), and thus the searching
        // is done on the values of the keys of each item.
        $weights = [];
        for ($i = 0, $len = sizeof($list); $i < $len; $i++) {
            $item = $list[$i];
            // Iterate over every key
            for ($j = 0, $keysLen = sizeof($this->options['keys']); $j < $keysLen; $j++) {
                $key = $this->options['keys'][$j];
                if (!is_string($key)) {
                    $weights[$key['name']] = [
                        'weight' => (1 - $key['weight']) ?: 1
                    ];
                    if ($key['weight'] <= 0 || $key['weight'] > 1) {
                        throw new \LogicException('Key weight has to be > 0 and <= 1');
                    }
                    $key = $key['name'];
                } else {
                    $weights[$key] = [
                        'weight' => 1
                    ];
                }

                $this->analyze(
                    [
                        'key' => $key,
                        'value' => $this->options['getFn']($item, $key),
                        'record' => $item,
                        'index' => $i
                    ],
                    $resultMap,
                    $results,
                    $tokenSearchers,
                    $fullSearcher
                );
            }
        }

        return [
            'weights' => $weights,
            'results' => $results
        ];
    }

    protected function analyze($query = [], &$resultMap = [], &$results = [], &$tokenSearchers = [], &$fullSearcher = null)
    {
        $query = array_merge([
            'key' => null,
            'arrayIndex' => -1,
            'value' => null,
            'record' => null,
            'index' => null
        ], $query);

        // Check if the texvaluet can be searched
        if (is_null($query['value'])) {
            return;
        }

        $exists = false;
        $averageScore = -1;
        $numTextMatches = 0;

        if (is_string($query['value'])) {
            $this->log("\nKey: " . ($query['key'] === '' ? '-' : $query['key']));

            $mainSearchResult = $fullSearcher->search($query['value']);
            $this->log('Full text: "' . $query['value'] . '", score: ' . $mainSearchResult['score']);

            if ($this->options['tokenize']) {
                $words = mb_split($this->options['tokenSeparator'], $query['value']);
                $scores = [];

                for ($i = 0; $i < sizeof($tokenSearchers); $i++) {
                    $tokenSearcher = $tokenSearchers[$i];

                    $this->log("\nPattern: \"{$tokenSearcher->pattern}\"");

                    // $tokenScores = []
                    $hasMatchInText = false;

                    for ($j = 0; $j < sizeof($words); $j++) {
                        $word = $words[$j];
                        $tokenSearchResult = $tokenSearcher->search($word);
                        $obj = [];
                        if ($tokenSearchResult['isMatch']) {
                            $obj[$word] = $tokenSearchResult['score'];
                            $exists = true;
                            $hasMatchInText = true;
                            $scores[] = $tokenSearchResult['score'];
                        } else {
                            $obj[$word] = 1;
                            if (!$this->options['matchAllTokens']) {
                                $scores[] = 1;
                            }
                        }
                        $this->log('Token: "' . $word . '", score: ' . $obj[$word]);
                        // tokenScores.push(obj)
                    }

                    if ($hasMatchInText) {
                        $numTextMatches += 1;
                    }
                }

                $scoresLen = sizeof($scores);

                if ($scoresLen > 0) {
                    $averageScore = $scores[0];
                    for ($i = 1; $i < $scoresLen; $i++) {
                        $averageScore += $scores[$i];
                    }
                    $averageScore = $averageScore / $scoresLen;
                } else {
                    $averageScore = -1;
                }

                $this->log('Token score average: ', $averageScore);
            }

            $finalScore = $mainSearchResult['score'];
            if ($averageScore > -1) {
                $finalScore = ($finalScore + $averageScore) / 2;
            }

            $this->log('Score average: ', $finalScore);

            $checkTextMatches = ($this->options['tokenize'] && $this->options['matchAllTokens'])
                ? $numTextMatches >= sizeof($tokenSearchers)
                : true;

            $this->log("\nCheck Matches: ", $checkTextMatches);

            // If a match is found, add the item to <rawResults>, including its score
            if (($exists || $mainSearchResult['isMatch']) && $checkTextMatches) {
                // Check if the item already exists in our results
                if (isset($resultMap[$query['index']])) {
                    $existingResult = &$resultMap[$query['index']];
                } else {
                    $existingResult = null;
                }

                if (!is_null($existingResult)) {
                    // Use the lowest score
                    // existingResult.score, bitapResult.score
                    $existingResult['output'][] = [
                        'key' => $query['key'],
                        'arrayIndex' => $query['arrayIndex'],
                        'value' => $query['value'],
                        'score' => $finalScore,
                        'matchedIndices' => $mainSearchResult['matchedIndices']
                    ];
                } else {
                    // Add it to the raw result list
                    $resultMap[$query['index']] = [
                        'item' => $query['record'],
                        'output' => [[
                            'key' => $query['key'],
                            'arrayIndex' => $query['arrayIndex'],
                            'value' => $query['value'],
                            'score' => $finalScore,
                            'matchedIndices' => $mainSearchResult['matchedIndices']
                        ]]
                    ];

                    $results[] = &$resultMap[$query['index']];
                }
            }
        } elseif (is_list($query['value'])) {
            for ($i = 0, $len = sizeof($query['value']); $i < $len; $i++) {
                $this->analyze(
                    [
                        'key' => $query['key'],
                        'arrayIndex' => $i,
                        'value' => $query['value'][$i],
                        'record' => $query['record'],
                        'index' => $query['index']
                    ],
                    $resultMap,
                    $results,
                    $tokenSearchers,
                    $fullSearcher
                );
            }
        }
    }

    protected function computeScore($weights, &$results)
    {
        $this->log("\n\nComputing score:\n");

        for ($i = 0, $len = sizeof($results); $i < $len; $i++) {
            $result = &$results[$i];
            $output = $result['output'];
            $scoreLen = sizeof($output);

            $currScore = 1;
            $bestScore = 1;

            for ($j = 0; $j < $scoreLen; $j++) {
                $weight = $weights
                    ? $weights[$output[$j]['key']]['weight']
                    : 1;
                $score = $weight === 1
                    ? $output[$j]['score']
                    : ($output[$j]['score'] ?: 0.001);
                $nScore = $score * $weight;

                if ($weight !== 1) {
                    $bestScore = min($bestScore, $nScore);
                } else {
                    $output[$j]['nScore'] = $nScore;
                    $currScore *= $nScore;
                }
            }

            $result['score'] = $bestScore == 1
                ? $currScore
                : $bestScore;

            $this->log($result);
        }
    }

    protected function sort(&$results)
    {
        $this->log("\n\nSorting....");

        $results = array_map(function ($result, $index) {
            $result['index'] = $index;
            return $result;
        }, array_values($results), array_keys($results));

        usort($results, $this->options['sortFn']);

        $results = array_map(function ($result) {
            unset($result['index']);
            return $result;
        }, $results);
    }

    protected function format(&$results)
    {
        $finalOutput = [];

        $this->log("\n\nOutput:\n\n", $results);

        $transformers = [];

        if ($this->options['includeMatches']) {
            $transformers[] = function ($result, &$data) {
                $output = $result['output'];
                $data['matches'] = [];

                for ($i = 0, $len = sizeof($output); $i < $len; $i++) {
                    $item = $output[$i];

                    if (sizeof($item['matchedIndices']) === 0) {
                        continue;
                    }

                    $obj = [
                        'indices' => $item['matchedIndices'],
                        'value' => $item['value']
                    ];
                    if ($item['key']) {
                        $obj['key'] = $item['key'];
                    }
                    if (isset($item['arrayIndex']) && $item['arrayIndex'] > -1) {
                        $obj['arrayIndex'] = $item['arrayIndex'];
                    }
                    $data['matches'][] = $obj;
                }
            };
        }

        if ($this->options['includeScore']) {
            $transformers[] = function ($result, &$data) {
                $data['score'] = $result['score'];
            };
        }

        for ($i = 0, $len = sizeof($results); $i < $len; $i += 1) {
            $result = &$results[$i];

            if ($this->options['id']) {
                $getterResult = $this->options['getFn']($result['item'], $this->options['id']);
                $result['item'] = $getterResult[0];
            }

            if (!sizeof($transformers)) {
                $finalOutput[] = $result['item'];
                continue;
            }

            $data = [
                'item' => $result['item']
            ];

            for ($j = 0, $tlen = sizeof($transformers); $j < $tlen; $j++) {
                $transformers[$j]($result, $data);
            }

            $finalOutput[] = $data;
        }

        return $finalOutput;
    }

    protected function log(...$args)
    {
        if ($this->options['verbose']) {
            echo "\n";
            foreach ($args as $arg) {
                if (is_array($arg) || is_object($arg)) {
                    var_dump($arg);
                } elseif (is_bool($arg)) {
                    echo($arg ? 'true' : 'false');
                } else {
                    echo $arg;
                }
            }
        }
    }
}