🔗 Common Data Structures and Algorithms

Overview

🔗 Data Structures and Algorithms

Build Status Build status Coverage Status Codacy Badge

This library provides common data structures. It will also provide some data structures which needed in render or game engines. In the future I'll try to optimize memmory access.

There may multiple way to implement a data structure but I tried to implement best way to do that. For instance Red-Black Trees are only implemented as top down insertion/deletion to make it faster.

There are some convenient constructors for common use cases. For instance rb_newtree_str() creates new rb-tree that uses strings as key, rb_newtree_ptr() creates new rb-tree that uses pointers as key. When you use these functions to alloc a data structure then you don't need to provide compare or print functions.

This library prodives allocator api so you can override default allocator.

Usage

#include <ds/rb.h> // Red-Black Tree

int
main(int argc, const char * argv[]) {
  RBTree *tree;
  /* ... */

  /* use string keys */
  tree = rb_newtree_str();

  rb_insert(tree, "key", value);

  /* ... */
  value = rb_find(tree, "key");

  rb_destroy(tree);
}

Todo

  • rbtree
    • top-down insertion
    • top-down deletion
  • forward-list
    • forward-list-separate (reduces FList struct)
  • hash-table
    • builtin hash functions e.g. djb2
    • resizing hash table
  • quick sort implementation for float, double, i32, u32, i64, u64
  • queue (working on this)
  • stack
  • binary heap / priority queue
  • dynamic array
  • octree
  • quadtree
  • b-tree

Build

Unix (Autotools)

$ sh autogen.sh
$ ./configure
$ make
$ make check # [Optional]
$ [sudo] make install # [Optional]

Windows (MSBuild)

Windows related build, project files are located in win folder, make sure that you are inside in the libds/win folder. Code Analysis are enabled, it may take awhile to finish build

$ cd win
$ .\build.bat

if msbuild didn't work then you can try to build it with devenv:

$ devenv libds.sln /Build Release

License

MIT. check the LICENSE file

Issues
  • Red Black Tree: Provide extra function to override compare(cmp) function

    Red Black Tree: Provide extra function to override compare(cmp) function

    New functions:

    void*   rb_find_by(RBTree * __restrict tree, void * __restrict key, const DsCmpFn cmp);
    RBNode* rb_find_node_by(RBTree * __restrict tree, void * __restrict key, const DsCmpFn cmp);
    

    Custom compare can be used for getting items. For instance you can compare null terminated string with non-null terminated string by providing custom compare to rb_find_by().

    • previous rb_find() and rb_find_node() now uses rb_find_node_by() to reduce pointer dereferencing (hope there will no bugs here)
    opened by recp 0
  • quick sort implementation

    quick sort implementation

    Quick sort implementation for float, double, int32, uint32, int64 and uint64.

    The implementation is specific to primitive types so it must be faster than builtin qsort. Because

    • it eliminates compare function
    • it eliminates size parameter

    Some features:

    • clean interface
    • it allows both ASC and DESC ordering
    • it provides a swap item callback so if you have two or more arrays and you can swap elements in other arrays while the array is being sorted.
    • it uses Hoare partition scheme

    in the future sorting order data structures especially linked lists may be supported.

    opened by recp 0
Releases(v0.2.2)
Owner
Recep Aslantas
alone with numbers
Recep Aslantas
Repository of problems and solutions of labsheets used for Data Structures and Algorithms (CS F211) in Semester 2, 2020-21 at BITS Pilani - Hyderabad Campus.

CS F211 Data Structures and Algorithms (BITS Pilani - Hyderabad Campus) This repository contains the problems, solution approaches & explanations and

Rohit Dwivedula 27 Apr 13, 2022
Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design

Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. It contains solutions in various languages such as C++, Python and Java.

DSC-Banasthali 53 Jun 12, 2022
Templates, algorithms and data structures implemented and collected for programming contests.

Templates, algorithms and data structures implemented and collected for programming contests.

Shahjalal Shohag 1.8k Jun 27, 2022
An assortment of commonly used algorithms and data structures implemented with C++.

Algorithms-And-Data-Structures This repo contains C++ implementations of common algorithms and data structures, grouped by topics. The list will be sp

Tony Sheng 23 Nov 9, 2021
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

Lib9wada Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada Usage Compile the library with mak

Lprogrammers Lm9awdine 47 May 29, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

LibC+ Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -lC+ Better than C, not as much as c++ Usage

BnademOverflow 47 May 29, 2022
The aim of this repository is to make it a one final stop for revision for technical interviews involving data structures and algorithms .

Hey ??‍♂️ This repository is meant for data structures and algorithms . I will be updating this often and will include all the data structures importa

Prakhar Rai 48 Jun 7, 2022
This is a beginner-friendly project aiming to build a problem-set on different data structures and algorithms in different programming languages.

DSAready Overview This is a beginner-friendly project that aims to create a problem-set for various Data Structures and Algorithms. Being a programmer

Riddhi Jain 12 Jun 12, 2022
Implementation of various data structures and algorithms.

Data Structures and Algorithms A place where you can find and learn the copious number of algorithms in an efficient manner. This repository covers va

Google DSC, GVP Chapter 13 Apr 8, 2022
Data Structures and Algorithms implemented in C++

OpenOcto - Data Structures and Algorithms Data Structures and Algorithms implemented in C++ Code here directly using Gitpod! Everthing done in C++ All

null 3 Oct 19, 2021
Data structures and algorithms course, winter 2021/22

Data Structures and Algorithms 2021/22 Repository for the "Data structures and algorithms" course for the 2021/22 academic year. Structure lectures --

Atanas Semerdzhiev 20 May 13, 2022
A repository by [email protected] for data structures and algorithms

DSA Overview The main goal of this project is to promote open-source, allowing anyone who wants to contribute. This repository would be focused on var

null 18 Jun 7, 2022
Personal reference material for Data Structures and Algorithms

?? DSA ?? Sr Filename Title Notes 1 2-1_datatypes_and_modifiers.cpp Datatypes and Modifiers Type modifiers explained 2 2-2_input_output.cpp stdin and

Kapil Pramod Deshmukh 2 Oct 24, 2021
Redacted source code for exercises proposed in the Data Structures and Algorithms laboratory.

fsega_ie2_dsa Redacted source code for exercises proposed in the Data Structures and Algorithms laboratory. Usage The src/ directory contains a direct

Cezar Mathe 1 Dec 5, 2021
Data Structures and Algorithms course (IIC2133-PUC)

Data-Structures-And-Algorithms This are the homeworks of Jose Antonio Castro from Data Structures and Algorithms course (IIC2133) in Pontificia Univer

Jose Antonio Castro 3 Jun 22, 2022
100daysofDSA - Explore about arrays, linked lists, stacks & queues, graphs, and more to master the foundations of data structures & algorithms!

Explore about arrays, linked lists, stacks & queues, graphs, and more to master the foundations of data structures & algorithms!

null 25 Jun 6, 2022
Implementation of data structures and algorithms in C language

DataStructure_and_Algorithms_in_C Implementation of basic data structures and algorithms in C Data Structure LinkedList Singly Linked List Doubly Link

Boyoon Choi 2 Jan 5, 2022
A repository by [email protected] for data structures and algorithms

DSA Overview The main goal of this project is to promote open-source, allowing anyone who wants to contribute. This repository would be focused on var

null 18 Jun 7, 2022
Step is a C++17, header-only library of STL-like algorithms and data structures

Step is a C++17, header-only library of STL-like algorithms and data structures. Installation git clone --depth 1 https://github.com/storm-ptr/step.gi

storm-ptr 3 Dec 12, 2021