My Project
container.h
Go to the documentation of this file.
1/* carray.h
2 */
3#ifndef OSL_CONTAINER_H
4#define OSL_CONTAINER_H
5#include "osl/basic_type.h"
6#include "osl/config.h"
8#include <algorithm>
9#include <cstddef>
10#include <cassert>
11#include <array>
12#include <type_traits>
13
14#define CONSERVATIVE_PLAYER_ACCESS
15
16namespace osl
17{
18 template <typename T, size_t Capacity>
19 class CArray
20 {
21 public:
22 std::array<T,Capacity> array;
23 typedef typename std::remove_cv<T>::type T_simple;
24
25 T& operator[] (size_t i) {
26 assert(i < Capacity);
27 return array[i];
28 }
29 T const& operator[] (size_t i) const {
30 assert(i < Capacity);
31 return array[i];
32 }
33
35 assert(1 < Capacity);
36#ifndef CONSERVATIVE_PLAYER_ACCESS
37 // equivalent to operator[](playerToIndex(p))
38 return *((T*)((char *)&elements[0] +
39 (p & ((char *)&elements[1]-(char *)&elements[0]))));
40#else
41 return operator[](playerToIndex(p));
42#endif
43 }
44 const T& operator[] (Player p) const {
45 assert(1 < Capacity);
46#ifndef CONSERVATIVE_PLAYER_ACCESS
47 return *((T*)((char *)&elements[0] +
48 (p & ((char *)&elements[1]-(char *)&elements[0]))));
49#else
50 return operator[](playerToIndex(p));
51#endif
52 }
53 T& operator[] (PtypeO ptypeo) {
54 assert(PTYPEO_SIZE <= (int)Capacity);
55 return operator[](ptypeOIndex(ptypeo));
56 }
57 const T& operator[] (PtypeO ptypeo) const {
58 assert(PTYPEO_SIZE <= (int)Capacity);
59 return operator[](ptypeOIndex(ptypeo));
60 }
61
62 typedef T value_type;
63 typedef typename std::array<T,Capacity>::iterator iterator;
64 iterator begin() { return array.begin(); }
65 iterator end() { return array.end(); }
66
67 void fill(const T_simple& value=T_simple()) {
68 array.fill(value);
69 }
70 // for nested CArray
71 template <class T2, class = typename std::enable_if<!std::is_convertible<T2,T_simple>::value>::type>
72 void fill(const T2& value=T2()) {
73 for (auto& a:array)
74 a.fill(value);
75 }
76 static size_t size() { return Capacity; }
77 typedef typename std::array<T,Capacity>::const_iterator const_iterator;
78 const_iterator begin() const { return array.begin(); }
79 const_iterator end() const { return array.end(); }
80 const_iterator cbegin() const { return array.cbegin(); }
81 const_iterator cend() const { return array.cend(); }
82
83 bool operator==(const CArray& other) const {
84 return array == other.array;
85 }
86
87 T& front() { return array.front(); }
88 T& back() { return array.back(); }
89 const T& front() const { return array.front(); }
90 const T& back() const { return array.back(); }
91 };
92
93
94 template <typename T, size_t Capacity1, size_t Capacity2>
96
97 template <typename T, size_t Capacity1, size_t Capacity2, size_t Capacity3>
99
100 namespace detail
101 {
102 template <typename T>
104 {
105 T *ptr;
106 T **vPtr;
107#if ! (defined NDEBUG && defined MINIMAL)
109#endif
110 public:
111 FixedCapacityVectorPushBack(T** vPtr_, T* limit_)
112 : ptr(*vPtr_), vPtr(vPtr_)
113#if ! (defined NDEBUG && defined MINIMAL)
114 ,limit(limit_)
115#endif
116 {
117 }
119 assert( *vPtr == ptr );
120 *vPtr = ptr;
121 }
122 void push_back(const T& e) {
123 assert(ptr < limit);
124 assert( *vPtr == ptr );
126 *ptr++ = e;
127 else
128 misc::construct(ptr++,e);
129#ifndef NDEBUG
130 (*vPtr)++;
131#endif
132 }
133 };
134 } // namespace deteail
135 template <typename T, size_t Capacity>
137 {
138 protected:
139 struct Array : public CArray<T, Capacity> {}
140#ifdef __GNUC__
141 __attribute__((__may_alias__))
142#endif
143 ;
144 typedef Array array_t;
145 T* ptr;
146 CArray<int64_t, (sizeof(T[Capacity])+sizeof(int64_t)-1)/sizeof(int64_t)> relements;
147 private:
148 const array_t &elements() const {
149 return *reinterpret_cast<const array_t*>(&relements);
150 }
152 return *reinterpret_cast<array_t*>(&relements);
153 }
154 public:
156 typedef typename array_t::iterator iterator;
158
160 explicit FixedCapacityVector(size_t size) : ptr(&(elements()[0])) {
161 resize(size);
162 }
164 ptr= &*begin()+rhs.size();
165 std::uninitialized_copy(rhs.begin(),rhs.end(),begin());
166 }
167 template <class RangeIterator>
168 FixedCapacityVector(const RangeIterator& first, const RangeIterator& last)
169 : ptr(&(elements()[0])) {
170 push_back(first, last);
171 }
176 if (this == &rhs)
177 return *this;
178
179 if(size()>rhs.size()) {
180 iterator it=std::copy(rhs.begin(),rhs.end(),begin());
181 misc::destroy(it,end());
182 }
183 else {
184 iterator it=std::copy(&(rhs.elements()[0]),
185 &(rhs.elements()[0])+size(),begin());
186 std::uninitialized_copy(&(rhs.elements()[0])+size(),
187 &(rhs.elements()[0])+rhs.size(),it);
188 }
189 ptr= &*begin()+rhs.size();
190 return *this;
191 }
192
193 T& operator[] (size_t i) {
194 assert(i <= size());
195 return elements()[i];
196 }
197
198 iterator begin() { return &elements()[0]; }
199 iterator end() { return static_cast<iterator>(ptr); }
200
201 T& front() { return *begin(); }
202 T& back() { return *(end() - 1); }
203
204 void push_back(const T& e) {
205 assert(size() < Capacity);
207 ++ptr;
208 }
209 template <class RangeIterator>
210 void push_back(const RangeIterator& first, const RangeIterator& last);
211 void pop_back() {
212 --ptr;
214 }
215 void clear() {
216 size_t s=size();
217 ptr= &(elements()[0]);
218 // 該当する部分のdestructorを呼ぶ
219 misc::destroy(begin(),begin()+(int)s);
220 }
221 void resize(size_t new_length) {
222 while (size() < new_length)
223 push_back(T());
224 if (new_length < size()) {
225 misc::destroy(begin()+(int)new_length,end());
226 ptr= &(elements()[new_length]);
227 }
228 }
229 void erase(const T& e) {
230 const iterator new_end = std::remove(begin(), end(), e);
231 ptr= &*new_end;
232 misc::destroy(new_end,end());
233 }
234
236 void unique() {
237 std::sort(begin(),end());
238 iterator last = std::unique(begin(), end());
239 ptr = &*last;
240 misc::destroy(last,end());
241 }
242
243 size_t size() const { return ptr-&*begin(); }
244 bool empty() const { return ptr==&*begin(); }
245 size_t capacity() const { return Capacity; }
246
247 T const& operator[] (size_t i) const {
248 assert(i < size());
249 return elements()[i];
250 }
251 const_iterator begin() const { return &elements()[0]; }
252 const_iterator end() const { return ptr; }
253
254 const T& front() const { return *begin(); }
255 const T& back() const { return *(end() - 1); }
256
257 bool isMember(const T& e, const_iterator first, const_iterator last) const {
258 return std::find(first, last, e) != last;
259 }
260 bool isMember(const T& e) const {
261 return isMember(e, begin(), end());
262 }
264 return {&ptr, &*begin()+Capacity};
265 }
266 };
267 template <typename T, size_t C> inline
269 {
270 return l.size() == r.size() && std::equal(l.begin(), l.end(), r.begin());
271 }
272 template <typename T, size_t C> inline
274 {
275 return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end());
276 }
277 using detail::FixedCapacityVectorPushBack;
278} // namespace osl
279
280template <typename T, size_t Capacity>
281template <class RangeIterator>
282void osl::FixedCapacityVector<T,Capacity>::push_back(const RangeIterator& first, const RangeIterator& last)
283{
284 iterator insert_point = end();
285 std::uninitialized_copy(first, last, insert_point);
286 ptr += last-first;
287 assert(size() <= Capacity);
288}
289
290namespace osl
291{
292 class MoveVector : public FixedCapacityVector<Move,Move::MaxUniqMoves>
293 {
294 public:
295 };
296 std::ostream& operator<<(std::ostream& os,MoveVector const& mv);
297 bool operator<(const MoveVector& l, const MoveVector& r);
298
300 class CheckMoveVector : public FixedCapacityVector<Move,CheckOrEscapeMaxUniqMoves>
301 {
302 };
303
304 class PieceVector : public FixedCapacityVector<Piece,Piece::SIZE>
305 {
306 public:
311 void sortByBasic();
316 void sortByPtype();
317 };
318 std::ostream& operator<<(std::ostream& os,const PieceVector&);
319
321 : public FixedCapacityVector<std::pair<PtypeO,Square>,Piece::SIZE>
322 {
323 public:
327 void sort();
328
330 };
331}
332
333#endif /* OSL_CONTAINER_H */
334// ;;; Local Variables:
335// ;;; mode:c++
336// ;;; c-basic-offset:2
337// ;;; End:
void fill(const T_simple &value=T_simple())
Definition container.h:67
const T & front() const
Definition container.h:89
static size_t size()
Definition container.h:76
iterator end()
Definition container.h:65
std::array< T, Capacity >::const_iterator const_iterator
Definition container.h:77
T & operator[](size_t i)
Definition container.h:25
std::array< T, Capacity > array
Definition container.h:22
std::array< T, Capacity >::iterator iterator
Definition container.h:63
const_iterator cbegin() const
Definition container.h:80
T & front()
Definition container.h:87
const T & back() const
Definition container.h:90
void fill(const T2 &value=T2())
Definition container.h:72
const_iterator cend() const
Definition container.h:81
bool operator==(const CArray &other) const
Definition container.h:83
const_iterator end() const
Definition container.h:79
std::remove_cv< T >::type T_simple
Definition container.h:23
T & back()
Definition container.h:88
const_iterator begin() const
Definition container.h:78
iterator begin()
Definition container.h:64
size_t size() const
Definition container.h:243
const T & back() const
Definition container.h:255
const array_t & elements() const
Definition container.h:148
T & operator[](size_t i)
Definition container.h:193
bool isMember(const T &e) const
Definition container.h:260
void unique()
重複する要素を取り除く
Definition container.h:236
const T & front() const
Definition container.h:254
const_iterator begin() const
Definition container.h:251
FixedCapacityVector(size_t size)
Definition container.h:160
void push_back(const T &e)
Definition container.h:204
array_t::value_type value_type
Definition container.h:155
const_iterator end() const
Definition container.h:252
FixedCapacityVector & operator=(FixedCapacityVector const &rhs)
Definition container.h:175
array_t::iterator iterator
Definition container.h:156
FixedCapacityVector(FixedCapacityVector const &rhs)
Definition container.h:163
void resize(size_t new_length)
Definition container.h:221
bool isMember(const T &e, const_iterator first, const_iterator last) const
Definition container.h:257
void push_back(const RangeIterator &first, const RangeIterator &last)
Definition container.h:282
size_t capacity() const
Definition container.h:245
array_t::const_iterator const_iterator
Definition container.h:157
detail::FixedCapacityVectorPushBack< T > pushBackHelper()
Definition container.h:263
void erase(const T &e)
Definition container.h:229
FixedCapacityVector(const RangeIterator &first, const RangeIterator &last)
Definition container.h:168
CArray< int64_t,(sizeof(T[Capacity])+sizeof(int64_t) -1)/sizeof(int64_t)> relements
Definition container.h:146
static const unsigned int MaxUniqMoves
一局面辺りの合法手の最大値 重複して手を生成することがある場合は,600では不足かもしれない
void sortByPtype()
駒の価値の大きい順に並び替える.
Definition container.cc:46
void sortByBasic()
駒の価値の小さい順に並び替える.
Definition container.cc:41
void sort()
駒の価値の小さい順に並び替える
Definition container.cc:74
FixedCapacityVectorPushBack(T **vPtr_, T *limit_)
Definition container.h:111
void construct(T1 *ptr, const T2 &value, typename boost::enable_if< detail::BitCopyTraits< T1 > >::type *=0)
Definition construct.h:40
void destroy(T *ptr)
Definition construct.h:57
const int PTYPEO_SIZE
Definition basic_type.h:308
constexpr int playerToIndex(Player player)
Definition basic_type.h:16
bool operator<(Offset l, Offset r)
Definition basic_type.h:520
unsigned int ptypeOIndex(PtypeO ptypeo)
Definition basic_type.h:205
Player
Definition basic_type.h:8
const PtypeO PTYPEO_EDGE __attribute__((unused))
@ CheckOrEscapeMaxUniqMoves
Definition container.h:299
PtypeO
Player + Ptype [-15, 15] PtypeO の O は Owner の O.
Definition basic_type.h:199
std::ostream & operator<<(std::ostream &os, Player player)
Definition basic_type.cc:14
bool operator==(Square l, Square r)
Definition basic_type.h:758
use raw memory copy instead of placement new not to test a given pointer is null
Definition construct.h:28