From: "Mauricio Fernández" <batsman.geo@...>
Date: 2004-05-21T17:30:54+09:00
Subject: Re: Ruby's builtin Datastructures

On Fri, May 21, 2004 at 07:23:47AM +0900, Charles Comstock wrote:
> How much does it cost for an array access in the middle? 

O(1), since an Array is implemented as a C array of VALUEs.

> Why does it cost order(n) to remove the tail?  Why doesn't it float
> backwards until it needs memory ahead of it for instance? 

Array uses internally an array of VALUEs, array->ptr.
When you unshift a VALUE, it has to be inserted at array->ptr[0]; all
elements must be shifted, hence O(n). You cannot just do array->ptr--
since you'd fall outside the malloc()ed area.

> I'd be curious to now a bit more of about 
> this, as well as how the other datastructures are implemented.

I recommend you read the sources, they are very easy to follow.  For
instance, to see how unshift is implemented, just look at array.c, and
scroll down to the method definition to find the associated C function.
   rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
                                          ================

-- 
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

baz bat bamus batis bant.
	-- James Troup