<s> import copy <EOL> class SquareAlgorithmNode ( object ) : <EOL> def __init__ ( self , x = <NUM_LIT:0> , y = <NUM_LIT:0> , width = <NUM_LIT:0> , height = <NUM_LIT:0> , used = False , <EOL> down = None , right = None ) : <EOL> """<STR_LIT>""" <EOL> self . x = x <EOL> self . y = y <EOL> self . width = width <EOL> self . height = height <EOL> self . used = used <EOL> self . right = right <EOL> self . down = down <EOL> def find ( self , node , width , height ) : <EOL> """<STR_LIT>""" <EOL> if node . used : <EOL> return self . find ( node . right , width , height ) or self . find ( node . down , width , height ) <EOL> elif node . width >= width and node . height >= height : <EOL> return node <EOL> return None <EOL> def grow ( self , width , height ) : <EOL> """<STR_LIT>""" <EOL> can_grow_d = width <= self . width <EOL> can_grow_r = height <= self . height <EOL> should_grow_r = can_grow_r and self . height >= ( self . width + width ) <EOL> should_grow_d = can_grow_d and self . width >= ( self . height + height ) <EOL> if should_grow_r : <EOL> return self . grow_right ( width , height ) <EOL> elif should_grow_d : <EOL> return self . grow_down ( width , height ) <EOL> elif can_grow_r : <EOL> return self . grow_right ( width , height ) <EOL> elif can_grow_d : <EOL> return self . grow_down ( width , height ) <EOL> return None <EOL> def grow_right ( self , width , height ) : <EOL> """<STR_LIT>""" <EOL> old_self = copy . copy ( self ) <EOL> self . used = True <EOL> self . x = self . y = <NUM_LIT:0> <EOL> self . width += width <EOL> self . down = old_self <EOL> self . right = SquareAlgorithmNode ( x = old_self . width , <EOL> y = <NUM_LIT:0> , <EOL> width = width , <EOL> height = self . height ) <EOL> node = self . find ( self , width , height ) <EOL> if node : <EOL> return self . split ( node , width , height ) <EOL> return None <EOL> def grow_down ( self , width , height ) : <EOL> """<STR_LIT>""" <EOL> old_self = copy . copy ( self ) <EOL> self . used = True <EOL> self . x = self . y = <NUM_LIT:0> <EOL> self . height += height <EOL> self . right = old_self <EOL> self . down = SquareAlgorithmNode ( x = <NUM_LIT:0> , <EOL> y = old_self . height , <EOL> width = self . width , <EOL> height = height ) <EOL> node = self . find ( self , width , height ) <EOL> if node : <EOL> return self . split ( node , width , height ) <EOL> return None <EOL> def split ( self , node , width , height ) : <EOL> """<STR_LIT>""" <EOL> node . used = True <EOL> node . down = SquareAlgorithmNode ( x = node . x , <EOL> y = node . y + height , <EOL> width = node . width , <EOL> height = node . height - height ) <EOL> node . right = SquareAlgorithmNode ( x = node . x + width , <EOL> y = node . y , <EOL> width = node . width - width , <EOL> height = height ) <EOL> return node <EOL> class SquareAlgorithm ( object ) : <EOL> def process ( self , sprite ) : <EOL> root = SquareAlgorithmNode ( width = sprite . images [ <NUM_LIT:0> ] . absolute_width , <EOL> height = sprite . images [ <NUM_LIT:0> ] . absolute_height ) <EOL> for image in sprite . images : <EOL> node = root . find ( root , image . absolute_width , image . absolute_height ) <EOL> if node : <EOL> node = root . split ( node , image . absolute_width , image . absolute_height ) <EOL> else : <EOL> node = root . grow ( image . absolute_width , image . absolute_height ) <EOL> image . x = node . x <EOL> image . y = node . y </s>
