<commit_before>using System.Runtime.CompilerServices;

namespace ImTools.Experimental.Tree234
{
    /// <summary>The base class for tree leafs and branches, defines the Empty tree</summary>
    public class ImMap<V>
    {
        /// <summary>Empty tree to start with.</summary>
        public static readonly ImMap<V> Empty = new ImMap<V>();

        /// <summary>Hide the constructor to prevent the multiple Empty trees creation</summary>
        protected ImMap() { }

        /// <summary>Produces the new or updated map</summary>
        public virtual ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry) => entry;
    }

    /// <summary>Wraps the stored data with "fixed" reference semantics - 
    /// when added to the tree it won't be changed or reconstructed in memory</summary>
    public sealed class ImMapEntry<V> : ImMap<V>
    {
        /// <summary>The Key is basically the hash, or the Height for ImMapTree</summary>
        public readonly int Key;

        /// <summary>The value - may be modified if you need a Ref{V} semantics</summary>
        public V Value;

        /// <summary>Constructs the entry with the default value</summary>
        public ImMapEntry(int key) => Key = key;

        /// <summary>Constructs the entry with the key and value</summary>
        public ImMapEntry(int key, V value)
        {
            Key = key;
            Value = value;
        }

        /// Prints the key value pair
        public override string ToString() => Key + ":" + Value;

        /// <summary>Produces the new or updated map</summary>
        public override ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry) =>
            entry.Key > Key ? new ImMapLeafs2<V>(this, entry) : 
            entry.Key < Key ? new ImMapLeafs2<V>(entry, this) : 
            (ImMap<V>)entry;
    }

    /// <summary>2 leafs</summary>
    public class ImMapLeafs2<V> : ImMap<V>
    {
        /// <summary>Left entry</summary>
        public readonly ImMapEntry<V> Entry0;

        /// <summary>Right entry</summary>
        public readonly ImMapEntry<V> Entry1;

        /// <summary>Constructs 2 leafs</summary>
        public ImMapLeafs2(ImMapEntry<V> entry0, ImMapEntry<V> entry1)
        {
            Entry0 = entry0;
            Entry1 = entry1;
        }

        /// Prints the key value pair
        public override string ToString() => Entry0 + ";" + Entry1;

        /// <summary>Produces the new or updated map</summary>
        public override ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry) =>
            entry.Key > Entry1.Key ? new ImMapLeafs3<V>(Entry0, Entry1, entry) :
            entry.Key < Entry0.Key ? new ImMapLeafs3<V>(entry, Entry0, Entry1) :
            entry.Key > Entry0.Key && entry.Key < Entry1.Key ? new ImMapLeafs3<V>(Entry0, entry, Entry1) :
            entry.Key == Entry0.Key ? new ImMapLeafs2<V>(entry, Entry1) : 
            new ImMapLeafs2<V>(Entry0, entry);
    }

    /// <summary>3 leafs</summary>
    public sealed class ImMapLeafs3<V> : ImMapLeafs2<V>
    {
        /// <summary>Rightmost leaf</summary>
        public readonly ImMapEntry<V> Entry2;

        /// <summary>Constructs a tree leaf</summary>
        public ImMapLeafs3(ImMapEntry<V> entry0, ImMapEntry<V> entry1, ImMapEntry<V> entry2)
            : base(entry0, entry1) =>
            Entry2 = entry2;

        /// Prints the key value pair
        public override string ToString() => Entry0 + ";" + Entry1 + ";" + Entry2;

        /// <summary>Produces the new or updated map</summary>
        public override ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry)
        {
            var key = entry.Key;

            // [1 3 5]  =>      [3]
            // adding 7     [1]     [5, 7]
            if (key > Entry2.Key)
                return new ImMapBranch2<V>(Entry1, Entry0, new ImMapLeafs2<V>(Entry2, entry));

            if (key < Entry0.Key)
                return new ImMapBranch2<V>(Entry1, new ImMapLeafs2<V>(entry, Entry0), Entry2);

            if (key > Entry1.Key && key < Entry2.Key)
                return new ImMapBranch2<V>(Entry1, Entry0, new ImMapLeafs2<V>(entry, Entry2));

            if (key > Entry0.Key && key < Entry1.Key)
                return new ImMapBranch2<V>(Entry1, new ImMapLeafs2<V>(Entry0, entry), Entry2);

            return key == Entry0.Key ? new ImMapLeafs3<V>(entry, Entry1, Entry2)
                : key == Entry1.Key ? new ImMapLeafs3<V>(Entry0, entry, Entry2)
                : new ImMapLeafs3<V>(Entry0, Entry1, entry);
        }
    }

    /// <summary>2 branches</summary>
    public class ImMapBranch2<V> : ImMap<V>
    {
        /// <summary>The only entry</summary>
        public readonly ImMapEntry<V> Entry0;

        /// <summary>Left branch</summary>
        public readonly ImMap<V> Branch0; // can be Branchs | Entry | Leaf2 | Leaf3, if it is an Entry then other Tree cannot be an Entry

        /// <summary>Right branch</summary>
        public readonly ImMap<V> Branch1;

        /// <summary>Constructs</summary>
        public ImMapBranch2(ImMapEntry<V> entry0, ImMap<V> branch0, ImMap<V> branch1)
        {
            Entry0 = entry0;
            Branch0 = branch0;
            Branch1 = branch1;
        }
    }

    /// <summary>3 branches</summary>
    public sealed class ImMapBranch3<V> : ImMapBranch2<V>
    {
        /// <summary>Right entry</summary>
        public readonly ImMapEntry<V> Entry1;

        /// <summary>Rightmost branch</summary>
        public readonly ImMap<V> Branch2;

        /// <summary>Constructs</summary>
        public ImMapBranch3(ImMapEntry<V> entry0, ImMap<V> branch0, ImMap<V> branch1,
            ImMapEntry<V> entry1, ImMap<V> branch2) : base(entry0, branch0, branch1)
        {
            Entry1 = entry1;<commit_msg>wip found to how to detect the split<commit_after>using System.Runtime.CompilerServices;

namespace ImTools.Experimental.Tree234
{
    /// <summary>The base class for tree leafs and branches, defines the Empty tree</summary>
    public class ImMap<V>
    {
        /// <summary>Empty tree to start with.</summary>
        public static readonly ImMap<V> Empty = new ImMap<V>();

        /// <summary>Hide the constructor to prevent the multiple Empty trees creation</summary>
        protected ImMap() { }

        /// <summary>Produces the new or updated map</summary>
        public virtual ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry) => entry;
    }

    /// <summary>Wraps the stored data with "fixed" reference semantics - 
    /// when added to the tree it won't be changed or reconstructed in memory</summary>
    public sealed class ImMapEntry<V> : ImMap<V>
    {
        /// <summary>The Key is basically the hash, or the Height for ImMapTree</summary>
        public readonly int Key;

        /// <summary>The value - may be modified if you need a Ref{V} semantics</summary>
        public V Value;

        /// <summary>Constructs the entry with the default value</summary>
        public ImMapEntry(int key) => Key = key;

        /// <summary>Constructs the entry with the key and value</summary>
        public ImMapEntry(int key, V value)
        {
            Key = key;
            Value = value;
        }

        /// Prints the key value pair
        public override string ToString() => Key + ":" + Value;

        /// <summary>Produces the new or updated map</summary>
        public override ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry) =>
            entry.Key > Key ? new ImMapLeafs2<V>(this, entry) : 
            entry.Key < Key ? new ImMapLeafs2<V>(entry, this) : 
            (ImMap<V>)entry;
    }

    /// <summary>2 leafs</summary>
    public class ImMapLeafs2<V> : ImMap<V>
    {
        /// <summary>Left entry</summary>
        public readonly ImMapEntry<V> Entry0;

        /// <summary>Right entry</summary>
        public readonly ImMapEntry<V> Entry1;

        /// <summary>Constructs 2 leafs</summary>
        public ImMapLeafs2(ImMapEntry<V> entry0, ImMapEntry<V> entry1)
        {
            Entry0 = entry0;
            Entry1 = entry1;
        }

        /// Pretty-print
        public override string ToString() => Entry0 + ";" + Entry1;

        /// <summary>Produces the new or updated map</summary>
        public override ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry) =>
            entry.Key > Entry1.Key ? new ImMapLeafs3<V>(Entry0, Entry1, entry) :
            entry.Key < Entry0.Key ? new ImMapLeafs3<V>(entry, Entry0, Entry1) :
            entry.Key > Entry0.Key && entry.Key < Entry1.Key ? new ImMapLeafs3<V>(Entry0, entry, Entry1) :
            entry.Key == Entry0.Key ? new ImMapLeafs2<V>(entry, Entry1) : 
            new ImMapLeafs2<V>(Entry0, entry);
    }

    /// <summary>3 leafs</summary>
    public sealed class ImMapLeafs3<V> : ImMapLeafs2<V>
    {
        /// <summary>Rightmost leaf</summary>
        public readonly ImMapEntry<V> Entry2;

        /// <summary>Constructs a tree leaf</summary>
        public ImMapLeafs3(ImMapEntry<V> entry0, ImMapEntry<V> entry1, ImMapEntry<V> entry2)
            : base(entry0, entry1) =>
            Entry2 = entry2;

        /// Pretty-print
        public override string ToString() => Entry0 + ";" + Entry1 + ";" + Entry2;

        /// <summary>Produces the new or updated map</summary>
        public override ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry)
        {
            var key = entry.Key;

            // [1 3 5]  =>      [3]
            // adding 7     [1]     [5, 7]
            if (key > Entry2.Key)
                return new ImMapBranch2<V>(Entry1, Entry0, new ImMapLeafs2<V>(Entry2, entry));

            if (key < Entry0.Key)
                return new ImMapBranch2<V>(Entry1, new ImMapLeafs2<V>(entry, Entry0), Entry2);

            if (key > Entry1.Key && key < Entry2.Key)
                return new ImMapBranch2<V>(Entry1, Entry0, new ImMapLeafs2<V>(entry, Entry2));

            if (key > Entry0.Key && key < Entry1.Key)
                return new ImMapBranch2<V>(Entry1, new ImMapLeafs2<V>(Entry0, entry), Entry2);

            return key == Entry0.Key ? new ImMapLeafs3<V>(entry, Entry1, Entry2)
                : key == Entry1.Key ? new ImMapLeafs3<V>(Entry0, entry, Entry2)
                : new ImMapLeafs3<V>(Entry0, Entry1, entry);
        }
    }

    /// <summary>2 branches</summary>
    public class ImMapBranch2<V> : ImMap<V>
    {
        /// <summary>The only entry</summary>
        public readonly ImMapEntry<V> Entry0;

        /// <summary>Left branch</summary>
        public readonly ImMap<V> Branch0; // can be Branchs | Entry | Leaf2 | Leaf3, if it is an Entry then other Tree cannot be an Entry

        /// <summary>Right branch</summary>
        public readonly ImMap<V> Branch1;

        /// <summary>Constructs</summary>
        public ImMapBranch2(ImMapEntry<V> entry0, ImMap<V> branch0, ImMap<V> branch1)
        {
            Entry0 = entry0;
            Branch0 = branch0;
            Branch1 = branch1;
        }

        /// Pretty-print
        public override string ToString() =>
            (Branch0 is ImMapBranch2<V> ? Branch0.GetType().Name : Branch0.ToString()) + 
            " <- " + Entry0 + " -> " +
            (Branch1 is ImMapBranch2<V> ? Branch1.GetType().Name : Branch1.ToString());

        /// <summary>Produces the new or updated map</summary>
        public override ImMap<V> AddOrUpdateEntry(ImMapEntry<V> entry)
        {
            if (entry.Key > Entry0.Key)
            {
                //      [3]                     [3]    ->  [6]                [3, 6]
                // [1]       [5, 6, 7] =>  [1]       [4,5]     [7] =>  [1]   [4, 5]   [7]
                // adding 4, so we are merging the branches

                //         [4]
                //    [2]        [6]
                // [1]   [3]   [5]   [7, 8, 9?]
                // adding 9 - no need to merge

                //         [4]
                //    [2]         [6, 8]
                // [1]   [3]   [5]  [7]  [9, 10, 11] 12?
                // adding 12

                // How to find a split !!!
                // 1. The branch was Leaf3
                // 2. The branch was Branch2

                // todo: @incomplete
                var branchSplitOrNot = Branch1.AddOrUpdateEntry(entry);


                var newBranch = Branch1.AddOrUpdateBranch(entry.Key, entry, out var popEntry, out var popRight);
                if (popEntry != null)
                    return new ImMapBranch3<V>(Entry0, Branch0, newBranch, popEntry, popRight);

                return new ImMapBranch2<V>(Entry0, Branch0, newBranch);
            }

            if (entry.Key < Entry0.Key)
            {
                //           [4]                [2]  <-  [4]
                // [1, 2, 3]      [5] =>  [0, 1]    [3]      [5]  =>
                // and adding 0, so we are merging the branches

                var newBranch = Branch0.AddOrUpdateBranch(entry.Key, entry,
                    out var popEntry, out var popRight);

                if (popEntry != null)
                    return new ImMapBranch3<V>(popEntry, newBranch, popRight, Entry0, Branch1);

                return new ImMapBranch2<V>(Entry0, newBranch, Branch1);
            }

            // update
            return new ImMapBranch2<V>(entry, Branch0, Branch1);
        }
    }

    /// <summary>3 branches</summary>
    public sealed class ImMapBranch3<V> : ImMapBranch2<V>
    {
        /// <summary>Right entry</summary>
        public readonly ImMapEntry<V> Entry1;

        /// <summary>Rightmost branch</summary>
        public readonly ImMap<V> Branch2;

        /// <summary>Constructs</summary>
        public ImMapBranch3(ImMapEntry<V> entry0, ImMap<V> branch0, ImMap<V> branch1,
            ImMapEntry<V> entry1, ImMap<V> branch2) : base(entry0, branch0, branch1)
        {
            Entry1 = entry1;
{'fraction_non_alphanumeric': 0.12145396502938402, 'fraction_numerical': 0.025393600812595226, 'mean_word_length': 1.920957830048739, 'pattern_counts': {'":': 2, '<': 263, '<?xml version=': 0, '>': 286, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '404110', 'n_tokens_mistral': 4327, 'n_tokens_neox': 4181, 'n_words': 1120}