"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

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)