Change comparison function for BST dynamically in Python

Question

I have made a binary search tree with the help of the following library. I have made a comparison function to determine where the nodes should go. The comparison function determines the current y value for each segment.

Look at the following example:

from sortedcontainers import SortedList

def findCurrentY(segment):
   #uses current_x to calculate value of y...

def compare(segment):
   position = findCurrentY(segment)
   return position

global current_x
myList = SortedList(key = compare)

segments = [segment1,segment2]

current_x = 1
for segment in segments:
   myList.add(segment)

print(MyList)

current_x = 2
print(MyList)

current_x = 3
print(MyList)

This is how my output looks like

For current_x = 1:
MyList = [segment2,segment1] #y value of segment1 is higher than segment2
For current_x = 2:
MyList = [segment2,segment1]
For current_x = 3:
MyList = [segment2,segment1]

It shows three times the same thing, as it only calculated the compare function ones. How can I dynamically change the compare function when my current_x changes without deleting each element and adding it again to my list?

So it needs to look like this.

For current_x = 1:
MyList = [segment2,segment1] #segment 1 has higher y value
For current_x = 2:
MyList = [segment2,segment1] #segment 1 has higher y value
For current_x = 3:
MyList = [segment1,segment2] #segment 1 has **lower** y value

Are you sure that you are making a bst? Could you show how you calculate y? — PIG208
– PIG208, Commented Nov 30, 2020 at 15:59

PIG208 · Accepted Answer · 2020-12-01 08:37:21Z

Changing the value of current_x doesn't alter the list as intended. That's because the whole list needs to be updated again if we change the compare function (i.e., to be re-sorted according to the new y values generated) and this process is necessary for this data structure.

See the below example to see unexpected results brought by using a global variable here.

global current_x
current_x = 1


def key_func(val):
    return globals()['current_x'] * val


list = SortedList(key=compare)

>>> list.add(2)
>>> list.add(3)
>>> list.add(5)
>>> print(list)
SortedKeyList([2, 3, 5], key=<function compare at xxx>)
>>> current_x = -1
>>> list.add(5)
>>> list.add(4)
>>> print(list)
SortedKeyList([5, 4, 2, 3, 5], key=<function compare at xxx>)

Apparently, [5, 4, 2, 3, 5] isn't the result we're expecting. Therefore, instead of changing the key function in-place, a safer approach is to copy the original list into a new SortedList.

# Return a function that gives the y value according to x
# Segments are expected to be functions representing expressions like y=x or y=-x+4
def get_key_func(x_value: int):
    return lambda segment: segment(x_value)


# Return a new sorted list based on the same list but with different x
def new_sorted(sl: SortedList, new_x_value):
    return SortedList(sl, key=get_key_func(new_x_value))

So, according to the graph you gave, we can define segment1 and segment2.

# define y = -x + 4
def expr_one(x):
    return -x + 4


# define y = x
def expr_two(x):
    return x


# The x of the current list is 0
myList = SortedList(key=get_key_func(0))
myList.add(expr_one)         
myList.add(expr_two)

Then, we can try to create new list sorted by the resulting y different x.

for i in range(1, 4):
   print(f'For current_x = {i}:\nMyList = {new_sorted(myList, i)}')

The code above outputs:

For current_x = 1:
MyList = SortedKeyList([<function expr_two at xxx>, <function expr_one at xxx>], key=<...>)
For current_x = 2:
MyList = SortedKeyList([<function expr_two at xxx>, <function expr_one at xxx>], key=<...>)
For current_x = 3:
MyList = SortedKeyList([<function expr_one at xxx>, <function expr_two at xxx>], key=<...>)

However, if you insist to make the list dynamically sorted, you can implement a wrapper class in which self.list always refers to a list sorted as intended.

class DynamicSorted:
    def __init__(self, key_func):
        self.list = SortedList(key=key_func)

    def update_key_func(self, new_key_func):
        self.list = SortedList(self.list, key=new_key_func)

Thanks a lot. Does the two methods have the same complexity? Or is the wrapper class much more efficient?
They are basically the same, except that the wrapper class doesn't require extra space to place the new list.

Collectives™ on Stack Overflow

Change comparison function for BST dynamically in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related