00001
00002
00003 #ifndef OSL_CONTAINER_H
00004 #define OSL_CONTAINER_H
00005 #include "osl/basic_type.h"
00006 #include "osl/config.h"
00007 #include "osl/bits/construct.h"
00008 #include <algorithm>
00009 #include <cstddef>
00010 #include <cassert>
00011 #include <array>
00012 #include <type_traits>
00013
00014 #define CONSERVATIVE_PLAYER_ACCESS
00015
00016 namespace osl
00017 {
00018 template <typename T, size_t Capacity>
00019 class CArray
00020 {
00021 public:
00022 std::array<T,Capacity> array;
00023 typedef typename std::remove_cv<T>::type T_simple;
00024
00025 T& operator[] (size_t i) {
00026 assert(i < Capacity);
00027 return array[i];
00028 }
00029 T const& operator[] (size_t i) const {
00030 assert(i < Capacity);
00031 return array[i];
00032 }
00033
00034 T& operator[] (Player p) {
00035 assert(1 < Capacity);
00036 #ifndef CONSERVATIVE_PLAYER_ACCESS
00037
00038 return *((T*)((char *)&elements[0] +
00039 (p & ((char *)&elements[1]-(char *)&elements[0]))));
00040 #else
00041 return operator[](playerToIndex(p));
00042 #endif
00043 }
00044 const T& operator[] (Player p) const {
00045 assert(1 < Capacity);
00046 #ifndef CONSERVATIVE_PLAYER_ACCESS
00047 return *((T*)((char *)&elements[0] +
00048 (p & ((char *)&elements[1]-(char *)&elements[0]))));
00049 #else
00050 return operator[](playerToIndex(p));
00051 #endif
00052 }
00053 T& operator[] (PtypeO ptypeo) {
00054 assert(PTYPEO_SIZE <= (int)Capacity);
00055 return operator[](ptypeOIndex(ptypeo));
00056 }
00057 const T& operator[] (PtypeO ptypeo) const {
00058 assert(PTYPEO_SIZE <= (int)Capacity);
00059 return operator[](ptypeOIndex(ptypeo));
00060 }
00061
00062 typedef T value_type;
00063 typedef typename std::array<T,Capacity>::iterator iterator;
00064 iterator begin() { return array.begin(); }
00065 iterator end() { return array.end(); }
00066
00067 void fill(const T_simple& value=T_simple()) {
00068 array.fill(value);
00069 }
00070
00071 template <class T2, class = typename std::enable_if<!std::is_convertible<T2,T_simple>::value>::type>
00072 void fill(const T2& value=T2()) {
00073 for (auto& a:array)
00074 a.fill(value);
00075 }
00076 static size_t size() { return Capacity; }
00077 typedef typename std::array<T,Capacity>::const_iterator const_iterator;
00078 const_iterator begin() const { return array.begin(); }
00079 const_iterator end() const { return array.end(); }
00080 const_iterator cbegin() const { return array.cbegin(); }
00081 const_iterator cend() const { return array.cend(); }
00082
00083 bool operator==(const CArray& other) const {
00084 return array == other.array;
00085 }
00086
00087 T& front() { return array.front(); }
00088 T& back() { return array.back(); }
00089 const T& front() const { return array.front(); }
00090 const T& back() const { return array.back(); }
00091 };
00092
00093
00094 template <typename T, size_t Capacity1, size_t Capacity2>
00095 using CArray2d = CArray<CArray<T,Capacity2>,Capacity1>;
00096
00097 template <typename T, size_t Capacity1, size_t Capacity2, size_t Capacity3>
00098 using CArray3d = CArray<CArray2d<T,Capacity2,Capacity3>,Capacity1>;
00099
00100 namespace detail
00101 {
00102 template <typename T>
00103 class FixedCapacityVectorPushBack
00104 {
00105 T *ptr;
00106 T **vPtr;
00107 #if ! (defined NDEBUG && defined MINIMAL)
00108 T *limit;
00109 #endif
00110 public:
00111 FixedCapacityVectorPushBack(T** vPtr_, T* limit_)
00112 : ptr(*vPtr_), vPtr(vPtr_)
00113 #if ! (defined NDEBUG && defined MINIMAL)
00114 ,limit(limit_)
00115 #endif
00116 {
00117 }
00118 ~FixedCapacityVectorPushBack() {
00119 assert( *vPtr == ptr );
00120 *vPtr = ptr;
00121 }
00122 void push_back(const T& e) {
00123 assert(ptr < limit);
00124 assert( *vPtr == ptr );
00125 if(misc::detail::BitCopyTraits<T>::value)
00126 *ptr++ = e;
00127 else
00128 misc::construct(ptr++,e);
00129 #ifndef NDEBUG
00130 (*vPtr)++;
00131 #endif
00132 }
00133 };
00134 }
00135 template <typename T, size_t Capacity>
00136 class FixedCapacityVector
00137 {
00138 protected:
00139 struct Array : public CArray<T, Capacity> {}
00140 #ifdef __GNUC__
00141 __attribute__((__may_alias__))
00142 #endif
00143 ;
00144 typedef Array array_t;
00145 T* ptr;
00146 CArray<int64_t, (sizeof(T[Capacity])+sizeof(int64_t)-1)/sizeof(int64_t)> relements;
00147 private:
00148 const array_t &elements() const {
00149 return *reinterpret_cast<const array_t*>(&relements);
00150 }
00151 array_t &elements() {
00152 return *reinterpret_cast<array_t*>(&relements);
00153 }
00154 public:
00155 typedef typename array_t::value_type value_type;
00156 typedef typename array_t::iterator iterator;
00157 typedef typename array_t::const_iterator const_iterator;
00158
00159 FixedCapacityVector() : ptr(&(elements()[0])) {}
00160 explicit FixedCapacityVector(size_t size) : ptr(&(elements()[0])) {
00161 resize(size);
00162 }
00163 FixedCapacityVector(FixedCapacityVector const& rhs) {
00164 ptr= &*begin()+rhs.size();
00165 std::uninitialized_copy(rhs.begin(),rhs.end(),begin());
00166 }
00167 template <class RangeIterator>
00168 FixedCapacityVector(const RangeIterator& first, const RangeIterator& last)
00169 : ptr(&(elements()[0])) {
00170 push_back(first, last);
00171 }
00172 ~FixedCapacityVector() {
00173 misc::destroy(begin(),end());
00174 }
00175 FixedCapacityVector& operator=(FixedCapacityVector const& rhs) {
00176 if (this == &rhs)
00177 return *this;
00178
00179 if(size()>rhs.size()) {
00180 iterator it=std::copy(rhs.begin(),rhs.end(),begin());
00181 misc::destroy(it,end());
00182 }
00183 else {
00184 iterator it=std::copy(&(rhs.elements()[0]),
00185 &(rhs.elements()[0])+size(),begin());
00186 std::uninitialized_copy(&(rhs.elements()[0])+size(),
00187 &(rhs.elements()[0])+rhs.size(),it);
00188 }
00189 ptr= &*begin()+rhs.size();
00190 return *this;
00191 }
00192
00193 T& operator[] (size_t i) {
00194 assert(i <= size());
00195 return elements()[i];
00196 }
00197
00198 iterator begin() { return &elements()[0]; }
00199 iterator end() { return static_cast<iterator>(ptr); }
00200
00201 T& front() { return *begin(); }
00202 T& back() { return *(end() - 1); }
00203
00204 void push_back(const T& e) {
00205 assert(size() < Capacity);
00206 misc::construct(ptr,e);
00207 ++ptr;
00208 }
00209 template <class RangeIterator>
00210 void push_back(const RangeIterator& first, const RangeIterator& last);
00211 void pop_back() {
00212 --ptr;
00213 misc::destroy(ptr+1);
00214 }
00215 void clear() {
00216 size_t s=size();
00217 ptr= &(elements()[0]);
00218
00219 misc::destroy(begin(),begin()+(int)s);
00220 }
00221 void resize(size_t new_length) {
00222 while (size() < new_length)
00223 push_back(T());
00224 if (new_length < size()) {
00225 misc::destroy(begin()+(int)new_length,end());
00226 ptr= &(elements()[new_length]);
00227 }
00228 }
00229 void erase(const T& e) {
00230 const iterator new_end = std::remove(begin(), end(), e);
00231 ptr= &*new_end;
00232 misc::destroy(new_end,end());
00233 }
00234
00236 void unique() {
00237 std::sort(begin(),end());
00238 iterator last = std::unique(begin(), end());
00239 ptr = &*last;
00240 misc::destroy(last,end());
00241 }
00242
00243 size_t size() const { return ptr-&*begin(); }
00244 bool empty() const { return ptr==&*begin(); }
00245 size_t capacity() const { return Capacity; }
00246
00247 T const& operator[] (size_t i) const {
00248 assert(i < size());
00249 return elements()[i];
00250 }
00251 const_iterator begin() const { return &elements()[0]; }
00252 const_iterator end() const { return ptr; }
00253
00254 const T& front() const { return *begin(); }
00255 const T& back() const { return *(end() - 1); }
00256
00257 bool isMember(const T& e, const_iterator first, const_iterator last) const {
00258 return std::find(first, last, e) != last;
00259 }
00260 bool isMember(const T& e) const {
00261 return isMember(e, begin(), end());
00262 }
00263 detail::FixedCapacityVectorPushBack<T> pushBackHelper() {
00264 return {&ptr, &*begin()+Capacity};
00265 }
00266 };
00267 template <typename T, size_t C> inline
00268 bool operator==(const FixedCapacityVector<T,C>& l, const FixedCapacityVector<T,C>& r)
00269 {
00270 return l.size() == r.size() && std::equal(l.begin(), l.end(), r.begin());
00271 }
00272 template <typename T, size_t C> inline
00273 bool operator<(const FixedCapacityVector<T,C>& l, const FixedCapacityVector<T,C>& r)
00274 {
00275 return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end());
00276 }
00277 using detail::FixedCapacityVectorPushBack;
00278 }
00279
00280 template <typename T, size_t Capacity>
00281 template <class RangeIterator>
00282 void osl::FixedCapacityVector<T,Capacity>::push_back(const RangeIterator& first, const RangeIterator& last)
00283 {
00284 iterator insert_point = end();
00285 std::uninitialized_copy(first, last, insert_point);
00286 ptr += last-first;
00287 assert(size() <= Capacity);
00288 }
00289
00290 namespace osl
00291 {
00292 class MoveVector : public FixedCapacityVector<Move,Move::MaxUniqMoves>
00293 {
00294 public:
00295 };
00296 std::ostream& operator<<(std::ostream& os,MoveVector const& mv);
00297 bool operator<(const MoveVector& l, const MoveVector& r);
00298
00299 enum { CheckOrEscapeMaxUniqMoves = Move::MaxUniqMoves/4 };
00300 class CheckMoveVector : public FixedCapacityVector<Move,CheckOrEscapeMaxUniqMoves>
00301 {
00302 };
00303
00304 class PieceVector : public FixedCapacityVector<Piece,Piece::SIZE>
00305 {
00306 public:
00311 void sortByBasic();
00316 void sortByPtype();
00317 };
00318 std::ostream& operator<<(std::ostream& os,const PieceVector&);
00319
00320 class PtypeOSquareVector
00321 : public FixedCapacityVector<std::pair<PtypeO,Square>,Piece::SIZE>
00322 {
00323 public:
00327 void sort();
00328
00329 struct PtypeOSquareLessThan;
00330 };
00331 }
00332
00333 #endif
00334
00335
00336
00337