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"
7 #include "osl/bits/construct.h"
8 #include <algorithm>
9 #include <cstddef>
10 #include <cassert>
11 #include <array>
12 #include <type_traits>
13 
14 #define CONSERVATIVE_PLAYER_ACCESS
15 
16 namespace 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)
108  T *limit;
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:
155  typedef typename array_t::value_type value_type;
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  }
173  misc::destroy(begin(),end());
174  }
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);
206  misc::construct(ptr,e);
207  ++ptr;
208  }
209  template <class RangeIterator>
210  void push_back(const RangeIterator& first, const RangeIterator& last);
211  void pop_back() {
212  --ptr;
213  misc::destroy(ptr+1);
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 
280 template <typename T, size_t Capacity>
281 template <class RangeIterator>
282 void 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 
290 namespace 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 
329  struct PtypeOSquareLessThan;
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
T & operator[](size_t i)
Definition: container.h:25
const T & front() const
Definition: container.h:89
static size_t size()
Definition: container.h:76
iterator end()
Definition: container.h:65
const T & back() const
Definition: container.h:90
std::array< T, Capacity >::const_iterator const_iterator
Definition: container.h:77
T & back()
Definition: container.h:88
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
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
T & front()
Definition: container.h:87
std::remove_cv< T >::type T_simple
Definition: container.h:23
const_iterator begin() const
Definition: container.h:78
iterator begin()
Definition: container.h:64
size_t size() const
Definition: container.h:243
detail::FixedCapacityVectorPushBack< T > pushBackHelper()
Definition: container.h:263
bool isMember(const T &e) const
Definition: container.h:260
void unique()
重複する要素を取り除く
Definition: container.h:236
const_iterator begin() const
Definition: container.h:251
const T & front() const
Definition: container.h:254
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
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
FixedCapacityVector & operator=(FixedCapacityVector const &rhs)
Definition: container.h:175
const T & back() const
Definition: container.h:255
size_t capacity() const
Definition: container.h:245
const array_t & elements() const
Definition: container.h:148
array_t::const_iterator const_iterator
Definition: container.h:157
void erase(const T &e)
Definition: container.h:229
T & operator[](size_t i)
Definition: container.h:193
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では不足かもしれない
Definition: basic_type.h:1071
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