Sequence (ADT)

A sequence, according to the textbook is "a union between a vector and a list." It mentions two functions used to convert between ranks and positions, but nothing else.

This page is my interpretation of what the book said.

A sequence has access to elements by both rank and position.

Functions

Standard ADT Methods:

• int size() — Returns how many items are in the list.
• bool isEmpty() — Returns whether the list is empty (i.e. size is 0).

"Bridge" Methods:

• Rank rankOf(Position p) — Returns the corresponding rank of the given position $p$.
• Position positionOf(Rank r) — Returns the corresponding position of the given rank $r$.

Methods from List:

• bool isFirst(Position p) — Returns whether the specified position $p$ is the first item in the list.
• bool isLast(Position p) — Returns whether the specified position $p$ is the last item in the list.
• Position first() — Returns the position of the first item in the list.
• Position last() — Returns the position of the last item in the list.
• Position before(Position p) — Returns the position of the element prior to Position $p$.
• Position after(Position p) — Returns the position of the element after Position $p$.
• void replaceElement(Position p, Object o) — Replaces the element at position $p$ with an object $o$.
• void swapElements(Position p, Position q) — Switches the element stored at position $p$ with the one from position $q$ and vice versa.
• Position insertBefore(Position p, Object o) — Inserts a new element $o$ before position $p$ and returns the position of the newly inserted element.
• Position insertAfter(Position p, Object o) — Inserts a new element $o$ after position $p$ and returns the position of the newly inserted element.
• Position insertFirst(Object o) — Inserts a new element $o$ at the beginning of the list and returns the position of the newly inserted element.
• Position insertLast(Object o) — Inserts a new element $o$ at the end of the list and returns the position of the newly inserted element.
• void remove(Position p) — Removes an object from Position $p$.

Methods from Vector:

• Object elemAtRank(Rank r) — Returns the element stored at rank $r$ (similar to [] operator).
• void replaceAtRank(Rank r, Object o) — Puts an object $o$ at the specified rank $r$.
• void insertAtRank(Rank r) — Inserts an element at rank $r$ and shifts all following items down a rank.
• void removeAtRank(Rank r) — Removes an element from rank $r$ and shifts all following items up a rank to fill in the gap.