1 #ifndef PYTHONIC_INCLUDE_TYPES_LIST_HPP 2 #define PYTHONIC_INCLUDE_TYPES_LIST_HPP 3 4 #include "pythonic/include/types/assignable.hpp" 5 #include "pythonic/include/types/empty_iterator.hpp" 6 #include "pythonic/include/types/nditerator.hpp" 7 #include "pythonic/include/utils/shared_ref.hpp" 8 #include "pythonic/include/utils/nested_container.hpp" 9 #include "pythonic/include/utils/int_.hpp" 10 #include "pythonic/include/utils/reserve.hpp" 11 #include "pythonic/include/types/tuple.hpp" 12 #include "pythonic/include/types/slice.hpp" 13 #include "pythonic/include/types/vectorizable_type.hpp" 14 15 #include <ostream> 16 #include <vector> 17 #include <utility> 18 #include <algorithm> 19 #include <iterator> 20 21 PYTHONIC_NS_BEGIN 22 23 namespace types 24 { 25 template <class T> 26 using container = std::vector<T>; 27 28 static const size_t DEFAULT_LIST_CAPACITY = 16; 29 30 /* forward declaration */ 31 struct empty_list; 32 template <class T> 33 class list; 34 template <class T, class S> 35 class sliced_list; 36 template <class T, class pS> 37 struct ndarray; 38 template <class... Tys> 39 struct pshape; 40 template <class T> 41 struct is_list { 42 static const bool value = false; 43 }; 44 template <class T> 45 struct is_list<list<T>> { 46 static const bool value = true; 47 }; 48 template <class T, class S> 49 struct is_list<sliced_list<T, S>> { 50 static const bool value = true; 51 }; 52 template <class T, size_t N> 53 struct is_list<static_list<T, N>> { 54 static const bool value = true; 55 }; 56 57 /* for type disambiguification */ 58 struct single_value { 59 }; 60 61 /* list view */ 62 template <class T, class S = slice> 63 class sliced_list 64 { 65 66 // data holder 67 typedef 68 typename std::remove_cv<typename std::remove_reference<T>::type>::type 69 _type; 70 typedef container<_type> container_type; 71 utils::shared_ref<container_type> data; 72 73 template <class U> 74 friend class list; 75 76 typename S::normalized_type slicing; 77 78 public: 79 // types 80 typedef typename container_type::reference reference; 81 typedef typename container_type::const_reference const_reference; 82 typedef nditerator<sliced_list> iterator; 83 typedef const_nditerator<sliced_list> const_iterator; 84 typedef typename container_type::size_type size_type; 85 typedef typename container_type::difference_type difference_type; 86 typedef typename container_type::value_type value_type; 87 typedef typename container_type::allocator_type allocator_type; 88 typedef typename container_type::pointer pointer; 89 typedef typename container_type::const_pointer const_pointer; 90 typedef typename container_type::reverse_iterator reverse_iterator; 91 typedef 92 typename container_type::const_reverse_iterator const_reverse_iterator; 93 94 // minimal ndarray interface 95 typedef 96 typename utils::nested_container_value_type<sliced_list>::type dtype; 97 static const size_t value = 98 utils::nested_container_depth<sliced_list>::value; 99 static_assert(value != 0, "valid shape"); 100 static const bool is_vectorizable = 101 types::is_vectorizable_dtype<dtype>::value && 102 !std::is_same<S, slice>::value; 103 static const bool is_strided = std::is_same<slice, S>::value; 104 105 using shape_t = types::array<long, value>; 106 template <size_t I> shape() const107 auto shape() const 108 -> decltype(details::extract_shape(*this, utils::int_<I>{})) 109 { 110 return details::extract_shape(*this, utils::int_<I>{}); 111 } 112 113 // constructor 114 sliced_list(); 115 sliced_list(sliced_list<T, S> const &s); 116 sliced_list(list<T> const &other, S const &s); 117 template <class Sn> 118 sliced_list(utils::shared_ref<container_type> const &other, Sn const &s); 119 120 // assignment 121 sliced_list &operator=(list<T> const &); 122 sliced_list &operator=(sliced_list<T, S> const &); 123 list<T> operator+(list<T> const &) const; 124 template <size_t N, class V> 125 list<T> operator+(array_base<T, N, V> const &) const; 126 template <class Tp, class Sp> 127 list<typename __combined<T, Tp>::type> 128 operator+(sliced_list<Tp, Sp> const &) const; 129 130 // iterators 131 iterator begin(); 132 const_iterator begin() const; 133 iterator end(); 134 const_iterator end() const; 135 136 // size 137 long size() const; 138 explicit operator bool() const; 139 140 // accessors 141 const_reference fast(long i) const; 142 const_reference operator[](long i) const; 143 reference operator[](long i); 144 template <class Sp> 145 typename std::enable_if< 146 is_slice<Sp>::value, 147 sliced_list<T, decltype(std::declval<S>() * std::declval<Sp>())>>::type 148 operator[](Sp s) const; 149 150 template <class... Indices> load(long index0,long index1,Indices...indices) const151 dtype load(long index0, long index1, Indices... indices) const 152 { 153 return fast(index0).load(index1, indices...); 154 } 155 load(long index) const156 dtype load(long index) const 157 { 158 return fast(index); 159 } 160 // comparison 161 template <class K> 162 bool operator==(list<K> const &other) const; 163 bool operator==(empty_list const &other) const; 164 165 #ifdef USE_XSIMD 166 using simd_iterator = const_simd_nditerator<sliced_list>; 167 using simd_iterator_nobroadcast = simd_iterator; 168 template <class vectorizer> 169 simd_iterator vbegin(vectorizer) const; 170 template <class vectorizer> 171 simd_iterator vend(vectorizer) const; 172 #endif 173 174 // other operations 175 template <class V> 176 bool contains(V const &v) const; 177 intptr_t id() const; 178 179 long count(T const &x) const; 180 template <class Tp, class Sp> 181 friend std::ostream &operator<<(std::ostream &os, 182 sliced_list<Tp, Sp> const &v); 183 }; 184 185 /* list */ 186 template <class T> 187 class list 188 { 189 190 // data holder 191 typedef 192 typename std::remove_cv<typename std::remove_reference<T>::type>::type 193 _type; 194 typedef container<_type> container_type; 195 utils::shared_ref<container_type> data; 196 197 template <class U, class S> 198 friend class sliced_list; 199 200 template <class U> 201 friend class list; 202 203 public: 204 // types 205 typedef typename container_type::value_type value_type; 206 typedef typename container_type::reference reference; 207 typedef typename container_type::const_reference const_reference; 208 typedef typename container_type::iterator iterator; 209 typedef typename container_type::const_iterator const_iterator; 210 typedef typename container_type::size_type size_type; 211 typedef typename container_type::difference_type difference_type; 212 typedef typename container_type::allocator_type allocator_type; 213 typedef typename container_type::pointer pointer; 214 typedef typename container_type::const_pointer const_pointer; 215 typedef typename container_type::reverse_iterator reverse_iterator; 216 typedef 217 typename container_type::const_reverse_iterator const_reverse_iterator; 218 219 // minimal ndarray interface 220 typedef typename utils::nested_container_value_type<list>::type dtype; 221 static const size_t value = utils::nested_container_depth<list>::value; 222 static const bool is_vectorizable = types::is_vectorizable<dtype>::value; 223 static const bool is_strided = false; 224 225 // constructors 226 list(); 227 template <class InputIterator> 228 list(InputIterator start, InputIterator stop); 229 list(empty_list const &); 230 list(size_type sz); 231 list(T const &value, single_value, size_type sz = 1); 232 list(std::initializer_list<T> l); 233 list(list<T> &&other); 234 list(list<T> const &other); 235 template <class F> 236 list(list<F> const &other); 237 template <class Tp, class S> 238 list(sliced_list<Tp, S> const &other); 239 template <class Tp, size_t N> list(static_list<Tp,N> const & other)240 list(static_list<Tp, N> const &other) 241 : list(other.begin(), other.end()) 242 { 243 } 244 template <class Tp, size_t N, class... S> list(numpy_gexpr<static_list<Tp,N>,S...> const & other)245 list(numpy_gexpr<static_list<Tp, N>, S...> const &other) 246 : list(other.begin(), other.end()) 247 { 248 } 249 list<T> &operator=(list<T> &&other); 250 template <class F> 251 list<T> &operator=(list<F> const &other); 252 list<T> &operator=(list<T> const &other); 253 list<T> &operator=(empty_list const &); 254 template <class Tp, size_t N, class V> 255 list<T> &operator=(array_base<Tp, N, V> const &); 256 template <class Tp, class S> 257 list<T> &operator=(sliced_list<Tp, S> const &other); 258 259 template <class pS> 260 list & 261 operator=(ndarray<T, pshape<pS>> const &); // implemented in ndarray.hpp 262 263 template <class S> 264 list<T> &operator+=(sliced_list<T, S> const &other); 265 template <class S> 266 list<T> operator+(sliced_list<T, S> const &other) const; 267 template <size_t N, class V> 268 list<T> operator+(array_base<T, N, V> const &other) const; 269 270 // io 271 template <class S> 272 friend std::ostream &operator<<(std::ostream &os, list<S> const &v); 273 274 // comparison 275 template <class K> 276 bool operator==(list<K> const &other) const; 277 bool operator==(empty_list const &) const; 278 template <class K> 279 bool operator!=(list<K> const &other) const; 280 bool operator!=(empty_list const &) const; 281 282 // iterators 283 iterator begin(); 284 const_iterator begin() const; 285 iterator end(); 286 const_iterator end() const; 287 reverse_iterator rbegin(); 288 const_reverse_iterator rbegin() const; 289 reverse_iterator rend(); 290 const_reverse_iterator rend() const; 291 292 // comparison 293 bool operator<(list<T> const &other) const; 294 bool operator<=(list<T> const &other) const; 295 bool operator>(list<T> const &other) const; 296 bool operator>=(list<T> const &other) const; 297 298 // element access 299 #ifdef USE_XSIMD 300 using simd_iterator = const_simd_nditerator<list>; 301 using simd_iterator_nobroadcast = simd_iterator; 302 template <class vectorizer> 303 simd_iterator vbegin(vectorizer) const; 304 template <class vectorizer> 305 simd_iterator vend(vectorizer) const; 306 #endif 307 reference fast(long n); 308 reference operator[](long n); 309 310 const_reference fast(long n) const; 311 const_reference operator[](long n) const; 312 313 template <class Sp> 314 typename std::enable_if<is_slice<Sp>::value, sliced_list<T, Sp>>::type 315 operator[](Sp const &s) const; 316 317 template <class... Indices> load(long index0,long index1,Indices...indices) const318 dtype load(long index0, long index1, Indices... indices) const 319 { 320 return fast(index0).load(index1, indices...); 321 } 322 load(long index) const323 dtype load(long index) const 324 { 325 return fast(index); 326 } 327 328 // modifiers 329 template <class Tp> 330 void push_back(Tp &&x); 331 template <class Tp> 332 void insert(long i, Tp &&x); 333 334 void reserve(size_t n); 335 void resize(size_t n); 336 iterator erase(size_t n); 337 338 T pop(long x = -1); 339 340 // TODO: have to raise a valueError 341 none_type remove(T const &x); 342 343 // Misc 344 // TODO: have to raise a valueError 345 long index(T const &x) const; 346 347 // list interface 348 explicit operator bool() const; 349 350 template <class F> 351 list<typename __combined<T, F>::type> operator+(list<F> const &s) const; 352 353 template <class F, class S> 354 list<decltype(std::declval<T>() + 355 std::declval<typename sliced_list<F, S>::value_type>())> 356 operator+(sliced_list<F, S> const &s) const; 357 358 list<T> operator+(empty_list const &) const; 359 list<T> operator*(long t) const; 360 list<T> const &operator*=(long t); 361 362 template <class F> 363 list<T> &operator+=(F const &s); 364 365 long size() const; 366 template <class E> 367 long _flat_size(E const &e, utils::int_<1>) const; 368 template <class E, size_t L> 369 long _flat_size(E const &e, utils::int_<L>) const; 370 long flat_size() const; 371 372 template <class V> 373 bool contains(V const &v) const; 374 intptr_t id() const; 375 376 long count(T const &x) const; 377 using shape_t = array<long, value>; 378 template <size_t I> shape() const379 long shape() const 380 { 381 if (I == 0) 382 return size(); 383 else 384 return details::extract_shape(*this, utils::int_<I>{}); 385 } 386 387 template <class Tp, size_t N, class V> operator array_base<Tp,N,V>() const388 operator array_base<Tp, N, V>() const 389 { 390 assert(size() == N && "consistent size"); 391 array_base<Tp, N, V> res; 392 std::copy(begin(), end(), res.begin()); 393 return res; 394 } 395 }; 396 397 template <class T, size_t N> operator *(static_list<T,N> const & self,long t)398 list<T> operator*(static_list<T, N> const &self, long t) 399 { 400 list<T> res(self); 401 res *= t; 402 return res; 403 } 404 template <class T, size_t N> operator *(long t,static_list<T,N> const & self)405 list<T> operator*(long t, static_list<T, N> const &self) 406 { 407 return self * t; 408 } 409 410 template <class T0, size_t N, class T1> 411 list<typename __combined<T0, T1>::type> operator +(static_list<T0,N> const & l0,list<T1> const & l1)412 operator+(static_list<T0, N> const &l0, list<T1> const &l1) 413 { 414 list<typename __combined<T0, T1>::type> out(l0.begin(), l0.end()); 415 return out += l1; 416 } 417 418 /* empty list implementation */ 419 struct empty_list { 420 // minimal ndarray interface 421 typedef char dtype; 422 static const size_t value = 1; 423 static const bool is_vectorizable = false; 424 static const bool is_strided = false; 425 using shape_t = types::array<long, value>; 426 typedef char value_type; 427 428 typedef empty_iterator iterator; 429 typedef empty_iterator const_iterator; 430 #ifdef USE_XSIMD 431 typedef empty_iterator simd_iterator; 432 typedef empty_iterator simd_iterator_nobroadcast; 433 #endif 434 template <class T> 435 list<T> operator+(list<T> const &s) const; 436 template <class T, class S> 437 sliced_list<T, S> operator+(sliced_list<T, S> const &s) const; 438 template <class T, size_t N, class V> 439 static_list<T, N> operator+(array_base<T, N, V> const &s) const; 440 empty_list operator+(empty_list const &) const; 441 template <class F> 442 typename std::enable_if<!is_numexpr_arg<F>::value, 443 list<typename F::value_type>>::type 444 operator+(F s) const; 445 explicit operator bool() const; 446 template <class T> 447 operator list<T>() const; 448 static constexpr long size(); 449 450 template <size_t I> shapetypes::empty_list451 std::integral_constant<long, 0> shape() const 452 { 453 return {}; 454 } 455 fasttypes::empty_list456 char fast(long) const 457 { 458 return {}; 459 } operator []types::empty_list460 char operator[](long) const 461 { 462 return {}; 463 } 464 template <class S> 465 typename std::enable_if<is_slice<S>::value, empty_list>::type operator []types::empty_list466 operator[](S) const 467 { 468 return {}; 469 } 470 begintypes::empty_list471 empty_iterator begin() const 472 { 473 return {}; 474 } endtypes::empty_list475 empty_iterator end() const 476 { 477 return {}; 478 } 479 }; 480 481 std::ostream &operator<<(std::ostream &os, empty_list const &); 482 template <class T, size_t N> operator +(static_list<T,N> const & self,list<T> const & other)483 list<T> operator+(static_list<T, N> const &self, list<T> const &other) 484 { 485 list<T> res(self.begin(), self.end()); 486 return res += other; 487 } 488 } 489 490 namespace utils 491 { 492 /** 493 * Reserve enough space to save all values generated from f. 494 * 495 * We use a dummy arguments (p) to reserve only when f have a 496 * const_iterator type. 497 */ 498 template <class T, class From> 499 void reserve(types::list<T> &l, From const &f, 500 typename From::const_iterator *p = nullptr); 501 } 502 503 template <class T> 504 struct assignable<types::list<T>> { 505 typedef types::list<typename assignable<T>::type> type; 506 }; 507 508 template <class T, class S> 509 struct assignable<types::sliced_list<T, S>> { 510 typedef types::list<typename assignable<T>::type> type; 511 }; 512 513 // to cope with std::vector<bool> specialization 514 template <> 515 struct returnable<types::list<bool>::reference> { 516 using type = bool; 517 }; 518 PYTHONIC_NS_END 519 520 /* overload std::get */ 521 namespace std 522 { 523 template <size_t I, class T> 524 typename pythonic::types::list<T>::reference get(pythonic::types::list<T> &t); 525 526 template <size_t I, class T> 527 typename pythonic::types::list<T>::const_reference 528 get(pythonic::types::list<T> const &t); 529 530 template <size_t I, class T> 531 typename pythonic::types::list<T>::value_type 532 get(pythonic::types::list<T> &&t); 533 534 template <size_t I, class T, class S> 535 typename pythonic::types::sliced_list<T, S>::reference 536 get(pythonic::types::sliced_list<T, S> &t); 537 538 template <size_t I, class T, class S> 539 typename pythonic::types::sliced_list<T, S>::const_reference 540 get(pythonic::types::sliced_list<T, S> const &t); 541 542 template <size_t I, class T, class S> 543 typename pythonic::types::sliced_list<T, S>::value_type 544 get(pythonic::types::sliced_list<T, S> &&t); 545 546 template <size_t I, class T> 547 struct tuple_element<I, pythonic::types::list<T>> { 548 typedef typename pythonic::types::list<T>::value_type type; 549 }; 550 template <size_t I, class T, class S> 551 struct tuple_element<I, pythonic::types::sliced_list<T, S>> { 552 typedef typename pythonic::types::sliced_list<T, S>::value_type type; 553 }; 554 } 555 556 /* type inference stuff {*/ 557 #include "pythonic/include/types/combined.hpp" 558 559 template <class A> 560 struct __combined<container<A>, pythonic::types::empty_list> { 561 typedef pythonic::types::list<A> type; 562 }; 563 564 template <class A> 565 struct __combined<pythonic::types::empty_list, container<A>> { 566 typedef pythonic::types::list<A> type; 567 }; 568 569 template <class A, class B> 570 struct __combined<container<A>, pythonic::types::list<B>> { 571 typedef pythonic::types::list<typename __combined<A, B>::type> type; 572 }; 573 574 template <class A, class B> 575 struct __combined<pythonic::types::list<B>, container<A>> { 576 typedef pythonic::types::list<typename __combined<A, B>::type> type; 577 }; 578 579 template <class K, class V> 580 struct __combined<indexable<K>, pythonic::types::list<V>> { 581 typedef pythonic::types::list<V> type; 582 }; 583 584 template <class V, class K> 585 struct __combined<pythonic::types::list<V>, indexable<K>> { 586 typedef pythonic::types::list<V> type; 587 }; 588 589 template <class K, class V0, class V1> 590 struct __combined<indexable_container<K, V0>, pythonic::types::list<V1>> { 591 typedef pythonic::types::list<typename __combined<V0, V1>::type> type; 592 }; 593 594 template <class K, class V0, class V1> 595 struct __combined<pythonic::types::list<V1>, indexable_container<K, V0>> { 596 typedef pythonic::types::list<typename __combined<V0, V1>::type> type; 597 }; 598 599 template <class K, class V> 600 struct __combined<indexable_container<K, V>, pythonic::types::empty_list> { 601 typedef pythonic::types::list<V> type; 602 }; 603 604 template <class K, class V> 605 struct __combined<pythonic::types::empty_list, indexable_container<K, V>> { 606 typedef pythonic::types::list<V> type; 607 }; 608 609 template <class T0, class T1> 610 struct __combined<pythonic::types::list<T0>, pythonic::types::list<T1>> { 611 typedef pythonic::types::list<typename __combined<T0, T1>::type> type; 612 }; 613 614 template <class T, class S> 615 struct __combined<pythonic::types::sliced_list<T, S>, 616 pythonic::types::empty_list> { 617 typedef pythonic::types::list<T> type; 618 }; 619 template <class T, class S> 620 struct __combined<pythonic::types::empty_list, 621 pythonic::types::sliced_list<T, S>> { 622 typedef pythonic::types::list<T> type; 623 }; 624 625 template <class T0, class T1, class S> 626 struct __combined<pythonic::types::sliced_list<T1, S>, 627 pythonic::types::list<T0>> { 628 typedef pythonic::types::list<typename __combined<T0, T1>::type> type; 629 }; 630 template <class T0, class T1, class S> 631 struct __combined<pythonic::types::list<T0>, 632 pythonic::types::sliced_list<T1, S>> { 633 typedef pythonic::types::list<typename __combined<T0, T1>::type> type; 634 }; 635 636 template <class T, size_t N, class V> 637 struct __combined<pythonic::types::array_base<T, N, V>, 638 pythonic::types::empty_list> { 639 typedef pythonic::types::list<T> type; 640 }; 641 template <class T, size_t N, class V> 642 struct __combined<pythonic::types::empty_list, 643 pythonic::types::array_base<T, N, V>> { 644 typedef pythonic::types::list<T> type; 645 }; 646 template <class T, size_t N, class V, class Tp> 647 struct __combined<pythonic::types::array_base<T, N, V>, 648 pythonic::types::list<Tp>> { 649 typedef pythonic::types::list<typename __combined<T, Tp>::type> type; 650 }; 651 template <class T, size_t N, class V, class Tp> 652 struct __combined<pythonic::types::list<Tp>, 653 pythonic::types::array_base<T, N, V>> { 654 typedef pythonic::types::list<typename __combined<T, Tp>::type> type; 655 }; 656 657 /* } */ 658 659 #ifdef ENABLE_PYTHON_MODULE 660 661 PYTHONIC_NS_BEGIN 662 663 template <> 664 struct to_python<typename std::vector<bool>::reference> { 665 static PyObject *convert(typename std::vector<bool>::reference const &v); 666 }; 667 668 struct phantom_type; // ghost don't exist 669 template <> 670 struct to_python<typename std::conditional< 671 std::is_same<bool, typename std::vector<bool>::const_reference>::value, 672 phantom_type, typename std::vector<bool>::const_reference>::type> { 673 static PyObject * 674 convert(typename std::vector<bool>::const_reference const &v); 675 }; 676 677 template <typename T> 678 struct to_python<types::list<T>> { 679 static PyObject *convert(types::list<T> const &v); 680 }; 681 template <typename T, typename S> 682 struct to_python<types::sliced_list<T, S>> { 683 static PyObject *convert(types::sliced_list<T, S> const &v); 684 }; 685 template <> 686 struct to_python<types::empty_list> { 687 static PyObject *convert(types::empty_list const &); 688 }; 689 690 template <class T> 691 struct from_python<types::list<T>> { 692 693 static bool is_convertible(PyObject *obj); 694 695 static types::list<T> convert(PyObject *obj); 696 }; 697 PYTHONIC_NS_END 698 699 #endif 700 701 #endif 702