DEV Community: Melanchall

Red-black tree: complete C# implementation

Melanchall — Sun, 06 Jul 2025 19:38:09 +0000

What can make you pay attention to red-black trees, and how to implement them? The article will answer both of these questions. As a bonus, it will show how to construct an interval tree based on a red-black one.

Important note: the article focuses on the code. Big O, binary trees, linked lists — all these concepts will remain behind the scenes. Articles are valuable for their unique content, but the listed things (including the mechanics of red-black trees) have been discussed many times.

If your thirst for ready-made solutions is as strong as mine was six months ago when I started to learn the subject, then you can immediately go to the Construction section. Or even to the end of the article to the links to the files.

Why?
Construction
Interval tree
Conclusion

Why?

Before diving into the information botany, I will answer the first question asked at the beginning of the article. What I needed is:

an ordered (sorted by some attribute) collection of objects;
the order should be preserved on insertion and removal;
these operations, as well as searching for an object, should be performed as quickly as possible.

Like my previous articles, this one is inspired by my work on DryWetMIDI library. The 8.0.0 version allowed change playback objects (MIDI events, notes, etc.) on the fly. In short, now you can remove, add and change data without having to create a new instance of Playback class again and again. So you can work with just a single instance. Since objects within playback must be ordered by the time, we come to the list of requirements shown above.

Invaluable experience of previous generations gives us the clue — we need a self-balancing binary search tree. Complexity of insertion, removal and search in such a data structure is O(log n), both on average and in the worst case. Unfortunately we cannot say the same about a simple BST (binary search tree), because after a series of modifications we easily can get, for example, such a chain:

Complexity of the operations will obviously be linear (i.e. O(n)). Maintaining the minimum height of the tree (which gives us the desired logarithm) is why we need the balancing procedure, the essence of which is to reorder nodes preserving the BST properties.

So, we have decided on data structure. But self-balancing binary search trees can be different. The most famous are AVL tree and the subject of the article — red-black tree (RBT). Here I should tell you about how I’ve researched the pros and cons of each option, but something went wrong. I already knew about red-black trees and their properties, and so I chose this data structure. Professionally, right?

But writing articles is not only about knowledge sharing. It’s also about learning the subject more deeply. It would be completely stupid not to try to figure out which data structure is better even now. Brief summary of various texts is: in general, they are the same. After all, the complexity of both is O(log n) for all operations. Of course, there are nuances:

search is slightly faster in AVL tree due to its lower height;
RBT wins in the speed of removal since lower number of rotations required to balance it (AVL tree requires O(log n) rotations in the worst case compared to O(1) for red-black one).

Insertion and removal are the most important operations for me. Search happens rarely: when jumping around the timeline of the data being played — in this case, of course, I need to find an event from which playback should start at a new position.

This article is intended to provide comprehensive code listings of red-black tree implementation, including basic operations and useful auxiliary ones. And very soon you will see those monospaced text fields.

You may ask: “Why not just take the code from the Internet?” Honestly, for me, as a typical programmer, this was the first thing that came to my head. But that is easier said than done. Search results for the phrase “red black tree c#”:

Red-Black Tree Implementation in C#. There is no method to remove data. Also, a bug was found in the code (see comments).
Working With Red-Black Trees In C#. There is no removal again.
Generic Red-Black Tree and its C# Implementation. An innovative method to show code was used: by images.
Red-Black Trees in C#. Key and value are the same object. This is incorrect, of course.
Red-Black Trees in C# (same name, but different article). Key is just IComparable, and value is object. That is, generics are not used.

“But surely there are libraries with ready-made classes!”

Maybe my search skills are bad, but I didn’t find a library on NuGet where the red-black tree meets my requirements (see the next section).
In my project I deliberately avoid third-party dependencies. Pulling an entire library for a single class or method is not always wise.
I needed to implement some additional methods that required access to the tree’s internals.

Construction

This is how a class representing a red-black tree should look like in my opinion:

Key and value are different entities. If a value is something more complex than int, then the value itself almost always will not be the key.
The class should be generic. We don’t need to guess on the type of key and value, or use object (you probably don’t want boxing).
Keys can be duplicated. Example: a group of notes in a MIDI file that make up a chord. So the start events (= values) of such notes have the same time (= key).

The last point is the most interesting, because it affects the final structure of the tree. Initially I decided to take the easy way: let nodes with the same keys always go to the right. Contradiction is the word that comes to my mind now. Because according to this logic a tree with identical objects only will contain only right nodes, which changes the complexity of operations to linear. But if we balance the tree, the rules of construction will be violated.

But to be fair, this approach is viable. Although some operations described below will be a bit more complicated. I decided that keys should be unique. However we need to be able to store data with duplicate identifiers. Solution is to store a collection of values inside a node instead of a single value. How exactly this will be implemented is up to you. I chose LinkedList<>.

In order to avoid mess and verbosity in the text below we will use the following terminology:

a tree consists of nodes, each node has the key;
a node contains a list of elements, in our case each element is LinkedListNode<>;
an element holds a value, i.e. a data object that we put into the tree.

Disclaimer: the code may be (and will be) imperfect in some places or not meeting your professional tastes. An example of an arguable solution is representation of a node color. Most of you probably say that we need to define some enum with two values (Red and Black) and use it for property Color in the node. That was my first intention too. But then I thought — color is nothing more than just a metaphor for an attribute needed by the tree balancing procedure. So I removed the enum and replaced Color with IsRed boolean property. Occam’s razor in action.

Well, let’s go! First, we will describe a node:

public sealed class RedBlackTreeNode<TKey, TValue>
    where TKey : IComparable<TKey>
{
    public static readonly RedBlackTreeNode<TKey, TValue> Void =
        new RedBlackTreeNode<TKey, TValue>(default(TKey), null);

    public RedBlackTreeNode(
        TKey key,
        RedBlackTreeNode<TKey, TValue> parent)
    {
        Key = key;
        Parent = parent;
    }

    public TKey Key { get; set; }

    public LinkedList<TValue> Values { get; } = new LinkedList<TValue>();

    public RedBlackTreeNode<TKey, TValue> Left { get; set; }

    public RedBlackTreeNode<TKey, TValue> Right { get; set; }

    public RedBlackTreeNode<TKey, TValue> Parent { get; set; }

    public bool IsRed { get; set; }
}

You may notice a strange constant (if you allow me to apply this word to a static readonly field) — Void. What is it? As a guide to red-black trees, I chose the book “Introduction to Algorithms”. For convenience of handling edge cases leaves are always the nil object there. I call it Void. There will be other mismatches with the book in my code. For example, I decided not to save such expressive variable names as w, x and y.

Regarding IComparable<TKey>: keys can’t be absolutely arbitrary. We obviously need to be able to compare them to locate elements in a tree. But that’s all, there won’t be and shouldn’t be any other requirements for either key or value.

Well, a tree consists of nodes, nodes contain elements, and each element holds a value. So we cannot point to a specific value with just a node. To solve this problem I’ve introduced coordinate:

public sealed class RedBlackTreeCoordinate<TKey, TValue>
    where TKey : IComparable<TKey>
{
    public RedBlackTreeCoordinate(
        RedBlackTreeNode<TKey, TValue> treeNode,
        LinkedListNode<TValue> nodeElement)
    {
        TreeNode = treeNode;
        NodeElement = nodeElement;
    }

    public RedBlackTreeNode<TKey, TValue> TreeNode { get; }

    public LinkedListNode<TValue> NodeElement { get; }

    public TKey Key => TreeNode.Key;

    public TValue Value => NodeElement.Value;
}

It’s time to define a tree. For now, let’s declare the root node, Count property and a couple of helper methods:

public class RedBlackTree<TKey, TValue>
    where TKey : IComparable<TKey>
{
    protected RedBlackTreeNode<TKey, TValue> _root = RedBlackTreeNode<TKey, TValue>.Void;

    public int Count { get; private set; }

    protected bool IsVoid(RedBlackTreeNode<TKey, TValue> node)
    {
        return node == null || node == RedBlackTreeNode<TKey, TValue>.Void;
    }

    private RedBlackTreeNode<TKey, TValue> NodeOrNull(RedBlackTreeNode<TKey, TValue> node)
    {
        return IsVoid(node) ? null : node;
    }
}

Now we can implement the method to add data:

public RedBlackTreeCoordinate<TKey, TValue> Add(TKey key, TValue value)
{
    var currentNode = _root;
    var lastNode = RedBlackTreeNode<TKey, TValue>.Void;

    while (!IsVoid(currentNode))
    {
        lastNode = currentNode;

        var compareResult = key.CompareTo(currentNode.Key);
        if (compareResult < 0)
            currentNode = currentNode.Left;
        else if (compareResult > 0)
            currentNode = currentNode.Right;
        else
        {
            Count++;
            var coordinateOnExistingNode = new RedBlackTreeCoordinate<TKey, TValue>(currentNode, currentNode.Values.AddLast(value));
            return coordinateOnExistingNode;
        }
    }

    var newNode = new RedBlackTreeNode<TKey, TValue>(key, lastNode);
    var result = new RedBlackTreeCoordinate<TKey, TValue>(newNode, newNode.Values.AddLast(value));

    if (IsVoid(lastNode))
        _root = newNode;
    else if (key.CompareTo(lastNode.Key) < 0)
        lastNode.Left = newNode;
    else
        lastNode.Right = newNode;

    newNode.Left = RedBlackTreeNode<TKey, TValue>.Void;
    newNode.Right = RedBlackTreeNode<TKey, TValue>.Void;
    newNode.IsRed = true;

    InsertFixup(newNode);

    Count++;
    return result;
}

Add method returns the coordinate which points to the added value. If there is a node with the passed key in the tree, we simply insert the value into the node's list of elements. If the key is not in the tree yet, we create a new node with the value and add this node to the tree.

But right now the code above is similar to that for a regular BST. More than that, a compiler won’t be happy, because InsertFixup is not implemented. This is the balancing:

private void InsertFixup(RedBlackTreeNode<TKey, TValue> node)
{
    RedBlackTreeNode<TKey, TValue> parent;

    while ((parent = node.Parent).IsRed)
    {
        var grandParent = parent.Parent;

        if (parent == grandParent.Left)
        {
            var uncle = grandParent.Right;
            if (uncle.IsRed)
            {
                parent.IsRed = false;
                uncle.IsRed = false;
                grandParent.IsRed = true;
                node = grandParent;
            }
            else
            {
                if (node == parent.Right)
                {
                    node = parent;
                    LeftRotate(node);
                    parent = node.Parent;
                    grandParent = parent.Parent;
                }

                parent.IsRed = false;
                grandParent.IsRed = true;
                RightRotate(grandParent);
            }
        }
        else
        {
            var uncle = grandParent.Left;
            if (uncle.IsRed)
            {
                parent.IsRed = false;
                uncle.IsRed = false;
                grandParent.IsRed = true;
                node = grandParent;
            }
            else
            {
                if (node == parent.Left)
                {
                    node = parent;
                    RightRotate(node);
                    parent = node.Parent;
                    grandParent = parent.Parent;
                }

                parent.IsRed = false;
                grandParent.IsRed = true;
                LeftRotate(grandParent);
            }
        }
    }

    _root.IsRed = false;
}

This is where rotations — the heart of balancing — come in. Left rotation:

private void LeftRotate(RedBlackTreeNode<TKey, TValue> node)
{
    var rightChild = node.Right;
    var leftGrandchild = rightChild.Left;

    node.Right = leftGrandchild;
    if (!IsVoid(leftGrandchild))
        leftGrandchild.Parent = node;

    var parent = node.Parent;
    rightChild.Parent = parent;

    if (IsVoid(parent))
        _root = rightChild;
    else if (node == parent.Left)
        parent.Left = rightChild;
    else
        parent.Right = rightChild;

    rightChild.Left = node;
    node.Parent = rightChild;
}

And right rotation (the code differs from the previous one by replacing Left with Right and vice versa):

private void RightRotate(RedBlackTreeNode<TKey, TValue> node)
{
    var leftChild = node.Left;
    var rightGrandChild = leftChild.Right;

    node.Left = rightGrandChild;
    if (!IsVoid(rightGrandChild))
        rightGrandChild.Parent = node;

    var parent = node.Parent;
    leftChild.Parent = parent;

    if (IsVoid(parent))
        _root = leftChild;
    else if (node == parent.Right)
        parent.Right = leftChild;
    else
        parent.Left = leftChild;

    leftChild.Right = node;
    node.Parent = leftChild;
}

Data has been added, now it’s time to learn how to remove it. By the way, have you noticed that LinkedListNode<> has List property? Each node contains a reference to the linked list it belongs to. Quite useful if you don’t want to accidentally remove an object from a wrong collection. We’ll follow the same path. Let’s add the property to RedBlackTreeNode<>:

public RedBlackTree<TKey, TValue> Tree { get; set; }

We also need several auxiliary methods:

public RedBlackTreeCoordinate<TKey, TValue> GetMinimumCoordinate()
{
    return GetMinimumCoordinate(_root);
}

public RedBlackTreeCoordinate<TKey, TValue> GetMinimumCoordinate(RedBlackTreeNode<TKey, TValue> node)
{
    while (!IsVoid(node?.Left))
        node = node.Left;

    return !IsVoid(node)
        ? new RedBlackTreeCoordinate<TKey, TValue>(node, node.Values.First)
        : null;
}

public RedBlackTreeCoordinate<TKey, TValue> GetMaximumCoordinate()
{
    return GetMaximumCoordinate(_root);
}

public RedBlackTreeCoordinate<TKey, TValue> GetMaximumCoordinate(RedBlackTreeNode<TKey, TValue> node)
{
    while (!IsVoid(node?.Right))
        node = node.Right;

    return !IsVoid(node)
        ? new RedBlackTreeCoordinate<TKey, TValue>(node, node.Values.Last)
        : null;
}

And now we are ready to remove an object by the specified coordinate. The code will return true if the object successfully removed, and false otherwise:

public bool Remove(RedBlackTreeCoordinate<TKey, TValue> coordinate)
{
    if (coordinate == null || coordinate.NodeElement.List == null)
        return false;

    var node = coordinate.TreeNode;
    if (IsVoid(node) || node.Tree != this)
        return false;

    node.Values.Remove(coordinate.NodeElement);
    if (node.Values.Count > 0)
        return true;

    return Remove(node);
}

As you can see we remove the value from the node’s element list at first. If there is data left in the list after that, we exit the method. But an empty node should be removed from the tree:

public bool Remove(RedBlackTreeNode<TKey, TValue> node)
{
    if (IsVoid(node) || node.Tree != this)
        return false;

    RedBlackTreeNode<TKey, TValue> child = null;
    var nextNode = node;
    var isNextNodeRed = nextNode.IsRed;

    if (IsVoid(node.Left))
    {
        child = node.Right;
        Transplant(node, node.Right);
    }
    else if (IsVoid(node.Right))
    {
        child = node.Left;
        Transplant(node, node.Left);
    }
    else
    {
        nextNode = GetMinimumCoordinate(node.Right).TreeNode;
        isNextNodeRed = nextNode.IsRed;
        child = nextNode.Right;

        if (nextNode != node.Right)
        {
            Transplant(nextNode, nextNode.Right);
            nextNode.Right = node.Right;
            nextNode.Right.Parent = nextNode;
        }
        else
            child.Parent = nextNode;

        Transplant(node, nextNode);
        nextNode.Left = node.Left;
        nextNode.Left.Parent = nextNode;
        nextNode.IsRed = node.IsRed;
    }

    if (!isNextNodeRed)
        RemoveFixup(child);

    node.Tree = null;
    Count--;

    return true;
}

In order to get rid of errors in a compilation log, we need to implement two methods: Transplant and RemoveFixup. The first one replaces one subtree with another:

private void Transplant(
    RedBlackTreeNode<TKey, TValue> oldRoot,
    RedBlackTreeNode<TKey, TValue> newRoot)
{
    var parent = oldRoot.Parent;

    if (IsVoid(parent))
        _root = newRoot;
    else if (oldRoot == parent.Left)
        parent.Left = newRoot;
    else
        parent.Right = newRoot;

    newRoot.Parent = parent;
}

The second method performs the balancing:

private void RemoveFixup(RedBlackTreeNode<TKey, TValue> node)
{
    while (node != _root && !node.IsRed)
    {
        var parent = node.Parent;

        if (node == parent.Left)
        {
            var sibling = parent.Right;
            if (IsVoid(sibling))
                break;

            if (sibling.IsRed)
            {
                sibling.IsRed = false;
                parent.IsRed = true;
                LeftRotate(parent);
                sibling = parent.Right;
            }

            if (!sibling.Left.IsRed && !sibling.Right.IsRed)
            {
                sibling.IsRed = true;
                node = parent;
            }
            else
            {
                if (!sibling.Right.IsRed)
                {
                    sibling.Left.IsRed = false;
                    sibling.IsRed = true;
                    RightRotate(sibling);
                    sibling = parent.Right;
                }

                sibling.IsRed = parent.IsRed;
                parent.IsRed = false;
                sibling.Right.IsRed = false;
                LeftRotate(parent);
                node = _root;
            }
        }
        else
        {
            var sibling = parent.Left;
            if (IsVoid(sibling))
                break;

            if (sibling.IsRed)
            {
                sibling.IsRed = false;
                parent.IsRed = true;
                RightRotate(parent);
                sibling = parent.Left;
            }

            if (!sibling.Right.IsRed && !sibling.Left.IsRed)
            {
                sibling.IsRed = true;
                node = parent;
            }
            else
            {
                if (!sibling.Left.IsRed)
                {
                    sibling.Right.IsRed = false;
                    sibling.IsRed = true;
                    LeftRotate(sibling);
                    sibling = parent.Left;
                }

                sibling.IsRed = parent.IsRed;
                parent.IsRed = false;
                sibling.Left.IsRed = false;
                RightRotate(parent);
                node = _root;
            }
        }
    }

    node.IsRed = false;
}

We have learned how to add and remove data. There is one fundamental operation left: search. To get a coordinate for the specified key and value, we need to implement several small methods:

public RedBlackTreeCoordinate<TKey, TValue> GetCoordinate(TKey key, TValue value)
{
    return GetCoordinatesByKey(key).FirstOrDefault(c => c.Value.Equals(value));
}

public IEnumerable<RedBlackTreeCoordinate<TKey, TValue>> GetCoordinatesByKey(TKey key)
{
    var node = GetNodeByKey(key);
    if (IsVoid(node))
        yield break;

    for (var element = node.Values.First; element != null; element = element.Next)
    {
        yield return new RedBlackTreeCoordinate<TKey, TValue>(node, element);
    }
}

public RedBlackTreeNode<TKey, TValue> GetNodeByKey(TKey key)
{
    var node = _root;

    while (!IsVoid(node) && key.CompareTo(node.Key) != 0)
    {
        if (key.CompareTo(node.Key) < 0)
            node = node.Left;
        else
            node = node.Right;
    }

    return NodeOrNull(node);
}

Here I need to make an unpleasant remark. Average-case complexity of the search is logarithmic, but what happens if there are a large number of values with the same key? If we search for an object in a node sequentially, then complexity will be linear. This is the worst case.

It is probably possible to somehow come to a logarithm, but I couldn’t come up with a solution quickly. Storing values in a mini-tree with a hash code as a key is also not an option: objects can be mutable. And the structure of a node will become much more complicated. I think it was not worth the trouble. Perhaps you can suggest an algorithm.

Well, the basic operations are implemented. But this is not enough. What is a collection without a constructor that accepts a list of elements? Let’s add it:

public RedBlackTree()
{
}

public RedBlackTree(IEnumerable<TValue> values, Func<TValue, TKey> keySelector)
{
    foreach (var v in values)
    {
        Add(keySelector(v), v);
    }
}

A couple of notes:

If you know in advance that the list being passed is sorted, you can optimize the process of building the tree: the first half of the list will be left subtree, the second half will be right one, then repeat the procedure for the subtrees. All that remains is to correctly “color” nodes and not forget about grouping objects with the same keys.
I do not pass keys, but a selector function that returns the key of a value.

Let’s return to the playback API in DryWetMIDI: how to move to the next event if it is time to play it? The “pointer” to the current event is a coordinate in a tree. GetNextCoordinate method helps to get the next one in chronological order:

public RedBlackTreeCoordinate<TKey, TValue> GetNextCoordinate(RedBlackTreeCoordinate<TKey, TValue> coordinate)
{
    if (coordinate == null || IsVoid(coordinate.TreeNode))
        return null;

    var nextElement = coordinate.NodeElement.Next;
    if (nextElement != null)
        return new RedBlackTreeCoordinate<TKey, TValue>(coordinate.TreeNode, nextElement);

    var node = coordinate.TreeNode;

    var right = node.Right;
    if (!IsVoid(right))
        return GetMinimumCoordinate(right);

    var nextNode = node.Parent;

    while (!IsVoid(nextNode))
    {
        if (node == nextNode.Left)
            return new RedBlackTreeCoordinate<TKey, TValue>(nextNode, nextNode.Values.First);

        node = nextNode;
        nextNode = node.Parent;
    }

    return IsVoid(nextNode)
        ? null
        : new RedBlackTreeCoordinate<TKey, TValue>(nextNode, nextNode.Values.First);
}

And the opposite method:

public RedBlackTreeCoordinate<TKey, TValue> GetPreviousCoordinate(RedBlackTreeCoordinate<TKey, TValue> coordinate)
{
    if (coordinate == null || IsVoid(coordinate.TreeNode))
        return null;

    var previousElement = coordinate.NodeElement.Previous;
    if (previousElement != null)
        return new RedBlackTreeCoordinate<TKey, TValue>(coordinate.TreeNode, previousElement);

    var node = coordinate.TreeNode;

    var left = node.Left;
    if (!IsVoid(left))
        return GetMaximumCoordinate(left);

    var previousNode = node.Parent;

    while (!IsVoid(previousNode))
    {
        if (node == previousNode.Right)
            return new RedBlackTreeCoordinate<TKey, TValue>(previousNode, previousNode.Values.Last);

        node = previousNode;
        previousNode = node.Parent;
    }

    return IsVoid(previousNode)
        ? null
        : new RedBlackTreeCoordinate<TKey, TValue>(previousNode, previousNode.Values.Last);
}

We can even get all the coordinates (of course, via IEnumerable<> to save memory):

public IEnumerable<RedBlackTreeCoordinate<TKey, TValue>> GetAllCoordinates()
{
    var coordinate = GetMinimumCoordinate();
    if (coordinate == null || IsVoid(coordinate.TreeNode))
        yield break;

    do
    {
        yield return coordinate;
    }
    while ((coordinate = GetNextCoordinate(coordinate)) != null);
}

This method opens the door to the society of full-fledged collections — all we need is to implement IEnumerable<>:

public class RedBlackTree<TKey, TValue> : IEnumerable<TValue>

...

public IEnumerator<TValue> GetEnumerator()
{
    foreach (var coordinate in GetAllCoordinates())
    {
        yield return coordinate.Value;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

The red-black tree is ready for use.

Interval tree

But my exploration of the algorithmic world’s flora did not end there. In DryWetMIDI there are methods like MoveToTime or MoveToNextSnapPoint which allow you to move to a position within a playback object. By default, the library calculates which notes are in the new time. Since a note has the start and the end, the task actually is to find all intervals containing a given point.

Unfortunately I did not know how to effectively (not by iterating all objects) search for intervals. But great minds invented the interval tree which is exactly what we need here. Wonderful thing is that it can be built by extending a red-black one.

The idea of the tree is:

values are intervals;
each node, in addition to values, holds the maximum upper value among all the intervals from this node down; let’s call this attribute the boundary;
key is the start endpoint of an interval.

From words to deeds. Let’s declare the tree:

public sealed class IntervalTree<TKey, TValue> : RedBlackTree<TKey, TValue>
    where TKey : IComparable<TKey>
    where TValue : IInterval<TKey>
{
}

Values must be intervals:

public interface IInterval<TEndpoint>
{
    TEndpoint Start { get; }

    TEndpoint End { get; }
}

According to the rules above, we need to attach boundaries to nodes. I didn’t build complex inheritance hierarchies (by defining a separate class for an interval tree node), and simply added Data property to RedBlackTreeNode<>:

public TKey Data { get; set; }

Not brilliant: the name implies anything, but we limit allowed values to the TKey type. But for my needs this was not a problem.

It is worth noting that the methods for adding and removing data are inherited from RedBlackTree<> without changes. Therefore, we just need to implement the search. Knowing the boundaries of nodes (or, in other words, subtrees), the code is pretty simple:

public IEnumerable<RedBlackTreeCoordinate<TKey, TValue>> Search(TKey point)
{
    var queue = new Queue<RedBlackTreeNode<TKey, TValue>>();
    queue.Enqueue(_root);

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();

        if (IsVoid(node) || node.Tree != this)
            continue;

        if (point.CompareTo(node.Data) >= 0)
            continue;

        queue.Enqueue(node.Left);

        for (var element = node.Values.First; element != null; element = element.Next)
        {
            var interval = element.Value;
            if (interval.Start.CompareTo(point) < 0 && interval.End.CompareTo(point) > 0)
                yield return new RedBlackTreeCoordinate<TKey, TValue>(node, element);
        }

        if (point.CompareTo(node.Key) <= 0)
            continue;

        queue.Enqueue(node.Right);
    }
}

But how and where does Data get updated? Let’s start with something simple. Here the method that updates the boundary of a node:

public bool UpdateMax(RedBlackTreeNode<TKey, TValue> node)
{
    if (node.Values.Count == 0)
        return false;

    var result = node.Values.First.Value.End;

    foreach (var value in node.Values)
    {
        if (value.End.CompareTo(result) > 0)
            result = value.End;
    }

    var left = node.Left;
    if (!IsVoid(left))
    {
        var leftMax = left.Data;
        if (leftMax.CompareTo(result) > 0)
            result = leftMax;
    }

    var right = node.Right;
    if (!IsVoid(right))
    {
        var rightMax = right.Data;
        if (rightMax.CompareTo(result) > 0)
            result = rightMax;
    }

    if (node.Data.Equals(result))
        return false;

    node.Data = result;
    return true;
}

We’ll also need a method that triggers an update of Data up the tree. Indeed, if the values of a node have changed, we’ll probably need to update the boundary in its parent, and in the parent’s parent, and so on:

public void UpdateMaxUp(RedBlackTreeNode<TKey, TValue> node)
{
    while (true)
    {
        var parent = node.Parent;
        if (IsVoid(parent) || !UpdateMax(parent))
            break;

        node = parent;
    }
}

But where do UpdateMax and UpdateMaxUp methods get called? What could cause recalculation of a boundary?

There are only two operations that modify a tree: insertion and removal. Let’s start with the first one. What actions during the procedure can change the boundary of a node? First of all, adding a new value. Let’s add empty virtual method OnValueAdded to RedBlackTree<>:

protected virtual void OnValueAdded(
    RedBlackTreeCoordinate<TKey, TValue> coordinate,
    TValue value)
{
}

And we’ll call it inside Add. First, here:

OnValueAdded(coordinateOnExistingNode, value);
return coordinateOnExistingNode;

Secondly, here:

OnValueAdded(result, value);
InsertFixup(newNode);

Implementation inside IntervalTree<>:

protected override void OnValueAdded(RedBlackTreeCoordinate<TKey, TValue> coordinate, TValue value)
{
    base.OnValueAdded(coordinate, value);

    var end = value.End;
    if (!UpdateMaxByNewValue(coordinate.TreeNode, end))
        return;

    UpdateMaxUp(coordinate.TreeNode);
}

When adding, it is easy to determine whether a cascade of boundary updates should be performed or not. UpdateMaxByNewValue method performs this check (and updates the boundary of a node):

private bool UpdateMaxByNewValue(RedBlackTreeNode<TKey, TValue> node, TKey end)
{
    var data = node.Data;
    if (data == null)
        node.Data = end;
    else if (data.CompareTo(end) < 0)
        node.Data = end;
    else
        return false;

    return true;
}

But there is a much more interesting place where node changes occur: balancing. I haven’t thought out algorithms on paper for a long time, but rotations in red-black tree forced me to do so.

After spending some time drawing lines and circles, I came up with this method inside RedBlackTree<>:

protected virtual void OnRotated(
    RedBlackTreeNode<TKey, TValue> bottomNode,
    RedBlackTreeNode<TKey, TValue> topNode)
{
}

I call it at the end of LeftRotate and RightRotate methods:

OnRotated(node, rightChild);

and

OnRotated(node, leftChild);

correspondingly.

Implementation of OnRotated in the interval tree:

protected override void OnRotated(
    RedBlackTreeNode<TKey, TValue> bottomNode,
    RedBlackTreeNode<TKey, TValue> topNode)
{
    base.OnRotated(bottomNode, topNode);

    UpdateMax(bottomNode);

    if (bottomNode.Data.CompareTo(topNode.Data) > 0)
        topNode.Data = bottomNode.Data;
}

We’ve handled insertion, now we have to think about removal. By analogy with OnValueAdded, we’ll declare OnValueRemoved method in the red-black tree class:

protected virtual void OnValueRemoved(
    RedBlackTreeNode<TKey, TValue> node)
{
}

We call it here:

node.Values.Remove(coordinate.NodeElement);
if (node.Values.Count > 0)
{
    OnValueRemoved(node);
    return true;
}

Implementation in IntervalTree<>:

protected override void OnValueRemoved(RedBlackTreeNode<TKey, TValue> node)
{
    base.OnValueRemoved(node);

    if (UpdateMax(node))
        UpdateMaxUp(node);
}

As you may recall, removal replaces one subtree with another. After spending some time with notebook trying to figure out what happens to a tree, RedBlackTree<> now has the method called OnTransplanted:

protected virtual void OnTransplanted(RedBlackTreeNode<TKey, TValue> node)
{
}

You need to call it only once, here:

OnTransplanted(nextNode);

if (!isNextNodeRed)
    RemoveFixup(child);

The interval tree just triggers cascade of boundaries updates:

protected override void OnTransplanted(RedBlackTreeNode<TKey, TValue> node)
{
    base.OnTransplanted(node);

    UpdateMax(node);
    UpdateMaxUp(node);
}

We don’t have to worry about balancing after removal: like addition, it is based on rotations, and we have already taken care of them.

The interval tree is ready. In fact, it can be built in different ways. But a red-black tree augmentation seems to be the simplest way because the tree has already been implemented.

Conclusion

You may have noticed that many methods inside RedBlackTree<> are not specific to a red-black tree. They are applicable to any binary search tree. Adherents of beautiful architecture will create BinaryTree<> class, from which RedBlackTree<> will inherit. I believe that if such a need arises, it will not be difficult to do this. But right now there is no point in introducing unnecessary classes.

As I said before, I couldn’t find a decent library with a red-black tree implementation. Maybe the code in this article will light a spark in you to create one. But if such a library does exist, I’d be glad to know.

As promised, I’m finishing the article with links to files with ready-made code:

Dropbox: How to Ignore Users for 10 Years

Melanchall — Tue, 17 Dec 2024 18:42:49 +0000

Millions of people use the Dropbox cloud. Many of them know about the opportunity to suggest an idea for new functionality. But only a select few have been waiting for the implementation of the most desired feature for ten years. In this article we will look at how Dropbox has managed to ignore the needs of its users for such a long time.

Like any concept, utilitarianism is not without criticism. However, from the point of view of a software developer, it seems quite reasonable to first make changes to the product that are desired by the majority of users. And when companies create specialized portals and feedback forms in order to make the voice of the people heard, this cannot but please.

But not every fairy tale is destined to come true. Today we “celebrate” the 10th anniversary of the original post asking for what has since become the most requested feature, but which is still not implemented.

How this all began
An idea!
Vox populi
Timeline
Suggested options
- Storing data outside the Dropbox folder
- Selective Sync
- Official solution
Why does Dropbox act like this?
Conclusion

How this all began

2008 was a year marked by the Olympic Games in Beijing, the global financial crisis, and the terrorist attacks in Mumbai. It’s no surprise, then, that the birth of a little-known cloud storage company was lost in the presence of those events. And yet Dropbox emerged from the backwater of the Y Combinator business incubator into the open ocean of the real market.

I first encountered the brainchild of Drew Houston and Arash Ferdowsi in January 2011 as a student. Someone from our stream thought it would be a good idea to share educational materials via Dropbox. I got an invite to the group's shared folder, and the guys with the superpower to actually remain awake during lectures started posting photos of their lecture notes there.

In July 2012 I bought a Dropbox account, and for good reason: I lost files containing music of my own production. More precisely, I deleted them with my own hands. Now I can’t even remember how it happened, but storing all important data in the cloud has become an immutable rule after that. Troubles with a hard drive and unruly hands are no longer scary.

Many things have happened since Dropbox was founded in 2008. It moved 500 petabytes of user data from Amazon to its own servers, launched a line of products for businesses, acquired several companies, and grew its revenue to over $2.5 billion a year.

In an effort to keep moving forward, Dropbox launched the Ideas portal to learn about user desires and provide them with the most requested features.

An idea!

I occasionally create small programs and utilities for my own needs, and I also develop the DryWetMIDI library. The files associated with these activities are certainly dear to me, and therefore live in a folder synchronized with the cloud.

But no matter what programming language you write code in and what platform you use, during the development process, temporary files and directories will be automatically created. I develop in C#, and building projects in Visual Studio results in the appearance of bin and obj folders. There's no benefit in synchronizing these up to the cloud.

Someone might say: “Well, let them synchronize, the Internet is fast these days.” Reasonable. But when there are many files, the process can take quite a noticeable amount of time even with a good network speed. After all, downloading one file of size N is not the same as M files of a total size N. The latter will take longer for obvious reasons: you need to send separate requests for each file, probably open connections, receive responses from the server, etc.

Another example is the obj folder generated by the docfx utility I use to build a reference site for my library. At times, there were thousands of small files in there that took an hour to sync with the cloud. In addition to being a waste of time and bandwidth, I had to keep my computer on until Dropbox finished its job.

At some point I got tired of it. A natural need for the following functionality arose:

Specify name patterns for files and folders that should not be sent to the cloud, while remaining locally on the computer. In essence, we’re talking about a file similar to the .gitignore one in the Git version control system.

It turned out that Dropbox couldn't help with this, and there were a lot of people who posted about the same problem. That's when I learned of the idea Add .dropboxignore directory to exclude folders without using selective sync.

Vox populi

In the article How ideas shared on the Dropbox Community are inspiring new features, community manager Emma Fay acknowledges that it is important for the company to hear what features and changes the audience needs and to deliver them. It is emphasized that Dropbox takes this very seriously.

The process is simple: a user creates an idea on the Ideas portal, after which others vote on it. Then Dropbox employees decide what to do with the initiative, and assign it a status. In the end, if the company agrees that the change will be useful for the product and its users, then upon completion of implementation the status will be set to Delivered.

The All Ideas section shows the total number of ideas at the moment — 889. However, only 27 (about 3%!) have the Delivered status. Perhaps these are the most desired proposals, with the largest number of votes? No. Moreover, the absolute leader of the list — the idea discussed in this article — has been consistently ignored by the company for 10 years.

As of today, the hero of the occasion has 1,300+ votes, 600,000+ views and over 1,000 comments. The closest competitor — the rejected idea Offline mode for Dropbox Paper web? — has less than 500 votes, and many fewer views and comments. As for the closest implemented one, the statistics are as follows: 200+ votes, 70,000+ views and 150+ comments.

Before we speculate on how this happened, let's look a little into history.

Timeline

I'm not sure about the date of creation of the idea, but right now the site says December 18, 2014. However, the first comment is dated December 16, 2014. It is unlikely that a person had a time machine, so most likely the correct birthday is a little earlier. But I have no proof, so we will rely on official data.

As one of the users noticed, the problem had already occurred to other people before. For example, in March of the same year and even in January 2012, and then in November. Someone even implemented this functionality by themself (although the project has long been abandoned and was only under macOS). In other words, it immediately became clear that the feature was extremely in demand. Everyone was waiting for the Dropbox representatives to respond.

And on December 18, 2014, they replied, advising users not to store in the Dropbox folder what does not need to be synchronized with the cloud. The same recommendation was repeated in March of the following year.

Some people began to lose hope and resent it. Increasingly, messages began to appear about abandoning Dropbox and switching to other cloud storage providers who offer this functionality. Over the years, the names of products such as MEGA, BitTorrent Sync (now Resilio Sync), pCloud, Sync and others have been mentioned.

But many still believed that users' opinions were important to Dropbox. Therefore, messages continued to appear with a detailed description of the necessary functionality and examples of use cases. People were even agreeable to the feature being implemented but left undocumented.

In July 2015, the author of the idea contacted Dropbox support, receiving a response that comments would be sent to the development team. I also had contact with support (already in 2022, in the eighth year of discussions) and received exactly the same response. Dropbox then remained silent publicly until September 2015, when they stated that the pain of users was understandable, and the feature was being discussed internally.

And examples of this pain continued to appear. The most frequent issue was the synchronization of node_modules folders: thousands of small files are sent to the server for hours. There have been other stories in which gigabytes of temporary data are uselessly transferred to Dropbox. There were also game developers on Unity, whose synchronization of meta files similarly highlights the importance of the proposed function. Problems have also arisen in LaTeX projects.

In January 2016, the number of votes for the idea exceeded 200. And what about Dropbox? Dropbox reads the discussion and understands the problem. The company has no other answer. However, in 2018, the company's employees decided to honestly declare that the implementation of the feature is not planned.

Of course, there was a wave of disappointment, canceling of paid accounts and product recommendations from competing companies. But not everyone lost hope, and once again an extremely detailed description of the problem appeared. After that, several messages were received from Dropbox representatives that the comments were passed on to the development team (for the umpteenth time).

In June 2019, a user shared an ironically worded announcement of the new version of the Dropbox Plus, sent to his email:

The all-new Plus plan is packed with top-requested features.

At the same time, the most requested feature, as you may have guessed, was missing from the release.

But, at the end of that year hope appeared! Dropbox has announced that it is working on a feature that will allow you to exclude files from syncing with your account. And after another 3 (!) years, the status of the idea was changed to Delivered.

Has it happened? Of course not. The provided “solution" has a number of problems, and we will analyze them in detail further.

A week later, under the onslaught of loud perplexity from users, the status was changed to Investigating. On the eighth birthday of the idea, a weary user prophesied that we would make it to 10 years as well, still without resolution. And now this day has come.

Let's remember what we were offered over this long period.

Suggested options

To simplify the presentation of the disadvantages of various approaches, we will use the previously shown example with the bin and obj directories that are created when building .NET code. But the essence will not change if we talk, for example, about the node_modules folder and the Node.js environment.

Storing data outside the Dropbox folder

Storing information outside of a synced folder was the very first solution suggested by Dropbox. And although the absurdity of this advice is obvious, let's describe the disadvantages of the approach. Actually, there is only one, but it's huge.

When building the project, the folders described above will appear. Moreover, they are created automatically inside the project directory. There is probably a way to move them somewhere so that they end up outside of a Dropbox folder, but no one does that and there is no point in forcing users to complicate their processes.

You can suggest that programmers use, for example, GitHub instead of Dropbox. But what if you create a small utility for your own needs that you don't want to send to GitHub, and versioning is not important? Git will also require execution of some commands to send data to a remote server, negating the transparency of synchronization with the cloud. And why forbid combining one with the other — to store a Git repository inside a Dropbox folder? Moreover, it was shown above that this functionality is needed not only by software developers.

At the same time, there are also defenders of the suggestion. But I hope a successful tech company like Dropbox, doesn't take seriously suggestions which essentially say "I don't know why this feature is needed, so no one needs it."

Selective Sync

Dropbox has been providing a feature called Selective Sync for a long time. You need to go to the settings of the client application, and in the huge folder tree uncheck those that do not need to be synced. But:

With the check box unchecked, the folders will be deleted from the computer, but they will remain in the cloud. But bin and obj are needed locally to run programs. Actually, they are executed from the bin folder by default.
To use the Selective Sync function, the data must first be sent to the server. But the files in question are temporary, they should never get into the cloud.
When creating a new project and getting new bin and obj folders, you need to manually repeat the whole procedure.
Of course, you will have to perform the same actions on another computer.

These are not even disadvantages, but the solution to a completely different task. Although, some people use Selective Sync to address this issue.

Official solution

In the end, Dropbox made it possible to ignore files and folders. Of course, they did it in a way that seemed like they had missed the whole long-term discussion.

According to Dropbox, users should run a command every time in the context menu or set a special flag through PowerShell that signals the client application to skip a file or folder. Problems:

Non-obvious folder transformations when performing the procedure on different computers synchronized with the same Dropbox folder.
These steps must be performed on each computer.
Information that a file or folder does not need to be synchronized with the server disappears when they are deleted. If you delete bin/obj folders, they will be automatically recreated on the next build. Of course, without the flag.
Users note that files are still “touched” by the Dropbox client, even though they are marked with the flag. This sometimes leads to compilation errors due to locked files.
The file or folder must exist for the procedure to be possible at all. This restriction makes it impossible to say “Don't sync any folder named X” before creating X.

Why does Dropbox act like this?

So, Dropbox is well aware of an idea with a huge number of votes and comments, many examples and detailed explanations of the problem, but the company has been ignoring its users for 10 years. How can this be?

It is probably related to an unwillingness to reduce the amount of data stored by users. Right now, when purchasing a minimum plan, a user gets 2 TB of storage. Two points:

most people don't need that much;
usually, when renting server capacity, a company pays only for the volume actually used.

Summing the first with the second, it turns out that in the case of an average user, Dropbox only incurs the cost of storing far less data than 2 TB, but the user nevertheless pays for the full 2 TB.

What happens if you provide an opportunity to not synchronize a ton of unnecessary data? Instead of, for example, 500 GB stored locally (out of the paid 2 TB), only 100 will be stored on the server. The thought “I think I'm paying a little too much" may sound louder in the head. It's not far from leaving for competitors.

And there are a lot of them these days. Here are just some options (prices are per year):

Google One: 100 GB for $20 and 2 TB for $100;
Microsoft OneDrive: 100 GB for $20 and 1 TB for $70;
Sync: 2 TB for $96;
pCloud: 500 GB for €50 and 2 TB for €100;
MEGA: 400 GB for €50 and 2 TB for €100.

Dropbox, meanwhile, only suggests 2 TB for $120. Not to mention that some of the above products have built-in functionality for ignoring files and folders.

There are a lot of requests for a more diverse range of plans, for example, Is there any smaller plan like 100 GB? or Can we have a lite plan?. By the way, I already forgot, but it turns out there was a 1 TB option before. So the increase in the volume provided and the resulting price fit into the company's strategy to raise revenue.

To be fair, there were also requests for larger storage amounts, for example, Allow a personal account to have more than 3 TB or Personal plans with more storage.

In April 2023, the CEO of the company announced the dismissal of 500 employees. Among the reasons, it is indicated that although the company is profitable, growth has slowed down. Presumably, Dropbox is trying to increase profits in various ways, so there is little hope for the emergence of alternative pricing plans or providing an opportunity to reduce the amount of data stored by users.

Conclusion

Dropbox was once the leading, if not the only, product providing cloud data storage. Using it meant getting high-quality and reliable service. Unfortunately, sometimes if a company is successful enough, it begins to ignore the voice of its users. And that can come back to the company in a bad way.

There are many discussions on the web, the essence of which is the same: Dropbox is stagnating. The company does not implement new really useful functions and does not listen to its users, although it provides them with a tribune in the form of a platform for publishing ideas. In fact, this site merely offered the illusion that we can influence the development of the product. Ignoring the most desired feature for a decade is nonsense.

According to the earnings reports, the number of paid accounts exceeds 18 million. This means that several thousand dissenters aren't going to make any difference. So see you next year!

Music via piano roll via C#

Melanchall — Tue, 10 Sep 2024 18:18:32 +0000

Are you a composer? Is the music a thing you express your creativity with? The article shows how you, as a programmer, can create musical compositions via C# and piano roll notation provided by the DryWetMIDI library.

Piano roll is a masterpiece of the digital music industry. I’m pretty sure all of you who create music know that great tool provided by DAWs. But wait… Digital music? DAW? In fact, piano roll is a thing with a much longer history then digital audio workstations and computers at all. It’s pretty interesting how the music storage medium for a player piano has been taken as an idea for visual representation of music on computers.

I’m a developer of the DryWetMIDI library. It has a rich set of features related to MIDI and MIDI-based music creation and editing. You can examine the README file or read help articles on the documentation site. Starting from the 7.0.2 version the library provides a way to create simple music parts via a piano roll string. It’s the subject of this article.

Pattern
Piano roll
Customization
Conclusion

Pattern

Before we dive into the piano roll magic provided by the DryWetMIDI, let’s take a look at the Pattern API which allows to create a MIDI file in a more "musical" manner. The key class here is the PatternBuilder which makes it easy to build a musical composition step by step. Using the PatternBuilder, you work with a fluent interface. Small example:

var patternBuilder = new PatternBuilder()
    .Note(Octave.Get(4).A, new MusicalTimeSpan(5, 17), (SevenBitNumber)68)
    .Note(Note.Get(NoteName.GSharp, 3), new MetricTimeSpan(0, 0, 2))
    .Note(“F#4”);

We add three notes here:

A4 with length of 5/17 and velocity of 68;
G#3 with a length of 2 seconds;
and F#4.

The last Note method call inserts the note with default length and velocity that can be altered via corresponding methods at any moment:

var patternBuilder = new PatternBuilder()
    .SetNoteLength(MusicalTimeSpan.Half)
    .SetVelocity((SevenBitNumber)50)

    // All the following notes will have length of 1/2 and velocity of 50

    .Note(Octave.Get(4).A)
    .Note(Note.Get(NoteName.B, 1))
    .Note(-Interval.Two)

    .SetNoteLength(MusicalTimeSpan.Quarter)

    // All the following notes will have length of 1/4

    .Note(Octave.Get(2).A);

Notes (and other actions) are added after each other. So where a note ends, the following one starts.

You can also add chords, markers, control changes, move the current position back and forth and do many other actions. Please take a look at the entire API provided by the PatternBuilder.

What about something more interesting? Following example shows how to create first four bars of the Beethoven's "Moonlight Sonata":

// Define a chord for the bass part which is just an octave
var bassChord = new[] { Interval.Twelve };

// Build the composition
var pattern = new PatternBuilder()

    // The length of all main theme's notes within four first bars is
    // triplet eighth so set it as a note length which will free us from necessity to specify
    // the length of each note explicitly

    .SetNoteLength(MusicalTimeSpan.Eighth.Triplet())

    // Anchor current time (start of the pattern) to jump to it
    // when we'll start to program bass part

    .Anchor()

    // We will add notes relative to G#3.
    // Instead of Octave.Get(3).GSharp it is possible to use Note.Get(NoteName.GSharp, 3)

    .SetRootNote(Octave.Get(3).GSharp)

    // Add first three notes and repeat them seven times which will
    // give us two bars of the main theme

                           // G#3
    .Note(Interval.Zero)   // +0  (G#3)
    .Note(Interval.Five)   // +5  (C#4)
    .Note(Interval.Eight)  // +8  (E4)

    .Repeat(3, 7)          // repeat three previous notes seven times

    // Add notes of the next two bars

                           // G#3
    .Note(Interval.One)    // +1  (A3)
    .Note(Interval.Five)   // +5  (C#4)
    .Note(Interval.Eight)  // +8  (E4)

    .Repeat(3, 1)          // repeat three previous notes
                           // one time

    .Note(Interval.One)    // +1  (A3)
    .Note(Interval.Six)    // +6  (D4)
    .Note(Interval.Ten)    // +10 (F#4)

    .Repeat(3, 1)          // repeat three previous notes
                           // one time reaching the end of
                           // third bar

    .Note(Interval.Zero)   // +0  (G#3)
    .Note(Interval.Four)   // +4  (C4)
    .Note(Interval.Ten)    // +10 (F#4)
    .Note(Interval.Zero)   // +0  (G#3)
    .Note(Interval.Five)   // +5  (C#4)
    .Note(Interval.Eight)  // +8  (E4)
    .Note(Interval.Zero)   // +0  (G#3)
    .Note(Interval.Five)   // +5  (C#4)
    .Note(Interval.Seven) // +7  (D#4)
    .Note(-Interval.Two)   // -2  (F#3)
    .Note(Interval.Four)   // +4  (C4)
    .Note(Interval.Seven)  // +7  (D#4)

    // Now we will program the bass part. To start adding notes from the
    // beginning of the pattern we need to move to the anchor we set
    // above

    .MoveToFirstAnchor()

    // First two chords have the whole length

    .SetNoteLength(MusicalTimeSpan.Whole)

                                            // insert a chord relative to
    .Chord(bassChord, Octave.Get(2).CSharp) // C#2 (C#2, C#3)
    .Chord(bassChord, Octave.Get(1).B)      // B1  (B1, B2)

    // Remaining four chords has half length

    .SetNoteLength(MusicalTimeSpan.Half)

    .Chord(bassChord, Octave.Get(1).A)      // A1  (A1, A2)
    .Chord(bassChord, Octave.Get(1).FSharp) // F#1 (F#1, F#2)
    .Chord(bassChord, Octave.Get(1).GSharp) // G#1 (G#1, G#2)

    .Repeat()                               // repeat the previous chord

    // Build a pattern that can be then saved to a MIDI file

    .Build();

Build method returns an instance of the Pattern. A pattern can be transformed or altered by methods in PatternUtilities.

Pattern can be then saved to MidiFile (via ToFile method) or TrackChunk (via ToTrackChunk method). You need to provide a tempo map. Also you can optionally specify the channel that should be set to events. The default channel is 0. If you want to output the data to the default drum channel, just set (FourBitNumber)9 (channel is a number from 0 to 15 in the DryWetMIDI, so you need to pass 9 instead of 10).

Also please see the Extension methods section of the Pattern API.

Piano roll

And now we’re getting to the subject of the article. There is a way to create simple patterns easily — via the PianoRoll method. The method was introduced in the 7.2.0 version of the library. To quickly dive into the method, just take a look at this example:

var midiFile = new PatternBuilder()
    .SetNoteLength(MusicalTimeSpan.Eighth)
    .PianoRoll(@"
        F#2   ||||||||
        D2    --|---|-
        C2    |---|---")
    .Repeat(9)
    .Build()
    .ToFile(TempoMap.Default, (FourBitNumber)9);
midiFile.Write("pianoroll-simple.mid", true);

Each line starts with a note. Think about a line as a piano roll lane in your favorite DAW. So notes on the first line will be F#2, on the second line — D2 and on the third one — C2. Each character then except spaces means one cell. The length of a cell is determined by the SetNoteLength method.

'|' symbol means a single-cell note, i.e. the note's length is equal to a cell's length. So each note in the example will be an 8th one. By the way, you can alter this symbol with the SingleCellNoteSymbol property of the PianoRollSettings passed to the PianoRoll method.

Hyphen ('-') means nothing except a step of a cell's length. We will call it a fill symbol. You should keep in mind that spaces will be cut from the piano roll string before processing. So it's required to use a fill symbol to specify an empty space (rest) to get correct results. For example, this pattern:

F2   ||||
D2     |
C2   |

will be transformed by the piano roll processing engine to these strings:

F2||||
D2|
C2|

which is probably not what you want.

Be aware that a fill symbol must not be the same as those used for notes and must not be a part of a collection of custom actions symbols (see Customization section further).

The example above demonstrates how to create a simple drum rhythm — standard 8th note groove — using General MIDI drum map. You can listen to the file produced — pianoroll-simple.mid. By the way, you can use notes numbers instead of letters and octaves (and don't forget about string interpolation along with meaningful variables names):

var bassDrum = 36;
var snareDrum = 38;
var closedHiHat = 42;

var midiFile = new PatternBuilder()
    .SetNoteLength(MusicalTimeSpan.Eighth)
    .PianoRoll(@$"
        {closedHiHat}   ||||||||
          {snareDrum}   --|---|-
           {bassDrum}   |---|---")
    .Repeat(9)
    .Build()
    .ToFile(TempoMap.Default, (FourBitNumber)9);
midiFile.Write("pianoroll-simple.mid", true);

Or you can create an extension method like this:

public static PatternBuilder GmDrumPattern(
    this PatternBuilder patternBuilder,
    params (GeneralMidiPercussion Instrument, string PianoRollLine)[] pianoRoll)
{
    return patternBuilder.PianoRoll(string.Join(
        Environment.NewLine,
        pianoRoll.Select(l => $"{l.Instrument.AsSevenBitNumber()} {l.PianoRollLine}")));
}

And call it then:

var midiFile = new PatternBuilder()
    .SetNoteLength(MusicalTimeSpan.Eighth)
    .GmDrumPattern(
        (GeneralMidiPercussion.ClosedHiHat,      "||||||||"),
        (GeneralMidiPercussion.AcousticSnare,    "--|---|-"),
        (GeneralMidiPercussion.AcousticBassDrum, "|---|---"))
    .Repeat(9)
    .Build()
    .ToFile(TempoMap.Default, (FourBitNumber)9);

But let's take a more interesting example which we looked at above — "Moonlight Sonata". The same first four bars of it can be constructed via piano roll like this:

var midiFile = new PatternBuilder()
    .SetNoteLength(MusicalTimeSpan.Eighth.Triplet())
    .PianoRoll(@"
        F#4   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙|∙∙|   ∙∙|∙∙∙∙∙∙∙∙∙
        E4    ∙∙|∙∙|∙∙|∙∙|   ∙∙|∙∙|∙∙|∙∙|   ∙∙|∙∙|∙∙∙∙∙∙   ∙∙∙∙∙|∙∙∙∙∙∙
        D#4   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙|∙∙|
        C#4   ∙|∙∙|∙∙|∙∙|∙   ∙|∙∙|∙∙|∙∙|∙   ∙|∙∙|∙∙∙∙∙∙∙   ∙∙∙∙|∙∙|∙∙∙∙
        C4    ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙|∙∙∙∙∙∙∙∙|∙
        D4    ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙|∙∙|∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        A3    ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   |∙∙|∙∙|∙∙|∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        G#3   |∙∙|∙∙|∙∙|∙∙   |∙∙|∙∙|∙∙|∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   |∙∙|∙∙|∙∙∙∙∙
        F#3   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙|∙∙

        C#3   [==========]   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        B2    ∙∙∙∙∙∙∙∙∙∙∙∙   [==========]   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        A2    ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   [====]∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        G#2   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   [====][====]
        F#2   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙[====]   ∙∙∙∙∙∙∙∙∙∙∙∙
        C#2   [==========]   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        B1    ∙∙∙∙∙∙∙∙∙∙∙∙   [==========]   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        A1    ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   [====]∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙
        G#1   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   [====][====]
        F#1   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙∙∙∙∙∙∙   ∙∙∙∙∙∙[====]   ∙∙∙∙∙∙∙∙∙∙∙∙")
    .Build()
    .ToFile(TempoMap.Create(Tempo.FromBeatsPerMinute(69)));
midiFile.Write("pianoroll-moonlight-sonata.mid", true);

And here is the file — pianoroll-moonlight-sonata.mid.

Along with usage of spaces to separate bars visually for more readability you can see several new symbols in this example:

'.' and '=' are both just fill symbols.
'[' and ']' mean the start and the end of a multi-cell note correspondingly. These symbols can be changed too, see properties MultiCellNoteStartSymbol and MultiCellNoteEndSymbol of the PianoRollSettings that you can pass to the PianoRoll method.

Well, we can define long notes (multi-cell) along with single-cell ones. As for length of such notes, let's see at this note:

[====]

The length will be of six cells:

[====]
123456

So if one cell means 8th triplet time span in our example, the length of the note will be 1/2.

Customization

It's time to discuss how you can adjust piano roll processing. First of all, as we said before, you can set custom symbols for a single-cell note, start and end of a multi-cell note:

var midiFile = new PatternBuilder()
    .SetNoteLength(MusicalTimeSpan.Eighth.Triplet())
    .PianoRoll(@"
        F#4 ∙∙@∙∙@∙∙∙∙∙∙
        E4  ∙∙∙(~~~~~~~)", new PianoRollSettings
        {
            SingleCellNoteSymbol = '@',
            MultiCellNoteStartSymbol = '(',
            MultiCellNoteEndSymbol = ')',
        })
    .Build()
    .ToFile(TempoMap.Default);

So the way to customize the piano roll algorithm is to pass PianoRollSettings. But you can also define your own actions triggered by specified symbols. Let's take a look at the following example (yes, drums again):

var pianoRollSettings = new PianoRollSettings
{
    CustomActions = new Dictionary<char, Action<Melanchall.DryWetMidi.MusicTheory.Note, PatternBuilder>>
    {
        ['*'] = (note, pianoRollBuilder) => pianoRollBuilder
            .Note(note, velocity: (SevenBitNumber)(pianoRollBuilder.Velocity / 2)),
        ['║'] = (note, pianoRollBuilder) => pianoRollBuilder
            .Note(note, pianoRollBuilder.NoteLength.Divide(2))
            .Note(note, pianoRollBuilder.NoteLength.Divide(2), (SevenBitNumber)(pianoRollBuilder.Velocity / 2)),
        ['!'] = (note, pianoRollBuilder) => pianoRollBuilder
            .StepBack(MusicalTimeSpan.ThirtySecond)
            .Note(note, MusicalTimeSpan.ThirtySecond, (SevenBitNumber)(pianoRollBuilder.Velocity / 3))
            .Note(note),
    }
};

var bassDrum = 36;
var snareDrum = 38;
var closedHiHat = 42;

var midiFile = new PatternBuilder()
    .SetNoteLength(MusicalTimeSpan.Eighth)
    .PianoRoll(@$"
        {closedHiHat}   -------|   ║║|----|
          {snareDrum}   -*|---!-   --|--*!|
           {bassDrum}   |--║|---   |-|║|---",
        pianoRollSettings)
    .Repeat(9)
    .Build()
    .ToFile(TempoMap.Default, (FourBitNumber)9);
midiFile.Write("pianoroll-custom.mid", true);

And here the file — pianoroll-custom.mid. But what we have in the piano roll string:

'*' — ghost note (played with half of the current velocity);
'║' — double note (two notes, each with length of half of the single-cell note);
'!' — flam (ghost thirty-second note right before main beat).

Right now it's possible to specify single-cell actions only. A way to put custom multi-cell actions will be implemented in the next release.

Conclusion

Now you know how you can create simple music patterns. Just install DryWetMIDI into your project, type new PatternBuilder() and dot then and see what you can do. Of course you can ask any questions here in the comments or create an issue or start a discussion in the GitHub.

By the way, modern AI handles text pretty well, so maybe it’s a good idea to try to train a model to generate piano roll strings?... It’s just a thought.

Creating a NuGet package for a library with platform-specific API

Melanchall — Mon, 03 Oct 2022 17:38:23 +0000

It's my article reposted from Habr.

It's the English version of this article. Shout-out to Viktor Fedotov for helping with translation.

I’m developing a .NET library DryWetMIDI which is used to work with MIDI files and MIDI devices. Most of the library API is cross-platform (within the operating systems supported by .NET of course), however the exact handling of MIDI devices is different for every operating system. Currently the corresponding API works on Windows only, but there is a strong desire to support other systems too. I’m not rushing to support all the existing platforms from the start, so I’m going to make the API to work on macOS first, since it’s no less popular than Windows, but probably is the most popular one among music professionals.

Of course, it doesn't make sense to implement the whole API right away and It’s much easier to make sure that everything works on a small example. This is exactly what I did, and I am suggesting you to go through the whole path to the final solution along with me. The brief list of steps is at the end of the article.

First attempts

As it’s usually done in the .NET world the library is distributed through the NuGet package manager. That's why I immediately knew that the package must contain native binaries to provide API for specific operating systems.

In C# we can write a declaration of an external function as follows:

[DllImport("test")]public static extern int Foo();

As you can see we don’t need to specify the extension of a native library since .NET will use a suitable one based on the current operating system. In other words, if test.dll and test.dylib files are located alongside our application, the function Foo will be called from test.dll on Windows, and from test.dylib on macOS. We can scale the solution to *nix systems by providing a test.so file.

To move forward let’s create a project for our test library. DryWetMIDI specifies netstandard2.0 and net45 TFMs within its .csproj file, so in order to be as close as possible to the real conditions I specified those target platforms for the test project as well. The project will be called DualLibClassLibrary and will contain a single file Class.cs:

using System.Runtime.InteropServices;

namespace DualLibClassLibrary
{
    public static class Class
    {
        [DllImport("test")]
        public static extern int Foo();

        public static int Bar()
        {
            return Foo() * 1000;
        }
    }
}

Of course we also need native binaries: test.dll and test.dylib. I compiled them from a simple C code (I’m going to use the same approach for the real library):

for Windows

int Foo() { return 123; }

for macOS

int Foo() { return 456; }

If you’re interested, test.dll and test.dylib files were created within an Azure DevOps test pipeline (in fact two pipelines: one for Windows and one for macOS). After all of that, I’ll need to do all the required actions within CI builds, so right away I decided to see how it should be done for the DryWetMIDI. The pipeline is pretty simple and it consist of 3 steps:

1. generate a file containing C code (PowerShell task)

New-Item "test.c" -ItemType File -Value "int Foo() { return 123; 
}"

(return 456; for macOS);

2. build a library (Command Line task)

gcc -v -c test.c
gcc -v -shared -o test.dll test.o

(test.dylib for macOS);

3. publish an artifact with the library (Publish Pipeline Artifact task)

Here we have test.dll and test.dylib files implementing the same function Foo, which returns 123 for Windows and 456 for macOS, this way we can always easily check if a result of a function call is correct. We’ll place the files near DualLibClassLibrary.csproj.

Now we need to figure out how to add the files to a NuGet package so they are copied to the output directory after each application build in order to guarantee that our test library will work as it should. Since the library is cross-platform and uses the new .csproj format (SDK style), it would be great to declare packing instructions there. After doing some research I came up with this .csproj:

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <TargetFrameworks>netstandard2.0;net45</TargetFrameworks>
    <LangVersion>6</LangVersion>
    <Configurations>Debug;Release</Configurations>
  </PropertyGroup>

  <PropertyGroup>
    <PackageId>DualLibClassLibrary</PackageId>
    <Version>1.0.0</Version>
    <Authors>melanchall</Authors>
    <Owners>melanchall</Owners>
    <Description>Dual-lib class library</Description>
    <Copyright>Copyright  Melanchall 2021</Copyright>
    <AutoGenerateBindingRedirects>true</AutoGenerateBindingRedirects>
  </PropertyGroup>

  <ItemGroup>
    <Content Include="test.dll">
      <Pack>true</Pack>
      <CopyToOutputDirectory>Always</CopyToOutputDirectory>
    </Content>
    <Content Include="test.dylib">
      <Pack>true</Pack>
      <CopyToOutputDirectory>Always</CopyToOutputDirectory>
    </Content>
  </ItemGroup>

</Project>

Building the package:

dotnet pack .\DualLibClassLibrary.sln -c Release

To check the package installation let’s create a folder somewhere, add it as a packages feed in Visual Studio and put the generated file DualLibClassLibrary.1.0.0.nupkg to this folder. We are going to use classic .NET Framework on Windows to check the package installation. Now let’s create a console application and install our library into it. After doing so we can see the two files have appeared in the project:

So good so far, let’s write a simple code within the Program.cs:

static void Main(string[] args)
{
    var result = DualLibClassLibrary.Class.Bar();
    Console.WriteLine($"Result = {result}. Press any key to exit...");
    Console.ReadKey();
}

After running the application we see the unsatisfying picture:

Well... let’s take a look into bin/Debug folder:

Surprisingly enough the files are missing. It is indeed strange since we’ve specified the <CopyToOutputDirectory> item for them and we do actually see the files within the project structure. But everything becomes clear after we take a look into the .csproj file:

We have two weird things here. Firstly the <CopyToOutputDirectory> item is missing. And secondly, test.dylib has been added as <None> item but test.dll has been added as <Content> item. If we take a look into the .nupkg file with NuGet Package Explorer, we’ll see the following manifest:

<?xml version="1.0" encoding="utf-8"?>
<package xmlns="http://schemas.microsoft.com/packaging/2012/06/nuspec.xsd">
  <metadata>
    <id>DualLibClassLibrary</id>
    <version>1.0.0</version>
    <authors>melanchall</authors>
    <owners></owners>
    <requireLicenseAcceptance>false</requireLicenseAcceptance>
    <description>Dual-lib class library</description>
    <copyright>Copyright  Melanchall 2021</copyright>
    <dependencies>
      <group targetFramework=".NETFramework4.5" />
      <group targetFramework=".NETStandard2.0" />
    </dependencies>
    <contentFiles>
      <files include="any/net45/test.dll" buildAction="Content" />
      <files include="any/netstandard2.0/test.dll" buildAction="Content" />
      <files include="any/net45/test.dylib" buildAction="Content" />
      <files include="any/netstandard2.0/test.dylib" buildAction="Content" />
    </contentFiles>
  </metadata>
</package>

As you can see, sadly, the files were added without the copyToOutput attribute (you can read about the attribute here in the table: Using the contentFiles element for content files).

Copying files to the application’s output directory

After looking through the web (including issues on GitHub, answers on StackOverflow and official Microsoft documentation), I modified the files packing elements in the library’s .csproj:

<Content Include="test.dll">
  <Pack>true</Pack>
  <CopyToOutputDirectory>Always</CopyToOutputDirectory>
  <PackageCopyToOutput>true</PackageCopyToOutput>
  <PackagePath>contentFiles;content</PackagePath>
</Content>
<Content Include="test.dylib">
  <Pack>true</Pack>
  <CopyToOutputDirectory>Always</CopyToOutputDirectory>
  <PackageCopyToOutput>true</PackageCopyToOutput>
  <PackagePath>contentFiles;content</PackagePath>
</Content>

The <PackageCopyToOutput> item is exactly what we need to make the copyToOutput attribute to appear in the package manifest. Also we explicitly specified destination folders for the files to avoid directories like any. If you’re interested in this topic you can read more here: Including content in a package.

Let’s build the project one more time and check the manifest:

<?xml version="1.0" encoding="utf-8"?>
<package xmlns="http://schemas.microsoft.com/packaging/2012/06/nuspec.xsd">
  <metadata>
    <id>DualLibClassLibrary</id>
    <version>1.0.1</version>
    <authors>melanchall</authors>
    <owners></owners>
    <requireLicenseAcceptance>false</requireLicenseAcceptance>
    <description>Dual-lib class library</description>
    <copyright>Copyright  Melanchall 2021</copyright>
    <dependencies>
      <group targetFramework=".NETFramework4.5" />
      <group targetFramework=".NETStandard2.0" />
    </dependencies>
    <contentFiles>
      <files include="test.dll" buildAction="Content" copyToOutput="true" />
      <files include="test.dylib" buildAction="Content" copyToOutput="true" />
    </contentFiles>
  </metadata>
</package>

Another failure. If we are going to try the same thing in .NET5, we’ll get:

Basically there’s no difference except a slightly changed message of the exception. After submitting a GitHub issue I received the answer:

Please see our docs on contentFiles. It supports adding different content depending on project's target framework and language, and therefore needs files in a specific structure which your package is not currently using.

It turns out that I overlooked a few details in the documentation: if you add files into directories named like contentFiles/any/netstandard2.0 instead of simply contentFiles, a .props file is created automatically and it contains proper elements for copying files to the application’s output directory. However before I received any answer I did my own research and came up with a different approach. And in hindsight it was the right decision and the reason is that you will not have all of the files installed properly from a package into your .NET Framework application when using the contentFiles folder. I strongly believe it is an important scenario and thus it must be supported.

There is an article on the Microsoft documentation with a promising title: Creating native packages. The article itself is not very informative, but we can learn something useful from it – the fact that we can create a .targets file with <CopyToOutputDirectory> elements specified for our files. The .targets file must be included in a package along with native libraries. Well, let’s create DualLibClassLibrary.targets file:

<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <ItemGroup>
    <None Include="$(MSBuildThisFileDirectory)test.dll">
      <Link>test.dll</Link>
      <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
    </None>
    <None Include="$(MSBuildThisFileDirectory)test.dylib">
      <Link>test.dylib</Link>
      <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
    </None>
  </ItemGroup>
</Project>

And in the DualLibClassLibrary.csproj file we write:

<ItemGroup>
  <None Include="test.dll">
    <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
    <PackagePath>build\</PackagePath>
    <Pack>true</Pack>
  </None>
  <None Include="test.dylib">
    <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
    <PackagePath>build\</PackagePath>
    <Pack>true</Pack>
  </None>
  <None Include="DualLibClassLibrary.targets">
    <PackagePath>build\</PackagePath>
    <Pack>true</Pack>
  </None>
</ItemGroup>

By building a package for the version 1.0.2, installing it to our .NET Framework console application and running it we have:

This exception is usually thrown when the application's process is 64-bit while the native library is 32-bit or the other way around. But in this case I built the libraries on 64-bit systems and the application was running on a 64-bit operating system too. Well, it seems our journey continues.

Support for 32-bit and 64-bit processes

If we open the properties of our console application project in Visual Studio inside the Build tab, we can see this checkbox:

It turns out, this option is checked by default for a .NET Framework project and the application’s process will be 32-bit even on a 64-bit operating system. It’s funny that for .NET Core/.NET 5 projects this option is turned off by default:

Of course, we can turn this option off and the application will finally print the correct result:

Result = 123000. Press any key to exit...

But that’s obviously not the solution for the following reasons:

we won’t be able to use the library in 32-bit processes;
it requires additional actions from a user (unchecking a checkbox);
the classic default scenario (create new .NET Framework application without any additional actions) won’t be supported.

Certainly this is not an option and the problem must be solved. In fact the solution is obvious: let’s just create native binaries for each operating system in two versions – 32-bit and 64-bit. It means the package will be larger in size since it will contain 4 platform-specific libraries instead of 2. I don’t see anything wrong with this approach because the files are small, and thus I am going to proceed with it (and I can’t see how it can be done in another way).

Let me briefly tell you about how I build 32-bit libraries. As I’ve mentioned above I create binaries within Azure DevOps pipelines using gcc. gcc is called with -m32 flag which in theory tells gcc to build a 32-bit library. This is fine on build agents with macOS images, but on Windows I got quite a few nasty log messages:

C:/ProgramData/Chocolatey/lib/mingw/tools/install/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/8.1.0/../../../../x86_64-w64-mingw32/bin/ld.exe: skipping incompatible C:/ProgramData/Chocolatey/lib/mingw/tools/install/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/8.1.0/../../../../x86_64-w64-mingw32/lib\libuser32.a when searching for -luser32
...
C:/ProgramData/Chocolatey/lib/mingw/tools/install/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/8.1.0/../../../../x86_64-w64-mingw32/lib/libmsvcrt.a when searching for -lmsvcrt C:/ProgramData/Chocolatey/lib/mingw/tools/install/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/8.1.0/../../../../x86_64-w64-mingw32/bin/ld.exe: cannot find -lmsvcrt collect2.exe: error: ld returned 1 exit status

I asked a question about these errors on StackOverflow and on Microsoft Developer Community site, and got answers stating that the 32-bit version of the MinGW is not preinstalled on Microsoft-hosted agents, which causes the error. After trying many options, I chose the brechtsanders/winlibs_mingw project creating a simple PowerShell script:

Write-Host "Downloading winlibs..."
Invoke-WebRequest -Uri "https://github.com/brechtsanders/winlibs_mingw/releases/download/11.1.0-12.0.0-9.0.0-r1/winlibs-i686-posix-dwarf-gcc-11.1.0-mingw-w64-9.0.0-r1.zip" -OutFile "winlibs.zip"
Write-Host "Downloaded."

Write-Host "Extracting winlibs..."
Expand-Archive -LiteralPath 'winlibs.zip' -DestinationPath "winlibs"
Write-Host "Extracted."

Write-Host "Building DLL..."
$gccPath = Get-ChildItem -Path "winlibs" -File -Filter "i686-w64-mingw32-gcc.exe" -Recurse

& $gccPath.FullName -c test.c -m32
& $gccPath.FullName -shared -o test.dll test.o -m32
Write-Host "Built."

By using the i686-w64-mingw32-gcc.exe compiler from the archive, I was finally able to build the 32-bit test.dll. Hooray!

Now we need to figure out how to tell our library which API to use: 32-bit or 64-bit one. I am quite sure there are multiple different approaches, but I settled on the following one:

build test32.dll, test64.dll, test32.dylib and test64.dylib native binaries;
create abstract class Api containing abstract methods that correspond to our managed API for internal usage;
create two subclasses of Api – Api32 and Api64 – which will implement abstract API from the base class calling unmanaged API from test32 and test64 correspondingly;
create class ApiProvider with the Api property which will return an implementation based on a current process bitness.

Here the code of the classes:

Api.cs

namespace DualLibClassLibrary
{
    internal abstract class Api
    {
        public abstract int Method();
    }
}

Api32.cs

using System.Runtime.InteropServices;

namespace DualLibClassLibrary
{
    internal sealed class Api32 : Api
    {
        [DllImport("test32")]
        public static extern int Foo();

        public override int Method()
        {
            return Foo();
        }
    }
}

Api64.cs

using System.Runtime.InteropServices;

namespace DualLibClassLibrary
{
    internal sealed class Api64 : Api
    {
        [DllImport("test64")]
        public static extern int Foo();

        public override int Method()
        {
            return Foo();
        }
    }
}

ApiProvider.cs

using System;

namespace DualLibClassLibrary
{
    internal static class ApiProvider
    {
        private static readonly bool Is64Bit = IntPtr.Size == 8;
        private static Api _api;

        public static Api Api
        {
            get
            {
                if (_api == null)
                    _api = Is64Bit ? (Api)new Api64() : new Api32();

                return _api;
            }
        }
    }
}

And then the code of Class class will be:

namespace DualLibClassLibrary
{
    public static class Class
    {
        public static int Bar()
        {
            return ApiProvider.Api.Method() * 1000;
        }
    }
}

After a new version of the package is created (of course with new files added to the DualLibClassLibrary.targets and DualLibClassLibrary.csproj before that) we’ll see that the method of our library works correctly no matter whether application’s process is 32-bit or 64-bit.

Conclusion

Here you have a complete chronology of my trials on the creation of a NuGet package with platform-specific API, and it would be useful to briefly list the main points (I promised the instructions after all):

create native binaries in 32-bit and 64-bit versions;
place them near a library project (you can place them in any folder and specify the folder’s path in .csproj and .targets files);
add .targets file with the <CopyToOutputDirectory> element (with desired value) added for each native file;
add elements for packing .targets file (should be placed in the build folder of a package) and all native binaries in the .csproj file;
implement a way to select a native file based on the fact whether a process is 32-bit or 64-bit.

Simple as that! The solution of our test library is available here: DualLibClassLibrary.zip. The library was tested in the following scenarios on Windows and macOS:

.NET Framework application;
.NET Core / .NET 5 application;
Self-contained application.

As for support of 32-bit and 64-bit processes – I’ve checked only on Windows, I'm not sure how to check it on macOS.

DEV Community: Melanchall

Red-black tree: complete C# implementation

Table of contents

Why?

Construction

Interval tree

Conclusion

Dropbox: How to Ignore Users for 10 Years

Table of contents

How this all began

An idea!

Vox populi

Timeline

Suggested options

Storing data outside the Dropbox folder

Selective Sync

Official solution

Why does Dropbox act like this?

Conclusion

Music via piano roll via C#

Table of contents

Pattern

Piano roll

Customization

Conclusion

Creating a NuGet package for a library with platform-specific API

First attempts

Copying files to the application’s output directory

Support for 32-bit and 64-bit processes

Conclusion