from typing import Optional, Set

# Write a Cheney-style semi-space collector, using the same
# interface and requirements as before. The main difference is in
# the overhead of the algorithm (only 2 pointers outside of to/from
# spaces are available in the implementation of collect in this
# exercise).

class Heap:
    def __init__( self ):
        self.data : List[ List[ int ] ] = []

    def read( self, obj_id: int, index: int ) -> Optional[int]: pass
    def write( self, obj_id: int, index: int,
               value: int ) -> bool: pass
    def make( self, size: int ) -> int: pass
    def count( self ) -> int: pass
    def collect( self ) -> None: pass


def test_basic() -> None:
    h = Heap()

    def read( obj_id: int, idx: int ) -> int:
        r = h.read( obj_id, idx )
        assert r is not None
        return r

    def check( expect: Set[ int ] ) -> None:
        found = set()

        for i in range( 1, len( expect ) + 1 ):
            x = h.read( i, 0 ) 
            assert x is not None, i
            found.add( -x )

        for i in range( len( expect ) + 1, 5 ):
            assert h.read( i, 0 ) is None, i

        assert found == expect, ( found, expect )

        for i in expect:
            x = h.read( 0, i )
            assert x is not None
            if x != 0:
                assert h.read( x, 0 ) == -i

    h.make( 5 ) # create the root
    h.write( 0, 1, a := h.make( 2 ) )
    h.write( read( 0, 1 ), 0, -1 )
    h.write( 0, 2, h.make( 2 ) )
    h.write( read( 0, 2 ), 0, -2 )
    h.write( 0, 3, h.make( 2 ) )
    h.write( read( 0, 3 ), 0, -3 )
    h.write( 0, 4, b := h.make( 3 ) )
    h.write( read( 0, 4 ), 0, -4 )

    check( { 1, 2, 3, 4 } )
    h.collect()
    check( { 1, 2, 3, 4 } )

    h.write( read( 0, 1 ), 1, read( 0, 4 ) )
    h.write( read( 0, 4 ), 1, read( 0, 1 ) )

    check( { 1, 2, 3, 4 } )
    h.collect()
    check( { 1, 2, 3, 4 } )

    h.write( 0, 2, 0 )
    h.write( 0, 3, 0 )
    h.collect()
    check( { 1, 4 } )

    h.write( 0, 1, 0 )
    h.collect()
    check( { 1, 4 } )
    h.write( 0, 4, 0 )
    h.collect()
    check( set() )


if __name__ == '__main__':
    test_basic()