cppdsa-queue

A modern C++ (header-only) library that provides generic implementations of the Queue ADT and related algorithms.

Two implementations of the Queue ADT are included in the project off the shelf:

• dsa::CircArrayQueue : Circular array based implementation

• dsa::SLListQueue : Singly linked list based implementation

Different implementations of the Queue ADT are defined in separate header files.

...
#include "circ_array_queue.hpp"     // CircArrayQueue<Elem>

int main() {
    auto q = dsa::CircArrayQueue<int> {};
    q.enqueue(3);
    q.enqueue(1);
    ...
    while (!q.empty()) {
        std::cout << q.front() << ' ';
        q.dequeue();
    }
    std::cout << std::endl;
    ...
    return 0;
}

A collection of ADT-implementation-agnostic algorithms on the Queue ADT is included in a dedicated header file.

...
#include "algos.hpp"    // merge<...>()
...
using IntQueue = dsa::CircArrayQueue<int>;

dsa::IQueue<int, dsa::CircArrayQueue>* q1 { new IntQueue {} };
for (int nums[] { 4, 7, 2, 10 }; auto const num : nums) {       // num = priority
    q1->enqueue(num);
}

dsa::IQueue<int, dsa::CircArrayQueue>* q2 { new IntQueue {} };
for (int nums[] { 3, 6, 8, 9, 5, 1 }; auto const num : nums) {  // num = priority
    q2->enqueue(num);
}

// larger the element value, higher the priority given when 
// two queues are stable-merged
auto* q = dsa::merge<int, dsa::CircArrayQueue, std::greater<int>>(q1, q2);
std::cout << q->to_string("q", ",") << std::endl;
// prints "q[4,7,3,6,8,9,5,2,10,1]"
...
// manual memory deallocation requires to support 100% static polymorphism
destroy(q1);
destroy(q2);
destroy(q);

It is designed to support static (compile-time) polymorphism and is extensible by means of template programming.

For more details, visit the documentation site.

Here's what you need to get started.

• Dependencies
• Building & Testing the Project
• For Developers & Contributors
• License
• Also Want It In Another Language?

Dependencies

To build the project, you will need

• g++ (version 8+) or equivalent compiler that supports C++20 and above
• CMake (version 3.15+)
• Make (or equivalent build tool)
• GoogleTest (to be installed as submodule of the project using git)
• Git

Installing googletest

$ git submodule add --force https://github.com/google/googletest.git test/lib/googletest

Building & Testing the Project

Several bash scripts are included in the scripts/ subdirectory to simplify the build and test process, both debug and release, if you've CMake installed on the system. So you don't have to run neither ctest nor any executable test programs -- each successful build will have passed all the tests included.

For all of the following commands, it's assumed that you're in the scripts/ dir. If not, cd into it like

$ cd /path/to/project/root/scripts

or modify the commands with the right path accordingly.

Full build

To make the first build or a clean build, run either:

$ ./cmake-build-debug.sh        # debug build
$ ./cmake-build-release.sh      # release build

On success, you'll see the success message at the end of the build and test processes on the terminal like so:

...         # build/test info...
👍 Congrats! You are all set.
$

In that case, you'll find three newly created subdirectories under the project root.

1. build/[debug|release]/ --- contains all artifacts created during the build process
2. include/ --- contains the header files of the library.
3. bin/ --- contains the executable demo programs queue_demo and queue_merge_demo.

If any errors arise during the build process or the test process, otherwise, you'll get the error message at the end like so:

...         # build/test info...
👎 Oops! Something went wrong.
$

Rebuild

To build the whole project again after making changes to the source code, you may simply run either

$ ./cmake-rebuild-debug.sh      # debug
$ ./cmake-rebuild-release.sh    # release

Clean

Alternatively, if you'd like to have a clean build starting from scratch, you may do so by first running the following before either one of two *-build-*.sh scripts.

$ ./clean-build.sh

⚠️ WARNING : It permanently removes all three subdirectories created during a build process. So use it with caution if you choose to save any other files at those locations.

For Developers & Contributors

Project structure

.
├── src/
├── test/
├── scripts/
├── docs/                   
├── build/                  # to be created in the first build
├── bin/                    # to be created in the first build
├── include/                # to be created in the first build
├── ProjectConfig.h.in 
├── .clang-format
├── .gitignore
├── CMakeLists.txt
├── Doxyfile
├── LICENSE
└── README.md

Header and source files for the library and demo program are located in the src/ subdirectory, whereas those for unit tests are located in the test/ subdirectory.

Running tests

Although tests are automated via the bash scripts included, you may also run the included tests independently, which is typically useful for debugging after failing builds.

To do so, first cd into the build/[debug|release] subdirectory under the project root. Then run

$ ctest --verbose --output-on-failure

For debugging a failed build, you may want to add also the --rerun-failed flag to run only the tests that failed previously.

To find out all available options, run ctest -help.

Code formatting

Install clang-format and run it with the included .clang-format config file at the project root.

If you use an IDE, you're strongly revised to configure it to automatically run clang-format on each save.

Documentation

Style

All documentation text are written in the Javadoc style /** ... */ with @ as command marker. In multiline form (typically for classes and functions), include aligned leading asterisks * in each sandwiched lines. For text that can fit in a single line not exceeding 80 characters (including the comment delimiting characters), use the inline form, either succeeding a statement or on the line preceding the code block to document.

Site generation

To build the documentation site for the project, you will need

• Doxygen 1.9.2+
• Python 3.7+
• Sphinx
• Furo
• Breathe

License

The project is licensed under the BSD 3-Clause License.

Also Want It In Another Language?

• C : Repository | Documentation
• Go : Repository | Documentation [coming soon]
• Python : Repository | Documentation
• TypeScript : Repository | Documentation

The C language equivalent -- cdsa-queue -- is basically the procedural programming version of cppdsa-queue but without the compile-time polymorphism capabilities.

Acknowledgement

This project is bootstrapped using Cookiecutter with the cpp-lib-cookiecutter template (built by the same author of this project).

Copyright © 2022 - 2023 KriztoferY. All rights reserved.