"Rene Rivera" <grafik.list@redshift-software.com> wrote in message news:447CACE0.20907@redshift-software.com...
Maarten Kronenburg wrote:
Rene, In the meantime the get_sub has been added for bit access, see below.
Yes, I saw that before I sent the email. Hence I don't think it's sufficient.
This is not an iterator, but it may be sufficient for access of the binary representation. Is this also usefull for you?
size_type highest_bit() const; Complexity: O(N)
size_type lowest_bit() const; Complexity: O(N)
const integer get_sub( size_type startbit, size_type nbits ) const; Complexity: O(N)
There are a few problems with using those for "binary" access:
* It is not optimal. Using the above would result in an O(N^2) algo for something that most of the time would be an O(1) operation (depending on the internal representation, at worse would be O(N)).
The get_sub of one bit or byte is O(1), but as the maximum is the whole integer, it is specified as O(N).
* The representation that get_sub, highest_bit, lowest_bit, operate on is not defined. I don't see such a definition in the document either, AFAICT. So one couldn't even use the faster "int x = to_int(I.get_sub(0,16));"
The representation is a sign and the binary representation of the absolute value. That is what is mentioned in the design decisions. But now I will add it as a requirement, because indeed otherwise get_sub is undefined.
I don't care that much what the form of access looks like. The important aspect is having a *defined representation* that users can convert to and from. For example other access methods might be:
// Iterators, like std::string::data: std::pair<word_type const *, word_type const *> integer::data() const;
// Inserter, like std::string::copy: template <typename OutputIterator> void integer::copy(OutputIterator) const;
// Stream like: template <typename Container> operator << (Container &, integer const &);
Of course there would need to be a corresponding constructor to have the data round trip.
But what should the iterator iterate over? Bits? Bytes? In my opinion get_sub of a bit or byte or whatever, with a converter like to_unsigned_int, gives you the O(1) access you require. Perhaps the user can define an iterator based on get_sub. As mentioned I will add to the requirements that the sign and the binary representation of the absolute value should be stored separately, which defines the behaviour of get_sub. Is this what you require?
-- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo _______________________________________________ Unsubscribe & other changes: