From 5583fa60c179a8f7ec818829fb5bd53cd939bdcd Mon Sep 17 00:00:00 2001
From: Benjamin Otte <otte@redhat.com>
Date: Thu, 9 Mar 2023 04:42:45 +0100
Subject: [PATCH] listitemmanager: Add gtk_list_item_manager_get_nearest_tile()

... and make the tile finding code use distance.

This also changes how gtk_list_item_manager_get_tile_at() finds the
right tile, so this is a custom commit for bisectability.

gtk_list_item_manager_get_nearest_tile() isn't used yet.
---
 gtk/gtklistitemmanager.c        | 125 ++++++++++++++++++++++++++------
 gtk/gtklistitemmanagerprivate.h |   4 +
 2 files changed, 108 insertions(+), 21 deletions(-)

diff --git a/gtk/gtklistitemmanager.c b/gtk/gtklistitemmanager.c
index b34e6aa4a7..772b17d471 100644
--- a/gtk/gtklistitemmanager.c
+++ b/gtk/gtklistitemmanager.c
@@ -247,39 +247,94 @@ gtk_list_item_manager_get_nth (GtkListItemManager *self,
   return tile;
 }
 
+/* This computes Manhattan distance */
+static int
+rectangle_distance (const cairo_rectangle_int_t *rect,
+                    int                          x,
+                    int                          y)
+{
+  int x_dist, y_dist;
+
+  if (rect->x > x)
+    x_dist = rect->x - x;
+  else if (rect->x + rect->width < x)
+    x_dist = x - (rect->x + rect->width);
+  else
+    x_dist = 0;
+
+  if (rect->y > y)
+    y_dist = rect->y - y;
+  else if (rect->y + rect->height < y)
+    y_dist = y - (rect->y + rect->height);
+  else
+    y_dist = 0;
+
+  return x_dist + y_dist;
+}
+
 static GtkListTile *
 gtk_list_tile_get_tile_at (GtkListItemManager *self,
                            GtkListTile        *tile,
                            int                 x,
-                           int                 y)
+                           int                 y,
+                           int                *distance)
 {
   GtkListTileAugment *aug;
-  GtkListTile *subtile;
-
-  aug = gtk_list_tile_get_augment (self, tile);
-  if (!gdk_rectangle_contains_point (&aug->area, x, y))
-    return NULL;
+  GtkListTile *left, *right, *result;
+  int dist, left_dist, right_dist;
 
-  subtile = gtk_rb_tree_node_get_left (tile);
-  if (subtile)
+  left = gtk_rb_tree_node_get_left (tile);
+  if (left)
     {
-      subtile = gtk_list_tile_get_tile_at (self, subtile, x, y);
-      if (subtile)
-        return subtile;
+      aug = gtk_list_tile_get_augment (self, left);
+      left_dist = rectangle_distance (&aug->area, x, y);
     }
+  else
+    left_dist = *distance;
+  right = gtk_rb_tree_node_get_right (tile);
+  if (right)
+    {
+      aug = gtk_list_tile_get_augment (self, right);
+      right_dist = rectangle_distance (&aug->area, x, y);
+    }
+  else
+    right_dist = *distance;
 
-  if (gdk_rectangle_contains_point (&tile->area, x, y))
-    return tile;
+  dist = rectangle_distance (&tile->area, x, y);
+  result = NULL;
 
-  subtile = gtk_rb_tree_node_get_right (tile);
-  if (subtile)
+  while (TRUE)
     {
-      subtile = gtk_list_tile_get_tile_at (self, subtile, x, y);
-      if (subtile)
-        return subtile;
-    }
+      if (dist < left_dist && dist < right_dist)
+        {
+          if (dist >= *distance)
+            return result;
+
+          *distance = dist;
+          return tile;
+        }
+
+      if (left_dist < right_dist)
+        {
+          if (left_dist >= *distance)
+            return result;
 
-  return NULL;
+          left = gtk_list_tile_get_tile_at (self, left, x, y, distance);
+          if (left)
+            result = left;
+          left_dist = G_MAXINT;
+        }
+      else
+        {
+          if (right_dist >= *distance)
+            return result;
+
+          right = gtk_list_tile_get_tile_at (self, right, x, y, distance);
+          if (right)
+            result = right;
+          right_dist = G_MAXINT;
+        }
+    }
 }
 
 /*
@@ -299,7 +354,35 @@ gtk_list_item_manager_get_tile_at (GtkListItemManager *self,
                                    int                 x,
                                    int                 y)
 {
-  return gtk_list_tile_get_tile_at (self, gtk_list_item_manager_get_root (self), x, y);
+  int distance = 1;
+
+  return gtk_list_tile_get_tile_at (self, gtk_list_item_manager_get_root (self), x, y, &distance);
+}
+
+/*
+ * gtk_list_item_manager_get_nearest_tile:
+ * @self: a GtkListItemManager
+ * @x: x coordinate of tile
+ * @y: y coordinate of tile
+ *
+ * Finds the tile closest to the coordinates at (x, y). If no
+ * tile occupies the coordinates (for example, if the tile is out of bounds),
+ * Manhattan distance is used to find the nearest tile.
+ *
+ * If multiple tiles have the same distance, the one closest to the start
+ * will be returned.
+ *
+ * Returns: (nullable): The tile nearest to (x, y) or NULL if there are no
+ *     tile
+ **/
+GtkListTile *
+gtk_list_item_manager_get_nearest_tile (GtkListItemManager *self,
+                                        int                 x,
+                                        int                 y)
+{
+  int distance = G_MAXINT;
+
+  return gtk_list_tile_get_tile_at (self, gtk_list_item_manager_get_root (self), x, y, &distance);
 }
 
 guint
diff --git a/gtk/gtklistitemmanagerprivate.h b/gtk/gtklistitemmanagerprivate.h
index eb10303618..7d4172aacc 100644
--- a/gtk/gtklistitemmanagerprivate.h
+++ b/gtk/gtklistitemmanagerprivate.h
@@ -78,6 +78,10 @@ gpointer                gtk_list_item_manager_get_nth           (GtkListItemMana
 GtkListTile *           gtk_list_item_manager_get_tile_at       (GtkListItemManager     *self,
                                                                  int                     x,
                                                                  int                     y);
+GtkListTile *           gtk_list_item_manager_get_nearest_tile  (GtkListItemManager     *self,
+                                                                 int                     x,
+                                                                 int                     y);
+
 
 guint                   gtk_list_tile_get_position              (GtkListItemManager     *self,
                                                                  GtkListTile            *tile);
-- 
2.30.2