Line data Source code
1 : /*
2 : # Copyright (C) 2016-2018 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 : #ifndef SCID_HFILTER_H
20 : #define SCID_HFILTER_H
21 :
22 : #include "common.h"
23 : #include <algorithm>
24 : #include <iterator>
25 : #include <memory>
26 :
27 : /*
28 : * A database can be searched according to different criteria and the list of
29 : * matching games is stored into a Filter object.
30 : * A value of 0 indicates the game is excluded, or 1-255 indicates
31 : * the game is included, and what position to show when the game
32 : * is loaded: 1 means the start position, 2 means the position after
33 : * Whites first move, etc.
34 : */
35 398 : class Filter {
36 : std::unique_ptr<byte[]> data_; // The actual filter data.
37 : gamenumT size_; // Number of values in filter.
38 : gamenumT nonzero_; // Number of nonzero values in filter.
39 : size_t capacity_; // Number of values allocated for data_.
40 :
41 : public:
42 398 : explicit Filter(gamenumT size)
43 398 : : size_(size), nonzero_(size), capacity_(0) {}
44 :
45 56 : void Init(gamenumT size) {
46 56 : data_ = nullptr;
47 56 : nonzero_ = size_ = size;
48 56 : }
49 :
50 : /// Return a pointer to the allocated data.
51 4 : byte* data() { return data_.get(); }
52 :
53 : /// Return the number of nonzero values in filter.
54 16783 : gamenumT Count() const { return nonzero_; }
55 :
56 : /// Return the number of elements in filter.
57 3851084 : gamenumT Size() const { return size_; }
58 :
59 : /// Changes the number of elements stored.
60 27 : void Resize(gamenumT size) {
61 27 : if (!data_) {
62 22 : nonzero_ = size;
63 5 : } else if (size < size_) {
64 4 : nonzero_ = size - static_cast<gamenumT>(std::count(
65 2 : data_.get(), data_.get() + size, 0));
66 3 : } else if (size > size_) {
67 3 : if (size > capacity_) {
68 2 : auto tmp(std::move(data_));
69 1 : allocate(size);
70 1 : std::copy_n(tmp.get(), size_, data_.get());
71 : }
72 3 : byte val = 0;
73 3 : if (Count() == Size()) {
74 1 : val = 1;
75 1 : nonzero_ = size;
76 : }
77 3 : std::fill(data_.get() + size_, data_.get() + size, val);
78 : }
79 27 : size_ = size;
80 27 : }
81 :
82 : /// Gets the value at index.
83 3844553 : byte Get(gamenumT index) const {
84 3844553 : ASSERT(index < Size());
85 3844553 : return data_ ? data_[index] : 1;
86 : }
87 :
88 : /// Sets the value at index.
89 3385 : void Set(gamenumT index, byte value) {
90 3385 : ASSERT(index < Size());
91 3385 : if (data_) {
92 2770 : if (value == 0) {
93 1663 : if (data_[index] != 0)
94 1466 : --nonzero_;
95 1107 : } else if (data_[index] == 0) {
96 173 : ++nonzero_;
97 : }
98 2770 : data_[index] = value;
99 615 : } else if (value != 1) {
100 203 : allocate(size_);
101 203 : std::fill(data_.get(), data_.get() + size_, 1);
102 203 : data_[index] = value;
103 203 : if (value == 0)
104 98 : --nonzero_;
105 : }
106 3385 : }
107 :
108 : /// Sets all values.
109 42 : void Fill(byte value) {
110 42 : if (value == 1) {
111 20 : data_ = nullptr;
112 20 : nonzero_ = size_;
113 : } else {
114 22 : if (!data_) {
115 9 : allocate(size_);
116 : }
117 22 : std::fill(data_.get(), data_.get() + size_, value);
118 22 : nonzero_ = (value == 0) ? 0 : size_;
119 : }
120 42 : }
121 :
122 : private:
123 213 : void allocate(size_t size) {
124 213 : auto capacity = (size | 63) + 1;
125 213 : data_ = std::make_unique<byte[]>(capacity);
126 213 : capacity_ = capacity;
127 213 : }
128 : };
129 :
130 : /*
131 : * This class abstracts the Filter class providing an interface equivalent to a
132 : * pointer to a std::map<gamenumT, uint8_t> object, where the keys are the
133 : * gamenumT of matching games and the mapped_types are the number of half-moves
134 : * necessary to reach the matching position.
135 : * Searches that use only header informations (player names, dates, ...) match
136 : * at the starting position (0 half-moves).
137 : *
138 : * It is also possible to combine two filters in an efficient and transparent
139 : * way. If a secondary "mask" filter is supplied, the functions get(), size()
140 : * and the const_iterator consider only the games included in both filters.
141 : * Their behavior is equal to:
142 : * using Filter = std::map<gamenumT, uint8_t>;
143 : * Filter tmp_combined;
144 : * std::set_intersection(mask->begin(), mask->end(), main->begin(), main->end(),
145 : * std::inserter(tmp_combined, tmp_combined.end()),
146 : * [](auto& a, auto& b) { return a.first < b.first; });
147 : * return HFilter(&tmp_combined).begin/get/size();
148 : */
149 : class HFilter {
150 : Filter* main_;
151 : const Filter* mask_;
152 :
153 : public:
154 : /**
155 : * class const_iterator - iterator for HFilter objects
156 : *
157 : * This class and the relative functions begin() and end() allow to use
158 : * HFilter objects with STL algorithms and c++11 for-ranged loops.
159 : * For example:
160 : * for (auto& gnum : *hfilter_obj) {}
161 : * is equal to:
162 : * for (gamenumT gnum = 0, gnum < scidBaseT::numGames(); gnum++) {
163 : * if (hfilter_obj->get(gnum) == 0) continue;
164 : * }
165 : */
166 : class const_iterator {
167 : gamenumT gnum_;
168 : gamenumT end_;
169 : const HFilter* hfilter_;
170 : bool inFilter_;
171 :
172 : public:
173 : typedef std::forward_iterator_tag iterator_category;
174 : typedef std::ptrdiff_t difference_type;
175 : typedef gamenumT value_type;
176 : typedef const gamenumT* pointer;
177 : typedef const gamenumT& reference;
178 :
179 1778 : const_iterator(gamenumT gnum, gamenumT end, const HFilter* hfilter,
180 : bool inFilter = true)
181 1778 : : gnum_(gnum), end_(end), hfilter_(hfilter), inFilter_(inFilter) {
182 1778 : ASSERT(hfilter != 0);
183 1778 : if (gnum_ != end_) {
184 825 : bool included = (hfilter_->get(gnum_) != 0);
185 825 : if (included != inFilter_)
186 512 : operator++();
187 : }
188 1778 : }
189 :
190 1067 : reference operator*() const { return gnum_; }
191 :
192 4950 : const_iterator& operator++() {
193 8033 : while (++gnum_ != end_) {
194 4125 : bool included = (hfilter_->get(gnum_) != 0);
195 4125 : if (included == inFilter_)
196 1042 : break;
197 : }
198 1867 : return *this;
199 : }
200 :
201 2196 : bool operator!=(const const_iterator& b) const {
202 2196 : return gnum_ != b.gnum_ || hfilter_ != b.hfilter_;
203 : }
204 438 : bool operator==(const const_iterator& b) const {
205 438 : return !operator!=(b);
206 : }
207 : };
208 :
209 787 : const_iterator begin() const {
210 787 : return const_iterator(0, main_->Size(), this);
211 : }
212 883 : const_iterator end() const {
213 883 : return const_iterator(main_->Size(), main_->Size(), this);
214 : }
215 54 : const_iterator beginInverted() const {
216 54 : return const_iterator(0, main_->Size(), this, false);
217 : }
218 54 : const_iterator endInverted() const {
219 54 : return const_iterator(main_->Size(), main_->Size(), this, false);
220 : }
221 36 : size_t sizeInverted() const { return main_->Size() - size(); }
222 :
223 : public: // Pointer interface
224 17427 : bool operator==(const Filter* b) const { return main_ == b; }
225 27298 : bool operator!=(const Filter* b) const { return main_ != b; }
226 2240 : HFilter* operator->() { return this; }
227 3841742 : const HFilter* operator->() const { return this; }
228 36 : HFilter& operator*() { return *this; }
229 : const HFilter& operator*() const { return *this; }
230 :
231 : public:
232 36713 : explicit HFilter(Filter* main = 0, const Filter* mask = 0)
233 36713 : : main_(main), mask_(mask) {}
234 :
235 19 : void clear() { return main_->Fill(0); }
236 206 : void erase(gamenumT gnum) { return main_->Set(gnum, 0); }
237 179 : void insert_or_assign(gamenumT gnum, uint8_t ply) {
238 179 : return main_->Set(gnum, ply + 1);
239 : }
240 16676 : size_t size() const {
241 16676 : if (mask_ == 0)
242 16310 : return main_->Count();
243 366 : if (main_->Count() == main_->Size())
244 89 : return mask_->Count();
245 277 : const_iterator::difference_type res = std::distance(begin(), end());
246 277 : return static_cast<size_t>(res);
247 : }
248 :
249 : /* Convenience function, behave like:
250 : * for (gamenumT gnum = 0; gnum < scidBaseT::numGames(); gnum++)
251 : * std:map::insert_or_assign(gnum, 0);
252 : */
253 18 : void includeAll() { return main_->Fill(1); }
254 :
255 : /* Convenience function, behave like:
256 : * auto it = std::map::find(gnum);
257 : * if (it == std::map::end()) return 0;
258 : * return 1 + it->second;
259 : */
260 3842004 : byte get(gamenumT gnum) const {
261 3842004 : byte res = main_->Get(gnum);
262 3842004 : if (res != 0 && mask_ != 0)
263 2549 : res = mask_->Get(gnum);
264 :
265 3842004 : return res;
266 : }
267 :
268 : /* Convenience function, behave like:
269 : * if (value == 0)
270 : * erase(gnum);
271 : * else
272 : * insert_or_assign(gnum, value - 1);
273 : */
274 1531 : void set(gamenumT gnum, byte value) { return main_->Set(gnum, value); }
275 : };
276 :
277 : /**
278 : * class HFilterInverted - iterate through games excluded from a filter
279 : *
280 : * This class allow to iterate through games not included in HFilter objects
281 : * using STL algorithms and c++11 for-ranged loops.
282 : * For example:
283 : * for (auto& gnum : HFilterInverted(hfilter_obj)) {}
284 : * is equal to:
285 : * for (gamenumT gnum = 0, gnum < scidBaseT::numGames(); gnum++) {
286 : * if (hfilter_obj->get(gnum) != 0) continue;
287 : * }
288 : */
289 : class HFilterInverted {
290 : const HFilter& hfilter_;
291 :
292 : public:
293 54 : explicit HFilterInverted(const HFilter& hfilter) : hfilter_(hfilter) {
294 54 : ASSERT(hfilter != 0);
295 54 : }
296 36 : HFilter::const_iterator begin() const { return hfilter_.beginInverted(); }
297 36 : HFilter::const_iterator end() const { return hfilter_.endInverted(); }
298 18 : size_t size() const { return hfilter_.sizeInverted(); }
299 : };
300 :
301 : #endif
|
