I’m trying to work through one of the assignments for MITOpenCourseware’s Introduction to Algorithms:

Sisa Limpson is a very organized second grade student who keeps all of her course notes on individual pages stored in a three-ring binder. If she has n pages of notes in her binder, the first page is at index 0 and the last page is at index n − 1. While studying, Sisa often reorders pages of her notes. To help her reorganize, she has two bookmarks, A and B, which help her keep track of locations in the binder.

Describe a database to keep track of pages in Sisa’s binder, supporting the following operations, where n is the number of pages in the binder at the time of the operation. Assume that both bookmarks will be placed in the binder before any shift or move operation can occur, and that bookmark A will always be at a lower index than B. For each operation, state whether your running time is worst-case or amortized.

build(X) – Initialize database with pages from iterator X in O(|X|) time.
place mark(i, m) – Place bookmark m ∈ {A, B} between the page at index i and the page at index i + 1 in O(n) time.
read page(i) – Return the page at index i in O(1) time.
shift mark(m, d) – Take the bookmark m ∈ {A, B}, currently in front of the page at
index i, and move it in front of the page at index i + d for d ∈ {−1, 1} in O(1) time.
move page(m) – Take the page currently in front of bookmark m ∈ {A, B},
and move it in front of the other bookmark in O(1) time.

To build the database, the answer states:

For our approach, after both bookmarks have been placed, we will store the n pages in a static array S of size 3n, which we can completely re-build in O(n) time whenever build(X) or place_mark(i, m) are called (assuming n = |X|). To build S:

• place the subsequence P1 of pages from index 0 up to bookmark A at the beginning of S,
• followed by n empty array locations,
• followed by the subsequence of pages P2 between bookmarks A and B,
• followed by n empty array locations,
• followed by the subsequence of pages P3 from bookmark B to index n − 1.

We will maintain the separation invariant that P1, P2, and P3 are stored contiguously in S with a non-zero number of empty array slots between them. We also maintain four indices with semantic invariants: a1 pointing to the end of P1, a2 pointing to the start of P2, b1 pointing to the end of P2, and b2 pointing to the start of P3.

My interpretation of what the database looks like is the following for n=5, with bookmark A between the second and third page, and bookmark B between the 4th and 5th:

------------------------------------
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|
------------------------------------
   ^           ^ ^                ^
  a1          a2 b1              b2

The answer on how to implement move_page() says:

To support move page(m), move the relevent page at one of indices (a1, b1) to the index location (b1 + 1, a1 + 1) respectively, and then increment the stored indices to maintain the invariants. If performing this move breaks the separation invariant (i.e., either pair (a1, a2) or (b1, b2) become adjacent), rebuild the entire data structure as described above. This algorithm maintains the invariants of the data structure, so is correct. Note that this algorithm: rebuilds any time the extra space between two adjacent sections closes; after rebuilding, there is n extra space between adjacent sections; and the extra space between adjacent sections changes by at most one per move page operation. Thus, since this operation takes O(n) time at most once every n operations, and O(1) time otherwise, this operation runs in amortized O(1) time.

In what case would (a1, a2) or (b1, b2) become adjacent? The problem says to assume that bookmark A will always be at a lower index than B. I took this to mean that the max pages that can be in front of A is n-1. Another problem I have is that what happens when B doesn’t have any pages after it? My interpretation of the database is most likely wrong, but I’m not sure how else to interpret it.