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() { } } } }