1
\$\begingroup\$

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&lt;t&gt; 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);
    }
}
\$\endgroup\$
2
\$\begingroup\$

IAlphaBetaOmega

    /// <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);

this, especially the "Note:" would IMHO be better to state, "Each implementation of this method should throw a "CustomException"" if the passed newValue is equal or bigger than the current Beta".

This is because you can't control what will be passed by using an interface, so you should clearly state what is expected from an implementation of this interface to do if the passed value doesn't match the requirement.

In addition can you spot the error here

// -----------------------------------------------------------------------
// <copyright file="ISummable.cs" company="Snowbody">
// This file licensed according to the Creative Commons Sharealike License.
// CC-BY-SA
// </copyright>
// -----------------------------------------------------------------------  

shouldn't it be <copyright file="IAlphaBetaOmega.cs" instead of <copyright file="ISummable.cs" ?

The very same is true for IABOFactory.cs and ABOFactory.cs.

Otherwise your design and documentation is lookong good and understandable.

\$\endgroup\$
  • \$\begingroup\$ I actually intended for the method RelaxAlphaPastBeta() to exhibit undefined behavior if called with an argument that is not less than Beta. The reason is, sometimes the caller just knows that the new value is less than Beta, and if it can guarantee that to the method, it's not necessary for the method to even check. How should this be signalled? Or is this bad design? \$\endgroup\$ – Snowbody Jul 30 '15 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.