Persistent random-access queue

Question

I need a queue $[x_0, ..., x_n]$ that supports the following operations:

• $\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$
• $\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$
• $\operatorname{lookup}([x_0, ..., x_n], i) = x_i$
• $\operatorname{update}([x_0, ..., x_n], i, y) = [x_0, ..., x_{i - 1}, y, x_{i + 1}, ... x_n]$
• $\operatorname{insert}([x_0, ..., x_n], i, y) = [x_0, ..., x_i, y, x_{i + 1}, ..., x_n]$
• $\operatorname{delete}([x_0, ..., x_n], i) = [x_0, ..., x_{i - 1}, x_{i + 1}, ... x_n]$
• $\operatorname{length}([x_0, ..., x_n]) = n + 1$

All operations should be in $O(\log n)$. The data structure should be atomic and persistent, i.e. it is written to a random-access data storage device, such a hard disk or flash memory. Therefore the data structure should minimize the number of seeks. I thought about using Counted B-Trees without keys and with a rollback journal. I also looked at several purely real-time functional data structures that use multiple lists (lists can be efficiently implemented with a file system with a truncate operation) but they seemed to be too complicated or not randomly accessible.

Assume that the filesystem has the following operations:

• write(file, offset, x)
• read(file, offset, length)
• append(file, x)
• truncate(file, length)

Is there any other data structure that I is more efficient or easier to implement while being as efficient?

Answer 1

Yes there is a data structure which name is Treap You can also do other things too (ex. range sum, range min-max, etc.) using this or you can also use BBST (Balanced binary search tree like AVL ).

Okay i will explain some terms i am assuming you have some Knowledge about Trees and BST(Binary search Tree)
Q. What Treap is?
A. Treap = Tree + Heap (in easy way)

Q. Use of Treap?
A. its randomized balanced tree basically its contain 2 values first one is data and second is rank (data, rank) and it has two property using data we keep BST(Binary search Tree) property it mean smaller than data will go on left side and bigger will be on right side and rank keep heap property its your choice that you want min heap aur max heap property. trick here is that rank is given uniformly random. So when we heapify using rank height of tree will not exceed O(LogN). so in easy implementation we can get a self balanced binary search tree.

Q. How to implement above requirements?
A. Insert and Delete methods are easy and equal to BST's methods

struct Node *insert(struct Node *root, int pos, int data) {
  if(root == dummy) {
    ptr ->left = ptr ->rig = dummy;
    ptr ->size = 1;
    ptr ->pri = rand();
    ptr ->data = data;
    return ptr++;
  } else if(root ->left ->size >= pos) {
    root ->left = insert(root ->left, pos, data);
    if(root ->left ->pri > root ->pri) root = rot(root, root ->left);
  } else {
    root ->rig = insert(root ->rig, pos - root ->left ->size - 1, data);
    if(root ->rig ->pri > root ->pri) root = rot(root, root ->rig);
  }
  update(root);
  return root;
}

here you can see 2 methods which are unknown to you actually one it rot which is rotation when our tree violate heap property and update where you can update your tree's attribute here we keeping size so you can updated this information here

Delete method is homework for you it will be same as insert in above code pos define that you want to insert an element in between pos-1 pos.

okay now lets come on your requirements :

enqueue -> call insert and pos will be root ->size
denqueue -> call delete 
lookup -> search method same as binary search tree's search method
update , insert -> call insert
length -> root ->size