Library Development: What to finish/flesh out?

[spir]

On 03/17/2011 11:25 PM, dsimcha wrote:
> On 3/17/2011 6:18 PM, spir wrote:
>> I'd have much use for both below.
>>
>> On 03/17/2011 04:33 PM, dsimcha wrote:
>>> 1. Rational: A library for handling rational numbers exactly.
>>> Templated on
>>> integer type, can use BigInts for guaranteed accuracy, or fixed-width
>>> integers
>>> for more speed where the denominator and numerator will be small.
>>> Completion
>>> state: Mostly finished. Just need to fix a litte bit rot and submit for
>>> review. (Phobos candidate)
>>
>> For decimal exactitude, what about plain fixed point (with decimal
>> factor and binary mantissa)?
>>
>
> I wouldn't mind having this, but I see it as completely orthogonal to rational
> numbers and don't have any near-term intentions of implementing it.

Right.

>>> 2. RandAA: A hash table implementation with deterministic memory
>>> management,
>>> based on randomized probing. Main advantage over builtin AAs is that
>>> it plays
>>> much nicer with the GC and multithreaded programs. Lookup times are also
>>> expected O(1) no matter how many collisions exist in modulus hash
>>> space, as
>>> long as there are few collisions in full 32- or 64-bit hash space.
>>> Completion
>>> state: Mostly finished. Just needs a little doc improvement, a few
>>> benchmarks and submission for review. (Phobos candidate)
>>
>> How complicated would it be to add (optional) support for keeping
>> insertion order (for iteration only)? Thought at a // array with
>> pointers to the cells holding key/value pairs.
>
> It's a good idea, but IMHO something like this should be templated on the type
> of the associative array and work with builtin AAs, etc., too. It should be a
> decorator or something:
>
> /**
> Wraps any type that conforms to the duck interface of an associative
> array to preserve ordering for iteration.
> */
> struct OrderedAA(AA) {
> alias typeof(AA.init.keys.front) K;
> alias typeof(AA.init.values.front) V;
> K[] order;
> AA aa;
>
> void opIndexAssign(V val, K key) {
> if(!(key in aa)) {
> order ~= key;
> }
>
> aa[key] = val;
> }
>
> // opApply, etc.
> }

Right too. But the reason I have not implemented it yet is I don't want to keep 
a // array of keys, which require AA lookup for each key. Instead, I thought at 
an array of pointers to where the (key:value) cells are stored (cell 
"buckets"), to avoid AA key lookups. This, I guess, requires tweaking the 
implementation of the actual data structure. Reason why I asked you as you are 
dfevelopping a new one (so, you may have such a use case in mind before design 
is frozen).
I have not yet had a look at the implementation of builtin AAs to see whether 
this would be easy. I guess not: it just require catching the very moment where 
a new pair is placed into a given bucket corresponding to its hash value. (And 
possibly the same thing at re-hash time.)

Denis
-- 
_________________
vita es estrany
spir.wikidot.com