rope

class RopeNode(object):
    def __init__(self, chars=None, num_chars=0, parent=None):
        self.left = None
        self.right = None
        # If leaf: number of chars
        # If non-leaf: number of total chars in left sub-tree
        self.num_chars = num_chars
        self.chars = chars
        self.parent = parent

class NewString(object):
    def __init__(self, rank):
        self.root = RopeNode()
        self.size = 0
        # All leaf nodes must have between [1, rank - 1] chars, except the root node.
        self.rank = rank

    def read(self, index):
        if index >= self.size:
            return None

        cur_index = index
        cur_node = self.root
        while cur_node.left is not None:
            if cur_index >= cur_node.num_chars:
                cur_node = cur_node.right
                cur_index -= cur_node.num_chars
            else:
                cur_node = cur_node.left
        return cur_node.chars[cur_index]

    def insert(self, char, index):
        if index > self.size:
            return False

        self.size += 1

        cur_index = index
        cur_node = self.root
        while cur_node.left is not None:
            if cur_index > cur_node.num_chars:
                cur_node = cur_node.right
                cur_index -= cur_node.num_chars
            else:
                cur_node.num_chars += 1
                cur_node = cur_node.left

        if cur_node.chars is None:
            assert cur_node.num_chars == 0
            assert cur_index == 0
            cur_node.chars = []
        cur_node.chars.insert(cur_index, char)
        cur_node.num_chars += 1

        if cur_node.num_chars >= self.rank:
            mid = cur_node.num_chars / 2
            left_num_chars = mid
            right_num_chars = cur_node.num_chars - mid
            cur_node.left = RopeNode(cur_node.chars[:mid], left_num_chars, cur_node)
            cur_node.right = RopeNode(cur_node.chars[mid:], right_num_chars, cur_node)
            cur_node.num_chars = left_num_chars
            cur_node.chars = None
        return True

    def delete(self, index):
        if index < 0 or index >= self.size:
            return False

        self.size -= 1

        if self.root.left is None:
            self.root.num_chars -= 1
            del self.root.chars[index]
            return True

        cur_index = index
        cur_node = self.root
        while cur_node.left is not None:
            if cur_index >= cur_node.num_chars:
                cur_node = cur_node.right
                cur_index -= cur_node.num_chars
            else:
                cur_node.num_chars -= 1
                cur_node = cur_node.left

        del cur_node.chars[cur_index]
        cur_node.num_chars -= 1
        if cur_node.num_chars == 0:
            parent = cur_node.parent
            sibling_node = None
            if parent.left == cur_node:
                sibling_node = parent.right
            else:
                sibling_node = parent.left
            if parent.parent is None:
                self.root = sibling_node
                sibling_node.parent = None
            else:
                grand_parent = parent.parent
                if grand_parent.left == parent:
                    grand_parent.left = sibling_node
                else:
                    grand_parent.right = sibling_node
                sibling_node.parent = grand_parent

        return True