← Back to branch summary

~ubuntu-branches/ubuntu/warty/aqsis/warty

« back to all changes in this revision

Viewing changes to boost/boost/multi_array/base.hpp

  • Committer: Bazaar Package Importer
  • Author(s): LaMont Jones
  • Date: 2004-08-24 07:25:04 UTC
  • Revision ID: james.westby@ubuntu.com-20040824072504-zf993vnevvisdsvb
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
boost/boost/multi_array/base.hpp
 
1
// Copyright (C) 2002 Ronald Garcia
 
2
//
 
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.
 
8
//
 
9
// This software is provided "as is" without express or implied warranty, 
 
10
// and with no claim as to its suitability for any purpose.
 
11
//
 
12
 
 
13
#ifndef BASE_RG071801_HPP
 
14
#define BASE_RG071801_HPP
 
15
 
 
16
//
 
17
// base.hpp - some implementation base classes for from which
 
18
// functionality is acquired
 
19
//
 
20
 
 
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"
 
31
#include <cassert>
 
32
#include <cstddef>
 
33
#include <memory>
 
34
 
 
35
namespace boost {
 
36
 
 
37
/////////////////////////////////////////////////////////////////////////
 
38
// class declarations
 
39
/////////////////////////////////////////////////////////////////////////
 
40
 
 
41
template<typename T, std::size_t NumDims,
 
42
  typename Allocator = std::allocator<T> >
 
43
class multi_array;
 
44
 
 
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;
 
54
}
 
55
 
 
56
 
 
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
 
64
namespace {
 
65
  multi_array_types::extent_gen extents;
 
66
  multi_array_types::index_gen indices;
 
67
}
 
68
#endif // BOOST_MULTI_ARRAY_NO_GENERATORS
 
69
 
 
70
namespace detail {
 
71
namespace multi_array {
 
72
 
 
73
template <typename T, std::size_t NumDims>
 
74
class sub_array;
 
75
 
 
76
template <typename T, std::size_t NumDims, typename TPtr = const T*>
 
77
class const_sub_array;
 
78
 
 
79
template <typename T, std::size_t NumDims, typename value_type,
 
80
  typename reference_type, typename tag, typename difference_type>
 
81
struct iterator_generator;
 
82
 
 
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;
 
86
 
 
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;
 
90
 
 
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;
 
94
 
 
95
template <typename T,typename TPtr>
 
96
struct iterator_base;
 
97
 
 
98
template <typename T, std::size_t NumDims>
 
99
struct iterator_policies;
 
100
 
 
101
template <typename T, std::size_t NumDims, typename TPtr = const T*>
 
102
class const_multi_array_view;
 
103
 
 
104
template <typename T, std::size_t NumDims>
 
105
class multi_array_view;
 
106
 
 
107
/////////////////////////////////////////////////////////////////////////
 
108
// class interfaces
 
109
/////////////////////////////////////////////////////////////////////////
 
110
 
 
111
class multi_array_base {
 
112
public:
 
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;
 
120
};
 
121
 
 
122
//
 
123
// value_accessor_n
 
124
//  contains the routines for accessing elements from
 
125
//  N-dimensional views.
 
126
//
 
127
template<typename T, std::size_t NumDims>
 
128
class value_accessor_n : public multi_array_base {
 
129
  typedef multi_array_base super_type;
 
130
public:
 
131
  typedef typename super_type::index index;
 
132
 
 
133
  // 
 
134
  // public typedefs used by classes that inherit from this base
 
135
  //
 
136
  typedef T element;
 
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;
 
140
 
 
141
protected:
 
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 {
 
148
 
 
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);
 
152
 
 
153
  }
 
154
 
 
155
  value_accessor_n() { }
 
156
  ~value_accessor_n() { }
 
157
};
 
158
 
 
159
 
 
160
 
 
161
//
 
162
// value_accessor_one
 
163
//  contains the routines for accessing reference elements from
 
164
//  1-dimensional views.
 
165
//
 
166
template<typename T>
 
167
class value_accessor_one : public multi_array_base {
 
168
  typedef multi_array_base super_type;
 
169
public:
 
170
  typedef typename super_type::index index;
 
171
  //
 
172
  // public typedefs for use by classes that inherit it.
 
173
  //
 
174
  typedef T element;
 
175
  typedef T value_type;
 
176
  typedef T& reference;
 
177
  typedef T const& const_reference;
 
178
 
 
179
protected:
 
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,
 
183
                   const size_type*,
 
184
                   const index* strides,
 
185
                   const index*) const {
 
186
    return *(base + idx * strides[0]);
 
187
  }
 
188
 
 
189
  value_accessor_one() { }
 
190
  ~value_accessor_one() { }
 
191
};
 
192
 
 
193
 
 
194
/////////////////////////////////////////////////////////////////////////
 
195
// choose value accessor begins
 
196
//
 
197
 
 
198
struct choose_value_accessor_n {
 
199
  template <typename T, std::size_t NumDims>
 
200
  struct bind {
 
201
    typedef value_accessor_n<T,NumDims> type;
 
202
  };
 
203
};
 
204
 
 
205
struct choose_value_accessor_one {
 
206
  template <typename T, std::size_t NumDims>
 
207
  struct bind {
 
208
    typedef value_accessor_one<T> type;
 
209
  };
 
210
};
 
211
 
 
212
 
 
213
template <std::size_t NumDims>
 
214
struct value_accessor_gen_helper {
 
215
  typedef choose_value_accessor_n choice;
 
216
};
 
217
 
 
218
template <>
 
219
struct value_accessor_gen_helper<1> {
 
220
  typedef choose_value_accessor_one choice;
 
221
};
 
222
 
 
223
template <typename T, std::size_t NumDims>
 
224
struct value_accessor_generator {
 
225
private:
 
226
  typedef typename value_accessor_gen_helper<NumDims>::choice Choice;
 
227
public:
 
228
  typedef typename Choice::template bind<T,NumDims>::type type;
 
229
};
 
230
 
 
231
//
 
232
// choose value accessor ends
 
233
/////////////////////////////////////////////////////////////////////////
 
234
 
 
235
 
 
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;
 
242
};
 
243
 
 
244
template <>
 
245
struct iterator_tag_selector<1> {
 
246
  typedef std::random_access_iterator_tag type;
 
247
};
 
248
 
 
249
 
 
250
////////////////////////////////////////////////////////////////////////
 
251
// multi_array_base
 
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;
 
257
public:
 
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;
 
265
 
 
266
  template <std::size_t NDims>
 
267
  struct subarray {
 
268
    typedef boost::detail::multi_array::sub_array<T,NDims> type;
 
269
  };
 
270
 
 
271
  template <std::size_t NDims>
 
272
  struct const_subarray {
 
273
    typedef boost::detail::multi_array::const_sub_array<T,NDims> type;
 
274
  };
 
275
 
 
276
  template <std::size_t NDims>
 
277
  struct array_view {
 
278
    typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
 
279
  };
 
280
 
 
281
  template <std::size_t NDims>
 
282
  struct const_array_view {
 
283
  public:
 
284
    typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
 
285
  };
 
286
 
 
287
  //
 
288
  // iterator support
 
289
  //
 
290
 
 
291
  typedef typename iterator_tag_selector<NumDims>::type iterator_tag;
 
292
 
 
293
  typedef typename
 
294
    iterator_generator<T,NumDims,value_type,
 
295
    reference,iterator_tag,index>::type iterator;
 
296
 
 
297
  typedef typename
 
298
    const_iterator_generator<T,NumDims,value_type,
 
299
    const_reference,iterator_tag,index>::type const_iterator;
 
300
 
 
301
  typedef typename
 
302
    reverse_iterator_generator<T,NumDims,value_type,
 
303
    reference,iterator_tag,index>::type reverse_iterator;
 
304
 
 
305
  typedef typename
 
306
    const_reverse_iterator_generator<T,NumDims,value_type,
 
307
    const_reference,iterator_tag,index>::type const_reverse_iterator;
 
308
 
 
309
protected:
 
310
  typedef iterator_base<T,T*> iter_base;
 
311
  typedef iterator_base<T,const T*> const_iter_base;
 
312
 
 
313
  multi_array_impl_base() { }
 
314
  ~multi_array_impl_base() { }
 
315
 
 
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 {
 
321
    index offset = 0;
 
322
    for (size_type n = 0; n != NumDims; ++n) 
 
323
      offset += indices[n] * strides[n];
 
324
    
 
325
    return base[offset];
 
326
  }
 
327
 
 
328
  template <typename StrideList, typename ExtentList>
 
329
  void compute_strides(StrideList& stride_list, ExtentList& extent_list,
 
330
                       const general_storage_order<NumDims>& storage)
 
331
  {
 
332
    // invariant: stride = the stride for dimension n
 
333
    index stride = 1;
 
334
    for (size_type n = 0; n != NumDims; ++n) {
 
335
      index stride_sign = +1;
 
336
      
 
337
      if (!storage.ascending(storage.ordering(n)))
 
338
        stride_sign = -1;
 
339
      
 
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;
 
343
      
 
344
      stride *= extent_list[storage.ordering(n)];
 
345
    } 
 
346
  }
 
347
 
 
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>
 
352
  index
 
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)
 
357
  {
 
358
    return
 
359
      calculate_descending_dimension_offset(stride_list,extent_list,
 
360
                                            storage) +
 
361
      calculate_indexing_offset(stride_list,index_base_list);
 
362
  }
 
363
 
 
364
  // This calculates the offset added to the base pointer that are
 
365
  // caused by descending dimensions
 
366
  template <typename StrideList, typename ExtentList>
 
367
  index
 
368
  calculate_descending_dimension_offset(const StrideList& stride_list,
 
369
                                const ExtentList& extent_list,
 
370
                                const general_storage_order<NumDims>& storage)
 
371
  {
 
372
    index offset = 0;
 
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];
 
377
 
 
378
    return offset;
 
379
  }
 
380
 
 
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.
 
384
 
 
385
  template <typename StrideList, typename BaseList>
 
386
  index
 
387
  calculate_indexing_offset(const StrideList& stride_list,
 
388
                          const BaseList& index_base_list)
 
389
  {
 
390
    index offset = 0;
 
391
    for (size_type n = 0; n != NumDims; ++n)
 
392
        offset -= stride_list[n] * index_base_list[n];
 
393
    return offset;
 
394
  }
 
395
 
 
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>
 
406
  ArrayRef
 
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,
 
413
                      TPtr base) const {
 
414
 
 
415
    boost::array<index,NDims> new_strides;
 
416
    boost::array<index,NDims> new_extents;
 
417
 
 
418
    index offset = 0;
 
419
    size_type dim = 0;
 
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;
 
428
 
 
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];
 
432
 
 
433
      if (!current_range.is_degenerate()) {
 
434
 
 
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];
 
438
        
 
439
        // calculate new extents
 
440
        new_extents[dim] = len;
 
441
        ++dim;
 
442
      }
 
443
    }
 
444
    assert (dim == NDims);
 
445
 
 
446
    return
 
447
      ArrayRef(base+offset,
 
448
               new_extents,
 
449
               new_strides);
 
450
  }
 
451
                     
 
452
 
 
453
};
 
454
 
 
455
} // namespace multi_array
 
456
} // namespace detail
 
457
 
 
458
} // namespace boost
 
459
 
 
460
#endif // BASE_RG071801_HPP