using System;
using System.Collections.Generic;

namespace App
{

#region LineStorage
abstract class LineStorage
{
  public abstract int LineCount { get; }

  public abstract void CharToLine(int charIndex, out int line, out int column);
  public abstract void GetLineInfo(int line, out int offset, out int length);
  public abstract int GetLineLength(int line);

  public void AddLine(int length)
  {
    InsertLine(LineCount, length);
  }

  public abstract void AlterLine(int line, int newLength);
  public abstract void InsertLine(int line, int length);
  public abstract void DeleteLine(int line);
  public abstract void Rebuild(int[] lineLengths);

  protected void ValidateLineLengths(int[] lineLengths)
  {
    if(lineLengths == null) throw new ArgumentNullException();
    for(int i=0; i<lineLengths.Length; i++)
    {
      if(lineLengths[i] < 0) throw new ArgumentOutOfRangeException("Line lengths cannot be negative.");
      if(lineLengths[i] == 0 && i != lineLengths.Length-1)
      {
        throw new ArgumentOutOfRangeException("Zero-length lines are not supported (except at the final position).");
      }
    }
  }
}
#endregion

#region ArrayLineStorage
sealed class ArrayLineStorage : LineStorage
{
  public ArrayLineStorage()
  {
    lineLengths = new int[0];
  }

  public override int LineCount
  {
    get { return count; }
  }

  public override void CharToLine(int charIndex, out int line, out int column)
  {
    if(charIndex < 0) throw new ArgumentOutOfRangeException();

    for(int i=0; i<count; i++)
    {
      if(charIndex < lineLengths[i])
      {
        line   = i;
        column = charIndex;
        return;
      }

      charIndex -= lineLengths[i];
    }

    if(charIndex > 0) throw new ArgumentOutOfRangeException();

    line = count-1;
    column = lineLengths[line];
  }

  public override void GetLineInfo(int line, out int offset, out int length)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();

    offset = 0;
    for(int i=0; i<line; i++) offset += lineLengths[i];
    length = lineLengths[line];
  }

  public override int GetLineLength(int line)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();
    return lineLengths[line];
  }

  public override void AlterLine(int line, int newLength)
  {
    if(line < 0 || line >= count || newLength < 0) throw new ArgumentOutOfRangeException();
    lineLengths[line] = newLength;
  }

  public override void InsertLine(int line, int length)
  {
    if(line < 0 || line > count || length < 0) throw new ArgumentOutOfRangeException();

    if(count == lineLengths.Length)
    {
      int[] newArray = new int[count == 0 ? 16 : count*2];
      Array.Copy(lineLengths, newArray, count);
      lineLengths = newArray;
    }

    Array.Copy(lineLengths, line, lineLengths, line+1, count-line);
    lineLengths[line] = length;
    count++;
  }

  public override void DeleteLine(int line)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();
    Array.Copy(lineLengths, line+1, lineLengths, line, count-line-1);
    count--;
  }

  public override void Rebuild(int[] lineLengths)
  {
    ValidateLineLengths(lineLengths);
    this.lineLengths = (int[])lineLengths.Clone();
    count = lineLengths.Length;
  }

  int[] lineLengths;
  int count;
}
#endregion

#region TreeLineStorage
sealed class TreeLineStorage : LineStorage
{
  public TreeLineStorage()
  {
    Rebuild(new int[0]);
  }

  public override int LineCount
  {
    get { return count; }
  }

  public override void CharToLine(int charIndex, out int line, out int column)
  {
    if(charIndex < 0 || charIndex > array[0]) throw new ArgumentOutOfRangeException();

    int index;
    if(charIndex == array[0])
    {
      // if the character index is equal to the total length, then strictly speaking it's out of bounds, but it's more
      // friendly to consider it to be at the end of the last line. we have a special case for that because the
      // algorithm below fails due to the index being out of bounds
      GetLineInfo(count-1, out index, out line);
      column = charIndex - index;
      line   = count-1;
    }
    else
    {
      // we can convert a character to line index by starting near the root and traversing the tree downwards. the two
      // nodes under the root (starting with index 1) store the total lengths of the left and right halfs of the lines.
      // if the character index is less than the the left node, then it lies within the left side and we examine the
      // children of the left node and repeat. if instead, the character index was not less than the left node, then we
      // know it's in the right half of the lines, and we can subtract the value of the left node to get the offset
      // into the right side. we then examine the children of the right node and repeat.
      index = 1; // start by examining the left child of the root
      while(index < array.Length) // loop until the index is no longer valid -- ie, we've gone past all leaf nodes.
      {
        int value = array[index];
        if(charIndex < value)
        {
          index = index*2+1; // move to the left child
        }
        else
        {
          charIndex -= value;
          index = index*2+3; // move to the left child of the right child
        }
      }

      line   = GetLineIndex(index/2);
      column = charIndex;
    }
  }

  public override void GetLineInfo(int line, out int offset, out int length)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();

    int nodeIndex = GetLeafIndex(line); // get the leaf node that holds the line
    length = array[nodeIndex];          // the length of the line is stored there.

    offset = 0;
    
    // we can use the bitwise structure of the node index to tell us which nodes to add to generate the offset.
    // imagine a tree containing information about 8 lines (numbered 0 through 7). then there are interior nodes
    // containing the sums (0+1), (2+3), (4+5), (6+7), (0+1+2+3), and (4+5+6+7), where those numbers represent line
    // numbers. the indices of the leaf nodes range from 7 (for line 0) to 14 (for line 7). consider the leaf index for
    // line number 6. we can determine the offset by adding the nodes containing (0+1+2+3) plus (4+5). the binary
    // representation of the leaf indices tell us which direction to go when we traverse the tree. line number 6's node
    // index is 13. in binary, that's 1101. we'll do the following: if the least significant bit is zero, then we
    // subtract one from the index and add the offset of the node there. in either case, we'll then shift it to the
    // right. we'll repeat until the index is zero. for line number six with index 13, this works as follows: 13 is
    // 1101. we shift. 110. the LSB is zero, so we subtract one yielding 101. this is 5, the index of the node storing
    // (4+5), so we add that to the offset. we shift and get 10. we subtract one yielding 1, the index of the node
    // storing (0+1+2+3). we add that and shift again, producing zero, so we're done. the offset is (0+1+2+3) + (4+5),
    // which is correct.
    if(line != 0)
    {
      do
      {
        if((nodeIndex & 1) == 0)
        {
          nodeIndex--;
          offset += array[nodeIndex];
        }
        nodeIndex >>= 1;
      } while(nodeIndex != 0);
    }
  }

  public override int GetLineLength(int line)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();
    return array[GetLeafIndex(line)];
  }

  public override void AlterLine(int line, int newLength)
  {
    if(line < 0 || line > count || newLength < 0) throw new ArgumentOutOfRangeException();

    int nodeIndex = GetLeafIndex(line);
    if(array[nodeIndex] != newLength) // if the new length is different
    {
      array[nodeIndex] = newLength;   // set the new length
      do                              // and recalculate the nodes up the tree to the root
      {
        nodeIndex = GetParent(nodeIndex);
        RecalculateNode(nodeIndex);
      } while(nodeIndex != 0);
    }
  }

  public override void InsertLine(int line, int length)
  {
    if(line < 0 || line > count || length < 0) throw new ArgumentOutOfRangeException();

    int leafIndex = GetLeafIndex(line);

    if(count == maxLines) // if there isn't enough space to insert the new line, we need to rebuild the whole tree
    {
      int[] newLengths = new int[count+1];
      Array.Copy(array, GetLeafIndex(0), newLengths, 0, line);      // copy the line lengths up to the new line
      newLengths[line] = length;                                    // add the new line length
      Array.Copy(array, leafIndex, newLengths, line+1, count-line); // copy the line lengths after the new line
      Rebuild(newLengths);                                          // build a new tree given those line lengths
    }
    else
    {
      Array.Copy(array, leafIndex, array, leafIndex+1, count-line); // make space for the new line length
      array[leafIndex] = length;                                    // add the new line
      FixupTree(leafIndex);                                         // fix up the interior nodes
      count++;
    }
  }

  public override void DeleteLine(int line)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();

    // TODO: if the tree shrinks significantly (ie, to 1/8th of the maximum capacity), it may be best to resize and
    // rebuild the tree at this point to speed up future traversal operations

    int leafIndex = GetLeafIndex(line);
    Array.Copy(array, leafIndex+1, array, leafIndex, count-line-1); // shift over all the other lengths
    array[GetLeafIndex(--count)] = 0;                               // set the length of the previously-last leaf to 0
    FixupTree(leafIndex);                                           // fix up the interior nodes
  }

  public override void Rebuild(int[] lineLengths)
  {
    ValidateLineLengths(lineLengths);

    // we'll build a tree where the root node is the total length of all lines, the left child is the total length
    // of the first half of the lines, and the right child is the total length of the second half of the lines. the
    // subdivision continues until we have the individual line lengths on the bottom layer.

    // the bottom layer of the tree contains a power of 2 number of leaves. the line lengths are all stored in the
    // bottom layer, so we need to find a power of 2 at least as big as the number of lines. that power of 2 is the
    // maximum number of lines that can be stored in the tree
    count    = lineLengths.Length;
    maxLines = 1;
    while(maxLines < count) maxLines *= 2;

    // fill in the bottom layer of the tree with the line lengths. the bottom layer starts at index array.Length/2
    array = new int[maxLines*2-1];
    for(int i=0, j=array.Length/2; i<lineLengths.Length; j++, i++) array[j] = lineLengths[i];

    FixupTree(GetLeafIndex(0)); // calculate the rest of the tree
  }

  /// <summary>Fixes the interior nodes of the tree, assuming that all leaves from <paramref name="nodeIndex"/> to the
  /// end have changed.
  /// </summary>
  void FixupTree(int nodeIndex)
  {
    if(nodeIndex == 0) return; // if we're already at the root, there's no work to do. (this simplifies the logic below)

    int layerEnd = maxLines-1;
    do
    {
      nodeIndex = GetParent(nodeIndex); // move to the previous layer in the tree
      for(int i=nodeIndex; i<layerEnd; i++) RecalculateNode(i); // recalculate the rest of the nodes in this layer
      layerEnd /= 2; // calculate the end of the next layer
    } while(layerEnd != 0);
  }

  /// <summary>Converts the given line number, which must be within bounds, to the index of the leaf which stores
  /// its length.
  /// </summary>
  int GetLeafIndex(int line)
  {
    return line + maxLines - 1;
  }

  /// <summary>Converts the given leaf index to its corresponding line number.</summary>
  int GetLineIndex(int leafIndex)
  {
    return leafIndex - maxLines + 1;
  }

  /// <summary>Given an node index, recalculates the node's value based on its two children. No other nodes are
  /// visited or updated.
  /// </summary>
  void RecalculateNode(int nodeIndex)
  {
    array[nodeIndex] = array[nodeIndex*2+1] + array[nodeIndex*2+2];
  }

  /// <summary>An array that contains a binary tree.</summary>
  int[] array;
  /// <summary>The number of lines currently stored in the tree.</summary>
  int count;
  /// <summary>The maximum number of lines that can be stored in the tree before it needs to be resized.</summary>
  int maxLines;

  /// <summary>Given a node index other than the root, returns the index of its parent node.</summary>
  static int GetParent(int nodeIndex)
  {
    return (nodeIndex-1) / 2;
  }
}
#endregion

#region FancyTreeLineStorage
sealed class FancyTreeLineStorage : LineStorage
{
  public override int LineCount
  {
    get { return count; }
  }

  public override void CharToLine(int charIndex, out int line, out int column)
  {
    if(charIndex < 0 || charIndex > array[0]) throw new ArgumentOutOfRangeException();

    if(charIndex == array[0])                     // if the character index is past the end of the last line, it's out
    {                                             // strictly speaking, so we can't use the algorithm below. but
      GetLineInfo(count-1, out column, out line); // instead of giving an error, it's more friendly to make it seem
      column = charIndex - column;                // like it's at the end of the last line.
      line   = count-1;
    }
    else if(array.Length == 1) // if the array only has one element (ie, it doesn't contain the tree),
    {                          // then we cannot use the algorithm below
      line   = 0;
      column = charIndex;
    }
    else
    {
      // we'll start at the root of the tree, which stores the sum of the lengths of the first half of the lines. if
      // the character index is less than that value, then it lies within the first half of the lines and we'll go
      // left. otherwise, we'll subtract the value and go right.

      int index = 1, value;
      while(index < bottomNodes) // traverse downwards until we get to the leaves
      {
        value = array[index];
        if(charIndex < value)
        {
          index *= 2; // go to the left child
        }
        else
        {
          charIndex -= value;
          index = index*2+1; // go to the right child
        }
      }

      // now we're at a leaf node
      line  = GetLineIndex(index);
      value = array[index];

      if(charIndex >= value) // if it's not in this leaf node, it must be in the line after (the odd-numbered line)
      {
        charIndex -= value;
        line++;
      }

      column = charIndex;
    }
  }

  public override void GetLineInfo(int line, out int offset, out int length)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();

    offset = 0;

    if(array.Length == 1) // if the array only has one element (ie, it doesn't contain the tree),
    {                     // then we cannot use the algorithm below
      length = array[0];
      return;
    }

    // we can use the bitwise structure of the line number to tell us which nodes to add to generate the offset, and
    // which nodes to add and subtract to generate the length. imagine a tree containing information about 8 lines
    // (numbered 0 through 7). the leaf nodes contain the lengths of lines 0, 2, 4, and 6, and there are interior nodes
    // containing the sums (0+1), (4+5), (0+1+2+3), and (0+1+2+3+4+5+6+7), where those numbers represent line
    // numbers. consider line number 5 (the sixth line). we can determine the offset by adding the two nodes (0+1+2+3)
    // and 4. we can determine the length by subtracting 4 from (4+5).
    // 
    // we'll position the node pointer at leaf node found by dividing the line number
    // by 2. for 5, that's 2, the 3rd leaf, which contains the length of line 4. line number 5 in binary is 101.
    // we'll then do the following: if the least significant bit of the line number is one, we'll add that node's
    // length to the offset and subtract it from the length. if the bit is zero, we'll add the node's value to the
    // length and finish the calculation of the length (so it won't be modified in future iterations). in either case,
    // we'll then shift the line number right and move the node pointer to its parent. when the line number is zero,
    // we're done.
    //
    // for line number 5 with the node pointer at the node for line 4, the least significant bit of the line number 101
    // is 1, so we add the length of line 4 to the offset and subtract it from the length. then we shift the line
    // number and node pointer to the right. now the line number is 10 and the node pointer is at the node for (4+5).
    // since the LSB is zero, we'll add the value to the length and finish calculating the length. just shift both
    // right again. now the line number is 1 and the node pointer is at the node for the lengths (0+1+2+3). since the
    // LSB is a 1, we add it to the offset. after shifting, the line number is zero, so we're done. the offset is
    // (0+1+2+3) + 4, and the length is (4+5) - 4, which are both correct.

    length = 0;
    int nodeIndex = GetNearestLeafIndex(line);
    bool doneWithLength = false;

    do
    {
      int value = array[nodeIndex];

      if((line & 1) != 0)
      {
        offset += value;
        if(!doneWithLength) length -= value;
      }
      else if(!doneWithLength)
      {
        length += value;
        doneWithLength = true;
      }

      nodeIndex >>= 1;
      line >>= 1;
    } while(line != 0);

    if(!doneWithLength) length += array[nodeIndex];
  }

  public override int GetLineLength(int line)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();
    return array.Length == 1 ? array[0] : InternalGetLineLength(line);
  }

  public override void AlterLine(int line, int newLength)
  {
    if(line < 0 || line >= count || newLength < 0) throw new ArgumentOutOfRangeException();

    if(array.Length == 1) // if the array doesn't contain the tree, then we'll simply set the total length
    {
      array[0] = newLength;
    }
    else
    {
      // we'll start from the leaf node nearest the line and, similar to what we do in GetLineInfo, use the bitwise
      // structure of the line number to determine which interior nodes need to be updated.
      int lengthDelta = newLength - InternalGetLineLength(line);
      if(lengthDelta != 0) // if the line length is different...
      {
        ApplyDeltaToLine(line, lengthDelta);
        array[0] += lengthDelta;
      }
    }
  }

  public override void InsertLine(int line, int length)
  {
    if(line < 0 || line > count || length < 0) throw new ArgumentOutOfRangeException();

    if(count == bottomNodes*2) // if there isn't enough space to insert the new line, we need to rebuild the whole tree
    {
      int[] newLengths = new int[count+1];
      for(int i=0; i<line; i++) newLengths[i] = InternalGetLineLength(i); // copy the line lengths up to the new line
      newLengths[line] = length;                                          // add the new line length
      for(int i=line; i<count; i++) newLengths[i+1] = InternalGetLineLength(i); // copy the line lengths after the new line
      Rebuild(newLengths);                                                // build a new tree given those line lengths
    }
    else
    {
      if(array.Length != 1) // if we have the tree...
      {
        // we'll start from the end of the tree, at line number 'count', and work our way left towards the point
        // where the line is to be inserted. for each line along the way, we'll get the length of the previous line
        // (or the new line, as the case may be) and find the difference. then we'll add the difference to all of the
        // nodes that contain the length of the current line. 
        for(int i=count, previousLength, currentLength=0; i >= line; i--)
        {
          previousLength = i > line ? InternalGetLineLength(i-1) : length;
          ApplyDeltaToLine(i, previousLength - currentLength);
          currentLength = previousLength;
        }
      }

      // then we'll add the new length to the total
      array[0] += length;
      count++;
    }
  }

  public override void DeleteLine(int line)
  {
    if(line < 0 || line >= count) throw new ArgumentOutOfRangeException();

    // we'll start from the end of the tree, at line number 'count-1', and work our way left towards the point
    // where the line is to be deleted. for each line along the way, we'll take the length of the next line and
    // find the difference. then we'll subtract the difference from all of the nodes that contain the length of the
    // current line. 
    int currentLength = array[0]; // ensure that if there's no tree (ie, we don't enter the for loop),
    for(int i=count-1, nextLength=0; i >= line; i--)      // that we end up removing the right amount
    {
      currentLength = InternalGetLineLength(i);
      ApplyDeltaToLine(i, nextLength - currentLength);
      nextLength = currentLength;
    }

    // then we'll add the new length to the total
    array[0] -= currentLength;
    count--;
  }

  public override void Rebuild(int[] lineLengths)
  {
    ValidateLineLengths(lineLengths);

    // we'll build an array where the total length is stored in the first element, and the second element is the root
    // of a binary tree that stores sums of spans of line lengths. the bottom layer stores the lengths of the even
    // lines (lines whose line number has a least significant bit equal to zero). the next layer up has half as many
    // nodes and stores the lengths of lines with the second bit equal to zero. the next layer has half as many again
    // and stores sums of lines with the third bit equal to zero. for example, for a tree containing 8 lines (numbered
    // from 0 to 7), the bottom layer has 4 nodes, storing the lengths of lines 0, 2, 4, and 6. the next layer has 2
    // nodes, storing the sums of lengths of lines 0+1, and 4+5. the next layer (the root) has one node and stores the
    // sum of lines 0+1+2+3. the array element before the root stores the total length: 0+1+2+3+4+5+6+7.

    // this can also be considered to be a binary tree starting at the first element of the array, except that the root
    // node has only a left child, which is rooted in the second element.

    // to hold N line lengths, we want a power of two greater than or equal to N
    count    = lineLengths.Length;
    int size = 1;
    while(size < count) size *= 2;

    array = new int[size];

    // store the lengths of even lines in the bottom layer of the tree
    size /= 2;
    bottomNodes = size;
    for(int i=0, j=size; i<lineLengths.Length; j++, i+=2) array[j] = lineLengths[i];

    // now fill out the other layers. the span is how many will line lengths be summed into a single node. we can get
    // half of the span from the layer below.
    int halfSpan = 1;

    size /= 2;
    while(size != 0)
    {
      // the layer with N nodes starts at index N, so 'size' is both the size and the starting index.
      for(int i=size,j=halfSpan, end=i+size; i<end; j += halfSpan*3, i++) // for each node on this layer
      {
        array[i] = array[i*2]; // get half of the span from the layer below
        // now loop to get the rest of the values in the span
        for(int endOfSpan=Math.Min(lineLengths.Length, j+halfSpan); j<endOfSpan; j++) array[i] += lineLengths[j];
      }

      halfSpan *= 2; // the next layer has twice as many lines per span
      size /= 2;
    }

    if(array.Length != 1)
    {
      // the first element in the array is a special case, but works pretty similarly.
      array[0] = array[1]; // get half of the span from the layer below
      // now loop to get the rest of the values in the span
      for(int i=halfSpan, end=Math.Min(i+halfSpan, lineLengths.Length); i<end; i++) array[0] += lineLengths[i];
    }
  }

  /// <summary>Given the index of a valid line, returns the length of the line.</summary>
  int InternalGetLineLength(int line)
  {
    int nodeIndex = GetNearestLeafIndex(line);

    if((line & 1) == 0) // if the line number is even, we'll simply read the length from the leaf node.
    {
      return array[nodeIndex];
    }
    else // otherwise, we'll use the algorithm from GetLineInfo() to get the length.
    {
      int length = 0;

      do
      {
        int value = array[nodeIndex];

        if((line & 1) != 0) length -= value;
        else return length + value;

        nodeIndex >>= 1;
        line >>= 1;
      } while(line != 0);

      return length + array[nodeIndex];
    }
  }

  /// <summary>Given a valid line index and a length difference, applies the length difference to all of the nodes that
  /// contain the given line length. This does not update the total line length stored in the first array index.
  /// </summary>
  void ApplyDeltaToLine(int line, int lengthDelta)
  {
    int nodeIndex = GetNearestLeafIndex(line);
    do
    {
      if((line & 1) == 0) array[nodeIndex] += lengthDelta;
      line >>= 1;
      nodeIndex >>= 1;
    } while(nodeIndex != 0);
  }

  /// <summary>Converts the given leaf index to its corresponding line number. Note that the line will always be even,
  /// because the leaf nodes refer only to the even-numbered lines.
  /// </summary>
  int GetLineIndex(int leafIndex)
  {
    return (leafIndex - bottomNodes) * 2;
  }

  /// <summary>Gets the raw index of the leaf nearest the given line. Since the leaves store only the lengths of
  /// even-numbered lines, if <paramref cref="lineIndex"/> is odd, the leaf index of
  /// <c><paramref name="lineIndex"/>-1</c> will be returned.
  /// </summary>
  int GetNearestLeafIndex(int lineIndex)
  {
    return lineIndex/2 + bottomNodes;
  }

  /// <summary>An array containing the total length of the lines in the first element and a binary tree rooted in the
  /// second element that contains sums of spans of lines.
  /// </summary>
  int[] array;
  /// <summary>The number of lines stored in the tree.</summary>
  int count;
  /// <summary>Both the maximum number of leaf nodes and the index to the first leaf node. The maximum number of lines
  /// that can be represented by the tree is equal to <c>bottomNodes*2</c>.
  /// </summary>
  int bottomNodes;
}
#endregion

class Program
{
  static void Main(string[] args) 
  {
    //for(int i=0; i<100; i++) ValidateStorage(new FancyTreeLineStorage(), i);

    BenchmarkStorage(new ArrayLineStorage());
    BenchmarkStorage(new TreeLineStorage());
    BenchmarkStorage(new FancyTreeLineStorage());
    Console.ReadLine();
  }

  const int BenchmarkOps = 1000000;

  static void BenchmarkStorage(LineStorage storage)
  {
    /*
Benchmarking ArrayLineStorage with 1000000 operations
  Benchmarking with 10 lines
    Rebuild() = 5 ms (1000 ops)
    CharToLine() = 77 ms
    GetLineLength() = 39 ms
    GetLineInfo() = 83 ms
    AlterLine() = 113 ms
    AddLine() = 17 ms (100000 ops)
    InsertLine() = 28 ms (100000 ops)
    DeleteLine() = 19 ms (100000 ops)
  Benchmarking with 100 lines
    Rebuild() = 5 ms (1000 ops)
    CharToLine() = 203 ms
    GetLineLength() = 42 ms
    GetLineInfo() = 241 ms
    AlterLine() = 113 ms
    AddLine() = 16 ms (100000 ops)
    InsertLine() = 30 ms (100000 ops)
    DeleteLine() = 22 ms (100000 ops)
  Benchmarking with 1000 lines
    Rebuild() = 9 ms (1000 ops)
    CharToLine() = 1552 ms
    GetLineLength() = 41 ms
    GetLineInfo() = 1862 ms
    AlterLine() = 113 ms
    AddLine() = 16 ms (100000 ops)
    InsertLine() = 62 ms (100000 ops)
    DeleteLine() = 53 ms (100000 ops)
  Benchmarking with 10000 lines
    Rebuild() = 45 ms (1000 ops)
    CharToLine() = 15108 ms
    GetLineLength() = 42 ms
    GetLineInfo() = 18138 ms
    AlterLine() = 115 ms
    AddLine() = 16 ms (100000 ops)
    InsertLine() = 421 ms (100000 ops)
    DeleteLine() = 412 ms (100000 ops)
  Benchmarking with 100000 lines
    Rebuild() = 731 ms (1000 ops)
    CharToLine() = 150893 ms
    GetLineLength() = 43 ms
    GetLineInfo() = 181228 ms
    AlterLine() = 117 ms
    AddLine() = 17 ms (100000 ops)
    InsertLine() = 4757 ms (100000 ops)
    DeleteLine() = 5185 ms (100000 ops)

Benchmarking TreeLineStorage with 1000000 operations
  Benchmarking with 10 lines
    Rebuild() = 4 ms (1000 ops)
    CharToLine() = 89 ms
    GetLineLength() = 40 ms
    GetLineInfo() = 83 ms
    AlterLine() = 132 ms
    AddLine() = 44 ms (100000 ops)
    InsertLine() = 65 ms (100000 ops)
    DeleteLine() = 55 ms (100000 ops)
  Benchmarking with 100 lines
    Rebuild() = 6 ms (1000 ops)
    CharToLine() = 132 ms
    GetLineLength() = 40 ms
    GetLineInfo() = 109 ms
    AlterLine() = 143 ms
    AddLine() = 56 ms (100000 ops)
    InsertLine() = 94 ms (100000 ops)
    DeleteLine() = 85 ms (100000 ops)
  Benchmarking with 1000 lines
    Rebuild() = 14 ms (1000 ops)
    CharToLine() = 172 ms
    GetLineLength() = 40 ms
    GetLineInfo() = 134 ms
    AlterLine() = 153 ms
    AddLine() = 332 ms (100000 ops)
    InsertLine() = 537 ms (100000 ops)
    DeleteLine() = 527 ms (100000 ops)
  Benchmarking with 10000 lines
    Rebuild() = 153 ms (1000 ops)
    CharToLine() = 222 ms
    GetLineLength() = 41 ms
    GetLineInfo() = 161 ms
    AlterLine() = 169 ms
    AddLine() = 2048 ms (100000 ops)
    InsertLine() = 4162 ms (100000 ops)
    DeleteLine() = 4183 ms (100000 ops)
  Benchmarking with 100000 lines
    Rebuild() = 1609 ms (1000 ops)
    CharToLine() = 263 ms
    GetLineLength() = 43 ms
    GetLineInfo() = 189 ms
    AlterLine() = 183 ms
    AddLine() = 10106 ms (100000 ops)
    InsertLine() = 31142 ms (100000 ops)
    DeleteLine() = 31557 ms (100000 ops)

Benchmarking FancyTreeLineStorage with 1000000 operations
  Benchmarking with 10 lines
    Rebuild() = 4 ms (1000 ops)
    CharToLine() = 80 ms
    GetLineLength() = 75 ms
    GetLineInfo() = 86 ms
    AlterLine() = 178 ms
    AddLine() = 18 ms (100000 ops)
    InsertLine() = 247 ms (100000 ops)
    DeleteLine() = 239 ms (100000 ops)
  Benchmarking with 100 lines
    Rebuild() = 6 ms (1000 ops)
    CharToLine() = 114 ms
    GetLineLength() = 76 ms
    GetLineInfo() = 112 ms
    AlterLine() = 210 ms
    AddLine() = 18 ms (100000 ops)
    InsertLine() = 638 ms (100000 ops)
    DeleteLine() = 634 ms (100000 ops)
  Benchmarking with 1000 lines
    Rebuild() = 22 ms (1000 ops)
    CharToLine() = 145 ms
    GetLineLength() = 77 ms
    GetLineInfo() = 137 ms
    AlterLine() = 233 ms
    AddLine() = 19 ms (100000 ops)
    InsertLine() = 5035 ms (100000 ops)
    DeleteLine() = 5065 ms (100000 ops)
  Benchmarking with 10000 lines
    Rebuild() = 239 ms (1000 ops)
    CharToLine() = 178 ms
    GetLineLength() = 75 ms
    GetLineInfo() = 163 ms
    AlterLine() = 262 ms
    AddLine() = 20 ms (100000 ops)
    InsertLine() = 54754 ms (100000 ops)
    DeleteLine() = 55070 ms (100000 ops)
  Benchmarking with 100000 lines
    Rebuild() = 2702 ms (1000 ops)
    CharToLine() = 213 ms
    GetLineLength() = 78 ms
    GetLineInfo() = 192 ms
    AlterLine() = 291 ms
    AddLine() = 22 ms (100000 ops)
    InsertLine() = 605438 ms (100000 ops)
    DeleteLine() = 596321 ms (100000 ops)
   */

    // try a variety of operations with different line counts
    Console.WriteLine("Benchmarking "+storage.GetType().Name+" with "+BenchmarkOps+" operations");

    BenchmarkStorage(storage, 10);
    BenchmarkStorage(storage, 100);
    BenchmarkStorage(storage, 1000);
    BenchmarkStorage(storage, 10000);
    BenchmarkStorage(storage, 100000);

    Console.WriteLine();
  }

  static void BenchmarkStorage(LineStorage storage, int numLines)
  {
    Console.WriteLine("  Benchmarking with "+numLines+" lines");

    int[] lineLengths = new int[numLines];
    Random rand = new Random(numLines);
    int totalLength = 0;
    for(int i=0; i<lineLengths.Length; i++)
    {
      lineLengths[i] = rand.Next(1, 100);
      totalLength += lineLengths[i];
    }

    System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();

    storage.Rebuild(lineLengths);
    // benchmark Rebuild()
    timer.Reset();
    for(int i=0; i<BenchmarkOps/1000; i++)
    {
      GarbageCollect();
      timer.Start();
      storage.Rebuild(lineLengths);
      timer.Stop();
    }
    Console.WriteLine("    Rebuild() = "+GetRepTime(timer, 0, BenchmarkOps/1000)+" ("+(BenchmarkOps/1000)+" ops)");

    // calculate biases
    GarbageCollect();

    // bias with no random numbers
    timer.Reset();
    timer.Start();
    int total = 0;
    for(int i=0; i<BenchmarkOps; i++)
    {
      total++;
    }
    timer.Stop();
    long bias0 = timer.ElapsedMilliseconds;

    // bias with 1 random number
    timer.Reset();
    timer.Start();
    for(int i=0; i<BenchmarkOps; i++)
    {
      total += rand.Next(storage.LineCount);
    }
    timer.Stop();
    long bias1 = timer.ElapsedMilliseconds;

    // bias with 2 random number
    timer.Reset();
    timer.Start();
    for(int i=0; i<BenchmarkOps; i++)
    {
      total += rand.Next(storage.LineCount) + rand.Next(1, 100);
    }
    timer.Stop();
    long bias2 = timer.ElapsedMilliseconds;

    // benchmark CharToLine()
    timer.Reset();
    GarbageCollect();
    timer.Start();
    for(int i=0; i<BenchmarkOps; i++)
    {
      int line, column;
      storage.CharToLine(rand.Next(totalLength), out line, out column);
    }
    timer.Stop();
    Console.WriteLine("    CharToLine() = "+GetRepTime(timer, bias1, BenchmarkOps));

    // benchmark GetLineLength()
    timer.Reset();
    GarbageCollect();
    timer.Start();
    for(int i=0; i<BenchmarkOps; i++)
    {
      storage.GetLineLength(rand.Next(storage.LineCount));
    }
    timer.Stop();
    Console.WriteLine("    GetLineLength() = "+GetRepTime(timer, bias1, BenchmarkOps));

    // benchmark GetLineInfo()
    timer.Reset();
    GarbageCollect();
    timer.Start();
    for(int i=0; i<BenchmarkOps; i++)
    {
      int length, offset;
      storage.GetLineInfo(rand.Next(storage.LineCount), out offset, out length);
    }
    timer.Stop();
    Console.WriteLine("    GetLineInfo() = "+GetRepTime(timer, bias1, BenchmarkOps));

    // benchmark AlterLine()
    timer.Reset();
    GarbageCollect();
    timer.Start();
    for(int i=0; i<BenchmarkOps; i++)
    {
      storage.AlterLine(rand.Next(storage.LineCount), rand.Next(1, 100));
    }
    timer.Stop();
    Console.WriteLine("    AlterLine() = "+GetRepTime(timer, bias2, BenchmarkOps));

    // benchmark AddLine()
    timer.Reset();
    for(int outer=0; outer<1000; outer++)
    {
      GarbageCollect();
      timer.Start();
      for(int i=0; i<BenchmarkOps/10000; i++)
      {
        storage.AddLine(rand.Next(1, 100));
      }
      timer.Stop();

      // remove the added lines to keep it from growing too large
      for(int i=0; i<BenchmarkOps/10000; i++) storage.DeleteLine(storage.LineCount-1);
    }
    Console.WriteLine("    AddLine() = "+GetRepTime(timer, bias1/10, BenchmarkOps)+" ("+(BenchmarkOps/10)+" ops)");

    // benchmark InsertLine() and DeleteLine()
    System.Diagnostics.Stopwatch delTimer = new System.Diagnostics.Stopwatch();
    timer.Reset();
    for(int outer=0; outer<1000; outer++)
    {
      GarbageCollect();
      timer.Start();
      for(int i=0; i<BenchmarkOps/10000; i++)
      {
        storage.InsertLine(rand.Next(storage.LineCount), rand.Next(1, 100));
      }
      timer.Stop();

      // remove the added lines to keep it from growing too large
      delTimer.Start();
      for(int i=0; i<BenchmarkOps/10000; i++) storage.DeleteLine(rand.Next(storage.LineCount));
      delTimer.Stop();
    }
    Console.WriteLine("    InsertLine() = "+GetRepTime(timer, bias2/10, BenchmarkOps)+" ("+(BenchmarkOps/10)+" ops)");
    Console.WriteLine("    DeleteLine() = "+GetRepTime(delTimer, bias1/10, BenchmarkOps)+" ("+(BenchmarkOps/10)+" ops)");
  }

  static void GarbageCollect()
  {
    GC.Collect();
    GC.Collect();
    GC.WaitForPendingFinalizers();
  }

  static string GetRepTime(System.Diagnostics.Stopwatch timer, long bias, int numReps)
  {
    return timer.ElapsedMilliseconds + " ms";
    return ((double)(timer.ElapsedMilliseconds-bias) / numReps)+" ms";
  }

  static void ValidateStorage(LineStorage storage, int randomSeed)
  {
    ArrayLineStorage safe = new ArrayLineStorage();
    safe.Rebuild(new int[] { 10 });
    storage.Rebuild(new int[] { 10 });
    for(int i=0; i <= 10; i++) TestCharToLine(safe, storage, i);
    
    safe.Rebuild(new int[] { 10, 20 });
    storage.Rebuild(new int[] { 10, 20 });
    for(int i=0; i <= 30; i++) TestCharToLine(safe, storage, i);

    safe.AddLine(0);
    storage.AddLine(0);
    TestCharToLine(safe, storage, 30);

    Random rand = new Random(randomSeed);
    List<int> lineLengths = new List<int>(2000);
    int totalLength = 0;
    for(int i=0; i<1250; i++) // generate a document with 1250 lines of random length
    {
      lineLengths.Add(rand.Next(1, 100));
      totalLength += lineLengths[i];
    }

    safe.Rebuild(lineLengths.ToArray());
    storage.Rebuild(lineLengths.ToArray());

    for(int i=0; i<250; i++) // add 250 more lines
    {
      int length = rand.Next(1, 100);
      lineLengths.Add(length);
      safe.AddLine(length);
      storage.AddLine(length);
      totalLength += length;
    }

    TestLineLengths(storage, lineLengths); // verify line lengths

    for(int i=0; i<250; i++) // insert 250 random lines
    {
      int index = rand.Next(lineLengths.Count+1), length = rand.Next(1, 100);
      lineLengths.Insert(index, length);
      safe.InsertLine(index, length);
      storage.InsertLine(index, length);
      totalLength += length;
    }

    TestLineLengths(storage, lineLengths); // verify line lengths

    for(int i=0; i<250; i++) // delete 250 random lines
    {
      int index = rand.Next(lineLengths.Count);
      totalLength -= lineLengths[index];
      lineLengths.RemoveAt(index);
      safe.DeleteLine(index);
      storage.DeleteLine(index);
    }

    TestLineLengths(storage, lineLengths); // verify line lengths

    for(int i=0; i<500; i++) // mutate 500 random lines
    {
      int index = rand.Next(lineLengths.Count), newLength = rand.Next(1, 100);
      totalLength += newLength - lineLengths[index];
      lineLengths[index] = newLength;
      safe.AlterLine(index, newLength);
      storage.AlterLine(index, newLength);
    }

    TestLineLengths(storage, lineLengths); // verify line lengths

    for(int i=0; i<5000; i++) // test 5000 random indices
    {
      TestCharToLine(safe, storage, rand.Next(0, totalLength+1));
    }
  }

  static void TestCharToLine(LineStorage safe, LineStorage test, int charOffset)
  {
    int line1, line2, column1, column2;
    safe.CharToLine(charOffset, out line1, out column1);
    test.CharToLine(charOffset, out line2, out column2);
    if(line1 != line2 || column1 != column2) throw new Exception("CharToLine failed");
  }

  static void TestLineLengths(LineStorage storage, List<int> lineLengths)
  {
    if(storage.LineCount != lineLengths.Count) throw new Exception("Line count didn't match");

    for(int i=0, offset=0; i<lineLengths.Count; i++) // verify line lengths and offsets
    {
      int reportedOffset, reportedLength;
      storage.GetLineInfo(i, out reportedOffset, out reportedLength);
      if(reportedOffset != offset || reportedLength != lineLengths[i]) throw new Exception("Line info didn't match");
      offset += lineLengths[i];
    }
  }
}


} // namespace App