Merging lists in Kubernetes SSA

merge.py

#!/usr/bin/env python3

import unittest


def merge(a, b):
    """Merge 2 strings containing unique items into one final string
    containing the same unique items. This tries to preserve the order
    of the two lists if possible, but will prefer the order of the
    second list if they disagree. New items will also appear after older
    items preferably."""
    s = ""
    ai = 0
    bi = 0
    bidxs = {v: k for k, v in enumerate(b)}

    while ai < len(a) or bi < len(b):
        if ai < len(a) and bi < len(b) and a[ai] == b[bi]:
            # Take both
            s += a[ai]
            ai += 1
            bi += 1
        elif ai < len(a) and a[ai] in bidxs and bidxs[a[ai]] < bi:
            ai += 1 # We've seen this already, skip
        elif ai < len(a) and a[ai] not in bidxs:
            # take A
            s += a[ai]
            ai += 1
        elif bi < len(b):
            # take B
            s += b[bi]
            bi += 1
    return s

def new_merge(a, b):
    """Merge 2 strings containing unique items into one final string
    containing the same unique items. This tries to preserve the order
    of the two lists if possible, but will prefer the order of the
    second list if they disagree. New items will also appear after older
    items preferably."""
    s = ""
    ai = 0

    bi = 0
    aset = set(a)
    bset = set(b)

    while ai < len(a) or bi < len(b):
        if ai < len(a) and bi < len(b) and a[ai] == b[bi]:
            # Take both
            s += a[ai]
            ai += 1
            bi += 1
        elif ai < len(a) and bi < len(b) and a[ai] in bset and b[bi] in aset:
            # We have an ordering conflict. Skip a to preserve b's order
            # while prioritizing a's items.
            ai += 1
        elif ai < len(a) and a[ai] not in bset:
            # take A
            s += a[ai]
            ai += 1
        elif bi < len(b):
            # take B
            s += b[bi]
            bi += 1
    return s


class TestMerge(unittest.TestCase):
    def test_cases(self):
        self.assertEqual(merge("ab", "ba"), "ba")
        self.assertEqual(merge("abc", "def"), "abcdef")
        self.assertEqual(merge("abc", "cdef"), "abcdef")
        self.assertEqual(merge("abcgf", "cdef"), "abcgdef")
        self.assertEqual(merge("abc", "defxyz"), "abcdefxyz")
        self.assertEqual(merge("cdef", "ace"), "acdef")
        self.assertEqual(merge("abcxyz", "def"), "abcxyzdef")
        self.assertEqual(merge("abcxyz", "defxyz"), "abcdefxyz")
        self.assertEqual(merge("cagf", "cfag"), "cfag")
        self.assertEqual(merge("abcd", "defa"), "defabc")
        self.assertEqual(merge("cdefghij", "2h3e4kl"), "cd2h3efgij4kl")
        self.assertEqual(merge("abcdefghij", "1b2h3e4kl"), "a1bcd2h3efgij4kl")

    def test_cases_new(self):
        self.assertEqual(new_merge("ab", "ba"), "ba")
        self.assertEqual(new_merge("abc", "def"), "abcdef")
        self.assertEqual(new_merge("abc", "cdef"), "abcdef")
        self.assertEqual(new_merge("abcgf", "cdef"), "abcgdef")
        self.assertEqual(new_merge("abc", "defxyz"), "abcdefxyz")
        self.assertEqual(new_merge("cdef", "ace"), "acdef")
        self.assertEqual(new_merge("abcxyz", "def"), "abcxyzdef")
        self.assertEqual(new_merge("abcxyz", "defxyz"), "abcdefxyz")
        self.assertEqual(new_merge("cagf", "cfag"), "cfag")
        self.assertEqual(new_merge("abcd", "defa"), "bcdefa")
        self.assertEqual(new_merge("cdefghij", "2h3e4kl"), "cd2fghij3e4kl")
        self.assertEqual(new_merge("abcdefghij", "1b2h3e4kl"), "a1bcd2fghij3e4kl")


if __name__ == '__main__':
    unittest.main()