This is a partial update of this question.
An implementation of these interfaces is 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.
I tried to make the code as generic as possible, and make the constructors sensible. I also decided to include the factory paradigm as it simplifies testing of the multiple implementations.
This question contains only the code of the interfaces and abstract base classes. I hope to get some feedback about the overall paradigm, encapsulation, comments/docstrings, parameter choice, etc. I also have written 2.5 implementations of the interface; I'll post them in a couple more questions in the near future.
The namespace is Amoeba because this was written to support a Nelder-Mead (Amoeba) minimization algorithm.
ISummable.cs
// -----------------------------------------------------------------------
// <copyright file="ISummable.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;
/// <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.
/// Effectively these are += and -=.
/// Subtraction is the inverse operation of addition; if you add a number and subtract it you should be back where you started.
/// Subtraction and addition are mutually commutative; they can be performed in any order.
/// </summary>
/// <typeparam name="T">Type of entity that can be added/subtracted</typeparam>
public interface ISummable<T>
{
/// <summary>
/// Generalized addition, analogous to the += operator
/// </summary>
/// <remarks>The inverse is <see cref="Subtract"/></remarks>
/// <param name="addend">Item to be added</param>
void Add(T addend);
/// <summary>
/// Generalized subtraction, analogous to the -= operator
/// </summary>
/// <remarks>The inverse is <see cref="Add"/></remarks>
/// <param name="subtrahend">Item to be subtracted</param>
void Subtract(T subtrahend);
}
}
IAlphaBetaOmega.cs
// -----------------------------------------------------------------------
// <copyright file="ISummable.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;
/// <summary>
/// <para>A collection that supports the operations of returning the most-dominating ("<see cref="IAlphaBetaOmega.Alpha"/>"),
/// next-most-dominating ("<see cref="IAlphaBetaOmega.Beta"/>"), and least-dominating ("<see cref="IAlphaBetaOmega.Omega"/>") elements,
/// a sum of all elements ("<see cref="IAlphaBetaOmega.Sum"/>"),
/// and supporting the following operations: modify the
/// most-dominating element, and perform an operation on all of the elements except the least-dominating.</para>
/// <para>Contracts: After each public operation completes (construction, <see cref="IAlphaBetaOmega.RelaxAlpha"/>, <see cref="IAlphaBetaOmega.DoToEachExceptOmega"/>)
/// no element of the collection should dominate <see cref="IAlphaBetaOmega.Alpha"/>,
/// no element of the collection (except possibly for <see cref="IAlphaBetaOmega.Alpha"/>) should dominate <see cref="IAlphaBetaOmega.Beta"/>,
/// <see cref="IAlphaBetaOmega.Omega"/> should not dominate any element of the collection,
/// <see cref="IAlphaBetaOmega.Sum"/> should be 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 second-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 only permitted to pass in a newValue that is less than current Beta,
/// meaning that the value of Alpha after this finishes
/// will be the same as the previous value of <see cref="IAlphaBetaOmega.Beta"/>
/// </summary>
/// <param name="newValue">The new value of the former alpha element</param>
void RelaxAlphaPastBeta(T newValue);
/// <summary>
/// Changes the alpha (most-dominating) element of the collection
/// </summary>
/// <param name="newValue">The new value of the former alpha element</param>
void RelaxAlpha(T newValue);
/// <summary>
/// Performs the specified RefAction on each element of the IAlphaBetaOmega{T}.
/// </summary>
/// <param name="operation">The action to perform on each element of the array</param>
void ForEach(RefAction<T> operation);
}
}
IABOFactory.cs
// -----------------------------------------------------------------------
// <copyright file="ISummable.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;
/// <summary>
/// An interface that is implemented by all factories that can create a new IAlphaBetaOmega{<paramref name="T"/>}
/// using a specified dominates-function or comparison-function.
/// </summary>
/// <typeparam name="T">The type of elements in the container</typeparam>
public interface IAboFactory<T>
{
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparer" /> to compare elements, with lesser elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparer">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule.</returns>
IAlphaBetaOmega<T> MinAboFactory(IEnumerable<T> collection, IComparer<T> comparer = null);
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparer" /> to compare elements, with greater elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparer">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule. </returns>
IAlphaBetaOmega<T> MaxAboFactory(IEnumerable<T> collection, IComparer<T> comparer = null);
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparerFunc" /> to compare elements, with lesser elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparerFunc">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule.</returns>
IAlphaBetaOmega<T> MinAboFactory(IEnumerable<T> collection, Comparison<T> comparerFunc);
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparerFunc" /> to compare elements, with greater elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparerFunc">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule. </returns>
IAlphaBetaOmega<T> MaxAboFactory(IEnumerable<T> collection, Comparison<T> comparerFunc);
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} 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<t> with the specified collection and dominates-rule.</returns>
IAlphaBetaOmega<T> DefaultAboFactory(IEnumerable<T> collection, Func<T, T, bool> dominatesFunc = null);
}
}
ABOFactory.cs
// -----------------------------------------------------------------------
// <copyright file="ISummable.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;
/// <summary>
/// An abstract class that it's recommended to derive most implementations of IAboFactory{T} from.
/// It contains sensible implementations for Max factory and Min factory as long as the
/// derived class provides a sensible implementation of the default factory.
/// </summary>
/// <typeparam name="T">The type of objects in the collection that the factory will create.</typeparam>
public abstract class AboFactory<T> : IAboFactory<T>
{
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparer" /> to compare elements, with lesser elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparer">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule.</returns>
public IAlphaBetaOmega<T> MinAboFactory(IEnumerable<T> collection, IComparer<T> comparer = null)
{
if (comparer == null)
{
comparer = Comparer<T>.Default;
}
return this.DefaultAboFactory(collection, (lhs, rhs) => comparer.Compare(lhs, rhs) < 0);
}
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparer" /> to compare elements, with greater elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparer">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule. </returns>
public IAlphaBetaOmega<T> MaxAboFactory(IEnumerable<T> collection, IComparer<T> comparer = null)
{
if (comparer == null)
{
comparer = Comparer<T>.Default;
}
return this.DefaultAboFactory(collection, (lhs, rhs) => comparer.Compare(lhs, rhs) > 0);
}
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparerFunc" /> to compare elements, with lesser elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparerFunc">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule.</returns>
public IAlphaBetaOmega<T> MinAboFactory(IEnumerable<T> collection, Comparison<T> comparerFunc = null)
{
if (comparerFunc == null)
{
return this.DefaultAboFactory(collection, (lhs, rhs) => Comparer<T>.Default.Compare(lhs, rhs) < 0);
}
return this.DefaultAboFactory(collection, (lhs, rhs) => comparerFunc(lhs, rhs) < 0);
}
/// <summary>
/// Constructs a new IAlphaBetaOmega{T} by using <param name="comparerFunc" /> to compare elements, with greater elements dominating.
/// </summary>
/// <param name="collection">The initial values of the collection that we want to scan for alpha, beta, and omega.</param>
/// <param name="comparerFunc">The System.IComparer{T} generic interface implementation to use when comparing elements,
/// or null to use the System.IComparer{T}.Default (which comes from System.IComparable{T} if it's supported).</param>
/// <returns>A new instance of IAlphaBetaOmega{T} with the specified collection and dominates-rule. </returns>
public IAlphaBetaOmega<T> MaxAboFactory(IEnumerable<T> collection, Comparison<T> comparerFunc = null)
{
if (comparerFunc == null)
{
return this.DefaultAboFactory(collection, (lhs, rhs) => Comparer<T>.Default.Compare(lhs, rhs) > 0);
}
return this.DefaultAboFactory(collection, (lhs, rhs) => comparerFunc(lhs, rhs) > 0);
}
/// <summary>
/// Constructs a new <see cref="IAlphaBetaOmega{T}"/> 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 <see cref="IAlphaBetaOmega{T}"/> with the specified collection and dominates-rule.</returns>
public abstract IAlphaBetaOmega<T> DefaultAboFactory(IEnumerable<T> collection, Func<T, T, bool> dominatesFunc = null);
}
}
