Re: slicing and ranges of matrices

From: Ralf W. Grosse-Kunstleve (rwgk_at_[hidden])
Date: 2002-01-18 13:45:01

FWIW: a few theoretical remarks (born out of very pragmatic needs):

I came to the conclusion that multi_array will not
immediately work for us (see my other messages). Therefore
I thought some more about multi dimensional arrays. IMHO
Toon's questions only show that a more general design is
needed. There are three major concepts that I can
distinguish, and which I believe should be presented and
parameterized as such:

- Memory management
- Access schemes
- Iterators

Points:

Memory management:
  Ultimately any array is a one-dimensional array. Here I
  see six important memory management policies that are
  useful in different contexts:
    - automatic allocation, fixed size() (aka boost::array)
    - automatic allocation (fixed capacity), variable size()
    - dynamic allocation, fixed size()
        deep copy semantics
        reference counted
    - dynamic allocation, variable size() (e.g. std::vector)
        deep copy semantics
        reference counted
  The automatically allocated (i.e. stack) arrays will tend
  to be small, therefore deepcopy semantics is always
  appropriate.
  For the dynamically allocated arrays, both deepcopy and
  handle-based (referenced counting) copy semantics are
  useful, depending on the application. However, an array
  that is reference counted can easily provide a deep copy,
  but not vice versa. Therefore in practice four memory
  management varieties should be sufficient.
  A comprehensive package should give access to each of
  these.

Access schemes:
  An access scheme is a transformation from a general index
  object to a 1-dimensional array index. A simple index
  object is a tuple of integers. A simple access scheme is
  that of a conventional n-dimensional grid of points (as
  represented by multi_array). In real-world applications
  there are many other useful types of access schemes,
  mostly related to some type of symmetry (e.g.  Hermitian
  symmetry of complex-valued arrays).
  A comprehensive package should parameterize the access
  scheme (as a template argument) and provide the most
  common schemes as part of the package.
  Toon would provide a class implementing his custom
  access scheme, and then instantiate, e.g.
  multi_array<int, toon_accessor>.
  
  A slice is just a special access scheme, or a generalized
  simple access scheme.

Iterators:
  In the context of multi-dimensional arrays, iterators are
  a somewhat artificial concept. An iterator that does not
  keep track of the index object corresponding to the position
  in the underlying 1-dimensional array (e.g. the mapping from
  the 1-dimensional index to the corresponding three-tuple)
  is either fast but of limited use, or general but slow.
  A general multi-dimensional iterator must have some sort
  of nested loop inside. Therefore an iterator and a nested
  loop become almost indistinguishable.  However, I find it
  much more natural to think of a nested loop rather than
  an iterator. One could even argue that the STL iterators
  are the trivial form of a nested loop, and the nested
  loop is the proper abstraction for higher dimensions.

A partial implementation of these ideas can be found in the
cvs tree at cctbx.sf.net (e.g. shared_storage.h, ndim.h,
loops.h; maps/ndim.h implements a specialized accessor;
naming is still a bit disorganized). We are currently
refining the design. I would be happy to share more details
if there is an interest.

Ralf

__________________________________________________
Do You Yahoo!?
Send FREE video emails in Yahoo! Mail!
http://promo.yahoo.com/videomail/