Skip to content

Latest commit

 

History

History
272 lines (199 loc) · 8.54 KB

README.md

File metadata and controls

272 lines (199 loc) · 8.54 KB

AlgoDataStruct: Data Structures Library (C++)

License C++20

Description

AlgoDataStruct is an educational, header-only C++ library that implements classic data structures with modern C++20. The project favors clear invariants, clean APIs, and well-documented behavior over micro-optimizations.

Key characteristics:

  • Header-only templates with .tpp implementation files included by the public headers
  • STL-friendly iteration/traversal where applicable and explicit error handling via custom exceptions
  • Focused, testable implementations intended for study and extension

Implemented Data Structures

Linear Structures

  • Arrays

    • Static Array
    • Dynamic Array (vector-like growth)
    • Circular Array (wrap-around indexing)

  • Linked Lists

    • Singly Linked List
    • Doubly Linked List
    • Circular Linked List

  • Stacks

    • Array-based Stack
    • Linked-list-based Stack

  • Queues

    • Linked Queue
    • Circular Queue
    • Circular Deque
    • Priority Queue (binary heap)
Trees
  • Complete Binary Tree (level-order insertion)
  • Binary Search Tree (BST)
  • AVL Tree
  • Red-Black Tree
  • B-Tree
  • Trie (Prefix Tree)
  • Fenwick Tree (Binary Indexed Tree)
  • Segment Tree
Heaps
  • Min Heap
  • Max Heap
Hashing Structures
  • Hash table with chaining
  • Hash table with open addressing (linear, quadratic, double hashing)
Associative Structures
  • Dictionary interface
  • HashMap
  • TreeMap
  • HashSet
  • TreeSet
Graph Structures
  • Adjacency List
  • Adjacency Matrix
  • Disjoint Sets (Union-Find)

Roadmap (Advanced)

Planned, not implemented yet:

  • Skip List (advanced)
  • B+ Tree, 2-3 Tree, 2-3-4 Tree
  • String structures (Suffix Tree/Array, Suffix Automaton, Rope)
  • Probabilistic structures (Bloom Filter, Count-Min Sketch, HyperLogLog)
  • Spatial structures (KD-Tree, R-Tree, Quad/Oct-tree)

Repository Organization

AlgoDataStruct/
├── include/
│   └── ads/
│       ├── arrays/
│       ├── lists/
│       ├── stacks/
│       ├── queues/
│       ├── trees/
│       ├── heaps/
│       ├── hash/
│       ├── associative/
│       └── graphs/
├── src/
│   ├── ads/               # .tpp implementation files
│   └── main_*.cc          # usage demos / sample programs
├── tests/                 # unit tests (standalone)
├── docs/                  # generated documentation
│   └── html/
├── Documentation/         # additional notes and PDFs
├── CMakeLists.txt
├── clang-toolchain.cmake
├── gcc-toolchain.cmake
└── Makefile

Code Conventions

  • C++: Google C++ Style Guide conventions
  • Header-only templates: public headers in include/ads, implementations in src/ads
  • Many structures include iterators or traversal callbacks where they make sense
  • Documentation is written in Doxygen style; complexity notes are included when available
  • Tests and demos live in tests/ and src/main_*.cc

Build and Run (optional)

The library is header-only; you can include the headers directly. To build the demo executables in src/main_*.cc:

cmake -DCMAKE_TOOLCHAIN_FILE=clang-toolchain.cmake -B build
cmake --build build

Executables are placed in build/bin/. Use gcc-toolchain.cmake if you prefer GCC.

Usage

C++

// Example usage of an AVL Tree
#include "ads/trees/AVL_Tree.hpp"
#include <iostream>

int main() {
    ads::trees::AVLTree<int> avlTree;

    avlTree.insert(10);
    avlTree.insert(20);
    avlTree.insert(30);

    std::cout << std::boolalpha << avlTree.contains(20) << "\n"; // true
    avlTree.remove(20);
    std::cout << std::boolalpha << avlTree.contains(20) << "\n"; // false

    std::cout << "In-order traversal: ";
    avlTree.in_order_traversal([](const int& value) {
        std::cout << value << " ";
    });
    std::cout << "\n";

    return 0;
}

Example: Using HashMap

#include "ads/associative/Hash_Map.hpp"
#include <iostream>
#include <string>

int main() {
    ads::associative::HashMap<std::string, int> scores;

    // Adding key-value pairs
    scores.put("Alice", 95);
    scores.put("Bob", 89);
    scores.put("Charlie", 92);

    // Retrieving values
    std::cout << "Bob's score: " << scores.get("Bob") << "\n"; // 89

    // Checking if a key exists
    std::cout << "Does David have a score? " << std::boolalpha
              << scores.contains("David") << "\n"; // false

    // Updating a value
    scores.put("Bob", 91);
    std::cout << "Bob's updated score: " << scores.get("Bob") << "\n"; // 91

    // Removing a key-value pair
    scores.erase("Charlie");
    std::cout << "Charlie's score exists? " << std::boolalpha
              << scores.contains("Charlie") << "\n"; // false

    return 0;
}

Contributions

Contributions are welcome! Please read our contribution guidelines before submitting a pull request.

  1. Missing implementations: Check the list of pending structures
  2. Performance improvements: Optimizations without compromising clarity
  3. Documentation: Improvements to comments, examples, or guides
  4. Tests: Add more test cases or improve existing ones

When adding a new structure, please include:

  • Public header in include/ads/<area>/
  • .tpp implementation in src/ads/<area>/
  • A demo in src/main_<Structure>.cc and a unit test in tests/
  • An update to this README if it changes the public surface

Learning Resources

Essential References

Advanced Topics

Specialized Resources

Spatial and Nearest Neighbor Search

License

This project is licensed under the MIT License - see the LICENSE file for details.

Contact

For questions or suggestions, please open an issue in this repository.