README.md

Superseded by the full AltTreeMap repository.

See the the AltTreeMap class there.

With that said, if for some reason you want to use code from this gist, it's offered under 0BSD. See LICENSE.

AltTreeMap.cs

// SPDX-License-Identifier: 0BSD

/// <summary>A few fragments of a BST implementation.</summary>
public sealed class AltTreeMap<TKey, TValue> {
    public AltTreeMap() : this(Comparer<TKey>.Default) { }
    
    public AltTreeMap(IComparer<TKey> comparer)
        => Comparer = comparer;
    
    public IComparer<TKey> Comparer { get; }
    
    public int Count { get; private set; } = 0;
    
    public TValue this[TKey key]
    {
        get {
            var node = Search(key, out _);
            
            if (node == null) {
                throw new ArgumentException(paramName: nameof(key),
                                            message: "key not found");
            }
            
            return node.Value;
        }
        
        set {
            ref var child = ref Search(key, out var parent);
            
            if (child == null)
                Emplace(ref child, parent, key, value);
            else
                child.Value = value;
        }
    }
    
    public void Add(TKey key, TValue value)
    {
        ref var child = ref Search(key, out var parent);
        
        if (child != null) {
            throw new ArgumentException(paramName: nameof(key),
                                        message: "key already exists");
        }
        
        Emplace(ref child, parent, key, value);
    }
    
    public bool ContainsKey(TKey key)
        => Search(key, out _) != null;
    
    private sealed class Node {
        internal Node(TKey key, TValue value, Node? parent)
            : this(key, value, parent, null, null) { }
    
        internal Node(TKey key, TValue value,
                        Node? parent, Node? left, Node? right)
        {
            Key = key;
            Value = value;
            Parent = parent;
            Left = left;
            Right = right;
        }
        
        internal TKey Key { get; }
        
        internal TValue Value { get; set; }
        
        internal Node? Parent;
        
        internal Node? Left;
        
        internal Node? Right;
    }
    
    private ref Node? Search(TKey key, out Node? resultParent)
    {
        var parent = default(Node?);
        ref var child = ref _root;
        
        while (child != null) {
            var comp = Comparer.Compare(key, child.Key);
            
            if (comp < 0) {
                parent = child;
                child = ref parent.Left;
            }
            else if (comp != 0) {
                parent = child;
                child = ref parent.Right;
            }
            else break;
        }
        
        resultParent = parent;
        return ref child;
    }
    
    private void Emplace(ref Node? child, Node? parent,
                            TKey key, TValue value)
    {
        child = new Node(key, value, parent);
        ++Count;
        ++_version;
    }
    
    private Node? _root = null;
    
    private ulong _version = 0uL;
}

LICENSE

BSD Zero Clause License

Copyright (c) 2020 Eliah Kagan

Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.