COMP 5421-BB Assignment 1 Due 30 May 2025 Contents 1 Introduction 1.1 Heads-up 2 Objective NN 2.1 Functional Requirements . . 3 Sample Program Run CO 4 Class Specifications 4.1 Token Class 4.2 IntList Class . 4.3 IndexedToken Class 4.4 DLList Class 8 4.5 Indexer Class 10 4.6 Indexer UI Class . . 12 4.6.1 IndexerUI Class Starter Code 12 5 Implementation Guidelines & Constraints 12 6 Deliverables and Submission Process 13 1 Submission Instructions: 13 6.2 Required Files: . . 13 7 Grading Criteria 14 O1 Introduction Welcome to your first assignment in the Advanced Programming course! This assignment serves as a fundamental introduction to C++ programming, with a specific focus on core language mechanics often abstracted away in other languages or even in modern C++ idioms. We will intentionally be working with manual memory management (using new, delete, new, delete), raw pointers, and custom data structures built from the ground up. While contemporary C++ provides powerful tools like smart pointers and standard library containers (std: : vector, std: :list, std::string, std: :map) to automate resource management and provide robust data structures, understanding the underlying principles is crucial for becoming a proficient C++ developer. This assignment requires you to engage directly with these lower-level concepts for several key reasons: e Understanding Core Mechanics: By manually allocating and deallocating memory, you gain a deep appreciation for resource lifetimes, ownership semantics, and the potential pitfalls (like memory leaks or dangling pointers) that modern C++ tools are designed to prevent. Implementing Data Structures: Building your own dynamic array (IntList) and doubly linked list (DLList) clarifies how these fundamental structures work internally and provides context for using their standard library counterparts later. Mastering the Rule of Five: Correctly managing resources in classes that own dynamically allocated memory necessitates understanding and implementing the destructor, copy constructor, copy assignment operator, and potentially the move constructor and move assignment operator (the Rule of Five). This assignment requires explicit consideration of these special member functions for relevant classes. Developing Debugging Skills: Memory-related errors are common when working with manual management. This assignment will inevitably require you to develop skills in debugging using tools like integrated debuggers to find and fix leaks, invalid memory access, and other pointer-related issues. Context for Modern C++: Experiencing the challenges firsthand provides the necessary context to fully appreciate why modern C++ emphasizes RAII (Resource Acquisition Is Initialization), smart pointers, and standard containers. 1.1 Heads-up This assignment is designed to be challenging and requires meticulous attention to detail regarding pointer manipulation, memory allocation/deallocation, and class design involving resource ownership. The challenge isn't the programming concepts themselvesit's adjusting to C+-+'s unique rules and structure, especially if you have used languages like Python or Java, which have simpler syntax. This is very common! To support you, this assignment provides a detailed blueprint for the program you will 4.5 Indexer Class Purpose: To manage the complete text indexing workflow, storing the resulting index as an array of 27 alphabetically sorted sections, each implemented using a DLList. Required Functionality: Acts as the primary intermediary, connecting the user interaction layer (IndexerUI) with the underlying sorted token storage (DLList sections). . Provides the core functionalities for: - Reading and indexing tokens from a specified text file. - Presenting the indexed data to the user in various ways: the entire index, a single section, or tokens matching a specific length. Ensures that each token is inserted into the correct alphabetical or non-alphabetical section (a,A-+0, b,B-+1, . . ., z,Z-25, non-alpha-26) and that each DLList section remains sorted. This is accomplished by leveraging the DLList's positional interface (get IndexedTokenAt, insertBefore) to insert tokens in their sorted position within the determined section. Indexer DLList sections [27] ; sections[0] sections [2] sections [4 sections [26] DLL DLL DLL DLL DLL . . . DLL DLL sections [1] sections [3] sections [25Indexer Manages the entire text file indexing process, storing the index into 27 sections of tokens. - index: DLList [27] Stores the index, all 27 sections (DLLists). current Filename: std::string Name of the currently indexed file. + Indexer() Default ctor: Initializes 27 empty sections. + ~Indexer() Destructor: =default + Indexer(source: const Indexer&) Copy constructor: =delete, for efficiency operator=(source: const Indexer& ) : Copy assignment: =delete, for efficiency Indexer& + Indexer(source: Indexer&&) noexcept Move constructor:=default, for efficiency - operator=(source: Indexer&&) noexcept: Move assignment: =default, for efficiency Indexer& process Token (text: const char*, lineNumber: int): Locates the correct section and checks if the void supplied token already exists in that sec- process Token(token: Token, lineNumber: int): tion; if it does, calls addLine (line) on the void IndexedToken that stores the token; other- wise, constructs a brand new IndexedToken and inserts it in sorted order into the section. process TextFile(filename: const std::string&): If filename does not open successfully, void displays an error message and returns; otherwise, clears index, reads file contents line by line, tokenizes each line, and passes each token along with the line number to processToken. + clear(): void Empties the entire index. + isEmpty() const : bool Check if the index is empty. + print(os : std::ostream&) const: void Displays the entire index, calling each section's print to write on os. + display AllTokens() const : void print (std: : cout) ; + listByLength(length: size_t) const : void Displays the tokens of a specified length. + ViewBySection (section: char) const: void Displays the tokens in a specified section.4.6 IndexerUI Class Purpose: To serve as the main application class that orchestrates the overall program flow. Required Functionality: e Interacts with the user through a text-based menu. e Contains the main application loop: Repeatedly displays the menu, gets validated user input, and dispatches control to the appropriate private processing method based on the user's choice (Index, Display, List, View, Exit). e Defines explicitly all the special member functions via = default. 4.6.1 IndexerUI Class Starter Code To facilitate your start, a complete IndexerUI class implementation is provided as a starting point, allowing you to focus on implementing and integrating other program components. You can find and download IndexerUI.h and IndexerUI.cpp within the "Assignment 1" folder on Moodle. 5 Implementation Guidelines & Constraints 1. Token Class Restrictions: e The Token class must use only functions from the and head- ers, such as strlen, strcpy, strcmp, isalpha, etc. e It must not use std::string or any other C++ Standard Library string utilities. 2. Restriction on STL Containers and Algorithms: Do not use STL containers (e.g., std: : vector, std::list, std: :map) within the implementation of any of the assignment's classes. Instead, manually implement data structures like linked lists and dynamic arrays to gain a deeper understanding of their underlying mechanisms. Avoid using functions from the header (e.g., std: :sort, std: :find). Implement sorting, searching, and other logic manually to practice fundamental algorithm design and implementation. 6 Deliverables and Submission Process 6.1 Submission Instructions: Please refer to the course outline for the specific submission guidelines you must follow. 6.2 Required Files: Ensure your submission includes all the following files: Token . h, Token . cpp . IntList . h, IntList . cpp . IndexedToken. h, IndexedToken . cpp . DLList . h, DLList . cpp . Indexer . h, Indexer . cpp . IndexerUI . h, IndexerUI . cpp (provided starter code) . README . txt main. cpp, a driver program which simply creates a IndexerUI object and calls its run () method: main.cpp Driver Program #include 2 #include "IndexerUI.h" 4 int main() { std: : cout 0. Token text . "Apple"Required Functionality: 1. Manually allocates/ deallocates C-style string (char*) storage for storing the text of a token using new and delete 2. Ensures that the char* member text always points to a valid, null-terminated C-string even for empty tokens. Specifically, for an empty token, it must point to a dynamically allocated 1-byte array containing only '\\0'. It should never be nullptr after construction. This constraint must be satisfied by the move oper- ations, which must leave the moved-from objects in a state where they represent empty tokens This design is more common and preferred because it simplifies code by elimi- nating the need to constantly check for nullptr and more closely resembles the behavior of std: :string, which always represents an empty string as a valid object. 3. Uses functions (e.g., strlen, stropy, stromp, etc. ) for string opera- tions. 4. Uses functions (e.g., isalpha, ispunct, tolower, etc.) for character operations. 5. Avoids using std: : string or other STL containers.4.2 IntList Class Purpose: To represent and manage a dynamically growing sequence of integers, specifically intended for storing line numbers associated with a token. IntList A dynamic list of integers. pData : int* Pointer to the dynamic array. - size : size_t Number of elements currently stored. capacity : size_t Size of the dynamic array currently allocated. + IntList (): Default constructor: Initializes to empty state. + IntList (other : const IntList& ): Copy Constructor (deep copy). + operator=(other : const IntList&): IntList& Copy Assignment Operator (deep copy, handles self-assignment). + IntList(other : IntList&& ) noexcept: Move constructor: Transfers ownership of the dy- namic array from other, leaving other in a valid, empty state (i.e., sets other . pData to nullptr, and both other . count and other . capacity to 0). + operator=(other : IntList&&): IntList& Move assignment operator: Handles self- assignment, releases current array, and takes ownership of other's array, leaving other in a valid, empty state. + ~IntList () : Destructor: Frees the allocated array. + append(lineNumber : int) : void Appends lineNumber to the end of the list, re- sizing the dynamic array if necessary. + clear(): void Removes all elements and deallocates memory. + getSize() const: int Returns size, the number of integers stored resize() : void Resizes array capacity; starts at 2, then doubles. + isEmpty () const : bool Checks if size is 0. + isFull() const : bool Checks if size is equal to capacity. + print(os : std::ostream&) const: void Writes the list contents to the stream os. + getElementAt(size_t index) const: int Returns element at the specified 0-based index. Throws std: :out_of_range if index if invalid. Required Functionality: 1. Manually allocates/ deallocates dynamic array (int*) for storing integers using raw pointers and new and delete . IntList 2. Appends only performing no sorting or uniqueness checks. pData 3. Resizes capacity when full to: capacity == 0 ? 2 : capacity * 2; 1 5 7 (i.e., starts at 2 and doubles the capacity whenever more space is 3 size 4 capacity needed.4.3 IndexedToken Class Purpose Aggregates a token and its list of line numbers, representing a complete index entry for the token. Indexed Token Aggregates a Token and an IntList. - token: Token The token. - lines: IntList The list of line numbers. IndexedToken (text: const char*, lineNumber: int) Parameterized constructors: Each initialize IndexedToken(token: Token, lineNumber: int) the token and add the first lineNumber to the lines list + IndexedToken(it: const Indexed Token&): Copy constructor: =default. +IndexedToken(it: IndexedToken&&) noexcept: Move constructor: =default. + operator=(it: const IndexedToken&): IndexedToken& Copy assignment operator: =default. + operator=(rhs: IndexedToken&&): IndexedToken& Move assignment operator: =default. + ~Indexed Token (): Destructor: =default. + appendLineNumber(lineNumber: size_t): void Appends lineNumber to the lines list. + getToken() const: const Token& Returns token by const Token& + getLineNumbers() const: const IntList& Returns lines by const IntList& + print(os : std::ostream&) const: void Writes token followed by lines to os. + compare(other : const char*) const : int Compares token's text with a C-string (delegates to std: : stromp). compare(other : const IndexedToken&) const : Compares token with other. token int (delegates to Token: : compare). Required Functionality: Involves no direct dynamic memory management, relying entirely on the Rule of Five implementations of its Token and IntList members. an indexed token ndexedToken an indexed token lines Indexed Token token IntList oken lines Token pData Token IntList text "Apple" 1 5 7 3 size 4 capacity an indexed token Indexed Token4.4 DLList Class Purpose: To manage a section of IndexedToken objects using an internal doubly linked list structure. Required Functionality: e The doubly linked list is implemented using a private nested Node class within DLList. To fully encapsulate the linked list implementation, DLList makes the Node class and all node- related methods (e.g., those accepting or returning Node*) private, ensuring no direct exposure of the internal node structure to users. This design provides several key benefits: a Node object Node next [-4{-}- prev Indexed Token data Simpler Interface: Clients interact with DLList without needing knowledge of the underlying linked list implementation (e.g., node connections). Implementation Hiding: Clients interact solely through DLList's public inter- face, with no direct access to Node objects. Safety: Preventing direct Node access mitigates risks of misuse, such as broken links, list corruption, and memory leaks. Flexibility: The internal implementation of DLList can be modified (e.g., to a circular list) without impacting client code. OOP Principles: Adheres to encapsulation and information hiding by concealing the internal Node structure, promoting loose coupling and good object- oriented design. Internally manages the dynamic allocation, deallocation, and linking of Node objects using raw pointers and new/delete. e Offers a 0-based positional interface for accessing and manipulating IndexedToken objects, throwing std: :out_of_range for invalid positions. e Maintains head and tail pointers to the first and last nodes, updating them appro- priately during additions and removals. a DLList object DLList mal, head size | 4 tail : | node 1 node 2 node 3 node 4 Node Node Node Node next jig _| 4] next |i | 5 next |i __| 4 next |@ BB ev jf | prev i prev prev Indexed Token Indexed Token Indexed Token! Indexed Token data data data data 7 a DLList object DLL DLList Represents a doubly linked list of IndexedToken objects. head : Node * Pointers to the first node of the doubly linked list. tail : Node* Pointers to the last node of the doubly linked list. nodeCount : size_t Tracks total nodes. getNodeAt(pos: size_t): Node* Helper to return the node at position pos. + DLList() Default constructor: Initializes an empty linked list, setting both head and tail to nullptr. + ~DLList() Destructor: Deletes all nodes. + DLList (dll : const DLList&) Copy ctor. Deep copies dll into this linked list. + operator=(dll: const DLList&): DLList& Copy assignment: Deletes the current linked list, replacing it with deep copy of dll + DLList(dll: DLList&&) noexcept Move ctor: Transfers ownership of nodes from dll to this list, leaving dll in stable state. + operator=(dll: DLList&&) noexcept: DLList& Move assignment: Deletes the current linked list, then transfers ownership of nodes from dll to this list, leaving dll in a stable state. + addBefore(data: IndexedToken, pos: size_t): Inserts data before the node at position pos (0- void based, throws std: :out_of_range). + remove(pos: size_t): bool Removes the node at position pos (0-based, throws std: : out_of_range). getIndexedTokenAt(pos: size_t): IndexedTo- Returns a reference to data at position pos (0- ken& based, throws std: : out_of _range) getIndexedTokenAt(pos: size_t) const : Returns a const reference to data at position const Indexed Token& pos (0-based, throws std: : out_of_range). + clear(): void Removes all nodes. + size() const: size_t Returns nodeCount. + isEmpty () const: bool Check if this list is empty. + print (os : std::ostream&) const: void Calls print (os) on data stored in each node. Private member type Node Represents a node storing an IndexedToken. - prev : Node* Pointer to previous node - data : IndexedToken Stores the IndexedToken data in this node. - next : Node* Pointer to next node + Node(data : const IndexedToken&, Constructor: initializes prev pointer, next prv: Node*, nxt: Node*) pointer, and the node data