Algorithm Alley
by Erik Demaine

Listing One
template <class Element>
void ResizableArray<Element>::append (Element e) {
  // If the last nonempty data block is full, add a new block.
  if (elements_in_last_block >= last_block_size) {
    // If the last superblock is full, add a new superblock.
    if (blocks_in_last_superblock >= last_superblock_size) {
      num_superblocks++;
      // If the number of superblock is odd, double the number of 
      //                                    data blocks in a superblock.
      if (num_superblocks % 2 == 1)
        last_superblock_size *= 2;
      // Otherwise, double the number of elements in a data block.
      else
        last_block_size *= 2;
      // Set the occupancy of the last superblock to empty.
      blocks_in_last_superblock = 0;
    }
    // If there are no empty data blocks:
    if (! empty_block) {
      // If the index block is full, realloc it to twice its current size.
      if (num_blocks >= index_size)
        assert (index = (Block<Element> *) realloc (index, 
                              sizeof (Block<Element>) * (index_size *= 2)));
      // Allocate a new last data block, 
      //             and store a pointer to it in the index block.
      index[num_blocks].elements = 
                    new Element [index[num_blocks].size = last_block_size];
    } else
      empty_block = 0;
    // Increment the number of blocks in total and in this superblock.
    num_blocks++;
    blocks_in_last_superblock++;
    // Set the occupancy of the last data block to empty.
    elements_in_last_block = 0;
  }
  // Store the new element at the end of the last data block.
  index[num_blocks-1].elements[elements_in_last_block++] = e;
  num_elements++;
}


Listing Two
template <class Element>
ostream &operator<< (ostream &os, ResizableArray<Element> &array) {
  for (int block = 0; block < array.num_blocks - 1; block++)
    for (int i = 0; i < array.index[block].size; i++)
      os << array.index[block].elements[i] << endl;
  for (int i = 0; i < array.elements_in_last_block; i++)
    os << array.index[array.num_blocks-1].elements[i] << endl;
  return os;
}


Listing Three
#include <assert.h>
#include <stdlib.h>
#include <iostream>

template <class Element>
struct Block {
  Element *elements;
  int size;
};
template <class Element>
class ResizableArray {
 public:
  Block<Element> *index;
  int num_elements, index_size;
  int num_blocks, empty_block, elements_in_last_block, last_block_size;
  int num_superblocks, blocks_in_last_superblock, last_superblock_size;
 
  public:
  ResizableArray () {
    num_elements = elements_in_last_block = 0;
    assert (index = (Block<Element> *) 
                     malloc (sizeof (Block<Element>) * (index_size = 1)));
    index[0].elements = new Element [index[0].size = last_block_size = 1];
    num_blocks = num_superblocks = 1;
    empty_block = 0;
    blocks_in_last_superblock = last_superblock_size = 1;
  }
  void append (Element e);
  void shrink ();
  int length () const { return num_elements; }
  inline Element &operator[] (int i);
  friend ostream &operator<< <Element> (ostream &os, 
                                       ResizableArray<Element> &array);
};


Listing Four
template <class Element>
inline Element &ResizableArray<Element>::operator[] (int i) {
  assert (i < num_elements);
  int j = i + 1;
  int most_significant_1_index = find_most_significant_1_index (j);
  int most_significant_1 = 1 << most_significant_1_index;
  int half_ceiling = (most_significant_1_index + 1) >> 1;
  int two_power_half_ceiling_m1 = (1 << half_ceiling) - 1;
  return index[two_power_half_ceiling_m1 +
               (1 << most_significant_1_index - half_ceiling) - 1 +
              // part above is number of blocks before this superblock
               ((j ^ most_significant_1) >> half_ceiling)]
     .elements[j & two_power_half_ceiling_m1];
}


Listing Five
#ifdef __i386__
// Note: Return value is undefined for j == 0.
// Append the code "\n jnz 1f\n movl $-1,%0\n 1:" to support this case.
inline int find_most_significant_1_index (int j) {
  __asm__("bsrl %1,%0" :"=r" (j) :"r" (j));
  return j;
}
#endif // __i386__

Listing Six
#ifdef BINARY_SEARCH
// Assumes a 32-bit machine (or that j < 2^32), and that j != 0.
inline int find_most_significant_1_index (int j) {
  int new_j, r = 0;
  if ((new_j = j & 0xFFFF0000)) { r |= 16; j = new_j; }
  if ((new_j = j & 0xFF00FF00)) { r |=  8; j = new_j; }
  if ((new_j = j & 0xF0F0F0F0)) { r |=  4; j = new_j; }
  if ((new_j = j & 0xCCCCCCCC)) { r |=  2; j = new_j; }
  if (         j & 0xAAAAAAAA)    r |=  1;
  return r;
}
#endif // BINARY_SEARCH


Listing Seven
#ifdef LOOKUP
#define lookup_shift 16
#define lookup_mask ((1 << lookup_shift) - 1)

char lookup[lookup_mask + 1];
int lookup_init () {
  int most_significant_1_index = -1;
  int next_power_of_two = 1;
  for (int i = 0; i <= lookup_mask; i++) {
    if (i == next_power_of_two) {
      most_significant_1_index++;
      next_power_of_two <<= 1;
    }
    lookup[i] = most_significant_1_index;
  }
  return 0;
}
int lookup_garbage = lookup_init ();
// Assumes a 32-bit machine (or that j < 2^32).
inline int find_most_significant_1_index (int j) {
  int shifted_j;
# if lookup_shift == 16
    if ((shifted_j = j >> 16))
      return lookup[shifted_j] + 16;
    else
      return lookup[j];
# elif lookup_shift == 8
    if ((shifted_j = j >> 16)) {
      j = shifted_j;
      if ((shifted_j = j >> 8))
        return lookup[shifted_j] + 24;
      else
        return lookup[j] + 16;
    } else
      if ((shifted_j = j >> 8))
        return lookup[shifted_j] + 8;
      else
        return lookup[j];
# else
#   error Only lookup table shifts of 8 or 16 are currently supported.
# endif
}
#endif // LOOKUP


Listing Eight
template <class Element>
void ResizableArray<Element>::shrink () {
  // Remove element.
  assert (num_elements-- > 0);
  elements_in_last_block--;
  // If the last (but not first) data block is empty:
  if (elements_in_last_block <= 0 && num_blocks > 1) {
    // If there is another empty data block, deallocate it.
    if (empty_block)
      delete index[num_blocks].elements;
    else
      empty_block = 1;
    // If the index block is a quarter full, realloc it to half its size.
    if (num_blocks <= index_size / 4)
      assert (index = (Block<Element> *) realloc 
                    (index, sizeof (Block<Element>) * (index_size /= 2)));
    // Decrement number of data blocks in total and in this superblock.
    num_blocks--;
    blocks_in_last_superblock--;
    // If last (but not first) superblock is empty, remove it.
    if (blocks_in_last_superblock <= 0) {
      num_superblocks--;
      // If the number of superblocks is even, 
      //                halve the number of data blocks in a superblock.
      if (num_superblocks % 2 == 0)
        last_superblock_size /= 2;
      // Otherwise, halve the number of elements in a data block.
      else
        last_block_size /= 2;
      // Set the occupancy of the last superblock to full.
      blocks_in_last_superblock = last_superblock_size;
    }
    // Set the occupancy of the last data block to full.
    elements_in_last_block = last_block_size;
  }
}





4