RE: [sv-ec] Mantis 1702 - queue concatenation

From: Steven Sharp <sharp_at_.....>
Date: Mon Nov 19 2007 - 19:32:53 PST
>From: "Jonathan Bromley" <jonathan.bromley@doulos.com>
>
>> DOUG: Don't forget "associative" in that little list.
>> There are four kinds of unpacked arrays:
>> queue, dynamic, fixed-size, and associative.
>
>Yes, but I'll need a little help with how to define that.
>
>The fact that their indices are keys, and therefore may 
>lack any inherent or obvious ordering, makes trouble when 
>copying *from* an associative array to another kind.
>The lack of keys in any other kind of array presumably
>makes it impossible to copy *to* an associative array
>from anything that's not of equivalent type.  So I was
>anticipating special treatment for associative arrays.
>
>Any better or more specific ideas?  Please?

I agree that associative arrays are quite different from the
others.

The subset of associative arrays that are indexed by int or
smaller integral types could be treated much like the others.
However, I am not convinced that this is a good idea.

To do this, you would regard the associative array as a
sparse representation of a normal array.  The keys would
just correspond to addresses in the normal array.  The
copy operation would be equivalent to iterating through
the address range and reading from one kind of array and
writing to the other.  

So a copy from a fixed array to an associative array would
result in a set of consecutive keys from the lowest to the
highest address in the fixed array.  A copy from an associative
array to a fixed array would result in the data associated with
keys being written into the addresses corresponding to those
keys.  All other elements in the array would have the default
uninitialized value for the element type.

After the copy, a read from a given index in either array
would give the same value, which is what you would expect after
a copy.  However, the new copy would require more space to
represent than the original, perhaps vastly so in a copy from
an associative array to another type.

It is not clear what bounds the associative array would be
considered to have.  It could be the smallest to largest possible
value for the index type, or the smallest to largest index value
actually present in the array.  The first would mean that all
associative arrays with int indexes would create 4 billion element
arrays when assigned to a dynamic array or queue, which would be
excessive.  The second would mean that the size would depend on
what was in the array, making it hard to copy to a fixed array
unless you knew at when writing your code what the largest and
smallest values in the associative array were going to be.

Just because these could be treated as equivalent in this limited
case does not mean that they should be.  I don't see a lot of
advantage to it.  The reason to use an associative array with an
integral index is because it is impractical to use another type of
array, because the data is sparse and would take too much space
in another type of array.

From what you wrote, it sounds like you were thinking of a less
exact definition of copying.  For example, taking an associative
array with N keys and extracting it into an array with N elements
numbered 0:N-1 in the original order, but losing the actual key
values.  That might be a more practical operation, but isn't really
copying.

I think that associative arrays should be treated as distinct from
the other array types.  If someone really wants to copy values
from one to the other, they can always write the code to do so.
Then they can decide how they want it done, and deal with the
cost of doing so, which is more obvious in the explicit coding.

Steven Sharp
sharp@cadence.com


-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.
Received on Mon, 19 Nov 2007 22:32:53 -0500 (EST)

This archive was generated by hypermail 2.1.8 : Mon Nov 19 2007 - 19:33:50 PST