Line data Source code
1 : /*
2 : # Copyright (C) 2014-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 : #ifndef CONTAINERS_H
20 : #define CONTAINERS_H
21 :
22 : #include "common.h" // for ASSERT
23 : #include <vector>
24 :
25 : /**
26 : * A container useful for implementing a undo-redo behavior.
27 : * @e UNDOMAX: max number of copies to store.
28 : * Typical use:
29 : * store(obj_ptr); // (1)
30 : * modify obj;
31 : * obj_ptr = undo(obj_ptr); // obj_ptr now contains the copy of (1)
32 : */
33 15 : template <class TElem, size_t UNDOMAX> class UndoRedo {
34 : std::vector<TElem*> undo_;
35 : std::vector<TElem*> redo_;
36 :
37 : public:
38 15 : ~UndoRedo() { clear(); }
39 16 : void clear() {
40 16 : clear(undo_);
41 16 : clear(redo_);
42 16 : }
43 19 : size_t undoSize() const { return undo_.size(); }
44 7 : size_t redoSize() const { return redo_.size(); }
45 :
46 : /**
47 : * Stores a copy of an element into the undo queue.
48 : * Deletes all the objects of the redo queue.
49 : * @param current: the element to clone and store.
50 : */
51 12 : void store(TElem* current) {
52 12 : clear(redo_);
53 12 : undo_.push_back(current->clone());
54 12 : if (undo_.size() > UNDOMAX) {
55 1 : delete undo_.front();
56 1 : undo_.erase(undo_.begin());
57 : }
58 12 : }
59 :
60 : /**
61 : * Retrieve the last element from the undo queue.
62 : * @param current: pointer to the current element; it will be stored into
63 : * the redo queue.
64 : * @returns the pointer to the last element of the undo queue (the pointer
65 : * will be removed from the queue). If the queue is empty returns @e current
66 : */
67 15 : TElem* undo(TElem* current) { return doUndoRedo(undo_, redo_, current); }
68 :
69 : /**
70 : * Retrieve the last element from the redo queue.
71 : * @param current: pointer to the current element; it will be stored into
72 : * the undo queue.
73 : * @returns the pointer to the last element of the redo queue (the pointer
74 : * will be removed from the queue). If the queue is empty returns @e current
75 : */
76 4 : TElem* redo(TElem* current) { return doUndoRedo(redo_, undo_, current); }
77 :
78 : private:
79 : // Store current into cont2; remove and return the last element of cont1
80 : template <typename TCont>
81 19 : TElem* doUndoRedo(TCont& cont1, TCont& cont2, TElem* current) {
82 19 : if (cont1.empty())
83 5 : return current;
84 :
85 14 : if (cont2.empty() || cont2.back() != current)
86 14 : cont2.push_back(current);
87 :
88 14 : auto res = cont1.back();
89 14 : cont1.pop_back();
90 14 : return res;
91 : }
92 :
93 44 : template <typename TCont> void clear(TCont& cont) {
94 55 : for (auto& e : cont)
95 11 : delete e;
96 44 : cont.clear();
97 44 : }
98 : };
99 :
100 : /**
101 : * A vector-like container. Not all the elements are stored contiguously like in
102 : * a normal vector, but are allocated in separate chunks so that:
103 : * - growing in size do not move the elements and old references remain valid;
104 : * - very large containers can be created.
105 : * @e CHUNKSHIFT: is the base-2 logarithm of the number of T entries per chunk.
106 : * Total size of a chunk: (2^CHUNKSHIFT)*sizeof(T)
107 : */
108 : template <class T, size_t CHUNKSHIFT> class VectorChunked {
109 : std::vector<T*> chunks_;
110 : size_t size_ = 0;
111 :
112 : static constexpr size_t low_mask = ((1ULL << CHUNKSHIFT) - 1);
113 :
114 : public:
115 85 : VectorChunked() = default;
116 : VectorChunked(const VectorChunked&) = delete;
117 : VectorChunked& operator=(const VectorChunked&) = delete;
118 85 : ~VectorChunked() {
119 113 : for (auto& chunk : chunks_)
120 28 : delete[] chunk;
121 85 : }
122 :
123 1126436 : const T& operator[](size_t idx) const {
124 1126436 : ASSERT(idx < size_);
125 1126436 : return chunks_[idx >> CHUNKSHIFT][idx & low_mask];
126 : }
127 31577 : T& operator[](size_t idx) {
128 31577 : ASSERT(idx < size_);
129 31577 : return chunks_[idx >> CHUNKSHIFT][idx & low_mask];
130 : }
131 :
132 8086 : size_t capacity() const { return chunks_.size() << CHUNKSHIFT; }
133 :
134 : /**
135 : * @returns
136 : * the count of contiguously allocated objects starting at @e pos (included)
137 : */
138 15043 : size_t contiguous(size_t pos) const {
139 15043 : ASSERT(pos < size());
140 15043 : return 1 + (~pos & low_mask);
141 : }
142 :
143 10047 : void push_back(const T& e) {
144 10047 : size_t idx = size_;
145 10047 : resize(size_ + 1);
146 10047 : operator[](idx) = e;
147 10047 : }
148 :
149 18204 : void resize(size_t count) {
150 18204 : size_ = count;
151 18204 : size_t newSize = (count > 0) ? 1 + (count >> CHUNKSHIFT) : 0;
152 18204 : size_t chunksSz = chunks_.size();
153 18204 : if (newSize == chunksSz)
154 18116 : return;
155 :
156 88 : if (newSize > chunksSz) {
157 59 : chunks_.resize(newSize);
158 120 : for (auto i = chunksSz; i < newSize; ++i) {
159 61 : chunks_[i] = new T[1ULL << CHUNKSHIFT];
160 : }
161 : } else {
162 62 : for (auto i = newSize; i < chunksSz; ++i) {
163 33 : delete[] chunks_[i];
164 : }
165 29 : chunks_.resize(newSize);
166 : }
167 : }
168 :
169 37142 : size_t size() const { return size_; }
170 : };
171 :
172 : #endif
|
