searchindex.cpp

Go to the documentation of this file.

/*
# Copyright (C) 2015 Fulvio Benini

* This file is part of Scid (Shane's Chess Information Database).
*
* Scid is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation.
*
* Scid is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Scid. If not, see <http://www.gnu.org/licenses/>.
*/

#include "common.h"
#include "misc.h"
#include "scidbase.h"
#include <algorithm>
#include <string>
#include <vector>

namespace {

class SearchName {
    const scidBaseT* base_;
    idNumberT (IndexEntry::* f1_) () const;
    idNumberT (IndexEntry::* f2_) () const;
    std::vector<bool> mask_;

public:
    SearchName(const scidBaseT* base,
               std::string pattern,
               nameT name_type,
               idNumberT (IndexEntry::* f1) () const,
               idNumberT (IndexEntry::* f2) () const = 0)
    : base_(base), f1_(f1), f2_(f2) {
        idNumberT n = base->getNameBase()->GetNumNames(name_type);
        mask_.resize(n);

        size_t l = pattern.length();
        bool exact = (l > 2 && pattern[l -1] == '"' && pattern[0] == '"');
        if (exact) {
            Init_exact(n, name_type, pattern.substr(1, l -2));
        } else {
            Init_icase_ignoreSpaces(n, name_type, pattern.c_str());
        }
    }

    void Init_exact (idNumberT n, nameT name_type, std::string pattern) {
        const NameBase* nb = base_->getNameBase();
        for (idNumberT i=0; i < n; i++) {
            const char* name = nb->GetName (name_type, i);
            mask_[i] = (name == pattern);
        }
    }

    void Init_icase_ignoreSpaces(idNumberT n, nameT name_type, const char* pattern) {
        const NameBase* nb = base_->getNameBase();
        for (idNumberT i=0; i < n; i++) {
            const char* name = nb->GetName (name_type, i);
            mask_[i] = strAlphaContains(name, pattern);
        }
    }

    bool operator() (gamenumT gnum) const {
        bool res = mask_[(base_->getIndexEntry(gnum)->*f1_)()];
        if (!res && f2_ != 0) {
            return mask_[(base_->getIndexEntry(gnum)->*f2_)()];
        }
        return res;
    }
};

class SearchSiteCountry {
    const scidBaseT* base_;
    std::vector<bool> mask_;

public:
    SearchSiteCountry(const scidBaseT* base,
                      std::string country)
    : base_(base) {
        idNumberT n = base->getNameBase()->GetNumNames(NAME_SITE);
        mask_.resize(n);

        std::transform(country.begin(), country.end(), country.begin(), ::toupper);
        const NameBase* nb = base_->getNameBase();
        for (idNumberT i=0; i < n; i++) {
            const char* site = nb->GetName(NAME_SITE, i);
            const char* it = site;
            while (*it != 0) it++;
            if (std::distance(site, it) > 3) it -= 3;
            std::string tmp = it;
            std::transform(tmp.begin(), tmp.end(), tmp.begin(), ::toupper);
            mask_[i] = (tmp == country);
        }
    }

    bool operator() (gamenumT gnum) const {
        return mask_[base_->getIndexEntry(gnum)->GetSite()];
    }
};

class SearchFlag {
    const scidBaseT* base_;
    uint32_t flagMask_;

public:
    SearchFlag(const scidBaseT* base,
               const char* flags)
    : base_(base) {
        flagMask_ = IndexEntry::StrToFlagMask(flags);
        ASSERT(flagMask_ != 0);
    }

    bool operator() (gamenumT gnum) const {
        return base_->getIndexEntry(gnum)->GetFlag(flagMask_);
    }
};

class SearchResult {
    const scidBaseT* base_;
    bool result_[NUM_RESULT_TYPES];

public:
    SearchResult(const scidBaseT* base,
                 const char* results)
    : base_(base) {
        std::fill_n(result_, NUM_RESULT_TYPES, false);
        const char* end = RESULT_CHAR + NUM_RESULT_TYPES;
        while (*results != 0) {
            const char* it = std::find(RESULT_CHAR, end, *results);
            if (it != end) result_[std::distance(RESULT_CHAR, it)] = true;
            results++;
        }
    }

    bool operator() (gamenumT gnum) const {
        resultT r = base_->getIndexEntry(gnum)->GetResult();
        return result_[r];
    }
};

template <typename T>
class SearchRange : public StrRange {
protected:
    const scidBaseT* base_;
    T (IndexEntry::* f_) () const;

protected:
    SearchRange(const scidBaseT* base,
                T (IndexEntry::* f) () const)
    : base_(base), f_(f) {}

public:
    SearchRange(const scidBaseT* base,
                const char* range,
                T (IndexEntry::* f) () const)
    : StrRange(range), base_(base), f_(f) {}

    bool operator() (gamenumT gnum) const {
        long v = (base_->getIndexEntry(gnum)->*f_)();
        return inRange(v);
    }
};

class SearchRangeDate : public SearchRange<dateT> {
public:
    SearchRangeDate(const scidBaseT* base,
                    const char* range,
                    dateT (IndexEntry::* f) () const)
    : SearchRange<dateT>(base, f) {
        // Extract two whitespace-separated dates:
        const char* v = strFirstWord(range);
        min_ = date_EncodeFromString (v);
        const char* next = strNextWord(v);
        max_ = (*next == 0) ? min_ : date_EncodeFromString (next);
        if (min_ > max_) std::swap(min_, max_);
    }
};

class SearchRangeEco : public SearchRange<ecoT> {
public:
    SearchRangeEco(const scidBaseT* base,
                   const char* range,
                   ecoT (IndexEntry::* f) () const)
    : SearchRange<ecoT>(base, f) {
        // Extract two whitespace-separated ECO codes:
        const char* v = strFirstWord(range);
        min_ = eco_FromString(v);
        const char* next = strNextWord(v);
        max_ = (*next == 0) ? min_ : eco_FromString(next);
        if (min_ > max_) std::swap(min_, max_);
        // Set eco maximum to be the largest subcode, for example,
        // "B07" -> "B07z4" to make sure subcodes are included in the range:
        max_ = eco_LastSubCode(static_cast<ecoT>(max_));
    }
};

class SearchRangeGamenum : public SearchRange<gamenumT> {
public:
    SearchRangeGamenum(const scidBaseT* base,
                       const char* range)
    : SearchRange<gamenumT>(base, range, 0) {
        // Set up game number range:
        // Note that a negative number means a count from the end,
        // so -1 = last game, -2 = second to last, etc.
        if (min_ < 0) min_ += base->numGames();
        else min_ -=1;
        if (max_ < 0) max_ += base->numGames();
        else max_ -=1;
        if (min_ > max_) std::swap(min_, max_);
    }

    bool operator() (gamenumT gnum) const {
        if (static_cast<long>(gnum) < min_ ||
            static_cast<long>(gnum) > max_) return false;
        return true;
    }
};

class SearchRangeElo : public SearchRange<eloT> {
protected:
    eloT (IndexEntry::* fElo1_) (const NameBase*) const;
    eloT (IndexEntry::* fElo2_) (const NameBase*) const;
    const NameBase* nb_;

public:
    SearchRangeElo(const scidBaseT* base,
                   const char* range,
                   eloT (IndexEntry::* f1) (const NameBase*) const,
                   eloT (IndexEntry::* f2) (const NameBase*) const = 0)
    : SearchRange<eloT>(base, range, 0), fElo1_(f1), fElo2_(f2) {
        nb_ = base_->getNameBase();
    }

    bool operator() (gamenumT gnum) const {
        long v1 = (base_->getIndexEntry(gnum)->*fElo1_)(nb_);
        long v2 = min_;
        if (fElo2_ != 0) v2 = (base_->getIndexEntry(gnum)->*fElo2_)(nb_);
        if (v1 < min_ || v1 > max_ || v2 < min_ || v2 > max_) return false;
        return true;
    }
};

class SearchRangeEloDiff : public SearchRangeElo {
public:
    SearchRangeEloDiff(const scidBaseT* base,
                       const char* range,
                       eloT (IndexEntry::* f1) (const NameBase*) const,
                       eloT (IndexEntry::* f2) (const NameBase*) const)
    : SearchRangeElo(base, range, f1, f2) {}

    bool operator() (gamenumT gnum) const {
        long v1 = (base_->getIndexEntry(gnum)->*fElo1_)(nb_);
        long v2 = (base_->getIndexEntry(gnum)->*fElo2_)(nb_);
        long v = v1 - v2;
        if (v < min_ || v > max_) return false;
        return true;
    }
};

/**
 * class SearchParam - criteria for the search
 *
 * a SearchParam is a string pair <criteria,value>.
 * criteria should start with '-' and can include optional trailing chars:
 *     '!' look for games that do _not_ match the criteria
 *     '|' look for games that matches the previous criteria _or_ this critera
 *         _or_ operations can be concatenated, so -player a -player| b -player| c
 *         means player contains 'a' or 'b' or 'c'
 * This class do not check if criteria is valid.
 */
class SearchParam {
    std::string op_;
    const char* value_;
    bool opNot_;
    bool opOr_;

public:
    SearchParam(const char* op, const char* value)
    : value_(value), opNot_(false), opOr_(false) {
        if (op != 0 && value_ != 0 && value_[0] != 0) {
            op_ = op;
            if (op_.length() > 1 && op_[0] == '-') {
                op_.erase(0, 1);

                size_t extra = op_.find_last_not_of("!|");
                if (extra == std::string::npos) {
                    op_.clear();
                } else if (++extra < op_.length()) {
                    if (op_.find('!', extra) != std::string::npos) opNot_ = true;
                    if (op_.find('|', extra) != std::string::npos) opOr_ = true;
                    op_.erase(extra);
                }
            }
        }
    }

    void invalidate() {
        op_.clear();
        opNot_ = false;
        opOr_ = false;
    }

    bool operator!() const { return op_.empty(); }
    bool operator==(const char* s) const {
        // Compares @s with op_ (op_ do not contain the starting '-' char
        // and the optional trailing '!' and '|' chars.
        return op_ == s;
    }

    const char* getValue() const { return value_; }
    bool isNot() const { return opNot_; }
    bool isOr() const { return opOr_; }
};

/**
 * parseParams() - parse search criteria
 *
 * Return: a vector containing the SearchParams for the search
 * and set @filterOp to the requested operation.
 */
std::vector<SearchParam> parseParams(int argc, const char ** argv, filterOpT& filterOp) {
    std::vector<SearchParam> res;

    for (int i=0; (i+1) < argc; i += 2) {
        SearchParam p(argv[i], argv[i+1]);
        if (!p) continue;

        if (p == "filter")
            filterOp = strGetFilterOp(p.getValue());
        else
            res.push_back(p);
    }

    return res;
}

/**
 * gamesToSearch() - create the vector of games to be searched
 * @base:      the scidBaseT to search
 * @filter:    games to be searched
 * @filterOp:  FILTEROP_RESET -> reset @filter to include all games
 *             FILTEROP_AND   -> search only games in @filter
 *             FILTEROP_OR    -> search only games not in @filter
 *
 * Return: a vector containing the games (game number) to be searched.
 * If @filterOp == FILTEROP_RESET then
 *         @filter is reset to include all games
 *         @filterOp is changed to FILTEROP_AND
 */
std::vector<gamenumT> collectGames(HFilter& filter, filterOpT& filterOp) {
    ASSERT(filter != 0);

    std::vector<gamenumT> res;
    switch (filterOp) {
    case FILTEROP_RESET:
        filter->includeAll();
        filterOp = FILTEROP_AND;
        /* FALLTHRU */
    case FILTEROP_AND:
        res.resize(filter->size());
        std::copy(filter->begin(), filter->end(), res.begin());
        break;
    case FILTEROP_OR:
        HFilterInverted excluded(filter);
        res.resize(excluded.size());
        std::copy(excluded.begin(), excluded.end(), res.begin());
        break;
    }
    return res;
}

/**
 * doSearch() - partition the input range
 * @itB:    begin of the range
 * @itR:    previous partition point
 * @itE:    end of the range
 * @base:   the scidBaseT to search
 * @param:  parameters for the search
 *
 * Return: the new partition point so that the range [itB, result) contains the matching games
 * If @param is not found, invalidate it and return the previous partition point (@itR)
 */
template<typename I>
I doSearch(I itB, I itR, I itE, const scidBaseT* base, SearchParam& param) {
    if (param == "player") return std::stable_partition(itB, itE,
        SearchName(base, param.getValue(), NAME_PLAYER, &IndexEntry::GetWhite, &IndexEntry::GetBlack)
    );
    if (param == "white") return std::stable_partition(itB, itE,
        SearchName(base, param.getValue(), NAME_PLAYER, &IndexEntry::GetWhite)
    );
    if (param == "black") return std::stable_partition(itB, itE,
        SearchName(base, param.getValue(), NAME_PLAYER, &IndexEntry::GetBlack)
    );
    if (param == "event") return std::stable_partition(itB, itE,
        SearchName(base, param.getValue(), NAME_EVENT, &IndexEntry::GetEvent)
    );
    if (param == "site") return std::stable_partition(itB, itE,
        SearchName(base, param.getValue(), NAME_SITE, &IndexEntry::GetSite)
    );
    if (param == "sitecountry") return std::stable_partition(itB, itE,
        SearchSiteCountry(base, param.getValue())
    );
    if (param == "round") return std::stable_partition(itB, itE,
        SearchName(base, param.getValue(), NAME_ROUND, &IndexEntry::GetRound)
    );
    if (param == "date") return std::stable_partition(itB, itE,
        SearchRangeDate(base, param.getValue(), &IndexEntry::GetDate)
    );
    if (param == "eventdate") return std::stable_partition(itB, itE,
        SearchRangeDate(base, param.getValue(), &IndexEntry::GetEventDate)
    );
    if (param == "elo") return std::stable_partition(itB, itE,
        SearchRangeElo(base, param.getValue(), &IndexEntry::GetWhiteElo, &IndexEntry::GetBlackElo)
    );
    if (param == "welo") return std::stable_partition(itB, itE,
        SearchRangeElo(base, param.getValue(), &IndexEntry::GetWhiteElo)
    );
    if (param == "belo") return std::stable_partition(itB, itE,
        SearchRangeElo(base, param.getValue(), &IndexEntry::GetBlackElo)
    );
    if (param == "delo") return std::stable_partition(itB, itE,
        SearchRangeEloDiff(base, param.getValue(), &IndexEntry::GetWhiteElo, &IndexEntry::GetBlackElo)
    );
    if (param == "eco") return std::stable_partition(itB, itE,
        SearchRangeEco(base, param.getValue(), &IndexEntry::GetEcoCode)
    );
    if (param == "gnum") return std::stable_partition(itB, itE,
        SearchRangeGamenum(base, param.getValue())
    );
    if (param == "length") return std::stable_partition(itB, itE,
        SearchRange<ushort>(base, param.getValue(), &IndexEntry::GetNumHalfMoves)
    );
    if (param == "n_variations") return std::stable_partition(itB, itE,
        SearchRange<uint>(base, param.getValue(), &IndexEntry::GetVariationCount)
    );
    if (param == "n_comments") return std::stable_partition(itB, itE,
        SearchRange<uint>(base, param.getValue(), &IndexEntry::GetCommentCount)
    );
    if (param == "n_nags") return std::stable_partition(itB, itE,
        SearchRange<uint>(base, param.getValue(), &IndexEntry::GetNagCount)
    );
    if (param == "flag") return std::stable_partition(itB, itE,
        SearchFlag(base, param.getValue())
    );
    if (param == "result") return std::stable_partition(itB, itE,
        SearchResult(base, param.getValue())
    );

    param.invalidate();
    return itR;
}

} // End of anonymous namespace


/**
 * search_index() - search for games using game's IndexEntry info
 * @param base:     the scidBaseT to search
 * @param filter:   the filter to be modified with the result of the search
 *                  (RESET, AND, OR operations can be applied to the filter)
 * @param argc:     number of argv elements
 * @param argv:     an array of string pairs <criteria,value>
 * @param progress: report search progress to UI
 *
 * This function perform a fast games search using the IndexEntry info.
 * Criteria should start with the char '-' and can include the optional trailing chars
 *     '!': meaning that we want the games that do _not_ match the <criteria,value> pair
 *     '|': that allows to search for games that match at least one <criteria,value> in
 *          a group of <criteria,value> pairs
 *
 * Names searches (-player, -white, -black, -event, -site -round) have special rules:
 * - normal searches ignore case and spaces, so -player carlsen is equal to -player C a R L s en
 * - player surname and name are usually separated by the char ,
 * - exact searches (that do not ignore case and spaces) can be performed enclosing the searched
 *   value in "" like -player "Carlsen, Magnus"
 *
 * Examples:
 * -player "Carlsen, Magnus"
 * means search for games played by (either as white or black) Carlsen (surname) Magnus (name)
 *
 * -player carlsen -black kramnik
 * means (white name contains 'carlsen' || black name contains 'carlsen') && (black name contains 'kramnik')
 *
 * -white carlsen -black anand -black| kramnik -black| aronian
 * means (white == carlsen) && (black == anand || black == kramnik || black == aronian)
 * and will find the games played by carlsen as white against anand, or kramnik, or aronian
 *
 * -elo "2700 4000" -event! blitz
 * means elo > 2700 && elo < 4000 && event != blitz
 * and will find the games played by players with elo greater or equal than 2700, excluding the blitz events
 *
 * -welo "2700 4000" -belo|! "0 2700" -delo "-200 200"
 * means (white elo > 2700 && white elo < 4000) || (belo is not in the range 0-2700) && ((welo - belo) > -200 && (welo - belo) < 200)
 */
errorT search_index(const scidBaseT* base, HFilter& filter, int argc,
                    const char** argv, const Progress& progress) {
    ASSERT(base != 0);
    ASSERT(filter != 0);

    filterOpT filterOp = FILTEROP_RESET;
    std::vector<SearchParam> params = parseParams(argc, argv, filterOp);
    std::vector<gamenumT> glist = collectGames(filter, filterOp);

    // Partition glist so that the range [glist.begin(), it_res)
    // contains the matching games
    typedef std::vector<gamenumT>::iterator iter;
    iter it_begin = glist.begin();
    iter it_end = glist.end();
    iter it_res = glist.end();
    for (size_t i = 0, n = params.size(); i < n; i++) {
        if (!progress.report(i, n)) return ERROR_UserCancel;

        if (params[i].isOr()) {
            it_begin = it_res;
            // Now the range [it_begin, it_end) include the games
            // that did not matched the previous AND criteria
        } else {
            it_end = it_res;
            it_begin = glist.begin();
            // Now the range [glist.begin(), it_res) include the games
            // that matched all the criteria until now.
            // Nonmatching games are in the range [it_end, glist.end())
            // and excluded from subsequent searches
        }

        it_res = doSearch(it_begin, it_res, it_end, base, params[i]);

        if (params[i].isNot()) {
            // The nonmatching games are in the range [it_res, it_end)
            // Rotate glist so that nonmatching games are in
            // the range [it_begin, it_res)
            std::rotate(it_begin, it_res, it_end);
            it_res = it_begin + (it_end - it_res);
        }
    }

    if (filterOp == FILTEROP_AND) {
        // Remove nonmatching games from @filter
        for (iter it = it_res; it != glist.end(); ++it)
            filter->erase(*it);
    } else {
        // filterOp == FILTEROP_OR
        // Add matching games to @filter
        for (iter it = glist.begin(); it != it_res; ++it)
            filter->set(*it, 1);
    }
    progress.report(1,1);

    return OK;
}