An intrusive C++17 implementation of a Red-Black-Tree, a Weight Balanced Tree, a Dynamic Segment Tree and much more!

Overview

Build Status Coverage Status

This is Ygg (short for Yggdrasil), a C++17 implementation of several intrusive data structures:

  • several balanced binary search trees:
    • a red-black Tree
    • a Zip Tree
    • a weight balanced tree (aka BB[α]-tree)
  • an Interval Tree
  • a Doubly-Linked List
  • a Dynamic Segment Tree (which is something between a segment tree and an interval map)
    • ... based on a Red-Black Tree
    • ... based on a Zip Tree

If you need a Red-Black-Tree, a Zip Tree, a Segment Tree or an Interval Tree in your C++ application, and for some reason the existing implementations (like std::set or boost::instrusive::rbtree) are not suited for you, Ygg may be the answer. Also, I do not know of any other implementation of the "Dynamic Segment Tree" (if you know something similar, please let me know!)

See the list of features below for why Ygg is awesome!

If you're not sure whether one of these data structures is the right data structure for your application, check out the datastructure overview in the Documentation.

Warning: This is still in development. Therefore, things could break. Also, the API might change. If you found an example where one of the data structures does not behave as expected, please let me know.

Features

  • It's intrusive! Like the containers in boost::intrusive, Ygg follows a 'bring your own data structure' approach. Depending on your use case, this can save a lot of time by avoiding memory allocation and copying stuff around.
  • You can be notified when stuff happens. Want to do something to the tree nodes every time a tree rotation happens? Need to know whenever two nodes swap places in the tree? Look no further. Ygg will call methods specified by you on several occasions. In fact, that's how the Interval Tree (the augmented tree version from Cormen et al.) is implemented.
  • It's pretty fast. Doing benchmarks correctly is pretty difficult. However, performance should not be too far away from boost::intrusive::rbtree. Comparing against std::set is unfair - std::set loses because it needs to do memory allocation.

Installation

It's a header-only library. (Yes I know, there are .cpp files. I like to keep declaration and definition separated, even if everything's actually a header.) Just make sure everything in the src folder is in your include path, and you're set.

Note that Ygg relies heavily on C++17 features. Thus, your compiler must fully support C++17 and must be set to compile using the C++17 standard. I currently test compilation with GCC 7.0, Clang 7 and XCode 11, so those should be fine.

Documentation

There's a short usage example below which is probably enough if you just want to use the Red-Black-Tree.

The Documentation contains an overview over how the different datastructures behave as well as more in-depth examples as well as an API documentation.

Usage Example

This creates a Node class for you (which just holds an int-to-std::string mapping, pretty boring) and sets up an Red-Black-Tree on top of it:

#include "ygg.hpp"

using namespace ygg;

// The tree options
using MyTreeOptions = TreeOptions<TreeFlags::MULTIPLE>;

// The node class
class Node : public RBTreeNodeBase<Node, MyTreeOptions> {
public:
  int key;
  std::string value;

  // need to implement this s.t. we can use the default std::less as comparator
  bool operator<(const Node & other) const {
    return this->key < other.key;
  }
}

// Configure the RBTree based on Node and the default NodeTraits
using MyTree = RBTree<Node, RBDefaultNodeTraits, MyTreeOptions>;

Now, let's add some elements, iterate and query:

// We need this s.t. we can query by key value (i.e, an int) directly
bool operator<(const Node & lhs, int rhs) {
  return lhs.key < rhs;
}
bool operator<(int lhs, const Node & rhs) {
  return lhs < rhs.key;
}

int main(int argc, char **argv) {
  MyTree t;

  // Storage for the actual nodes.
  // WARNING: using STL containers here can backfire badly. See documentation for details.
  Node nodes[5];

  // Initialize the nodes with some values
  for (size_t i = 0 ; i < 5 ; ++i) {
    nodes[i].key = i;
    nodes[i].value = std::string("The key is ") + std::to_string(i);
  }

  // Insert them
  for (size_t i = 0 ; i < 5 ; ++i) {
    t.insert(nodes[i]);
  }

  // What was the string for i = 3 again?
  auto it = t.find(3); // Note we're using a int to query here, not a Node
  assert(it != t.end());
  std::string retrieved_value = it->value; // *it is the Node

  // Okay, we don't need that Node anymore.
  t.remove(*it);

  // Iterate all the nodes!
  for (const auto & n : t) {
    std::cout << "A node: " << n.value << "\n";
  }
}

License

This software is licensed under the MIT license. See LICENSE.txt for details.

You might also like...
This repository provides implementation of an incremental k-d tree for robotic applications.

ikd-Tree ikd-Tree is an incremental k-d tree designed for robotic applications. The ikd-Tree incrementally updates a k-d tree with new coming points o

Implementation of K-D tree in C++ programming language.
Implementation of K-D tree in C++ programming language.

KD_Trees Implementation of K-D tree in C++ programming language Demonstration Image What's in this repository anyway? This is a C++(PL) implementation

High performance build system for Windows, OSX and Linux. Supporting caching, network distribution and more.

FASTBuild FASTBuild is a build system for Windows, OSX and Linux, supporting distributed compilation and object caching. It is used by many game devel

Perception-Aware Trajectory Planner in Dynamic Environments
Perception-Aware Trajectory Planner in Dynamic Environments

PANTHER: Perception-Aware Trajectory Planner in Dynamic Environments Citation When using PANTHER, please cite PANTHER: Perception-Aware Trajectory Pla

Simple Useful Libraries: C++17/20 header-only dynamic bitset

dynamic_bitset Simple Useful Libraries: C++17/20 header-only dynamic bitset Requirements To use this dynamic bitset, you will need a C++17 (or later)

Implementing dynamic lists in C begginer level

Dynamic-Lists Implementing dynamic lists in C begginer level DESCRIPTION: This header file list.h implements python-like lists and it's functions.

C++ library to create dynamic structures in plain memory of shared-memory segments

Ищи описание на хабре @mrlolthe1st. #define _CRT_SECURE_NO_WARNINGS #include "shared_structures.h" #include iostream #include fstream #include ca

A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..
A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..

Access list is a collection of multiple types of lists used during pentesting, collected in one place, created by Undercode This list include a collec

A collection of libraries, data structures, and more that I have created to make coding in C less painful.

ctools A collection of libraries, data structures, and more that I have created to make coding in C less painful. Data structures There are many data

Comments
  • erase on iterators

    erase on iterators

    Trees should provide erase on iterators, returning the next iterator, for consistency with other containers.

    The alternative is to use remove, but that's not compatible with algorithms.

    opened by mgaunard 5
  • Update test CMakeLists.txt so you can build unittests on MacOS or directly

    Update test CMakeLists.txt so you can build unittests on MacOS or directly

    I found that I could not build the unittests directly using cmake on Sierra.

    Newer versions of cmake require cmake_minimum_required, which is a good thing. I put it at 3.8.0, and add set (CMAKE_CXX_STANDARD 11) in the file so it can compile the C++11 semantics.

    opened by robromano 5
  • Passing a {0, 0} in the intervaltree example

    Passing a {0, 0} in the intervaltree example

    Passing a {0, 0} in the intervaltree example crashes with a seg fault. I'm trying to ask the interval tree to return Nodes that contain the point 0.

    Here's the code I'm using. I hope I'm not doing anything stupid.

    // intv_test.mm
    
    #include <tuple>
    #include <string>
    #include <iostream>
    #include <ygg/intervaltree.hpp>
    
    using Interval = std::pair<int, int>;
    
    template<class Node>
    class NodeTraits : public ygg::ITreeNodeTraits<Node> {
    public:
      using key_type = int;
      static int get_lower(const Node& node) {
        return node.lower;
      }
      static int get_upper(const Node& node) {
        return node.upper;
      }
      static int get_lower(const Interval& i) {
        return std::get<0>(i);
      }
      static int get_upper(const Interval& i) {
        return std::get<1>(i);
      }
    };
    
    class Node : public ygg::ITreeNodeBase<Node, NodeTraits<Node>> {
    public:
      int upper;
      int lower;
      std::string value;
    };
    
    using Tree = ygg::IntervalTree<Node, NodeTraits<Node>>;
    
    int main(int argc, const char **argv) {
      Tree t;
      Node nodes[5];
      for (std::uint64_t i = 0; i < 5; i++) {
        nodes[i].lower = i;
        nodes[i].upper = i + 5;
        nodes[i].value = std::string("The interval is [") + std::to_string(i) + std::string(", ") + std::to_string((i+5)) + std::string("]");
        t.insert(nodes[i]);
      }
      Interval queryRange {0, 0};
      for (const auto& node : t.query(queryRange)) {
        std::cout << node.value << std::endl;
      }
      return 0;
    }
    

    And, for the sake of completeness, the output is:

    $ ./intv_test
    The interval is [0, 5]
    Segmentation fault: 11
    

    Also, passing {1, 1} gives the expected output:

    $ ./intv_test
    The interval is [0, 5]
    The interval is [1, 6]
    
    opened by bibhas 4
  • Is the method query() of intervalTree thread safe?

    Is the method query() of intervalTree thread safe?

    Thanks for developing this repo, and it helps me a lot! I'd like to create an intervalTree, and use query() method through multi-threading, can this be done?

    opened by tigeroses 2
Owner
Lukas Barth
Algorithm Engineer
Lukas Barth
Complete introduction to size balanced trees (O(1) amortized complexity)

Size Balanced Tree A size balanced tree (SBT) is a self-balancing binary search tree (SBBST) rebalanced by examining the sizes of each node's subtrees

Jishan Shaikh 18 Jun 2, 2022
Several translations of segment trees for CMU's 15-451 (Algorithms).

segtrees Several translations of segment trees for CMU's 15-451 (Algorithms). Feel free to contact me at [email protected] for questions/comment

Abigale Kim 20 Jun 17, 2022
📝 Performant plain text editor for iOS with syntax highlighting, line numbers, invisible characters and much more.

?? Welcome to Runestone - a performant plain text editor for iOS with code editing features Runestone uses GitHub's Tree-sitter to parse code to a syn

Simon Støvring 1.9k Sep 28, 2022
data structures which I've tried to implement in C++, much more incoming 👨‍💻

This repository contains some data structures which I've tried to implement, much more incoming ??‍?? I'm definitely not a C++ expert, so the code is

Wiktor Zając 2 Dec 21, 2021
FastDynamicCast - Fast dynamic cast in C++ for MSVC, outperforming the regular dynamic cast by up to 25 times

Fast dynamic cast This is a single header, dynamic cast implementation which outperforms the regular dynamic_cast by up to 25 times. Works on MSVC 201

tobspr 83 May 8, 2022
UnhookMe is an universal Windows API resolver & unhooker addressing problem of invoking unmonitored system calls from within of your Red Teams malware

UnhookMe - Dynamically unhooking imports resolver In the era of intrusive AVs and EDRs that introduce hot-patches to the running processes for their e

Mariusz B. 300 Sep 23, 2022
This is like Inverting Binary Tree, but instead of a Binary Tree it's a File Tree.

Invert File Tree in C++ This is like Inverting Binary Tree, but instead of the Binary Tree it's a File Tree. This is intended as a simple exercise to

Tsoding 11 Jun 18, 2021
Like neofetch, but much faster because written in c. Only Linux.

fastfetch fastfetch is a neofetch like tool for fetching system information and displaying them in a pretty way. It is written in c to achieve much be

Linus Dierheimer 346 Sep 28, 2022
This project Orchid-Fst implements a fast text string dictionary search data structure: Finite state transducer (short for FST) in c++ language.This FST C++ open source project has much significant advantages.

Orchid-Fst 1. Project Overview This project Orchid-Fst implements a fast text string dictionary search data structure: Finite state transducer , which

Bin Ding 9 Jul 25, 2022
Build a tree-sitter dynamic module

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I should clarify that this module is NOT a standalone tree-sitter module. It is supo

Yuan Fu 5 Sep 27, 2022