I realize that 2 * (2^(k/2) - 1) only works for even numbered superblocks, the odd numbered superblocks need an additional term added (the number of data blocks in SB_[k-1]) to jive with my interpretation; anyhow, I also came across an alternative characterization of superblock in the paper which states that data blocks are grouped within a superblock when they are the same size - to me, though, that implies that my example structure below would be<br>
<br>SB_0: [1]<br>SB_1: [2][2][2]<br>SB_2: [4][4][4][4][4][4]<br><br>which seems to contradict my understanding of (1) below.  I must be reading this upside down.<br><br><div class="gmail_quote">On Wed, Mar 31, 2010 at 6:36 PM, Kevin L. Stern <span dir="ltr"><<a href="mailto:kevin.l.stern@gmail.com">kevin.l.stern@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">What am I missing here?  In "Resizable arrays in optimal time and space" the authors define their data structure with the following property:<br>
<br>(1)  "When superblock SB_k is fully allocated, it consists of 2^(floor(k/2)) data blocks, each of size 2^(ceil(k/2))."<br>
<br>Since the superblock is zero-based indexed this implies the following structure:<br><br>SB_0: [1]<br>SB_1: [2]<br>SB_2: [2][2]<br>SB_3: [4][4]<br>SB_4: [4][4][4][4]<br>[...]<br><br>Let's have a look at Algorithm 3, Locate(i), with i = 3:<br>

<br>r = 100 (the binary expansion of i + 1)<br>k = |r| - 1 = 2<br>p = 2^k - 1 = 3<br><br>What concerns me is their statement that p represents "the number of data blocks in superblocks prior to SB_k."  There are only two data blocks in superblocks prior to SB_2, not three.  Given (1) above, unless I'm misinterpreting it, the number of data blocks in superblocks prior to SB_k should be:<br>

<br>2 * Sum[i=0->k/2-1] 2^i = 2 * (2^(k/2) - 1)<br><br>This, of course, seems to work out much better in my example above, giving the correct answer to my interpretation of their data structure, but I have a hard time believing that this is their mistake rather than my misinterpretation.<br>

<br>Thoughts?<br><font color="#888888"><br>Kevin</font><div><div></div><div class="h5"><br><br><div class="gmail_quote">On Tue, Mar 30, 2010 at 5:20 PM, Martin Buchholz <span dir="ltr"><<a href="mailto:martinrb@google.com" target="_blank">martinrb@google.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div>On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern <<a href="mailto:kevin.l.stern@gmail.com" target="_blank">kevin.l.stern@gmail.com</a>> wrote:<br>
> Hi Martin,<br>
><br>
> Thanks much for your feedback.  The first approach that comes to mind to<br>
> implement O(1) time front as well as rear insertion is to create a cyclic<br>
> list structure with a front/rear pointer - to insert at the front requires<br>
> decrementing the front pointer (modulo the size) and to insert at the rear<br>
> requires incrementing the rear pointer (modulo the size).  We need to resize<br>
> when the two pointers bump into each other.  Could you explain more about<br>
> your suggestion of introducing an arraylet that is shared by the front and<br>
> the rear?<br>
<br>
</div>It was a half-baked idea - I don't know if there's a way to turn it into<br>
something useful.  I was thinking of the ArrayDeque implementation,<br>
where all the elements live in a single array.<br>
<div><br>
>  It's not clear to me how that would help and/or be a better<br>
> approach than the cyclic list.  Anyhow, the paper that you reference,<br>
> "Resizable arrays in optimal time and space", gives a deque so if we take<br>
> that approach then the deque is specified.<br>
<br>
</div>Technically, ArrayList also supports the Deque operations -<br>
just not efficiently.<br>
</blockquote></div><br>
</div></div></blockquote></div><br>