No description, website, or topics provided.
C++ Shell Other
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
build
data
scripts
src
test
CMakeLists.txt
COPYING
README.md

README.md

Data Structures and Algorithms

datas-and-algos is free Software under the terms of the GNU General Public License Version 2. See COPYING for full license text.

Some data structures and algorithms I have implemented for fun, including unit tests.

Algorithms:

Data structures:

  • ds/square-matrix.h
    A square matrix utilising strassen-matrix-multiply.h
  • ds/stack.h
    A stack
  • ds/binary-search-tree.h
    A binary search tree
  • ds/fixed-hashtable.h
    A hashtable with fixed size. al::murmur_32 is used as a hash function.
  • ds/priority-queue.h
    A priority queue based on std::make_heap, std::push_heap and std::pop_heap
  • ds/bloom-filter.h
    Bloom filter, al::murmur_128 is used as a hash function.

Project structure:

  • src/al/
    Algorithms
  • src/ds/
    Data structures
  • test/src/al/
    Unit tests for algorithms
  • test/src/ds/
    Unit tests for data structures
  • test/src/generic/
    Generic unit tests (rule-of-five.h, useful for default constructible objects that implement the rule of five)
  • test/smhasher/
    SMHasher build to verify my MurmurHash (32bit, 128bit) implementation. Will automatically download SMHasher from Google Code.
  • scripts/
    Helper scripts (build.sh, build-and-run-tests.sh, ...)
  • scripts/static-analysis/
    Convenience wrappers for cppcheck and cpplint (run_cppcheck.sh, run_cpplint.sh)

Build unit tests:

Either use the convenience script in scripts/build-and-run-tests.sh or use cmake directly:

    cd test/build
    cmake ..
    make
    ./datas-and-algos-test

The unit testing framework (googletest) will automatically be downloaded and built by cmake.

Dependencies:

cmake >= 2.8.7, boost (boost::optional for ds::fixed_hashtable)