Coding under the Influence

No, I wasn't drunk, my mind was just under the influence of being happy to code again. It's been really hard for me to spend so much time doing nothing but get ready to code.

This is another little anomaly which happened, though I'm not quite sure how it came to be.

module tango.util.collection.ArrayStack;

// written 20080122135351 PST
// by Chris Miller (lord Sauron the Great {at} gmail {dot} com)

/**
* Implementation of an stack data structure using an array.  This
* implementation is auto-balancing and will shift itself to the front
* of its array to prevent runaway memory useage.  It does this during
* its routine ensure capacity routine.  It will also shrink its array
* size in the event that its internal array becomes inordinately larger
* than its current storage requirements.
*/
public class ArrayStack(K) {

  // l_bound = left bound = the first element
  // r_bound = right bound = the last element
  uint l_bound=0, r_bound=0;

  K[] data;

  /**
   * Default constructor; constructs a brand new ArrayStack just for you!
   * It begins with room for five (5) elements.  Obviously it can grow as
   * needed.
   */
  public ArrayStack() { this(5); }

  /**
   * Custom constructor; constructs a brand new ArrayStack just for you!
   * It begins with room for uint size elements.
   */
  public ArrayStack(uint size) {
      assert(size!=0);
      ensureCapacity(size);
  } // public ArrayStack(uint size)

  /**
   * Utility to ensure that the ArrayStack has room for uint capacity
   * number of elements.  It will also perform a rebalance should it have
   * enough space allocated but unavailable because it's stuck at the
   * wrong end of the array.
   *
   * Please note that it is not a good idea to ensure a capactiy greater
   * than four times the current because it will assume on the next
   * push that it needs to shrink itself to prevent memory abuse.
   */
  public void ensureCapacity(uint capacity) {
      assert(capacity>=r_bound-l_bound);
      if(data.length>=capacity) {
          // shrink if we're grossly over-large
          if(data.length>=capacity*4ui) {
              // simply create a new array, let the garbage men
              K[capacity] new_data=data[l_bound..r_bound];
              data=new_data;
              return;
          // if the space left on the back of the stack and the
          // space already taken in the array minus the null
          // space on the front of the array is
          // greater or equal to the desired capacity...
          if(data.length-r_bound+(r_bound-l_bound)>=capacity)
              return;
          else rebalance();
      } // if(data.length>=capacity)
      K[capacity] new_data;
      /* for(uint i=0; i!=r_bound-l_bound; i++)
          new_data[i]=data[i+l_bound]; */
      new_data[0..r_bound-l_bound] = data[l_bound..r_bound];
      data=new_data;
      r_bound-=l_bound; // make r_bound compensate for space at the
      // beginning of the array that is no longer taken
      l_bound=0;
  } // public void ensureCapacity(uint capacity)

  public K pop() {
      if(r_bound-l_bound==0) // empty stack
          return null;
      return data[l_bound++];
  } // public K pop()

  public void rebalance() {
      if(l_bound==0) return;
      if(r_bound-l_bound==0) {
          l_bound=0;
          r_bound=0;
          return;
      } // if (r_bound-l_bound==0)
      for(uint i=0; i!=r_bound-l_bound; i++)
          data[i]=data[l_bound+i];
      r_bound-=l_bound;
      l_bound=0;
  } // public void rebalance()

  public K peek() {
      if(r_bound-l_bound!=0)
          return data[l_bound];
      return null;
  }

  public void push(K e) {
      if(data.length-r_bound==0)
          ensureCapacity(data.length*1.5f);
      data[r_bound++]=e;
  } // public void push(K e)

} // class ArrayStack(K)

What's wrong? If you look closely it re balances itself to the front of the array. What's up with that? At the first push call it's going to have to move the whole dang data block over one. Actually, I think it might just do the dumb thing and shift it over zero places and then overwrite the first element. I only caught the error while reading over the code

I think I was really trying to create a queue, which is quite humorous to me. This is the second time I've tried to write one data structure and ended up writing something completely different. I really need to do this when I have more cylinders firing. But hey, at least it gives you some humorous code to read through. I tend to think it's really nice code, if only it'd work. I think I'll just throw the whole thing out and start anew. I know so much more about D now that I really think I could do a much better job with a fresh start.