<commit_before>﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Bearded.Utilities.Linq;

namespace Bearded.Utilities.Collections
{
    /// <summary>
    /// An immutable prefix trie, useful for extending prefixes and getting all strings with a given prefix.
    /// </summary>
    sealed public class PrefixTrie : ICollection<string>
    {
        private struct Node
        {
            private readonly Dictionary<char, Node> values;
            private readonly string key;

            public string Key { get { return this.key; } }

            #region creating

            // expects and requires sorted list of unique strings
            public Node(List<string> values)
                : this(values, 0, 0, values.Count)
            {

            }

            private Node(List<string> values, int index, int iMin, int iMax)
                : this()
            {
                var s = values[iMin];

                if (s.Length == index)
                {
                    this.key = s;
                    iMin++;
                }

                this.values = makeChildren(values, index, iMin, iMax);
            }

            private static Dictionary<char, Node> makeChildren(List<string> values, int index, int iMin, int iMax)
            {
                if (iMin >= iMax)
                    return null;

                var dict = new Dictionary<char, Node>(iMax - iMin);

                int index2 = index + 1;

                char c = values[iMin][index];
                for (int i = iMin + 1; i < iMax; i++)
                {
                    var c2 = values[i][index];
                    if (c2 != c)
                    {
                        dict.Add(c, new Node(values, index2, iMin, i));
                        iMin = i;
                        c = c2;
                    }
                }
                dict.Add(c, new Node(values, index2, iMin, iMax));

                return dict;<commit_msg>removed space estimate from prefix trie dictionary allocation, closes #52<commit_after>﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Bearded.Utilities.Linq;

namespace Bearded.Utilities.Collections
{
    /// <summary>
    /// An immutable prefix trie, useful for extending prefixes and getting all strings with a given prefix.
    /// </summary>
    sealed public class PrefixTrie : ICollection<string>
    {
        private struct Node
        {
            private readonly Dictionary<char, Node> values;
            private readonly string key;

            public string Key { get { return this.key; } }

            #region creating

            // expects and requires sorted list of unique strings
            public Node(List<string> values)
                : this(values, 0, 0, values.Count)
            {

            }

            private Node(List<string> values, int index, int iMin, int iMax)
                : this()
            {
                var s = values[iMin];

                if (s.Length == index)
                {
                    this.key = s;
                    iMin++;
                }

                this.values = makeChildren(values, index, iMin, iMax);
            }

            private static Dictionary<char, Node> makeChildren(List<string> values, int index, int iMin, int iMax)
            {
                if (iMin >= iMax)
                    return null;

                var dict = new Dictionary<char, Node>();

                int index2 = index + 1;

                char c = values[iMin][index];
                for (int i = iMin + 1; i < iMax; i++)
                {
                    var c2 = values[i][index];
                    if (c2 != c)
                    {
                        dict.Add(c, new Node(values, index2, iMin, i));
                        iMin = i;
                        c = c2;
                    }
                }
                dict.Add(c, new Node(values, index2, iMin, iMax));

                return dict;
{'fraction_non_alphanumeric': 0.09104222601903832, 'fraction_numerical': 0.005369782767878936, 'mean_word_length': 1.2628382109331862, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 23, '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': '4096358', 'n_tokens_mistral': 1083, 'n_tokens_neox': 1006, 'n_words': 323}