Glas List: Re: [glas] [boost] Possible class submission: Sparse Array

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2006-04-26 16:05:58

Spencer Collyer wrote:
> I'd like to canvas opinions on whether it is worth submitting a class
> I've developed to Boost.
 >
 > It is a policy-based sparse array class. I'm aware there is a
 > sparse_vector class in the uBLAS library, but when I looked at it it
 > didn't seem to offer the degree of flexibility I needed, so I
 > developed my own. Like a lot of things, it grew a little
 > during development, but I've tried to keep the interface as close
 > to std::vector as seemed sensible.
 >
 > To try and make it as flexible as possible, I've implemented it using
 > four policies, as follows:
 >
 > bounds:
 > This determines what the bounds on the sparse_array are, and how
 > values that exceed them are handled. For example, the 'unbounded'
 > policy allows virtually any positive value of the subscript type
 > to be used, 'bounded'only allows values within the
 >(compile-time specified) max value and throws if
 > a subscript exceeding this is given, while 'clamped' makes such
 > value equal to the max value.

I'm interested.

> iterator:
> This determines how the limits on iterators are defined. So it is
> possible to specify that iteration should be over the whole range of the
> sparse_array, or that it should only be from the lowest assigned
> subscript to the highest assigned subscript.

what syntax do you use exactly for these different iterators?

> 
> value:
> This policy is currently used to define the default value for unassigned
> elements of the sparse_array, and also to determine how default values
> are handled in cases such as assigning from one sparse_array to another.

interesting

> 
> storage:
> This allows the user to specify how the underlying storage for the
> sparse_array is handled. Currently I only have one policy defined
> (std_map, which unsurprisingly uses a std::map for the storage), but
> policies to use hash maps or something akin to Loki's AssocVector could
> be easily defined.

can you also separate the structure from the values. I.e is it possible 
to first define the structure and then afterwards assign the values to 
the corresponding positions? Does the interface also allow me to share 
the structure-information between multiple sparse vectors?

> 
> I'd like to know if people would be interested in seeing such a class in
> Boost before I plunge into writing up the documentation (which is
> currently pretty sparse, and consists primarily of the comments in the
> code) and finishing off all the test programs prior to submission.
> 

What a coincidence, I just started discussing the design of a 
sparse-vector on the glas mailing list 
(http://lists.boost.org/mailman/listinfo.cgi/glas). One of the questions 
that pops up: what should be the return-type of operator[](size_type) ?

toon

PS: I also cross-posted this to the glas-ml.