I'm almost convinced now that the paper is incorrect.  The code below gives me the appropriate index into the index array and the offset into the data block.  That being said, remember when I mentioned that this will include a bit more work to access an element than a simple bit shift and a bit mask?  Well this is more than a bit more - we'll be doing this each time an index is requested.  I'll spend some time trying to twiddle the bits to see if I can eliminate/combine some of the operations.<br>
<br>        for (int r = 1; r < 33; r++) {<br>            int k = lg(r);<br>            int floorKO2 = k >> 1;<br>            int powFloorKO2 = (1 << floorKO2);<br>            int p = ((1 << floorKO2) - 1) << 1;<br>
            int ceilKO2;<br>            if ((k & 1) == 1) {<br>                ceilKO2 = floorKO2 + 1;<br>                p += powFloorKO2;<br>            } else {<br>                ceilKO2 = floorKO2;<br>            }<br>
            int e = r & ((1 << ceilKO2) - 1);<br>            int b = (r >> ceilKO2) & (powFloorKO2 - 1);<br><br>            System.out.println((r - 1) + " " + (p + b) + " " + e);<br>
        }<br><br>Kevin<br><br><div class="gmail_quote">On Wed, Mar 31, 2010 at 7:08 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;">
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.<div><div></div><div class="h5"><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" target="_blank">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><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>
</div></div></blockquote></div><br>