## The problem

I have been playing with one of my toy projects and ended up having to shuffle text many times in a file that is around 10MB long. A naïve implementation chopping a string and gluing it together again ended up being painfully slow:

\[ O(n \cdot k) \]where n is the length of the string and k is the number of shuffling operations.

## A solution

It turns out that the problem can be efficiently solved using splay trees, where each node holds:

- the starting offset in the source string
- the length of the substring it represents
- the offset from the beginning of the substring taking into account all of the children on the left-hand-side
- total length of the substring taking into account all the children on the right-hand side

The find operation looks for a node containing the offset and splits it in two, if the node does not start with the offset.

```
1 static Node *Find(uint32_t offset, Node *root)
2 {
3 if(!root)
4 return 0;
5 if(offset >= root->offset && offset < (root->offset + root->length))
6 return root;
7 if(offset < root->offset)
8 return Find(offset, root->left);
9 return Find(offset-root->offset-root->length, root->right);
10 }
11
12 static Node *STFind(uint32_t offset, Node *root)
13 {
14 Node *n = Find(offset, root);
15 Splay(n);
16
17 if(n->offset < offset) {
18 Node *newNode = new Node();
19 newNode->start = n->start;
20 newNode->length = offset - n->offset;
21 n->start = newNode->start + newNode->length;
22 n->length -= newNode->length;
23 newNode->left = n->left;
24 update(newNode);
25 n->left = newNode;
26 update(n);
27 }
28 return n;
29 }
```

The actual shuffling boils down to splitting and merging sub-trees and producing the result to traversing the whole tree in-order.

```
1 void process(int i, int j, int k)
2 {
3 Node *n, *t, *left, *right = 0;
4 STSplit(left, n, i, pRoot);
5 if(j+1 < pS.length())
6 STSplit(n, right, j+1-i, n);
7 t = STMerge(left, right);
8 if(k < (t->offset + t->total_length))
9 STSplit(left, right, k, t);
10 else {
11 right = 0;
12 left = t;
13 }
14 pRoot = STMerge(left, n);
15 pRoot = STMerge(pRoot, right);
16 }
```

The amortized complexity is:

\[ O(k \cdot log(k) + n) \]See rope-splay.cpp.

## A test

It all runs pretty nicely for a test case with 10M characters and 100k shuffle operations:

```
]==> ./testgen 10000000 100000 > test
]==> time ./rope-naive < test > test-o-naive
./rope-naive < test > test-o-naive 386.17s user 66.19s system 99% cpu 7:32.86 total
]==> time ./rope-splay < test > test-o-splay
./rope-splay < test > test-o-splay 0.71s user 0.04s system 99% cpu 0.752 total
]==> diff test-o-splay test-o-naive
```