Крисс-кросс, этюды для программистов

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <memory>
#include <set>
#include <list>
#include <algorithm>
 
using std::string;
using std::pair;
using std::vector;
using std::ref;
template <typename T>
using ref_t = std::reference_wrapper<T>;
template <typename T>
using cref_t = std::reference_wrapper<const T>;
 
// универсальный hash дл¤ pair
struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const {
        return (std::hash<T1>()(pair.first) + std::hash<T2>()(pair.second)) ^ std::hash<T2>()(pair.second);
    }
};
 
// это просто Data класс, он хранит только данные, и не ¤вл¤етс¤ самосто¤тельной единицей.
// поэтому нет инкапсул¤ции полей.
struct CWord{
    CWord(const string &word):word{word}{
    }
    enum class Dir{Hor, Vert};
    struct CWordLink{
        CWordLink(CWord &cword, int pos):cword{cword}, pos{pos}{
        }
        bool operator==(const CWordLink &rhs){
            return (pos == rhs.pos) && (&cword.get() == &rhs.cword.get());
        }
        ref_t<CWord> cword; // ссыкла на cross - слово
        int pos; // номер буквы пересечени¤ с данным словом
    };
    int x{},y{}; // начало слова
    Dir dir{}; // ориентаци¤
    short pn{}; // ѕ/Ќ - пор¤дковый номер // если нужно
    cref_t<string> word; // слово
    std::map<int, CWordLink> links; // число - позици¤ буквы пересечени¤, с кемой буквой
    // danger !!!
    bool Linked() const{
        return links.size()!=0;
    }
    bool Link(int pos, CWord& to, int pos_to){
        if (pos < word.get().size() && pos_to < to.word.get().size()){
            links.emplace(pos, CWordLink(to, pos_to));
            return true;
        }
        return false;
    }
    void break_links(){
        for(auto& [pos, link] : links)
            link.cword.get().links.erase(pos);
        links.clear();
    }
};
 
// сетка (виртуальна¤), отвечает за расположение в ней слов.
// правила их расстановок, отступы , правила пересечений и т.д
struct Grid{
    using cells_t = std::map<pair<int,int>, vector<CWord::CWordLink>>;
    //using available_cells_t = std::unordered_map<pair<int,int>, CWord::CWordLink, pair_hash>;
    using available_cells_t = std::map<pair<int,int>, CWord::CWordLink>;
    using available_queued_cells_t = std::list<CWord::CWordLink>;   
    // максимальна¤ ширина и высота пол¤.
    // -1 - резинова¤
//      Grid(int max_width=-1, int max_height=-1)
         Grid()
      :width{0}, height{0}{
    }
    // одна из самых важных функций-членов Cетки
    // с отступами между словами
    bool CanBurn(const CWord & cword){
        if (cword.word.get().empty())
            return false;
        int dx = (cword.dir == CWord::Dir::Hor );
        int dy = (cword.dir == CWord::Dir::Vert);
        int x = cword.x, y = cword.y;
        auto cells_end = cells.end();
        for (int i = 0, end = cword.word.get().size(); i != end ; ++i){
            auto search = cells.find({x, y});
 
            if (search != cells_end){
                const auto& links = search->second;
                if (links.size()==2)
                    return false;
                else if ( links.size()==1){
                        if ( links[0].cword.get().word.get()[links[0].pos] != cword.word.get()[i]) 
                            return false;
                }
            }else{
                // проверка прилегаемости
                switch(cword.dir){
                    case CWord::Dir::Hor  : 
                        if (cells.find({x, y-1}) != cells_end || cells.find({x, y+1}) != cells_end)
                            return false;
                        break;
                    case CWord::Dir::Vert : 
                        if (cells.find({x-1, y}) != cells_end || cells.find({x+1, y}) != cells_end)
                            return false;
                        break;
                    default : break;
                }
            }
            x+=dx, y+=dy;
        }
        return true;
    }
    // прожиг слова на —етке
    bool Burn(CWord &cword){
        if (!CanBurn(cword))
            return false;
 
        int dx = (cword.dir == CWord::Dir::Hor );
        int dy = (cword.dir == CWord::Dir::Vert);
        int x = cword.x, y = cword.y;
        top_left_x = std::min(top_left_x, x);
        top_left_y = std::min(top_left_y, y);
        bottom_right_x = std::max(bottom_right_x, x + dx * int(cword.word.get().size()-1));
        bottom_right_y = std::max(bottom_right_y, y + dy * int(cword.word.get().size()-1));
 
        for (int i = 0, end = cword.word.get().size(); i != end ; ++i){
            cells_t::mapped_type & links = cells[{x,y}];
            links.emplace_back(cword, i);
            if (links.size()==1){
                available_cells.emplace(std::make_pair(x,y), CWord::CWordLink(cword, i) );
                available_queued_cells.push_back(CWord::CWordLink(cword, i));
            }
            else{
                available_queued_cells.erase(std::find(available_queued_cells.begin(), available_queued_cells.end(),
                    CWord::CWordLink(links[0].cword,links[0].pos))
                );
                cword.Link(i, links[0].cword, links[0].pos);
                available_cells.erase(std::make_pair(x,y));
                
            }
            x+=dx; y+=dy;
        }
        return true;
    }
    
    bool Excision (const CWord &cword);
    
    vector<string> MakeRows(){
        if (cells.size()!=0){
            int w = GetWidth();
            int h = GetHeight();
            vector<string> rows(h, string(w, ' '));
            for(auto& cell : cells){
                rows[cell.first.second - top_left_y][cell.first.first - top_left_x] = cell.second[0].cword.get().word.get()[cell.second[0].pos];
            }
            return rows;
        }
        return {};
    }
    
    int GetWidth() const{
        return bottom_right_x - top_left_x + 1;
    }
    int GetHeight() const{
        return bottom_right_y - top_left_y + 1;
    }
    const cells_t& Cells() const{
        return cells;
    }
    const available_cells_t& AvailableCells() const{
        return available_cells;
    }
    const available_queued_cells_t& AvailableQueuedCells() const{
        return available_queued_cells;
    }
private:
    // карта клеток, можно определить к какому слову/словам относитс¤ клетка
    cells_t cells;
    available_cells_t available_cells;
    available_queued_cells_t available_queued_cells;
    // bounds
    int top_left_x{0}, top_left_y{0};
    int bottom_right_x{0}, bottom_right_y{0};
    
    int width;  // текуща¤ ширина
    int height; // текуща¤ высота
    int max_width;
    int max_hegiht;
};
 
// главный класс, хран¤щий слова, св¤зи между ними и сетку дл¤ слов.
template <typename TGrid>
class CrossWord{
    //std::unique_ptr<TGrid> grid;  // сетка
    TGrid grid;
    std::set<string> words; // сами слова
    std::list<CWord> cwords; // crossed words
    std::map<pair<int, int>, ref_t<CWord>> table; // таблица cross-слов
    int horizontal_words = 0;
    int vertical_words = 0;
public:
    CrossWord(const CrossWord &) = delete;
    CrossWord(CrossWord&&) = delete;
    CrossWord& operator=(const CrossWord&) = delete;
    CrossWord& operator=(CrossWord&&) = delete;
    CrossWord() = default;
    ~CrossWord() = default;
    
    bool AddWord(const string &word){
        //const auto &cells  = grid.Cells();
        //const auto &acells = grid.AvailableCells();
        if (words.size() == 0){
            auto inserted_word = words.insert(word);
            if (inserted_word.second == false)
                return false;
            cwords.emplace_back(*(inserted_word.first));
            auto& cword = cwords.back();
            cword.dir = CWord::Dir::Hor;
            if (grid.Burn(cword)){
                cword.pn = ++horizontal_words;
                table.emplace(std::make_pair(cword.pn, 0), cword); 
                return true;
            }
            words.erase(inserted_word.first);
            cwords.pop_back();
            return false;
        }
        const auto &acells = grid.AvailableQueuedCells();
        if (acells.size() == 0)
            return false;
        
        auto inserted_word = words.insert(word);
        if (inserted_word.second == false)
            return false;
        cwords.emplace_back(*(inserted_word.first));
        auto& cword = cwords.back();
 
        for(const auto& wordlink : acells){
            for(int i = 0, end = word.size(); i != end; ++i){
                auto dir = wordlink.cword.get().dir;
                auto coord = std::make_pair(wordlink.cword.get().x + (dir == CWord::Dir::Hor)  * wordlink.pos ,
                                            wordlink.cword.get().y + (dir == CWord::Dir::Vert) * wordlink.pos);
                if (word[i] != wordlink.cword.get().word.get()[wordlink.pos])
                    continue;
                cword.x = coord.first  - (dir == CWord::Dir::Vert ? i : 0);
                cword.y = coord.second - (dir == CWord::Dir::Hor  ? i : 0);
                cword.dir = (dir == CWord::Dir::Hor ? CWord::Dir::Vert : CWord::Dir::Hor);
                if (grid.Burn(cword)){
                    if (cword.dir == CWord::Dir::Hor){
                        cword.pn = ++horizontal_words;
                        table.emplace(std::make_pair(cword.pn, 0), cword);
                    }
                    if (cword.dir == CWord::Dir::Vert){
                        cword.pn = ++vertical_words;
                        table.emplace(std::make_pair(0, cword.pn), cword);
                    }
                    return true;
                }
                
            }
        }
        words.erase(inserted_word.first);
        cwords.pop_back();
        return false;
    }
    
    vector<string> MakeCrossField(){
        return grid.MakeRows();
    };
};
 
int main(){
    CrossWord<Grid> cross;
    vector<string> words{
        "universe", "colonist", "planet", "space", "galaxy",
        "meteorite", "cosmonaut", "telescope",
    };
    for (const auto& w : words)
        std::cout << "Add word \"" << w << "\" - " 
                  << (cross.AddWord(w) ? "success" : "fail") << std::endl;
    auto cw_paper{cross.MakeCrossField()};
    for(const auto& line : cw_paper)
       std::cout << line << std::endl;
}