# Implement a simple reference-counting garbage collector. The
# interface is described in the class ‹Heap› below. The root objects
# are immortal (those are established by ‹add_root›). The ‹count›
# method returns the number of reachable live objects. The ‹alive›
# method checks whether a given object is alive. All objects start
# out dead.
#
# References are added/removed using ‹add_ref› and ‹del_ref›. You
# can assume that the number of ‹del_ref› calls on given arguments
# is always at most the same as the number of corresponding
# ‹add_ref› calls. Assume that no reference cycles are created. You
# need to keep track of the references yourself.

class Heap:
    def add_root( self, obj: int ) -> None: pass
    def add_ref( self, obj_from: int, obj_to: int ) -> None: pass
    def del_ref( self, obj_from: int, obj_to: int ) -> None: pass
    def count( self ) -> int: pass
    def alive( self, obj: int ) -> bool: pass


def test_basic() -> None:
    h = Heap()
    assert h.count() == 0
    h.add_root( 1 )
    assert h.count() == 1
    assert h.alive( 1 )
    assert not h.alive( 2 )

    h.add_ref( 1, 2 )
    assert h.count() == 2
    assert h.alive( 1 )
    assert h.alive( 2 )

    h.add_ref( 1, 3 )
    assert h.count() == 3
    assert h.alive( 1 )
    assert h.alive( 2 )
    assert h.alive( 3 )

    h.add_ref( 2, 3 )
    assert h.count() == 3
    assert h.alive( 1 )
    assert h.alive( 2 )
    assert h.alive( 3 )

    h.del_ref( 1, 2 )
    assert h.count() == 2
    assert h.alive( 1 )
    assert not h.alive( 2 )
    assert h.alive( 3 )

    h.del_ref( 1, 3 )
    assert h.count() == 1
    assert h.alive( 1 )
    assert not h.alive( 2 )
    assert not h.alive( 3 )

if __name__ == '__main__':
    test_basic()