This is another part of the update to this question. The interfaces are in this question.
To summarize, the class is a generic container similar to MaxHeap, but only needs to support the following operations.
- create from an existing collection or finite IEnumerable (constructor / factory) with arbitrary comparison rule
- peek at the maximum item (Alpha)
- peek at the nearest-to-maximum item (Beta)
- peek at the minimum item (Omega)
- calculate the sum of all items (Sum)
- alter the maximum item (RelaxAlpha). The caller may guarantee that it is smaller than Beta to save a comparison (RelaxAlphaPastBeta).
- perform an arbitrary operation on all elements, which is allowed to change their values (ForEach)
Note that the number of elements in the data structure does not change (no add nor delete) and the only changes supported are the ForEach (basically a new structure) and the relax operations which only affect the then-maximum.
This is an implementation of the interface which uses an unordered array. The properties are updated after each operation.
ABOUnsortedArray.cs
// -----------------------------------------------------------------------
// <copyright file="ABOUnsortedArray.cs" company="Snowbody">
// This file licensed according to the Creative Commons Sharealike License.
// CC-BY-SA
// </copyright>
// -----------------------------------------------------------------------
namespace Amoeba
{
using System;
using System.Collections.Generic;
using System.Linq;
/// <summary>
/// Implementation of <see cref="IAlphaBetaOmega{T}"/> 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>
/// The backing store for the DefaultFactory property
/// </summary>
private static IAboFactory<T> defaultFactory;
/// <summary>
/// The function that checks for domination, provided to constructor
/// </summary>
private readonly Func<T, T, bool> dominatesFunc;
/// <summary>
/// The array that stores the collection
/// </summary>
private T[] array;
/// <summary>
/// Index of the current most-dominating item
/// </summary>
private int alphaIndex;
/// <summary>
/// Index of the current second-most-dominating item
/// </summary>
private int betaIndex;
/// <summary>
/// Index of the current least-dominating item
/// </summary>
private int omegaIndex;
/// <summary>
/// Initializes a new instance of the <see cref="ABOUnsortedArray{T}"/> 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{T}"/> class from being created.
/// </summary>
private ABOUnsortedArray()
{
}
/// <summary>
/// Gets a factory that can make min and max ABOUnsortedArray{T}
/// </summary>
public static IAboFactory<T> DefaultFactory
{
get
{
if (ABOUnsortedArray<T>.defaultFactory == null)
{
ABOUnsortedArray<T>.defaultFactory = new Factory();
}
return ABOUnsortedArray<T>.defaultFactory;
}
}
/// <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>
/// Changes the alpha (most-dominating) element of the collection
/// Since newValue is dominated by Beta,
/// we know the new Alpha is the old Beta (but not its index...should we keep that?)
/// and we know the new Omega is either the old Omega or the old Alpha
/// we definitely have to scan to find the new Beta.
/// </summary>
/// <param name="newValue">The new value of the former alpha element</param>
public void RelaxAlphaPastBeta(T newValue)
{
this.Sum.Subtract(this.array[this.alphaIndex]);
this.Sum.Add(newValue);
this.array[this.alphaIndex] = newValue;
this.MinimalRecalc(newValue);
}
/// <summary>
/// Changes the alpha (most-dominating) element of the collection
/// If newValue is not dominated by beta, we only have to update the sum.
/// If newValue is dominated by Beta,
/// we know the new Alpha is the old Beta (but not its index...should we keep that?)
/// and we know the new Omega is either the old Omega or the old Alpha
/// we definitely 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;
if (this.dominatesFunc(this.Beta, newValue))
{
this.MinimalRecalc(newValue);
}
}
/// <summary>
/// Iterate over all elements of the collection
/// <remarks>The ABOUnsortedArray is not an ICollection, let alone an IEnumerable; this is the only way to touch all the elements.</remarks>
/// </summary>
/// <param name="operation">The operation/action to perform on each element of the collection</param>
public void ForEach(RefAction<T> operation)
{
AggregateCatcher a = new AggregateCatcher(this.dominatesFunc);
this.DoToEachAndAggregateBetween(operation, a, 0, this.Count);
this.Alpha = a.Alpha;
this.alphaIndex = a.AlphaIndex;
this.Beta = a.Beta;
this.betaIndex = a.BetaIndex;
this.Omega = a.Omega;
this.omegaIndex = a.OmegaIndex;
this.Sum = a.Sum;
}
/// <summary>
/// Recalculates only what's necessary after a relax operation.
/// </summary>
/// <param name="newValue">The new value that just replaced alpha.</param>
private void MinimalRecalc(T newValue)
{
// If we're certain newValue doesn't dominate Beta, after a relax, we know that:
// - new omega will either remain the same as old omega, or it will be the slot of old alpha.
// - new alpha will definitely come from old beta
// - we have to find the new beta
if (this.dominatesFunc(this.Omega, newValue))
{
this.Omega = newValue;
this.omegaIndex = this.alphaIndex;
}
this.Alpha = this.Beta;
this.alphaIndex = this.betaIndex;
this.Beta = this.Omega;
this.betaIndex = this.omegaIndex;
for (int i = 0; i < this.Count; i++)
{
if (i == this.alphaIndex)
{
continue;
}
if (this.dominatesFunc(this.array[i], this.Beta))
{
this.Beta = this.array[i];
this.betaIndex = i;
}
}
}
/// <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>
/// 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 UpdateStatisticsIncludingSum(AggregateCatcher currentAccumulatorValue, T currentItem)
{
currentAccumulatorValue.Sum.Add(currentItem);
return this.UpdateStatisticsExceptSum(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 UpdateStatisticsExceptSum(AggregateCatcher accumulator, T currentItem)
{
if (this.dominatesFunc(currentItem, accumulator.Alpha))
{
accumulator.BetaIndex = accumulator.AlphaIndex;
accumulator.Beta = accumulator.Alpha;
accumulator.Alpha = currentItem;
accumulator.AlphaIndex = accumulator.Count;
}
else if (this.dominatesFunc(currentItem, accumulator.Beta))
{
accumulator.BetaIndex = accumulator.Count;
accumulator.Beta = currentItem;
}
else if (this.dominatesFunc(accumulator.Omega, currentItem))
{
accumulator.Omega = currentItem;
accumulator.OmegaIndex = accumulator.Count;
}
accumulator.Count++;
return accumulator;
}
/// <summary>
/// Recalculate all the statistics for the container.
/// This is usually employed after the collection has been changed
/// in a widespread manner.
/// </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?
accumulator = this.array.Skip(2).Aggregate(accumulator, isSum ? this.UpdateStatisticsIncludingSum : this.UpdateStatisticsExceptSum);
#else
if (isSum)
{
accumulator = this.array.Skip(2).Aggregate(accumulator, this.UpdateStatisticsIncludingSum);
this.Sum = accumulator.Sum;
}
else
{
accumulator = this.array.Skip(2).Aggregate(accumulator, this.UpdateStatisticsExceptSum);
}
#endif
this.Alpha = accumulator.Alpha;
this.alphaIndex = accumulator.AlphaIndex;
this.betaIndex = accumulator.BetaIndex;
this.Beta = accumulator.Beta;
this.Omega = accumulator.Omega;
this.omegaIndex = accumulator.OmegaIndex;
}
/// <summary>
/// A factory that can create new ABOUnsortedArray{T} using a standard interface for max and min.
/// </summary>
public class Factory : AboFactory<T>
{
/// <summary>
/// Constructs a new <see cref="ABOUnsortedArray{T}"/> that determines whether an element dominates another by using <paramref name="dominatesFunc" /> by itself.
/// </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{t} with the specified collection and dominates-rule.</returns>
public override IAlphaBetaOmega<T> DefaultAboFactory(IEnumerable<T> collection, Func<T, T, bool> dominatesFunc = null)
{
return new ABOUnsortedArray<T>(collection, dominatesFunc);
}
}
/// <summary>
/// The structure that holds the temporary values of Alpha, Beta, Omega, and Sum.
/// </summary>
private class AggregateCatcher
{
/// <summary>
/// function that determines whether an element dominates another element
/// </summary>
private Func<T, T, bool> dominates;
/// <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;
this.Sum = new T();
}
/// <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.BetaIndex = 1;
this.Beta = element1;
}
else
{
this.Alpha = element1;
this.AlphaIndex = 1;
this.Omega = element0;
this.OmegaIndex = 0;
this.BetaIndex = 0;
this.Beta = element0;
}
this.Sum = new T();
if (isSum)
{
this.Sum.Add(element0);
this.Sum.Add(element1);
}
}
/// <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 the running generalized sum of all items processed (using <see cref="ISummable{T}.Add()"/>
/// </summary>
public T Sum { get; private set; }
/// <summary>
/// Gets or sets the number of items processed
/// </summary>
public int Count { 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 beta (second-most-dominating) element
/// </summary>
public int BetaIndex { 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.BetaIndex = 1;
accumulator.Omega = element;
accumulator.OmegaIndex = 1; // or, Count
return accumulator;
}
accumulator.Beta = accumulator.Alpha;
accumulator.BetaIndex = accumulator.AlphaIndex;
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.BetaIndex = accumulator.AlphaIndex;
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.BetaIndex = accumulator.Count;
}
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);
this.BetaIndex = -1;
if (isSum)
{
this.Sum = new T();
this.Sum.Add(element);
}
}
}
}
}
