Merging lists, inserting unique entries

Question

I have 2 List lists. Both lists have all elements of the same type, but the type can differ each time I need to perform the following. And each list is sorted.

These lists are the X values for a chart, each list is the X values for a series in the chart. I need to merge them to get the combined values. The simple example is X is DateTime objects and one list has just weekdays while the other has weekend days too.

The more complex example is where the same X value can occur multiple times. So if it's occurs twice in one list and three times in the other, I need it three times in the final list.

Is there an easier way than just walking the two lists and inserting new entries from list 2 into list one as needed?

And as I walk the list, which is typed as objects as it can be a number, string, or DateTime, is there some library call I can call to get an inequality on each pair of objects?

Update:

Let me add a couple of things based on the comments below:

I don't know the type at compile time. This is to handle chart data and the X values can be strings, numbers (int or float), DateTime, and possibly a couple of other types. All I know is that the values on any given run will all be the same type.
What I need is different than AddRange() or Union(). If list A has 5 twice and list B has 5 three times, I need it three times in the final list.
I don't have a code sample because that's what I'm trying to figure out, what should the code for this be.
Basically what I need is Union() but where it handles the case of duplicate entries in each list.

@RuiJarimba - it's the inverse of distinct, if the value 5 is in one list twice and the other 3 times, I need it 3 times in the final list. — David Thielen, Oct 24 '18 at 15:45
Do any of the solutions in [this thread](https://stackoverflow.com/questions/1528171/joining-two-lists-together) work for you? Since you *want* duplicates I'm not sure why equality checking is an issue here as well. It's not 100% clear what you are trying to achieve. As @RuiJarimba mentioned, code would be extremely helpful here. — Dean, Oct 24 '18 at 15:49
Maybe use a stronger type than `object` for the lists? If they're `string` values, why can't you have `List` lists? If they're numbers, make them `List` lists, etc. Or introduce an `IAxisValue` interface maybe. — itsme86, Oct 24 '18 at 15:51
Also consider writing the algorithm with generics instead of casting to object. — juharr, Oct 24 '18 at 15:51
So if an item is duplicated, you want the final list to contain the number of duplicates? If your lists are sorted, then this is a simple extension of a two-way merge. — Jim Mischel, Oct 24 '18 at 16:29
@JimMischel - sort of. If list A has 5 twice and list B has 5 three times, I need the final list to have 5 three times. Not once, also not 5 times. — David Thielen, Oct 24 '18 at 16:54
Off topic, but I think we know each other from many years back. I'm interested in your "No Bugs" book, linked from your profile. The link goes to the Windward main site. Any way I can get a copy. My email is jim AT mischel.com. — Jim Mischel, Oct 24 '18 at 17:51

Jim Mischel · Answer 1 · 2018-10-25T01:20:05.387

This sounds like a simple modification to the standard two-way merge. First, sort the two lists individually. Then, do a standard merge that only copies matching duplicate items. You just have to keep track of the previous item in each list.

Basically, if two items are not equal and a.current == b.prev or b.current == a.prev, then you don't copy the item. Something like:

// This assumes that list1 and list2 are sorted.
l1 = 0
l2 = 0
lOutput = 0
l1Prev = null
l2Prev = null
while (l1 < list1.length && l2 < list2.length)
    if (list1[l1] == list2[l2])
        output[lOutput++] = list1[l1]
        l1Prev = list1[l1]
        l2Prev = list2[l2]
        l1++
        l2++
    else if (list1[l1] == l2Prev)
        // skip the list1 item because it's equal to the previous
        // list2 item
        l1Prev = list1[l1]
        l1++
    else if (list2[l2] == l1Prev)
        // skip the list2 item because it's equal to the previous
        // list1 item
        list2 = list2[l2]
        l2++
    else if (list1[l1] < list2[l2])
        output[lOutput++] = list1[l1]
        l1Prev = list1[l1]
        l1++
    else
        output[lOutput++] = list2[l2]
        l2Prev = list2[l2]
        l2++
// at this point, one of the lists is not empty
while (l1 < list1.length)
    if (list1[l1] != l2Prev)
        output[lOutput++] = list1[l1]
    l1Prev = list1[l1]
    l1++

while (l2 < list2.length)
    if (list2[l2] != l1Prev)
        output[lOutput++] = list2[l2]
    l2Prev = list2[l2]
    l2++

Merging lists, inserting unique entries

1 Answers1