package java.lang;

public class StringBuilder {
  private static final int BufferSize = 32;

  private Cell chain;
  private int length;
  private char[] buffer;
  private int position;

  public StringBuilder(String s) {
    append(s);
  }

  public StringBuilder(int capacity) { }

  public StringBuilder() {
    this(0);
  }

  private void flush() {
    if (position > 0) {
      char[] b = buffer;
      int p = position;
      buffer = null;
      position = 0;
      append(new String(b, 0, p, false));
      length -= p;
    }
  }

  public StringBuilder append(String s) {
    if (s == null) {
      return append("null");
    } else {
      if (s.length() > 0) {
        if (buffer != null && s.length() <= buffer.length - position) {
          s.getChars(0, s.length(), buffer, position);
          position += s.length();
        } else {
          flush();
          chain = new Cell(s, chain);
        }
        length += s.length();
      }
      return this;
    }
  }

  public StringBuilder append(char[] b, int offset, int length) {
    return append(new String(b, offset, length));
  }

  public StringBuilder append(Object o) {
    return append(o == null ? "null" : o.toString());
  }

  public StringBuilder append(char v) {
    if (buffer == null) {
      buffer = new char[BufferSize];
    } else if (position >= buffer.length) {
      flush();
      buffer = new char[BufferSize];
    }

    buffer[position++] = v;
    ++ length;

    return this;
  }

  public StringBuilder append(boolean v) {
    return append(String.valueOf(v));
  }

  public StringBuilder append(int v) {
    return append(String.valueOf(v));
  }

  public StringBuilder append(long v) {
    return append(String.valueOf(v));
  }

  public StringBuilder append(float v) {
    return append(String.valueOf(v));
  }

  public StringBuilder append(double v) {
    return append(String.valueOf(v));
  }


  public char charAt(int i) {
    if (i < 0 || i >= length) {
      throw new IndexOutOfBoundsException();
    }

    flush();

    int index = length;
    -- length;
    Cell p = null;
    for (Cell c = chain; c != null; c = c.next) {
      int start = index - c.value.length();
      index = start;
      
      if (i >= start) {
        return c.value.charAt(i - start);
      }
    }

    throw new RuntimeException();
  }

  public StringBuilder insert(int i, String s) {
    if (i < 0 || i >= length) {
      throw new IndexOutOfBoundsException();
    }

    if (i == length) {
      append(s);
    } else {
      flush();

      int index = length;
      -- length;
      for (Cell c = chain; c != null; c = c.next) {
        int start = index - c.value.length();
        index = start;
      
        if (i >= start) {
          if (i == start) {
            c.next = new Cell(s, c.next);
          } else {
            String v = c.value;
            c.value = v.substring(i - start, v.length());
            c.next = new Cell(s, new Cell(v.substring(0, i - start), c.next));
          }
          break;
        }
      }
    }

    return this;
  }

  public StringBuilder insert(int i, char c) {
    return insert(i, new String(new char[] { c }, 0, 1, false));
  }

  public StringBuilder delete(int start, int end) {
    if (start >= end) {
      return this;
    }

    if (start < 0 || end > length) {
      throw new IndexOutOfBoundsException();
    }

    flush();

    int index = length;
    -- length;
    Cell p = null;
    for (Cell c = chain; c != null; c = c.next) {
      int e = index;
      int s = index - c.value.length();
      index = s;
      
      if (end >= e) {
        if (start <= s) {
          if (p == null) {
            chain = c.next;
          } else {
            p.next = c.next;
          }          
        } else {
          c.value = c.value.substring(0, start - s);
          break;
        }
      } else {
        if (start <= s) {
          c.value = c.value.substring(end - s, e - s);
        } else {
          String v = c.value;
          c.value = v.substring(end - s, e - s);
          c.next = new Cell(v.substring(0, start - s), c.next);
          break;
        }        
      }
    }

    return this;
  }

  public StringBuilder deleteCharAt(int i) {
    return delete(i, i + 1);
  }

  public StringBuilder replace(int start, int end, String str) {
    delete(start, end);
    insert(start, str);
    return this;
  }

  public int length() {
    return length;
  }

  public void setLength(int v) {
    if (v < 0) {
      throw new IndexOutOfBoundsException();
    }

    if (v == 0) {
      length = 0;
      chain = null;
      return;
    }

    flush();

    int index = length;
    length = v;
    for (Cell c = chain; c != null; c = c.next) {
      int start = index - c.value.length();

      if (v > start) {
        if (v < index) {
          c.value = c.value.substring(0, v - start);
        }
        break;
      }

      chain = c.next;
      index = start;
    }
  }

  public void getChars(int srcOffset, int srcLength, char[] dst, int dstOffset)
  {
    if (srcOffset < 0 || srcOffset + srcLength > length) {
      throw new IndexOutOfBoundsException();
    }

    flush();

    int index = length;
    for (Cell c = chain; c != null; c = c.next) {
      int start = index - c.value.length();
      int end = index;
      index = start;

      if (start < srcOffset) {
        start = srcOffset;
      }

      if (end > srcOffset + srcLength) {
        end = srcOffset + srcLength;
      }

      if (start < end) {
        c.value.getChars(start - index, end - start,
                         dst, dstOffset + (start - srcOffset));
      }
    }
  }

  public String toString() {
    char[] array = new char[length];
    getChars(0, length, array, 0);
    return new String(array, 0, length, false);
  }

  private static class Cell {
    public String value;
    public Cell next;

    public Cell(String value, Cell next) {
      this.value = value;
      this.next = next;
    }
  }
}

@@ -385,148 +385,109 @@
  cha
-r%5B%5D b = buffer;%0A      int p = position;%0A      buffer = null;%0A      position = 0;%0A      append(new String(b, 0, p, false));%0A      length -= p
+in = new Cell(new String(buffer, 0, position, false), chain);%0A      buffer = null;%0A      position = 0
 ;%0A  
@@ -2004,39 +2004,24 @@
 x = length;%0A
-    -- length;%0A
     Cell p =
@@ -2501,25 +2501,8 @@
 th;%0A
-      -- length;%0A
     
@@ -2947,32 +2947,61 @@
        %7D%0A      %7D
+%0A%0A      length += s.length();
 %0A    %7D%0A%0A    retu
@@ -3364,23 +3364,8 @@
 th;%0A
-    -- length;%0A
     
@@ -4082,32 +4082,62 @@
 %0A      %7D%0A    %7D%0A%0A
+    length -= (end - start);%0A%0A
     return this;

fix length tracking bugs in StringBuilder