nautilus-3.6.3/libnautilus-private/nautilus-canvas-container.c

No issues found

   1 /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 8; tab-width: 8 -*- */
   2 
   3 /* nautilus-canvas-container.c - Canvas container widget.
   4 
   5    Copyright (C) 1999, 2000 Free Software Foundation
   6    Copyright (C) 2000, 2001 Eazel, Inc.
   7    Copyright (C) 2002, 2003 Red Hat, Inc.
   8    
   9    The Gnome Library is free software; you can redistribute it and/or
  10    modify it under the terms of the GNU Library General Public License as
  11    published by the Free Software Foundation; either version 2 of the
  12    License, or (at your option) any later version.
  13 
  14    The Gnome Library is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17    Library General Public License for more details.
  18 
  19    You should have received a copy of the GNU Library General Public
  20    License along with the Gnome Library; see the file COPYING.LIB.  If not,
  21    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  22    Boston, MA 02111-1307, USA.
  23 
  24    Authors: Ettore Perazzoli <ettore@gnu.org>,
  25    Darin Adler <darin@bentspoon.com>
  26 */
  27 
  28 #include <config.h>
  29 #include <math.h>
  30 #include "nautilus-canvas-container.h"
  31 
  32 #include "nautilus-global-preferences.h"
  33 #include "nautilus-canvas-private.h"
  34 #include "nautilus-lib-self-check-functions.h"
  35 #include "nautilus-selection-canvas-item.h"
  36 #include <atk/atkaction.h>
  37 #include <eel/eel-accessibility.h>
  38 #include <eel/eel-vfs-extensions.h>
  39 #include <eel/eel-gtk-extensions.h>
  40 #include <eel/eel-art-extensions.h>
  41 #include <eel/eel-editable-label.h>
  42 
  43 #include <gdk/gdkkeysyms.h>
  44 #include <gtk/gtk.h>
  45 #include <gdk/gdkx.h>
  46 #include <glib/gi18n.h>
  47 #include <stdio.h>
  48 #include <string.h>
  49 
  50 #define DEBUG_FLAG NAUTILUS_DEBUG_CANVAS_CONTAINER
  51 #include "nautilus-debug.h"
  52 
  53 #define TAB_NAVIGATION_DISABLED
  54 
  55 /* Interval for updating the rubberband selection, in milliseconds.  */
  56 #define RUBBERBAND_TIMEOUT_INTERVAL 10
  57 
  58 #define RUBBERBAND_SCROLL_THRESHOLD 5
  59 
  60 /* Initial unpositioned icon value */
  61 #define ICON_UNPOSITIONED_VALUE -1
  62 
  63 /* Timeout for making the icon currently selected for keyboard operation visible.
  64  * If this is 0, you can get into trouble with extra scrolling after holding
  65  * down the arrow key for awhile when there are many items.
  66  */
  67 #define KEYBOARD_ICON_REVEAL_TIMEOUT 10
  68 
  69 #define CONTEXT_MENU_TIMEOUT_INTERVAL 500
  70 
  71 /* Maximum amount of milliseconds the mouse button is allowed to stay down
  72  * and still be considered a click.
  73  */
  74 #define MAX_CLICK_TIME 1500
  75 
  76 /* Button assignments. */
  77 #define DRAG_BUTTON 1
  78 #define RUBBERBAND_BUTTON 1
  79 #define MIDDLE_BUTTON 2
  80 #define CONTEXTUAL_MENU_BUTTON 3
  81 #define DRAG_MENU_BUTTON 2
  82 
  83 /* Maximum size (pixels) allowed for icons at the standard zoom level. */
  84 #define MINIMUM_IMAGE_SIZE 24
  85 #define MAXIMUM_IMAGE_SIZE 96
  86 
  87 #define ICON_PAD_LEFT 4
  88 #define ICON_PAD_RIGHT 4
  89 #define ICON_BASE_WIDTH 96
  90 
  91 #define ICON_PAD_TOP 4
  92 #define ICON_PAD_BOTTOM 4
  93 
  94 #define CONTAINER_PAD_LEFT 4
  95 #define CONTAINER_PAD_RIGHT 4
  96 #define CONTAINER_PAD_TOP 4
  97 #define CONTAINER_PAD_BOTTOM 4
  98 
  99 #define STANDARD_ICON_GRID_WIDTH 155
 100 
 101 /* Desktop layout mode defines */
 102 #define DESKTOP_PAD_HORIZONTAL 	10
 103 #define DESKTOP_PAD_VERTICAL 	10
 104 #define SNAP_SIZE_X 		78
 105 #define SNAP_SIZE_Y 		20
 106 
 107 #define MINIMUM_EMBEDDED_TEXT_RECT_WIDTH       20
 108 #define MINIMUM_EMBEDDED_TEXT_RECT_HEIGHT      20
 109 
 110 /* If icon size is bigger than this, request large embedded text.
 111  * Its selected so that the non-large text should fit in "normal" icon sizes
 112  */
 113 #define ICON_SIZE_FOR_LARGE_EMBEDDED_TEXT 55
 114 
 115 #define SNAP_HORIZONTAL(func,x) ((func ((double)((x) - DESKTOP_PAD_HORIZONTAL) / SNAP_SIZE_X) * SNAP_SIZE_X) + DESKTOP_PAD_HORIZONTAL)
 116 #define SNAP_VERTICAL(func, y) ((func ((double)((y) - DESKTOP_PAD_VERTICAL) / SNAP_SIZE_Y) * SNAP_SIZE_Y) + DESKTOP_PAD_VERTICAL)
 117 
 118 #define SNAP_NEAREST_HORIZONTAL(x) SNAP_HORIZONTAL (floor, x + .5)
 119 #define SNAP_NEAREST_VERTICAL(y) SNAP_VERTICAL (floor, y + .5)
 120 
 121 #define SNAP_CEIL_HORIZONTAL(x) SNAP_HORIZONTAL (ceil, x)
 122 #define SNAP_CEIL_VERTICAL(y) SNAP_VERTICAL (ceil, y)
 123 
 124 /* Copied from NautilusCanvasContainer */
 125 #define NAUTILUS_CANVAS_CONTAINER_SEARCH_DIALOG_TIMEOUT 5
 126 
 127 /* Copied from NautilusFile */
 128 #define UNDEFINED_TIME ((time_t) (-1))
 129 
 130 enum {
 131 	ACTION_ACTIVATE,
 132 	ACTION_MENU,
 133 	LAST_ACTION
 134 };
 135 
 136 typedef struct {
 137 	GList *selection;
 138 	char *action_descriptions[LAST_ACTION];
 139 } NautilusCanvasContainerAccessiblePrivate;
 140 
 141 static AtkObject *   get_accessible                                 (GtkWidget *widget);
 142 
 143 static void          preview_selected_items                         (NautilusCanvasContainer *container);
 144 static void          activate_selected_items                        (NautilusCanvasContainer *container);
 145 static void          activate_selected_items_alternate              (NautilusCanvasContainer *container,
 146 								     NautilusCanvasIcon          *icon);
 147 static void          compute_stretch                                (StretchState          *start,
 148 								     StretchState          *current);
 149 static NautilusCanvasIcon *get_first_selected_icon                        (NautilusCanvasContainer *container);
 150 static NautilusCanvasIcon *get_nth_selected_icon                          (NautilusCanvasContainer *container,
 151 									 int                    index);
 152 static gboolean      has_multiple_selection                         (NautilusCanvasContainer *container);
 153 static gboolean      all_selected                                   (NautilusCanvasContainer *container);
 154 static gboolean      has_selection                                  (NautilusCanvasContainer *container);
 155 static void          icon_destroy                                   (NautilusCanvasContainer *container,
 156 								       NautilusCanvasIcon          *icon);
 157 static void          end_renaming_mode                              (NautilusCanvasContainer *container,
 158 								     gboolean               commit);
 159 static NautilusCanvasIcon *get_icon_being_renamed                         (NautilusCanvasContainer *container);
 160 static void          finish_adding_new_icons                        (NautilusCanvasContainer *container);
 161 static inline void   icon_get_bounding_box                          (NautilusCanvasIcon          *icon,
 162 								       int                   *x1_return,
 163 								       int                   *y1_return,
 164 								       int                   *x2_return,
 165 								       int                   *y2_return,
 166 								       NautilusCanvasItemBoundsUsage usage);
 167 static gboolean      is_renaming                                    (NautilusCanvasContainer *container);
 168 static gboolean      is_renaming_pending                            (NautilusCanvasContainer *container);
 169 static void          process_pending_icon_to_rename                 (NautilusCanvasContainer *container);
 170 static void          nautilus_canvas_container_stop_monitor_top_left  (NautilusCanvasContainer *container,
 171 								       NautilusCanvasIconData      *data,
 172 								       gconstpointer          client);
 173 static void          nautilus_canvas_container_start_monitor_top_left (NautilusCanvasContainer *container,
 174 								       NautilusCanvasIconData      *data,
 175 								       gconstpointer          client,
 176 								       gboolean               large_text);
 177 static void          handle_hadjustment_changed                     (GtkAdjustment         *adjustment,
 178 								     NautilusCanvasContainer *container);
 179 static void          handle_vadjustment_changed                     (GtkAdjustment         *adjustment,
 180 								     NautilusCanvasContainer *container);
 181 static GList *       nautilus_canvas_container_get_selected_icons (NautilusCanvasContainer *container);
 182 static void          nautilus_canvas_container_update_visible_icons   (NautilusCanvasContainer *container);
 183 static void          reveal_icon                                    (NautilusCanvasContainer *container,
 184 								       NautilusCanvasIcon *icon);
 185 
 186 static void	     nautilus_canvas_container_set_rtl_positions (NautilusCanvasContainer *container);
 187 static double	     get_mirror_x_position                     (NautilusCanvasContainer *container,
 188 								NautilusCanvasIcon *icon,
 189 								double x);
 190 static void         text_ellipsis_limit_changed_container_callback  (gpointer callback_data);
 191 
 192 static int compare_icons_horizontal (NautilusCanvasContainer *container,
 193 				       NautilusCanvasIcon *icon_a,
 194 				       NautilusCanvasIcon *icon_b);
 195 
 196 static int compare_icons_vertical (NautilusCanvasContainer *container,
 197 				     NautilusCanvasIcon *icon_a,
 198 				     NautilusCanvasIcon *icon_b);
 199 
 200 static void store_layout_timestamps_now (NautilusCanvasContainer *container);
 201 
 202 static const char *nautilus_canvas_container_accessible_action_names[] = {
 203 	"activate",
 204 	"menu",
 205 	NULL
 206 };
 207 
 208 static const char *nautilus_canvas_container_accessible_action_descriptions[] = {
 209 	"Activate selected items",
 210 	"Popup context menu",
 211 	NULL
 212 };
 213 
 214 G_DEFINE_TYPE (NautilusCanvasContainer, nautilus_canvas_container, EEL_TYPE_CANVAS);
 215 
 216 /* The NautilusCanvasContainer signals.  */
 217 enum {
 218 	ACTIVATE,
 219 	ACTIVATE_ALTERNATE,
 220 	ACTIVATE_PREVIEWER,
 221 	BAND_SELECT_STARTED,
 222 	BAND_SELECT_ENDED,
 223 	BUTTON_PRESS,
 224 	CAN_ACCEPT_ITEM,
 225 	CONTEXT_CLICK_BACKGROUND,
 226 	CONTEXT_CLICK_SELECTION,
 227 	MIDDLE_CLICK,
 228 	GET_CONTAINER_URI,
 229 	GET_ICON_URI,
 230 	GET_ICON_DROP_TARGET_URI,
 231 	GET_STORED_ICON_POSITION,
 232 	ICON_POSITION_CHANGED,
 233 	GET_STORED_LAYOUT_TIMESTAMP,
 234 	STORE_LAYOUT_TIMESTAMP,
 235 	ICON_RENAME_STARTED,
 236 	ICON_RENAME_ENDED,
 237 	ICON_STRETCH_STARTED,
 238 	ICON_STRETCH_ENDED,
 239 	LAYOUT_CHANGED,
 240 	MOVE_COPY_ITEMS,
 241 	HANDLE_NETSCAPE_URL,
 242 	HANDLE_URI_LIST,
 243 	HANDLE_TEXT,
 244 	HANDLE_RAW,
 245 	SELECTION_CHANGED,
 246 	ICON_ADDED,
 247 	ICON_REMOVED,
 248 	CLEARED,
 249 	LAST_SIGNAL
 250 };
 251 
 252 typedef struct {
 253 	int **icon_grid;
 254 	int *grid_memory;
 255 	int num_rows;
 256 	int num_columns;
 257 	gboolean tight;
 258 } PlacementGrid;
 259 
 260 static guint signals[LAST_SIGNAL];
 261 
 262 /* Functions dealing with NautilusIcons.  */
 263 
 264 static void
 265 icon_free (NautilusCanvasIcon *icon)
 266 {
 267 	/* Destroy this icon item; the parent will unref it. */
 268 	eel_canvas_item_destroy (EEL_CANVAS_ITEM (icon->item));
 269 	g_free (icon);
 270 }
 271 
 272 static gboolean
 273 icon_is_positioned (const NautilusCanvasIcon *icon)
 274 {
 275 	return icon->x != ICON_UNPOSITIONED_VALUE && icon->y != ICON_UNPOSITIONED_VALUE;
 276 }
 277 
 278 
 279 /* x, y are the top-left coordinates of the icon. */
 280 static void
 281 icon_set_position (NautilusCanvasIcon *icon,
 282 		     double x, double y)
 283 {	
 284 	NautilusCanvasContainer *container;
 285 	double pixels_per_unit;	
 286 	int container_left, container_top, container_right, container_bottom;
 287 	int x1, x2, y1, y2;
 288 	int container_x, container_y, container_width, container_height;
 289 	EelDRect icon_bounds;
 290 	int item_width, item_height;
 291 	int height_above, width_left;
 292 	int min_x, max_x, min_y, max_y;
 293 
 294 	if (icon->x == x && icon->y == y) {
 295 		return;
 296 	}
 297 
 298 	container = NAUTILUS_CANVAS_CONTAINER (EEL_CANVAS_ITEM (icon->item)->canvas);
 299 
 300 	if (icon == get_icon_being_renamed (container)) {
 301 		end_renaming_mode (container, TRUE);
 302 	}
 303 
 304 	if (nautilus_canvas_container_get_is_fixed_size (container)) {
 305 		/*  FIXME: This should be:
 306 		    
 307 		    container_x = GTK_WIDGET (container)->allocation.x;
 308 		    container_y = GTK_WIDGET (container)->allocation.y;
 309 		    container_width = GTK_WIDGET (container)->allocation.width;
 310 		    container_height = GTK_WIDGET (container)->allocation.height;
 311 
 312 		    But for some reason the widget allocation is sometimes not done
 313 		    at startup, and the allocation is then only 45x60. which is
 314 		    really bad.
 315 
 316 		    For now, we have a cheesy workaround:
 317 		*/
 318 		container_x = 0;
 319 		container_y = 0;
 320 		container_width = gdk_screen_width () - container_x
 321 			- container->details->left_margin
 322 			- container->details->right_margin;
 323 		container_height = gdk_screen_height () - container_y
 324 			- container->details->top_margin
 325 			- container->details->bottom_margin;
 326 		pixels_per_unit = EEL_CANVAS (container)->pixels_per_unit;
 327 		/* Clip the position of the icon within our desktop bounds */
 328 		container_left = container_x / pixels_per_unit;
 329 		container_top =  container_y / pixels_per_unit;
 330 		container_right = container_left + container_width / pixels_per_unit;
 331 		container_bottom = container_top + container_height / pixels_per_unit;
 332 
 333 		icon_get_bounding_box (icon, &x1, &y1, &x2, &y2,
 334 				       BOUNDS_USAGE_FOR_ENTIRE_ITEM);
 335 		item_width = x2 - x1;
 336 		item_height = y2 - y1;
 337 
 338 		icon_bounds = nautilus_canvas_item_get_icon_rectangle (icon->item);
 339 
 340 		/* determine icon rectangle relative to item rectangle */
 341 		height_above = icon_bounds.y0 - y1;
 342 		width_left = icon_bounds.x0 - x1;
 343 
 344 		min_x = container_left + DESKTOP_PAD_HORIZONTAL + width_left;
 345 		max_x = container_right - DESKTOP_PAD_HORIZONTAL - item_width + width_left;
 346 		x = CLAMP (x, min_x, max_x);
 347 
 348 		min_y = container_top + height_above + DESKTOP_PAD_VERTICAL;
 349 		max_y = container_bottom - DESKTOP_PAD_VERTICAL - item_height + height_above;
 350 		y = CLAMP (y, min_y, max_y);
 351 	}
 352 
 353 	if (icon->x == ICON_UNPOSITIONED_VALUE) {
 354 		icon->x = 0;
 355 	}
 356 	if (icon->y == ICON_UNPOSITIONED_VALUE) {
 357 		icon->y = 0;
 358 	}
 359 	
 360 	eel_canvas_item_move (EEL_CANVAS_ITEM (icon->item),
 361 			      x - icon->x,
 362 			      y - icon->y);
 363 
 364 	icon->x = x;
 365 	icon->y = y;
 366 }
 367 
 368 static void
 369 icon_get_size (NautilusCanvasContainer *container,
 370 		 NautilusCanvasIcon *icon,
 371 		 guint *size)
 372 {
 373 	if (size != NULL) {
 374 		*size = MAX (nautilus_get_icon_size_for_zoom_level (container->details->zoom_level)
 375 			     * icon->scale, NAUTILUS_ICON_SIZE_SMALLEST);
 376 	}
 377 }
 378 
 379 /* The icon_set_size function is used by the stretching user
 380  * interface, which currently stretches in a way that keeps the aspect
 381  * ratio. Later we might have a stretching interface that stretches Y
 382  * separate from X and we will change this around.
 383  */
 384 static void
 385 icon_set_size (NautilusCanvasContainer *container,
 386 		 NautilusCanvasIcon *icon,
 387 		 guint icon_size,
 388 		 gboolean snap,
 389 		 gboolean update_position)
 390 {
 391 	guint old_size;
 392 	double scale;
 393 
 394 	icon_get_size (container, icon, &old_size);
 395 	if (icon_size == old_size) {
 396 		return;
 397 	}
 398 
 399 	scale = (double) icon_size /
 400 		nautilus_get_icon_size_for_zoom_level
 401 		(container->details->zoom_level);
 402 	nautilus_canvas_container_move_icon (container, icon,
 403 					       icon->x, icon->y,
 404 					       scale, FALSE,
 405 					       snap, update_position);
 406 }
 407 
 408 static void
 409 icon_raise (NautilusCanvasIcon *icon)
 410 {
 411 	EelCanvasItem *item, *band;
 412 	
 413 	item = EEL_CANVAS_ITEM (icon->item);
 414 	band = NAUTILUS_CANVAS_CONTAINER (item->canvas)->details->rubberband_info.selection_rectangle;
 415 	
 416 	eel_canvas_item_send_behind (item, band);
 417 }
 418 
 419 static void
 420 emit_stretch_started (NautilusCanvasContainer *container, NautilusCanvasIcon *icon)
 421 {
 422 	g_signal_emit (container,
 423 		       signals[ICON_STRETCH_STARTED], 0,
 424 		       icon->data);
 425 }
 426 
 427 static void
 428 emit_stretch_ended (NautilusCanvasContainer *container, NautilusCanvasIcon *icon)
 429 {
 430 	g_signal_emit (container,
 431 		       signals[ICON_STRETCH_ENDED], 0,
 432 		       icon->data);
 433 }
 434 
 435 static void
 436 icon_toggle_selected (NautilusCanvasContainer *container,
 437 		      NautilusCanvasIcon *icon)
 438 {		
 439 	end_renaming_mode (container, TRUE);
 440 
 441 	icon->is_selected = !icon->is_selected;
 442 	eel_canvas_item_set (EEL_CANVAS_ITEM (icon->item),
 443 			     "highlighted_for_selection", (gboolean) icon->is_selected,
 444 			     NULL);
 445 
 446 	/* If the icon is deselected, then get rid of the stretch handles.
 447 	 * No harm in doing the same if the item is newly selected.
 448 	 */
 449 	if (icon == container->details->stretch_icon) {
 450 		container->details->stretch_icon = NULL;
 451 		nautilus_canvas_item_set_show_stretch_handles (icon->item, FALSE);
 452 		/* snap the icon if necessary */
 453 		if (container->details->keep_aligned) {
 454 			nautilus_canvas_container_move_icon (container,
 455 							       icon,
 456 							       icon->x, icon->y,
 457 							       icon->scale,
 458 							       FALSE, TRUE, TRUE);
 459 		}
 460 		
 461 		emit_stretch_ended (container, icon);
 462 	}
 463 
 464 	/* Raise each newly-selected icon to the front as it is selected. */
 465 	if (icon->is_selected) {
 466 		icon_raise (icon);
 467 	}
 468 }
 469 
 470 /* Select an icon. Return TRUE if selection has changed. */
 471 static gboolean
 472 icon_set_selected (NautilusCanvasContainer *container,
 473 		     NautilusCanvasIcon *icon,
 474 		     gboolean select)
 475 {
 476 	g_assert (select == FALSE || select == TRUE);
 477 	g_assert (icon->is_selected == FALSE || icon->is_selected == TRUE);
 478 
 479 	if (select == icon->is_selected) {
 480 		return FALSE;
 481 	}
 482 
 483 	icon_toggle_selected (container, icon);
 484 	g_assert (select == icon->is_selected);
 485 	return TRUE;
 486 }
 487 
 488 static inline void
 489 icon_get_bounding_box (NautilusCanvasIcon *icon,
 490 		       int *x1_return, int *y1_return,
 491 		       int *x2_return, int *y2_return,
 492 		       NautilusCanvasItemBoundsUsage usage)
 493 {
 494 	double x1, y1, x2, y2;
 495 
 496 	if (usage == BOUNDS_USAGE_FOR_DISPLAY) {
 497 		eel_canvas_item_get_bounds (EEL_CANVAS_ITEM (icon->item),
 498 					    &x1, &y1, &x2, &y2);
 499 	} else if (usage == BOUNDS_USAGE_FOR_LAYOUT) {
 500 		nautilus_canvas_item_get_bounds_for_layout (icon->item,
 501 								   &x1, &y1, &x2, &y2);
 502 	} else if (usage == BOUNDS_USAGE_FOR_ENTIRE_ITEM) {
 503 		nautilus_canvas_item_get_bounds_for_entire_item (icon->item,
 504 									&x1, &y1, &x2, &y2);
 505 	} else {
 506 		g_assert_not_reached ();
 507 	}
 508 
 509 	if (x1_return != NULL) {
 510 		*x1_return = x1;
 511 	}
 512 
 513 	if (y1_return != NULL) {
 514 		*y1_return = y1;
 515 	}
 516 
 517 	if (x2_return != NULL) {
 518 		*x2_return = x2;
 519 	}
 520 
 521 	if (y2_return != NULL) {
 522 		*y2_return = y2;
 523 	}
 524 }
 525 
 526 /* Utility functions for NautilusCanvasContainer.  */
 527 
 528 gboolean
 529 nautilus_canvas_container_scroll (NautilusCanvasContainer *container,
 530 				  int delta_x, int delta_y)
 531 {
 532 	GtkAdjustment *hadj, *vadj;
 533 	int old_h_value, old_v_value;
 534 
 535 	hadj = gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (container));
 536 	vadj = gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (container));
 537 
 538 	/* Store the old ajustment values so we can tell if we
 539 	 * ended up actually scrolling. We may not have in a case
 540 	 * where the resulting value got pinned to the adjustment
 541 	 * min or max.
 542 	 */
 543 	old_h_value = gtk_adjustment_get_value (hadj);
 544 	old_v_value = gtk_adjustment_get_value (vadj);
 545 	
 546 	gtk_adjustment_set_value (hadj, gtk_adjustment_get_value (hadj) + delta_x);
 547 	gtk_adjustment_set_value (vadj, gtk_adjustment_get_value (vadj) + delta_y);
 548 
 549 	/* return TRUE if we did scroll */
 550 	return gtk_adjustment_get_value (hadj) != old_h_value || gtk_adjustment_get_value (vadj) != old_v_value;
 551 }
 552 
 553 static void
 554 pending_icon_to_reveal_destroy_callback (NautilusCanvasItem *item,
 555 					   NautilusCanvasContainer *container)
 556 {
 557 	g_assert (NAUTILUS_IS_CANVAS_CONTAINER (container));
 558 	g_assert (container->details->pending_icon_to_reveal != NULL);
 559 	g_assert (container->details->pending_icon_to_reveal->item == item);
 560 
 561 	container->details->pending_icon_to_reveal = NULL;
 562 }
 563 
 564 static NautilusCanvasIcon *
 565 get_pending_icon_to_reveal (NautilusCanvasContainer *container)
 566 {
 567 	return container->details->pending_icon_to_reveal;
 568 }
 569 
 570 static void
 571 set_pending_icon_to_reveal (NautilusCanvasContainer *container, NautilusCanvasIcon *icon)
 572 {
 573 	NautilusCanvasIcon *old_icon;
 574 	
 575 	old_icon = container->details->pending_icon_to_reveal;
 576 	
 577 	if (icon == old_icon) {
 578 		return;
 579 	}
 580 	
 581 	if (old_icon != NULL) {
 582 		g_signal_handlers_disconnect_by_func
 583 			(old_icon->item,
 584 			 G_CALLBACK (pending_icon_to_reveal_destroy_callback),
 585 			 container);
 586 	}
 587 	
 588 	if (icon != NULL) {
 589 		g_signal_connect (icon->item, "destroy",
 590 				  G_CALLBACK (pending_icon_to_reveal_destroy_callback),
 591 				  container);
 592 	}
 593 	
 594 	container->details->pending_icon_to_reveal = icon;
 595 }
 596 
 597 static void
 598 item_get_canvas_bounds (EelCanvasItem *item,
 599 			EelIRect *bounds,
 600 			gboolean safety_pad)
 601 {
 602 	EelDRect world_rect;
 603 	
 604 	eel_canvas_item_get_bounds (item,
 605 				    &world_rect.x0,
 606 				    &world_rect.y0,
 607 				    &world_rect.x1,
 608 				    &world_rect.y1);
 609 	eel_canvas_item_i2w (item->parent,
 610 			     &world_rect.x0,
 611 			     &world_rect.y0);
 612 	eel_canvas_item_i2w (item->parent,
 613 			     &world_rect.x1,
 614 			     &world_rect.y1);
 615 	if (safety_pad) {
 616 		world_rect.x0 -= ICON_PAD_LEFT + ICON_PAD_RIGHT;
 617 		world_rect.x1 += ICON_PAD_LEFT + ICON_PAD_RIGHT;
 618 
 619 		world_rect.y0 -= ICON_PAD_TOP + ICON_PAD_BOTTOM;
 620 		world_rect.y1 += ICON_PAD_TOP + ICON_PAD_BOTTOM;
 621 	}
 622 
 623 	eel_canvas_w2c (item->canvas,
 624 			world_rect.x0,
 625 			world_rect.y0,
 626 			&bounds->x0,
 627 			&bounds->y0);
 628 	eel_canvas_w2c (item->canvas,
 629 			world_rect.x1,
 630 			world_rect.y1,
 631 			&bounds->x1,
 632 			&bounds->y1);
 633 }
 634 
 635 static void
 636 icon_get_row_and_column_bounds (NautilusCanvasContainer *container,
 637 				NautilusCanvasIcon *icon,
 638 				EelIRect *bounds,
 639 				gboolean safety_pad)
 640 {
 641 	GList *p;
 642 	NautilusCanvasIcon *one_icon;
 643 	EelIRect one_bounds;
 644 
 645 	item_get_canvas_bounds (EEL_CANVAS_ITEM (icon->item), bounds, safety_pad);
 646 
 647 	for (p = container->details->icons; p != NULL; p = p->next) {
 648 		one_icon = p->data;
 649 
 650 		if (icon == one_icon) {
 651 			continue;
 652 		}
 653 
 654 		if (compare_icons_horizontal (container, icon, one_icon) == 0) {
 655 			item_get_canvas_bounds (EEL_CANVAS_ITEM (one_icon->item), &one_bounds, safety_pad);
 656 			bounds->x0 = MIN (bounds->x0, one_bounds.x0);
 657 			bounds->x1 = MAX (bounds->x1, one_bounds.x1);
 658 		}
 659 
 660 		if (compare_icons_vertical (container, icon, one_icon) == 0) {
 661 			item_get_canvas_bounds (EEL_CANVAS_ITEM (one_icon->item), &one_bounds, safety_pad);
 662 			bounds->y0 = MIN (bounds->y0, one_bounds.y0);
 663 			bounds->y1 = MAX (bounds->y1, one_bounds.y1);
 664 		}
 665 	}
 666 
 667 
 668 }
 669 
 670 static void
 671 reveal_icon (NautilusCanvasContainer *container,
 672 	     NautilusCanvasIcon *icon)
 673 {
 674 	GtkAllocation allocation;
 675 	GtkAdjustment *hadj, *vadj;
 676 	EelIRect bounds;
 677 
 678 	if (!icon_is_positioned (icon)) {
 679 		set_pending_icon_to_reveal (container, icon);
 680 		return;
 681 	}
 682 	
 683 	set_pending_icon_to_reveal (container, NULL);
 684 
 685 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
 686 
 687 	hadj = gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (container));
 688 	vadj = gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (container));
 689 
 690 	if (nautilus_canvas_container_is_auto_layout (container)) {
 691 		/* ensure that we reveal the entire row/column */
 692 		icon_get_row_and_column_bounds (container, icon, &bounds, TRUE);
 693 	} else {
 694 		item_get_canvas_bounds (EEL_CANVAS_ITEM (icon->item), &bounds, TRUE);
 695 	}
 696 	if (bounds.y0 < gtk_adjustment_get_value (vadj)) {
 697 		gtk_adjustment_set_value (vadj, bounds.y0);
 698 	} else if (bounds.y1 > gtk_adjustment_get_value (vadj) + allocation.height) {
 699 		gtk_adjustment_set_value
 700 			(vadj, bounds.y1 - allocation.height);
 701 	}
 702 
 703 	if (bounds.x0 < gtk_adjustment_get_value (hadj)) {
 704 		gtk_adjustment_set_value (hadj, bounds.x0);
 705 	} else if (bounds.x1 > gtk_adjustment_get_value (hadj) + allocation.width) {
 706 		gtk_adjustment_set_value
 707 			(hadj, bounds.x1 - allocation.width);
 708 	}
 709 }
 710 
 711 static void
 712 process_pending_icon_to_reveal (NautilusCanvasContainer *container)
 713 {
 714 	NautilusCanvasIcon *pending_icon_to_reveal;
 715 	
 716 	pending_icon_to_reveal = get_pending_icon_to_reveal (container);
 717 	
 718 	if (pending_icon_to_reveal != NULL) {
 719 		reveal_icon (container, pending_icon_to_reveal);
 720 	}
 721 }
 722 
 723 static gboolean
 724 keyboard_icon_reveal_timeout_callback (gpointer data)
 725 {
 726 	NautilusCanvasContainer *container;
 727 	NautilusCanvasIcon *icon;
 728 
 729 	container = NAUTILUS_CANVAS_CONTAINER (data);
 730 	icon = container->details->keyboard_icon_to_reveal;
 731 
 732 	g_assert (icon != NULL);
 733 
 734 	/* Only reveal the icon if it's still the keyboard focus or if
 735 	 * it's still selected. Someone originally thought we should
 736 	 * cancel this reveal if the user manages to sneak a direct
 737 	 * scroll in before the timeout fires, but we later realized
 738 	 * this wouldn't actually be an improvement 
 739 	 * (see bugzilla.gnome.org 40612).
 740 	 */
 741 	if (icon == container->details->keyboard_focus
 742 	    || icon->is_selected) {
 743 		reveal_icon (container, icon);
 744 	}
 745 	container->details->keyboard_icon_reveal_timer_id = 0;
 746 
 747 	return FALSE;
 748 }
 749 
 750 static void
 751 unschedule_keyboard_icon_reveal (NautilusCanvasContainer *container)
 752 {
 753 	NautilusCanvasContainerDetails *details;
 754 
 755 	details = container->details;
 756 
 757 	if (details->keyboard_icon_reveal_timer_id != 0) {
 758 		g_source_remove (details->keyboard_icon_reveal_timer_id);
 759 	}
 760 }
 761 
 762 static void
 763 schedule_keyboard_icon_reveal (NautilusCanvasContainer *container,
 764 				 NautilusCanvasIcon *icon)
 765 {
 766 	NautilusCanvasContainerDetails *details;
 767 
 768 	details = container->details;
 769 
 770 	unschedule_keyboard_icon_reveal (container);
 771 
 772 	details->keyboard_icon_to_reveal = icon;
 773 	details->keyboard_icon_reveal_timer_id
 774 		= g_timeout_add (KEYBOARD_ICON_REVEAL_TIMEOUT,
 775 				 keyboard_icon_reveal_timeout_callback,
 776 				 container);
 777 }
 778 
 779 static void
 780 clear_keyboard_focus (NautilusCanvasContainer *container)
 781 {
 782         if (container->details->keyboard_focus != NULL) {
 783 		eel_canvas_item_set (EEL_CANVAS_ITEM (container->details->keyboard_focus->item),
 784 				     "highlighted_as_keyboard_focus", 0,
 785 				     NULL);
 786 	}
 787 	
 788 	container->details->keyboard_focus = NULL;
 789 }
 790 
 791 static void inline
 792 emit_atk_focus_tracker_notify (NautilusCanvasIcon *icon)
 793 {
 794 	AtkObject *atk_object = atk_gobject_accessible_for_object (G_OBJECT (icon->item));
 795 	atk_focus_tracker_notify (atk_object);
 796 }
 797 
 798 /* Set @icon as the icon currently selected for keyboard operations. */
 799 static void
 800 set_keyboard_focus (NautilusCanvasContainer *container,
 801 		    NautilusCanvasIcon *icon)
 802 {
 803 	g_assert (icon != NULL);
 804 
 805 	if (icon == container->details->keyboard_focus) {
 806 		return;
 807 	}
 808 
 809 	clear_keyboard_focus (container);
 810 
 811 	container->details->keyboard_focus = icon;
 812 
 813 	eel_canvas_item_set (EEL_CANVAS_ITEM (container->details->keyboard_focus->item),
 814 			     "highlighted_as_keyboard_focus", 1,
 815 			     NULL);
 816 
 817 	emit_atk_focus_tracker_notify (icon);
 818 }
 819 
 820 static void
 821 set_keyboard_rubberband_start (NautilusCanvasContainer *container,
 822 			       NautilusCanvasIcon *icon)
 823 {
 824 	container->details->keyboard_rubberband_start = icon;
 825 }
 826 
 827 static void
 828 clear_keyboard_rubberband_start (NautilusCanvasContainer *container)
 829 {
 830 	container->details->keyboard_rubberband_start = NULL;
 831 }
 832 
 833 /* carbon-copy of eel_canvas_group_bounds(), but
 834  * for NautilusCanvasContainerItems it returns the
 835  * bounds for the “entire item”.
 836  */
 837 static void
 838 get_icon_bounds_for_canvas_bounds (EelCanvasGroup *group,
 839 				     double *x1, double *y1,
 840 				     double *x2, double *y2,
 841 				     NautilusCanvasItemBoundsUsage usage)
 842 {
 843 	EelCanvasItem *child;
 844 	GList *list;
 845 	double tx1, ty1, tx2, ty2;
 846 	double minx, miny, maxx, maxy;
 847 	int set;
 848 
 849 	/* Get the bounds of the first visible item */
 850 
 851 	child = NULL; /* Unnecessary but eliminates a warning. */
 852 
 853 	set = FALSE;
 854 
 855 	for (list = group->item_list; list; list = list->next) {
 856 		child = list->data;
 857 
 858 		if (!NAUTILUS_IS_CANVAS_ITEM (child)) {
 859 			continue;
 860 		}
 861 
 862 		if (child->flags & EEL_CANVAS_ITEM_VISIBLE) {
 863 			set = TRUE;
 864 			if (!NAUTILUS_IS_CANVAS_ITEM (child) ||
 865 			    usage == BOUNDS_USAGE_FOR_DISPLAY) {
 866 				eel_canvas_item_get_bounds (child, &minx, &miny, &maxx, &maxy);
 867 			} else if (usage == BOUNDS_USAGE_FOR_LAYOUT) {
 868 				nautilus_canvas_item_get_bounds_for_layout (NAUTILUS_CANVAS_ITEM (child),
 869 										   &minx, &miny, &maxx, &maxy);
 870 			} else if (usage == BOUNDS_USAGE_FOR_ENTIRE_ITEM) {
 871 				nautilus_canvas_item_get_bounds_for_entire_item (NAUTILUS_CANVAS_ITEM (child),
 872 											&minx, &miny, &maxx, &maxy);
 873 			} else {
 874 				g_assert_not_reached ();
 875 			}
 876 			break;
 877 		}
 878 	}
 879 
 880 	/* If there were no visible items, return an empty bounding box */
 881 
 882 	if (!set) {
 883 		*x1 = *y1 = *x2 = *y2 = 0.0;
 884 		return;
 885 	}
 886 
 887 	/* Now we can grow the bounds using the rest of the items */
 888 
 889 	list = list->next;
 890 
 891 	for (; list; list = list->next) {
 892 		child = list->data;
 893 
 894 		if (!NAUTILUS_IS_CANVAS_ITEM (child)) {
 895 			continue;
 896 		}
 897 
 898 		if (!(child->flags & EEL_CANVAS_ITEM_VISIBLE))
 899 			continue;
 900 
 901 		if (!NAUTILUS_IS_CANVAS_ITEM (child) ||
 902 		    usage == BOUNDS_USAGE_FOR_DISPLAY) {
 903 			eel_canvas_item_get_bounds (child, &tx1, &ty1, &tx2, &ty2);
 904 		} else if (usage == BOUNDS_USAGE_FOR_LAYOUT) {
 905 			nautilus_canvas_item_get_bounds_for_layout (NAUTILUS_CANVAS_ITEM (child),
 906 									   &tx1, &ty1, &tx2, &ty2);
 907 		} else if (usage == BOUNDS_USAGE_FOR_ENTIRE_ITEM) {
 908 			nautilus_canvas_item_get_bounds_for_entire_item (NAUTILUS_CANVAS_ITEM (child),
 909 										&tx1, &ty1, &tx2, &ty2);
 910 		} else {
 911 			g_assert_not_reached ();
 912 		}
 913 
 914 		if (tx1 < minx)
 915 			minx = tx1;
 916 
 917 		if (ty1 < miny)
 918 			miny = ty1;
 919 
 920 		if (tx2 > maxx)
 921 			maxx = tx2;
 922 
 923 		if (ty2 > maxy)
 924 			maxy = ty2;
 925 	}
 926 
 927 	/* Make the bounds be relative to our parent's coordinate system */
 928 
 929 	if (EEL_CANVAS_ITEM (group)->parent) {
 930 		minx += group->xpos;
 931 		miny += group->ypos;
 932 		maxx += group->xpos;
 933 		maxy += group->ypos;
 934 	}
 935 	
 936 	if (x1 != NULL) {
 937 		*x1 = minx;
 938 	}
 939 
 940 	if (y1 != NULL) {
 941 		*y1 = miny;
 942 	}
 943 
 944 	if (x2 != NULL) {
 945 		*x2 = maxx;
 946 	}
 947 
 948 	if (y2 != NULL) {
 949 		*y2 = maxy;
 950 	}
 951 }
 952 
 953 static void
 954 get_all_icon_bounds (NautilusCanvasContainer *container,
 955 		     double *x1, double *y1,
 956 		     double *x2, double *y2,
 957 		     NautilusCanvasItemBoundsUsage usage)
 958 {
 959 	/* FIXME bugzilla.gnome.org 42477: Do we have to do something about the rubberband
 960 	 * here? Any other non-icon items?
 961 	 */
 962 	get_icon_bounds_for_canvas_bounds (EEL_CANVAS_GROUP (EEL_CANVAS (container)->root),
 963 					     x1, y1, x2, y2, usage);
 964 }
 965 
 966 /* Don't preserve visible white space the next time the scroll region
 967  * is recomputed when the container is not empty. */
 968 void
 969 nautilus_canvas_container_reset_scroll_region (NautilusCanvasContainer *container)
 970 {
 971 	container->details->reset_scroll_region_trigger = TRUE;
 972 }
 973 
 974 /* Set a new scroll region without eliminating any of the currently-visible area. */
 975 static void
 976 canvas_set_scroll_region_include_visible_area (EelCanvas *canvas,
 977 					       double x1, double y1,
 978 					       double x2, double y2)
 979 {
 980 	double old_x1, old_y1, old_x2, old_y2;
 981 	double old_scroll_x, old_scroll_y;
 982 	double height, width;
 983 	GtkAllocation allocation;
 984 	
 985 	eel_canvas_get_scroll_region (canvas, &old_x1, &old_y1, &old_x2, &old_y2);
 986 	gtk_widget_get_allocation (GTK_WIDGET (canvas), &allocation);
 987 
 988 	width = (allocation.width) / canvas->pixels_per_unit;
 989 	height = (allocation.height) / canvas->pixels_per_unit;
 990 
 991 	old_scroll_x = gtk_adjustment_get_value (gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (canvas)));
 992 	old_scroll_y = gtk_adjustment_get_value (gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (canvas)));
 993 
 994 	x1 = MIN (x1, old_x1 + old_scroll_x);
 995 	y1 = MIN (y1, old_y1 + old_scroll_y);
 996 	x2 = MAX (x2, old_x1 + old_scroll_x + width);
 997 	y2 = MAX (y2, old_y1 + old_scroll_y + height);
 998 
 999 	eel_canvas_set_scroll_region
1000 		(canvas, x1, y1, x2, y2);
1001 }
1002 
1003 void
1004 nautilus_canvas_container_update_scroll_region (NautilusCanvasContainer *container)
1005 {
1006 	double x1, y1, x2, y2;
1007 	double pixels_per_unit;
1008 	GtkAdjustment *hadj, *vadj;
1009 	float step_increment;
1010 	gboolean reset_scroll_region;
1011 	GtkAllocation allocation;
1012 
1013 	pixels_per_unit = EEL_CANVAS (container)->pixels_per_unit;
1014 
1015 	if (nautilus_canvas_container_get_is_fixed_size (container)) {
1016 		/* Set the scroll region to the size of the container allocation */
1017 		gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1018 		eel_canvas_set_scroll_region
1019 			(EEL_CANVAS (container),
1020 			 (double) - container->details->left_margin / pixels_per_unit,
1021 			 (double) - container->details->top_margin / pixels_per_unit,
1022 			 ((double) (allocation.width - 1)
1023 			  - container->details->left_margin
1024 			  - container->details->right_margin)
1025 			 / pixels_per_unit,
1026 			 ((double) (allocation.height - 1)
1027 			  - container->details->top_margin
1028 			  - container->details->bottom_margin)
1029 			 / pixels_per_unit);
1030 		return;
1031 	}
1032 
1033 	reset_scroll_region = container->details->reset_scroll_region_trigger
1034 		|| nautilus_canvas_container_is_empty (container)
1035 		|| nautilus_canvas_container_is_auto_layout (container);
1036 
1037 	/* The trigger is only cleared when container is non-empty, so
1038 	 * callers can reliably reset the scroll region when an item
1039 	 * is added even if extraneous relayouts are called when the
1040 	 * window is still empty.
1041 	 */
1042 	if (!nautilus_canvas_container_is_empty (container)) {
1043 		container->details->reset_scroll_region_trigger = FALSE;
1044 	}
1045 
1046 	get_all_icon_bounds (container, &x1, &y1, &x2, &y2, BOUNDS_USAGE_FOR_ENTIRE_ITEM);
1047 
1048 	/* Add border at the "end"of the layout (i.e. after the icons), to
1049 	 * ensure we get some space when scrolled to the end.
1050 	 * For horizontal layouts, we add a bottom border.
1051 	 * Vertical layout is used by the compact view so the end
1052 	 * depends on the RTL setting.
1053 	 */
1054 	if (nautilus_canvas_container_is_layout_vertical (container)) {
1055 		if (nautilus_canvas_container_is_layout_rtl (container)) {
1056 			x1 -= ICON_PAD_LEFT + CONTAINER_PAD_LEFT;
1057 		} else {
1058 			x2 += ICON_PAD_RIGHT + CONTAINER_PAD_RIGHT;
1059 		}
1060 	} else {
1061 		y2 += ICON_PAD_BOTTOM + CONTAINER_PAD_BOTTOM;
1062 	}
1063 
1064 	/* Auto-layout assumes a 0, 0 scroll origin and at least allocation->width.
1065 	 * Then we lay out to the right or to the left, so
1066 	 * x can be < 0 and > allocation */
1067 	if (nautilus_canvas_container_is_auto_layout (container)) {
1068 		gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1069 		x1 = MIN (x1, 0);
1070 		x2 = MAX (x2, allocation.width / pixels_per_unit);
1071 		y1 = 0;
1072 	} else {
1073 		/* Otherwise we add the padding that is at the start of the
1074 		   layout */
1075 		if (nautilus_canvas_container_is_layout_rtl (container)) {
1076 			x2 += ICON_PAD_RIGHT + CONTAINER_PAD_RIGHT;
1077 		} else {
1078 			x1 -= ICON_PAD_LEFT + CONTAINER_PAD_LEFT;
1079 		}
1080 		y1 -= ICON_PAD_TOP + CONTAINER_PAD_TOP;
1081 	}
1082 
1083 	x2 -= 1;
1084 	x2 = MAX(x1, x2);
1085 
1086 	y2 -= 1;
1087 	y2 = MAX(y1, y2);
1088 
1089 	if (reset_scroll_region) {
1090 		eel_canvas_set_scroll_region
1091 			(EEL_CANVAS (container),
1092 			 x1, y1, x2, y2);
1093 	} else {
1094 		canvas_set_scroll_region_include_visible_area
1095 			(EEL_CANVAS (container),
1096 			 x1, y1, x2, y2);
1097 	}
1098 
1099 	hadj = gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (container));
1100 	vadj = gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (container));
1101 
1102 	/* Scroll by 1/4 icon each time you click. */
1103 	step_increment = nautilus_get_icon_size_for_zoom_level
1104 		(container->details->zoom_level) / 4;
1105 	if (gtk_adjustment_get_step_increment (hadj) != step_increment) {
1106 		gtk_adjustment_set_step_increment (hadj, step_increment);
1107 	}
1108 	if (gtk_adjustment_get_step_increment (vadj) != step_increment) {
1109 		gtk_adjustment_set_step_increment (vadj, step_increment);
1110 	}
1111 }
1112 
1113 static int
1114 compare_icons (gconstpointer a, gconstpointer b, gpointer canvas_container)
1115 {
1116 	NautilusCanvasContainerClass *klass;
1117 	const NautilusCanvasIcon *icon_a, *icon_b;
1118 
1119 	icon_a = a;
1120 	icon_b = b;
1121 	klass  = NAUTILUS_CANVAS_CONTAINER_GET_CLASS (canvas_container);
1122 
1123 	return klass->compare_icons (canvas_container, icon_a->data, icon_b->data);
1124 }
1125 
1126 static void
1127 sort_icons (NautilusCanvasContainer *container,
1128 	      GList                **icons)
1129 {
1130 	NautilusCanvasContainerClass *klass;
1131 
1132 	klass = NAUTILUS_CANVAS_CONTAINER_GET_CLASS (container);
1133 	g_assert (klass->compare_icons != NULL);
1134 
1135 	*icons = g_list_sort_with_data (*icons, compare_icons, container);
1136 }
1137 
1138 static void
1139 resort (NautilusCanvasContainer *container)
1140 {
1141 	sort_icons (container, &container->details->icons);
1142 }
1143 
1144 #if 0
1145 static double
1146 get_grid_width (NautilusCanvasContainer *container)
1147 {
1148 	return STANDARD_ICON_GRID_WIDTH;
1149 }
1150 #endif
1151 typedef struct {
1152 	double width;
1153 	double height;
1154 	double x_offset;
1155 	double y_offset;
1156 } IconPositions;
1157 
1158 static void
1159 lay_down_one_line (NautilusCanvasContainer *container,
1160 		   GList *line_start,
1161 		   GList *line_end,
1162 		   double y,
1163 		   double max_height,
1164 		   GArray *positions,
1165 		   gboolean whole_text)
1166 {
1167 	GList *p;
1168 	NautilusCanvasIcon *icon;
1169 	double x, y_offset;
1170 	IconPositions *position;
1171 	int i;
1172 	gboolean is_rtl;
1173 
1174 	is_rtl = nautilus_canvas_container_is_layout_rtl (container);
1175 
1176 	/* Lay out the icons along the baseline. */
1177 	x = ICON_PAD_LEFT;
1178 	i = 0;
1179 	for (p = line_start; p != line_end; p = p->next) {
1180 		icon = p->data;
1181 
1182 		position = &g_array_index (positions, IconPositions, i++);
1183 		y_offset = position->y_offset;
1184 
1185 		icon_set_position
1186 			(icon,
1187 			 is_rtl ? get_mirror_x_position (container, icon, x + position->x_offset) : x + position->x_offset,
1188 			 y + y_offset);
1189 		nautilus_canvas_item_set_entire_text (icon->item, whole_text);
1190 
1191 		icon->saved_ltr_x = is_rtl ? get_mirror_x_position (container, icon, icon->x) : icon->x;
1192 
1193 		x += position->width;
1194 	}
1195 }
1196 
1197 static void
1198 lay_down_one_column (NautilusCanvasContainer *container,
1199 		     GList *line_start,
1200 		     GList *line_end,
1201 		     double x,
1202 		     double y_start,
1203 		     double y_iter,
1204 		     GArray *positions)
1205 {
1206 	GList *p;
1207 	NautilusCanvasIcon *icon;
1208 	double y;
1209 	IconPositions *position;
1210 	int i;
1211 	gboolean is_rtl;
1212 
1213         is_rtl = nautilus_canvas_container_is_layout_rtl (container);
1214 
1215 	/* Lay out the icons along the baseline. */
1216 	y = y_start;
1217 	i = 0;
1218 	for (p = line_start; p != line_end; p = p->next) {
1219 		icon = p->data;
1220 
1221 		position = &g_array_index (positions, IconPositions, i++);
1222 
1223 		icon_set_position
1224 			(icon,
1225 			 is_rtl ? get_mirror_x_position (container, icon, x + position->x_offset) : x + position->x_offset,
1226 			 y + position->y_offset);
1227 
1228 		icon->saved_ltr_x = is_rtl ? get_mirror_x_position (container, icon, icon->x) : icon->x;
1229 
1230 		y += y_iter;
1231 	}
1232 }
1233 
1234 static void
1235 lay_down_icons_horizontal (NautilusCanvasContainer *container,
1236 			     GList *icons,
1237 			     double start_y)
1238 {
1239 	GList *p, *line_start;
1240 	NautilusCanvasIcon *icon;
1241 	double canvas_width, y;
1242 	GArray *positions;
1243 	IconPositions *position;
1244 	EelDRect bounds;
1245 	EelDRect icon_bounds;
1246 	double max_height_above, max_height_below;
1247 	double height_above, height_below;
1248 	double line_width;
1249 	double grid_width;
1250 	int icon_width;
1251 	int i;
1252 	GtkAllocation allocation;
1253 
1254 	g_assert (NAUTILUS_IS_CANVAS_CONTAINER (container));
1255 
1256 	if (icons == NULL) {
1257 		return;
1258 	}
1259 
1260 	positions = g_array_new (FALSE, FALSE, sizeof (IconPositions));
1261 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1262 	
1263 	/* Lay out icons a line at a time. */
1264 	canvas_width = CANVAS_WIDTH(container, allocation);
1265 
1266 	grid_width = STANDARD_ICON_GRID_WIDTH;
1267 
1268 	line_width = 0;
1269 	line_start = icons;
1270 	y = start_y + CONTAINER_PAD_TOP;
1271 	i = 0;
1272 	
1273 	max_height_above = 0;
1274 	max_height_below = 0;
1275 	for (p = icons; p != NULL; p = p->next) {
1276 		icon = p->data;
1277 
1278 		/* Assume it's only one level hierarchy to avoid costly affine calculations */
1279 		nautilus_canvas_item_get_bounds_for_layout (icon->item,
1280 								   &bounds.x0, &bounds.y0,
1281 								   &bounds.x1, &bounds.y1);
1282 
1283 		icon_bounds = nautilus_canvas_item_get_icon_rectangle (icon->item);
1284 		icon_width = ceil ((bounds.x1 - bounds.x0)/grid_width) * grid_width;
1285 		
1286 		/* Calculate size above/below baseline */
1287 		height_above = icon_bounds.y1 - bounds.y0;
1288 		height_below = bounds.y1 - icon_bounds.y1;
1289 
1290 		/* If this icon doesn't fit, it's time to lay out the line that's queued up. */
1291 		if (line_start != p && line_width + icon_width >= canvas_width ) {
1292 			/* Advance to the baseline. */
1293 			y += ICON_PAD_TOP + max_height_above;
1294 
1295 			lay_down_one_line (container, line_start, p, y, max_height_above, positions, FALSE);
1296 
1297 			/* Advance to next line. */
1298 			y += max_height_below + ICON_PAD_BOTTOM;
1299 
1300 			line_width = 0;
1301 			line_start = p;
1302 			i = 0;
1303 			
1304 			max_height_above = height_above;
1305 			max_height_below = height_below;
1306 		} else {
1307 			if (height_above > max_height_above) {
1308 				max_height_above = height_above;
1309 			}
1310 			if (height_below > max_height_below) {
1311 				max_height_below = height_below;
1312 			}
1313 		}
1314 		
1315 		g_array_set_size (positions, i + 1);
1316 		position = &g_array_index (positions, IconPositions, i++);
1317 		position->width = icon_width;
1318 		position->height = icon_bounds.y1 - icon_bounds.y0;
1319 
1320 		position->x_offset = (icon_width - (icon_bounds.x1 - icon_bounds.x0)) / 2;
1321 		position->y_offset = icon_bounds.y0 - icon_bounds.y1;
1322 
1323 		/* Add this icon. */
1324 		line_width += icon_width;
1325 	}
1326 
1327 	/* Lay down that last line of icons. */
1328 	if (line_start != NULL) {
1329 		/* Advance to the baseline. */
1330 		y += ICON_PAD_TOP + max_height_above;
1331 
1332 		lay_down_one_line (container, line_start, NULL, y, max_height_above, positions, TRUE);
1333 	}
1334 
1335 	g_array_free (positions, TRUE);
1336 }
1337 
1338 static void
1339 get_max_icon_dimensions (GList *icon_start,
1340 			 GList *icon_end,
1341 			 double *max_icon_width,
1342 			 double *max_icon_height,
1343 			 double *max_text_width,
1344 			 double *max_text_height,
1345 			 double *max_bounds_height)
1346 {
1347 	NautilusCanvasIcon *icon;
1348 	EelDRect icon_bounds;
1349 	EelDRect text_bounds;
1350 	GList *p;
1351 	double y1, y2;
1352 
1353 	*max_icon_width = *max_text_width = 0.0;
1354 	*max_icon_height = *max_text_height = 0.0;
1355 	*max_bounds_height = 0.0;
1356 
1357 	/* Would it be worth caching these bounds for the next loop? */
1358 	for (p = icon_start; p != icon_end; p = p->next) {
1359 		icon = p->data;
1360 
1361 		icon_bounds = nautilus_canvas_item_get_icon_rectangle (icon->item);
1362 		*max_icon_width = MAX (*max_icon_width, ceil (icon_bounds.x1 - icon_bounds.x0));
1363 		*max_icon_height = MAX (*max_icon_height, ceil (icon_bounds.y1 - icon_bounds.y0));
1364 
1365 		text_bounds = nautilus_canvas_item_get_text_rectangle (icon->item, TRUE);
1366 		*max_text_width = MAX (*max_text_width, ceil (text_bounds.x1 - text_bounds.x0));
1367 		*max_text_height = MAX (*max_text_height, ceil (text_bounds.y1 - text_bounds.y0));
1368 
1369 		nautilus_canvas_item_get_bounds_for_layout (icon->item,
1370 								   NULL, &y1,
1371 								   NULL, &y2);
1372 		*max_bounds_height = MAX (*max_bounds_height, y2 - y1);
1373 	}
1374 }
1375 
1376 static void
1377 lay_down_icons_vertical (NautilusCanvasContainer *container,
1378 			   GList *icons,
1379 			   double start_y)
1380 {
1381 	GList *p, *line_start;
1382 	NautilusCanvasIcon *icon;
1383 	double x, canvas_height;
1384 	GArray *positions;
1385 	IconPositions *position;
1386 	EelDRect icon_bounds;
1387 	EelDRect text_bounds;
1388 	GtkAllocation allocation;
1389 
1390 	double line_height;
1391 
1392 	double max_height;
1393 	double max_height_with_borders;
1394 	double max_width;
1395 	double max_width_in_column;
1396 
1397 	double max_bounds_height;
1398 	double max_bounds_height_with_borders;
1399 
1400 	double max_text_width, max_icon_width;
1401 	double max_text_height, max_icon_height;
1402 	int height;
1403 	int i;
1404 
1405 	g_assert (NAUTILUS_IS_CANVAS_CONTAINER (container));
1406 
1407 	if (icons == NULL) {
1408 		return;
1409 	}
1410 
1411 	positions = g_array_new (FALSE, FALSE, sizeof (IconPositions));
1412 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1413 
1414 	/* Lay out icons a column at a time. */
1415 	canvas_height = CANVAS_HEIGHT(container, allocation);
1416 
1417 	max_icon_width = max_text_width = 0.0;
1418 	max_icon_height = max_text_height = 0.0;
1419 	max_bounds_height = 0.0;
1420 
1421 	get_max_icon_dimensions (icons, NULL,
1422 				   &max_icon_width, &max_icon_height,
1423 				   &max_text_width, &max_text_height,
1424 				   &max_bounds_height);
1425 
1426 	max_width = max_icon_width + max_text_width;
1427 	max_height = MAX (max_icon_height, max_text_height);
1428 	max_height_with_borders = ICON_PAD_TOP + max_height;
1429 
1430 	max_bounds_height_with_borders = ICON_PAD_TOP + max_bounds_height;
1431 
1432 	line_height = ICON_PAD_TOP;
1433 	line_start = icons;
1434 	x = 0;
1435 	i = 0;
1436 
1437 	max_width_in_column = 0.0;
1438 
1439 	for (p = icons; p != NULL; p = p->next) {
1440 		icon = p->data;
1441 
1442 		/* If this icon doesn't fit, it's time to lay out the column that's queued up. */
1443 
1444 		/* We use the bounds height here, since for wrapping we also want to consider
1445 		 * overlapping emblems at the bottom. We may wrap a little bit too early since
1446 		 * the icon with the max. bounds height may actually not be in the last row, but
1447 		 * it is better than visual glitches
1448 		 */
1449 		if (line_start != p && line_height + (max_bounds_height_with_borders-1) >= canvas_height ) {
1450 			x += ICON_PAD_LEFT;
1451 
1452 			/* correctly set (per-column) width */
1453 			for (i = 0; i < (int) positions->len; i++) {
1454 				position = &g_array_index (positions, IconPositions, i);
1455 				position->width = max_width_in_column;
1456 			}
1457 
1458 			lay_down_one_column (container, line_start, p, x, CONTAINER_PAD_TOP, max_height_with_borders, positions);
1459 
1460 			/* Advance to next column. */
1461 			x += max_width_in_column + ICON_PAD_RIGHT;
1462 
1463 			line_height = ICON_PAD_TOP;
1464 			line_start = p;
1465 			i = 0;
1466 
1467 			max_width_in_column = 0;
1468 		}
1469 
1470 		icon_bounds = nautilus_canvas_item_get_icon_rectangle (icon->item);
1471 		text_bounds = nautilus_canvas_item_get_text_rectangle (icon->item, TRUE);
1472 
1473 		max_width_in_column = MAX (max_width_in_column,
1474 					   ceil (icon_bounds.x1 - icon_bounds.x0) +
1475 					   ceil (text_bounds.x1 - text_bounds.x0));
1476 
1477 		g_array_set_size (positions, i + 1);
1478 		position = &g_array_index (positions, IconPositions, i++);
1479 
1480 		position->width = max_width;
1481 		position->height = max_height;
1482 		position->y_offset = ICON_PAD_TOP;
1483 		position->x_offset = ICON_PAD_LEFT;
1484 
1485 		position->x_offset += max_icon_width - ceil (icon_bounds.x1 - icon_bounds.x0);
1486 
1487 		height = MAX (ceil (icon_bounds.y1 - icon_bounds.y0), ceil(text_bounds.y1 - text_bounds.y0));
1488 		position->y_offset += (max_height - height) / 2;
1489 
1490 		/* Add this icon. */
1491 		line_height += max_height_with_borders;
1492 	}
1493 
1494 	/* Lay down that last column of icons. */
1495 	if (line_start != NULL) {
1496 		x += ICON_PAD_LEFT;
1497 		lay_down_one_column (container, line_start, NULL, x, CONTAINER_PAD_TOP, max_height_with_borders, positions);
1498 	}
1499 
1500 	g_array_free (positions, TRUE);
1501 }
1502 
1503 static void
1504 snap_position (NautilusCanvasContainer *container,
1505 	       NautilusCanvasIcon *icon,
1506 	       int *x, int *y)
1507 {
1508 	int center_x;
1509 	int baseline_y;
1510 	int icon_width;
1511 	int icon_height;
1512 	int total_width;
1513 	int total_height;
1514 	EelDRect canvas_position;
1515 	GtkAllocation allocation;
1516 	
1517 	canvas_position = nautilus_canvas_item_get_icon_rectangle (icon->item);
1518 	icon_width = canvas_position.x1 - canvas_position.x0;
1519 	icon_height = canvas_position.y1 - canvas_position.y0;
1520 
1521 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1522 	total_width = CANVAS_WIDTH (container, allocation);
1523 	total_height = CANVAS_HEIGHT (container, allocation);
1524 
1525 	if (nautilus_canvas_container_is_layout_rtl (container))
1526 		*x = get_mirror_x_position (container, icon, *x);
1527 
1528 	if (*x + icon_width / 2 < DESKTOP_PAD_HORIZONTAL + SNAP_SIZE_X) {
1529 		*x = DESKTOP_PAD_HORIZONTAL + SNAP_SIZE_X - icon_width / 2;
1530 	}
1531 
1532 	if (*x + icon_width / 2 > total_width - (DESKTOP_PAD_HORIZONTAL + SNAP_SIZE_X)) {
1533 		*x = total_width - (DESKTOP_PAD_HORIZONTAL + SNAP_SIZE_X + (icon_width / 2));
1534 	}
1535 
1536 	if (*y + icon_height < DESKTOP_PAD_VERTICAL + SNAP_SIZE_Y) {
1537 		*y = DESKTOP_PAD_VERTICAL + SNAP_SIZE_Y - icon_height;
1538 	}
1539 
1540 	if (*y + icon_height > total_height - (DESKTOP_PAD_VERTICAL + SNAP_SIZE_Y)) {
1541 		*y = total_height - (DESKTOP_PAD_VERTICAL + SNAP_SIZE_Y + (icon_height / 2));
1542 	}
1543 
1544 	center_x = *x + icon_width / 2;
1545 	*x = SNAP_NEAREST_HORIZONTAL (center_x) - (icon_width / 2);
1546 	if (nautilus_canvas_container_is_layout_rtl (container)) {
1547 		*x = get_mirror_x_position (container, icon, *x);
1548 	}
1549 
1550 
1551 	/* Find the grid position vertically and place on the proper baseline */
1552 	baseline_y = *y + icon_height;
1553 	baseline_y = SNAP_NEAREST_VERTICAL (baseline_y);
1554 	*y = baseline_y - icon_height;
1555 }
1556 
1557 static int
1558 compare_icons_by_position (gconstpointer a, gconstpointer b)
1559 {
1560 	NautilusCanvasIcon *icon_a, *icon_b;
1561 	int x1, y1, x2, y2;
1562 	int center_a;
1563 	int center_b;
1564 
1565 	icon_a = (NautilusCanvasIcon *)a;
1566 	icon_b = (NautilusCanvasIcon *)b;
1567 
1568 	icon_get_bounding_box (icon_a, &x1, &y1, &x2, &y2,
1569 				 BOUNDS_USAGE_FOR_DISPLAY);
1570 	center_a = x1 + (x2 - x1) / 2;
1571 	icon_get_bounding_box (icon_b, &x1, &y1, &x2, &y2,
1572 				 BOUNDS_USAGE_FOR_DISPLAY);
1573 	center_b = x1 + (x2 - x1) / 2;
1574 
1575 	return center_a == center_b ?
1576 		icon_a->y - icon_b->y :
1577 		center_a - center_b;
1578 }
1579 
1580 static PlacementGrid *
1581 placement_grid_new (NautilusCanvasContainer *container, gboolean tight)
1582 {
1583 	PlacementGrid *grid;
1584 	int width, height;
1585 	int num_columns;
1586 	int num_rows;
1587 	int i;
1588 	GtkAllocation allocation;
1589 
1590 	/* Get container dimensions */
1591 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1592 	width  = CANVAS_WIDTH(container, allocation);
1593 	height = CANVAS_HEIGHT(container, allocation);
1594 
1595 	num_columns = width / SNAP_SIZE_X;
1596 	num_rows = height / SNAP_SIZE_Y;
1597 	
1598 	if (num_columns == 0 || num_rows == 0) {
1599 		return NULL;
1600 	}
1601 
1602 	grid = g_new0 (PlacementGrid, 1);
1603 	grid->tight = tight;
1604 	grid->num_columns = num_columns;
1605 	grid->num_rows = num_rows;
1606 
1607 	grid->grid_memory = g_new0 (int, (num_rows * num_columns));
1608 	grid->icon_grid = g_new0 (int *, num_columns);
1609 	
1610 	for (i = 0; i < num_columns; i++) {
1611 		grid->icon_grid[i] = grid->grid_memory + (i * num_rows);
1612 	}
1613 	
1614 	return grid;
1615 }
1616 
1617 static void
1618 placement_grid_free (PlacementGrid *grid)
1619 {
1620 	g_free (grid->icon_grid);
1621 	g_free (grid->grid_memory);
1622 	g_free (grid);
1623 }
1624 
1625 static gboolean
1626 placement_grid_position_is_free (PlacementGrid *grid, EelIRect pos)
1627 {
1628 	int x, y;
1629 	
1630 	g_assert (pos.x0 >= 0 && pos.x0 < grid->num_columns);
1631 	g_assert (pos.y0 >= 0 && pos.y0 < grid->num_rows);
1632 	g_assert (pos.x1 >= 0 && pos.x1 < grid->num_columns);
1633 	g_assert (pos.y1 >= 0 && pos.y1 < grid->num_rows);
1634 
1635 	for (x = pos.x0; x <= pos.x1; x++) {
1636 		for (y = pos.y0; y <= pos.y1; y++) {
1637 			if (grid->icon_grid[x][y] != 0) {
1638 				return FALSE;
1639 			}
1640 		}
1641 	}
1642 
1643 	return TRUE;
1644 }
1645 
1646 static void
1647 placement_grid_mark (PlacementGrid *grid, EelIRect pos)
1648 {
1649 	int x, y;
1650 	
1651 	g_assert (pos.x0 >= 0 && pos.x0 < grid->num_columns);
1652 	g_assert (pos.y0 >= 0 && pos.y0 < grid->num_rows);
1653 	g_assert (pos.x1 >= 0 && pos.x1 < grid->num_columns);
1654 	g_assert (pos.y1 >= 0 && pos.y1 < grid->num_rows);
1655 
1656 	for (x = pos.x0; x <= pos.x1; x++) {
1657 		for (y = pos.y0; y <= pos.y1; y++) {
1658 			grid->icon_grid[x][y] = 1;
1659 		}
1660 	}
1661 }
1662 
1663 static void
1664 canvas_position_to_grid_position (PlacementGrid *grid,
1665 				  EelIRect canvas_position,
1666 				  EelIRect *grid_position)
1667 {
1668 	/* The first causes minimal moving around during a snap, but
1669 	 * can end up with partially overlapping icons.  The second one won't
1670 	 * allow any overlapping, but can cause more movement to happen 
1671 	 * during a snap. */
1672 	if (grid->tight) {
1673 		grid_position->x0 = ceil ((double)(canvas_position.x0 - DESKTOP_PAD_HORIZONTAL) / SNAP_SIZE_X);
1674 		grid_position->y0 = ceil ((double)(canvas_position.y0 - DESKTOP_PAD_VERTICAL) / SNAP_SIZE_Y);
1675 		grid_position->x1 = floor ((double)(canvas_position.x1 - DESKTOP_PAD_HORIZONTAL) / SNAP_SIZE_X);
1676 		grid_position->y1 = floor ((double)(canvas_position.y1 - DESKTOP_PAD_VERTICAL) / SNAP_SIZE_Y);
1677 	} else {
1678 		grid_position->x0 = floor ((double)(canvas_position.x0 - DESKTOP_PAD_HORIZONTAL) / SNAP_SIZE_X);
1679 		grid_position->y0 = floor ((double)(canvas_position.y0 - DESKTOP_PAD_VERTICAL) / SNAP_SIZE_Y);
1680 		grid_position->x1 = floor ((double)(canvas_position.x1 - DESKTOP_PAD_HORIZONTAL) / SNAP_SIZE_X);
1681 		grid_position->y1 = floor ((double)(canvas_position.y1 - DESKTOP_PAD_VERTICAL) / SNAP_SIZE_Y);
1682 	}
1683 
1684 	grid_position->x0 = CLAMP (grid_position->x0, 0, grid->num_columns - 1);
1685 	grid_position->y0 = CLAMP (grid_position->y0, 0, grid->num_rows - 1);
1686 	grid_position->x1 = CLAMP (grid_position->x1, grid_position->x0, grid->num_columns - 1);
1687 	grid_position->y1 = CLAMP (grid_position->y1, grid_position->y0, grid->num_rows - 1);
1688 }
1689 
1690 static void
1691 placement_grid_mark_icon (PlacementGrid *grid, NautilusCanvasIcon *icon)
1692 {
1693 	EelIRect canvas_pos;
1694 	EelIRect grid_pos;
1695 	
1696 	icon_get_bounding_box (icon,
1697 				 &canvas_pos.x0, &canvas_pos.y0,
1698 				 &canvas_pos.x1, &canvas_pos.y1,
1699 				 BOUNDS_USAGE_FOR_LAYOUT);
1700 	canvas_position_to_grid_position (grid, 
1701 					  canvas_pos,
1702 					  &grid_pos);
1703 	placement_grid_mark (grid, grid_pos);
1704 }
1705 
1706 static void
1707 find_empty_location (NautilusCanvasContainer *container,
1708 		     PlacementGrid *grid,
1709 		     NautilusCanvasIcon *icon,
1710 		     int start_x,
1711 		     int start_y,
1712 		     int *x, 
1713 		     int *y)
1714 {
1715 	double icon_width, icon_height;
1716 	int canvas_width;
1717 	int canvas_height;
1718 	int height_for_bound_check;
1719 	EelIRect icon_position;
1720 	EelDRect pixbuf_rect;
1721 	gboolean collision;
1722 	GtkAllocation allocation;
1723 
1724 	/* Get container dimensions */
1725 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1726 	canvas_width  = CANVAS_WIDTH(container, allocation);
1727 	canvas_height = CANVAS_HEIGHT(container, allocation);
1728 
1729 	icon_get_bounding_box (icon,
1730 				 &icon_position.x0, &icon_position.y0,
1731 				 &icon_position.x1, &icon_position.y1,
1732 				 BOUNDS_USAGE_FOR_LAYOUT);
1733 	icon_width = icon_position.x1 - icon_position.x0;
1734 	icon_height = icon_position.y1 - icon_position.y0;
1735 
1736 	icon_get_bounding_box (icon,
1737 				 NULL, &icon_position.y0,
1738 				 NULL, &icon_position.y1,
1739 				 BOUNDS_USAGE_FOR_ENTIRE_ITEM);
1740 	height_for_bound_check = icon_position.y1 - icon_position.y0;
1741 
1742 	pixbuf_rect = nautilus_canvas_item_get_icon_rectangle (icon->item);
1743 	
1744 	/* Start the icon on a grid location */
1745 	snap_position (container, icon, &start_x, &start_y);
1746 
1747 	icon_position.x0 = start_x;
1748 	icon_position.y0 = start_y;
1749 	icon_position.x1 = icon_position.x0 + icon_width;
1750 	icon_position.y1 = icon_position.y0 + icon_height;
1751 
1752 	do {
1753 		EelIRect grid_position;
1754 		gboolean need_new_column;
1755 
1756 		collision = FALSE;
1757 		
1758 		canvas_position_to_grid_position (grid,
1759 						  icon_position,
1760 						  &grid_position);
1761 
1762 		need_new_column = icon_position.y0 + height_for_bound_check + DESKTOP_PAD_VERTICAL > canvas_height;
1763 
1764 		if (need_new_column ||
1765 		    !placement_grid_position_is_free (grid, grid_position)) {
1766 			icon_position.y0 += SNAP_SIZE_Y;
1767 			icon_position.y1 = icon_position.y0 + icon_height;
1768 			
1769 			if (need_new_column) {
1770 				/* Move to the next column */
1771 				icon_position.y0 = DESKTOP_PAD_VERTICAL + SNAP_SIZE_Y - (pixbuf_rect.y1 - pixbuf_rect.y0);
1772 				while (icon_position.y0 < DESKTOP_PAD_VERTICAL) {
1773 					icon_position.y0 += SNAP_SIZE_Y;
1774 				}
1775 				icon_position.y1 = icon_position.y0 + icon_height;
1776 				
1777 				icon_position.x0 += SNAP_SIZE_X;
1778 				icon_position.x1 = icon_position.x0 + icon_width;
1779 			}
1780 				
1781 			collision = TRUE;
1782 		}
1783 	} while (collision && (icon_position.x1 < canvas_width));
1784 
1785 	*x = icon_position.x0;
1786 	*y = icon_position.y0;
1787 }
1788 
1789 static void
1790 align_icons (NautilusCanvasContainer *container)
1791 {
1792 	GList *unplaced_icons;
1793 	GList *l;
1794 	PlacementGrid *grid;
1795 
1796 	unplaced_icons = g_list_copy (container->details->icons);
1797 	
1798 	unplaced_icons = g_list_sort (unplaced_icons, 
1799 					compare_icons_by_position);
1800 
1801 	if (nautilus_canvas_container_is_layout_rtl (container)) {
1802 		unplaced_icons = g_list_reverse (unplaced_icons);
1803 	}
1804 
1805 	grid = placement_grid_new (container, TRUE);
1806 
1807 	if (!grid) {
1808 		return;
1809 	}
1810 
1811 	for (l = unplaced_icons; l != NULL; l = l->next) {
1812 		NautilusCanvasIcon *icon;
1813 		int x, y;
1814 
1815 		icon = l->data;
1816 		x = icon->saved_ltr_x;
1817 		y = icon->y;
1818 		find_empty_location (container, grid, 
1819 				     icon, x, y, &x, &y);
1820 
1821 		icon_set_position (icon, x, y);
1822 		icon->saved_ltr_x = icon->x;
1823 		placement_grid_mark_icon (grid, icon);
1824 	}
1825 
1826 	g_list_free (unplaced_icons);
1827 
1828 	placement_grid_free (grid);
1829 
1830 	if (nautilus_canvas_container_is_layout_rtl (container)) {
1831 		nautilus_canvas_container_set_rtl_positions (container);
1832 	}
1833 }
1834 
1835 static double
1836 get_mirror_x_position (NautilusCanvasContainer *container, NautilusCanvasIcon *icon, double x)
1837 {
1838 	EelDRect icon_bounds;
1839 	GtkAllocation allocation;
1840 
1841 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1842 	icon_bounds = nautilus_canvas_item_get_icon_rectangle (icon->item);
1843 
1844 	return CANVAS_WIDTH(container, allocation) - x - (icon_bounds.x1 - icon_bounds.x0);
1845 }
1846 
1847 static void
1848 nautilus_canvas_container_set_rtl_positions (NautilusCanvasContainer *container)
1849 {
1850 	GList *l;
1851 	NautilusCanvasIcon *icon;
1852 	double x;
1853 
1854 	if (!container->details->icons) {
1855 		return;
1856 	}
1857 
1858 	for (l = container->details->icons; l != NULL; l = l->next) {
1859 		icon = l->data;
1860 		x = get_mirror_x_position (container, icon, icon->saved_ltr_x);
1861 		icon_set_position (icon, x, icon->y);
1862 	}
1863 }
1864 
1865 static void
1866 lay_down_icons_vertical_desktop (NautilusCanvasContainer *container, GList *icons)
1867 {
1868 	GList *p, *placed_icons, *unplaced_icons;
1869 	int total, new_length, placed;
1870 	NautilusCanvasIcon *icon;
1871 	int height, max_width, column_width, icon_width, icon_height;
1872 	int x, y, x1, x2, y1, y2;
1873 	EelDRect icon_rect;
1874 	GtkAllocation allocation;
1875 
1876 	/* Get container dimensions */
1877 	gtk_widget_get_allocation (GTK_WIDGET (container), &allocation);
1878 	height = CANVAS_HEIGHT(container, allocation);
1879 
1880 	/* Determine which icons have and have not been placed */
1881 	placed_icons = NULL;
1882 	unplaced_icons = NULL;
1883 	
1884 	total = g_list_length (container->details->icons);
1885 	new_length = g_list_length (icons);
1886 	placed = total - new_length;
1887 	if (placed > 0) {
1888 		PlacementGrid *grid;
1889 		/* Add only placed icons in list */
1890 		for (p = container->details->icons; p != NULL; p = p->next) {
1891 			icon = p->data;
1892 			if (icon_is_positioned (icon)) {
1893 				icon_set_position(icon, icon->saved_ltr_x, icon->y);
1894 				placed_icons = g_list_prepend (placed_icons, icon);
1895 			} else {
1896 				icon->x = 0;
1897 				icon->y = 0;
1898 				unplaced_icons = g_list_prepend (unplaced_icons, icon);
1899 			}
1900 		}
1901 		placed_icons = g_list_reverse (placed_icons);
1902 		unplaced_icons = g_list_reverse (unplaced_icons);
1903 
1904 		grid = placement_grid_new (container, FALSE);
1905 
1906 		if (grid) {
1907 			for (p = placed_icons; p != NULL; p = p->next) {
1908 				placement_grid_mark_icon
1909 					(grid, (NautilusCanvasIcon *)p->data);
1910 			}
1911 			
1912 			/* Place unplaced icons in the best locations */
1913 			for (p = unplaced_icons; p != NULL; p = p->next) {
1914 				icon = p->data;
1915 				
1916 				icon_rect = nautilus_canvas_item_get_icon_rectangle (icon->item);
1917 				
1918 				/* Start the icon in the first column */
1919 				x = DESKTOP_PAD_HORIZONTAL + (SNAP_SIZE_X / 2) - ((icon_rect.x1 - icon_rect.x0) / 2);
1920 				y = DESKTOP_PAD_VERTICAL + SNAP_SIZE_Y - (icon_rect.y1 - icon_rect.y0);
1921 
1922 				find_empty_location (container,
1923 						     grid,
1924 						     icon,
1925 						     x, y,
1926 						     &x, &y);
1927 				
1928 				icon_set_position (icon, x, y);
1929 				icon->saved_ltr_x = x;
1930 				placement_grid_mark_icon (grid, icon);
1931 			}
1932 
1933 			placement_grid_free (grid);
1934 		}
1935 		
1936 		g_list_free (placed_icons);
1937 		g_list_free (unplaced_icons);
1938 	} else {
1939 		/* There are no placed icons.  Just lay them down using our rules */		
1940 		x = DESKTOP_PAD_HORIZONTAL;
1941 
1942 		while (icons != NULL) {
1943 			int center_x;
1944 			int baseline;
1945 			int icon_height_for_bound_check;
1946 			gboolean should_snap;
1947 			
1948 			should_snap = container->details->keep_aligned;
1949 			
1950 			y = DESKTOP_PAD_VERTICAL;
1951 
1952 			max_width = 0;
1953 			
1954 			/* Calculate max width for column */
1955 			for (p = icons; p != NULL; p = p->next) {
1956 				icon = p->data;
1957 
1958 				icon_get_bounding_box (icon, &x1, &y1, &x2, &y2,
1959 							 BOUNDS_USAGE_FOR_LAYOUT);
1960 				icon_width = x2 - x1;
1961 				icon_height = y2 - y1;
1962 
1963 				icon_get_bounding_box (icon, NULL, &y1, NULL, &y2,
1964 						       BOUNDS_USAGE_FOR_ENTIRE_ITEM);
1965 				icon_height_for_bound_check = y2 - y1;
1966 
1967 				if (should_snap) {
1968 					/* Snap the baseline to a grid position */
1969 					icon_rect = nautilus_canvas_item_get_icon_rectangle (icon->item);
1970 					baseline = y + (icon_rect.y1 - icon_rect.y0);
1971 					baseline = SNAP_CEIL_VERTICAL (baseline);
1972 					y = baseline - (icon_rect.y1 - icon_rect.y0);
1973 				}
1974 				    
1975 				/* Check and see if we need to move to a new column */
1976 				if (y != DESKTOP_PAD_VERTICAL && y + icon_height_for_bound_check > height) {
1977 					break;
1978 				}
1979 
1980 				if (max_width < icon_width) {
1981 					max_width = icon_width;
1982 				}
1983 				
1984 				y += icon_height + DESKTOP_PAD_VERTICAL;
1985 			}
1986 
1987 			y = DESKTOP_PAD_VERTICAL;
1988 
1989 			center_x = x + max_width / 2;
1990 			column_width = max_width;
1991 			if (should_snap) {
1992 				/* Find the grid column to center on */
1993 				center_x = SNAP_CEIL_HORIZONTAL (center_x);
1994 				column_width = (center_x - x) + (max_width / 2);
1995 			}
1996 			
1997 			/* Lay out column */
1998 			for (p = icons; p != NULL; p = p->next) {
1999 				icon = p->data;
2000 				icon_get_bounding_box (icon, &x1, &y1, &x2, &y2,
2001 							 BOUNDS_USAGE_FOR_LAYOUT);
2002 				icon_height = y2 - y1;
2003 
2004 				icon_get_bounding_box (icon, NULL, &y1, NULL, &y2,
2005 							 BOUNDS_USAGE_FOR_ENTIRE_ITEM);
2006 				icon_height_for_bound_check = y2 - y1;
2007 				
2008 				icon_rect = nautilus_canvas_item_get_icon_rectangle (icon->item);
2009 
2010 				if (should_snap) {
2011 					baseline = y + (icon_rect.y1 - icon_rect.y0);
2012 					baseline = SNAP_CEIL_VERTICAL (baseline);
2013 					y = baseline - (icon_rect.y1 - icon_rect.y0);
2014 				}
2015 				
2016 				/* Check and see if we need to move to a new column */
2017 				if (y != DESKTOP_PAD_VERTICAL && y > height - icon_height_for_bound_check &&
2018 				    /* Make sure we lay out at least one icon per column, to make progress */
2019 				    p != icons) {
2020 					x += column_width + DESKTOP_PAD_HORIZONTAL;
2021 					break;
2022 				}
2023 				
2024 				icon_set_position (icon,
2025 						     center_x - (icon_rect.x1 - icon_rect.x0) / 2,
2026 						     y);
2027 				
2028 				icon->saved_ltr_x = icon->x;
2029 				y += icon_height + DESKTOP_PAD_VERTICAL;
2030 			}
2031 			icons = p;
2032 		}
2033 	}
2034 
2035 	/* These modes are special. We freeze all of our positions
2036 	 * after we do the layout.
2037 	 */
2038 	/* FIXME bugzilla.gnome.org 42478: 
2039 	 * This should not be tied to the direction of layout.
2040 	 * It should be a separate switch.
2041 	 */
2042 	nautilus_canvas_container_freeze_icon_positions (container);
2043 }
2044 
2045 
2046 static void
2047 lay_down_icons (NautilusCanvasContainer *container, GList *icons, double start_y)
2048 {
2049 	switch (container->details->layout_mode)
2050 		{
2051 		case NAUTILUS_CANVAS_LAYOUT_L_R_T_B:
2052 		case NAUTILUS_CANVAS_LAYOUT_R_L_T_B:
2053 			lay_down_icons_horizontal (container, icons, start_y);
2054 			break;
2055 		
2056 		case NAUTILUS_CANVAS_LAYOUT_T_B_L_R:
2057 		case NAUTILUS_CANVAS_LAYOUT_T_B_R_L:
2058 			if (nautilus_canvas_container_get_is_desktop (container)) {
2059 				lay_down_icons_vertical_desktop (container, icons);
2060 			} else {
2061 				lay_down_icons_vertical (container, icons, start_y);
2062 			}
2063 			break;
2064 		
2065 		default:
2066 			g_assert_not_reached ();
2067 		}
2068 }
2069 
2070 static void
2071 redo_layout_internal (NautilusCanvasContainer *container)
2072 {
2073 	finish_adding_new_icons (container);
2074 
2075 	/* Don't do any re-laying-out during stretching. Later we
2076 	 * might add smart logic that does this and leaves room for
2077 	 * the stretched icon, but if we do it we want it to be fast
2078 	 * and only re-lay-out when it's really needed.
2079 	 */
2080 	if (container->details->auto_layout
2081 	    && container->details->drag_state != DRAG_STATE_STRETCH) {
2082 		if (container->details->needs_resort) {
2083 			resort (container);
2084 			container->details->needs_resort = FALSE;
2085 		}
2086 		lay_down_icons (container, container->details->icons, 0);
2087 	}
2088 
2089 	if (nautilus_canvas_container_is_layout_rtl (container)) {
2090 		nautilus_canvas_container_set_rtl_positions (container);
2091 	}
2092 
2093 	nautilus_canvas_container_update_scroll_region (container);
2094 
2095 	process_pending_icon_to_reveal (container);
2096 	process_pending_icon_to_rename (container);
2097 	nautilus_canvas_container_update_visible_icons (container);
2098 }
2099 
2100 static gboolean
2101 redo_layout_callback (gpointer callback_data)
2102 {
2103 	NautilusCanvasContainer *container;
2104 
2105 	container = NAUTILUS_CANVAS_CONTAINER (callback_data);
2106 	redo_layout_internal (container);
2107 	container->details->idle_id = 0;
2108 
2109 	return FALSE;
2110 }
2111 
2112 static void
2113 unschedule_redo_layout (NautilusCanvasContainer *container)
2114 {
2115         if (container->details->idle_id != 0) {
2116 		g_source_remove (container->details->idle_id);
2117 		container->details->idle_id = 0;
2118 	}
2119 }
2120 
2121 static void
2122 schedule_redo_layout (NautilusCanvasContainer *container)
2123 {
2124 	if (container->details->idle_id == 0
2125 	    && container->details->has_been_allocated) {
2126 		container->details->idle_id = g_idle_add
2127 			(redo_layout_callback, container);
2128 	}
2129 }
2130 
2131 static void
2132 redo_layout (NautilusCanvasContainer *container)
2133 {
2134 	unschedule_redo_layout (container);
2135 	redo_layout_internal (container);
2136 }
2137 
2138 static void
2139 reload_icon_positions (NautilusCanvasContainer *container)
2140 {
2141 	GList *p, *no_position_icons;
2142 	NautilusCanvasIcon *icon;
2143 	gboolean have_stored_position;
2144 	NautilusCanvasPosition position;
2145 	EelDRect bounds;
2146 	double bottom;
2147 	EelCanvasItem *item;
2148 
2149 	g_assert (!container->details->auto_layout);
2150 
2151 	resort (container);
2152 
2153 	no_position_icons = NULL;
2154 
2155 	/* Place all the icons with positions. */
2156 	bottom = 0;
2157 	for (p = container->details->icons; p != NULL; p = p->next) {
2158 		icon = p->data;
2159 
2160 		have_stored_position = FALSE;
2161 		g_signal_emit (container,
2162 			       signals[GET_STORED_ICON_POSITION], 0,
2163 			       icon->data,
2164 			       &position,
2165 			       &have_stored_position);
2166 		if (have_stored_position) {
2167 			icon_set_position (icon, position.x, position.y);
2168 			item = EEL_CANVAS_ITEM (icon->item);
2169 			nautilus_canvas_item_get_bounds_for_layout (icon->item,
2170 									   &bounds.x0,
2171 									   &bounds.y0,
2172 									   &bounds.x1,
2173 									   &bounds.y1);
2174 			eel_canvas_item_i2w (item->parent,
2175 					     &bounds.x0,
2176 					     &bounds.y0);
2177 			eel_canvas_item_i2w (item->parent,
2178 					     &bounds.x1,
2179 					     &bounds.y1);
2180 			if (bounds.y1 > bottom) {
2181 				bottom = bounds.y1;
2182 			}
2183 		} else {
2184 			no_position_icons = g_list_prepend (no_position_icons, icon);
2185 		}
2186 	}
2187 	no_position_icons = g_list_reverse (no_position_icons);
2188 
2189 	/* Place all the other icons. */
2190 	lay_down_icons (container, no_position_icons, bottom + ICON_PAD_BOTTOM);
2191 	g_list_free (no_position_icons);
2192 }
2193 
2194 /* Container-level icon handling functions.  */
2195 
2196 static gboolean
2197 button_event_modifies_selection (GdkEventButton *event)
2198 {
2199 	return (event->state & (GDK_CONTROL_MASK | GDK_SHIFT_MASK)) != 0;
2200 }
2201 
2202 /* invalidate the cached label sizes for all the icons */
2203 static void
2204 invalidate_label_sizes (NautilusCanvasContainer *container)
2205 {
2206 	GList *p;
2207 	NautilusCanvasIcon *icon;
2208 	
2209 	for (p = container->details->icons; p != NULL; p = p->next) {
2210 		icon = p->data;
2211 
2212 		nautilus_canvas_item_invalidate_label_size (icon->item);		
2213 	}
2214 }
2215 
2216 /* invalidate the entire labels (i.e. their attributes) for all the icons */
2217 static void
2218 invalidate_labels (NautilusCanvasContainer *container)
2219 {
2220 	GList *p;
2221 	NautilusCanvasIcon *icon;
2222 	
2223 	for (p = container->details->icons; p != NULL; p = p->next) {
2224 		icon = p->data;
2225 
2226 		nautilus_canvas_item_invalidate_label (icon->item);		
2227 	}
2228 }
2229 
2230 static gboolean
2231 select_range (NautilusCanvasContainer *container,
2232 	      NautilusCanvasIcon *icon1,
2233 	      NautilusCanvasIcon *icon2,
2234 	      gboolean unselect_outside_range)
2235 {
2236 	gboolean selection_changed;
2237 	GList *p;
2238 	NautilusCanvasIcon *icon;
2239 	NautilusCanvasIcon *unmatched_icon;
2240 	gboolean select;
2241 
2242 	selection_changed = FALSE;
2243 
2244 	unmatched_icon = NULL;
2245 	select = FALSE;
2246 	for (p = container->details->icons; p != NULL; p = p->next) {
2247 		icon = p->data;
2248 
2249 		if (unmatched_icon == NULL) {
2250 			if (icon == icon1) {
2251 				unmatched_icon = icon2;
2252 				select = TRUE;
2253 			} else if (icon == icon2) {
2254 				unmatched_icon = icon1;
2255 				select = TRUE;
2256 			}
2257 		}
2258 		
2259 		if (select || unselect_outside_range) {
2260 			selection_changed |= icon_set_selected
2261 				(container, icon, select);
2262 		}
2263 
2264 		if (unmatched_icon != NULL && icon == unmatched_icon) {
2265 			select = FALSE;
2266 		}
2267 		
2268 	}
2269 	
2270 	if (selection_changed && icon2 != NULL) {
2271 		emit_atk_focus_tracker_notify (icon2);
2272 	}
2273 	return selection_changed;
2274 }
2275 
2276 
2277 static gboolean
2278 select_one_unselect_others (NautilusCanvasContainer *container,
2279 			    NautilusCanvasIcon *icon_to_select)
2280 {
2281 	gboolean selection_changed;
2282 	GList *p;
2283 	NautilusCanvasIcon *icon;
2284 
2285 	selection_changed = FALSE;
2286 	
2287 	for (p = container->details->icons; p != NULL; p = p->next) {
2288 		icon = p->data;
2289 
2290 		selection_changed |= icon_set_selected
2291 			(container, icon, icon == icon_to_select);
2292 	}
2293 	
2294 	if (selection_changed && icon_to_select != NULL) {
2295 		emit_atk_focus_tracker_notify (icon_to_select);
2296 		reveal_icon (container, icon_to_select);
2297 	}
2298 	return selection_changed;
2299 }
2300 
2301 static gboolean
2302 unselect_all (NautilusCanvasContainer *container)
2303 {
2304 	return select_one_unselect_others (container, NULL);
2305 }
2306 
2307 void
2308 nautilus_canvas_container_move_icon (NautilusCanvasContainer *container,
2309 				       NautilusCanvasIcon *icon,
2310 				       int x, int y,
2311 				       double scale,
2312 				       gboolean raise,
2313 				       gboolean snap,
2314 				       gboolean update_position)
2315 {
2316 	NautilusCanvasContainerDetails *details;
2317 	gboolean emit_signal;
2318 	NautilusCanvasPosition position;
2319 	
2320 	details = container->details;
2321 	
2322 	emit_signal = FALSE;
2323 	
2324 	if (icon == get_icon_being_renamed (container)) {
2325 		end_renaming_mode (container, TRUE);
2326 	}
2327 
2328 	if (scale != icon->scale) {
2329 		icon->scale = scale;
2330 		nautilus_canvas_container_update_icon (container, icon);
2331 		if (update_position) {
2332 			redo_layout (container); 
2333 			emit_signal = TRUE;
2334 		}
2335 	}
2336 
2337 	if (!details->auto_layout) {
2338 		if (details->keep_aligned && snap) {
2339 			snap_position (container, icon, &x, &y);
2340 		}
2341 
2342 		if (x != icon->x || y != icon->y) {
2343 			icon_set_position (icon, x, y);
2344 			emit_signal = update_position;
2345 		}
2346 
2347 		icon->saved_ltr_x = nautilus_canvas_container_is_layout_rtl (container) ? get_mirror_x_position (container, icon, icon->x) : icon->x;
2348 	}
2349 	
2350 	if (emit_signal) {
2351 		position.x = icon->saved_ltr_x;
2352 		position.y = icon->y;
2353 		position.scale = scale;
2354 		g_signal_emit (container,
2355 			       signals[ICON_POSITION_CHANGED], 0,
2356 			       icon->data, &position);
2357 	}
2358 	
2359 	if (raise) {
2360 		icon_raise (icon);
2361 	}
2362 
2363 	/* FIXME bugzilla.gnome.org 42474: 
2364 	 * Handling of the scroll region is inconsistent here. In
2365 	 * the scale-changing case, redo_layout is called, which updates the
2366 	 * scroll region appropriately. In other cases, it's up to the
2367 	 * caller to make sure the scroll region is updated. This could
2368 	 * lead to hard-to-track-down bugs.
2369 	 */
2370 }
2371 
2372 /* Implementation of rubberband selection.  */
2373 static void
2374 rubberband_select (NautilusCanvasContainer *container,
2375 		   const EelDRect *previous_rect,
2376 		   const EelDRect *current_rect)
2377 {
2378 	GList *p;
2379 	gboolean selection_changed, is_in, canvas_rect_calculated;
2380 	NautilusCanvasIcon *icon;
2381 	EelIRect canvas_rect;
2382 	EelCanvas *canvas;
2383 			
2384 	selection_changed = FALSE;
2385 	canvas_rect_calculated = FALSE;
2386 
2387 	for (p = container->details->icons; p != NULL; p = p->next) {
2388 		icon = p->data;
2389 		
2390 		if (!canvas_rect_calculated) {
2391 			/* Only do this calculation once, since all the canvas items
2392 			 * we are interating are in the same coordinate space
2393 			 */
2394 			canvas = EEL_CANVAS_ITEM (icon->item)->canvas;
2395 			eel_canvas_w2c (canvas,
2396 					current_rect->x0,
2397 					current_rect->y0,
2398 					&canvas_rect.x0,
2399 					&canvas_rect.y0);
2400 			eel_canvas_w2c (canvas,
2401 					current_rect->x1,
2402 					current_rect->y1,
2403 					&canvas_rect.x1,
2404 					&canvas_rect.y1);
2405 			canvas_rect_calculated = TRUE;
2406 		}
2407 		
2408 		is_in = nautilus_canvas_item_hit_test_rectangle (icon->item, canvas_rect);
2409 
2410 		selection_changed |= icon_set_selected
2411 			(container, icon,
2412 			 is_in ^ icon->was_selected_before_rubberband);
2413 	}
2414 
2415 	if (selection_changed) {
2416 		g_signal_emit (container,
2417 			       signals[SELECTION_CHANGED], 0);
2418 	}
2419 }
2420 
2421 static int
2422 rubberband_timeout_callback (gpointer data)
2423 {
2424 	NautilusCanvasContainer *container;
2425 	GtkWidget *widget;
2426 	NautilusCanvasRubberbandInfo *band_info;
2427 	int x, y;
2428 	double x1, y1, x2, y2;
2429 	double world_x, world_y;
2430 	int x_scroll, y_scroll;
2431 	int adj_x, adj_y;
2432 	gboolean adj_changed;
2433 	GtkAllocation allocation;
2434 	
2435 	EelDRect selection_rect;
2436 
2437 	widget = GTK_WIDGET (data);
2438 	container = NAUTILUS_CANVAS_CONTAINER (data);
2439 	band_info = &container->details->rubberband_info;
2440 
2441 	g_assert (band_info->timer_id != 0);
2442 
2443 	adj_changed = FALSE;
2444 	gtk_widget_get_allocation (widget, &allocation);
2445 
2446 	adj_x = gtk_adjustment_get_value (gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (container)));
2447 	if (adj_x != band_info->last_adj_x) {
2448 		band_info->last_adj_x = adj_x;
2449 		adj_changed = TRUE;
2450 	}
2451 
2452 	adj_y = gtk_adjustment_get_value (gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (container)));
2453 	if (adj_y != band_info->last_adj_y) {
2454 		band_info->last_adj_y = adj_y;
2455 		adj_changed = TRUE;
2456 	}
2457 
2458 	gdk_window_get_device_position (gtk_widget_get_window (widget),
2459 					gdk_device_manager_get_client_pointer (
2460 									       gdk_display_get_device_manager (
2461 													       gtk_widget_get_display (widget))),
2462 					&x, &y, NULL);
2463 
2464 	if (x < RUBBERBAND_SCROLL_THRESHOLD) {
2465 		x_scroll = x - RUBBERBAND_SCROLL_THRESHOLD;
2466 		x = 0;
2467 	} else if (x >= allocation.width - RUBBERBAND_SCROLL_THRESHOLD) {
2468 		x_scroll = x - allocation.width + RUBBERBAND_SCROLL_THRESHOLD + 1;
2469 		x = allocation.width - 1;
2470 	} else {
2471 		x_scroll = 0;
2472 	}
2473 
2474 	if (y < RUBBERBAND_SCROLL_THRESHOLD) {
2475 		y_scroll = y - RUBBERBAND_SCROLL_THRESHOLD;
2476 		y = 0;
2477 	} else if (y >= allocation.height - RUBBERBAND_SCROLL_THRESHOLD) {
2478 		y_scroll = y - allocation.height + RUBBERBAND_SCROLL_THRESHOLD + 1;
2479 		y = allocation.height - 1;
2480 	} else {
2481 		y_scroll = 0;
2482 	}
2483 
2484 	if (y_scroll == 0 && x_scroll == 0
2485 	    && (int) band_info->prev_x == x && (int) band_info->prev_y == y && !adj_changed) {
2486 		return TRUE;
2487 	}
2488 
2489 	nautilus_canvas_container_scroll (container, x_scroll, y_scroll);
2490 
2491 	/* Remember to convert from widget to scrolled window coords */
2492 	eel_canvas_window_to_world (EEL_CANVAS (container),
2493 				    x + gtk_adjustment_get_value (gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (container))),
2494 				    y + gtk_adjustment_get_value (gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (container))),
2495 				    &world_x, &world_y);
2496 
2497 	if (world_x < band_info->start_x) {
2498 		x1 = world_x;
2499 		x2 = band_info->start_x;
2500 	} else {
2501 		x1 = band_info->start_x;
2502 		x2 = world_x;
2503 	}
2504 
2505 	if (world_y < band_info->start_y) {
2506 		y1 = world_y;
2507 		y2 = band_info->start_y;
2508 	} else {
2509 		y1 = band_info->start_y;
2510 		y2 = world_y;
2511 	}
2512 
2513 	/* Don't let the area of the selection rectangle be empty.
2514 	 * Aside from the fact that it would be funny when the rectangle disappears,
2515 	 * this also works around a crash in libart that happens sometimes when a
2516 	 * zero height rectangle is passed.
2517 	 */
2518 	x2 = MAX (x1 + 1, x2);
2519 	y2 = MAX (y1 + 1, y2);
2520 
2521 	eel_canvas_item_set
2522 		(band_info->selection_rectangle,
2523 		 "x1", x1, "y1", y1,
2524 		 "x2", x2, "y2", y2,
2525 		 NULL);
2526 
2527 	selection_rect.x0 = x1;
2528 	selection_rect.y0 = y1;
2529 	selection_rect.x1 = x2;
2530 	selection_rect.y1 = y2;
2531 
2532 	rubberband_select (container,
2533 			   &band_info->prev_rect,
2534 			   &selection_rect);
2535 	
2536 	band_info->prev_x = x;
2537 	band_info->prev_y = y;
2538 
2539 	band_info->prev_rect = selection_rect;
2540 
2541 	return TRUE;
2542 }
2543 
2544 static void
2545 start_rubberbanding (NautilusCanvasContainer *container,
2546 		     GdkEventButton *event)
2547 {
2548 	AtkObject *accessible;
2549 	NautilusCanvasContainerDetails *details;
2550 	NautilusCanvasRubberbandInfo *band_info;
2551 	GdkRGBA bg_color, border_color;
2552 	GList *p;
2553 	NautilusCanvasIcon *icon;
2554 	GtkStyleContext *context;
2555 
2556 	details = container->details;
2557 	band_info = &details->rubberband_info;
2558 
2559 	g_signal_emit (container,
2560 		       signals[BAND_SELECT_STARTED], 0);
2561 
2562 	for (p = details->icons; p != NULL; p = p->next) {
2563 		icon = p->data;
2564 		icon->was_selected_before_rubberband = icon->is_selected;
2565 	}
2566 
2567 	eel_canvas_window_to_world
2568 		(EEL_CANVAS (container), event->x, event->y,
2569 		 &band_info->start_x, &band_info->start_y);
2570 
2571 	context = gtk_widget_get_style_context (GTK_WIDGET (container));
2572 	gtk_style_context_save (context);
2573 	gtk_style_context_add_class (context, GTK_STYLE_CLASS_RUBBERBAND);
2574 
2575 	gtk_style_context_get_background_color (context, GTK_STATE_FLAG_NORMAL, &bg_color);
2576 	gtk_style_context_get_border_color (context, GTK_STATE_FLAG_NORMAL, &border_color);
2577 
2578 	gtk_style_context_restore (context);
2579 
2580 	band_info->selection_rectangle = eel_canvas_item_new
2581 		(eel_canvas_root
2582 		 (EEL_CANVAS (container)),
2583 		 NAUTILUS_TYPE_SELECTION_CANVAS_ITEM,
2584 		 "x1", band_info->start_x,
2585 		 "y1", band_info->start_y,
2586 		 "x2", band_info->start_x,
2587 		 "y2", band_info->start_y,
2588 		 "fill_color_rgba", &bg_color,
2589 		 "outline_color_rgba", &border_color,
2590 		 "width_pixels", 1,
2591 		 NULL);
2592 
2593 	accessible = atk_gobject_accessible_for_object
2594 		(G_OBJECT (band_info->selection_rectangle));
2595 	atk_object_set_name (accessible, "selection");
2596 	atk_object_set_description (accessible, _("The selection rectangle"));
2597 
2598 	band_info->prev_x = event->x - gtk_adjustment_get_value (gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (container)));
2599 	band_info->prev_y = event->y - gtk_adjustment_get_value (gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (container)));
2600 
2601 	band_info->active = TRUE;
2602 
2603 	if (band_info->timer_id == 0) {
2604 		band_info->timer_id = g_timeout_add
2605 			(RUBBERBAND_TIMEOUT_INTERVAL,
2606 			 rubberband_timeout_callback,
2607 			 container);
2608 	}
2609 
2610 	eel_canvas_item_grab (band_info->selection_rectangle,
2611 			      (GDK_POINTER_MOTION_MASK
2612 			       | GDK_BUTTON_RELEASE_MASK 
2613 			       | GDK_SCROLL_MASK),
2614 			      NULL, event->time);
2615 }
2616 
2617 static void
2618 stop_rubberbanding (NautilusCanvasContainer *container,
2619 		    guint32 time)
2620 {
2621 	NautilusCanvasRubberbandInfo *band_info;
2622 	GList *icons;
2623 	gboolean enable_animation;
2624 
2625 	band_info = &container->details->rubberband_info;
2626 
2627 	g_assert (band_info->timer_id != 0);
2628 	g_source_remove (band_info->timer_id);
2629 	band_info->timer_id = 0;
2630 
2631 	band_info->active = FALSE;
2632 
2633 	g_object_get (gtk_settings_get_default (), "gtk-enable-animations", &enable_animation, NULL);
2634 
2635 	/* Destroy this canvas item; the parent will unref it. */
2636 	eel_canvas_item_ungrab (band_info->selection_rectangle, time);
2637 	eel_canvas_item_lower_to_bottom (band_info->selection_rectangle);
2638 	if (enable_animation) {
2639 		nautilus_selection_canvas_item_fade_out (NAUTILUS_SELECTION_CANVAS_ITEM (band_info->selection_rectangle), 150);
2640 	} else {
2641 		eel_canvas_item_destroy (band_info->selection_rectangle);
2642 	}
2643 	band_info->selection_rectangle = NULL;
2644 
2645 	/* if only one item has been selected, use it as range
2646 	 * selection base (cf. handle_icon_button_press) */
2647 	icons = nautilus_canvas_container_get_selected_icons (container);
2648 	if (g_list_length (icons) == 1) {
2649 		container->details->range_selection_base_icon = icons->data;
2650 	}
2651 	g_list_free (icons);
2652 
2653 	g_signal_emit (container,
2654 		       signals[BAND_SELECT_ENDED], 0);
2655 }
2656 
2657 /* Keyboard navigation.  */
2658 
2659 typedef gboolean (* IsBetterCanvasFunction) (NautilusCanvasContainer *container,
2660 					     NautilusCanvasIcon *start_icon,
2661 					     NautilusCanvasIcon *best_so_far,
2662 					     NautilusCanvasIcon *candidate,
2663 					     void *data);
2664 
2665 static NautilusCanvasIcon *
2666 find_best_icon (NautilusCanvasContainer *container,
2667 		  NautilusCanvasIcon *start_icon,
2668 		  IsBetterCanvasFunction function,
2669 		  void *data)
2670 {
2671 	GList *p;
2672 	NautilusCanvasIcon *best, *candidate;
2673 
2674 	best = NULL;
2675 	for (p = container->details->icons; p != NULL; p = p->next) {
2676 		candidate = p->data;
2677 
2678 		if (candidate != start_icon) {
2679 			if ((* function) (container, start_icon, best, candidate, data)) {
2680 				best = candidate;
2681 			}
2682 		}
2683 	}
2684 	return best;
2685 }
2686 
2687 static NautilusCanvasIcon *
2688 find_best_selected_icon (NautilusCanvasContainer *container,
2689 			   NautilusCanvasIcon *start_icon,
2690 			   IsBetterCanvasFunction function,
2691 			   void *data)
2692 {
2693 	GList *p;
2694 	NautilusCanvasIcon *best, *candidate;
2695 
2696 	best = NULL;
2697 	for (p = container->details->icons; p != NULL; p = p->next) {
2698 		candidate = p->data;
2699 
2700 		if (candidate != start_icon && candidate->is_selected) {
2701 			if ((* function) (container, start_icon, best, candidate, data)) {
2702 				best = candidate;
2703 			}
2704 		}
2705 	}
2706 	return best;
2707 }
2708 
2709 static int
2710 compare_icons_by_uri (NautilusCanvasContainer *container,
2711 			NautilusCanvasIcon *icon_a,
2712 			NautilusCanvasIcon *icon_b)
2713 {
2714 	char *uri_a, *uri_b;
2715 	int result;
2716 
2717 	g_assert (NAUTILUS_IS_CANVAS_CONTAINER (container));
2718 	g_assert (icon_a != NULL);
2719 	g_assert (icon_b != NULL);
2720 	g_assert (icon_a != icon_b);
2721 
2722 	uri_a = nautilus_canvas_container_get_icon_uri (container, icon_a);
2723 	uri_b = nautilus_canvas_container_get_icon_uri (container, icon_b);
2724 	result = strcmp (uri_a, uri_b);
2725 	g_assert (result != 0);
2726 	g_free (uri_a);
2727 	g_free (uri_b);
2728 	
2729 	return result;
2730 }
2731 
2732 static int
2733 get_cmp_point_x (NautilusCanvasContainer *container,
2734 		 EelDRect icon_rect)
2735 {
2736 	return (icon_rect.x0 + icon_rect.x1) / 2;
2737 }
2738 
2739 static int
2740 get_cmp_point_y (NautilusCanvasContainer *container,
2741 		 EelDRect icon_rect)
2742 {
2743 	return icon_rect.y1;
2744 }
2745 
2746 
2747 static int
2748 compare_icons_horizontal (NautilusCanvasContainer *container,
2749 			    NautilusCanvasIcon *icon_a,
2750 			    NautilusCanvasIcon *icon_b)
2751 {
2752 	EelDRect world_rect;
2753 	int ax, bx;
2754 
2755 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_a->item);
2756 	eel_canvas_w2c
2757 		(EEL_CANVAS (container),
2758 		 get_cmp_point_x (container, world_rect),
2759 		 get_cmp_point_y (container, world_rect),
2760 		 &ax,
2761 		 NULL);
2762 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_b->item);
2763 	eel_canvas_w2c
2764 		(EEL_CANVAS (container),
2765 		 get_cmp_point_x (container, world_rect),
2766 		 get_cmp_point_y (container, world_rect),
2767 		 &bx,
2768 		 NULL);
2769 	
2770 	if (ax < bx) {
2771 		return -1;
2772 	}
2773 	if (ax > bx) {
2774 		return +1;
2775 	}
2776 	return 0;
2777 }
2778 
2779 static int
2780 compare_icons_vertical (NautilusCanvasContainer *container,
2781 			  NautilusCanvasIcon *icon_a,
2782 			  NautilusCanvasIcon *icon_b)
2783 {
2784 	EelDRect world_rect;
2785 	int ay, by;
2786 
2787 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_a->item);
2788 	eel_canvas_w2c
2789 		(EEL_CANVAS (container),
2790 		 get_cmp_point_x (container, world_rect),
2791 		 get_cmp_point_y (container, world_rect),
2792 		 NULL,
2793 		 &ay);
2794 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_b->item);
2795 	eel_canvas_w2c
2796 		(EEL_CANVAS (container),
2797 		 get_cmp_point_x (container, world_rect),
2798 		 get_cmp_point_y (container, world_rect),
2799 		 NULL,
2800 		 &by);
2801 	
2802 	if (ay < by) {
2803 		return -1;
2804 	}
2805 	if (ay > by) {
2806 		return +1;
2807 	}
2808 	return 0;
2809 }
2810 
2811 static int
2812 compare_icons_horizontal_first (NautilusCanvasContainer *container,
2813 				  NautilusCanvasIcon *icon_a,
2814 				  NautilusCanvasIcon *icon_b)
2815 {
2816 	EelDRect world_rect;
2817 	int ax, ay, bx, by;
2818 
2819 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_a->item);
2820 	eel_canvas_w2c
2821 		(EEL_CANVAS (container),
2822 		 get_cmp_point_x (container, world_rect),
2823 		 get_cmp_point_y (container, world_rect),
2824 		 &ax,
2825 		 &ay);
2826 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_b->item);
2827 	eel_canvas_w2c
2828 		(EEL_CANVAS (container),
2829 		 get_cmp_point_x (container, world_rect),
2830 		 get_cmp_point_y (container, world_rect),
2831 		 &bx,
2832 		 &by);
2833 	
2834 	if (ax < bx) {
2835 		return -1;
2836 	}
2837 	if (ax > bx) {
2838 		return +1;
2839 	}
2840 	if (ay < by) {
2841 		return -1;
2842 	}
2843 	if (ay > by) {
2844 		return +1;
2845 	}
2846 	return compare_icons_by_uri (container, icon_a, icon_b);
2847 }
2848 
2849 static int
2850 compare_icons_vertical_first (NautilusCanvasContainer *container,
2851 				NautilusCanvasIcon *icon_a,
2852 				NautilusCanvasIcon *icon_b)
2853 {
2854 	EelDRect world_rect;
2855 	int ax, ay, bx, by;
2856 
2857 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_a->item);
2858 	eel_canvas_w2c
2859 		(EEL_CANVAS (container),
2860 		 get_cmp_point_x (container, world_rect),
2861 		 get_cmp_point_y (container, world_rect),
2862 		 &ax,
2863 		 &ay);
2864 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon_b->item);
2865 	eel_canvas_w2c
2866 		(EEL_CANVAS (container),
2867 		 get_cmp_point_x (container, world_rect),
2868 		 get_cmp_point_y (container, world_rect),
2869 		 &bx,
2870 		 &by);
2871 	
2872 	if (ay < by) {
2873 		return -1;
2874 	}
2875 	if (ay > by) {
2876 		return +1;
2877 	}
2878 	if (ax < bx) {
2879 		return -1;
2880 	}
2881 	if (ax > bx) {
2882 		return +1;
2883 	}
2884 	return compare_icons_by_uri (container, icon_a, icon_b);
2885 }
2886 
2887 static gboolean
2888 leftmost_in_top_row (NautilusCanvasContainer *container,
2889 		     NautilusCanvasIcon *start_icon,
2890 		     NautilusCanvasIcon *best_so_far,
2891 		     NautilusCanvasIcon *candidate,
2892 		     void *data)
2893 {
2894 	if (best_so_far == NULL) {
2895 		return TRUE;
2896 	}
2897 	return compare_icons_vertical_first (container, best_so_far, candidate) > 0;
2898 }
2899 
2900 static gboolean
2901 rightmost_in_top_row (NautilusCanvasContainer *container,
2902 		      NautilusCanvasIcon *start_icon,
2903 		      NautilusCanvasIcon *best_so_far,
2904 		      NautilusCanvasIcon *candidate,
2905 		      void *data)
2906 {
2907 	if (best_so_far == NULL) {
2908 		return TRUE;
2909 	}
2910 	return compare_icons_vertical (container, best_so_far, candidate) > 0;
2911 	return compare_icons_horizontal (container, best_so_far, candidate) < 0;
2912 }
2913 
2914 static gboolean
2915 rightmost_in_bottom_row (NautilusCanvasContainer *container,
2916 			 NautilusCanvasIcon *start_icon,
2917 			 NautilusCanvasIcon *best_so_far,
2918 			 NautilusCanvasIcon *candidate,
2919 			 void *data)
2920 {
2921 	if (best_so_far == NULL) {
2922 		return TRUE;
2923 	}
2924 	return compare_icons_vertical_first (container, best_so_far, candidate) < 0;
2925 }
2926 
2927 static int
2928 compare_with_start_row (NautilusCanvasContainer *container,
2929 			NautilusCanvasIcon *icon)
2930 {
2931 	EelCanvasItem *item;
2932 
2933 	item = EEL_CANVAS_ITEM (icon->item);
2934 	
2935 	if (container->details->arrow_key_start_y < item->y1) {
2936 		return -1;
2937 	}
2938 	if (container->details->arrow_key_start_y > item->y2) {
2939 		return +1;
2940 	}
2941 	return 0;
2942 }
2943 
2944 static int
2945 compare_with_start_column (NautilusCanvasContainer *container,
2946 			   NautilusCanvasIcon *icon)
2947 {
2948 	EelCanvasItem *item;
2949 
2950 	item = EEL_CANVAS_ITEM (icon->item);
2951 	
2952 	if (container->details->arrow_key_start_x < item->x1) {
2953 		return -1;
2954 	}
2955 	if (container->details->arrow_key_start_x > item->x2) {
2956 		return +1;
2957 	}
2958 	return 0;
2959 }
2960 
2961 static gboolean
2962 same_row_right_side_leftmost (NautilusCanvasContainer *container,
2963 			      NautilusCanvasIcon *start_icon,
2964 			      NautilusCanvasIcon *best_so_far,
2965 			      NautilusCanvasIcon *candidate,
2966 			      void *data)
2967 {
2968 	/* Candidates not on the start row do not qualify. */
2969 	if (compare_with_start_row (container, candidate) != 0) {
2970 		return FALSE;
2971 	}
2972 
2973 	/* Candidates that are farther right lose out. */
2974 	if (best_so_far != NULL) {
2975 		if (compare_icons_horizontal_first (container,
2976 						      best_so_far,
2977 						      candidate) < 0) {
2978 			return FALSE;
2979 		}
2980 	}
2981 
2982 	/* Candidate to the left of the start do not qualify. */
2983 	if (compare_icons_horizontal_first (container,
2984 					      candidate,
2985 					      start_icon) <= 0) {
2986 		return FALSE;
2987 	}
2988 
2989 	return TRUE;
2990 }
2991 
2992 static gboolean
2993 same_row_left_side_rightmost (NautilusCanvasContainer *container,
2994 			      NautilusCanvasIcon *start_icon,
2995 			      NautilusCanvasIcon *best_so_far,
2996 			      NautilusCanvasIcon *candidate,
2997 			      void *data)
2998 {
2999 	/* Candidates not on the start row do not qualify. */
3000 	if (compare_with_start_row (container, candidate) != 0) {
3001 		return FALSE;
3002 	}
3003 
3004 	/* Candidates that are farther left lose out. */
3005 	if (best_so_far != NULL) {
3006 		if (compare_icons_horizontal_first (container,
3007 						      best_so_far,
3008 						      candidate) > 0) {
3009 			return FALSE;
3010 		}
3011 	}
3012 
3013 	/* Candidate to the right of the start do not qualify. */
3014 	if (compare_icons_horizontal_first (container,
3015 					      candidate,
3016 					      start_icon) >= 0) {
3017 		return FALSE;
3018 	}
3019 
3020 	return TRUE;
3021 }
3022 
3023 static gboolean
3024 next_row_leftmost (NautilusCanvasContainer *container,
3025 		   NautilusCanvasIcon *start_icon,
3026 	           NautilusCanvasIcon *best_so_far,
3027 		   NautilusCanvasIcon *candidate,
3028 		   void *data)
3029 {
3030 	/* sort out icons that are not below the current row */
3031 	if (compare_with_start_row (container, candidate) >= 0) {
3032 		return FALSE;
3033 	}
3034 
3035 	if (best_so_far != NULL) {
3036 		if (compare_icons_vertical_first (container,
3037 						    best_so_far,
3038 						    candidate) > 0) {
3039 			/* candidate is above best choice, but below the current row */
3040 			return TRUE;
3041 		}
3042 
3043 		if (compare_icons_horizontal_first (container,
3044 						      best_so_far,
3045 						      candidate) > 0) {
3046 			return TRUE;
3047 		}
3048 	}
3049 
3050 	return best_so_far == NULL;
3051 }
3052 
3053 static gboolean
3054 next_row_rightmost (NautilusCanvasContainer *container,
3055 		    NautilusCanvasIcon *start_icon,
3056 		    NautilusCanvasIcon *best_so_far,
3057 		    NautilusCanvasIcon *candidate,
3058 		    void *data)
3059 {
3060 	/* sort out icons that are not below the current row */
3061 	if (compare_with_start_row (container, candidate) >= 0) {
3062 		return FALSE;
3063 	}
3064 
3065 	if (best_so_far != NULL) {
3066 		if (compare_icons_vertical_first (container,
3067 						    best_so_far,
3068 						    candidate) > 0) {
3069 			/* candidate is above best choice, but below the current row */
3070 			return TRUE;
3071 		}
3072 
3073 		if (compare_icons_horizontal_first (container,
3074 						      best_so_far,
3075 						      candidate) < 0) {
3076 			return TRUE;
3077 		}
3078 	}
3079 
3080 	return best_so_far == NULL;
3081 }
3082 
3083 static gboolean
3084 next_column_bottommost (NautilusCanvasContainer *container,
3085 			NautilusCanvasIcon *start_icon,
3086 			NautilusCanvasIcon *best_so_far,
3087 			NautilusCanvasIcon *candidate,
3088 			void *data)
3089 {
3090 	/* sort out icons that are not on the right of the current column */
3091 	if (compare_with_start_column (container, candidate) >= 0) {
3092 		return FALSE;
3093 	}
3094 
3095 	if (best_so_far != NULL) {
3096 		if (compare_icons_horizontal_first (container,
3097 						      best_so_far,
3098 						      candidate) > 0) {
3099 			/* candidate is above best choice, but below the current row */
3100 			return TRUE;
3101 		}
3102 
3103 		if (compare_icons_vertical_first (container,
3104 						    best_so_far,
3105 						    candidate) < 0) {
3106 			return TRUE;
3107 		}
3108 	}
3109 
3110 	return best_so_far == NULL;
3111 }
3112 
3113 static gboolean
3114 previous_row_rightmost (NautilusCanvasContainer *container,
3115 		        NautilusCanvasIcon *start_icon,
3116 			NautilusCanvasIcon *best_so_far,
3117 			NautilusCanvasIcon *candidate,
3118 			void *data)
3119 {
3120 	/* sort out icons that are not above the current row */
3121 	if (compare_with_start_row (container, candidate) <= 0) {
3122 		return FALSE;
3123 	}
3124 
3125 	if (best_so_far != NULL) {
3126 		if (compare_icons_vertical_first (container,
3127 						    best_so_far,
3128 						    candidate) < 0) {
3129 			/* candidate is below the best choice, but above the current row */
3130 			return TRUE;
3131 		}
3132 
3133 		if (compare_icons_horizontal_first (container,
3134 						      best_so_far,
3135 						      candidate) < 0) {
3136 			return TRUE;
3137 		}
3138 	}
3139 
3140 	return best_so_far == NULL;
3141 }
3142 
3143 static gboolean
3144 same_column_above_lowest (NautilusCanvasContainer *container,
3145 			  NautilusCanvasIcon *start_icon,
3146 			  NautilusCanvasIcon *best_so_far,
3147 			  NautilusCanvasIcon *candidate,
3148 			  void *data)
3149 {
3150 	/* Candidates not on the start column do not qualify. */
3151 	if (compare_with_start_column (container, candidate) != 0) {
3152 		return FALSE;
3153 	}
3154 
3155 	/* Candidates that are higher lose out. */
3156 	if (best_so_far != NULL) {
3157 		if (compare_icons_vertical_first (container,
3158 						    best_so_far,
3159 						    candidate) > 0) {
3160 			return FALSE;
3161 		}
3162 	}
3163 
3164 	/* Candidates below the start do not qualify. */
3165 	if (compare_icons_vertical_first (container,
3166 					    candidate,
3167 					    start_icon) >= 0) {
3168 		return FALSE;
3169 	}
3170 
3171 	return TRUE;
3172 }
3173 
3174 static gboolean
3175 same_column_below_highest (NautilusCanvasContainer *container,
3176 			   NautilusCanvasIcon *start_icon,
3177 			   NautilusCanvasIcon *best_so_far,
3178 			   NautilusCanvasIcon *candidate,
3179 			   void *data)
3180 {
3181 	/* Candidates not on the start column do not qualify. */
3182 	if (compare_with_start_column (container, candidate) != 0) {
3183 		return FALSE;
3184 	}
3185 
3186 	/* Candidates that are lower lose out. */
3187 	if (best_so_far != NULL) {
3188 		if (compare_icons_vertical_first (container,
3189 						    best_so_far,
3190 						    candidate) < 0) {
3191 			return FALSE;
3192 		}
3193 	}
3194 
3195 	/* Candidates above the start do not qualify. */
3196 	if (compare_icons_vertical_first (container,
3197 					    candidate,
3198 					    start_icon) <= 0) {
3199 		return FALSE;
3200 	}
3201 
3202 	return TRUE;
3203 }
3204 
3205 static gboolean
3206 previous_column_highest (NautilusCanvasContainer *container,
3207 			 NautilusCanvasIcon *start_icon,
3208 			 NautilusCanvasIcon *best_so_far,
3209 			 NautilusCanvasIcon *candidate,
3210 			 void *data)
3211 {
3212 	/* sort out icons that are not before the current column */
3213 	if (compare_with_start_column (container, candidate) <= 0) {
3214 		return FALSE;
3215 	}
3216 
3217 	if (best_so_far != NULL) {
3218 		if (compare_icons_horizontal (container,
3219 						best_so_far,
3220 						candidate) < 0) {
3221 			/* candidate is right of the best choice, but left of the current column */
3222 			return TRUE;
3223 		}
3224 
3225 		if (compare_icons_vertical (container,
3226 					      best_so_far,
3227 					      candidate) > 0) {
3228 			return TRUE;
3229 		}
3230 	}
3231 
3232 	return best_so_far == NULL;
3233 }
3234 
3235 
3236 static gboolean
3237 next_column_highest (NautilusCanvasContainer *container,
3238 		     NautilusCanvasIcon *start_icon,
3239 		     NautilusCanvasIcon *best_so_far,
3240 		     NautilusCanvasIcon *candidate,
3241 		     void *data)
3242 {
3243 	/* sort out icons that are not after the current column */
3244 	if (compare_with_start_column (container, candidate) >= 0) {
3245 		return FALSE;
3246 	}
3247 
3248 	if (best_so_far != NULL) {
3249 		if (compare_icons_horizontal_first (container,
3250 						      best_so_far,
3251 						      candidate) > 0) {
3252 			/* candidate is left of the best choice, but right of the current column */
3253 			return TRUE;
3254 		}
3255 
3256 		if (compare_icons_vertical_first (container,
3257 						    best_so_far,
3258 						    candidate) > 0) {
3259 			return TRUE;
3260 		}
3261 	}
3262 
3263 	return best_so_far == NULL;
3264 }
3265 
3266 static gboolean
3267 previous_column_lowest (NautilusCanvasContainer *container,
3268 		        NautilusCanvasIcon *start_icon,
3269 			NautilusCanvasIcon *best_so_far,
3270 			NautilusCanvasIcon *candidate,
3271 			void *data)
3272 {
3273 	/* sort out icons that are not before the current column */
3274 	if (compare_with_start_column (container, candidate) <= 0) {
3275 		return FALSE;
3276 	}
3277 
3278 	if (best_so_far != NULL) {
3279 		if (compare_icons_horizontal_first (container,
3280 						      best_so_far,
3281 						      candidate) < 0) {
3282 			/* candidate is right of the best choice, but left of the current column */
3283 			return TRUE;
3284 		}
3285 
3286 		if (compare_icons_vertical_first (container,
3287 						    best_so_far,
3288 						    candidate) < 0) {
3289 			return TRUE;
3290 		}
3291 	}
3292 
3293 	return best_so_far == NULL;
3294 }
3295 
3296 static gboolean
3297 last_column_lowest (NautilusCanvasContainer *container,
3298 		    NautilusCanvasIcon *start_icon,
3299 		    NautilusCanvasIcon *best_so_far,
3300 		    NautilusCanvasIcon *candidate,
3301 		    void *data)
3302 {
3303 	if (best_so_far == NULL) {
3304 		return TRUE;
3305 	}
3306 	return compare_icons_horizontal_first (container, best_so_far, candidate) < 0;
3307 }
3308 
3309 static gboolean
3310 closest_in_90_degrees (NautilusCanvasContainer *container,
3311 		       NautilusCanvasIcon *start_icon,
3312 		       NautilusCanvasIcon *best_so_far,
3313 		       NautilusCanvasIcon *candidate,
3314 		       void *data)
3315 {
3316 	EelDRect world_rect;
3317 	int x, y;
3318 	int dx, dy;
3319 	int dist;
3320 	int *best_dist;
3321 
3322 
3323 	world_rect = nautilus_canvas_item_get_icon_rectangle (candidate->item);
3324 	eel_canvas_w2c
3325 		(EEL_CANVAS (container),
3326 		 get_cmp_point_x (container, world_rect),
3327 		 get_cmp_point_y (container, world_rect),
3328 		 &x,
3329 		 &y);
3330 
3331 	dx = x - container->details->arrow_key_start_x;
3332 	dy = y - container->details->arrow_key_start_y;
3333 	
3334 	switch (container->details->arrow_key_direction) {
3335 	case GTK_DIR_UP:
3336 		if (dy > 0 ||
3337 		    ABS(dx) > ABS(dy)) {
3338 			return FALSE;
3339 		}
3340 		break;
3341 	case GTK_DIR_DOWN:
3342 		if (dy < 0 ||
3343 		    ABS(dx) > ABS(dy)) {
3344 			return FALSE;
3345 		}
3346 		break;
3347 	case GTK_DIR_LEFT:
3348 		if (dx > 0 ||
3349 		    ABS(dy) > ABS(dx)) {
3350 			return FALSE;
3351 		}
3352 		break;
3353 	case GTK_DIR_RIGHT:
3354 		if (dx < 0 ||
3355 		    ABS(dy) > ABS(dx)) {
3356 			return FALSE;
3357 		}
3358 		break;
3359 	default:
3360 		g_assert_not_reached();
3361 	}
3362 
3363 	dist = dx*dx + dy*dy;
3364 	best_dist = data;
3365 	
3366 	if (best_so_far == NULL) {
3367 		*best_dist = dist;
3368 		return TRUE;
3369 	}
3370 
3371 	if (dist < *best_dist) {
3372 		*best_dist = dist;
3373 		return TRUE;
3374 	}
3375 
3376 	return FALSE;
3377 }
3378 
3379 static EelDRect 
3380 get_rubberband (NautilusCanvasIcon *icon1,
3381 		NautilusCanvasIcon *icon2)
3382 {
3383 	EelDRect rect1;
3384 	EelDRect rect2;
3385 	EelDRect ret;
3386 
3387 	eel_canvas_item_get_bounds (EEL_CANVAS_ITEM (icon1->item),
3388 				    &rect1.x0, &rect1.y0, 
3389 				    &rect1.x1, &rect1.y1);
3390 	eel_canvas_item_get_bounds (EEL_CANVAS_ITEM (icon2->item),
3391 				    &rect2.x0, &rect2.y0, 
3392 				    &rect2.x1, &rect2.y1);
3393 
3394 	eel_drect_union (&ret, &rect1, &rect2);
3395 
3396 	return ret;
3397 }
3398 
3399 static void
3400 keyboard_move_to (NautilusCanvasContainer *container,
3401 		  NautilusCanvasIcon *icon,
3402 		  NautilusCanvasIcon *from,
3403 		  GdkEventKey *event)
3404 {
3405 	if (icon == NULL) {
3406 		return;
3407 	}
3408 
3409 	if (event != NULL &&
3410 	    (event->state & GDK_CONTROL_MASK) != 0 &&
3411 	    (event->state & GDK_SHIFT_MASK) == 0) {
3412 		/* Move the keyboard focus. Use Control modifier
3413 		 * rather than Alt to avoid Sawfish conflict.
3414 		 */
3415 		set_keyboard_focus (container, icon);
3416 		container->details->keyboard_rubberband_start = NULL;
3417 	} else if (event != NULL &&
3418 		   ((event->state & GDK_CONTROL_MASK) != 0 ||
3419 		    !container->details->auto_layout) &&
3420 		   (event->state & GDK_SHIFT_MASK) != 0) {
3421 		/* Do rubberband selection */		
3422 		EelDRect rect;
3423 
3424 		if (from && !container->details->keyboard_rubberband_start) {
3425 			set_keyboard_rubberband_start (container, from);
3426 		} 
3427 
3428 		set_keyboard_focus (container, icon);
3429 
3430 		if (icon && container->details->keyboard_rubberband_start) {
3431 			rect = get_rubberband (container->details->keyboard_rubberband_start,
3432 					       icon);
3433 			rubberband_select (container, NULL, &rect);
3434 		}
3435 	} else if (event != NULL &&
3436 		   (event->state & GDK_CONTROL_MASK) == 0 &&
3437 		   (event->state & GDK_SHIFT_MASK) != 0) {
3438 		/* Select range */
3439 		NautilusCanvasIcon *start_icon;
3440 
3441 		start_icon = container->details->range_selection_base_icon;
3442 		if (start_icon == NULL || !start_icon->is_selected) {
3443 			start_icon = icon;
3444 			container->details->range_selection_base_icon = icon;
3445 		} 
3446 
3447 		set_keyboard_focus (container, icon);
3448 
3449 		if (select_range (container, start_icon, icon, TRUE)) {
3450 			g_signal_emit (container,
3451 				       signals[SELECTION_CHANGED], 0);
3452 		}
3453 	} else {
3454 		/* Select icons and get rid of the special keyboard focus. */
3455 		clear_keyboard_focus (container);
3456 		clear_keyboard_rubberband_start (container);
3457 		
3458 		container->details->range_selection_base_icon = icon;
3459 		if (select_one_unselect_others (container, icon)) {
3460 			g_signal_emit (container,
3461 				       signals[SELECTION_CHANGED], 0);
3462 		}
3463 	}
3464 	schedule_keyboard_icon_reveal (container, icon);
3465 }
3466 
3467 static void
3468 keyboard_home (NautilusCanvasContainer *container,
3469 	       GdkEventKey *event)
3470 {
3471 	NautilusCanvasIcon *from;
3472 	NautilusCanvasIcon *to;
3473 	
3474 	/* Home selects the first canvas.
3475 	 * Control-Home sets the keyboard focus to the first canvas.
3476 	 */
3477 
3478 	from = find_best_selected_icon (container, NULL,
3479 					  rightmost_in_bottom_row, 
3480 					  NULL);
3481 	to = find_best_icon (container, NULL, leftmost_in_top_row, NULL);	
3482 
3483 	keyboard_move_to (container, to, from, event);
3484 }
3485 
3486 static void
3487 keyboard_end (NautilusCanvasContainer *container,
3488 	      GdkEventKey *event)
3489 {
3490 	NautilusCanvasIcon *to;
3491 	NautilusCanvasIcon *from;
3492 
3493 	/* End selects the last canvas.
3494 	 * Control-End sets the keyboard focus to the last canvas.
3495 	 */
3496 	from = find_best_selected_icon (container, NULL,
3497 					  leftmost_in_top_row, 
3498 					  NULL);
3499 	to = find_best_icon (container, NULL,
3500 			       nautilus_canvas_container_is_layout_vertical (container) ?
3501 			       last_column_lowest :
3502 			       rightmost_in_bottom_row,
3503 			       NULL);
3504 
3505 	keyboard_move_to (container, to, from, event);
3506 }
3507 
3508 static void
3509 record_arrow_key_start (NautilusCanvasContainer *container,
3510 			NautilusCanvasIcon *icon,
3511 			GtkDirectionType direction)
3512 {
3513 	EelDRect world_rect;
3514 
3515 	world_rect = nautilus_canvas_item_get_icon_rectangle (icon->item);
3516 	eel_canvas_w2c
3517 		(EEL_CANVAS (container),
3518 		 get_cmp_point_x (container, world_rect),
3519 		 get_cmp_point_y (container, world_rect),
3520 		 &container->details->arrow_key_start_x,
3521 		 &container->details->arrow_key_start_y);
3522 	container->details->arrow_key_direction = direction;
3523 }
3524 
3525 static void
3526 keyboard_arrow_key (NautilusCanvasContainer *container,
3527 		    GdkEventKey *event,
3528 		    GtkDirectionType direction,
3529 		    IsBetterCanvasFunction better_start,
3530 		    IsBetterCanvasFunction empty_start,
3531 		    IsBetterCanvasFunction better_destination,
3532 		    IsBetterCanvasFunction better_destination_fallback,
3533 		    IsBetterCanvasFunction better_destination_fallback_fallback,
3534 		    IsBetterCanvasFunction better_destination_manual)
3535 {
3536 	NautilusCanvasIcon *from;
3537 	NautilusCanvasIcon *to;
3538 	int data;
3539 
3540 	/* Chose the icon to start with.
3541 	 * If we have a keyboard focus, start with it.
3542 	 * Otherwise, use the single selected icon.
3543 	 * If there's multiple selection, use the icon farthest toward the end.
3544 	 */
3545 	
3546 	from = container->details->keyboard_focus;
3547 
3548 	if (from == NULL) {
3549 		if (has_multiple_selection (container)) {
3550 			if (all_selected (container)) {
3551 				from = find_best_selected_icon
3552 					(container, NULL,
3553 					 empty_start, NULL);
3554 			} else {
3555 				from = find_best_selected_icon
3556 					(container, NULL,
3557 					 better_start, NULL);
3558 			}
3559 		} else {
3560 			from = get_first_selected_icon (container);
3561 		}
3562 	}
3563 
3564 	/* If there's no icon, select the icon farthest toward the end.
3565 	 * If there is an icon, select the next icon based on the arrow direction.
3566 	 */
3567 	if (from == NULL) {
3568 		to = from = find_best_icon
3569 			(container, NULL,
3570 			 empty_start, NULL);
3571 	} else {
3572 		record_arrow_key_start (container, from, direction);
3573 		
3574 		to = find_best_icon
3575 			(container, from,
3576 			 container->details->auto_layout ? better_destination : better_destination_manual,
3577 			 &data);
3578 
3579 		/* Wrap around to next/previous row/column */
3580 		if (to == NULL &&
3581 		    better_destination_fallback != NULL) {
3582 			to = find_best_icon
3583 				(container, from,
3584 				 better_destination_fallback,
3585 				 &data);
3586 		}
3587 
3588 		/* With a layout like
3589 		 * 1 2 3
3590 		 * 4
3591 		 * (horizontal layout)
3592 		 *
3593 		 * or
3594 		 *
3595 		 * 1 4
3596 		 * 2
3597 		 * 3 
3598 		 * (vertical layout)
3599 		 *
3600 		 * * pressing down for any of 1,2,3 (horizontal layout)
3601 		 * * pressing right for any of 1,2,3 (vertical layout)
3602 		 *
3603 		 * Should select 4.
3604 		 */
3605 		if (to == NULL &&
3606 		    container->details->auto_layout &&
3607 		    better_destination_fallback_fallback != NULL) {
3608 			to = find_best_icon
3609 				(container, from,
3610 				 better_destination_fallback_fallback,
3611 				 &data);
3612 		}
3613 
3614 		if (to == NULL) { 
3615 			to = from;
3616 		}
3617 
3618 	}
3619 
3620 	keyboard_move_to (container, to, from, event);
3621 }
3622 
3623 static gboolean
3624 is_rectangle_selection_event (GdkEventKey *event)
3625 {
3626 	return (event->state & GDK_CONTROL_MASK) != 0 &&
3627 		(event->state & GDK_SHIFT_MASK) != 0;
3628 }
3629 
3630 static void
3631 keyboard_right (NautilusCanvasContainer *container,
3632 		GdkEventKey *event)
3633 {
3634 	IsBetterCanvasFunction fallback;
3635 	IsBetterCanvasFunction next_column_fallback;
3636 
3637 	fallback = NULL;
3638 	if (container->details->auto_layout &&
3639 	    !nautilus_canvas_container_is_layout_vertical (container) &&
3640 	    !is_rectangle_selection_event (event)) {
3641 		fallback = next_row_leftmost;
3642 	}
3643 
3644 	next_column_fallback = NULL;
3645 	if (nautilus_canvas_container_is_layout_vertical (container) &&
3646 	    gtk_widget_get_direction (GTK_WIDGET (container)) != GTK_TEXT_DIR_RTL) {
3647 		next_column_fallback = next_column_bottommost;
3648 	}
3649 
3650 	/* Right selects the next icon in the same row.
3651 	 * Control-Right sets the keyboard focus to the next icon in the same row.
3652 	 */
3653 	keyboard_arrow_key (container,
3654 			    event,
3655 			    GTK_DIR_RIGHT,
3656 			    rightmost_in_bottom_row,
3657 			    nautilus_canvas_container_is_layout_rtl (container) ?
3658 			    rightmost_in_top_row : leftmost_in_top_row,
3659 			    same_row_right_side_leftmost,
3660 			    fallback,
3661 			    next_column_fallback,
3662 			    closest_in_90_degrees);
3663 }
3664 
3665 static void
3666 keyboard_left (NautilusCanvasContainer *container,
3667 	       GdkEventKey *event)
3668 {
3669 	IsBetterCanvasFunction fallback;
3670 	IsBetterCanvasFunction previous_column_fallback;
3671 
3672 	fallback = NULL;
3673 	if (container->details->auto_layout &&
3674 	    !nautilus_canvas_container_is_layout_vertical (container) &&
3675 	    !is_rectangle_selection_event (event)) {
3676 		fallback = previous_row_rightmost;
3677 	}
3678 
3679 	previous_column_fallback = NULL;
3680 	if (nautilus_canvas_container_is_layout_vertical (container) &&
3681 	    gtk_widget_get_direction (GTK_WIDGET (container)) == GTK_TEXT_DIR_RTL) {
3682 		previous_column_fallback = previous_column_lowest;
3683 	}
3684 
3685 	/* Left selects the next icon in the same row.
3686 	 * Control-Left sets the keyboard focus to the next icon in the same row.
3687 	 */
3688 	keyboard_arrow_key (container,
3689 			    event,
3690 			    GTK_DIR_LEFT,
3691 			    rightmost_in_bottom_row,
3692 			    nautilus_canvas_container_is_layout_rtl (container) ?
3693 			    rightmost_in_top_row : leftmost_in_top_row,
3694 			    same_row_left_side_rightmost,
3695 			    fallback,
3696 			    previous_column_fallback,
3697 			    closest_in_90_degrees);
3698 }
3699 
3700 static void
3701 keyboard_down (NautilusCanvasContainer *container,
3702 	       GdkEventKey *event)
3703 {
3704 	IsBetterCanvasFunction fallback;
3705 	IsBetterCanvasFunction next_row_fallback;
3706 
3707 	fallback = NULL;
3708 	if (container->details->auto_layout &&
3709 	    nautilus_canvas_container_is_layout_vertical (container) &&
3710 	    !is_rectangle_selection_event (event)) {
3711 		if (gtk_widget_get_direction (GTK_WIDGET (container)) == GTK_TEXT_DIR_RTL) {
3712 			fallback = previous_column_highest;
3713 		} else {
3714 			fallback = next_column_highest;
3715 		}
3716 	}
3717 
3718 	next_row_fallback = NULL;
3719 	if (!nautilus_canvas_container_is_layout_vertical (container)) {
3720 		if (gtk_widget_get_direction (GTK_WIDGET (container)) == GTK_TEXT_DIR_RTL) {
3721 			next_row_fallback = next_row_leftmost;
3722 		} else {
3723 			next_row_fallback = next_row_rightmost;
3724 		}
3725 	}
3726 
3727 	/* Down selects the next icon in the same column.
3728 	 * Control-Down sets the keyboard focus to the next icon in the same column.
3729 	 */
3730 	keyboard_arrow_key (container,
3731 			    event,
3732 			    GTK_DIR_DOWN,
3733 			    rightmost_in_bottom_row,
3734 			    nautilus_canvas_container_is_layout_rtl (container) ?
3735 			    rightmost_in_top_row : leftmost_in_top_row,
3736 			    same_column_below_highest,
3737 			    fallback,
3738 			    next_row_fallback,
3739 			    closest_in_90_degrees);
3740 }
3741 
3742 static void
3743 keyboard_up (NautilusCanvasContainer *container,
3744 	     GdkEventKey *event)
3745 {
3746 	IsBetterCanvasFunction fallback;
3747 
3748 	fallback = NULL;
3749 	if (container->details->auto_layout &&
3750 	    nautilus_canvas_container_is_layout_vertical (container) &&
3751 	    !is_rectangle_selection_event (event)) {
3752 		if (gtk_widget_get_direction (GTK_WIDGET (container)) == GTK_TEXT_DIR_RTL) {
3753 			fallback = next_column_bottommost;
3754 		} else {
3755 			fallback = previous_column_lowest;
3756 		}
3757 	}
3758 
3759 	/* Up selects the next icon in the same column.
3760 	 * Control-Up sets the keyboard focus to the next icon in the same column.
3761 	 */
3762 	keyboard_arrow_key (container,
3763 			    event,
3764 			    GTK_DIR_UP,
3765 			    rightmost_in_bottom_row,
3766 			    nautilus_canvas_container_is_layout_rtl (container) ?
3767 			    rightmost_in_top_row : leftmost_in_top_row,
3768 			    same_column_above_lowest,
3769 			    fallback,
3770 			    NULL,
3771 			    closest_in_90_degrees);
3772 }
3773 
3774 static void
3775 keyboard_space (NautilusCanvasContainer *container,
3776 		GdkEventKey *event)
3777 {
3778 	NautilusCanvasIcon *icon;
3779 	
3780 	if (!has_selection (container) &&
3781 	    container->details->keyboard_focus != NULL) {
3782 		keyboard_move_to (container,
3783 				  container->details->keyboard_focus,
3784 				  NULL, NULL);
3785 	} else if ((event->state & GDK_CONTROL_MASK) != 0 &&
3786 		   (event->state & GDK_SHIFT_MASK) == 0) {
3787 		/* Control-space toggles the selection state of the current icon. */
3788 		if (container->details->keyboard_focus != NULL) {
3789 			icon_toggle_selected (container, container->details->keyboard_focus);
3790 			g_signal_emit (container, signals[SELECTION_CHANGED], 0);
3791 			if  (container->details->keyboard_focus->is_selected) {
3792 				container->details->range_selection_base_icon = container->details->keyboard_focus;
3793 			} 
3794 		} else {
3795 			icon = find_best_selected_icon (container,
3796 							    NULL,
3797 							    leftmost_in_top_row,
3798 							    NULL);
3799 			if (icon == NULL) {
3800 				icon = find_best_icon (container,
3801 							   NULL,
3802 							   leftmost_in_top_row,
3803 							   NULL);
3804 			}
3805 			if (icon != NULL) {
3806 				set_keyboard_focus (container, icon);
3807 			}
3808 		}
3809 	} else if ((event->state & GDK_SHIFT_MASK) != 0) {
3810 		activate_selected_items_alternate (container, NULL);
3811 	} else {
3812 		preview_selected_items (container);
3813 	}
3814 }
3815 
3816 /* look for the first canvas that matches the longest part of a given
3817  * search pattern
3818  */
3819 typedef struct {
3820 	gunichar *name;
3821 	int last_match_length;
3822 } BestNameMatch;
3823 
3824 #ifndef TAB_NAVIGATION_DISABLED
3825 static void
3826 select_previous_or_next_icon (NautilusCanvasContainer *container, 
3827 				gboolean next, 
3828 				GdkEventKey *event)
3829 {
3830 	NautilusCanvasIcon *icon;
3831 	const GList *item;
3832 
3833 	item = NULL;
3834 	/* Chose the icon to start with.
3835 	 * If we have a keyboard focus, start with it.
3836 	 * Otherwise, use the single selected icon.
3837 	 */
3838 	icon = container->details->keyboard_focus;
3839 	if (icon == NULL) {
3840 		icon = get_first_selected_icon (container);
3841 	}
3842 
3843 	if (icon != NULL) {
3844 		/* must have at least @canvas in the list */
3845 		g_assert (container->details->icons != NULL);
3846 		item = g_list_find (container->details->icons, icon);
3847 		g_assert (item != NULL);
3848 		
3849 		item = next ? item->next : item->prev;
3850 		if (item == NULL) {
3851 			item = next ? g_list_first (container->details->icons) : g_list_last (container->details->icons);
3852 		}
3853 
3854 	} else if (container->details->icons != NULL) {
3855 		/* no selection yet, pick the first or last item to select */
3856 		item = next ? g_list_first (container->details->icons) : g_list_last (container->details->icons);
3857 	}
3858 
3859 	icon = (item != NULL) ? item->data : NULL;
3860 
3861 	if (icon != NULL) {
3862 		keyboard_move_to (container, icon, NULL, event);
3863 	}
3864 }
3865 #endif
3866 
3867 static void
3868 destroy (GtkWidget *object)
3869 {
3870 	NautilusCanvasContainer *container;
3871 
3872 	container = NAUTILUS_CANVAS_CONTAINER (object);
3873 
3874         nautilus_canvas_container_clear (container);
3875 
3876 	if (container->details->rubberband_info.timer_id != 0) {
3877 		g_source_remove (container->details->rubberband_info.timer_id);
3878 		container->details->rubberband_info.timer_id = 0;
3879 	}
3880 
3881         if (container->details->idle_id != 0) {
3882 		g_source_remove (container->details->idle_id);
3883 		container->details->idle_id = 0;
3884 	}
3885 
3886 	if (container->details->stretch_idle_id != 0) {
3887 		g_source_remove (container->details->stretch_idle_id);
3888 		container->details->stretch_idle_id = 0;
3889 	}
3890 
3891         if (container->details->align_idle_id != 0) {
3892 		g_source_remove (container->details->align_idle_id);
3893 		container->details->align_idle_id = 0;
3894 	}
3895 
3896         if (container->details->selection_changed_id != 0) {
3897 		g_source_remove (container->details->selection_changed_id);
3898 		container->details->selection_changed_id = 0;
3899 	}
3900 
3901         if (container->details->size_allocation_count_id != 0) {
3902 		g_source_remove (container->details->size_allocation_count_id);
3903 		container->details->size_allocation_count_id = 0;
3904 	}
3905 
3906 	GTK_WIDGET_CLASS (nautilus_canvas_container_parent_class)->destroy (object);
3907 }
3908 
3909 static void
3910 finalize (GObject *object)
3911 {
3912 	NautilusCanvasContainerDetails *details;
3913 
3914 	details = NAUTILUS_CANVAS_CONTAINER (object)->details;
3915 
3916 	g_signal_handlers_disconnect_by_func (nautilus_icon_view_preferences,
3917 					      text_ellipsis_limit_changed_container_callback,
3918 					      object);
3919 	g_signal_handlers_disconnect_by_func (nautilus_desktop_preferences,
3920 					      text_ellipsis_limit_changed_container_callback,
3921 					      object);
3922 
3923 	g_hash_table_destroy (details->icon_set);
3924 	details->icon_set = NULL;
3925 
3926 	g_free (details->font);
3927 
3928 	if (details->a11y_item_action_queue != NULL) {
3929 		while (!g_queue_is_empty (details->a11y_item_action_queue)) {
3930 			g_free (g_queue_pop_head (details->a11y_item_action_queue));
3931 		}
3932 		g_queue_free (details->a11y_item_action_queue);
3933 	}
3934 	if (details->a11y_item_action_idle_handler != 0) {
3935 		g_source_remove (details->a11y_item_action_idle_handler);
3936 	}
3937 
3938 	g_free (details);
3939 
3940 	G_OBJECT_CLASS (nautilus_canvas_container_parent_class)->finalize (object);
3941 }
3942 
3943 /* GtkWidget methods.  */
3944 
3945 static gboolean
3946 clear_size_allocation_count (gpointer data)
3947 {
3948 	NautilusCanvasContainer *container;
3949 
3950 	container = NAUTILUS_CANVAS_CONTAINER (data);
3951 
3952 	container->details->size_allocation_count_id = 0;
3953 	container->details->size_allocation_count = 0;
3954 
3955 	return FALSE;
3956 }
3957 
3958 static void
3959 size_allocate (GtkWidget *widget,
3960 	       GtkAllocation *allocation)
3961 {
3962 	NautilusCanvasContainer *container;
3963 	gboolean need_layout_redone;
3964 	GtkAllocation wid_allocation;
3965 
3966 	container = NAUTILUS_CANVAS_CONTAINER (widget);
3967 
3968 	need_layout_redone = !container->details->has_been_allocated;
3969 	gtk_widget_get_allocation (widget, &wid_allocation);
3970 
3971 	if (allocation->width != wid_allocation.width) {
3972 		need_layout_redone = TRUE;
3973 	}
3974 
3975 	if (allocation->height != wid_allocation.height) {
3976 		need_layout_redone = TRUE;
3977 	}
3978 
3979 	/* Under some conditions we can end up in a loop when size allocating.
3980 	 * This happens when the icons don't fit without a scrollbar, but fits
3981 	 * when a scrollbar is added (bug #129963 for details).
3982 	 * We keep track of this looping by increasing a counter in size_allocate
3983 	 * and clearing it in a high-prio idle (the only way to detect the loop is
3984 	 * done).
3985 	 * When we've done at more than two iterations (with/without scrollbar)
3986 	 * we terminate this looping by not redoing the layout when the width
3987 	 * is wider than the current one (i.e when removing the scrollbar).
3988 	 */
3989 	if (container->details->size_allocation_count_id == 0) {
3990 		container->details->size_allocation_count_id = 
3991 			g_idle_add_full  (G_PRIORITY_HIGH,
3992 					  clear_size_allocation_count,
3993 					  container, NULL);
3994 	}
3995 	container->details->size_allocation_count++;
3996 	if (container->details->size_allocation_count > 2 &&
3997 	    allocation->width >= wid_allocation.width) {
3998 		need_layout_redone = FALSE;
3999 	}
4000 	
4001 	GTK_WIDGET_CLASS (nautilus_canvas_container_parent_class)->size_allocate (widget, allocation);
4002 
4003 	container->details->has_been_allocated = TRUE;
4004 
4005 	if (need_layout_redone) {
4006 		redo_layout (container);
4007 	}
4008 }
4009 
4010 static GtkSizeRequestMode
4011 get_request_mode (GtkWidget *widget)
4012 {
4013 	/* Don't trade size at all, since we get whatever we get anyway. */
4014 	return GTK_SIZE_REQUEST_CONSTANT_SIZE;
4015 }
4016 
4017 /* We need to implement these since the GtkScrolledWindow uses them
4018    to guess whether to show scrollbars or not, and if we don't report
4019    anything it'll tend to get it wrong causing double calls
4020    to size_allocate (at different sizes) during its size allocation. */
4021 static void
4022 get_prefered_width (GtkWidget *widget,
4023 		    gint      *minimum_size,
4024 		    gint      *natural_size)
4025 {
4026 	EelCanvasGroup *root;
4027 	double x1, x2;
4028 	int cx1, cx2;
4029 	int width;
4030 
4031 	root = eel_canvas_root (EEL_CANVAS (widget));
4032 	eel_canvas_item_get_bounds (EEL_CANVAS_ITEM (root),
4033 				    &x1, NULL, &x2, NULL);
4034 	eel_canvas_w2c (EEL_CANVAS (widget), x1, 0, &cx1, NULL);
4035 	eel_canvas_w2c (EEL_CANVAS (widget), x2, 0, &cx2, NULL);
4036 
4037 	width = cx2 - cx1;
4038 	if (natural_size) {
4039 		*natural_size = width;
4040 	}
4041 	if (minimum_size) {
4042 		*minimum_size = width;
4043 	}
4044 }
4045 
4046 static void
4047 get_prefered_height (GtkWidget *widget,
4048 		     gint      *minimum_size,
4049 		     gint      *natural_size)
4050 {
4051 	EelCanvasGroup *root;
4052 	double y1, y2;
4053 	int cy1, cy2;
4054 	int height;
4055 
4056 	root = eel_canvas_root (EEL_CANVAS (widget));
4057 	eel_canvas_item_get_bounds (EEL_CANVAS_ITEM (root),
4058 				    NULL, &y1, NULL, &y2);
4059 	eel_canvas_w2c (EEL_CANVAS (widget), 0, y1, NULL, &cy1);
4060 	eel_canvas_w2c (EEL_CANVAS (widget), 0, y2, NULL, &cy2);
4061 
4062 	height = cy2 - cy1;
4063 	if (natural_size) {
4064 		*natural_size = height;
4065 	}
4066 	if (minimum_size) {
4067 		*minimum_size = height;
4068 	}
4069 }
4070 
4071 static void
4072 realize (GtkWidget *widget)
4073 {
4074 	GtkAdjustment *vadj, *hadj;
4075 	NautilusCanvasContainer *container;
4076 
4077 	GTK_WIDGET_CLASS (nautilus_canvas_container_parent_class)->realize (widget);
4078 
4079 	container = NAUTILUS_CANVAS_CONTAINER (widget);
4080 
4081 	/* Ensure that the desktop window is native so the background
4082 	   set on it is drawn by X. */
4083 	if (container->details->is_desktop) {
4084 		gdk_x11_window_get_xid (gtk_layout_get_bin_window (GTK_LAYOUT (widget)));
4085 	}
4086 
4087 	/* Set up DnD.  */
4088 	nautilus_canvas_dnd_init (container);
4089 
4090 	hadj = gtk_scrollable_get_hadjustment (GTK_SCROLLABLE (widget));
4091 	g_signal_connect (hadj, "value_changed",
4092 			  G_CALLBACK (handle_hadjustment_changed), widget);
4093 
4094 	vadj = gtk_scrollable_get_vadjustment (GTK_SCROLLABLE (widget));
4095 	g_signal_connect (vadj, "value_changed",
4096 			  G_CALLBACK (handle_vadjustment_changed), widget);
4097 
4098 }
4099 
4100 static void
4101 unrealize (GtkWidget *widget)
4102 {
4103 	NautilusCanvasContainer *container;
4104 
4105 	container = NAUTILUS_CANVAS_CONTAINER (widget);
4106 
4107 	nautilus_canvas_dnd_fini (container);
4108 
4109 	GTK_WIDGET_CLASS (nautilus_canvas_container_parent_class)->unrealize (widget);
4110 }
4111 
4112 static void
4113 style_updated (GtkWidget *widget)
4114 {
4115 	NautilusCanvasContainer *container;
4116 
4117 	container = NAUTILUS_CANVAS_CONTAINER (widget);
4118 	container->details->use_drop_shadows = container->details->drop_shadows_requested;
4119 
4120 	/* Don't chain up to parent, if this is a desktop container,
4121 	 * because that resets the background of the window.
4122 	 */
4123 	if (!nautilus_canvas_container_get_is_desktop (container)) {
4124 		GTK_WIDGET_CLASS (nautilus_canvas_container_parent_class)->style_updated (widget);
4125 	}
4126 
4127 	if (gtk_widget_get_realized (widget)) {
4128 		invalidate_labels (container);
4129 		nautilus_canvas_container_request_update_all (container);
4130 	}
4131 }
4132 
4133 static gboolean
4134 button_press_event (GtkWidget *widget,
4135 		    GdkEventButton *event)
4136 {
4137 	NautilusCanvasContainer *container;
4138 	gboolean selection_changed;
4139 	gboolean return_value;
4140 	gboolean clicked_on_icon;
4141 
4142 	container = NAUTILUS_CANVAS_CONTAINER (widget);
4143         container->details->button_down_time = event->time;
4144 	
4145         /* Forget about the old keyboard selection now that we've started mousing. */
4146         clear_keyboard_focus (container);
4147 	clear_keyboard_rubberband_start (container);
4148 
4149 	if (event->type == GDK_2BUTTON_PRESS || event->type == GDK_3BUTTON_PRESS) {
4150 		/* We use our own double-click detection. */
4151 		return TRUE;
4152 	}
4153 
4154 	/* Invoke the canvas event handler and see if an item picks up the event. */
4155 	clicked_on_icon = GTK_WIDGET_CLASS (nautilus_canvas_container_parent_class)->button_press_event (widget, event);
4156 	
4157 	/* Move focus to canvas container, unless we're still renaming (to avoid exiting
4158 	 * renaming mode)
4159 	 */
4160   	if (!gtk_widget_has_focus (widget) && !(is_renaming (container) || is_renaming_pending (container))) {
4161     		gtk_widget_grab_focus (widget);
4162     	}
4163 
4164 	if (clicked_on_icon) {
4165 		return TRUE;
4166 	}
4167 
4168 	if (event->button == DRAG_BUTTON &&
4169 	    event->type == GDK_BUTTON_PRESS) {
4170 		/* Clear the last click icon for double click */
4171 		container->details->double_click_icon[1] = container->details->double_click_icon[0];
4172 		container->details->double_click_icon[0] = NULL;
4173 	}
4174 	
4175 	/* Button 1 does rubber banding. */
4176 	if (event->button == RUBBERBAND_BUTTON) {
4177 		if (! button_event_modifies_selection (event)) {
4178 			selection_changed = unselect_all (container);
4179 			if (selection_changed) {
4180 				g_signal_emit (container,
4181 					       signals[SELECTION_CHANGED], 0);
4182 			}
4183 		}
4184 
4185 		start_rubberbanding (container, event);
4186 		return TRUE;
4187 	}
4188 
4189 	/* Prevent multi-button weirdness such as bug 6181 */
4190 	if (container->details->rubberband_info.active) {
4191 		return TRUE;
4192 	}
4193 	
4194 	/* Button 2 may be passed to the window manager. */
4195 	if (event->button == MIDDLE_BUTTON) {
4196 		selection_changed = unselect_all (container);
4197 		if (selection_changed) {
4198 			g_signal_emit (container, signals[SELECTION_CHANGED], 0);
4199 		}
4200 		g_signal_emit (widget, signals[MIDDLE_CLICK], 0, event);
4201 		return TRUE;
4202 	}
4203 
4204 	/* Button 3 does a contextual menu. */
4205 	if (event->button == CONTEXTUAL_MENU_BUTTON) {
4206 		end_renaming_mode (container, TRUE);
4207 		selection_changed = unselect_all (container);
4208 		if (selection_changed) {
4209 			g_signal_emit (container, signals[SELECTION_CHANGED], 0);
4210 		}
4211 		g_signal_emit (widget, signals[CONTEXT_CLICK_BACKGROUND], 0, event);
4212 		return TRUE;
4213 	}
4214 	
4215 	/* Otherwise, we emit a button_press message. */
4216 	g_signal_emit (widget,
4217 		       signals[BUTTON_PRESS], 0, event,
4218 		       &return_value);
4219 	return return_value;
4220 }
4221 
4222 static void
4223 nautilus_canvas_container_did_not_drag (NautilusCanvasContainer *container,
4224 					GdkEventButton *event)
4225 {
4226 	NautilusCanvasContainerDetails *details;
4227 	gboolean selection_changed;
4228 	static gint64 last_click_time = 0;
4229 	static gint click_count = 0;
4230 	gint double_click_time;
4231 	gint64 current_time;
4232 		
4233 	details = container->details;
4234 
4235 	if (details->icon_selected_on_button_down &&
4236 	    ((event->state & GDK_CONTROL_MASK) != 0 ||
4237 	     (event->state & GDK_SHIFT_MASK) == 0)) {
4238 		if (button_event_modifies_selection (event)) {
4239 			details->range_selection_base_icon = NULL;
4240 			icon_toggle_selected (container, details->drag_icon);
4241 			g_signal_emit (container,
4242 				       signals[SELECTION_CHANGED], 0);
4243 		} else {
4244 			details->range_selection_base_icon = details->drag_icon;
4245 			selection_changed = select_one_unselect_others 
4246 				(container, details->drag_icon);
4247 			
4248 			if (selection_changed) {
4249 				g_signal_emit (container,
4250 					       signals[SELECTION_CHANGED], 0);
4251 			}
4252 		}
4253 	} 
4254 	
4255 	if (details->drag_icon != NULL &&
4256 	    (details->single_click_mode ||
4257 	     event->button == MIDDLE_BUTTON)) {
4258 		/* Determine click count */
4259 		g_object_get (G_OBJECT (gtk_widget_get_settings (GTK_WIDGET (container))), 
4260 			      "gtk-double-click-time", &double_click_time,
4261 			      NULL);
4262 		current_time = g_get_monotonic_time ();
4263 		if (current_time - last_click_time < double_click_time * 1000) {
4264 			click_count++;
4265 		} else {
4266 			click_count = 0;
4267 		}
4268 		
4269 		/* Stash time for next compare */
4270 		last_click_time = current_time;
4271 
4272 		/* If single-click mode, activate the selected icons, unless modifying
4273 		 * the selection or pressing for a very long time, or double clicking.
4274 		 */
4275 
4276 		
4277 		if (click_count == 0 &&
4278 		    event->time - details->button_down_time < MAX_CLICK_TIME &&
4279 		    ! button_event_modifies_selection (event)) {