editor_with_rope.js

class Rope {
  constructor(text) {
    this.text = text;
    this.size = text.length
  }

  insert(text, location) {
    let { left, right } = this.splitAt(location)
    // Avoid creating empty children
    if (right.toStringPretty() == '') right = undefined;
    if (left.toStringPretty() == '') left = undefined;
    const newRoot = new Rope(text)
    newRoot.left = left
    newRoot.right = right
    return newRoot.rebalance()
  }

  splitAt(position) {
    const leftSize = this.left?.totalSize() || 0
    if (position < leftSize) {
      const { left, right } = this.left.splitAt(position)
      const newRight = new Rope(this.text)
      newRight.right = this.right
      newRight.left = right
      return { left, right: newRight }
    }
    if (position <= leftSize + this.size) {
      const left = new Rope(this.text.slice(0, position - leftSize))
      left.left = this.left
      const right = new Rope(this.text.slice(position - leftSize))
      right.right = this.right
      return { left, right }
    }
    const { left, right } = this.right.splitAt(position - (leftSize + this.size))
    const newLeft = new Rope(this.text)
    newLeft.right = left
    newLeft.left = this.left
    return { left: newLeft, right }
  }

  rebalance() {
    this.left = this.left?.rebalance()
    this.right = this.right?.rebalance()
    const leftDepth = this.left?.depth() || 0
    const rightDepth = this.right?.depth() || 0

    if (leftDepth > rightDepth + 1) {
      const newRight = new Rope(this.text)
      newRight.left = this.left.right
      newRight.right = this.right
      const newRoot = new Rope(this.left.text)
      newRoot.left = this.left.left
      newRoot.right = newRight
      return newRoot;
    }

    if (rightDepth > leftDepth + 1) {
      const newLeft = new Rope(this.text)
      newLeft.left = this.left
      newLeft.right = this.right.left
      const newRoot = new Rope(this.right.text)
      newRoot.right = this.right.right
      newRoot.left = newLeft
      return newRoot;
    }

    return this;
  }
  prepend(text) {
    if (this.left) {
      return this.left.prepend(text)
    }
    this.left = new Rope(text)
  }
  append(text) {
    if (this.right) {
      this.right.append(text)
    } else {
      this.right = new Rope(text)
    }
    return this;
  }

  deleteTrailing(number) {
    const totalSize = this.totalSize()
    return this.deleteRange(totalSize - number, totalSize)
  }
  trailingCharacters(number) {
    const { right } = this.splitAt(this.totalSize()  - number)
    return right.toStringPretty()
  }
  deleteRange(start, end) {
    const { left, right: temporaryRight } = this.splitAt(start)
    const { right } = temporaryRight.splitAt(end - start)
    const root = new Rope('')
    root.left = left
    root.right = right
    return root.rebalance()
  }
  characterAt(position) {
    const leftSize = this.left?.totalSize() || 0
    if (position < leftSize) {
      return this.left.characterAt(position)
    }
    if (position < leftSize + this.size) {
      return this.text[position - leftSize]
    }
    return this.right.characterAt(position - (leftSize + this.size))
  }
  // prints contents including showing the hierarchy
  toString() {
    const leftText = this.left ? '(' + this.left.toString() + ')' : ''
    const rightText = this.right ? '[' + this.right.toString() + ']' : ''
    return leftText + '|' + this.text + '|' + rightText
  }
  // just prints the stored text
  toStringPretty() {
    const leftText = this.left ? this.left.toStringPretty() : ''
    const rightText = this.right ? this.right.toStringPretty() : ''
    return leftText + this.text + rightText
  }
  totalSize() {
    const leftText = this.left ? this.left.totalSize() : 0
    const rightText = this.right ? this.right.totalSize() : 0
    return leftText + this.text.length + rightText
  }
  // how deep the tree is
  depth() {
    return 1 + Math.max(this.left?.depth() || 0, this.right?.depth() || 0)
  }
}

/*
Alternative edit commands, where we prioritize small memory consumption
*/
const edit_commands_alt = {
  '1': (buffer, input) => {
    return { new_buffer: buffer.append(input), inverse: b => b.deleteTrailing(input.length) }
  },
  '2': (buffer, input) => {
    const readd = buffer.trailingCharacters(parseInt(input))

    return {
      new_buffer: buffer.deleteTrailing(parseInt(input)),
      inverse: b => b.append(readd)
    }
  }
}
function processData(input) {
  input.split('\n').slice(1).reduce((state, line) => {
    const [instruction, input] = line.split(' ')
    switch (instruction) {
      case '1':
      case '2':
        const { new_buffer, inverse } = edit_commands_alt[instruction](state.buffer, input)
        state.history.push(inverse)
        state.buffer = new_buffer;
        break;
      case '3':
        process.stdout.write(state.buffer.characterAt(parseInt(input) - 1) + '\n');
        break;
      case '4':
        const inverse_operation = state.history.pop();
        state.buffer = inverse_operation(state.buffer)
    }
    // console.log(state.buffer.to_string())
    return state;
  }, { buffer: new Rope(''), history: [] });
}