// CharBuffer.cs // // Copyright (C) 2003-2004 Ryan Seghers // // This software is provided AS IS. No warranty is granted, // neither expressed nor implied. USE THIS SOFTWARE AT YOUR OWN RISK. // NO REPRESENTATION OF MERCHANTABILITY or FITNESS FOR ANY // PURPOSE is given. // // License to use this software is limited by the following terms: // 1) This code may be used in any program, including programs developed // for commercial purposes, provided that this notice is included verbatim. // // Also, in return for using this code, please attempt to make your fixes and // updates available in some way, such as by sending your updates to the // author. using System; namespace RTools_NTS.Util { /// <summary> /// Buffer for characters. This approximates StringBuilder /// but is designed to be faster for specific operations. /// This is about 30% faster for the operations I'm interested in /// (Append, Clear, Length, ToString). /// This trades off memory for speed. /// </summary> /// <remarks> /// <para>To make Remove from the head fast, this is implemented /// as a ring buffer.</para> /// <para>This uses head and tail indices into a fixed-size /// array. This will grow the array as necessary.</para> /// </remarks> public class CharBuffer { #region Fields int capacity = 128; char[] buffer; int headIndex; // index of first char int tailIndex; // index 1 past last char #endregion #region Properties /// <summary> /// Gets/Sets the number of characters in the character buffer. /// Increasing the length this way provides indeterminate results. /// </summary> public int Length { get { return(tailIndex - headIndex); } set { tailIndex = headIndex + value; if (tailIndex >= capacity) throw new IndexOutOfRangeException("Tail index greater than capacity"); } } /// <summary> /// Returns the capacity of this character buffer. /// </summary> public int Capacity { get { return(capacity); } } #endregion #region Constructors /// <summary> /// Default constructor. /// </summary> public CharBuffer() { buffer = new char[capacity]; } /// <summary> /// Construct with a specific capacity. /// </summary> /// <param name="capacity"></param> public CharBuffer(int capacity) { this.capacity = capacity; buffer = new char[capacity]; } #endregion #region Non-Public Methods /// <summary> /// Reallocate the buffer to be larger. For the new size, this /// uses the max of the requested length and double the current /// capacity. /// This does not shift, meaning it does not change the head or /// tail indices. /// </summary> /// <param name="requestedLen">The new requested length.</param> protected void Grow(int requestedLen) { int newLen = Math.Max(capacity*2, requestedLen); newLen = Math.Max(newLen, 16); char[] newBuffer = new char[newLen]; Array.Copy(buffer, 0, newBuffer, 0, capacity); buffer = newBuffer; capacity = newLen; } /// <summary> /// Ensure that we're set for the requested length by /// potentially growing or shifting contents. /// </summary> /// <param name="requestedLength"></param> protected void CheckCapacity(int requestedLength) { if (requestedLength + headIndex >= capacity) { // have to do something if ((requestedLength + headIndex > (capacity >> 1)) && (requestedLength < capacity - 1)) { // we're more than half-way through the buffer, and shifting is enough // so just shift ShiftToZero(); } else { // not far into buffer or shift wouldn't be enough anyway Grow(0); } } } /// <summary> /// Move the buffer contents such that headIndex becomes 0. /// </summary> protected void ShiftToZero() { int len = Length; for (int i = 0; i < len; i++) { buffer[i] = buffer[i + headIndex]; } headIndex = 0; tailIndex = len; } #endregion #region Public Methods and Indexer /// <summary> /// Overwrite this object's underlying buffer with the specified /// buffer. /// </summary> /// <param name="b">The character array.</param> /// <param name="len">The number of characters to consider filled /// in the input buffer.</param> public void SetBuffer(char[] b, int len) { capacity = b.Length; buffer = b; headIndex = 0; tailIndex = len; } /// <summary> /// Append a character to this buffer. /// </summary> /// <param name="c"></param> public void Append(char c) { if (tailIndex >= capacity) CheckCapacity(Length + 1); buffer[tailIndex++] = c; } /// <summary> /// Append a string to this buffer. /// </summary> /// <param name="s">The string to append.</param> public void Append(string s) { if (s.Length + tailIndex >= capacity) CheckCapacity(Length + s.Length); for(int i = 0; i < s.Length; i++) buffer[tailIndex++] = s[i]; } /// <summary> /// Append a string to this buffer. /// </summary> /// <param name="s">The string to append.</param> public void Append(CharBuffer s) { if (s.Length + tailIndex >= capacity) CheckCapacity(Length + s.Length); for(int i = 0; i < s.Length; i++) buffer[tailIndex++] = s[i]; } /// <summary> /// Remove a character at the specified index. /// </summary> /// <param name="i">The index of the character to remove.</param> /// <returns></returns> public void Remove(int i) { Remove(i, 1); } /// <summary> /// Remove a specified number of characters at the specified index. /// </summary> /// <param name="i">The index of the characters to remove.</param> /// <param name="n">The number of characters to remove.</param> public void Remove(int i, int n) { n = Math.Min(n, Length); if (i == 0) { headIndex += n; } else { Array.Copy(buffer, i + headIndex + n, buffer, i + headIndex, tailIndex - (i + headIndex + n)); } } /// <summary> /// Find the first instance of a character in the buffer, and /// return its index. This returns -1 if the character is /// not found. /// </summary> /// <param name="c">The character to find.</param> /// <returns>The index of the specified character, or -1 /// for not found.</returns> public int IndexOf(char c) { for (int i = headIndex; i < tailIndex; i++) { if (buffer[i] == c) return(i - headIndex); } return(-1); } /// <summary> /// Empty the buffer. /// </summary> public void Clear() { headIndex = 0; tailIndex = 0; } /// <summary> /// Indexer. /// </summary> public char this [int index] { get { return(buffer[index + headIndex]); } set { buffer[index + headIndex] = value; } } /// <summary> /// Return the current contents as a string. /// </summary> /// <returns>The new string.</returns> public override String ToString() { return(new String(buffer, headIndex, tailIndex - headIndex)); } #endregion } }