Scid  4.7.0
containers.h
Go to the documentation of this file.
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 template <class TElem, size_t UNDOMAX> class UndoRedo {
34  std::vector<TElem*> undo_;
35  std::vector<TElem*> redo_;
36 
37 public:
38  ~UndoRedo() { clear(); }
39  void clear() {
40  clear(undo_);
41  clear(redo_);
42  }
43  size_t undoSize() const { return undo_.size(); }
44  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  void store(TElem* current) {
52  clear(redo_);
53  undo_.push_back(current->clone());
54  if (undo_.size() > UNDOMAX) {
55  delete undo_.front();
56  undo_.erase(undo_.begin());
57  }
58  }
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  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  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  TElem* doUndoRedo(TCont& cont1, TCont& cont2, TElem* current) {
82  if (cont1.empty())
83  return current;
84 
85  if (cont2.empty() || cont2.back() != current)
86  cont2.push_back(current);
87 
88  auto res = cont1.back();
89  cont1.pop_back();
90  return res;
91  }
92 
93  template <typename TCont> void clear(TCont& cont) {
94  for (auto& e : cont)
95  delete e;
96  cont.clear();
97  }
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  VectorChunked() = default;
116  VectorChunked(const VectorChunked&) = delete;
117  VectorChunked& operator=(const VectorChunked&) = delete;
119  for (auto& chunk : chunks_)
120  delete[] chunk;
121  }
122 
123  const T& operator[](size_t idx) const {
124  ASSERT(idx < size_);
125  return chunks_[idx >> CHUNKSHIFT][idx & low_mask];
126  }
127  T& operator[](size_t idx) {
128  ASSERT(idx < size_);
129  return chunks_[idx >> CHUNKSHIFT][idx & low_mask];
130  }
131 
132  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  size_t contiguous(size_t pos) const {
139  ASSERT(pos < size());
140  return 1 + (~pos & low_mask);
141  }
142 
143  void push_back(const T& e) {
144  size_t idx = size_;
145  resize(size_ + 1);
146  operator[](idx) = e;
147  }
148 
149  void resize(size_t count) {
150  size_ = count;
151  size_t newSize = (count > 0) ? 1 + (count >> CHUNKSHIFT) : 0;
152  size_t chunksSz = chunks_.size();
153  if (newSize == chunksSz)
154  return;
155 
156  if (newSize > chunksSz) {
157  chunks_.resize(newSize);
158  for (auto i = chunksSz; i < newSize; ++i) {
159  chunks_[i] = new T[1ULL << CHUNKSHIFT];
160  }
161  } else {
162  for (auto i = newSize; i < chunksSz; ++i) {
163  delete[] chunks_[i];
164  }
165  chunks_.resize(newSize);
166  }
167  }
168 
169  size_t size() const { return size_; }
170 };
171 
172 #endif
resizew psize
Definition: board.tcl:602
void resize(size_t count)
Definition: containers.h:149
size_t redoSize() const
Definition: containers.h:44
#define ASSERT(f)
Definition: common.h:59
size_t size() const
Definition: containers.h:169
void store(TElem *current)
Stores a copy of an element into the undo queue.
Definition: containers.h:51
size_t undoSize() const
Definition: containers.h:43
sizew
Definition: board.tcl:574
A vector-like container.
Definition: containers.h:108
~UndoRedo()
Definition: containers.h:38
TElem * redo(TElem *current)
Retrieve the last element from the redo queue.
Definition: containers.h:76
TElem * undo(TElem *current)
Retrieve the last element from the undo queue.
Definition: containers.h:67
size_t contiguous(size_t pos) const
Definition: containers.h:138
T & operator[](size_t idx)
Definition: containers.h:127
void push_back(const T &e)
Definition: containers.h:143
const T & operator[](size_t idx) const
Definition: containers.h:123
size_t capacity() const
Definition: containers.h:132
void clear()
Definition: containers.h:39
A container useful for implementing a undo-redo behavior.
Definition: containers.h:33