www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.dtl - MinTL dmd-119 update and arraylist enhancement

reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
I've updated MinTL to work with dmd-119, though there could be a problem 
with MultiAA, which is an alias for Value[][Key]. The unittest fails when I 
try to concatenate onto the end of the Value[] array and set that back into 
the AA. I don't know what is going on with that so I'll have to check it out 
when I get more time.

I also added some functions to ArrayList to allow it to be used like an 
array with capacity. I added the new read/write property capacity and added 
a setter for length. For those who don't know MinTL an ArrayList is an array 
with efficient insert/delete from the head and tail. Basically it is a 
circular array. By keeping the head at 0 it becomes an array with capacity. 
I decided the tradeoff of reusing ArrayList is better than inventing a whole 
new type for tracking capacity.

Available from the usual place http://home.comcast.net/~benhinkle/mintl/
Mar 23 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Ben Hinkle" <ben.hinkle gmail.com> wrote in message 
news:d1tdnp$109m$1 digitaldaemon.com...

 I've updated MinTL to work with dmd-119, though there could be a problem 
 with MultiAA, which is an alias for Value[][Key]. The unittest fails when 
 I try to concatenate onto the end of the Value[] array and set that back 
 into the AA. I don't know what is going on with that so I'll have to check 
 it out when I get more time.


posted bug report with AAs indexed by double.


 I also added some functions to ArrayList to allow it to be used like an 
 array with capacity. I added the new read/write property capacity and 
 added a setter for length. For those who don't know MinTL an ArrayList is 
 an array with efficient insert/delete from the head and tail. Basically it 
 is a circular array. By keeping the head at 0 it becomes an array with 
 capacity. I decided the tradeoff of reusing ArrayList is better than 
 inventing a whole new type for tracking capacity.


After mulling over some MinTL behaviors that had grown to bug me, I've made 
some changes that break backwards compatibility. They are
1) removed seq and util modules and moved the contents elsewhere. Results in 
fewer modules needed to do basic stuff
2) made ArrayList resize automatically instead of throwing an error when the 
backing array is full
3) switched all (integer) indexing and length to use size_t instead of ints 
and uints.

I've update the zip file with these changes.
Mar 26 2005
parent reply bug d.com writes:
Should the following two commonly used methods be added into mintl/list.d ?

Value first() { return head.data; }
Value last()  { return tail.data; }
Mar 26 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
<bug d.com> wrote in message news:d25bth$174i$1 digitaldaemon.com...

 Should the following two commonly used methods be added into mintl/list.d 
 ?

 Value first() { return head.data; }
 Value last()  { return tail.data; }


Maybe, but the same thing is x[0] and x[x.length-1], just like arrays. 
Typing ".last" is shorter than "[x.length-1]" but that is the only advantage 
I can see and that wasn't enough of an advantage to me to add them. But I'll 
think about it.
Mar 27 2005
parent reply bug d.com writes:
In article <d26a9f$26cr$1 digitaldaemon.com>, Ben Hinkle says...

<bug d.com> wrote in message news:d25bth$174i$1 digitaldaemon.com...

 Should the following two commonly used methods be added into mintl/list.d 
 ?

 Value first() { return head.data; }
 Value last()  { return tail.data; }


Maybe, but the same thing is x[0] and x[x.length-1], just like arrays. 
Typing ".last" is shorter than "[x.length-1]" but that is the only advantage 
I can see and that wasn't enough of an advantage to me to add them. But I'll 
think about it. 


I think in the implementation, the actual pointer to head/tail is cached, so
x[0] take same time as first(), but x[x.length-1] will take O(N) instead of
O(1)!
Mar 27 2005
parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
<bug d.com> wrote in message news:d26v7a$2rdm$1 digitaldaemon.com...

 In article <d26a9f$26cr$1 digitaldaemon.com>, Ben Hinkle says...

<bug d.com> wrote in message news:d25bth$174i$1 digitaldaemon.com...

 Should the following two commonly used methods be added into 
 mintl/list.d
 ?

 Value first() { return head.data; }
 Value last()  { return tail.data; }


Maybe, but the same thing is x[0] and x[x.length-1], just like arrays.
Typing ".last" is shorter than "[x.length-1]" but that is the only 
advantage
I can see and that wasn't enough of an advantage to me to add them. But 
I'll
think about it.


 I think in the implementation, the actual pointer to head/tail is cached, 
 so
 x[0] take same time as first(), but x[x.length-1] will take O(N) instead 
 of
 O(1)!


For doubly-linked lists the length is cached, too. So to look up x[n] it 
starts from the head if n < length/2 and the tail if n > length/2. For 
singly-linked lists the length isn't cached and so there is the property 
tailList that returns a single-item slice for the tail item.
Mar 27 2005