Bookshelf Data Structure Project

A modern C++17 implementation of a type-safe bookshelf data structure that organizes values by C++ type. Each type gets its own "shelf" (a TypedShelf) which can operate in either sorted or unsorted modes.

Features

• Type-Safe Storage: Store different types in the same data structure
• Dual-Mode Shelves: Each type can have both sorted and unsorted shelves
• Binary Search: Fast lookups in sorted shelves using binary search
• Range Queries: Get all values within a range [lower, upper]
• Min/Max Operations: O(1) min/max retrieval from sorted shelves
• Modern C++: Leverages C++17 features like constexpr if and structured bindings
• Comprehensive Tests: Unit tests for all major functionalities

Project Structure

bookshelf-dsa-project/
├── CMakeLists.txt              # CMake build configuration
├── README.md                   # This file
├── include/                    # Header files
│   ├── Bookshelf.hpp           # Main bookshelf class
│   ├── TypedShelf.hpp          # Template class for type-specific shelves
│   ├── ShelfInfo.hpp           # Metadata structure about shelves
│   └── ShelfEntry.hpp          # Shelf entry combining metadata and shelf pointer
├── src/                        # Implementation files
│   ├── main.cpp                # Demo application
│   └── Bookshelf.cpp           # Bookshelf implementation
└── test/                       # Test files
    ├── test_typed_shelf.cpp    # Unit tests for TypedShelf
    └── test_bookshelf.cpp      # Unit tests for Bookshelf

Building

Prerequisites

• C++17 compatible compiler (GCC 7+, Clang 5+, MSVC 2017+)
• CMake 3.10 or higher

Build Instructions

cd /path/to/bookshelf-dsa-project
mkdir build
cd build
cmake ..
make

Run Application

./bin/bookshelf_app

Run Tests

Run individual test suites:

./bin/tests/test_typed_shelf
./bin/tests/test_bookshelf

Or run all tests with CMake:

make test

Class Overview

TypedShelf<T, Sorted>

A template class that stores values of a single type T in a std::list.

Template Parameters:

• T: The type of data stored in the shelf
• Sorted (default: true): Whether the shelf maintains sorted order

Features:

• Sorted mode (Sorted=true): Maintains elements in sorted order using std::lower_bound
• Unsorted mode (Sorted=false): Maintains insertion order
• Requires operator< for comparisons in sorted mode
• Requires operator== for all modes

Key Methods:

• void add(const T& value) - Add a value to the shelf
• bool remove(const T& value) - Remove a value from the shelf
• bool contains(const T& value) - Check if a value exists
• typename std::list::iterator find(const T& value) - Find a value
• const T& min() - Get minimum value
• const T& max() - Get maximum value
• std::list getRange(const T& lower, const T& upper) - Get values in range
• const std::list& getAll() const - Get all values
• size_t size() const - Get number of elements
• bool empty() const - Check if empty
• void print() const - Print shelf contents

ShelfInfo

A structure that stores metadata about a shelf.

Members:

• std::type_index type - The type of data stored
• size_t elementCount - Number of elements
• bool isSorted - Whether shelf is sorted

ShelfEntry

A structure that combines shelf metadata with the actual shelf pointer.

Members:

• ShelfInfo info - Metadata about the shelf
• std::shared_ptr shelf - Void pointer to the actual TypedShelf
• std::function<void()> printFunc - Function to print shelf contents

Bookshelf

The main data structure that manages multiple TypedShelves.

Key Methods:

• template void add(const T& value) - Add value to sorted shelf
• template void addUnsorted(const T& value) - Add value to unsorted shelf
• template bool remove(const T& value) - Remove value from either shelf
• template std::list getAll() const - Get all values of type T
• template size_t count() const - Count values of type T
• template bool contains(const T& value) - Check if value exists
• template const T& min() - Get minimum value
• template const T& max() - Get maximum value
• void print(bool detail=false) - Print all shelves
• size_t shelfCount() const - Get number of different types stored

Usage Example

#include "Bookshelf.hpp"
#include <iostream>
#include <string>

int main() {
    Bookshelf bookshelf;

    // Add different types
    bookshelf.add(5);
    bookshelf.add(2);
    bookshelf.add(10);
    
    bookshelf.add(3.14);
    bookshelf.add(2.71);
    
    bookshelf.add(std::string("hello"));
    bookshelf.add(std::string("world"));

    // Add to unsorted shelves
    bookshelf.addUnsorted('z');
    bookshelf.addUnsorted('a');

    // Check if value exists
    if (bookshelf.contains(5)) {
        std::cout << "Found 5!" << std::endl;
    }

    // Get min/max for each type
    std::cout << "Integer range: [" << bookshelf.min<int>() 
              << ", " << bookshelf.max<int>() << "]" << std::endl;

    // Get values in a range
    auto range = bookshelf.getRange(2, 8);

    // Remove values
    bookshelf.remove(5);

    // Print all shelves
    bookshelf.print();
    bookshelf.print(true);

    return 0;
}

Time Complexity Analysis

Operation	Sorted Shelf	Unsorted Shelf
Add	O(n)	O(1)
Remove	O(n)	O(n)
Contains	O(n)*	O(n)
Find	O(n)*	O(n)
Min	O(1)	O(n)
Max	O(1)	O(n)
Get Range	O(k)	O(n)
Get All	O(n)	O(n)

*Due to std::list sequential access, binary search effectiveness is limited.

Design Decisions

1. Template-Based TypedShelf: Provides type safety and compile-time optimization
2. std::list Container: Chosen for efficient insertion in sorted shelves
3. std::type_index: Used for runtime type identification
4. Dual Shelves Per Type: Support for both sorted and unsorted modes
5. Alphabetical Sorting: Shelves are printed in alphabetical order by type name

Testing

The project includes comprehensive unit tests:

test_typed_shelf.cpp

Tests the TypedShelf template class with various operations.

test_bookshelf.cpp

Tests the Bookshelf class across multiple types.

License

GNU General Public License v3.0

Author

Seymen Kalkan (seymenkalkan@gmail.com)