1
\$\begingroup\$

I had posted this previously as part of Generic container similar supporting PeekMax, PeekMin, Sum, and PeekNextToMax but I think it was to big a morsel for people to chew on. So I'm splitting it up.

As part of another project (involving portfolio optimization) I'm using an algorithm that requires a data structure supporting the following operations:

  • Construct from a ICollection<T> or finite IEnumerable<T> (The elements are not required to be unique)
  • Get the count of elements of the container
  • Peek at the container's current maximum (or any of them, if more than one are tied for max) but leave it in the container
  • Peek at the container's current minimum (or any of them, if more than one are tied for min) and leave it in the container
  • Get the order-2 statistic (any largest element less than or equal to maximum)
  • Alter the value of the maximum element ("relaxing")
  • Perform an arbitrary operation on all elements of the container except the minimum element (potentially changing them, but no deletions)
  • Return the sum (or more generally, an aggregate) of all elements

None of the operations change the number of elements in the container.

The requirements are flexible enough that I don't need the type parameter to implement IComparable<T> (although if it does, we can use IComparer<T>.Default). If it's not, an ordering function can be passed in to the constructor. The ordering function only needs to determine if one element strictly dominates another -- if they're equal it needs to return false -- in other words, it behaves like >. Unfortunately I don't see any way to specify this in the interface.

Note that it does not require the ability to find or access arbitrary elements, nor does it require the ability to add or remove elements. So it doesn't need to implement ICollection<T>.

Here are some questions I'd be interested in reviewers addressing, thouhg of course any comments at all are appreciated:

The docstrings

  • Are they readable? Am I doing it the right way?
  • Do they help make the code understandable?
  • Am I missing any XML features I should be using?

Other comments

Are they clear? Do they help? Would more of them be helpful? In what places?

The interfaces themselves

  • Do they clearly and concisely specify what I am looking for?
  • Any better ways to do it? (I'm pretty sure there's no way to specify that an interface has to implement an operator, a constructor, or a static method)
  • Do the constraints (on the interface itself and on T) make sense? Should there be others?

IAlphaBetaOmega.cs

// -----------------------------------------------------------------------
// <copyright file="IAlphaBetaOmega.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.
    /// Subtraction is the opposite of addition.
    /// </summary>
    /// <typeparam name="T">Type of entity that can be added/subtracted</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);
    }

    /// <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 dominates <see cref="IAlphaBetaOmega.Alpha"/>,
    /// no element of the collection (except possibly for <see cref="IAlphaBetaOmega.Alpha"/>) dominates <see cref="IAlphaBetaOmega.Beta"/>,
    /// <see cref="IAlphaBetaOmega.Omega"/> does not dominate any element of the collection,
    /// <see cref="IAlphaBetaOmega.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; }

#if false
        /// <summary>
        /// Constructs a new IAlphaBetaOmega&lt;t&gt; 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.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 IAlphaBetaOmega&lt;t&gt; with the specified collection and dominates-rule.</returns>
        public static IAlphaBetaOmega<T> MinAboFactory(IEnumerable<T> collection, IComparer<T> comparerFunc = null);

        /// <summary>
        /// Constructs a new IAlphaBetaOmega&lt;t&gt; 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.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 IAlphaBetaOmega&lt;t&gt; with the specified collection and dominates-rule. </returns>
        public static IAlphaBetaOmega<T> MaxAboFactory(IEnumerable<T> collection, IComparer<T> comparerFunc = null);

        /// <summary>
        /// Constructs a new IAlphaBetaOmega&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 IAlphaBetaOmega<T> DefaultAboFactory(IEnumerable<T> collection, Func<T, T, bool> dominatesFunc = null);
#endif
        /// <summary>
        /// Changes the alpha (most-dominating) element of the collection
        /// Note: It's a safe assumption that <see cref="IAlphaBetaOmega.Beta"/> before this runs
        /// will be the same as <see cref="IAlphaBetaOmega.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);
    }
}
\$\endgroup\$
1
\$\begingroup\$

Let us nitpick a little bit.

There is a little naming issue, which I feel could use some facelifting.

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

You have named the parameter for the Add() method quite well, but you are using an abbreviation for the parameter of the Substract() method.


A collection that supports the operations of returning ...

This does not feel right. It isn't a collection but an interface which defines methods and properties for a collection.

Looking at the object browser for ICollection<T> we are seeing the summary:

Defines methods to manipulate generic collections

Also Microsoft is a little bit to vage, the summary of the IAlphaBetaOmega<T> is a little bit overhelming and demanding.

/// <para>Contracts: After each public operation completes (construction, <see cref="IAlphaBetaOmega.RelaxAlpha"/>, <see cref="IAlphaBetaOmega.DoToEachExceptOmega"/>)
/// no element of the collection dominates <see cref="IAlphaBetaOmega.Alpha"/>,

IMHO the summary of an interface should explain how it should be implemented. So I would rephrase this and maybe some other parts like so

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"/>,  

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

I just don't like this method name. Why not name it e.g ProcessAlphaBeta() ?

\$\endgroup\$
  • \$\begingroup\$ You're right, it isn't a collection (it doesn't have to implement ICollection<T>. DoToEachExceptOmega() is the closest thing to an iterator that an implementation is required to provide. It's more like System.Array.ForEach(). so maybe I should rename it to that? Except it specifically avoids calling the operation on the Omega element. The summary there is wrong. \$\endgroup\$ – Snowbody Jun 30 '15 at 14:42

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.