LCOV - code coverage report
Current view: top level - src - movetree.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 74 90 82.2 %
Date: 2018-02-05 16:49:44 Functions: 15 19 78.9 %

          Line data    Source code
       1             : /*
       2             :  * Copyright (C) 2017  Fulvio Benini
       3             : 
       4             :  * This file is part of Scid (Shane's Chess Information Database).
       5             :  *
       6             :  * Scid is free software: you can redistribute it and/or modify
       7             :  * it under the terms of the GNU General Public License as published by
       8             :  * the Free Software Foundation.
       9             :  *
      10             :  * Scid is distributed in the hope that it will be useful,
      11             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      12             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      13             :  * GNU General Public License for more details.
      14             :  *
      15             :  * You should have received a copy of the GNU General Public License
      16             :  * along with Scid.  If not, see <http://www.gnu.org/licenses/>.
      17             :  *
      18             :  */
      19             : 
      20             : /** @file
      21             :  * A tree graph of moves representing a game.
      22             :  */
      23             : 
      24             : #ifndef SCID_MOVETREE_H
      25             : #define SCID_MOVETREE_H
      26             : 
      27             : #include "common.h"
      28             : #include "movelist.h"
      29             : #include <string>
      30             : 
      31             : enum markerT : byte { NO_MARKER = 0, START_MARKER = 1, END_MARKER = 2 };
      32             : 
      33             : // MAX_NAGS is the maximum number of NAGs (annotation symbols) a single
      34             : // move can have:
      35             : #define MAX_NAGS 8
      36             : 
      37             : // This class creates a tree graph of moves representing a game.
      38             : //
      39             : // For each node there are two edges: *next* (to the next move) and *varChild*
      40             : // (to an alternative line). For example the graph for the move sequence
      41             : // "1.d4 (1.e4 e5 ( 1...c5)) (1.c4) 1...d5 2.c4" is:
      42             : // clang-format off
      43             : // (START_MARKER, pgn_1) --next-> (d4, pgn_2) --next-> (d5, pgn_10) --next-> (c4, pgn_11) --next-> (END_MARKER, none)
      44             : //                                      |
      45             : //                                      |-child-> (START_MARKER, pgn_3) --next-> (e4, pgn_4) --next-> (e5, pgn_5) --next-> (END_MARKER, none)
      46             : //                                                           |                                             |
      47             : //                                                           |                                             |-child-> (START_MARKER, pgn_6) --next-> (c5, pgn_7) --next-> (END_MARKER, none)
      48             : //                                                           |
      49             : //                                                           |-child-> (START_MARKER, pgn_8) --next-> (c4, pgn_9) --next-> (END_MARKER, none)
      50             : // clang-format on
      51             : // The graph illustrates also that:
      52             : // - each variation starts and ends with two nodes containing a START_MARKER
      53             : //   and a END_MARKER instead of a move. This implies that *next* never points
      54             : //   to a START_MARKER node and *varChild* always point to a START_MARKER.
      55             : // - multiple variations are stored as a list of children. In the example there
      56             : //   are two alternatives to "1.d4": "1.e4" is stored as direct child of "1.d4",
      57             : //   instead "1.c4" is stored as the child of the START_MARKER of "1.e4".
      58             : // - when represented as a PGN string, the moves creates a sequence that can be
      59             : //   counted (each new variation is counted as an additional move). This is used
      60             : //   to specify a location in the game.
      61             : //
      62     8775875 : struct moveT {
      63             :         simpleMoveT moveData; // piece moving, target square etc
      64             :         moveT* prev;
      65             :         moveT* next;
      66             :         moveT* varChild;
      67             :         char san[10];   // SAN representation of move
      68             :         markerT marker; // can be NO_MARKER, START_MARKER or END_MARKER
      69             :         byte numVariations;
      70             :         byte nagCount;
      71             :         byte nags[MAX_NAGS];
      72             :         std::string comment;
      73             : 
      74     4373353 :         void clear() {
      75     4373353 :                 moveData.clear();
      76     4373353 :                 prev = nullptr;
      77     4373353 :                 next = nullptr;
      78     4373353 :                 varChild = nullptr;
      79     4373353 :                 std::fill_n(san, sizeof(san), '\0');
      80     4373353 :                 marker = NO_MARKER;
      81     4373353 :                 numVariations = 0;
      82     4373353 :                 nagCount = 0;
      83     4373353 :                 std::fill_n(nags, sizeof(nags), 0);
      84     4373353 :                 comment.clear();
      85     4373353 :         }
      86             : 
      87    25445281 :         bool startMarker() const { return marker == START_MARKER; }
      88    14990062 :         bool endMarker() const { return marker == END_MARKER; }
      89     1561972 :         bool isNull() const { return moveData.isNullMove(); }
      90             : 
      91             :         template <typename TNew>
      92         147 :         moveT* cloneLine(moveT* parent, TNew newMove) const {
      93         147 :                 const moveT* orig = this;
      94         147 :                 moveT* top = newMove();
      95         147 :                 *top = *orig;
      96         147 :                 top->prev = parent;
      97         147 :                 parent = top;
      98         147 :                 if (orig->varChild) {
      99          15 :                         auto root = parent->startMarker() ? parent->prev : parent;
     100          15 :                         parent->varChild = orig->varChild->cloneLine(root, newMove);
     101             :                 }
     102             : 
     103        3315 :                 while (orig->next) {
     104        1584 :                         orig = orig->next;
     105        1584 :                         auto copy = newMove();
     106        1584 :                         *copy = *orig;
     107        1584 :                         parent->setNext(copy);
     108        1584 :                         parent = copy;
     109        1584 :                         if (orig->varChild) {
     110         129 :                                 auto root = parent->startMarker() ? parent->prev : parent;
     111         129 :                                 parent->varChild = orig->varChild->cloneLine(root, newMove);
     112             :                         }
     113             :                 }
     114         147 :                 return top;
     115             :         }
     116             : 
     117           0 :         void swapLine(moveT& move) {
     118           0 :                 ASSERT(!startMarker() && !move.startMarker());
     119           0 :                 std::swap(*this, move);
     120             :                 // We need to swap back the pointers (but not next)
     121           0 :                 std::swap(prev, move.prev);
     122           0 :                 std::swap(varChild, move.varChild);
     123           0 :                 std::swap(numVariations, move.numVariations);
     124           0 :         }
     125             : 
     126        1445 :         const moveT* getPrevMove() const {
     127        1445 :                 if (!startMarker() && !prev->startMarker())
     128        1443 :                         return prev;
     129             : 
     130           2 :                 auto root = getParent().first;
     131           2 :                 return root ? root->getPrevMove() : nullptr;
     132             :         }
     133             : 
     134      113396 :         std::pair<const moveT*, const moveT*> getParent() const {
     135      113396 :                 const moveT* varStart = this;
     136     1787886 :                 while (!varStart->startMarker()) {
     137      837245 :                         varStart = varStart->prev;
     138             :                 }
     139      113396 :                 return {varStart->prev, varStart};
     140             :         }
     141             : 
     142     1004561 :         std::pair<moveT*, moveT*> getParent() {
     143     1004561 :                 moveT* varStart = this;
     144     3523397 :                 while (!varStart->startMarker()) {
     145     1259418 :                         varStart = varStart->prev;
     146             :                 }
     147     1004561 :                 return {varStart->prev, varStart};
     148             :         }
     149             : 
     150     1332854 :         const moveT* nextMoveInPGN() const {
     151     1332854 :                 if (endMarker()) {
     152      113394 :                         auto parent = getParent();
     153      113394 :                         auto nextVar = parent.second->varChild;
     154      305328 :                         return (nextVar) ? nextVar
     155      418722 :                                          : (parent.first) ? parent.first->next : nullptr;
     156             :                 }
     157     1219460 :                 return (startMarker() || !varChild) ? next : varChild;
     158             :         }
     159             : 
     160     3752099 :         void setNext(moveT* move) {
     161     3752099 :                 this->next = move;
     162     3752099 :                 move->prev = this;
     163     3752099 :         }
     164             : 
     165      617636 :         void insertChild(moveT* varStart, int pos) {
     166      617636 :                 ASSERT(!this->startMarker() && !this->endMarker());
     167      617636 :                 ASSERT(this != varStart);
     168      617636 :                 ASSERT(varStart->startMarker());
     169      617636 :                 auto parent = this;
     170      617842 :                 for (; parent->varChild && pos != 0; --pos) {
     171         103 :                         parent = parent->varChild;
     172             :                 }
     173      617636 :                 varStart->varChild = varStart;
     174      617636 :                 std::swap(parent->varChild, varStart->varChild);
     175             : 
     176      617636 :                 varStart->prev = this;
     177      617636 :                 ++numVariations;
     178      617636 :         }
     179             : 
     180      617636 :         void appendChild(moveT* varStart) { insertChild(varStart, -1); }
     181             : 
     182           0 :         void detachChild(moveT* varStart) {
     183           0 :                 ASSERT(this != varStart);
     184           0 :                 ASSERT(varStart->startMarker());
     185           0 :                 auto parent = this;
     186           0 :                 while (parent->varChild != varStart) {
     187           0 :                         parent = parent->varChild;
     188             :                 }
     189           0 :                 std::swap(parent->varChild, varStart->varChild);
     190           0 :                 --numVariations;
     191           0 :         };
     192             : };
     193             : 
     194             : #endif // SCID_MOVETREE_H

Generated by: LCOV version 1.13