<commit_before>﻿using System;

namespace AvsAnLib.Internals {
    /// <summary>
    /// A node the article lookup trie. Do not mutate after construction.
    /// </summary>
    public struct Node : IComparable<Node> {
        public char c;
        public Ratio ratio;
        public Node[] SortedKids;
        public int CompareTo(Node other) { return c.CompareTo(other.c); }

        public static Node CreateFromMutable(MutableNode node, char key = ' ') {
            Node[] sortedKids = null;
            if (node.Kids != null) {
                sortedKids = new Node[node.Kids.Count];
                int i = 0;
                foreach (var kv in node.Kids)
                    sortedKids[i++] = CreateFromMutable(kv.Value, kv.Key);
                Array.Sort(sortedKids);
            }
            return new Node { c = key, ratio = node.ratio, SortedKids = sortedKids };
        }


        public void LoadPrefixRatio(string prefix, int depth, Ratio prefixRatio) {
            if (prefix.Length == depth) {
                ratio = prefixRatio;
            } else {
                int idx;
                char kidC = prefix[depth];
                if (SortedKids == null) {
                    SortedKids = new[] { new Node { c = kidC, } };
                    idx = 0;
                } else {
                    var nearestIdx = FindNearestNode(kidC);
                    idx = nearestIdx;
                    if (SortedKids[nearestIdx].c != kidC) {
                        if (SortedKids[nearestIdx].c < kidC) {
                            idx = nearestIdx + 1;
                        }
                        InsertBefore(idx, kidC);
                    }
                }
                SortedKids[idx].LoadPrefixRatio(prefix, depth + 1, prefixRatio);
            }
        }

        int FindNearestNode(char c) {
            int start = 0, end = SortedKids.Length;
            while (end - start > 1) {
                int midpoint = end + start >> 1;
                if (SortedKids[midpoint].c <= c) {
                    start = midpoint;
                } else {
                    end = midpoint;
                }
            }
            return start;
        }

        void InsertBefore(int idx, char c) {
            var newArr = new Node[SortedKids.Length + 1];
            int i = 0;
            for (; i < idx; i++) {
                newArr[i] = SortedKids[i];
            }
            newArr[idx].c = c;
            for (; i < SortedKids.Length; i++) {
                newArr[i + 1] = SortedKids[i];
            }
            SortedKids = newArr;
        }
    }
}<commit_msg>Improve Node's binary search, add comments about invariants.<commit_after>﻿using System;

namespace AvsAnLib.Internals {
    /// <summary>
    /// A node the article lookup trie. Do not mutate after construction.
    /// </summary>
    public struct Node : IComparable<Node> {
        public char c;
        public Ratio ratio;
        public Node[] SortedKids;
        public int CompareTo(Node other) { return c.CompareTo(other.c); }

        public static Node CreateFromMutable(MutableNode node, char key = ' ') {
            Node[] sortedKids = null;
            if (node.Kids != null) {
                sortedKids = new Node[node.Kids.Count];
                int i = 0;
                foreach (var kv in node.Kids)
                    sortedKids[i++] = CreateFromMutable(kv.Value, kv.Key);
                Array.Sort(sortedKids);
            }
            return new Node { c = key, ratio = node.ratio, SortedKids = sortedKids };
        }


        public void LoadPrefixRatio(string prefix, int depth, Ratio prefixRatio) {
            if (prefix.Length == depth) {
                ratio = prefixRatio;
            } else {
                char kidC = prefix[depth];
                var idx = GetOrAddKidIdx(kidC);
                SortedKids[idx].LoadPrefixRatio(prefix, depth + 1, prefixRatio);
            }
        }

        public int GetOrAddKidIdx(char kidC) {
            if (SortedKids == null) {
                SortedKids = new[] { new Node { c = kidC, } };
                return 0;
            } else {
                int idx = IdxAfterLastLtNode(kidC);

                if (idx == SortedKids.Length || SortedKids[idx].c != kidC)
                    InsertBefore(idx, kidC);
                return idx;
            }
        }

        int IdxAfterLastLtNode(char needle) {
            int start = 0, end = SortedKids.Length;
            //invariant: only LT nodes before start
            //invariant: only GTE nodes at or past end

            while (end != start) {
                int midpoint = end + start >> 1;
                // start <= midpoint < end
                if (SortedKids[midpoint].c < needle) {
                    start = midpoint + 1;//i.e.  midpoint < start1 so start0 < start1
                } else {
                    end = midpoint;//i.e end1 = midpoint so end1 < end0
                }
            }
            return end;
        }

        void InsertBefore(int idx, char c) {
            var newArr = new Node[SortedKids.Length + 1];
            int i = 0;
            for (; i < idx; i++) {
                newArr[i] = SortedKids[i];
            }
            newArr[idx].c = c;
            for (; i < SortedKids.Length; i++) {
                newArr[i + 1] = SortedKids[i];
            }
            SortedKids = newArr;
        }
    }
}
{'fraction_non_alphanumeric': 0.10240295748613679, 'fraction_numerical': 0.0046210720887245845, 'mean_word_length': 1.2545833333333334, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '354681', 'n_tokens_mistral': 1584, 'n_tokens_neox': 1475, 'n_words': 397}