using System;
using System.Collections.Generic;

namespace Myc
{
    public enum PointType { Peak, Trough }

    public struct ExtremumPoint
    {
        public double Price; 
        public int Index;
        public PointType Type;
    }

    public struct ClusterZone
    {
        public double Price;
        public double Score;
    }

    /// <summary>
    /// Hochoptimierte Engine. Hält den State im Speicher, um GC-Allocations zu vermeiden.
    /// Nutzt eine permanent preis-sortierte Liste für extrem schnelle Range-Abfragen.
    /// </summary>
    public class ClusterCalculator
    {
        // Permanente Buffer verhindern "new List<>" Zuweisungen pro Tick
        private readonly List<ExtremumPoint> _priceSortedPoints; 
        private readonly List<ClusterZone> _candidatesBuffer;
        private readonly List<ClusterZone> _resultsBuffer;
        
        private readonly CandidateComparer _candidateComparer = new CandidateComparer();
        
        // Status für effizientes Aufräumen (Pruning)
        private int _lastPruneIndex = 0;
        private const int PruneInterval = 100; // Nur alle 100 Bars aufräumen spart CPU

        public ClusterCalculator(int capacity = 2000)
        {
            _priceSortedPoints = new List<ExtremumPoint>(capacity);
            _candidatesBuffer = new List<ClusterZone>(capacity);
            _resultsBuffer = new List<ClusterZone>(100);
        }

        /// <summary>
        /// Fügt einen Punkt via BinarySearch ein, um die Sortierung beizubehalten (O(log N)).
        /// </summary>
        public void AddPoint(ExtremumPoint point)
        {
            int low = 0;
            int high = _priceSortedPoints.Count - 1;

            while (low <= high)
            {
                int mid = low + (high - low) / 2;
                if (_priceSortedPoints[mid].Price < point.Price)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            
            _priceSortedPoints.Insert(low, point);
        }

        /// <summary>
        /// Entfernt alte Punkte. Nutzt einen effizienten "Swap-and-Cut" Algorithmus (O(N)),
        /// statt langsamem RemoveAt in einer Schleife (O(N^2)).
        /// </summary>
        private void PruneOldPoints(int currentIndex, int decayPeriod)
        {
            int cutoffIndex = currentIndex - decayPeriod;
            int writeIndex = 0;

            // In-Place Filterung (vermeidet Array-Copies)
            for (int i = 0; i < _priceSortedPoints.Count; i++)
            {
                if (_priceSortedPoints[i].Index >= cutoffIndex)
                {
                    _priceSortedPoints[writeIndex] = _priceSortedPoints[i];
                    writeIndex++;
                }
            }

            // Den Rest der Liste abschneiden
            if (writeIndex < _priceSortedPoints.Count)
            {
                _priceSortedPoints.RemoveRange(writeIndex, _priceSortedPoints.Count - writeIndex);
            }
        }

        public (List<ClusterZone> Zones, double TotalWeight) Calculate(
            int currentIndex,
            double currentPrice,
            double range,
            int decayPeriod,
            int maxZones)
        {
            // 1. Internes Auto-Pruning (gedrosselt)
            if (currentIndex - _lastPruneIndex >= PruneInterval)
            {
                PruneOldPoints(currentIndex, decayPeriod);
                _lastPruneIndex = currentIndex;
            }

            _candidatesBuffer.Clear();
            _resultsBuffer.Clear();
            
            int count = _priceSortedPoints.Count;
            if (count < 2) return (_resultsBuffer, 0.0);

            double totalWeightSum = 0.0;
            
            // 2. Sliding Window auf der sortierten Liste
            // Da die Liste nach Preis sortiert ist, können wir Fenster [Center-Range, Center+Range] effizient finden.
            int left = 0;
            int right = 0;
            
            for (int i = 0; i < count; i++)
            {
                var centerPt = _priceSortedPoints[i];
                double centerWeight = GetWeight(centerPt, currentIndex, currentPrice, decayPeriod);
                
                // Tote Punkte ignorieren (Micro-Optimierung)
                if (centerWeight <= 0.001) continue;
                
                totalWeightSum += centerWeight;

                double minPrice = centerPt.Price - range;
                double maxPrice = centerPt.Price + range;

                // Fenster nach rechts erweitern
                while (right < count && _priceSortedPoints[right].Price <= maxPrice)
                {
                    right++;
                }
                
                // Fenster von links verkleinern
                while (left < right && _priceSortedPoints[left].Price < minPrice)
                {
                    left++;
                }

                // Gewichtung im Fenster summieren
                double localScore = 0;
                for (int k = left; k < right; k++)
                {
                    localScore += GetWeight(_priceSortedPoints[k], currentIndex, currentPrice, decayPeriod);
                }

                if (localScore > 0.01)
                {
                    _candidatesBuffer.Add(new ClusterZone 
                    { 
                        Price = centerPt.Price, 
                        Score = localScore 
                    });
                }
            }

            // 3. Kandidaten sortieren (Allocation Free via Comparer)
            _candidatesBuffer.Sort(_candidateComparer);

            // 4. Überlappungen filtern
            int candCount = _candidatesBuffer.Count;
            for (int i = 0; i < candCount; i++)
            {
                if (_resultsBuffer.Count >= maxZones) break;

                var cand = _candidatesBuffer[i];
                bool overlaps = false;
                
                int resCount = _resultsBuffer.Count;
                for (int j = 0; j < resCount; j++)
                {
                    if (Math.Abs(_resultsBuffer[j].Price - cand.Price) < range)
                    {
                        overlaps = true;
                        break;
                    }
                }

                if (!overlaps)
                {
                    _resultsBuffer.Add(cand);
                }
            }

            return (_resultsBuffer, totalWeightSum);
        }

        private double GetWeight(ExtremumPoint p, int currentIndex, double currentPrice, int decayPeriod)
        {
            double age = currentIndex - p.Index;
            if (age > decayPeriod) return 0.0;
            
            double w = 1.0 - (age / decayPeriod);
            if (w < 0) return 0.0;

            // Role Reversal Logic
            if ((p.Type == PointType.Peak && p.Price < currentPrice) ||
                (p.Type == PointType.Trough && p.Price > currentPrice))
            {
                w *= 2.0;
            }
            return w;
        }

        private class CandidateComparer : IComparer<ClusterZone>
        {
            public int Compare(ClusterZone x, ClusterZone y) => y.Score.CompareTo(x.Score);
        }
    }
}