Search code examples
algorithmdynamic-arrays

Binder Bookmark database using dynamic arrays

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.

Solution

  • Your understanding of the representation of the data structure is correct, although it might be more clear if you displayed the page numbers alongside the indexes.

    In what case would (a1, a2) or (b1, b2) become adjacent?

    The empty spots might be used up by alternately moving pages and shifting the bookmark.

    Consider the following simple example with only 3 pages (where zeros represent empty spots and positive integers represent an actual page).

    We start with bookmark A between page 1 and 2, and bookmark B between page 2 and 3.

    The initial structure is:

    |1|0|0|0|2|0|0|0|3|
 ^       ^       ^
a1     a2,b1     b2

    After performing move page(A), one empty spot after P2 is consumed:

    |0|0|0|0|2|1|0|0|3|
^        ^ ^     ^
a1      a2 b1    b2

    After performing shift mark(A, 1), bookmark A is now after page 2:

    |2|0|0|0|0|1|0|0|3|
 ^         ^     ^
a1       a2,b1   b2

    After performing move page(A) again:

    |0|0|0|0|0|1|2|0|3|
^          ^ ^   ^
a1        a2 b1  b2

    After performing shift mark(A, 1):

    |1|0|0|0|0|0|2|0|3|
 ^           ^   ^
a1         a2,b1 b2

    Finally, performing move page(A):

    |0|0|0|0|0|0|2|1|3|
^            ^ ^ ^
a1          a2 b1 b2

    And now b1 and b2 are adjacent. It is necessary to rebuild the structure as there are no more empty spots to move more pages to. Note that initially having n empty spaces between the sections guarantees amortized constant time.

    what happens when B doesn't have any pages after it?

    It doesn't matter. The entire P3 can be empty and we can point b2 to index 3n (one after the last valid index in this array).