"Age-Record" datastructure

Question

I've been searching for a datastructure that works like an agerecord list. You have an agerecord if no-one younger has a higher mark.

So I want a list of pairs (a,b), where for all couple of pairs (a1,b1) and (a2,b2) following implication holds a1>a2 => b1>b2.

There should be an insertion method insert( a_new, b_new) that inserts (a_new,b_new) if there doesn't exist a pair (a_k, b_k) such that a_k < a_new but b_k > b_new. If this criterion is satisfied then the new pair inserted and all pairs from the list such that a_k > a_new but b_k < b_new are deleted.

The datastructure need not support deletion.

Answer 1

This AgeList keeps track of the best record for each age, then ignores the ages that don't have agerecords when asked for the winners.

While not all losers are removed on Insert (unsure if that's a strong requirement), it should save time overall by being lazy. The biggest weakpoint is the call to OrderBy. If that sort is too expensive while space is available, one might spring for a SortedList to hold all the a's inserted.

If space is at a premium while time is available, it's simple to write a cleanup method similiar to the GetWinners method. Could even be called from the InsertMethod to clean up after every insert.

public class AgeList<T, U> where T:IComparable<T> where U:IComparable<U>
{
    Dictionary<T, U> store = new Dictionary<T, U>();

    public void Insert(T a, U b)
    {
        if (!store.ContainsKey(a) || store[a].CompareTo(b) < 0)
        {
            store[a] = b;
        }
        //else discard by doing nothing
    }

    public IEnumerable<KeyValuePair<T, U>> GetWinners()
    {
        bool first = true;
        U record = default(U);
        foreach(T key in store.Keys.OrderBy(t => t))
        {
            U newValue = store[key];
            if (first)
            {
                first = false;
                record = newValue;
                yield return new KeyValuePair<T, U>(key, record);
            }
            else if (record.CompareTo(newValue) < 0)
            {
                record = newValue;
                yield return new KeyValuePair<T, U>(key, record);
            }
        }
    }
}

Answer 2

Here's a generic solution that I think will do the job for you. It's not optimized for performance, nor is it particularly well tested.

public class AgePair<T, Y>
    where T : IComparable<T>
    where Y : IComparable<Y>
{
    public T A { get; set; }

    public Y B { get; set; }
}

public class AgeRecordList<T, Y> : IEnumerable<AgePair<T,Y>>
    where T : IComparable<T>
    where Y : IComparable<Y> 
{
    private List<AgePair<T, Y>> m_List = new List<AgePair<T, Y>>();

    public void Add(T a, Y b)
    {
        AgePair<T, Y> newPair = new AgePair<T, Y> { A = a, B = b };

        // Get all elements that are younger
        var younger = GetYounger(newPair.A);

        // Find any of the younger with a higher score
        // If found, return without inserting the element
        foreach (var v in younger)
        {
            if (v.B.CompareTo(newPair.B) >= 0)
            {
                return; 
            }
        }

        // Cache elements to delete 
        List<AgePair<T, Y>> toDelete = new List<AgePair<T, Y>>();

        // Find all the elder elements     
        var elder = GetElder(newPair.A);

        // Find all elder elements with a lower B
        foreach (var v in elder)
        {
            if (v.B.CompareTo(newPair.B) <= 0)
            {
                // Mark for delete
                toDelete.Add(v);
            }
        }

        // Delete those elements found above
        foreach (var v in toDelete)
        {
            m_List.Remove(v);
        }

        // Add the new element
        m_List.Add(newPair);

        // Sort the list (ascending by A)
        m_List.Sort(CompareA);
    }

    private List<AgePair<T, Y>> GetElder(T t)
    {
        List<AgePair<T, Y>> result = new List<AgePair<T, Y>>();

        foreach (var current in m_List)
        {
            if (t.CompareTo(current.A) <= 0)
            {
                result.Add(current);
            }
        }

        return result;
    }

    private List<AgePair<T, Y>> GetYounger(T t)
    {
        List<AgePair<T, Y>> result = new List<AgePair<T, Y>>();

        foreach (var current in m_List)
        {
            if (t.CompareTo(current.A) > 0)
            {
                result.Add(current);
            }
        }

        return result;
    }

    private static int CompareA(AgePair<T,Y> item1, AgePair<T,Y> item2)
    {
        return item1.A.CompareTo(item2.A);
    }


    public IEnumerator<AgePair<T, Y>> GetEnumerator()
    {
        return m_List.GetEnumerator();
    }

}

Edit 1: High level overview of the algorithm

1. Find all younger or equal elements,
2. For all younger or equal elements, see if any have a higher B
3. If (2) return
4. Find all elder elements
5. If any elder element has a lower score, delete
6. Sort the list in ascending order (by A)

Edit 2: The speed can easily be increased by a) once you found the younger elements, you can continue from that point when looking for elder elements instead of iterating over all again, and b) instead of sorting it using the Sort method of List, you can use InsertAt(0 or index of first elder)