Prev: repeating elements in an array
Next: The trim function and its intented purpose?
From: Kai-Uwe Bux on 6 Apr 2010 06:17
none wrote:

> Kai-Uwe Bux wrote:
>
>>> And I understand that you can create similar behavior in more strict
>>> languages, like C++, by creating an array class whose members can
>>> also be arrays, thereby allowing array-of-array-of-array-etc...
>>
>> Not in C++. Instead you could do something like:
>
> When you say "Not in C++," do you mean that you *can't* do that in C++
> or that you *shouldn't* do that in C++ because it doesn't follow the
> "spirit" of C++? If you mean the former, I have to disagree because
> I've done it, more than once. I can post sample code if needed, but all
> you have to do is create a class that contains a vector of pointers to
> the same class. You can even make your arrays behave similarly to perl
> arrays by having your class's [] operator perform an allocation when
> invoked on a node that doesn't already exist. Then, syntax like this
> becomes perfectly legal:
>
> MyArrayOfArrayClass x;
> x[2][3][4][5][6] = 7;
>
> The array x now has six dimensions and (depending on how you define the
> semantics of your [] operator) a total of 720 elements.

I was taking "an array class whose members can also be arrays" too
literally. It steered my thinking process toward:

class ArrayClass {
...
std::vector<ArrayClass> member;

};

But you are right: this problem can be solved by introducing another level
of indirection (i.e., pointers).

>> typedef std::vector< unsigned long > multi_index;
>> typedef std::map< multi_index, T > sparse_variable_dim_array_of_T;
>
> This is interesting. You get a map with whatever element type you like,
> with a key that is a vector. So how would you assign elements into your
> map? I don't believe that C++ allows anything like this:
>
> x[{1, 2, 3, 4, 5}] = 6;

No, it does not.

> Having to create and initialize a vector just to use it as an index
> every time you want to access the map would be cumbersome:
>
> std::vector key;
> key.push_back(1);
> key.push_back(2);
> key.push_back(3);
> key.push_back(4);
> key.push_back(5);
> x[key] = 6;
>
> I suppose there's a more elegant way, maybe like this:
>
> unsigned long indices[5] = {1, 2, 3, 4, 5};
> std::vector key(indices, &indices[5]}; // (first, last) constructor
> x[key] = 6;
>
> It's still a bit awkward. Maybe it's possible to create a class with an
> overloaded [] operator that could build the vector, then use it as the
> look-up into the map, so that the above could be written as:
>
> x[1][2][3][4][5] = 6;
>
> It's not obvious to me how (if) that could be done, though.

The following would be better if we could overload the dot-operator. This
way, it suffers from the usual limitations of a proxy class:

#include <map>
#include <vector>

typedef unsigned long index_type;
typedef std::vector< index_type > multi_index_type;

template < typename T >
class multi_array :
private std::map< multi_index_type, T >
{
typedef std::map< multi_index_type, T > base;

public:

class partially_indexed {

friend class multi_array;

multi_array & the_array;
multi_index_type the_prefix;

partially_indexed ( multi_array & array, index_type i )
: the_array ( array )
, the_prefix ( 1, i )
{}

public:

operator T& ( void ) {
return ( the_array.base::operator[]( the_prefix ) );
}

partially_indexed & operator[] ( index_type i ) {
the_prefix.push_back( i );
return ( *this );
}

T & operator= ( T const & val ) {
T & dummy = the_array.base::operator[]( the_prefix );
dummy = val;
return ( dummy );
}

};

partially_indexed operator[] ( index_type i ) {
return ( partially_indexed( *this, i ) );
}

};

#include <iostream>
#include <ostream>

int main ( void ) {
multi_array< int > x;
x[5][3] = -2;
std::cout << x[5][3] << "\n";
std::cout << x[5] << "\n"; // default value
}


Best

Kai-Uwe Bux
From: Pascal J. Bourguignon on 6 Apr 2010 16:10
none <none(a)none.none> writes:

> Hi
>
> Sorry if this is a FAQ, but I don't even know the correct terminology to
> Google.
>
> In general, how do you solve the "variable dimension" problem? I
> understand that some languages support arbitrary-dimension arrays
> intrinsically, as in Perl:
>
> my $x;
> $x[5][5][5][5][5][5] = 5;
>
> And I understand that you can create similar behavior in more strict
> languages, like C++, by creating an array class whose members can also be
> arrays, thereby allowing array-of-array-of-array-etc...
>
> But how do you go about writing code to deal with such objects? For
> example, if I knew that my array was three levels deep, I could write the
> following:
>
> ThreeLevelArray A;
> int x, y, z;
>
> for (x = 0; x < A.size() x++)
> {
> for (y = 0; y < A[x].size(); y++)
> {
> for (z = 0; z < A[x][y].size(); z++)
> {
> A[x][y][z] = x + y + z;
> }
> }
> }
>
> But how do you get a variable number of nested for-loops, or the logical
> equivalent of that? I'm really just looking for general advice on how to
> deal with variable-dimension arrays. In the past, I've run into the
> problem only a handful of times, and in each case I was able to do
> something that worked but was very un-elegant and required heavy
> assumptions about what the nature of the array would be.

This question is linked to the question of compilation-time
vs. run-time.



If the rank of the array is known at compilation-time, then the problem
is easily solved in the case of lisp where we deal with this constantly
when writing macros. For example, here is a macro I wrote to deal with
it:

(defmacro rloop (clauses &rest body)
(if (null clauses)
`(progn ,@body)
`(loop ,@(car clauses) do (rloop ,(cdr clauses) ,@body))))


So I can write:

(rloop ((for i0 from 0 below n0)
(for i1 from 0 below n1)
...
(for ik from 0 below nk))
(aref a i0 i1 .. ik))

and the macro rloop will generate the required number of embedded loops,
at compilation-time.

This is trivial meta-programming, and it is "doable" in C++ too, thanks
to template and their unexpected Turing completeness... But I don't
think you'd want to do it. I mean, just try to write the required
templates and compare with the rloop macro above.



On the other hand, if the rank of the array is not known at compilation
time, then you won't have any other solution than to use a dynamic data
structure (ie. a vector) to index the array. Iterating on such a vector
of indices is not hard, just a little delicate. But indeed, in this
case you wouldn't write syntactically nested loops. You would just have
one loop to iterate on the set of indices, and then you would index the
array with the indices vector.


You could write something like (rusty "pseudo-code" C++ ahead):

Indices i(a);
for(i=0;!i.is_done();i++){
a[i];
}

with:

class Indices{
std::vector<int> indices;
std::vector<int> dimensions;
public:
Indices(const Array& a){
indices=std::vector<int>(a->rank(),0);
dimensions=a->dimensions();
}
Indices& operator=(int zero){
if(zero==0){
indices=std::vector<int>(a->rank(),0);
}else{
error("Can only assign 0 to reset the Indices");
}
return(*this);
}
Indices& operator++(){
int k=indices.size()-1;
indices[k]++;
while((0<k)&&(indices[k]>=dimensions[k])){
indices[k]=0;
k--;
indices[k]++;
}
return(*this);
}
bool is_done() const{
for(int k=0;k<indices.size();k++){
if(indices[k]!=0){
return(false);
}
}
return(true);
}
int operator[](int k) const{
return(indices[k]);
}
// ...
};


template <ElementType> class Array{
// ...
public:
ElementType& operator[](const Indices& i){
int rowMajor=0;
for(k=0;k<this->rank();k++){
rowMajor*=this->dimensions[k];
rowMajor+=i[k];
}
return(this->elements[rowMajor]);
}
// ...
};


Or if you are somewhat lazy, you'd just write:

(defstruct indices indices dimensions)

(defun create-indices (array)
(make-indices :indices (make-array (array-rank array) :initial-element 0)
:dimensions (copy-list (array-dimensions array))))

(defmethod reset ((self indices))
(fill (indices-indices self) 0)
self)

(defmethod ++ ((self indices))
(let ((k (1- (length (indices-indices self)))))
(incf (aref (indices-indices self)))
(loop while (and (plusp k)
(<= (aref (indices-dimensions self) k)
(aref (indices-indices self) k)))
do (setf (aref (indices-indices self) k) 0)
(decf k)
(incf (aref (indices-indices self) k)))
self))

(defmethod indices-ref ((self indices) k)
(aref (indices-indices self) k))


(defmethod array-ref ((self array) (i indices))
(row-major-index self (apply (function array-row-major-index)
self
(coerce (indices-indices i) 'list))))

which is more concise.

--
__Pascal Bourguignon__
From: Kai-Uwe Bux on 7 Apr 2010 09:12
Kai-Uwe Bux wrote:

> none wrote:
>
>> Kai-Uwe Bux wrote:
>>
>>>> And I understand that you can create similar behavior in more strict
>>>> languages, like C++, by creating an array class whose members can
>>>> also be arrays, thereby allowing array-of-array-of-array-etc...
>>>
>>> Not in C++. Instead you could do something like:
>>
>> When you say "Not in C++," do you mean that you *can't* do that in C++
>> or that you *shouldn't* do that in C++ because it doesn't follow the
>> "spirit" of C++? If you mean the former, I have to disagree because
>> I've done it, more than once. I can post sample code if needed, but all
>> you have to do is create a class that contains a vector of pointers to
>> the same class. You can even make your arrays behave similarly to perl
>> arrays by having your class's [] operator perform an allocation when
>> invoked on a node that doesn't already exist. Then, syntax like this
>> becomes perfectly legal:
>>
>> MyArrayOfArrayClass x;
>> x[2][3][4][5][6] = 7;
>>
>> The array x now has six dimensions and (depending on how you define the
>> semantics of your [] operator) a total of 720 elements.
>
> I was taking "an array class whose members can also be arrays" too
> literally. It steered my thinking process toward:
>
> class ArrayClass {
> ...
> std::vector<ArrayClass> member;
>
> };
>
> But you are right: this problem can be solved by introducing another level
> of indirection (i.e., pointers).
>
>>> typedef std::vector< unsigned long > multi_index;
>>> typedef std::map< multi_index, T > sparse_variable_dim_array_of_T;
>>
>> This is interesting. You get a map with whatever element type you like,
>> with a key that is a vector. So how would you assign elements into your
>> map? I don't believe that C++ allows anything like this:
>>
>> x[{1, 2, 3, 4, 5}] = 6;
>
> No, it does not.
>
>> Having to create and initialize a vector just to use it as an index
>> every time you want to access the map would be cumbersome:
>>
>> std::vector key;
>> key.push_back(1);
>> key.push_back(2);
>> key.push_back(3);
>> key.push_back(4);
>> key.push_back(5);
>> x[key] = 6;
>>
>> I suppose there's a more elegant way, maybe like this:
>>
>> unsigned long indices[5] = {1, 2, 3, 4, 5};
>> std::vector key(indices, &indices[5]}; // (first, last) constructor
>> x[key] = 6;
>>
>> It's still a bit awkward. Maybe it's possible to create a class with an
>> overloaded [] operator that could build the vector, then use it as the
>> look-up into the map, so that the above could be written as:
>>
>> x[1][2][3][4][5] = 6;
>>
>> It's not obvious to me how (if) that could be done, though.
>
> The following would be better if we could overload the dot-operator. This
> way, it suffers from the usual limitations of a proxy class:
>
> #include <map>
> #include <vector>
>
> typedef unsigned long index_type;
> typedef std::vector< index_type > multi_index_type;
>
> template < typename T >
> class multi_array :
> private std::map< multi_index_type, T >
> {
> typedef std::map< multi_index_type, T > base;
>
> public:
>
> class partially_indexed {
>
> friend class multi_array;
>
> multi_array & the_array;
> multi_index_type the_prefix;
>
> partially_indexed ( multi_array & array, index_type i )
> : the_array ( array )
> , the_prefix ( 1, i )
> {}
>
> public:
>
> operator T& ( void ) {
> return ( the_array.base::operator[]( the_prefix ) );
> }
>
> partially_indexed & operator[] ( index_type i ) {
> the_prefix.push_back( i );
> return ( *this );
> }
>
> T & operator= ( T const & val ) {
> T & dummy = the_array.base::operator[]( the_prefix );
> dummy = val;
> return ( dummy );
> }
>
> };
>
> partially_indexed operator[] ( index_type i ) {
> return ( partially_indexed( *this, i ) );
> }
>
> };
>
> #include <iostream>
> #include <ostream>
>
> int main ( void ) {
> multi_array< int > x;
> x[5][3] = -2;
> std::cout << x[5][3] << "\n";
> std::cout << x[5] << "\n"; // default value
> }

Here is another idea for syntactic sugar:

#include <vector>
#include <iterator>

template < typename T >
struct multi_index
: std::vector< T >
{

friend
multi_index operator| ( multi_index const & lhs, T const & rhs ) {
multi_index result ( lhs );
result.push_back( rhs );
return ( result );
}

friend
multi_index operator| ( multi_index const & lhs,
multi_index const & rhs ) {
multi_index result ( lhs );
std::copy( rhs.begin(), rhs.end(), std::back_inserter( result ) );
return ( result );
}

};

#include <map>
#include <iostream>
#include <ostream>

int main ( void ) {
multi_index< unsigned > empty;
std::map< multi_index< unsigned >, int > m;
m[ empty|2|1|0 ] = -2;
std::cout << m[ empty|2|1|0 ] << "\n";
}


Best

Kai-Uwe Bux
From: none on 7 Apr 2010 11:46
Kai-Uwe Bux wrote:

> The following would be better if we could overload the dot-operator.
> This way, it suffers from the usual limitations of a proxy class:

[cut]

> int main ( void ) {
> multi_array< int > x;
> x[5][3] = -2;
> std::cout << x[5][3] << "\n";
> std::cout << x[5] << "\n"; // default value
> }



This is a very nice approach. And elsewhere in this thread, Andrew
Poelstra and Richard Heathfield answered the question about how to process
such an object. In a nutshell, the answer is recursion. In many cases,
though, with the way you've defined this object, recursion can be
eliminated. The fact that you're storing the actual elements in a
"sparse" manner is very clever and very convenient.

Thanks for the great responses.
From: Lie Ryan on 8 Apr 2010 00:44
On 04/08/10 01:46, none wrote:
> Kai-Uwe Bux wrote:
>
>> The following would be better if we could overload the dot-operator.
>> This way, it suffers from the usual limitations of a proxy class:
>
> [cut]
>
>> int main ( void ) {
>> multi_array< int > x;
>> x[5][3] = -2;
>> std::cout << x[5][3] << "\n";
>> std::cout << x[5] << "\n"; // default value
>> }
>
>
>
> This is a very nice approach. And elsewhere in this thread, Andrew
> Poelstra and Richard Heathfield answered the question about how to process
> such an object. In a nutshell, the answer is recursion. In many cases,
> though, with the way you've defined this object, recursion can be
> eliminated. The fact that you're storing the actual elements in a
> "sparse" manner is very clever and very convenient.
>
> Thanks for the great responses.

Another approach which doesn't use recursion is iterating the array by
manually managing a "frame stack". With recursion, we're actually using
the function call stack as our "frame stack". However, unless your
language doesn't support recursion, I don't think there's any practical
advantage in using an iterative approach for iterating a recursive data
structure (e.g. variable depth array).
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: repeating elements in an array
Next: The trim function and its intented purpose?