1

I'm working on an algorithm visualizer for sorting algorithms. Give it a (user-submitted) sorting algorithm, hit run, it'll generate a random list of integers and show you what the algorithm looks like. But then you pause to think about this for more than 2 seconds and realize that this is easier said than done. You need a way of passing a list into a function that can spy on everything done to it and report back. Specifically, two features are needed:

  1. Identify when two elements are compared
  2. Identify when one or more elements are moved/swapped

This spying needs to work even when the user makes a temporary copy of one of the elements, with there being nothing a user can do with an element that removes it from view of the spying. For those functional language people out there, there's something distinctly monad-smelling about this sort of problem.

My proposed solution is to wrap the number type and the list type and then reimplement all of the magic methods on both to sneak in the spying:

class Monitorable:

    def __init__(self, value):
        # Idempotent wrapping to handle use of Monitorables and other types
        if isinstance(value, Monitorable):
            # Tell the visualizer they're the same object
            self.__visualize_ref = value.__visualize_ref
            # Copy in the value
            self.__value = value.__value
        else:
            self.__value = value
            self.__visualize_ref = uuid()
            visualize_create(self)

    def __lt__(self, other):
        visualize_compare(self, other)
        return self.__value < other.__value

    def __gt__(self, other):
        visualize_compare(self, other)
        return self.__value > other.__value

    ...


class MonitorList:

    def __init__(self, values):
        self.monitorable_values = [Monitorable(val) for val in values]
        visualize_list(self)

    def __setitem__(self, key, val):
        visualize_setitem(self, key, val)
        self.monitorable_values[key] = Monitorable(val)

    ...

Planning this out before writing the code, this looks like a ridiculous amount of work to reimplement every single magic method just to throw a visualize_x() function in there and wrap the types in Monitorable. Is there a library or Python trick I'm missing to cut down on the hundreds of lines of boilerplate the spying is going to take?

1
  • Couldn’t you instead have a function or class that takes an IComparable, and two numbers? And then notifies the visualizer each time?
    – Adam B
    Dec 5 '20 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.