source: branches/3057_DynamicALPS/TestProblems/oesr-alps-master/HeuristicLab.Algorithms.OESRALPS/DriftDetection/Histogram.cs @ 17717

using HEAL.Attic;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HeuristicLab.Algorithms.OESRALPS.DriftDetection
{
    [StorableType("714AE0E4-A88F-44A1-A2D0-92F418252C04")]
    public class Histogram : IEnumerable<Bucket>
    {
        [Storable]
        public int MaxBucketsPerBucketContainer { get; }
        [Storable]
        public int NumBucketContainers { get; set; }
        [Storable]
        public int NumBuckets { get; set; }
        [Storable]
        public int NumElements { get; set; }
        [Storable]
        public double Total { get; set; }
        [Storable]
        public double Variance { get; set; }
        [Storable]
        internal BucketContainer Tail { get; set; }
        [Storable]
        internal BucketContainer Head { get; set; }

        public Histogram() { }

        /**
         * Creates a new empty Histogram
         * @param maxBucketsPerBucketContainer max number of Buckets in one bucket container. default is 5
         */
        public Histogram(int maxBucketsPerBucketContainer)
        {
            if (maxBucketsPerBucketContainer < 2)
            {
                throw new Exception("maxBucketsPerBucketContainer must be at least 2.");
            }

            Head = new BucketContainer(null, null, maxBucketsPerBucketContainer, 1);
            Tail = Head;
            NumBucketContainers = 1;
            MaxBucketsPerBucketContainer = maxBucketsPerBucketContainer;
        }

        // TODO Evaluate
        private Histogram(Histogram original)
        {
            MaxBucketsPerBucketContainer = original.MaxBucketsPerBucketContainer;

            NumBucketContainers = original.NumBucketContainers;
            NumBuckets = original.NumBuckets;
            NumElements = original.NumElements;

            Total = original.Total;
            Variance = original.Variance;

            Head = original.Head.DeepCopy();
            BucketContainer currentBucketContainer = Head;
            while (currentBucketContainer.Next != null)
            {
                currentBucketContainer = currentBucketContainer.Next;
            }
            Tail = currentBucketContainer;
        }

        public void AddElement(double element)
        {
            Bucket newBucket = new Bucket(element, 0, 1);
            Head.AddBucket(newBucket);
            NumBuckets++;
            NumElements++;
            if (NumElements > 1)
            {
                Variance += (NumElements - 1) * Math.Pow(element - Total / (NumElements - 1), 2) / NumElements;
            }
            Total += element;
            Compress();
        }

        private void AddEmptyTailBucketContainer()
        {
            BucketContainer newTail = new BucketContainer(Tail, null, MaxBucketsPerBucketContainer, Tail.NumElementsPerBucket * 2);
            Tail.Next = newTail;
            Tail = newTail;
            NumBucketContainers++;
        }

        private void Compress()
        {
            BucketContainer pointer = Head;
            while (pointer != null)
            {
                if (pointer.NumBuckets == pointer.MaxBuckets)
                {
                    if (pointer.Next == null)
                    {
                        AddEmptyTailBucketContainer();
                    }
                    Bucket[] removedBuckets = pointer.RemoveBuckets(2);
                    Bucket newBucket = CompressBuckets(removedBuckets[0], removedBuckets[1]);
                    pointer.Next.AddBucket(newBucket);
                    NumBuckets -= 1;
                }
                pointer = pointer.Next;
            }
        }

        private Bucket CompressBuckets(Bucket firstBucket, Bucket secondBucket)
        {
            if (firstBucket.NumElements != secondBucket.NumElements)
                throw new Exception("Number of buckets unequal.");

            int elementsPerBucket = firstBucket.NumElements;
            double newTotal = firstBucket.Total + secondBucket.Total;
            double varianceIncrease = Math.Pow(firstBucket.Total - secondBucket.Total, 2) / (2 * elementsPerBucket);
            double newVariance = firstBucket.Variance + secondBucket.Variance + varianceIncrease;
            return new Bucket(newTotal, newVariance, 2 * elementsPerBucket);
        }

        public void RemoveBuckets(int num)
        {
            while (num > 0)
            {
                Bucket[] removedBuckets;
                if (num >= Tail.NumBuckets)
                {
                    num -= Tail.NumBuckets;
                    removedBuckets = Tail.RemoveBuckets(Tail.NumBuckets);
                    Tail = Tail.Prev;
                    Tail.Next = null;
                    NumBucketContainers--;
                }
                else
                {
                    removedBuckets = Tail.RemoveBuckets(num);
                    num = 0;
                }
                foreach (Bucket bucket in removedBuckets)
                {
                    NumElements -= bucket.NumElements;
                    NumBuckets--;
                    Total -= bucket.Total;
                    Variance -= bucket.Variance + bucket.NumElements * NumElements * Math.Pow(bucket.Mean - Total / NumElements, 2) / (bucket.NumElements + NumElements);
                }
            }
        }

        public Histogram copy()
        {
            return new Histogram(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<Bucket> GetEnumerator()
        {
            return new HistogramReverseEnumerator<Bucket>(this);
        }

        private class HistogramReverseEnumerator<T> : IEnumerator<Bucket>
        {
            private BucketContainer currentBucketContainer;
            private int currentBucketIndex;

            public HistogramReverseEnumerator(Histogram histogram)
            {
                currentBucketContainer = histogram.Tail;
                currentBucketIndex = histogram.Tail.NumBuckets;
            }

            public Bucket Current => currentBucketContainer.GetBucket(currentBucketIndex);

            object IEnumerator.Current => Current;

            public void Dispose()
            {
            }

            private bool HasNext()
            {
                return (currentBucketIndex > 0) || (currentBucketContainer.Prev != null);
            }

            public bool MoveNext()
            {
                if (!HasNext())
                    return false;

                currentBucketIndex--;
                if (currentBucketIndex < 0)
                {
                    currentBucketContainer = currentBucketContainer.Prev;
                    currentBucketIndex = currentBucketContainer.NumBuckets - 1;
                }
                return true;
            }

            public void Reset()
            {
            }
        }

        private class HistogramEnumerator<T> : IEnumerator<Bucket>
        {
            private Histogram histogram;
            private BucketContainer currentBucketContainer;
            private int currentBucketIndex;

            public HistogramEnumerator(Histogram histogram)
            {
                this.histogram = histogram;
                currentBucketContainer = histogram.Head;
                currentBucketIndex = -1;
            }

            public Bucket Current => currentBucketContainer.GetBucket(currentBucketIndex);

            object IEnumerator.Current => Current;

            public void Dispose()
            {
            }

            private bool HasNext()
            {
                return (currentBucketIndex < currentBucketContainer.NumBuckets - 1) || (currentBucketContainer.Next != null);
            }

            public bool MoveNext()
            {
                if (!HasNext())
                    return false;

                currentBucketIndex++;
                if (currentBucketIndex > currentBucketContainer.NumBuckets - 1)
                {
                    currentBucketContainer = currentBucketContainer.Next;
                    currentBucketIndex = 0;
                }

                return true;
            }

            public void Reset()
            {
            }
        }
    }
}