Generic container similar supporting PeekMax, PeekMin, Sum, and PeekNextToMax

Question

I needed to implement a data structure that supports the following operations:

• create from an existing collection
• get the maximum item ("Alpha")
• get the nearest-to-maximum item ("Beta")
• get the minimum item ("Omega")
• get the sum of all items ("Sum")
• reduce the maximum item to a lower value
• perform an arbitrary operation on all elements except the minimum, which will probably change their values

There are several possible ways to implement this data structure: a linked-list/queue, an ordered array/circular buffer, an unordered array/circular buffer, a minheap plus keeping track of the maxes, a maxheap plus keeping track of the min, a MinMax heap, or Cartesian trees (and I'm sure there are others). I wanted to be able to switch between potential implementations for testing purposes, so an interface seemed the way to go.

I want the classes to support collections of arbitrary types, as long as addition/subtraction and ordering are well-defined. .NET already gives us IComparable but there needs to be an interface to represent summability (that is, support for operations comparable to += and -=).

I'd like the interface to mandate constructors with a specific format...but that's not allowed. I'd like the interface to mandate static factory methods...but that's not allowed either. Oh well, I'll implement them in the real classes anyway.

ISummable.cs

//-----------------------------------------------------------------------
// <copyright file="ISummable.cs" company="Snowbody">
//     Copyright (C) 2014-15 Snowbody
// </copyright>
//-----------------------------------------------------------------------
namespace Amoeba
{
    using System;
    using System.Collections.Generic;

    /// <summary>
    /// Encapsulates a method that has a single parameter and does not return a value.
    /// The method can operate on an element...or change it entirely.
    /// Similar to <see cref="System.Action"/> except it allows reference parameters
    /// </summary>
    /// <typeparam name="T">The type of the parameter of the method that this delegate encapsulates.</typeparam>
    /// <param name="obj">The parameter of the method that this delegate encapsulates.</param>
    public delegate void RefAction<T>(ref T obj);

    /// <summary>
    /// Types supporting this interface support adding and subtracting other instances.
    /// Subtraction is the opposite of addition.
    /// </summary>
    /// <typeparam name="T">Basic type</typeparam>
    public interface ISummable<T> where T : new()
    {
        /// <summary>
        /// Generalized addition
        /// </summary>
        /// <param name="addend">Item to be added</param>
        void Add(T addend);

        /// <summary>
        /// Generalized subtraction, the inverse of <see cref="Plus"/>
        /// </summary>
        /// <param name="sub">Subtrahend (value to be subtracted)</param>
        void Subtract(T sub);
    }
}

IAlphaBetaOmega.cs

//-----------------------------------------------------------------------
// <copyright file="ISummable.cs" company="Snowbody">
//     Copyright (C) 2014-15 Snowbody
// </copyright>
//-----------------------------------------------------------------------
namespace Amoeba
{
    using System;
    using System.Collections.Generic;

    /// <summary>
    /// <para>A collection that supports the operations of returning the most-dominating ("<see cref="Alpha"/>),
    /// next-most-dominating ("<see cref="Beta"/>"), and least-dominating ("<see cref="Omega"/>") elements,
    /// a sum of all elements ("<see cref="Sum"/>"),
    /// and the only change it supports to the collection is to modify the
    /// most-dominating element.</para>
    /// <para>Contracts: After each public operation completes (construction, <see cref="RelaxAlpha"/>, <see cref="DoToEachExceptOmega"/>)
    /// no element of the collection dominates <see cref="Alpha"/>,
    /// no element of the collection (except possibly for <see cref="Alpha"/>) dominates <see cref="Beta"/>,
    /// <see cref="Omega"/> does not dominate any element of the collection,
    /// <see cref="Sum"/> is equal to the sum of all elements in the collection
    /// </para></summary>
    /// <typeparam name="T">Type of the elements in collection</typeparam>
    public interface IAlphaBetaOmega<T>
    {
        /// <summary>
        /// Gets the count of items in the collection
        /// </summary>
        int Count { get; }

        /// <summary>
        /// Gets the most dominating element of the collection
        /// </summary>
        T Alpha { get; }

        /// <summary>
        /// Gets the next-most dominating element of the collection
        /// </summary>
        T Beta { get; }

        /// <summary>
        /// Gets the least dominating element of the collection
        /// </summary>
        T Omega { get; }

        /// <summary>
        /// Gets the sum of all elements of the collection
        /// </summary>
        T Sum { get; }

        /// <summary>
        /// Changes the alpha (most-dominating) element of the collection
        /// Note: It's a safe assumption that <paramref name="Beta"/> before this runs
        /// will be the same as <paramref name="Alpha"/>after this runs
        /// </summary>
        /// <param name="newValue">The new value of the former alpha element</param>
        void RelaxAlpha(T newValue);

        /// <summary>
        /// Change every element of the collection according to a rule.
        /// </summary>
        /// <param name="operation">The action to perform</param>
        void DoToEachExceptOmega(RefAction<T> operation);
    }
}

ABOUnsortedArray.cs

// -----------------------------------------------------------------------
// <copyright file="ABOUnsortedArray.cs" company="Snowbody">
// Copyright (C) 2014-15 Snowbody
// </copyright>
// -----------------------------------------------------------------------

namespace Amoeba
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// Implementation of <see cref="IAlphaBetaOmega&lt;T&gt;"/> using an unsorted array.
    /// </summary>
    /// <typeparam name="T">The type of item that is stored in the collection</typeparam>
    public class ABOUnsortedArray<T> : IAlphaBetaOmega<T> where T : ISummable<T>, new()
    {
        /// <summary>
        /// Function variable that points to the function that checks for domination
        /// </summary>
        private readonly Func<T, T, bool> dominatesFunc;

        /// <summary>
        /// The array that stores the collection
        /// </summary>
        private T[] array;

        /// <summary>
        /// Index of the presently most-dominating item
        /// </summary>
        private int alphaIndex;

        /// <summary>
        /// Index of the presently least-dominating item
        /// </summary>
        private int omegaIndex;

        /// <summary>
        /// Initializes a new instance of the <see cref="ABOUnsortedArray&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="collection">The initial collection of data</param>
        /// <param name="dominates">The function that determines whether one element strictly dominates another.</param>
        public ABOUnsortedArray(IEnumerable<T> collection, Func<T, T, bool> dominates)
        {
            if (dominates == null)
            {
                throw new ArgumentNullException("dominates");
            }

            this.dominatesFunc = dominates;
            this.ConstructorHelper(collection);
        }

        /// <summary>
        /// Prevents a default instance of the <see cref="ABOUnsortedArray&lt;T&gt;"/> class from being created.
        /// </summary>
        private ABOUnsortedArray()
        {
        }

        /// <summary>
        /// Gets count of elements in the collection
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// Gets the most dominating element of the collection
        /// </summary>
        public T Alpha { get; private set; }

        /// <summary>
        /// Gets the second-most dominating element of the collection
        /// </summary>
        public T Beta { get; private set; }

        /// <summary>
        /// Gets the least dominating element of the collection
        /// </summary>
        public T Omega { get; private set; }

        /// <summary>
        /// Gets the sum of all elements of the collection
        /// </summary>
        public T Sum { get; private set; }

        /// <summary>
        /// Factory that makes an ABOUnsortedArray which just uses the comparison provided to determine if an element dominates another if it is strictly greater
        /// </summary>
        /// <param name="collection">The initial collection of items that should be ordered</param>
        /// <param name="comparer">The System.Collections.Generic.IComparer&lt;T&gt; generic interface implementation to use when comparing elements, or null to use the System.IComparable&lt;T&gt; generic interface implementation of each element.</param>
        /// <returns>A new instance of ABOUnsortedArray&lt;T&gt; where the dominates rule is based on the specified comparer</returns>
        public static ABOUnsortedArray<T> MaxABOFactory(IEnumerable<T> collection, IComparer<T> comparer = null)
        {
            if (comparer == null)
            {
                comparer = Comparer<T>.Default;
            }

            return new ABOUnsortedArray<T>(collection, (t1, t2) => comparer.Compare(t1, t2) > 0);
        }

        /// <summary>
        /// Factory that makes an ABOUnsortedArray which just uses the comparison provided to determine if an element dominates another if it is strictly less
        /// </summary>
        /// <param name="collection">The initial collection of items that should be ordered</param>
        /// <param name="comparer">The System.Collections.Generic.IComparer&lt;T&gt; generic interface implementation to use when comparing elements, or null to use the System.IComparable&lt;T&gt; generic interface implementation of each element.</param>
        /// <returns>A new instance of ABOUnsortedArray&lt;T&gt; where the dominates rule is based on the specified comparer</returns>
        public static ABOUnsortedArray<T> MinABOFactory(IEnumerable<T> collection, IComparer<T> comparer = null)
        {
            if (comparer == null)
            {
                comparer = Comparer<T>.Default;
            }

            return new ABOUnsortedArray<T>(collection, (t1, t2) => comparer.Compare(t1, t2) < 0);
        }

        /// <summary>
        /// Constructs a new ABOUnsortedArray&lt;t&gt; by using <param name="dominatesFunc" /> to directly determine whether an element dominates another
        /// </summary>
        /// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
        /// <param name="dominatesFunc">Function used to determine whether an element dominates another</param>
        /// <returns>A new instance of IAlphaBetaOmega&lt;t&gt; with the specified collection and dominates-rule.</returns>
        public static ABOUnsortedArray<T> DefaultAbofactory(IEnumerable<T> collection, Func<T, T, bool> dominatesFunc = null)
        {
            return new ABOUnsortedArray<T>(collection, dominatesFunc);
        }

        /// <summary>
        /// Changes the alpha (most-dominating) element of the collection
        /// It's safe to assume that newValue will be dominated by Beta, but this isn't much use
        /// since we still have to scan to find the new Beta
        /// </summary>
        /// <param name="newValue">The new value of the former alpha element</param>
        public void RelaxAlpha(T newValue)
        {
            this.Sum.Subtract(this.array[this.alphaIndex]);
            this.Sum.Add(newValue);
            this.array[this.alphaIndex] = newValue;
            this.Recalculate(isSum: false);
        }

        /// <summary>
        /// Since we're no longer an <see cref="IEnumerable"/> , this allows iteration among all elements of the collection
        /// </summary>
        /// <param name="operation">The operation/action to perform on each element of the collection</param>
        public void DoToEachExceptOmega(RefAction<T> operation)
        {
            AggregateCatcher a = new AggregateCatcher(this.dominatesFunc);
            this.DoToEachAndAggregateBetween(operation, a, 0, this.omegaIndex);
            AggregateCatcher.AccumulatofFunctionAlphaBetaOmegaSum(a, this.Omega);
            this.DoToEachAndAggregateBetween(operation, a, this.omegaIndex + 1, this.Count);
        }

        /// <summary>
        /// Performs aggregation based on a range of values of the array.
        /// </summary>
        /// <param name="operation">The operation to perform on each element</param>
        /// <param name="a">Stores the intermediate results of aggregation</param>
        /// <param name="startIndex">Index of first array member to aggregate</param>
        /// <param name="pastIndex">One past index of last array member to aggregate</param>
        private void DoToEachAndAggregateBetween(RefAction<T> operation, AggregateCatcher a, int startIndex, int pastIndex)
        {
            for (int i = startIndex; i < pastIndex; i++)
            {
                operation(ref this.array[i]);
                AggregateCatcher.AccumulatofFunctionAlphaBetaOmegaSum(a, this.array[i]);
            }
        }

        /// <summary>
        /// Checks if one element strictly dominates another
        /// </summary>
        /// <param name="x">The element being checked to determine if it is dominant.</param>
        /// <param name="y">The element that is being compared to <see cref="x"/> </param>
        /// <returns>true if <paramref name="x"/> dominates <paramref name="y"/>, false if it does not.</returns>
        private bool Dominates(T x, T y)
        {
            return this.dominatesFunc(x, y);
        }

        /// <summary>
        /// A factoring out of the work that's common to all forms of the constructor
        /// </summary>
        /// <param name="collection">The elements that are initially in the collection, for which we want to know the Alpha, Beta, Omega elements and the sum.</param>
        private void ConstructorHelper(IEnumerable<T> collection)
        {
            if (collection == null)
            {
                throw new ArgumentNullException("collection");
            }

            this.array = collection.ToArray(); // If we only use builtins, we have to make two passes.
            this.Count = this.array.Length;
            if (this.Count < 3)
            {
                throw new ArgumentOutOfRangeException("collection", this.Count, "Size of collection must be at least 3");
            }

            this.Recalculate(isSum: true);  // this also sets Alpha, Beta, Omega, and PSum
        }

        /// <summary>
        /// The accumulator function provided to Aggregate in order to calculate all the properties including sum
        /// </summary>
        /// <param name="currentAccumulatorValue">The current value of the accumulator,
        /// representing the statistics for all elements processed so far.</param>
        /// <param name="currentItem">The current item to be processed</param>
        /// <returns>The updated accumulator object.</returns>
        private AggregateCatcher Accumulator(AggregateCatcher currentAccumulatorValue, T currentItem)
        {
            currentAccumulatorValue.Sum.Add(currentItem);
            return this.AccumulatorWithoutSum(currentAccumulatorValue, currentItem);
        }

        /// <summary>
        /// The accumulator function provided to Aggregate in order to calculate the properties except for sum
        /// </summary>
        /// <param name="accumulator">The current accumulator object, representing the
        /// statistics for everything processed so far.</param>
        /// <param name="currentItem">The current item to be accumulated.</param>
        /// <returns>The accumulator object updated for the <paramref name="currentItem"/></returns>
        private AggregateCatcher AccumulatorWithoutSum(AggregateCatcher accumulator, T currentItem)
        {
            if (this.Dominates(currentItem, accumulator.Alpha))
            {
                accumulator.Beta = accumulator.Alpha;
                accumulator.Alpha = currentItem;
                accumulator.AlphaIndex = accumulator.Count;
            }
            else if (this.Dominates(currentItem, accumulator.Beta))
            {
                accumulator.Beta = currentItem;
            }
            else if (this.Dominates(accumulator.Omega, currentItem))
            {
                accumulator.Omega = currentItem;
                accumulator.OmegaIndex = accumulator.Count;
            }

            accumulator.Count++;
            return accumulator;
        }

        /// <summary>
        /// After changes have happened, this recalculates the properties
        /// </summary>
        /// <param name="isSum">Whether <see cref="Sum"/> needs to be recalculated</param>
        private void Recalculate(bool isSum)
        {
            AggregateCatcher accumulator = new AggregateCatcher(this.dominatesFunc, isSum, this.array[0], this.array[1]);
#if false
            // Why doesn't this work?
            catcher = _array.Skip(2).Aggregate(catcher, isSum ? (x,catcher) => this.Accumulator(x,catcher) : (x,catcher) => this.AccumulatorWithoutSum(x,catcher) );
#else
            if (isSum)
            {
                accumulator = this.array.Skip(2).Aggregate(accumulator, this.Accumulator);
            }
            else
            {
                accumulator = this.array.Skip(2).Aggregate(accumulator, this.AccumulatorWithoutSum);
            }
#endif
            this.Alpha = accumulator.Alpha;
            this.alphaIndex = accumulator.AlphaIndex;
            this.Beta = accumulator.Beta;
            this.Omega = accumulator.Omega;
            this.omegaIndex = accumulator.OmegaIndex;
            this.Sum = accumulator.Sum;
        }

        /// <summary>
        /// The structure that holds the temporary values of Alpha, Beta, Omega, and Sum.
        /// </summary>
        private class AggregateCatcher
        {
            /// <summary>
            /// Initializes a new instance of the <see cref="AggregateCatcher"/> class.
            /// </summary>
            /// <param name="dominatesFunc">A function that determines whether one element dominates another.</param>
            public AggregateCatcher(Func<T, T, bool> dominatesFunc)
            {
                this.Dominates = dominatesFunc;
                this.Count = 0;
            }

            /// <summary>
            /// Initializes a new instance of the <see cref="AggregateCatcher"/> class.
            /// </summary>
            /// <param name="dominatesFunc">A function that determines whether an element dominates another</param>
            /// <param name="isSum">Whether this aggregation is keeping track of the sum</param>
            /// <param name="element">The first element being aggregated</param>
            public AggregateCatcher(Func<T, T, bool> dominatesFunc, bool isSum, T element)
            {
                this.Dominates = dominatesFunc;

                this.SingletonConstructorHelper(isSum, element);
            }

            /// <summary>
            /// Initializes a new instance of the <see cref="AggregateCatcher"/> class.
            /// </summary>
            /// <param name="dominatesFunc">A function that determines whether an element dominates another element.</param>
            /// <param name="isSum">Set to true to indicate that this aggregation is keeping track of sum.</param>
            /// <param name="element0">One element that is being aggregated</param>
            /// <param name="element1">Another element that is being aggregated</param>
            public AggregateCatcher(Func<T, T, bool> dominatesFunc, bool isSum, T element0, T element1)
            {
                this.Count = 2;
                this.Dominates = dominatesFunc;
                if (dominatesFunc(element0, element1))
                {
                    this.Alpha = element0;
                    this.AlphaIndex = 0;
                    this.Omega = element1;
                    this.OmegaIndex = 1;
                    this.Beta = element1;
                }
                else
                {
                    this.Alpha = element1;
                    this.AlphaIndex = 1;
                    this.Omega = element0;
                    this.OmegaIndex = 0;
                    this.Beta = element0;
                }

                if (isSum)
                {
                    this.Sum = new T();
                    this.Sum.Add(element0);
                    this.Sum.Add(element1);
                }
                else
                {
                    this.Sum = default(T);
                }
            }

            /// <summary>
            /// Prevents a default instance of the <see cref="AggregateCatcher"/> class from being created.
            /// </summary>
            private AggregateCatcher()
            {
            }

            /// <summary>
            /// Gets or sets a reference to the most-dominating element found so far
            /// </summary>
            public T Alpha { get; set; }

            /// <summary>
            /// Gets or sets a reference to the second-most dominating element found so far
            /// </summary>
            public T Beta { get; set; }

            /// <summary>
            /// Gets or sets a reference to the least-dominating element found so far
            /// </summary>
            public T Omega { get; set; }

            /// <summary>
            /// Gets or sets the running generalized sum of all items processed (using <see cref="ISummable&lt;T&gt;.Add()"/>
            /// </summary>
            public T Sum { get; set; }

            /// <summary>
            /// Gets or sets the number of items processed
            /// </summary>
            public int Count { get; set; }

            /// <summary>
            /// Gets or sets the function that determines whether an element dominates another element
            /// </summary>
            public Func<T, T, bool> Dominates { get; set; }

            /// <summary>
            /// Gets or sets the index of the alpha (most-dominating) element
            /// </summary>
            public int AlphaIndex { get; set; }

            /// <summary>
            /// Gets or sets the index of the omega (least-dominating) element
            /// </summary>
            public int OmegaIndex { get; set; }

            /// <summary>
            /// The aggregator accumulation function, for computing Alpha, Beta, and Omega, S Sum.
            /// </summary>
            /// <param name="accumulator">The accumulator object for all elements processed so far.</param>
            /// <param name="element">The current element to be processed.</param>
            /// <returns>The accumulator object, updated for the current element</returns>
            public static AggregateCatcher AccumulatofFunctionAlphaBetaOmegaSum(AggregateCatcher accumulator, T element)
            {
                accumulator.Sum.Add(element);
                return AccumulatorFunctionAlphaBetaOmega(accumulator, element);
            }

            /// <summary>
            /// The aggregator accumulation function, for computing Alpha, Beta, and Omega.
            /// </summary>
            /// <param name="accumulator">The accumulator object for all elements processed so far.</param>
            /// <param name="element">The current element to be processed.</param>
            /// <remarks>I'm not happy with the "case 0 - case 1 - case default" structure; wish I was able to start it up better.</remarks>
            /// <returns>The accumulator object, updated for the current element</returns>
            public static AggregateCatcher AccumulatorFunctionAlphaBetaOmega(AggregateCatcher accumulator, T element)
            {
                // switch (accumulator.Count)
                if (accumulator.Count == 0)
                {
                    // hopefully this will never be taken
                    accumulator.SingletonConstructorHelper(false, element);
                    return accumulator;
                }

                if (accumulator.Count == 1)
                {
                    accumulator.Count = 2; // or, Count++
                    if (accumulator.Dominates(accumulator.Alpha, element))
                    {
                        accumulator.Beta = element;
                        accumulator.Omega = element;
                        accumulator.OmegaIndex = 1; // or, Count
                        return accumulator;
                    }

                    accumulator.Beta = accumulator.Alpha;
                    accumulator.Alpha = element;
                    accumulator.AlphaIndex = 1;
                    return accumulator;
                }

                // case default:
                if (accumulator.Dominates(element, accumulator.Alpha))
                {
                    // a new most-dominant item pushes alpha down to beta
                    accumulator.Beta = accumulator.Alpha;
                    accumulator.Alpha = element;
                    accumulator.AlphaIndex = accumulator.Count;
                }
                else if (accumulator.Dominates(accumulator.Omega, element))
                {
                    // a new least-dominant item replaces omega
                    accumulator.Omega = element;
                    accumulator.OmegaIndex = accumulator.Count;
                }
                else if (accumulator.Dominates(element, accumulator.Beta))
                {
                    accumulator.Beta = element;
                }

                accumulator.Count++;
                return accumulator;
            }

            /// <summary>
            /// A helper function called by constructors and the like when there is a single element known.
            /// </summary>
            /// <param name="isSum">If true, then the aggregator keeps track of the sum too.</param>
            /// <param name="element">The initial element of the collection we're aggregating</param>
            public void SingletonConstructorHelper(bool isSum, T element)
            {
                this.Count = 1;
                this.Alpha = element;
                this.Omega = element;
                this.AlphaIndex = 0;
                this.OmegaIndex = 0;
                this.Beta = default(T);
                if (isSum)
                {
                    this.Sum.Add(element);
                }
            }
        }
    }
}

Answer 1

There seems to be a bug where Sum is not properly recalculated after a call to RelaxAlpha. Here is the failing test:

var e = new ABOUnsortedArray<MyInt>(new MyInt[] { 1, 2, 3 }, (x, y) => x.Value >= y.Value);

Assert.AreEqual(3, e.Alpha);
Assert.AreEqual(2, e.Beta);
Assert.AreEqual(1, e.Omega);

Assert.AreEqual(1 + 2 + 3, e.Sum);

e.RelaxAlpha(-100);

Assert.AreEqual(2, e.Alpha);
Assert.AreEqual(1, e.Beta);
Assert.AreEqual(-100, e.Omega);

// e.Sum is null here.
Assert.AreEqual(1 + 2 - 100, e.Sum);

And the MyInt class, for completeness (or in case I'm using your code incorrectly)

public class MyInt : ISummable<MyInt>
{
    public MyInt() : this(0)
    {
    }

    public MyInt(int value)
    {
        Value = value;
    }

    public int Value { get; private set; }

    public void Add(MyInt addend)
    {
        Value += addend.Value;
    }

    public void Subtract(MyInt sub)
    {
        Value -= sub.Value;
    }

    public override string ToString() => Value.ToString();

    public static implicit operator MyInt(int v) => new MyInt(v);

    public static implicit operator int(MyInt m) => m.Value;
}

---

Here's another test that fails with a NullReferenceException

var e = new ABOUnsortedArray<MyInt>(new MyInt[] { 1, 2, 3 }, (x, y) => x.Value >= y.Value);

RefAction<MyInt> foo = (ref MyInt i) => i.Add(10);
// Throws a NullReferenceException.
e.DoToEachExceptOmega(foo);