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