namebase.h

/*
 * Copyright (C) 2014-2017 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/>.
 */
 
#ifndef SCID_NAMEBASE_H
#define SCID_NAMEBASE_H
 
#include "scid/database/game_id.h"
#include "scid/database/index.h"
#include "scid/database/indexentry.h"
#include "scid/database/misc.h"
#include <algorithm>
#include <array>
#include <limits>
#include <map>
#include <memory>
#include <string_view>
#include <vector>
 
namespace scid::database {
 
using nameT = unsigned;
enum {
    NAME_PLAYER,
    NAME_EVENT,
    NAME_SITE,
    NAME_ROUND,
    NUM_NAME_TYPES,
    NAME_INVALID = 99
};
 
class NameBase {
    std::vector<std::unique_ptr<const char[]>> names_[NUM_NAME_TYPES];
    struct idxCmp {
        bool operator()(const char* str1, const char* str2) const {
            // *** Compatibility ***
            // Older code used a custom StrTree class with a peculiar sorting:
            // - the first char was interpreted as an unsigned char;
            // - the remaining part was compared with the function
            // strComapare(),
            //   which converts the chars to ints, and is not consistent with
            //   the standard function strcmp().
            // The old StrTree class did also have unpredictable behaviors when
            // fed with names not sorted according to that criteria, for example
            // it could create Namebase objects with duplicate entries.
            // ***
            if (*str1 == *str2)
                return strCompare(str1, str2) < 0;
 
            return static_cast<uint32_t>(*str1) < static_cast<uint32_t>(*str2);
        }
    };
    std::map<const char*, idNumberT, idxCmp> idx_[NUM_NAME_TYPES];
 
public:
    // Add a name (string) to the NameBase.
    // @param nt:      @e nameT type of the name to add.
    // @param name:    the name to add.
    // @return the ID assigned to @e name.
    idNumberT namebase_add(
        nameT nt, std::string_view name,
        std::map<const char*, idNumberT, idxCmp>::iterator* hint = nullptr) {
        ASSERT(IsValidNameType(nt));
        ASSERT(names_[nt].size() <= std::numeric_limits<idNumberT>::max());
 
        char* alloc = new char[name.size() + 1];
        std::copy_n(name.data(), name.size(), alloc);
        alloc[name.size()] = '\0';
        idNumberT newID = static_cast<idNumberT>(names_[nt].size());
        names_[nt].emplace_back(alloc);
        if (hint) {
            idx_[nt].emplace_hint(*hint, alloc, newID);
        } else {
            idx_[nt].emplace(alloc, newID);
        }
        return newID;
    }
 
    // Return the ID corresponding to @e name.
    // Add the name to the NameBase if it doesn't exists.
    // @param nt:      @e nameT type of the name.
    idNumberT namebase_find_or_add(nameT nt, const char* name) {
        ASSERT(IsValidNameType(nt));
 
        auto& nb = idx_[nt];
        auto it = nb.lower_bound(name);
        if (it != nb.end() && !nb.key_comp()(name, it->first))
            return it->second;
 
        return namebase_add(nt, name, &it);
    }
 
    // Return the number of names stored in the NameBase.
    // @param nt: a valid @e nameT type.
    size_t namebase_size(nameT nt) const {
        ASSERT(IsValidNameType(nt));
 
        return names_[nt].size();
    }
 
    bool insert(const char* name, size_t nameLen, nameT nt, idNumberT id) {
        if (id >= names_[nt].size())
            names_[nt].resize(id + size_t{1});
 
        if (names_[nt][id]) // A name with the same ID already exists
            return false;
 
        char* buf = new char[nameLen + 1];
        std::copy_n(name, nameLen, buf);
        buf[nameLen] = '\0';
        names_[nt][id].reset(buf);
        auto it = idx_[nt].emplace_hint(idx_[nt].end(), buf, id);
        return it->second == id; // Check that the name doesn't already exists
    }
 
    void Clear() { *this = NameBase(); }
 
    std::vector<idNumberT> getFirstMatches(nameT nt, const char* str,
                                           size_t maxMatches) const {
        ASSERT(IsValidNameType(nt) && str != NULL);
 
        std::vector<idNumberT> res;
        size_t len = strlen(str);
        for (auto it = idx_[nt].lower_bound(str);
             it != idx_[nt].end() && res.size() < maxMatches; ++it) {
            const char* s = it->first;
            if (strlen(s) < len || !std::equal(str, str + len, s))
                break;
            res.emplace_back(it->second);
        }
        return res;
    }
 
    const char* GetName(nameT nt, idNumberT id) const {
        ASSERT(IsValidNameType(nt) && id < GetNumNames(nt));
        return names_[nt][id].get();
    }
 
    const decltype(idx_)& getNames() const { return idx_; }
 
    idNumberT GetNumNames(nameT nt) const {
        ASSERT(IsValidNameType(nt));
        return static_cast<idNumberT>(names_[nt].size());
    }
 
    scid::core::errorT FindExactName(nameT nt, const char* str, idNumberT* idPtr) const {
        ASSERT(IsValidNameType(nt) && str != NULL && idPtr != NULL);
 
        auto it = idx_[nt].find(str);
        if (it != idx_[nt].end()) {
            *idPtr = (*it).second;
            return scid::core::OK;
        }
        return scid::core::ERROR_NameNotFound;
    }
 
    std::vector<uint32_t> generateHashMap(nameT nt) const {
        std::vector<uint32_t> res(names_[nt].size());
        std::transform(
            names_[nt].begin(), names_[nt].end(), res.begin(),
            [](auto const& name) { return strStartHash(name.get()); });
        return res;
    }
 
    std::array<std::vector<int>, NUM_NAME_TYPES>
    calcNameFreq(Index const& idx) const {
        std::array<std::vector<int>, NUM_NAME_TYPES> resVec;
        for (nameT n = NAME_PLAYER; n < NUM_NAME_TYPES; n++) {
            resVec[n].resize(GetNumNames(n), 0);
        }
        for (gamenumT i = 0, n = idx.GetNumGames(); i < n; i++) {
            const IndexEntry* ie = idx.GetEntry(i);
            resVec[NAME_PLAYER][ie->GetWhite()] += 1;
            resVec[NAME_PLAYER][ie->GetBlack()] += 1;
            resVec[NAME_EVENT][ie->GetEvent()] += 1;
            resVec[NAME_SITE][ie->GetSite()] += 1;
            resVec[NAME_ROUND][ie->GetRound()] += 1;
        }
        return resVec;
    }
 
    size_t count_invalid_ids(Index const& idx) const {
        size_t n_invalid = 0;
        std::array<size_t, NUM_NAME_TYPES> maxID;
        for (auto n = nameT{}; n < NUM_NAME_TYPES; n++) {
            maxID[n] = GetNumNames(n);
        }
        for (gamenumT i = 0, n = idx.GetNumGames(); i < n; i++) {
            const IndexEntry* ie = idx.GetEntry(i);
            n_invalid += ie->GetWhite() < maxID[NAME_PLAYER] ? 0 : 1;
            n_invalid += ie->GetBlack() < maxID[NAME_PLAYER] ? 0 : 1;
            n_invalid += ie->GetEvent() < maxID[NAME_EVENT] ? 0 : 1;
            n_invalid += ie->GetSite() < maxID[NAME_SITE] ? 0 : 1;
            n_invalid += ie->GetRound() < maxID[NAME_ROUND] ? 0 : 1;
        }
        return n_invalid;
    }
 
    static bool IsValidNameType(nameT nt) { return (nt < NUM_NAME_TYPES); }
 
    static nameT NameTypeFromString(const char* str) {
        if (*str == '\0')
            return NAME_INVALID;
        if (strIsAlphaPrefix(str, "player"))
            return NAME_PLAYER;
        if (strIsAlphaPrefix(str, "event"))
            return NAME_EVENT;
        if (strIsAlphaPrefix(str, "site"))
            return NAME_SITE;
        if (strIsAlphaPrefix(str, "round"))
            return NAME_ROUND;
        if (strIsAlphaPrefix("player", str))
            return NAME_PLAYER;
        if (strIsAlphaPrefix("event", str))
            return NAME_EVENT;
        if (strIsAlphaPrefix("site", str))
            return NAME_SITE;
        if (strIsAlphaPrefix("round", str))
            return NAME_ROUND;
        return NAME_INVALID;
    }
};
 
struct TagRoster {
    const char* event;
    const char* site;
    const char* round;
    const char* white;
    const char* black;
 
    template <typename TEntry>
    static TagRoster make(TEntry const& ie, NameBase const& nb) {
        TagRoster res;
        res.event = nb.GetName(NAME_EVENT, ie.GetEvent());
        res.site = nb.GetName(NAME_SITE, ie.GetSite());
        res.white = nb.GetName(NAME_PLAYER, ie.GetWhite());
        res.black = nb.GetName(NAME_PLAYER, ie.GetBlack());
        res.round = nb.GetName(NAME_ROUND, ie.GetRound());
        return res;
    }
 
    template <typename TEntry, typename Fn>
    auto map(TEntry& dest, Fn getID) const {
        {
            auto [err, id] = getID(NAME_EVENT, event);
            if (err)
                return err;
            dest.SetEvent(id);
        }
        {
            auto [err, id] = getID(NAME_SITE, site);
            if (err)
                return err;
            dest.SetSite(id);
        }
        {
            auto [err, id] = getID(NAME_ROUND, round);
            if (err)
                return err;
            dest.SetRound(id);
        }
        {
            auto [err, id] = getID(NAME_PLAYER, white);
            if (err)
                return err;
            dest.SetWhite(id);
        }
        {
            auto [err, id] = getID(NAME_PLAYER, black);
            if (!err)
                dest.SetBlack(id);
 
            return err;
        }
    }
};
 
 
} // namespace scid::database
#endif // SCID_NAMEBASE_H