Merging Two SortedLists

Question

var h1 = SortedList {
  {"one", 1},
  {"two", 2}
};

var h2 = SortedList {
  {"two", 22},
  {"three", 3}
};

How to achieve in idiomatic way h3 ending up with {"one", 1},{"two", 2},{"three", 3}?

Answer 1

The example data you provided is a bit odd, given that the key "three" would generally be ordered before the key "two". I will therefore assume regular string comparison for the keys of the sorted list to be applicable in this answer.

The method below provides the merging algorithm, using enumerators that are advanced when an element is added to the output. If the lists contain an element with the same key, the value is compared as a tie breaker.

public static IEnumerable<KeyValuePair<K, V>> MergeSortedLists<K, V>(
    SortedList<K, V> l1, 
    SortedList<K, V> l2)
    where K : IComparable
    where V : IComparable
{
    using (var l1Iter = l1.GetEnumerator())
    using (var l2Iter = l2.GetEnumerator())
    {
        var morel1 = l1Iter.MoveNext();
        var morel2 = l2Iter.MoveNext();
        while (morel1 || morel2)
        {
            if (!morel1)
            {
                yield return l2Iter.Current;
                morel2 = l2Iter.MoveNext();
            }
            else if (!morel2)
            {
                yield return l1Iter.Current;
                morel1 = l1Iter.MoveNext();
            }
            else 
            {
                var cmp = l1.Comparer.Compare(l1Iter.Current.Key, l2Iter.Current.Key);
                if (cmp < 0)
                {
                    yield return l1Iter.Current;
                    morel1 = l1Iter.MoveNext();
                }
                else if (cmp > 0)
                {
                    yield return l2Iter.Current;
                    morel2 = l2Iter.MoveNext();
                }
                else // keys equal: use value to break tie.
                {
                    if (l1Iter.Current.Value.CompareTo(l1Iter.Current.Value) <= 0)
                        yield return l1Iter.Current;
                    else
                        yield return l2Iter.Current;
                    // or if l1 takes precedence, replace above 4 lines with:
                    // yield return l1Iter.Current;
                    morel1 = l1Iter.MoveNext();
                    morel2 = l2Iter.MoveNext();
                }
            }
        }
    }
}

Usage example:

public static void Main(params string[] args)
{
    // Note: this is not an idiomatic way to instantiate sorted lists.
    var h1 = new SortedList<string, int>() { 
        { "one", 1 }, 
        { "two", 2 }
    };
    var h2 = new SortedList<string, int>() { 
        { "three", 3 }, // because "three" < "two"
        { "two", 22 }
    };
    var h3 = MergeSortedLists(h1, h2);
    Console.WriteLine(string.Join(", ", h3.Select(e => string.Format("{{{0}, {1}}}", e.Key, e.Value))));
    // Outputs:
    // {one, 1}, {three, 3}, {two, 2}
}

Note that it would be a bit more idiomatic C# to make this an extension method named something like MergeWith, so that it could be called as

var h3 = h1.MergeWith(h2);

Answer 2

SortedList can accept an IDictionary as a constructor parameter you can use this workaround to overcome your issue

class Program
{
    private static void Main(string[] args)
    {
        var h1 = new SortedList<string, int>();
            h1.Add("One", 1);
            h1.Add("Two", 2);
        var h2 = new SortedList<string, int>();
            h2.Add("One", 1);
            h2.Add("Two", 22);
            h2.Add("Three", 3);
         var unDict = h1.Union(h2).Distinct(new SortedListComparer()).ToDictionary(d=>d.Key,v=>v.Value);

        SortedList<string,int>  finSortedList = new SortedList<string,int>((IDictionary<string,int>)unDict,StringComparer.InvariantCultureIgnoreCase);
    }
}

class SortedListComparer:EqualityComparer<KeyValuePair<string,int>>
{

    public override bool Equals(KeyValuePair<string, int> x, KeyValuePair<string, int> y)
    {
        return x.Key == y.Key;  
    }

    public override int GetHashCode(KeyValuePair<string, int> obj)
    {
       return   obj.Key.GetHashCode(); 
    }
}

I know this is not Idiomatic but you can try it; Ater all SortedList implement IDictionary

 public class SortedList<TKey, TValue> : IDictionary<TKey, TValue>

Answer 3

I took a little liberty to make your question work in LinqPad4.
Basicly, the same as what you had. Create two collections (List<> here) then join the differences together.

var h1 = new List<Tuple<string,int>>();
h1.Add(new Tuple<string,int>("one",1));
h1.Add(new Tuple<string,int>("two",2));

var h2 = new List<Tuple<string,int>>();
h2.Add(new Tuple<string,int>("two", 22));
h2.Add(new Tuple<string,int>("three",3));

var h3 = from a in h2
        where !(from b in h1 select b.Item1).Contains(a.Item1)
        select a;

h1.AddRange(h3);

h1.Dump();

LinqPad4 link for code. http://share.linqpad.net/soivue.linq

Answer 4

Some PseudoCode to get an algorithm down.

Assuming you can traverse these lists:

var h3 = new SortedList;
var ptrA, ptrB, ptrC = 0;

while(ptrA ! h1.length && ptrB ! h2.length){

     if(h1.ptrA.key < h2.ptrB.key){
           h3.ptrC.key = h1.ptrA.key;
           h3.ptrC.value = h1.ptrA.key;
           ptrA++;
           ptrC++;
       }
     else if(h1.ptrA.key > h2.ptrB.key){
           h3.ptrC.key = h2.ptrB.key;
           h3.ptrC.value = h2.ptrB.key;
           ptrB++;
           ptrC++;
       }
     else if(h1.ptrA.key == h2.ptrB.key){
           h3.ptrC.key = h1.ptrA.key;
           h3.ptrC.value = h1.ptrA.key;
           ptrA++;
           ptrB++;
           ptrC++;
           }
}

maybe my colleagues have a better method or perhaps some additions to this fairly brute force method.

The concept here is simple, as we increment some pointer for each list, we comapre the keys at this location. depending what we find determines which key gets written into the list. If we find equal pairs, then we take the value from list A and increment ALL pointers, effectively leaving behind the value that matched that key in list B.