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 8776387 : 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 4373367 : void clear() {
75 4373367 : moveData.clear();
76 4373367 : prev = nullptr;
77 4373367 : next = nullptr;
78 4373367 : varChild = nullptr;
79 4373367 : std::fill_n(san, sizeof(san), '\0');
80 4373367 : marker = NO_MARKER;
81 4373367 : numVariations = 0;
82 4373367 : nagCount = 0;
83 4373367 : std::fill_n(nags, sizeof(nags), 0);
84 4373367 : comment.clear();
85 4373367 : }
86 :
87 25479661 : bool startMarker() const { return marker == START_MARKER; }
88 15006515 : 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(prev && move.prev);
119 0 : ASSERT(!startMarker() && !move.startMarker());
120 0 : ASSERT(!endMarker() && !move.endMarker());
121 : // Swap lines
122 0 : auto swap_tmp = move.prev;
123 0 : prev->setNext(&move);
124 0 : swap_tmp->setNext(this);
125 : // Swap children
126 0 : std::swap(varChild, move.varChild);
127 0 : std::swap(numVariations, move.numVariations);
128 0 : auto updateParentLink = [](moveT& parent) {
129 0 : for (auto tmp = parent.varChild; tmp; tmp = tmp->varChild) {
130 0 : tmp->prev = &parent;
131 : }
132 0 : };
133 0 : updateParentLink(*this);
134 0 : updateParentLink(move);
135 0 : }
136 :
137 1443 : const moveT* getPrevMove() const {
138 1443 : if (!startMarker() && !prev->startMarker())
139 1443 : return prev;
140 :
141 0 : auto root = getParent().first;
142 0 : return root ? root->getPrevMove() : nullptr;
143 : }
144 :
145 113367 : std::pair<const moveT*, const moveT*> getParent() const {
146 113367 : const moveT* varStart = this;
147 1787301 : while (!varStart->startMarker()) {
148 836967 : varStart = varStart->prev;
149 : }
150 113367 : return {varStart->prev, varStart};
151 : }
152 :
153 1004525 : std::pair<moveT*, moveT*> getParent() {
154 1004525 : moveT* varStart = this;
155 3522957 : while (!varStart->startMarker()) {
156 1259216 : varStart = varStart->prev;
157 : }
158 1004525 : return {varStart->prev, varStart};
159 : }
160 :
161 1332510 : const moveT* nextMoveInPGN() const {
162 1332510 : if (endMarker()) {
163 113367 : auto parent = getParent();
164 113367 : auto nextVar = parent.second->varChild;
165 305253 : return (nextVar) ? nextVar
166 418620 : : (parent.first) ? parent.first->next : nullptr;
167 : }
168 1219143 : return (startMarker() || !varChild) ? next : varChild;
169 : }
170 :
171 3752106 : void setNext(moveT* move) {
172 3752106 : ASSERT(move);
173 3752106 : this->next = move;
174 3752106 : move->prev = this;
175 3752106 : }
176 :
177 617636 : void insertChild(moveT* varStart, int pos) {
178 617636 : ASSERT(!this->startMarker() && !this->endMarker());
179 617636 : ASSERT(this != varStart);
180 617636 : ASSERT(varStart->startMarker());
181 617636 : auto parent = this;
182 617842 : for (; parent->varChild && pos != 0; --pos) {
183 103 : parent = parent->varChild;
184 : }
185 617636 : varStart->varChild = varStart;
186 617636 : std::swap(parent->varChild, varStart->varChild);
187 :
188 617636 : varStart->prev = this;
189 617636 : ++numVariations;
190 617636 : }
191 :
192 617636 : void appendChild(moveT* varStart) { insertChild(varStart, -1); }
193 :
194 0 : void detachChild(moveT* varStart) {
195 0 : ASSERT(this != varStart);
196 0 : ASSERT(varStart->startMarker());
197 0 : auto parent = this;
198 0 : while (parent->varChild != varStart) {
199 0 : parent = parent->varChild;
200 : }
201 0 : std::swap(parent->varChild, varStart->varChild);
202 0 : --numVariations;
203 0 : };
204 : };
205 :
206 : #endif // SCID_MOVETREE_H
|
