# CTDL & GT
## Ứng dụng Ngăn xếp (Stack) để tạo menu
Đối việc hiển thị các thông tin lựa chọn lên giao diện, ta xem màn hình đang hiển thị một `Menu`. Như vậy, một `Menu` có thể sẽ bị xếp chồng lên bởi một `Menu` khác và màn hình hiện tại chỉ hiển thị `Menu` đang ở trên đỉnh.
Để cài đặt, ta định nghĩa 2 lớp là `Menu` (định nghĩa một `Menu` - bao gồm các lựa chọn và tiêu đề) và `MenuStack` (chứa một ngăn xếp các `Menu`). Các phương thức trên lớp `MenuStack` có thể kể đến như:
- Phương thức `push(Menu)`: thêm một `Menu` lên đỉnh ngăn xếp
- Phương thức `pop()`: xoá bỏ đi `Menu` đang ở đỉnh ngăn xếp
- Phương thức `top()`: lấy ra `Menu` đang ở đỉnh ngăn xếp (để hiển thị)
- Phương thức `getChoice()`: yêu cầu người dùng nhập vào một chọn lựa và trả về số ứng với chọn lựa (đã bao gồm việc kiểm tra hợp lệ)
:::info
Cài đặt của 2 lớp này có thể tìm thấy ở file mã nguồn `Menu.h`.
:::
Việc định nghĩa ra các `Menu` và sử dụng chúng sẽ được thể hiện ở file mã nguồn `main.cpp`. Ở đây các `Menu` bao gồm: Đăng nhập, Chọn mục cần quản trị, Quản lý sách, Quản lý độc giả, Quản lý thủ thư, Quản lý mượn-trả và các `Menu` tìm kiếm.
```cpp=
const Menu loginMenu("WELCOME TO THE LIBRARY", vector<string>{"Login as librarian"});
const Menu mainMenu("WELCOME TO THE LIBRARY", vector<string>{"Books", "Readers", "Borrowing", "Librarians"});
const Menu booksMenu("BOOKS", vector<string>{"List all books", "Add book", "Edit book", "Delete book", "Search book"});
const Menu bookSearchMenu("BOOKS", vector<string>{"Search by id", "Search by title", "Search by author"});
const Menu readersMenu("READERS", vector<string>{"List all readers", "Add reader", "Edit reader", "Delete reader", "Search reader"});
const Menu readerSearchMenu("READERS", vector<string>{"Search by id", "Search by name"});
const Menu borrowingMenu("BORROWING", vector<string>{"List all borrowings", "Add borrowing", "Delete borrowing", "Search borrowing"});
const Menu borrowingSearchMenu("BORROWING", vector<string>{"Search by reader id", "Search by book id"});
const Menu librariansMenu("LIBRARIANS", vector<string>{"List all librarians", "Add librarian"});
```
Việc luân chuyển giữa các `Menu` thực hiện bằng câu lệnh `switch-case`, `goto` kết hợp phương thức `getChoice()`.
```cpp=
// 1. Login screen
loginScreen:
clearScreen();
cout << menuStack;
op = menuStack.getChoice();
switch (op)
{
case 1:
while (!enterLoginMenu());
menuStack.push(mainMenu);
break;
default:
goto exitApp;
}
// 2. Main menu
mainMenu:
clearScreen();
cout << menuStack;
op = menuStack.getChoice();
switch (op)
{
case 1:
menuStack.push(booksMenu);
goto booksMenu;
break;
case 2:
menuStack.push(readersMenu);
goto readersMenu;
break;
case 3:
menuStack.push(borrowingMenu);
goto borrowingMenu;
break;
case 4:
menuStack.push(librariansMenu);
goto librariansMenu;
break;
default:
menuStack.pop();
goto loginScreen;
}
```
Ở mã nguồn trên, sau khi hiển thị `Menu` trên cùng của ngăn xếp `MenuStack` (bằng lệnh `cout << menuStack;`), ta sẽ dựa vào lựa chọn trả về từ phương thức `getChoice()` mà sẽ lựa chọn đẩy `Menu` nào tiếp theo vào ngăn xếp (phương thức `push()`) và di chuyển đến nhãn tương ứng (lệnh `goto`).
## Bảng băm (HashTable), Danh sách liên kết (Linked List) và ứng dụng
Bảng băm là một cấu trúc dữ liệu quan trọng để phục vụ việc tối ưu hoá các truy vấn tìm kiếm, thêm mới, sửa đổi. Ta có thể ứng dụng trong việc lưu trữ các thông tin như: thông tin sách, thông tin mượn-trả hoặc thông tin độc giả. Do được sử dụng ở nhiều nơi và liên quan đến nhiều lớp, cũng như việc lựa chọn khoá để băm cũng phụ thuộc vào ngữ cảnh bài toán. Ta sẽ dựng một lớp chung để cài đặt cấu trúc dữ liệu này (có sử dụng generic).
Một trong những yếu tố quan trọng để xây dựng bảng băm là phải xây dựng **hàm băm**. Hàm băm sẽ quyết định vị trí lưu trữ của dữ liệu (ở đây là kiểu dữ liệu generic `<T>`) trong bảng băm.
Việc lựa chọn hàm băm sẽ được quyết định tại lúc tạo ra một đối tượng của lớp `HashTableLL`. Hai con trỏ hàm `hash` và `isEqual` sẽ trỏ đến hai hàm tương ứng là hàm băm khoá `hash` dựa trên giá trị có kiểu `T` - trả về một số nguyên ứng với giá trị băm được và hàm kiểm tra bằng nhau `isEqual` - kiểm tra xem khoá trong giá trị đứng trước và giá trị đứng sau trong tham số (đều có kiểu `T`) có thực sự bằng nhau hay không.
Việc kiểm tra này là cực kỳ cần thiết trong trường hợp tìm kiếm từ bảng băm, đặc biệt là khi xác suất xảy ra đụng độ luôn tồn tại.
Đối với giải thuật được cài trong lớp `HashTableLL`, việc xử lý đụng độ được dựa trên giải pháp sử dụng danh sách liên kết (hai chữ cái `LL` đại diện cho danh sách liên kết đơn - (single) **L**inked **L**ist). Như vậy, ta xem mỗi dòng trong bảng băm là một danh sách liên kết các `Node`, mà bảng băm là một mảng các `Node` nên sẽ có kiểu dữ liệu con trỏ cấp hai `Node**` (bảng sẽ có `size` dòng). Các phương thức `insert(T)` (thêm một giá trị mới vào bảng băm), `remove(T)` (xoá một giá trị ra khỏi bảng băm) và `search(T)` đều có sử dụng đến hàm `hash(T)` được truyền vào; hàm `isEqual` được sử dụng trong phương thức `remove` để đảm bảo xoá chính xác giá trị (khoá đúng với khoá cần xoá) và `search(T)` để đảm bảo tìm kiếm chính xác các giá trị chứa khoá cần tìm.
```cpp=
vector<T> search(const T& searchKey) const
{
vector<T> result;
int index = hash(searchKey) % size;
Node* current = table[index];
while (current != nullptr)
{
if (isEqual(current->value, searchKey))
{
result.push_back(current->value);
}
current = current->next;
}
return result;
}
```
Đối với phương thức `search(T)`, ta giả định rằng sẽ có nhiều giá trị mang cùng một khoá nên sẽ trả về không, một hoặc nhiều giá trị tìm được trong một mảng.
:::info
Cài đặt của lớp này có thể tìm thấy ở file mã nguồn `HashTableLL.h`.
:::
Đối với từng kho chứa dữ liệu (Repository) - cụ thể là `BookRepository` (chứa thông tin của tất cả sách hiện có), `ReaderRepository` (chứa thông tin của tất cả độc giả) và `BorrowingRepository` (chứa thông tin của tất cả lượt mượn-trả sách) - ta sẽ tạo ra một hoặc một số bảng băm ứng với khoá là thuộc tính đang quan tâm. Ví dụ, đối với `BookRepository`, ta quan tâm việc tối ưu tìm kiếm theo tên tác giả hoặc mã định danh của sách. Do đó, ta sẽ tạo ra 2 bảng băm là `booksByAuthorTable` (ứng với hàm băm khoá là `hashAuthor`, hàm so sánh kiểm tra trùng khớp là `isEqualAuthor`) và `booksByIdTable` (hàm băm khoá là `hashId`, hàm so sánh kiểm tra trùng khớp là `isEqualId`).
Giải thuật trong các hàm băm khoá được sử dụng trong bài cũng hết sức đơn điệu, đó là cộng các ký tự để lấy tổng các giá trị mã hoá ký tự (theo bảng mã ASCII) và trả về tổng đó. Ví dụ đơn giản với hàm `isEqualAuthor` và hàm `isEqualAuthor`:
```cpp=
// Hash function for author
static int hashAuthor(Book* const& book)
{
// Hash author's name, return the sum of ASCII values of all characters
int hashValue = 0;
for (char c : toLower(book->getAuthor()))
{
hashValue += c;
}
return hashValue;
}
// Compare function for author
static bool isEqualAuthor(Book* const& book1, Book* const& book2)
{
return toLower(book1->getAuthor()) == toLower(book2->getAuthor());
}
```
:::info
Cài đặt của các lớp này có thể tìm thấy ở các file mã nguồn `Book.h`, `Reader.h` và `Borrowing.h`.
Ngoài ra, bảng băm còn được sử dụng trong file mã nguồn `Librarian.h` để phục vụ tìm kiếm nhanh thủ thư để thực hiện bước đăng nhập hệ thống. Tuy nhiên, nếu số lượng thủ thư ít thì việc tối ưu này cũng không mang lại nhiều lợi ích mà ngược lại còn gây hao tổn không ít không gian bộ nhớ để chứa cả bảng băm.
:::
Song song với việc tìm kiếm (ví dụ như phương thức `getBookById(string)`, `getBooksByAuthor(string)`,...), việc thực hiện các thao tác thêm hay xoá cũng sẽ làm ảnh hưởng đến dữ liệu trên bảng băm. Do đó, trên các phương thức như `addBook(...)`, `removeBook(string)`,... ta cũng sẽ phải xử lý cập nhật trên các bảng băm tương ứng. Dưới đây là minh hoạ cho các phương thức kể trên.
```cpp=
// This is not the final code, just for demonstrating the example above
// Find books by author
vector<Book*> getBooksByAuthor(const string& author) const
{
Book temp("", "", author, "", "", 0, 0);
return this->booksByAuthorTable.search(&temp);
}
// Add a new book
Book* addBook(const string& bookId, const string& title, const string& author, const string& category, const string& publisher, int year, int quantity)
{
// Check if the book already exists
Book* book = getBookById(bookId);
if (book != nullptr)
{
cout << "Book with id " << bookId << " already exists\n";
return nullptr;
}
// Create a new book
book = new Book(bookId, title, author, category, publisher, year, quantity);
// Insert to hash tables
booksByAuthorTable.insert(books.back());
booksByIdTable.insert(books.back());
return book;
}
// Remove a book by id
bool removeBook(const string& bookId)
{
// Find the book by id
Book* book = getBookById(bookId);
if (book == nullptr)
{
cout << "Book with id " << bookId << " not found\n";
return false;
}
// Remove the book from the hash tables
booksByAuthorTable.remove(book);
booksByIdTable.remove(book);
// Free memory
delete book;
return true;
}
```
Để minh hoạ cho cách hoạt động, ta giả sử có 3 cuốn sách và một bảng băm có kích thước là 5 (chỉ số dòng là 0, 1, 2, 3, 4) và 3 quyển sách có mã định danh lần lượt là:
- `BOOK00001`: giá trị băm được là `66+79+79+75+48+48+48+49=492`, vị trí trong bảng băm là `492 % 5 = 2`
- `BOOK00002`: giá trị băm được là `66+79+79+75+48+48+48+50=493`, vị trí trong bảng băm là `493 % 5 = 3`
- `BOOK00010`: giá trị băm được là `66+79+79+75+48+48+49+48=492`, vị trí trong bảng băm là `492 % 5 = 2`
Vậy sau khi thêm tất cả vào bảng băm `booksByIdTable`, ta được kết quả như sau:
## Cây nhị phân cân bằng AVL (AVL Tree) và ứng dụng
Ngoài việc sử dụng bảng băm, ta có thể sử dụng thêm cây nhị phân cân bằng AVL để tối ưu hoá thao tác tìm kiếm. Trong bài này, ta cũng sẽ cài đặt cây AVL dưới dạng sử dụng generic và cung cấp sẵn một số phương thức trên cây.
Cây AVL sử dụng chiều cao để cân bằng, do đó các thông tin cơ bản trong một nút (`Node`) bao gồm: `value` (giá trị tại nút), `left` (nút bên trái), `right` (nút bên phải) và `height` (chiều cao nút hiện tại).
Tương tự như cài đặt của `HashTableLL`, các phương thức cơ bản phải có của lớp `AVLTree` bao gồm: phương thức `insert(T)` (thêm một giá trị mới vào cây - ứng với việc tạo mới một nút), `remove(T)` (xoá một giá trị ra khỏi cây - ứng với việc xoá đi một nút) và `search(T)` (so sánh và tìm ra một hoặc một số giá trị (nút) thoả điều kiện bằng của hàm so sánh `compare(T, T)` truyền vào lúc tạo ra `AVLTree`).
Ngoài ra các phương thức hỗ trợ như tính toán chiều cao của nút `height(Node*)`, tính độ chênh lệch chiều cao tại nút (bằng chiều cao cây con trái trừ chiều cao cây con phải) `getBalance(Node*)`, xoay trái `leftRotate(Node*)`, xoay phải `rightRotate(Node*)`, thêm nút vào cây `insert(Node*, T)`, xoá nút khỏi cây `remove(Node*, T)`, tìm nút con bé nhất (nút trái cùng) `minValueNode(Node*)` cũng được cài đặt để hỗ trợ các phương thức chính phía trên.
:::info
Cài đặt của lớp này có thể tìm thấy ở file mã nguồn `AVLTree.h`.
:::
Cây AVL được sử dụng ở 2 kho chứa là `BookRepository` (phục vụ tìm kiếm theo tên sách) và `ReaderRepository` (phục vụ tìm kiếm theo tên độc giả). Ứng với đó là 2 phương thức so sánh `compareTitle(Book*, Book*)` và `compareReaderByName(Reader*, Reader*)`:
```cpp=
// Book.h
// Compare function for title
static int compareTitle(Book* const& book1, Book* const& book2)
{
return toLower(book1->getTitle()).compare(toLower(book2->getTitle()));
}
```
```cpp=
// Reader.h
// Compare function for reader by name
static int compareReaderByName(Reader* const& reader1, Reader* const& reader2)
{
return toLower(reader1->getName()).compare(toLower(reader2->getName()));
}
```
Ở trong hai phương thức so sánh này có sử dụng đến hàm `toLower()` (có thể tìm thấy trong file mã nguồn `StringHelper.h`) để chuyển đổi chuỗi về dạng in thường, từ đó cho phép tìm kiếm không phân biệt hoa thường.
Đương nhiên, việc thêm hay xoá dữ liệu sách, độc giả cũng làm cây phải cập nhật. Do đó trong các phương thức như `addBook(...)`, `removeBook(string)`,... cũng sẽ phải gọi đến các phương thức cập nhật của cây.
```cpp=
// This is not the final code, just for demonstrating the example above
// Add a new book
Book* addBook(const string& bookId, const string& title, const string& author, const string& category, const string& publisher, int year, int quantity)
{
// Check if the book already exists
Book* book = getBookById(bookId);
if (book != nullptr)
{
cout << "Book with id " << bookId << " already exists\n";
return nullptr;
}
// Create a new book
book = new Book(bookId, title, author, category, publisher, year, quantity);
// Construct AVL tree
booksByTitleTree.insert(books.back());
return book;
}
// Remove a book by id
bool removeBook(const string& bookId)
{
// Find the book by id
Book* book = getBookById(bookId);
if (book == nullptr)
{
cout << "Book with id " << bookId << " not found\n";
return false;
}
// Remove the book from the hash table and AVL tree
booksByTitleTree.remove(book);
// Free memory
delete book;
return true;
}
```
:::info
Cài đặt của các lớp này có thể tìm thấy ở các file mã nguồn `Book.h` và `Reader.h`.
:::
Để minh hoạ cho cách hoạt động, ta giả sử có 3 cuốn sách có tên lần lượt là:
- `ABC`
- `AAC`
- `ACD`
- `ACE`
Vậy sau khi thêm tất cả vào cây AVL `booksByTitleTree` theo thứ tự, ta được kết quả như sau:
Nếu ta thêm một cuốn sách có tiêu đề là `ADE`, cây sẽ bị mất cân bằng tại nút `ACD` và phép xoay trái xảy ra tại nút này để cây cân bằng lại như sau:
Sign in with Wallet
Connect another wallet