FastInsertDeleteString

import math

class Node(object):
    def __init__(self, val=None):
        self.val = val
        self.next = None
        self.prev = None

class NewString(object):
    def __init__(self, capacity):
        self.capacity = capacity

        self.rank = int(math.sqrt(capacity))
        if self.rank * self.rank < self.rank:
            self.rank += 1

        self.size = 0
        self.data_map = {}

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

        node = self.data_map[index / self.rank]
        for i in range(index % self.rank):
            node = node.next
        return node.val

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

        self.size += 1
        new_node = Node(char)

        # Check if it's the first char.
        if self.size == 1:
            self.data_map[0] = new_node
            return True

        # Check if we are inserting at the end.
        if index == self.size - 1:
            last_node = self.data_map[(self.size - 2) / self.rank]
            while last_node.next is not None:
                last_node = last_node.next
            last_node.next = new_node
            new_node.prev = last_node
            # check if we need a new entry in the map
            if (self.size - 1) % self.rank == 0:
                self.data_map[(self.size - 1) / self.rank] = new_node
            return True

        insert_before = self.data_map[index / self.rank]
        for i in range(index % self.rank):
            insert_before = insert_before.next
        if insert_before.prev is not None:
            new_node.prev = insert_before.prev
            insert_before.prev.next = new_node
        new_node.next = insert_before
        insert_before.prev = new_node

        next_map_entry_to_move = (index + self.rank - 1) / self.rank
        last_map_entry = (self.size - 2) / self.rank
        for i in range(next_map_entry_to_move, last_map_entry + 1):
            self.data_map[i] = self.data_map[i].prev

        # Check if we need a new entry in the map.
        if (self.size - 1) % self.rank == 0:
            last_node = self.data_map[last_map_entry]
            while last_node.next is not None:
                last_node = last_node.next
            self.data_map[(self.size - 1) / self.rank] = last_node
        return True

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

        self.size -= 1

        # check if we are deleting the only char
        if self.size == 0:
            del self.data_map[0]
            return True

        node_to_delete = self.data_map[index / self.rank]
        for i in range(index % self.rank):
            node_to_delete = node_to_delete.next

        # check if we need to delete the last entry in the map
        if self.size % self.rank == 0:
            del self.data_map[self.size / self.rank]

        # check if we are deleting the last char
        if node_to_delete.next is None:
            node_to_delete.prev.next = None
            return True

        node_to_delete.next.prev = node_to_delete.prev
        if node_to_delete.prev is not None:
            node_to_delete.prev.next = node_to_delete.next
        next_map_entry_to_move = (index + self.rank - 1) / self.rank
        last_map_entry = (self.size - 1) / self.rank
        for i in range(next_map_entry_to_move, last_map_entry + 1):
            self.data_map[i] = self.data_map[i].next
        return True