Use Grid to resolve collisions in the favorites view.

7 files changed, 407 insertions, 307 deletions

diff --git a/src/view/home/FriendsBox.py b/src/view/home/FriendsBox.py
index 8c6ddcf..c45c1c6 100644
--- a/src/view/home/FriendsBox.py
+++ b/src/view/home/FriendsBox.py
@@ -50,7 +50,7 @@ class FriendsBox(hippo.Canvas):
         palette = Palette(None, primary_text=profile.get_nick_name(),
                           icon=palette_icon)
         self._owner_icon.set_palette(palette)
-        self._layout.add_center(self._owner_icon)
+        self._layout.add(self._owner_icon)
 
         friends = shellmodel.get_instance().get_friends()
 
@@ -75,3 +75,15 @@ class FriendsBox(hippo.Canvas):
         del self._friends[key]
         icon.destroy()
 
+    def do_size_allocate(self, allocation):
+        width = allocation.width        
+        height = allocation.height
+
+        min_w_, icon_width = self._owner_icon.get_width_request()
+        min_h_, icon_height = self._owner_icon.get_height_request(icon_width)
+        x = (width - icon_width) / 2
+        y = (height - icon_height) / 2
+        self._layout.move(self._owner_icon, x, y)
+
+        hippo.Canvas.do_size_allocate(self, allocation)
+
diff --git a/src/view/home/Makefile.am b/src/view/home/Makefile.am
index 0983077..80781d7 100644
--- a/src/view/home/Makefile.am
+++ b/src/view/home/Makefile.am
@@ -4,6 +4,7 @@ sugar_PYTHON =			\
 	activitieslist.py	\
 	favoritesview.py	\
 	favoriteslayout.py	\
+	grid.py			\
 	FriendView.py		\
 	FriendsBox.py		\
 	launchbox.py		\
diff --git a/src/view/home/MeshBox.py b/src/view/home/MeshBox.py
index cf447d4..1dff8cb 100644
--- a/src/view/home/MeshBox.py
+++ b/src/view/home/MeshBox.py
@@ -430,6 +430,7 @@ class MeshToolbar(gtk.Toolbar):
         return False
 
 class MeshBox(gtk.VBox):
+    __gtype_name__ = 'SugarMeshBox'
     def __init__(self):
         gobject.GObject.__init__(self)
 
@@ -441,7 +442,8 @@ class MeshBox(gtk.VBox):
         self._buddy_to_activity = {}
         self._suspended = True
         self._query = ''
-
+        self._owner_icon = None
+            
         self._toolbar = MeshToolbar()
         self._toolbar.connect('query-changed', self._toolbar_query_changed_cb)
         self.add(self._toolbar)
@@ -481,21 +483,31 @@ class MeshBox(gtk.VBox):
         if self._model.get_mesh():
             self._mesh_added_cb(self._model, self._model.get_mesh())
 
-        self._model.connect('mesh-added',
-                            self._mesh_added_cb)
-        self._model.connect('mesh-removed',
-                            self._mesh_removed_cb)
+        self._model.connect('mesh-added', self.__mesh_added_cb)
+        self._model.connect('mesh-removed', self.__mesh_removed_cb)
 
-    def _mesh_added_cb(self, model, meshdev):
+    def __mesh_added_cb(self, model, meshdev):
         self._add_mesh_icon(meshdev, 1)
         self._add_mesh_icon(meshdev, 6)
         self._add_mesh_icon(meshdev, 11)
 
-    def _mesh_removed_cb(self, model):
+    def __mesh_removed_cb(self, model):
         self._remove_mesh_icon(1)
         self._remove_mesh_icon(6)
         self._remove_mesh_icon(11)
 
+    def do_size_allocate(self, allocation):
+        width = allocation.width        
+        height = allocation.height
+
+        min_w_, icon_width = self._owner_icon.get_width_request()
+        min_h_, icon_height = self._owner_icon.get_height_request(icon_width)
+        x = (width - icon_width) / 2
+        y = (height - icon_height) / 2 - style.GRID_CELL_SIZE
+        self._layout.move(self._owner_icon, x, y)
+
+        gtk.VBox.do_size_allocate(self, allocation)
+
     def _buddy_added_cb(self, model, buddy_model):
         self._add_alone_buddy(buddy_model)
 
@@ -537,10 +549,8 @@ class MeshBox(gtk.VBox):
     def _add_alone_buddy(self, buddy_model):
         icon = BuddyIcon(buddy_model)
         if buddy_model.is_owner():
-            vertical_offset = - style.GRID_CELL_SIZE
-            self._layout.add_center(icon, vertical_offset)
-        else:
-            self._layout.add(icon)
+            self._owner_icon = icon
+        self._layout.add(icon)
 
         if hasattr(icon, 'set_filter'):
             icon.set_filter(self._query)
diff --git a/src/view/home/favoriteslayout.py b/src/view/home/favoriteslayout.py
index 9ab4eff..54cccb1 100644
--- a/src/view/home/favoriteslayout.py
+++ b/src/view/home/favoriteslayout.py
@@ -25,8 +25,13 @@ import hippo
 from sugar.graphics import style
 from sugar import activity
 
+from view.home.grid import Grid
+
 _logger = logging.getLogger('FavoritesLayout')
 
+_CELL_SIZE = 4
+_BASE_SCALE = 1000
+
 class FavoritesLayout(gobject.GObject, hippo.CanvasLayout):
     __gtype_name__ = 'FavoritesLayout'
 
@@ -44,40 +49,39 @@ class FavoritesLayout(gobject.GObject, hippo.CanvasLayout):
     def do_get_width_request(self):
         return 0, gtk.gdk.screen_width()
 
-    def _compare_activities(self, icon_a, icon_b):
-        if hasattr(icon_a, 'installation_time') and \
-                hasattr(icon_b, 'installation_time'):
-            return icon_b.installation_time - icon_a.installation_time
-        else:
-            return 0
+    def compare_activities(self, icon_a, icon_b):
+        return 0
 
     def append(self, icon):
-        self.box.insert_sorted(icon, 0, self._compare_activities)
-        relative_x, relative_y = icon.fixed_position
-        if relative_x >= 0 and relative_y >= 0:
-            width = gtk.gdk.screen_width()
-            height = gtk.gdk.screen_height() - style.GRID_CELL_SIZE
-            self.fixed_positions[icon] = (relative_x * 1000 / width,
-                                           relative_y * 1000 / height)
-        self.update_icon_sizes()
+        self.box.insert_sorted(icon, 0, self.compare_activities)
+        if hasattr(icon, 'fixed_position'):
+            relative_x, relative_y = icon.fixed_position
+            if relative_x >= 0 and relative_y >= 0:
+                min_width_, width = self.box.get_width_request()
+                min_height_, height = self.box.get_height_request(width)
+                self.fixed_positions[icon] = \
+                        (int(relative_x * _BASE_SCALE / float(width)),
+                         int(relative_y * _BASE_SCALE / float(height)))
+            self.update_icon_sizes()
 
     def remove(self, icon):
         del self.fixed_positions[icon]
         self.box.remove(icon)
         self.update_icon_sizes()
 
-    def move_icon(self, icon, x, y):
+    def move_icon(self, icon, x, y, locked=False):
         if icon not in self.box.get_children():
             raise ValueError('Child not in box.')
 
-        width = gtk.gdk.screen_width()
-        height = gtk.gdk.screen_height() - style.GRID_CELL_SIZE
-        registry = activity.get_registry()
-        registry.set_activity_position(icon.get_bundle_id(), icon.get_version(),
-                                       x * width / 1000, y * height / 1000)
-
-        self.fixed_positions[icon] = (x, y)
-        self.box.emit_request_changed()
+        if hasattr(icon, 'get_bundle_id') and hasattr(icon, 'get_version'):
+            min_width_, width = self.box.get_width_request()
+            min_height_, height = self.box.get_height_request(width)
+            registry = activity.get_registry()
+            registry.set_activity_position(
+                    icon.get_bundle_id(), icon.get_version(),
+                    x * width / float(_BASE_SCALE),
+                    y * height / float(_BASE_SCALE))
+            self.fixed_positions[icon] = (x, y)
 
     def update_icon_sizes(self):
         pass
@@ -86,15 +90,59 @@ class FavoritesLayout(gobject.GObject, hippo.CanvasLayout):
                     origin_changed):
         raise NotImplementedError()
 
+    def allow_dnd(self):
+        return False
+
 class RandomLayout(FavoritesLayout):
     __gtype_name__ = 'RandomLayout'
 
     def __init__(self):
         FavoritesLayout.__init__(self)
 
+        min_width_, width = self.do_get_width_request()
+        min_height_, height = self.do_get_height_request(width)
+
+        self._grid = Grid(width / _CELL_SIZE, height / _CELL_SIZE)
+        self._grid.connect('child-changed', self.__grid_child_changed_cb)
+
+    def __grid_child_changed_cb(self, grid, child):
+        child.emit_request_changed()
+
     def append(self, icon):
         FavoritesLayout.append(self, icon)
-        icon.props.size = style.STANDARD_ICON_SIZE
+
+        min_width_, child_width = icon.get_width_request()
+        min_height_, child_height = icon.get_height_request(child_width)
+        min_width_, width = self.box.get_width_request()
+        min_height_, height = self.box.get_height_request(width)
+
+        if icon in self.fixed_positions:
+            x, y = self.fixed_positions[icon]
+            x = min(x, width - child_width)
+            y = min(y, height - child_height)
+        elif hasattr(icon, 'get_bundle_id'):
+            name_hash = hashlib.md5(icon.get_bundle_id())
+            x = int(name_hash.hexdigest()[:5], 16) % (width - child_width)
+            y = int(name_hash.hexdigest()[-5:], 16) % (height - child_height)
+        else:
+            x = None
+            y = None
+
+        if x is None or y is None:
+            self._grid.add(icon,
+                           child_width / _CELL_SIZE, child_height / _CELL_SIZE)
+        else:
+            self._grid.add(icon,
+                           child_width / _CELL_SIZE, child_height / _CELL_SIZE,
+                           x / _CELL_SIZE, y / _CELL_SIZE)
+
+    def remove(self, icon):
+        self._grid.remove(icon)
+        FavoritesLayout.remove(self, icon)
+
+    def move_icon(self, icon, x, y, locked=False):
+        self._grid.move(icon, x / _CELL_SIZE, y / _CELL_SIZE, locked)
+        FavoritesLayout.move_icon(self, icon, x, y, locked)
 
     def do_allocate(self, x, y, width, height, req_width, req_height,
                     origin_changed):
@@ -103,18 +151,15 @@ class RandomLayout(FavoritesLayout):
             min_w_, child_width = child.get_width_request()
             min_h_, child_height = child.get_height_request(child_width)
 
-            if child.item in self.fixed_positions:
-                x, y = self.fixed_positions[child.item]
-            else:
-                name_hash = hashlib.md5(child.item.get_bundle_id())
-                
-                x = int(name_hash.hexdigest()[:5], 16) % (width - child_width)
-                y = int(name_hash.hexdigest()[-5:], 16) % (height - child_height)
-                
-                # TODO Handle collisions
+            rect = self._grid.get_child_rect(child.item)
+            child.allocate(rect.x * _CELL_SIZE,
+                           rect.y * _CELL_SIZE,
+                           child_width,
+                           child_height,
+                           origin_changed)
 
-            child.allocate(int(x), int(y), child_width, child_height,
-                            origin_changed)
+    def allow_dnd(self):
+        return True
 
 _MINIMUM_RADIUS = style.XLARGE_ICON_SIZE / 2 + style.DEFAULT_SPACING + \
         style.STANDARD_ICON_SIZE * 2
@@ -126,6 +171,13 @@ class RingLayout(FavoritesLayout):
 
     def __init__(self):
         FavoritesLayout.__init__(self)
+        self._locked_children = {}
+
+    def move_icon(self, icon, x, y, locked=False):
+        FavoritesLayout.move_icon(self, icon, x, y, locked)
+        if locked:
+            child = self.box.find_box_child(icon)
+            self._locked_children[child] = (x, y)
 
     def _calculate_radius_and_icon_size(self, children_count):
         angle = 2 * math.pi / children_count
@@ -163,32 +215,17 @@ class RingLayout(FavoritesLayout):
         return x, y
 
     def _get_children_in_ring(self):
-        children = self.box.get_layout_children()
-        width, height = self.box.get_allocation()
-        children_in_ring = []
-        for child in children:
-            if child.item in self.fixed_positions:
-                x, y = self.fixed_positions[child.item]
-                distance_to_center = math.hypot(x - width / 2, y - height / 2)
-                # TODO at what distance should we consider a child inside the ring?
-            else:
-                children_in_ring.append(child)
-
+        children_in_ring = [child for child in self.box.get_layout_children() \
+                if child not in self._locked_children]
         return children_in_ring
 
     def update_icon_sizes(self):
         children_in_ring = self._get_children_in_ring()
-        if children_in_ring:
-            radius_, icon_size = \
-                    self._calculate_radius_and_icon_size(len(children_in_ring))
+        radius_, icon_size = \
+                self._calculate_radius_and_icon_size(len(children_in_ring))
 
-            for n in range(len(children_in_ring)):
-                child = children_in_ring[n]
-                child.item.props.size = icon_size
-
-        for child in self.box.get_layout_children():
-            if child not in children_in_ring:
-                child.item.props.size = style.STANDARD_ICON_SIZE
+        for child in children_in_ring:
+            child.item.props.size = icon_size
 
     def do_allocate(self, x, y, width, height, req_width, req_height,
                     origin_changed):
@@ -210,16 +247,20 @@ class RingLayout(FavoritesLayout):
                 child.allocate(int(x), int(y), child_width, child_height,
                                origin_changed)
 
-        for child in self.box.get_layout_children():
-            if child in children_in_ring:
-                continue
+        for child in self._locked_children.keys():
+            x, y = self._locked_children[child]
 
             # We need to always get requests to not confuse hippo
             min_w_, child_width = child.get_width_request()
             min_h_, child_height = child.get_height_request(child_width)
 
-            x, y = self.fixed_positions[child.item]
-
             child.allocate(int(x), int(y), child_width, child_height,
                             origin_changed)
 
+    def compare_activities(self, icon_a, icon_b):
+        if hasattr(icon_a, 'installation_time') and \
+                hasattr(icon_b, 'installation_time'):
+            return icon_b.installation_time - icon_a.installation_time
+        else:
+            return 0
+
diff --git a/src/view/home/favoritesview.py b/src/view/home/favoritesview.py
index bf8ab38..81364c2 100644
--- a/src/view/home/favoritesview.py
+++ b/src/view/home/favoritesview.py
@@ -58,14 +58,14 @@ class FavoritesView(hippo.Canvas):
         shell_model = shellmodel.get_instance()
         shell_model.connect('notify::state', self._shell_state_changed_cb)
 
+        self._layout = RandomLayout()
+        self._box.set_layout(self._layout)
+
         self._my_icon = _MyIcon(style.XLARGE_ICON_SIZE)
-        self._box.append(self._my_icon, hippo.PACK_FIXED)
+        self._layout.append(self._my_icon)
 
         self._current_activity = CurrentActivityIcon()
-        self._box.append(self._current_activity, hippo.PACK_FIXED)
-
-        self._layout = RandomLayout()
-        self._box.set_layout(self._layout)
+        self._layout.append(self._current_activity)
 
         registry = activity.get_registry()
         registry.get_activities_async(reply_handler=self._get_activities_cb)
@@ -79,20 +79,22 @@ class FavoritesView(hippo.Canvas):
         self._press_start_y = None
         self._last_clicked_icon = None
 
-        self.drag_source_set(0, [], 0)
-        self.add_events(gtk.gdk.BUTTON_PRESS_MASK |
-                        gtk.gdk.POINTER_MOTION_HINT_MASK)
-        self.connect('motion-notify-event', self.__motion_notify_event_cb)
-        self.connect('button-press-event', self.__button_press_event_cb)
-        self.connect('drag-begin', self.__drag_begin_cb)
+        if self._layout.allow_dnd():
+            self.drag_source_set(0, [], 0)
+            self.add_events(gtk.gdk.BUTTON_PRESS_MASK |
+                            gtk.gdk.POINTER_MOTION_HINT_MASK)
+            self.connect('motion-notify-event', self.__motion_notify_event_cb)
+            self.connect('button-press-event', self.__button_press_event_cb)
+            self.connect('drag-begin', self.__drag_begin_cb)
 
-        self.drag_dest_set(0, [], 0)
-        self.connect('drag-motion', self.__drag_motion_cb)
-        self.connect('drag-drop', self.__drag_drop_cb)
-        self.connect('drag-data-received', self.__drag_data_received_cb)
+            self.drag_dest_set(0, [], 0)
+            self.connect('drag-motion', self.__drag_motion_cb)
+            self.connect('drag-drop', self.__drag_drop_cb)
+            self.connect('drag-data-received', self.__drag_data_received_cb)
 
     def _add_activity(self, activity_info):
         icon = ActivityIcon(activity_info)
+        icon.props.size = style.STANDARD_ICON_SIZE
         self._layout.append(icon)
 
     def _get_activities_cb(self, activity_list):
@@ -123,9 +125,9 @@ class FavoritesView(hippo.Canvas):
             return
         icon = self._find_activity_icon(activity_info.bundle_id,
                 activity_info.version)
-        if icon is not None and not activity_info.favorite:
+        if icon is not None:
             self._box.remove(icon)
-        elif icon is None and activity_info.favorite:
+        if activity_info.favorite:
             self._add_activity(activity_info)
 
     def _shell_state_changed_cb(self, model, pspec):
@@ -134,21 +136,24 @@ class FavoritesView(hippo.Canvas):
             pass
 
     def do_size_allocate(self, allocation):
-        hippo.Canvas.do_size_allocate(self, allocation)
-        
         width = allocation.width        
         height = allocation.height
 
-        [my_icon_width, my_icon_height] = self._my_icon.get_allocation()
+        min_w_, my_icon_width = self._my_icon.get_width_request()
+        min_h_, my_icon_height = self._my_icon.get_height_request(my_icon_width)
         x = (width - my_icon_width) / 2
         y = (height - my_icon_height - style.GRID_CELL_SIZE) / 2
-        self._box.set_position(self._my_icon, x, y)
+        self._layout.move_icon(self._my_icon, x, y, locked=True)
 
-        [icon_width, icon_height] = self._current_activity.get_allocation()
+        min_w_, icon_width = self._current_activity.get_width_request()
+        min_h_, icon_height = \
+                self._current_activity.get_height_request(icon_width)
         x = (width - icon_width) / 2
-        y = (height + my_icon_height + style.DEFAULT_PADDING \
-                 - style.GRID_CELL_SIZE) / 2
-        self._box.set_position(self._current_activity, x, y)
+        y = (height - my_icon_height - style.GRID_CELL_SIZE) / 2 + \
+                my_icon_height + style.DEFAULT_PADDING
+        self._layout.move_icon(self._current_activity, x, y, locked=True)
+
+        hippo.Canvas.do_size_allocate(self, allocation)
 
     def enable_xo_palette(self):
         self._my_icon.enable_palette()
diff --git a/src/view/home/grid.py b/src/view/home/grid.py
new file mode 100644
index 0000000..abea706
--- /dev/null
+++ b/src/view/home/grid.py
@@ -0,0 +1,223 @@
+# Copyright (C) 2007 Red Hat, Inc.
+# Copyright (C) 2008 One Laptop Per Child
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+from numpy import array
+import random
+
+import gobject
+import gtk
+
+_PLACE_TRIALS = 20
+_MAX_WEIGHT = 255
+_REFRESH_RATE = 200
+_MAX_COLLISIONS_PER_REFRESH = 20
+
+class Grid(gobject.GObject):
+    __gsignals__ = {
+        'child-changed' : (gobject.SIGNAL_RUN_FIRST,
+                           gobject.TYPE_NONE,
+                           ([gobject.TYPE_PYOBJECT]))
+    }
+    def __init__(self, width, height):
+        gobject.GObject.__init__(self)
+
+        self.width = width
+        self.height = height
+        self._children = []
+        self._child_rects = {}
+        self._locked_children = set()
+        self._collisions = []
+        self._collisions_sid = 0
+
+        self._array = array([0], dtype='b')
+        self._array.resize(width * height)
+
+    def add(self, child, width, height, x=None, y=None, locked=False):
+        if x is not None and y is not None:
+            rect = gtk.gdk.Rectangle(x, y, width, height)
+            weight = self._compute_weight(rect)
+        else:
+            trials = _PLACE_TRIALS
+            weight = _MAX_WEIGHT
+            while trials > 0 and weight:
+                x = int(random.random() * (self.width - width))
+                y = int(random.random() * (self.height - height))
+
+                rect = gtk.gdk.Rectangle(x, y, width, height)
+                new_weight = self._compute_weight(rect)
+                if weight > new_weight:
+                    weight = new_weight
+
+                trials -= 1
+
+        self._child_rects[child] = rect
+        self._children.append(child)
+        self._add_weight(self._child_rects[child])
+        if locked:
+            self._locked_children.add(child)
+
+        if weight > 0:
+            self._detect_collisions(child)
+
+    def remove(self, child):
+        self._children.remove(child)
+        self._remove_weight(self._child_rects[child])
+        self._locked_children.discard(child)
+        del self._child_rects[child]
+
+    def move(self, child, x, y, locked=False):
+        self._remove_weight(self._child_rects[child])
+
+        rect = self._child_rects[child]
+        rect.x = x
+        rect.y = y
+
+        weight = self._compute_weight(rect)
+        self._add_weight(self._child_rects[child])
+
+        if locked:
+            self._locked_children.add(child)
+        else:
+            self._locked_children.discard(child)
+
+        if weight > 0:
+            self._detect_collisions(child)
+        
+    def _shift_child(self, child, weight):
+        rect = self._child_rects[child]
+        
+        new_rects = []
+
+        # Get rects right, left, bottom and top
+        if (rect.x + rect.width < self.width - 1):
+            new_rects.append(gtk.gdk.Rectangle(rect.x + 1, rect.y,
+                                               rect.width, rect.height))
+
+        if (rect.x - 1 > 0):
+            new_rects.append(gtk.gdk.Rectangle(rect.x - 1, rect.y,
+                                               rect.width, rect.height))
+
+        if (rect.y + rect.height < self.height - 1):
+            new_rects.append(gtk.gdk.Rectangle(rect.x, rect.y + 1,
+                                               rect.width, rect.height))
+
+        if (rect.y - 1 > 0):
+            new_rects.append(gtk.gdk.Rectangle(rect.x, rect.y - 1,
+                                               rect.width, rect.height))
+
+        # Get diagonal rects
+        if rect.x + rect.width < self.width - 1 and \
+                rect.y + rect.height < self.height - 1:
+            new_rects.append(gtk.gdk.Rectangle(rect.x + 1, rect.y + 1,
+                                               rect.width, rect.height))
+
+        if rect.x - 1 > 0 and rect.y + rect.height < self.height - 1:
+            new_rects.append(gtk.gdk.Rectangle(rect.x - 1, rect.y + 1,
+                                               rect.width, rect.height))
+
+        if rect.x + rect.width < self.width - 1 and rect.y - 1 > 0:
+            new_rects.append(gtk.gdk.Rectangle(rect.x + 1, rect.y - 1,
+                                               rect.width, rect.height))
+
+        if rect.x - 1 > 0 and rect.y - 1 > 0:
+            new_rects.append(gtk.gdk.Rectangle(rect.x - 1, rect.y - 1,
+                                               rect.width, rect.height))
+
+        random.shuffle(new_rects)
+
+        best_rect = None
+        for new_rect in new_rects:
+            new_weight = self._compute_weight(new_rect)
+            if new_weight < weight:
+                best_rect = new_rect
+                weight = new_weight
+        
+        if best_rect:
+            self._child_rects[child] = best_rect
+            weight = self._shift_child(child, weight)
+
+        return weight
+
+    def __solve_collisions_cb(self):
+        for i in range(_MAX_COLLISIONS_PER_REFRESH):
+            collision = self._collisions.pop(0)
+
+            old_rect = self._child_rects[collision]
+            self._remove_weight(old_rect)
+            weight = self._compute_weight(old_rect)
+            weight = self._shift_child(collision, weight)
+            self._add_weight(self._child_rects[collision])
+
+            # TODO: we shouldn't give up the first time we failed to find a
+            # better position.
+            if old_rect != self._child_rects[collision]:
+                self._detect_collisions(collision)
+                self.emit('child-changed', collision)
+                if weight > 0:
+                    self._collisions.append(collision)
+
+            if not self._collisions:
+                self._collisions_sid = 0
+                return False
+
+        return True
+
+    def _detect_collisions(self, child):
+        collision_found = False
+        child_rect = self._child_rects[child]
+        for c in self._children:
+            intersection = child_rect.intersect(self._child_rects[c])
+            if c != child and intersection.width > 0:
+                if c not in self._locked_children and c not in self._collisions:
+                    collision_found = True
+                    self._collisions.append(c)
+
+        if collision_found:
+            if child not in self._collisions:
+                self._collisions.append(child)
+
+        if len(self._collisions) and not self._collisions_sid:
+            self._collisions_sid = gobject.timeout_add(_REFRESH_RATE,
+                    self.__solve_collisions_cb, priority=gobject.PRIORITY_LOW)
+
+    def _add_weight(self, rect):
+        for i in range(rect.x, rect.x + rect.width):
+            for j in range(rect.y, rect.y + rect.height):
+                self[j, i] += 1
+
+    def _remove_weight(self, rect):
+        for i in range(rect.x, rect.x + rect.width):
+            for j in range(rect.y, rect.y + rect.height):
+                self[j, i] -= 1
+
+    def _compute_weight(self, rect):
+        weight = 0
+
+        for i in range(rect.x, rect.x + rect.width):
+            for j in range(rect.y, rect.y + rect.height):
+                weight += self[j, i]
+
+        return weight
+    
+    def __getitem__(self, (row, col)):
+        return self._array[col + row * self.width]
+
+    def __setitem__(self, (row, col), value):
+        self._array[col + row * self.width] = value
+
+    def get_child_rect(self, child):
+        return self._child_rects[child]
diff --git a/src/view/home/spreadlayout.py b/src/view/home/spreadlayout.py
index 23ff587..f7584ab 100644
--- a/src/view/home/spreadlayout.py
+++ b/src/view/home/spreadlayout.py
@@ -14,188 +14,15 @@
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
-from numpy import array
-import random
-
 import hippo
 import gobject
 import gtk
 
 from sugar.graphics import style
 
-_PLACE_TRIALS = 20
-_MAX_WEIGHT = 255
-_CELL_SIZE = 4
-_REFRESH_RATE = 200
-_MAX_COLLISIONS_PER_REFRESH = 20
-
-class _Grid(gobject.GObject):
-    __gsignals__ = {
-        'child-changed' : (gobject.SIGNAL_RUN_FIRST,
-                           gobject.TYPE_NONE,
-                           ([gobject.TYPE_PYOBJECT]))
-    }
-    def __init__(self, width, height):
-        gobject.GObject.__init__(self)
-
-        self.width = width
-        self.height = height
-        self._children = []
-        self._collisions = []
-        self._collisions_sid = 0
-
-        self._array = array([0], dtype='b')
-        self._array.resize(width * height)
-
-    def add(self, child, width, height):
-        trials = _PLACE_TRIALS
-        weight = _MAX_WEIGHT
-        while trials > 0 and weight:
-            x = int(random.random() * (self.width - width))
-            y = int(random.random() * (self.height - height))
-
-            rect = gtk.gdk.Rectangle(x, y, width, height)
-            new_weight = self._compute_weight(rect)
-            if weight > new_weight:
-                weight = new_weight
-
-            trials -= 1
-
-        child.grid_rect = rect
-        child.locked = False
-
-        self._add_child(child)
-
-        if weight > 0:
-            self._detect_collisions(child)
-
-    def remove(self, child):
-        self._children.remove(child)
-        self._remove_weight(child.grid_rect)
-        child.grid_rect = None
-
-    def _add_child(self, child):
-        self._children.append(child)
-        self.add_weight(child.grid_rect)
-
-    def _shift_child(self, child, weight):
-        rect = child.grid_rect
-        
-        new_rects = []
-
-        if (rect.x + rect.width < self.width - 1):
-            new_rects.append(gtk.gdk.Rectangle(rect.x + 1, rect.y,
-                                               rect.width, rect.height))
-
-        if (rect.x - 1 > 0):
-            new_rects.append(gtk.gdk.Rectangle(rect.x - 1, rect.y,
-                                               rect.width, rect.height))
-
-        if (rect.y + rect.height < self.height - 1):
-            new_rects.append(gtk.gdk.Rectangle(rect.x, rect.y + 1,
-                                               rect.width, rect.height))
-
-        if (rect.y - 1 > 0):
-            new_rects.append(gtk.gdk.Rectangle(rect.x, rect.y - 1,
-                                               rect.width, rect.height))
-
-        if rect.x + rect.width < self.width - 1 and \
-                rect.y + rect.height < self.height - 1:
-            new_rects.append(gtk.gdk.Rectangle(rect.x + 1, rect.y + 1,
-                                               rect.width, rect.height))
-
-        if rect.x - 1 > 0 and rect.y + rect.height < self.height - 1:
-            new_rects.append(gtk.gdk.Rectangle(rect.x - 1, rect.y + 1,
-                                               rect.width, rect.height))
-
-        if rect.x + rect.width < self.width - 1 and rect.y - 1 > 0:
-            new_rects.append(gtk.gdk.Rectangle(rect.x + 1, rect.y - 1,
-                                               rect.width, rect.height))
-
-        if rect.x - 1 > 0 and rect.y - 1 > 0:
-            new_rects.append(gtk.gdk.Rectangle(rect.x - 1, rect.y - 1,
-                                               rect.width, rect.height))
-
-        random.shuffle(new_rects)
-
-        best_rect = None
-        for new_rect in new_rects:
-            new_weight = self._compute_weight(new_rect)
-            if new_weight < weight:
-                best_rect = new_rect
-                weight = new_weight
-        
-        if best_rect:
-            child.grid_rect = best_rect
-            weight = self._shift_child(child, weight)
-
-        return weight
-
-    def __solve_collisions_cb(self):
-        for i in range(_MAX_COLLISIONS_PER_REFRESH):
-            collision = self._collisions.pop(0)
-
-            old_rect = collision.grid_rect
-            self._remove_weight(collision.grid_rect)
-            weight = self._compute_weight(collision.grid_rect)
-            weight = self._shift_child(collision, weight)
-            self.add_weight(collision.grid_rect)
-
-            # TODO: we shouldn't give up the first time we failed to find a
-            # better position.
-            if old_rect != collision.grid_rect:
-                self._detect_collisions(collision)
-                self.emit('child-changed', collision)
-                if weight > 0:
-                    self._collisions.append(collision)
-
-            if not self._collisions:
-                return False
-
-        return True
-
-    def _detect_collisions(self, child):
-        collision_found = False
-        for c in self._children:
-            intersection = child.grid_rect.intersect(c.grid_rect)
-            if c != child and intersection.width > 0:
-                if c not in self._collisions:
-                    collision_found = True
-                    self._collisions.append(c)
-
-        if collision_found:
-            if child not in self._collisions:
-                self._collisions.append(child)
-
-        if len(self._collisions) and not self._collisions_sid:
-            self._collisions_sid = gobject.timeout_add(_REFRESH_RATE,
-                    self.__solve_collisions_cb, priority=gobject.PRIORITY_LOW)
-
-    def add_weight(self, rect):
-        for i in range(rect.x, rect.x + rect.width):
-            for j in range(rect.y, rect.y + rect.height):
-                self[j, i] += 1
-
-    def _remove_weight(self, rect):
-        for i in range(rect.x, rect.x + rect.width):
-            for j in range(rect.y, rect.y + rect.height):
-                self[j, i] -= 1
-
-    def _compute_weight(self, rect):
-        weight = 0
-
-        for i in range(rect.x, rect.x + rect.width):
-            for j in range(rect.y, rect.y + rect.height):
-                weight += self[j, i]
-
-        return weight
-    
-    def __getitem__(self, (row, col)):
-        return self._array[col + row * self.width]
-
-    def __setitem__(self, (row, col), value):
-        self._array[col + row * self.width] = value
+from view.home.grid import Grid
 
+_CELL_SIZE = 4
 
 class SpreadLayout(gobject.GObject, hippo.CanvasLayout):
     __gtype_name__ = 'SugarSpreadLayout'
@@ -206,35 +33,22 @@ class SpreadLayout(gobject.GObject, hippo.CanvasLayout):
         min_width, width = self.do_get_width_request()
         min_height, height = self.do_get_height_request(width)
 
-        self._grid = _Grid(width / _CELL_SIZE, height / _CELL_SIZE)
+        self._grid = Grid(width / _CELL_SIZE, height / _CELL_SIZE)
         self._grid.connect('child-changed', self._grid_child_changed_cb)
 
-    def add_center(self, child, vertical_offset=0):
-        self._box.append(child)
-
-        width, height = self._get_child_grid_size(child)
-        rect = gtk.gdk.Rectangle(int((self._grid.width - width) / 2),
-                                 int((self._grid.height - height) / 2),
-                                 width + 1, height + 1)
-        self._grid.add_weight(rect)
-
-        box_child = self._box.find_box_child(child)
-        box_child.grid_rect = None
-        box_child.vertical_offset = vertical_offset
-
     def add(self, child):
         self._box.append(child)
 
         width, height = self._get_child_grid_size(child)
-        box_child = self._box.find_box_child(child)
-        self._grid.add(box_child, width, height)
+        self._grid.add(child, width, height)
 
     def remove(self, child):
-        box_child = self._box.find_box_child(child)
-        self._grid.remove(box_child)
-
+        self._grid.remove(child)
         self._box.remove(child)
 
+    def move(self, child, x, y):
+        self._grid.move(child, x / _CELL_SIZE, y / _CELL_SIZE, locked=True)
+
     def do_set_box(self, box):
         self._box = box
 
@@ -251,19 +65,12 @@ class SpreadLayout(gobject.GObject, hippo.CanvasLayout):
             min_w, child_width = child.get_width_request()
             min_h, child_height = child.get_height_request(child_width)
 
-            rect = child.grid_rect
-            if child.grid_rect:
-                child.allocate(rect.x * _CELL_SIZE,
-                               rect.y * _CELL_SIZE,
-                               rect.width * _CELL_SIZE,
-                               rect.height * _CELL_SIZE,
-                               origin_changed)
-            else:
-                vertical_offset = child.vertical_offset
-                child_x = x + (width - child_width) / 2
-                child_y = y + (height - child_height + vertical_offset) / 2
-                child.allocate(child_x, child_y, child_width, child_height,
-                               origin_changed)
+            rect = self._grid.get_child_rect(child.item)
+            child.allocate(rect.x * _CELL_SIZE,
+                           rect.y * _CELL_SIZE,
+                           rect.width * _CELL_SIZE,
+                           rect.height * _CELL_SIZE,
+                           origin_changed)
 
     def _get_child_grid_size(self, child):
         min_width, width = child.get_width_request()
@@ -271,5 +78,6 @@ class SpreadLayout(gobject.GObject, hippo.CanvasLayout):
 
         return int(width / _CELL_SIZE), int(height / _CELL_SIZE)
 
-    def _grid_child_changed_cb(self, grid, box_child):
-        box_child.item.emit_request_changed()
+    def _grid_child_changed_cb(self, grid, child):
+        child.emit_request_changed()
+