/// SinkWorld split buffer class
/// Copyright 2001 Neil Hodgson
/// All implementations use the intrinsic char type which is 1 byte 
/// in C++ and 2 bytes in Java and C#.

class cbx {
private:
    char *body;
    int size;
    int length;
    int part1Length;
    int gapLength;
    int growSize;

    /// Move the gap to a particular position so that insertion and 
    /// deletion at that point will not require much copying and 
    /// hence be fast.
    void GapTo(int position) {
        if (position != part1Length) {
            if (position < part1Length) {
                int diff = part1Length - position;
                for (int i = 0; i < diff; i++)
                    body[part1Length + gapLength - i - 1] = 
                        body[part1Length - i - 1];
            } else {    // position > part1Length
                int diff = position - part1Length;
                for (int i = 0; i < diff; i++)
                    body[part1Length + i] = 
                        body[part1Length + gapLength + i];
            }
            part1Length = position;
        }
    }

    /// Reallocate the storage for the buffer to be newSize and 
    /// copy exisiting contents to the new buffer.
    /// Must not be used to decrease the size of the buffer.
    void ReAllocate(int newSize) {
        // Move the gap to the end
        GapTo(length);
        char *newBody = new char[newSize];
        if (size != 0) {
            for (int i = 0; i < size; i++)
                newBody[i] = body[i];
            delete []body;
        }
        body = newBody;
        gapLength += newSize - size;
        size = newSize;
    }

    /// Check that there is room in the buffer for an insertion, 
    /// reallocating if more space needed.
    void RoomFor(int insertionLength) {
        if (gapLength <= insertionLength) {
            if (growSize * 6 < size)
                growSize *= 2;
            ReAllocate(size + insertionLength + growSize);
        }
    }

public:
    /// Construct a split buffer.
    cbx(int initialLength, int growSize_) {
        growSize = growSize_;
        size = 0;
        length = 0;
        part1Length = 0;
        gapLength = 0;
        ReAllocate(initialLength);
    }

    ~cbx() {
        delete []body;
        body = NULL;
    }

    /// Retrieve the character at a particular position.
    /// Retrieving positions outside the range of the buffer works 
    /// and returns 0.
    char CharAt(int position) {
        if (position < part1Length) {
            if (position < 0) {
                return '\0';
            } else {
                return body[position];
            }
        } else {
            if (position >= length) {
                return '\0';
            } else {
                return body[gapLength + position];
            }
        }
    }

    /// Retrieve the length of the buffer.
    int Length() {
        return length;
    }

    /// Retrieve a range of text from the buffer.
    /// Retrieving positions outside the range of the buffer fails.
    void RetrieveString(int position, char s[], int retrieveLength) {
        int i = 0;
        int pos = position;
        while ((i < retrieveLength) && (pos < part1Length)) {
            s[i++] = body[pos++];
        }
        while (i < retrieveLength) {
            s[i++] = body[gapLength + pos++];
        }
    }

    /// Insert text into the buffer.
    /// Inserting at positions outside the current range throws a
    /// BadPositionException.
    void InsertString(int position, char s[], int insertLength) {
        if (insertLength > 0) {
            if ((position < 0) || (position > length)) {
                throw new BadPositionException();
            }
            RoomFor(insertLength);
            GapTo(position);
            for (int i = 0; i < insertLength; i++)
                body[part1Length + i] = s[i];
            length += insertLength;
            part1Length += insertLength;
            gapLength -= insertLength;
        }
    }

    /// Fill an already allocated range with a value.
    /// Modifying outside the current range throws a
    /// BadPositionException.
    void FillRange(int position, char ch, int fillLength) {
        if (fillLength > 0) {
            if ((position < 0) || ((position + fillLength) > length)) {
                throw new BadPositionException();
            }
            int i = 0;
            int pos = position;
            while ((i < fillLength) && (pos < part1Length)) {
                body[pos++] = ch;
                i++;
            }
            while (i < fillLength) {
                body[gapLength + pos++] = ch;
                i++;
            }
        }
    }

    /// Insert a number of zero characters into the buffer.
    /// Inserting at positions outside the current range fails.
    void InsertZeros(int position, int insertLength) {
        if (insertLength > 0) {
            RoomFor(insertLength);
            GapTo(position);
            for (int i = 0; i < insertLength; i++)
                body[part1Length + i] = '\0';
            length += insertLength;
            part1Length += insertLength;
            gapLength -= insertLength;
        }
    }

    /// Delete a range from the buffer.
    /// Deleting positions outside the current range fails.
    void DeleteChars(int position, int deleteLength) {
        if (deleteLength > 0) {
            GapTo(position);
            length -= deleteLength;
            gapLength += deleteLength;
        }
    }
};