How to implement Rope data structure split operation

user_7411909 0
Viewed 118

I was reading about Rope(or cord) data structure https://en.wikipedia.org/wiki/Rope_(data_structure) and trying to implement it, but I am struggling to implement the split operation. I tried to look it up but all related answers I was able to find were incorrect.

Below is the split operation:

enter image description here

We want to find the character and return two nodes before and after the split. For example, if we want to split at index 5 of'MyNameIsSimon' then we should return the root of two ropes 'MyName' and 'IsSimon' respectively. Finding the index is easy as given by the pseudo-code in wiki. But I'm struggling the split part especially how to join and return the 2nd half as a new rope. Anyone can help with pseudo-code or any language is much appreciated.

graph-theory data-structures algorithm python
1 Answers

Wikipedia’s diagram looks muddled to me. Here’s a working implementation in Python (without balancing).

class Leaf:
    def __init__(self, s):
        self._s = s

    def __len__(self):
        return len(self._s)

    def __str__(self):
        return self._s

    def inspect(self, indent=0):
        print(" " * indent + repr(self._s))

    def split(self, i):
        return Leaf(self._s[:i]), Leaf(self._s[i:])


class Branch:
    def __init__(self, a, b):
        self._a = a
        self._b = b
        self._l = len(a) + len(b)

    def __len__(self):
        return self._l

    def __str__(self):
        return str(self._a) + str(self._b)

    def inspect(self, indent=0):
        self._a.inspect(indent + 2)
        print(" " * indent + str(len(self._a)))
        self._b.inspect(indent + 2)

    def split(self, i):
        if i < len(self._a):
            a0, a1 = self._a.split(i)
            return a0, Branch(a1, self._b)
        elif i == len(self._a):
            return self._a, self._b
        else:
            assert i > len(self._a)
            b0, b1 = self._b.split(i - len(self._a))
            return Branch(self._a, b0), b1


def make_test_rope():
    e = Leaf("Hello ")
    f = Leaf("my ")
    c = Branch(e, f)
    j = Leaf("na")
    k = Leaf("me i")
    g = Branch(j, k)
    m = Leaf("s")
    n = Leaf(" Simon")
    h = Branch(m, n)
    d = Branch(g, h)
    b = Branch(c, d)
    a = Branch(b, Leaf(""))
    return a


def test():
    a = make_test_rope()
    a.inspect()
    b, c = a.split(11)
    print("--")
    b.inspect()
    print("--")
    c.inspect()


test()

Output:

      'Hello '
    6
      'my '
  9
        'na'
      2
        'me i'
    6
        's'
      1
        ' Simon'
22
  ''
--
    'Hello '
  6
    'my '
9
  'na'
--
    'me i'
  4
      's'
    1
      ' Simon'
11
  ''
user_21446690
Related