<commit_before>﻿namespace Buddhabrot.Core.Boundary.RegionQuadTree;

public sealed class RegionMap2 : IRegionMap
{
    private readonly List<Quad> _nodes = new();
    private readonly Quad _top;
    private readonly ComplexArea _topLevelArea = new(new Range(-2, 2), new Range(0, 4));

    public static readonly RegionMap2 Empty = new();
    public ComplexArea PopulatedArea { get; }

    private RegionMap2()
    {
        PopulatedArea = ComplexArea.Empty;
    }

    public RegionMap2(
        int verticalPower,
        IReadOnlyList<RegionId> regions,
        Action<string>? log = default)
    {
        QuadCache cache = new(_nodes);

        HashSet<RegionId> regionLookup = new(regions.Count);

        Quad LookupLocation(int x, int y) =>
            regionLookup.Contains(new RegionId(x, y)) ? Quad.Border : Quad.Empty;

        int maxX = 0;
        int maxY = 0;
        foreach (var region in regions)
        {
            regionLookup.Add(region);
            maxX = Math.Max(maxX, region.X);
            maxY = Math.Max(maxY, region.Y);
        }

        var sideLength = 2.0 / (1 << verticalPower);
        PopulatedArea = new ComplexArea(
            Range.FromMinAndLength(-2, (maxX + 1) * sideLength),
            new Range(0, (maxY + 1) * sideLength));

        Quad BuildQuad(int level, int xOffset, int yOffset)
        {
            if (level == 0)
            {
                return cache.MakeQuad(
                    sw: LookupLocation(xOffset, yOffset),
                    se: LookupLocation(xOffset + 1, yOffset),
                    ne: LookupLocation(xOffset + 1, yOffset + 1),
                    nw: LookupLocation(xOffset, yOffset + 1));
            }

            var levelWidth = 1 << level;

            return cache.MakeQuad(
                sw: BuildQuad(level - 1, xOffset, yOffset),
                se: BuildQuad(level - 1, xOffset + levelWidth, yOffset),
                ne: BuildQuad(level - 1, xOffset + levelWidth, yOffset + levelWidth),
                nw: BuildQuad(level - 1, xOffset, yOffset + levelWidth));
        }

        var topLevelWidth = 1 << verticalPower;
        _top = cache.MakeQuad(
            nw: Quad.Empty,
            ne: Quad.Empty,
            sw: BuildQuad(verticalPower - 1, 0, 0),
            se: BuildQuad(verticalPower - 1, topLevelWidth, 0));
        log?.Invoke($"Cache size: {cache.Size:N0}, num times cached value used: {cache.NumCachedValuesUsed:N0}");
    }

    public IReadOnlyList<ComplexArea> GetVisibleAreas(ComplexArea searchArea)
    {
        return Array.Empty<ComplexArea>();
    }

    sealed class QuadCache
    {
        private readonly List<Quad> _nodes;
        private readonly Dictionary<int, int> _dict = new();

        public QuadCache(List<Quad> nodes) => _nodes = nodes;

        public int Size => _dict.Count;
        public int NumCachedValuesUsed { get; private set; }

        public Quad MakeQuad(Quad nw, Quad ne, Quad se, Quad sw)
        {
            if (nw == ne &&
                ne == se &&
                se == sw)
            {
                if (nw == Quad.Empty)
                    return Quad.Empty;

                if (nw == Quad.Border)
                    return Quad.Border;

                if (nw == Quad.Filament)
                    return Quad.Filament;
            }

            var key = HashCode.Combine(nw, ne, se, sw);
            if (!_dict.TryGetValue(key, out var index))
            {
                index = _nodes.Count;
                _nodes.Add(new Quad(index));
                _nodes.Add(nw);
                _nodes.Add(ne);
                _nodes.Add(se);
                _nodes.Add(sw);
                
                _dict.Add(key, index);
            }
            else
            {
                NumCachedValuesUsed++;
            }

            return _nodes[index];
        }
    }

    readonly record struct Quad(int ChildIndex)
    {
        public static readonly Quad Empty = new(-1);
        public static readonly Quad Border = new(-2);
        public static readonly Quad Filament = new(-3);

        public QuadType Type => ChildIndex switch
        {
            -1 => QuadType.Empty,
            -2 => QuadType.Border,
            -3 => QuadType.Filament,
            _ => QuadType.Mixed
        };
    }
}<commit_msg>WIP on building new tree; utterly broken<commit_after>﻿namespace Buddhabrot.Core.Boundary.RegionQuadTree;

public sealed class RegionMap2 : IRegionMap
{
    private readonly List<Quad> _nodes = new() {Quad.Empty};

    private readonly ComplexArea _topLevelArea = new(
        new Range(-2, 2),
        new Range(0, 4));

    private enum Quadrant
    {
        SouthWest,
        SouthEast,
        NorthEast,
        NorthWest,
    }

    public static readonly RegionMap2 Empty = new();
    public ComplexArea PopulatedArea { get; }

    private RegionMap2()
    {
        PopulatedArea = ComplexArea.Empty;
    }

    public RegionMap2(
        int verticalPower,
        IReadOnlyList<RegionId> regions,
        Action<string>? log = default)
    {
        int maxX = 0;
        int maxY = 0;

        // TODO: This is awful. Write an insert method and test it, then use that in the constructor
        
        foreach (var region in regions)
        {
            maxX = Math.Max(maxX, region.X);
            maxY = Math.Max(maxY, region.Y);

            var quadIndex = 0;
            var quad = _nodes[quadIndex];

            int xOffset = 0;
            int yOffset = 0;
            for (int level = verticalPower; level >= 0; level--)
            {
                if (quad.Type == QuadType.Empty)
                {
                    int index = _nodes.Count;
                    _nodes.Add(Quad.Empty);
                    _nodes.Add(Quad.Empty);
                    _nodes.Add(Quad.Empty);
                    _nodes.Add(Quad.Empty);
                    quad = new Quad(index);
                    _nodes[quadIndex] = quad;
                }

                // figure out which quadrant it's in
                var halfWidth = 1 << level;
                var xSmall = region.X < (xOffset + halfWidth);
                var ySmall = region.Y < (yOffset + halfWidth);
                var quadrant = (xSmall, ySmall) switch
                {
                    (true, true) => Quadrant.SouthWest,
                    (false, true) => Quadrant.SouthEast,
                    (true, false) => Quadrant.NorthWest,
                    (false, false) => Quadrant.NorthEast,
                };

                switch (quadrant)
                {
                    case Quadrant.NorthEast:
                        xOffset += halfWidth;
                        yOffset += halfWidth;
                        break;
                    case Quadrant.SouthWest:
                        xOffset += halfWidth;
                        break;
                    case Quadrant.NorthWest:
                        yOffset += halfWidth;
                        break;
                    case Quadrant.SouthEast:
                        break;
                }
                quadIndex = quad.GetQuadrantIndex(quadrant);
                quad = _nodes[quadIndex];
            }

            _nodes[quadIndex] = Quad.Border;
        }

        var sideLength = 2.0 / (1 << verticalPower);
        PopulatedArea = new ComplexArea(
            Range.FromMinAndLength(-2, (maxX + 1) * sideLength),
            new Range(0, (maxY + 1) * sideLength));

        log?.Invoke($"Quad tree nodes: {_nodes.Count:N0}");
    }

    public IReadOnlyList<ComplexArea> GetVisibleAreas(ComplexArea searchArea)
    {
        var visibleAreas = new List<ComplexArea>();

        var toCheck = new Queue<(ComplexArea, Quad)>();
        toCheck.Enqueue((_topLevelArea, _nodes[0]));

        while (toCheck.Any())
        {
            var (quadArea, currentQuad) = toCheck.Dequeue();

            if (currentQuad != Quad.Empty &&
                searchArea.OverlapsWith(quadArea))
            {
                if (currentQuad == Quad.Border)
                {
                    visibleAreas.Add(quadArea.Intersect(searchArea));
                }
                else
                {
                    toCheck.Enqueue(
                        (quadArea.GetNWQuadrant(), _nodes[currentQuad.GetQuadrantIndex(Quadrant.NorthWest)]));
                    toCheck.Enqueue(
                        (quadArea.GetNEQuadrant(), _nodes[currentQuad.GetQuadrantIndex(Quadrant.NorthEast)]));
                    toCheck.Enqueue(
                        (quadArea.GetSEQuadrant(), _nodes[currentQuad.GetQuadrantIndex(Quadrant.SouthEast)]));
                    toCheck.Enqueue(
                        (quadArea.GetSWQuadrant(), _nodes[currentQuad.GetQuadrantIndex(Quadrant.SouthWest)]));
                }
            }
        }

        return visibleAreas;
    }

    sealed class QuadCache
    {
        private readonly List<Quad> _nodes;
        private readonly Dictionary<int, int> _dict = new();

        public QuadCache(List<Quad> nodes) => _nodes = nodes;

        public int Size => _dict.Count;
        public int NumCachedValuesUsed { get; private set; }

        public Quad MakeQuad(Quad nw, Quad ne, Quad se, Quad sw)
        {
            if (nw == ne &&
                ne == se &&
                se == sw)
            {
                if (nw == Quad.Empty)
                    return Quad.Empty;

                if (nw == Quad.Border)
                    return Quad.Border;

                if (nw == Quad.Filament)
                    return Quad.Filament;
            }

            var key = HashCode.Combine(nw, ne, se, sw);
            if (!_dict.TryGetValue(key, out var index))
            {
                index = _nodes.Count;
                _nodes.Add(new Quad(index));
                _nodes.Add(nw);
                _nodes.Add(ne);
                _nodes.Add(se);
                _nodes.Add(sw);

                _dict.Add(key, index);
            }
            else
            {
                NumCachedValuesUsed++;
            }

            return _nodes[index];
        }
    }

    readonly record struct Quad(int ChildIndex)
    {
        public static readonly Quad Empty = new(-1);
        public static readonly Quad Border = new(-2);
        public static readonly Quad Filament = new(-3);

        public QuadType Type => ChildIndex switch
        {
            -1 => QuadType.Empty,
            -2 => QuadType.Border,
            -3 => QuadType.Filament,
            _ => QuadType.Mixed
        };

        public int GetQuadrantIndex(Quadrant child) => ChildIndex + (int) child;
    }
}
{'fraction_non_alphanumeric': 0.09868049010367577, 'fraction_numerical': 0.006691800188501414, 'mean_word_length': 1.4110429447852761, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 42, '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': '6269137', 'n_tokens_mistral': 3097, 'n_tokens_neox': 2812, 'n_words': 698}