-
Notifications
You must be signed in to change notification settings - Fork 13
MTFList
Andrew Epstein edited this page Mar 31, 2018
·
1 revision
Given: MTFList<4> myMTFList;
When: myMTFList.moveToFront(2);
Then: The following diagrams show the execution of the moveToFront()
function.
index = i;
if (index == root) {
return;
}
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│ -1 │ │ 0 ├───>│ 1 ├───>│ 2 ├───>│ 3 │
│ │<───┤ │<───┤ │<───┤ │<───┤ │
└─────┘ └─────┘ └─────┘ └─────┘ └─────┘
index = 2, root = 0, i = 2
list[list[index].previous].next = list[index].next;
┌─────────────────┐
│ v
┌─────┐ ┌─────┐ ┌─────┐│ ┌─────┐ ┌─────┐
│ -1 │ │ 0 ├───>│ 1 ├┘ │ 2 ├───>│ 3 │
│ │<───┤ │<───┤ │<───┤ │<───┤ │
└─────┘ └─────┘ └─────┘ └─────┘ └─────┘
index = 2, root = 0, i = 2
if (list[index].next >= 0) {
list[list[index].next].previous = list[index].previous;
}
┌─────────────────┐
│ v
┌─────┐ ┌─────┐ ┌─────┐│ ┌─────┐ ┌─────┐
│ -1 │ │ 0 ├───>│ 1 ├┘ │ 2 ├───>│ 3 │
│ │<───┤ │<───┤ │<───┤ │ ┌┤ │
└─────┘ └─────┘ └─────┘ └─────┘ │└─────┘
^ │
└─────────────────┘
index = 2, root = 0, i = 2
list[root].previous = index;
┌─────────────────┐
│ v
┌─────┐ ┌─────┐ ┌─────┐│ ┌─────┐ ┌─────┐
│ -1 │ │ 0 ├───>│ 1 ├┘ │ 2 ├───>│ 3 │
│ │ ┌┤ │<───┤ │<───┤ │ ┌┤ │
└─────┘ │└─────┘ └─────┘ └─────┘ │└─────┘
│ ^ ^ │
│ └──────────┼──────┘
└─────────────────────────┘
index = 2, root = 0, i = 2
list[index].next = root;
┌─────────────────────────┐
│ ┌──────────┼──────┐
v │ │ v
┌─────┐ ┌─────┐ ┌─────┐│ ┌─────┐│ ┌─────┐
│ -1 │ │ 0 ├───>│ 1 ├┘ │ 2 ├┘ │ 3 │
│ │ ┌┤ │<───┤ │<───┤ │ ┌┤ │
└─────┘ │└─────┘ └─────┘ └─────┘ │└─────┘
│ ^ ^ │
│ └──────────┼──────┘
└─────────────────────────┘
index = 2, root = 0, i = 2
root = index;
list[root].previous = -1;
┌─────────────────────────┐
│ ┌──────────┼──────┐
v │ │ v
┌─────┐ ┌─────┐ ┌─────┐│ ┌─────┐│ ┌─────┐
│ -1 │ │ 0 ├───>│ 1 ├┘ │ 2 ├┘ │ 3 │
│ │ ┌┤ │<───┤ │ ┌┤ │ ┌┤ │
└─────┘ │└─────┘ └─────┘ │└─────┘ │└─────┘
^ │ ^ │ ^ │
│ │ └──────┼───┼──────┘
│ └─────────────────────┼───┘
└────────────────────────────┘
index = 2, root = 2, i = 2