<commit_before>﻿// <copyright file="SuffixTree.cs" company="Public Domain">
//     Copyright (c) 2018 <NAME>.
// </copyright>

/*
A suffix tree based on Ukkonen's algorithm for byte values. I followed the ideas based in this helpful article:
http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english/9513423#9513423

The code written here is based on a C++ implementation given here:
http://pastie.org/5925809

A note on memory management:
Try creating as few new suffix tree classes as possible. Every time a new node is created, it has to initialize an array of child nodes of size equal to the alphabet size (257). For large sets of data, this operation becomes expensive and time-consuming. To counter the performance hit, the SuffixTree class can be reused. The class keeps a list of every used node. When the class is reset to implement a new tree structure, it simply erases all of the nodes information and reference data without letting the class itself be erased from memory. This way, the next tree creation (if another one will be made) does not lose time on allocating new memory. The performance gains are very significant.
*/

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Helper
{
    public class SuffixTree
    {
        public const int TerminationValue = AlphabetSize;
        public const int AlphabetSize = Byte.MaxValue + 1;
        private const int EndOfData = SubstringPointer.EndOfString;

        private const int FallbakNodeCollectionSize = 0x1000;

        private RootNode Root
        {
            get;
            set;
        }

        private NodeCollection Nodes
        {
            get;
            set;
        }

        private int Position
        {
            get;
            set;
        }

        private Node ActiveLinkNode
        {
            get;
            set;
        }

        private int Remainder
        {
            get;
            set;
        }

        private Node ActiveNode
        {
            get;
            set;
        }

        private int ActivePosition
        {
            get;
            set;
        }

        private int ActiveLength
        {
            get;
            set;
        }

        private int[] Data
        {
            get;
            set;
        }

        public int this[int index]
        {
            get
            {
                return Data[index];
            }
        }

        public int Size
        {
            get;
            private set;
        }

        public SuffixTree()
        {
            // Create a large node collection now to save time in the future.
            Nodes = new NodeCollection(this, FallbakNodeCollectionSize);

            Root = new RootNode(this);
        }

        private void Initialize(int size)
        {
            if (size < 0)
            {
                throw new ArgumentOutOfRangeException(
                    nameof(size),
                    SR.ErrorLowerBoundExclusive(nameof(size), size, 0));
            }

            Nodes.Clear();

            size++;                 // +1 for the termination value.
            Data = new int[size];
            Size = size;

            Position = -1;
            Remainder = 0;
            ActiveLength = 0;
            ActivePosition = 0;

            Root.Reset();
            ActiveNode = Root;
        }

        public void CreateTree(byte[] data)
        {
            if (data is null)
            {
                throw new ArgumentNullException(nameof(data));
            }

            CreateTree(data, 0, data.Length);
        }

        public void CreateTree(byte[] data, int start, int size)
        {
            if (data is null)
            {
                throw new ArgumentNullException(nameof(data));
            }

            unsafe
            {
                fixed (byte* ptr = data)
                    CreateTree(ptr, data.Length, start, size);
            }
        }

        public void CreateTree(IntPtr data, int length)
        {
            unsafe
            {
                CreateTree((byte*)data, length, 0, length);
            }
        }

        public void CreateTree(IntPtr data, int length, int start, int size)
        {
            unsafe
            {
                CreateTree((byte*)data, length, start, size);
            }
        }

        private unsafe void CreateTree(byte* data, int length, int start, int size)
        {
            if (data is null)
            {
                throw new ArgumentNullException(nameof(data));
            }

            if (start < 0)
            {
                throw new ArgumentOutOfRangeException(
                    nameof(start),
                    SR.ErrorLowerBoundExclusive(nameof(start), start, 0));
            }

            if (start + size > length)
            {
                throw new ArgumentOutOfRangeException(
                    nameof(size),
                    SR.ErrorArrayRange(nameof(size), size, nameof(data), length, start));
            }

            Initialize(size);

            data += start;
            for (var i = 0; i < size; i++)
            {
                Add(data[i]);
            }

            Add(TerminationValue);
            Position++;
        }
<commit_msg>Update SuffixTree.CreateTree methods<commit_after>﻿// <copyright file="SuffixTree.cs" company="Public Domain">
//     Copyright (c) 2018 <NAME>.
// </copyright>

/*
A suffix tree based on Ukkonen's algorithm for byte values. I followed the ideas based in this helpful article:
http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english/9513423#9513423

The code written here is based on a C++ implementation given here:
http://pastie.org/5925809

A note on memory management:
Try creating as few new suffix tree classes as possible. Every time a new node is created, it has to initialize an array of child nodes of size equal to the alphabet size (257). For large sets of data, this operation becomes expensive and time-consuming. To counter the performance hit, the SuffixTree class can be reused. The class keeps a list of every used node. When the class is reset to implement a new tree structure, it simply erases all of the nodes information and reference data without letting the class itself be erased from memory. This way, the next tree creation (if another one will be made) does not lose time on allocating new memory. The performance gains are very significant.
*/

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Helper
{
    public class SuffixTree
    {
        public const int TerminationValue = AlphabetSize;
        public const int AlphabetSize = Byte.MaxValue + 1;
        private const int EndOfData = SubstringPointer.EndOfString;

        private const int FallbakNodeCollectionSize = 0x1000;

        private RootNode Root
        {
            get;
            set;
        }

        private NodeCollection Nodes
        {
            get;
            set;
        }

        private int Position
        {
            get;
            set;
        }

        private Node ActiveLinkNode
        {
            get;
            set;
        }

        private int Remainder
        {
            get;
            set;
        }

        private Node ActiveNode
        {
            get;
            set;
        }

        private int ActivePosition
        {
            get;
            set;
        }

        private int ActiveLength
        {
            get;
            set;
        }

        private int[] Data
        {
            get;
            set;
        }

        public int this[int index]
        {
            get
            {
                return Data[index];
            }
        }

        public int Size
        {
            get;
            private set;
        }

        public SuffixTree()
        {
            // Create a large node collection now to save time in the future.
            Nodes = new NodeCollection(this, FallbakNodeCollectionSize);

            Root = new RootNode(this);
        }

        private void Initialize(int size)
        {
            if (size < 0)
            {
                throw new ArgumentOutOfRangeException(
                    nameof(size),
                    SR.ErrorLowerBoundExclusive(nameof(size), size, 0));
            }

            Nodes.Clear();

            size++;                 // +1 for the termination value.
            Data = new int[size];
            Size = size;

            Position = -1;
            Remainder = 0;
            ActiveLength = 0;
            ActivePosition = 0;

            Root.Reset();
            ActiveNode = Root;
        }

        public void CreateTree(byte[] data)
        {
            if (data is null)
            {
                throw new ArgumentNullException(nameof(data));
            }

            CreateTree(data, 0, data.Length);
        }

        public void CreateTree(byte[] data, int start, int size)
        {
            if (data is null)
            {
                throw new ArgumentNullException(nameof(data));
            }

            unsafe
            {
                fixed (byte* ptr = data)
                    CreateTree(ptr, data.Length, start, size);
            }
        }

        public void CreateTree(IntPtr data, int length)
        {
            CreateTree(data, length, 0, length);
        }

        public void CreateTree(IntPtr data, int length, int start, int size)
        {
            if (data == IntPtr.Zero)
            {
                throw new ArgumentNullException(nameof(data));
            }

            unsafe
            {
                CreateTree((byte*)data, length, start, size);
            }
        }

        private unsafe void CreateTree(byte* data, int length, int start, int size)
        {
            if (start < 0)
            {
                throw new ArgumentOutOfRangeException(
                    nameof(start),
                    SR.ErrorLowerBoundExclusive(nameof(start), start, 0));
            }

            if (start + size > length)
            {
                throw new ArgumentOutOfRangeException(
                    nameof(size),
                    SR.ErrorArrayRange(nameof(size), size, nameof(data), length, start));
            }

            Initialize(size);

            data += start;
            for (var i = 0; i < size; i++)
            {
                Add(data[i]);
            }

            Add(TerminationValue);
            Position++;
        }

{'fraction_non_alphanumeric': 0.07268099547511313, 'fraction_numerical': 0.009992458521870286, 'mean_word_length': 1.3492028343666962, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 11, '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': '2610167', 'n_tokens_mistral': 2731, 'n_tokens_neox': 2541, 'n_words': 872}