1 // Copyright (C) 2002 Ronald Garcia
3 // Permission to copy, use, sell and distribute this software is granted
4 // provided this copyright notice appears in all copies.
5 // Permission to modify the code and to distribute modified code is granted
6 // provided this copyright notice appears in all copies, and a notice
7 // that the code was modified is included with the copyright notice.
9 // This software is provided "as is" without express or implied warranty,
10 // and with no claim as to its suitability for any purpose.
13 #ifndef BASE_RG071801_HPP
14 #define BASE_RG071801_HPP
17 // base.hpp - some implementation base classes for from which
18 // functionality is acquired
21 #include "boost/multi_array/extent_range.hpp"
22 #include "boost/multi_array/extent_gen.hpp"
23 #include "boost/multi_array/index_range.hpp"
24 #include "boost/multi_array/index_gen.hpp"
25 #include "boost/multi_array/storage_order.hpp"
26 #include "boost/multi_array/types.hpp"
27 #include "boost/config.hpp"
28 #include "boost/multi_array/iterator_adaptors.hpp"
29 #include "boost/static_assert.hpp"
30 #include "boost/type.hpp"
37 /////////////////////////////////////////////////////////////////////////
39 /////////////////////////////////////////////////////////////////////////
41 template<typename T, std::size_t NumDims,
42 typename Allocator = std::allocator<T> >
45 // This is a public interface for use by end users!
46 namespace multi_array_types {
47 typedef boost::detail::multi_array::size_type size_type;
48 typedef std::ptrdiff_t difference_type;
49 typedef boost::detail::multi_array::index index;
50 typedef detail::multi_array::index_range<index,size_type> index_range;
51 typedef detail::multi_array::extent_range<index,size_type> extent_range;
52 typedef detail::multi_array::index_gen<0,0> index_gen;
53 typedef detail::multi_array::extent_gen<0> extent_gen;
57 // boost::extents and boost::indices are now a part of the public
58 // interface. That way users don't necessarily have to create their
59 // own objects. On the other hand, one may not want the overhead of
60 // object creation in small-memory environments. Thus, the objects
61 // can be left undefined by defining BOOST_MULTI_ARRAY_NO_GENERATORS
62 // before loading multi_array.hpp.
63 #if !BOOST_MULTI_ARRAY_NO_GENERATORS
65 multi_array_types::extent_gen extents;
66 multi_array_types::index_gen indices;
68 #endif // BOOST_MULTI_ARRAY_NO_GENERATORS
71 namespace multi_array {
73 template <typename T, std::size_t NumDims>
76 template <typename T, std::size_t NumDims, typename TPtr = const T*>
77 class const_sub_array;
79 template <typename T, std::size_t NumDims, typename value_type,
80 typename reference_type, typename tag, typename difference_type>
81 struct iterator_generator;
83 template <typename T, std::size_t NumDims, typename value_type,
84 typename reference_type, typename tag, typename difference_type>
85 struct const_iterator_generator;
87 template <typename T, std::size_t NumDims, typename value_type,
88 typename reference_type, typename tag, typename difference_type>
89 struct reverse_iterator_generator;
91 template <typename T, std::size_t NumDims, typename value_type,
92 typename reference_type, typename tag, typename difference_type>
93 struct const_reverse_iterator_generator;
95 template <typename T,typename TPtr>
98 template <typename T, std::size_t NumDims>
99 struct iterator_policies;
101 template <typename T, std::size_t NumDims, typename TPtr = const T*>
102 class const_multi_array_view;
104 template <typename T, std::size_t NumDims>
105 class multi_array_view;
107 /////////////////////////////////////////////////////////////////////////
109 /////////////////////////////////////////////////////////////////////////
111 class multi_array_base {
113 typedef multi_array_types::size_type size_type;
114 typedef multi_array_types::difference_type difference_type;
115 typedef multi_array_types::index index;
116 typedef multi_array_types::index_range index_range;
117 typedef multi_array_types::extent_range extent_range;
118 typedef multi_array_types::index_gen index_gen;
119 typedef multi_array_types::extent_gen extent_gen;
124 // contains the routines for accessing elements from
125 // N-dimensional views.
127 template<typename T, std::size_t NumDims>
128 class value_accessor_n : public multi_array_base {
129 typedef multi_array_base super_type;
131 typedef typename super_type::index index;
134 // public typedefs used by classes that inherit from this base
137 typedef boost::multi_array<T,NumDims-1> value_type;
138 typedef sub_array<T,NumDims-1> reference;
139 typedef const_sub_array<T,NumDims-1> const_reference;
142 // used by array operator[] and iterators to get reference types.
143 template <typename Reference, typename TPtr>
144 Reference access(boost::type<Reference>,index idx,TPtr base,
145 const size_type* extents,
146 const index* strides,
147 const index* index_base) const {
149 // return a sub_array<T,NDims-1> proxy object
150 TPtr newbase = base + idx * strides[0];
151 return Reference(newbase,extents+1,strides+1,index_base+1);
155 value_accessor_n() { }
156 ~value_accessor_n() { }
162 // value_accessor_one
163 // contains the routines for accessing reference elements from
164 // 1-dimensional views.
167 class value_accessor_one : public multi_array_base {
168 typedef multi_array_base super_type;
170 typedef typename super_type::index index;
172 // public typedefs for use by classes that inherit it.
175 typedef T value_type;
176 typedef T& reference;
177 typedef T const& const_reference;
180 // used by array operator[] and iterators to get reference types.
181 template <typename Reference, typename TPtr>
182 Reference access(boost::type<Reference>,index idx,TPtr base,
184 const index* strides,
185 const index*) const {
186 return *(base + idx * strides[0]);
189 value_accessor_one() { }
190 ~value_accessor_one() { }
194 /////////////////////////////////////////////////////////////////////////
195 // choose value accessor begins
198 struct choose_value_accessor_n {
199 template <typename T, std::size_t NumDims>
201 typedef value_accessor_n<T,NumDims> type;
205 struct choose_value_accessor_one {
206 template <typename T, std::size_t NumDims>
208 typedef value_accessor_one<T> type;
213 template <std::size_t NumDims>
214 struct value_accessor_gen_helper {
215 typedef choose_value_accessor_n choice;
219 struct value_accessor_gen_helper<1> {
220 typedef choose_value_accessor_one choice;
223 template <typename T, std::size_t NumDims>
224 struct value_accessor_generator {
226 typedef typename value_accessor_gen_helper<NumDims>::choice Choice;
228 typedef typename Choice::template bind<T,NumDims>::type type;
232 // choose value accessor ends
233 /////////////////////////////////////////////////////////////////////////
236 /////////////////////////////////////////////////////////////////////////
237 // multi_array/sub_array base stuffs
238 /////////////////////////////////////////////////////////////////////////
239 template <std::size_t NumDims>
240 struct iterator_tag_selector {
241 typedef std::input_iterator_tag type;
245 struct iterator_tag_selector<1> {
246 typedef std::random_access_iterator_tag type;
250 ////////////////////////////////////////////////////////////////////////
252 ////////////////////////////////////////////////////////////////////////
253 template <typename T, std::size_t NumDims>
254 class multi_array_impl_base :
255 public value_accessor_generator<T,NumDims>::type {
256 typedef typename value_accessor_generator<T,NumDims>::type super_type;
258 typedef typename super_type::index index;
259 typedef typename super_type::size_type size_type;
260 typedef typename super_type::element element;
261 typedef typename super_type::index_range index_range;
262 typedef typename super_type::value_type value_type;
263 typedef typename super_type::reference reference;
264 typedef typename super_type::const_reference const_reference;
266 template <std::size_t NDims>
268 typedef boost::detail::multi_array::sub_array<T,NDims> type;
271 template <std::size_t NDims>
272 struct const_subarray {
273 typedef boost::detail::multi_array::const_sub_array<T,NDims> type;
276 template <std::size_t NDims>
278 typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
281 template <std::size_t NDims>
282 struct const_array_view {
284 typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
291 typedef typename iterator_tag_selector<NumDims>::type iterator_tag;
294 iterator_generator<T,NumDims,value_type,
295 reference,iterator_tag,index>::type iterator;
298 const_iterator_generator<T,NumDims,value_type,
299 const_reference,iterator_tag,index>::type const_iterator;
302 reverse_iterator_generator<T,NumDims,value_type,
303 reference,iterator_tag,index>::type reverse_iterator;
306 const_reverse_iterator_generator<T,NumDims,value_type,
307 const_reference,iterator_tag,index>::type const_reverse_iterator;
310 typedef iterator_base<T,T*> iter_base;
311 typedef iterator_base<T,const T*> const_iter_base;
313 multi_array_impl_base() { }
314 ~multi_array_impl_base() { }
316 // Used by operator() in our array classes
317 template <typename Reference, typename IndexList, typename TPtr>
318 Reference access_element(boost::type<Reference>, TPtr base,
319 const IndexList& indices,
320 const index* strides) const {
322 for (size_type n = 0; n != NumDims; ++n)
323 offset += indices[n] * strides[n];
328 template <typename StrideList, typename ExtentList>
329 void compute_strides(StrideList& stride_list, ExtentList& extent_list,
330 const general_storage_order<NumDims>& storage)
332 // invariant: stride = the stride for dimension n
334 for (size_type n = 0; n != NumDims; ++n) {
335 index stride_sign = +1;
337 if (!storage.ascending(storage.ordering(n)))
340 // The stride for this dimension is the product of the
341 // lengths of the ranks minor to it.
342 stride_list[storage.ordering(n)] = stride * stride_sign;
344 stride *= extent_list[storage.ordering(n)];
348 // This calculates the offset to the array base pointer due to:
349 // 1. dimensions stored in descending order
350 // 2. non-zero dimension index bases
351 template <typename StrideList, typename ExtentList, typename BaseList>
353 calculate_origin_offset(const StrideList& stride_list,
354 const ExtentList& extent_list,
355 const general_storage_order<NumDims>& storage,
356 const BaseList& index_base_list)
359 calculate_descending_dimension_offset(stride_list,extent_list,
361 calculate_indexing_offset(stride_list,index_base_list);
364 // This calculates the offset added to the base pointer that are
365 // caused by descending dimensions
366 template <typename StrideList, typename ExtentList>
368 calculate_descending_dimension_offset(const StrideList& stride_list,
369 const ExtentList& extent_list,
370 const general_storage_order<NumDims>& storage)
373 if (!storage.all_dims_ascending())
374 for (size_type n = 0; n != NumDims; ++n)
375 if (!storage.ascending(n))
376 offset -= (extent_list[n] - 1) * stride_list[n];
381 // This is used to reindex array_views, which are no longer
382 // concerned about storage order (specifically, whether dimensions
383 // are ascending or descending) since the viewed array handled it.
385 template <typename StrideList, typename BaseList>
387 calculate_indexing_offset(const StrideList& stride_list,
388 const BaseList& index_base_list)
391 for (size_type n = 0; n != NumDims; ++n)
392 offset -= stride_list[n] * index_base_list[n];
396 // Slicing using an index_gen.
397 // Note that populating an index_gen creates a type that encodes
398 // both the number of dimensions in the current Array (NumDims), and
399 // the Number of dimensions for the resulting view. This allows the
400 // compiler to fail if the dimensions aren't completely accounted
401 // for. For reasons unbeknownst to me, a BOOST_STATIC_ASSERT
402 // within the member function template does not work. I should add a
403 // note to the documentation specifying that you get a damn ugly
404 // error message if you screw up in your slicing code.
405 template <typename ArrayRef, int NDims, typename TPtr>
407 generate_array_view(boost::type<ArrayRef>,
408 const boost::detail::multi_array::
409 index_gen<NumDims,NDims>& indices,
410 const size_type* extents,
411 const index* strides,
412 const index* index_bases,
415 boost::array<index,NDims> new_strides;
416 boost::array<index,NDims> new_extents;
420 for (size_type n = 0; n != NumDims; ++n) {
421 const index default_start = index_bases[n];
422 const index default_finish = default_start+extents[n];
423 const index_range& current_range = indices.ranges_[n];
424 index start = current_range.get_start(default_start);
425 index finish = current_range.get_finish(default_finish);
426 index index_factor = current_range.stride();
427 index len = (finish - start) / index_factor;
429 // the array data pointer is modified to account for non-zero
430 // bases during slicing (see [Garcia] for the math involved)
431 offset += start * strides[n];
433 if (!current_range.is_degenerate()) {
435 // The index_factor for each dimension is included into the
436 // strides for the array_view (see [Garcia] for the math involved).
437 new_strides[dim] = index_factor * strides[n];
439 // calculate new extents
440 new_extents[dim] = len;
444 assert (dim == NDims);
447 ArrayRef(base+offset,
455 } // namespace multi_array
456 } // namespace detail
460 #endif // BASE_RG071801_HPP