Age Record Data Structure

Question

I was looking for a data structure that works like an agerecord list. Do you have agerecord if someone younger has a higher sign.

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

An insertion method (a_new, b_new) must be inserted that inserts (a_new, b_new) if the pair (a_k, b_k) does not exist, so a_k <a_new, but b_k> b_new. If this criterion is met, then a new pair is inserted and all pairs from the list are such that a_k> a_new, but b_k <b_new are deleted.

The data structure should not support deletion.

Answer 1

Here is a general solution that I think will do the work for you. It is not optimized for performance, and is not particularly well tested .

public class AgePair<T, Y> where T : IComparable<T> where Y : IComparable<Y> { public TA { get; set; } public YB { 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 (vBCompareTo(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 (vBCompareTo(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 Algorithm Overview

• Find all minor or equal items,
• For all minor or equal elements, see if they have a higher B
• If (2) return
• Find all high items
• If any senior element has a lower score, remove
• Sort the list in ascending order (A)

Change 2: the speed can be easily increased by: a) after you find younger elements, you can continue from this point when searching for older elements instead of repeating everything again, and b) instead of sorting using the Sort List method, you can use InsertAt (0 or index of first high)

Answer 2

This AgeList keeps track of the best record for each age, and then ignores ages that do not have agorists when asked for winners.

While not all players are removed on the Insert (unsure if this is a strong requirement), this should save time in general by being lazy. The biggest weakness is the call for OrderBy. If this view is too expensive and space is available, spring for SortedList could hold all inserted a.

If space is at its best when time is available, simply write a cleaning method similar to GetWinners. You can even call from InsertMethod to clean up after each 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); } } } }