Carefully and sensibly make some changes. Change only what is needed.
- Record changes in a changelog on top of the spec
- There is likely some separation/sharpening that still needs to be done between accessing data by key, by index (like an array), or by the element itself (i.e. contains)
Carefully analyze and propose 2 designs, and what the tradeoffs are.

Think hard, and be systematic. Also extrapolate from the existing spec, its style and what my motivations/priorities are.

Produce a very detailed plan, justify every step and state your assumptions!

# **REVISED DESIGN SPEC (v2.1)**

## **1. Goals & Philosophy**

This library is designed for teaching and learning, not for production performance. Its primary goal is to provide clear, consistent, and well-documented implementations of common data structures. The core philosophy is to emphasize the abstract properties and operations of data types, allowing learners to understand the "why" behind a structure's design before diving into the "how" of its implementation. We prioritize **clarity**, **consistency**, and **conceptual separation** over raw speed or feature-richness.

## **2. TAGS**

The tag system is the primary method for categorizing and comparing data structures. Each structure in the library will be associated with a set of tags from the categories below.

### **Structure**

This tag categorizes the data structure based on its logical organization and underlying memory model.

*   **Linear:** Elements are arranged in a sequential or linear manner.
    *   **Array-based:** Implemented using a contiguous block of memory. This typically provides fast O(1) indexed access but can be slow for insertions/deletions in the middle.
    *   **List-based:** Elements are linked to one another via pointers. This allows for efficient O(1) insertions/deletions but requires traversing the list for indexed access.
*   **Tree:** A hierarchical structure with a root node and child nodes. Excellent for representing hierarchical data and enabling efficient searching.
*   *   **Heap:** A specialized, partially-ordered tree-based structure that satisfies the heap property (e.g., in a min-heap, every parent is smaller than its children).
*   **Graph:** A collection of nodes (vertices) and edges that connect them, representing complex relationships.
*   *   **DAG:** A directed graph without cycles.
*   **Mapping:** Uses a hash function to map keys to indices in an array, providing average O(1) time for key-based operations.

### **Mutability**

This tag indicates whether the data structure can be modified after it is created.

*   **Mutable:** Allows for the modification of its state (e.g., insertion, deletion, update) after creation.
*   **Immutable:** Does not allow for modification after creation. Any "modification" operation returns a new, independent instance of the data structure with the change applied.

### **Access**

This tag describes the primary access pattern or intended use case of the data structure.

*   **Key-based Access:** Storing and retrieving data using a unique key. The primary operations involve keys, not positions.
*   **Sequential Access:** Accessing elements in a specific, predictable order relative to their insertion.
    *   **FIFO (First-In, First-Out):** A "queue" access pattern. The first element added is the first to be removed.
    *   **LIFO (Last-In, First-Out):** A "stack" access pattern. The last element added is the first to be removed.
    *   **Double-ended (Deque):** Allows for addition and removal of elements from both ends.
*   **Priority-based Access:** Elements are accessed based on an intrinsic priority, not their insertion order. The highest (or lowest) priority element is always accessed first.
*   **Range-based Queries:** Optimized for efficiently querying data within a specified range of values on a single dimension.
    *   **Prefix/Suffix Search:** A specialized form of query for finding data that starts or ends with a certain sequence, common in stringology.

### **Ordering**

This tag describes the ordering guarantees of the elements within the structure.

*   **Ordered:** The elements are maintained in a specific, sorted order based on their values (e.g., 1, 2, 3, 4). Iteration will yield elements in this sorted order.
*   **Insertion-Ordered:** The elements maintain the order in which they were inserted. Iteration will yield elements in their original insertion sequence. (This is a useful new sub-category for structures like Linked Lists).
*   **Unordered:** The elements have no guaranteed order. Iteration order may be arbitrary and can change between runs. (NOTE: I am still not sure if this should exists...)

## **3. Core Operations API (ADT View)**

This section defines a minimal, consistent set of operations. Concrete data structures will implement a subset of this API. The goal is to use these generic names to teach the abstract concepts.

### **Lifecycle Operations**

*   **`create()`**: Initializes a new, empty data structure.

### **Traversable / Collection Query Operations**

This group contains operations for querying the collection as a whole, inspired by the `Foldable` and `Traversable` concepts in functional programming. They allow you to inspect the container's state or retrieve all its contents without reference to a specific key or position.

*   **`size()`**: Returns the total number of elements in the collection.
*   **`isEmpty()`**: Returns `true` if the collection contains no elements, `false` otherwise.
*   **`elements()`**: Returns a list or array containing all elements in the collection. The order of elements depends on the structure's `Ordering` tag (e.g., insertion-ordered, sorted, or arbitrary). This operation is fundamental for iteration.

### **Element-based Operations**

These operations treat the structure as a collection of elements without a specific key or position.

*   **`insert(element)`**: Adds an element to the collection. The exact behavior (e.g., where it's added) is defined by the data structure's access pattern (LIFO, FIFO, etc.).
*   **`delete()`**: Removes an element from the collection. The exact behavior (e.g., which element is removed) is defined by the access pattern. Returns the removed element.
*   **`contains(element)`**: Returns `true` if the specified element exists in the structure, `false` otherwise.
*   **`find(element)`**: Searches for an element. On success, returns information about the element's location (e.g., its index, a node reference). On failure, returns a null/failure indicator.

### **Key-based Operations**

These operations are for structures that associate keys with values (Mappings, Tries).

*   **`insert_keyed(key, value)`**: Associates a `value` with a `key`. If the key already exists, its value is updated.
*   **`delete_keyed(key)`**: Removes the key and its associated value. Returns the removed value.
*   **`get_keyed(key)`**: Retrieves the value associated with a specific `key`.
*   **`contains_key(key)`**: Returns `true` if the specified key exists, `false` otherwise.

### **Positional & Range Operations**

These operations are for structures where element position is well-defined (e.g., Array-based lists, Deques).

*   **`get_at(position)`**: Retrieves the element at a specific, zero-based index or position.
*   **`get_slice(start_position, end_position)`**: Retrieves a new, shallow copy of the collection containing elements in the specified contiguous range.
*   **`get_subsequence(sequence_of_positions)`**: Retrieves elements from a non-contiguous set of positions, returned in the order they were requested.

## **4. Data Structures & Operation Mappings**

This section details the specific data structures, their tags, and how they map the Core Operations API to their conventional, well-known method names. This mapping is a key pedagogical tool.

---

### **Stack**

*   **Description:** A linear structure that follows a Last-In, First-Out (LIFO) principle.
*   **Tags:**
    *   `Structure: Linear, List-based` (common) or `Array-based`
    *   `Mutability: Mutable`
    *   `Access: Sequential Access, LIFO`
    *   `Ordering: Insertion-Ordered`
*   **Supported Operations:** `create`, `insert`, `delete`, `get_at(0)` (for peeking), `size`, `isEmpty`, `elements`.
*   **Operation Mapping (Pedagogical Notes):**
    *   `insert(element)` -> **`push(element)`**
    *   `delete()` -> **`pop()`**
    *   `get_at(0)` -> **`peek()`** or **`top()`**

---

### **Queue**

*   **Description:** A linear structure that follows a First-In, First-Out (FIFO) principle.
*   **Tags:**
    *   `Structure: Linear, List-based` (common) or `Array-based` (as a circular buffer)
    *   `Mutability: Mutable`
    *   `Access: Sequential Access, FIFO`
    *   `Ordering: Insertion-Ordered`
*   **Supported Operations:** `create`, `insert`, `delete`, `get_at(0)` (for peeking), `size`, `isEmpty`, `elements`.
*   **Operation Mapping (Pedagogical Notes):**
    *   `insert(element)` -> **`enqueue(element)`**
    *   `delete()` -> **`dequeue()`**
    *   `get_at(0)` -> **`peek()`** or **`front()`**

---

### **Deque (Double-Ended Queue)**

*   **Description:** A linear structure that allows for efficient insertion and deletion at both its front and back.
*   **Tags:**
    *   `Structure: Linear, List-based` (as a doubly-linked list) or `Array-based`
    *   `Mutability: Mutable`
    *   `Access: Sequential Access, Double-ended`
    *   `Ordering: Insertion-Ordered`
*   **Supported Operations:** `create`, `insert`, `delete`, `get_at`, `size`, `isEmpty`, `elements`.
*   **Operation Mapping (Pedagogical Notes):**
    *   `insert(element, at_front=false)` -> **`insert_back(element)` / `push_back(element)`**
    *   `insert(element, at_front=true)` -> **`insert_front(element)` / `push_front(element)`**
    *   `delete(from_front=false)` -> **`delete_back()` / `pop_back()`**
    *   `delete(from_front=true)` -> **`delete_front()` / `pop_front()`**

---

### **Trie (Prefix Tree)**

*   **Description:** A tree-like structure for storing a dynamic set of strings, optimized for prefix-based searches.
*   **Tags:**
    *   `Structure: Tree`
    *   `Mutability: Mutable`
    *   `Access: Key-based Access, Range-based Queries, Prefix/Suffix Search`
    *   `Ordering: Ordered` (Keys are retrievable in lexicographical order)
*   **Supported Operations:** `create`, `insert_keyed`, `delete_keyed`, `contains_key`, `find`, `size`, `isEmpty`, `elements`.
*   **Operation Mapping (Pedagogical Notes):**
    *   `insert_keyed(key, value)` -> **`insert(word, value)`**: Here the `key` is the word itself. The `value` could be a boolean flag or associated metadata.
    *   `delete_keyed(key)` -> **`delete(word)`**
    *   `contains_key(key)` -> **`contains(word)`**
    *   `size()` -> **`count_words()`**: Returns the number of complete words stored in the Trie.
    *   `elements()` -> **`get_all_words()`**: Returns all stored words, typically in lexicographical order.
    *   The `find` operation can be adapted for powerful queries like `find_words_with_prefix(prefix)`.

---

### **DAFSA (Deterministic Acyclic Finite State Automaton)**

*   **Description:** A highly compressed representation of a set of strings (like a Trie), but which merges all common suffixes. It is typically built once and then used for fast lookups.
*   **Tags:**
    *   `Structure: Graph` (as it's a DAG)
    *   `Mutability: Immutable` (once built)
    *   `Access: Key-based Access, Prefix/Suffix Search`
    *   `Ordering: Unordered` (Lexicographical ordering is lost due to suffix merging)
*   **Supported Operations:** `create(from_list_of_words)`, `contains_key`, `size`, `isEmpty`, `elements`.
*   **Operation Mapping (Pedagogical Notes):**
    *   `create(from_list_of_words)` -> **`build(word_list)`**: The structure is created in a single batch operation.
    *   `contains_key(key)` -> **`lookup(word)`**: The primary use is extremely fast membership testing.
    *   `elements()` -> **`get_all_words()`**: This may be a computationally expensive operation if not planned for during the build process, which is a valuable pedagogical point about the trade-offs of this structure.
    *   No `insert` or `delete` operations are typically supported on a built DAFSA, perfectly illustrating the `Immutable` tag.

---

### **Suffix Tree**

*   **Description:** A compressed trie containing all suffixes of a single given text. It is a powerful tool for complex substring queries.
*   **Tags:**
    *   `Structure: Tree`
    *   `Mutability: Immutable` (built for a single text)
    *   `Access: Range-based Queries, Prefix/Suffix Search`
    *   `Ordering: N/A` (structure is determined by the suffixes of the source text)
*   **Supported Operations:** `create(from_text)`, `contains`, `find`, `size`, `isEmpty`, `elements`.
*   **Operation Mapping (Pedagogical Notes):**
    *   `create(from_text)` -> **`build(text)`**: The entire tree is generated from a source string.
    *   `contains(substring)` -> **`is_substring(query)`**: A highly efficient O(m) check where m is the length of the query string.
    *   `find(substring)` -> **`find_occurrences(query)`**: Can be used to find the starting positions of all occurrences of a substring.
    *   The traversable operations (`size`, `isEmpty`, `elements`) on a Suffix Tree require careful definition. For example, `size()` could mean the number of nodes, or more usefully, the number of suffixes (leaf nodes). `elements()` could return all the suffixes. These are not typically primary operations but can be implemented.

## **5. Future Development & Next Steps**

*   **Complexity Analysis:** Each operation for each data structure should be documented with its Big-O time and space complexity (amortized, average, and worst-case). This is a critical pedagogical component.
*   **Visualizations:** Integrate or provide hooks for simple textual or graphical visualizations of the data structures to aid understanding.
*   **Implementations:** Add more data structures (e.g., Hash Table, Binary Search Tree, AVL Tree, Red-Black Tree, Heap, Graph).
*   **Generic Typing:** The spec should eventually define how it handles generic element types.