[gnome-calendar/gbsneto/timeline: 4/25] range-tree: Switch to use GDateTime
- From: Georges Basile Stavracas Neto <gbsneto src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gnome-calendar/gbsneto/timeline: 4/25] range-tree: Switch to use GDateTime
- Date: Fri, 27 Mar 2020 17:34:11 +0000 (UTC)
commit e599f58a9ee97d6449fd7bb3a72f464e70795f52
Author: Georges Basile Stavracas Neto <georges stavracas gmail com>
Date: Fri Mar 20 19:51:09 2020 -0300
range-tree: Switch to use GDateTime
Using raw integers forces us to select a pre-defined
start and end ranges for the timeline. Since we want
to reuse this data structure on GcalTimeline, make it
a bit more useful.
src/views/gcal-range-tree.c | 247 ++++++++++++++++++++++++++++----------------
src/views/gcal-range-tree.h | 29 +++---
src/views/gcal-week-grid.c | 164 ++++++++++-------------------
tests/meson.build | 1 +
tests/test-range-tree.c | 155 +++++++++++++++++++++++++++
5 files changed, 388 insertions(+), 208 deletions(-)
---
diff --git a/src/views/gcal-range-tree.c b/src/views/gcal-range-tree.c
index 7bab24c5..3dbbee05 100644
--- a/src/views/gcal-range-tree.c
+++ b/src/views/gcal-range-tree.c
@@ -19,6 +19,7 @@
#define G_LOG_DOMAIN "GcalRangeTree"
#include "gcal-range-tree.h"
+#include "utils/gcal-date-time-utils.h"
/**
* SECTION:gcal-range-tree
@@ -27,13 +28,12 @@
* @stability:stable
*
* #GcalRangeTree is an augmented AVL tree implemented to be
- * able to handle ranges rather than point values. This tree
- * is used by @GcalWeekGrid to store events according to their
- * start and end minutes, and thus all the data structure was
- * optimized to handle a limited subset of values.
+ * able to handle time ranges rather than point values. This
+ * tree is used by @GcalWeekGrid to store events according to
+ * their start and end times.
*
- * In the future, we may need to extend support for broader
- * range values, and move away from guint16 in function params.
+ * By using #GDateTime to store the ranges, it supports a very
+ * long time range.
*
* # Ranges
*
@@ -46,9 +46,9 @@ typedef struct _Node
{
struct _Node *left;
struct _Node *right;
- guint16 start;
- guint16 end;
- guint16 max;
+ GDateTime *start;
+ GDateTime *end;
+ GDateTime *max;
guint16 hits;
gint64 height;
GPtrArray *data_array;
@@ -73,6 +73,10 @@ destroy_tree (Node *n)
destroy_tree (n->left);
destroy_tree (n->right);
+ gcal_clear_date_time (&n->start);
+ gcal_clear_date_time (&n->end);
+ gcal_clear_date_time (&n->max);
+
g_ptr_array_unref (n->data_array);
g_free (n);
}
@@ -95,48 +99,70 @@ balance (Node *n)
return n ? height (n->left) - height (n->right) : 0;
}
+/*
+ * Compares the ranges A [a_start, a_end] and B [b_start, b_end]. A is
+ * less rangy than B when either it starts before B, or starts at the
+ * same point but ends before B.
+ *
+ * Some examples:
+ *
+ * 1. [-----A----] = 0
+ * [-----B----]
+ *
+ * 2. [----A----] = 1
+ * [----B----]
+ *
+ * 3. [------A-----] = -1
+ * [----B----]
+ *
+ * 4. [----A----] = -1
+ * [----B----]
+ *
+ * This is *not* comparing the sizes of the ranges.
+ */
static inline gboolean
-compare_intervals (guint16 a_start,
- guint16 a_end,
- guint16 b_start,
- guint16 b_end)
+compare_intervals (GDateTime *a_start,
+ GDateTime *a_end,
+ GDateTime *b_start,
+ GDateTime *b_end)
{
- if (a_start != b_start)
- return b_start - a_start;
+ gint result = g_date_time_compare (b_start, a_start);
- if (a_end != b_end)
- return b_end - a_end;
+ if (result == 0)
+ result = g_date_time_compare (b_end, a_end);
- return 0;
+ return result;
}
static inline gboolean
-is_interval_lower (Node *n,
- guint32 start,
- guint32 end)
+is_interval_lower (Node *n,
+ GDateTime *start,
+ GDateTime *end)
{
- return start < n->start || (start == n->start && end < n->end);
+ gint a_compare = g_date_time_compare (start, n->start);
+ return a_compare < 0 || (a_compare == 0 && g_date_time_compare (end, n->end) < 0);
}
static inline gboolean
-is_interval_higher (Node *n,
- guint32 start,
- guint32 end)
+is_interval_higher (Node *n,
+ GDateTime *start,
+ GDateTime *end)
{
- return start > n->start || (start == n->start && end > n->end);
+ gint a_compare = g_date_time_compare (start, n->start);
+ return a_compare > 0 || (a_compare == 0 && g_date_time_compare (end, n->end) > 0);
}
static Node*
-node_new (guint32 start,
- guint32 end,
- gpointer data)
+node_new (GDateTime *start,
+ GDateTime *end,
+ gpointer data)
{
Node *n;
n = g_new0 (Node, 1);
- n->start = start;
- n->end = end;
- n->max = end;
+ n->start = g_date_time_ref (start);
+ n->end = g_date_time_ref (end);
+ n->max = g_date_time_ref (end);
n->height = 1;
n->hits = 1;
@@ -217,23 +243,31 @@ rebalance (Node *n)
}
static Node*
-insert (Node *n,
- guint32 start,
- guint32 end,
- gpointer data)
+insert (Node *n,
+ GDateTime *start,
+ GDateTime *end,
+ gpointer data)
{
+ gint result;
+
if (!n)
return node_new (start, end, data);
- if (compare_intervals (n->start, n->end, start, end) < 0)
+ result = compare_intervals (n->start, n->end, start, end);
+
+ if (result < 0)
n->left = insert (n->left, start, end, data);
- else if (compare_intervals (n->start, n->end, start, end) > 0)
+ else if (result > 0)
n->right = insert (n->right, start, end, data);
else
return hit_node (n, data);
/* Update the current node's maximum subrange value */
- n->max = MAX (n->max, end);
+ if (!n->max || g_date_time_compare (end, n->max) > 0)
+ {
+ gcal_clear_date_time (&n->max);
+ n->max = g_date_time_ref (end);
+ }
return rebalance (n);
}
@@ -289,23 +323,24 @@ delete_node (Node *n,
}
static Node*
-remove (Node *n,
- guint32 start,
- guint32 end,
- gpointer data)
+remove_node (Node *n,
+ GDateTime *start,
+ GDateTime *end,
+ gpointer data)
{
if (!n)
return NULL;
if (is_interval_lower (n, start, end))
- n->left = remove (n->left, start, end, data);
+ n->left = remove_node (n->left, start, end, data);
else if (is_interval_higher (n, start, end))
- n->right = remove (n->right, start, end, data);
+ n->right = remove_node (n->right, start, end, data);
else
return delete_node (n, data);
return rebalance (n);
}
+
/* Traverse */
static inline gboolean
run_traverse_func (Node *n,
@@ -330,97 +365,110 @@ traverse (Node *n,
gpointer user_data)
{
if (!n)
- return FALSE;
+ return GCAL_TRAVERSE_CONTINUE;
if (type == G_PRE_ORDER)
{
if (run_traverse_func (n, func, user_data))
- return TRUE;
+ return GCAL_TRAVERSE_STOP;
}
if (traverse (n->left, type, func, user_data))
- return TRUE;
+ return GCAL_TRAVERSE_STOP;
if (type == G_IN_ORDER)
{
if (run_traverse_func (n, func, user_data))
- return TRUE;
+ return GCAL_TRAVERSE_STOP;
}
if (traverse (n->right, type, func, user_data))
- return TRUE;
+ return GCAL_TRAVERSE_STOP;
if (type == G_POST_ORDER)
{
if (run_traverse_func (n, func, user_data))
- return TRUE;
+ return GCAL_TRAVERSE_STOP;
}
- return FALSE;
+ return GCAL_TRAVERSE_CONTINUE;
}
/* Internal traverse functions */
static inline gboolean
-gather_data_at_range (guint16 start,
- guint16 end,
- gpointer data,
- gpointer user_data)
+gather_all_data (GDateTime *start,
+ GDateTime *end,
+ gpointer data,
+ gpointer user_data)
+{
+ GPtrArray *array = user_data;
+
+ g_ptr_array_add (array, data);
+
+ return FALSE;
+}
+
+static inline gboolean
+gather_data_at_range (GDateTime *start,
+ GDateTime *end,
+ gpointer data,
+ gpointer user_data)
{
struct {
- guint16 start, end;
+ GDateTime *start, *end;
GPtrArray **array;
} *range = user_data;
/* Since we're traversing in order, stop here */
if (compare_intervals (range->start, range->end, start, end) > 0 &&
- start >= range->end)
+ g_date_time_compare (start, range->end) >= 0)
{
- return TRUE;
+ return GCAL_TRAVERSE_STOP;
}
/*
* If the current range doesn't overlap but we're before the desired range, keep
* traversing the tree
*/
- if (range->start >= end)
- return FALSE;
+ if (g_date_time_compare (range->start, end) >= 0)
+ return GCAL_TRAVERSE_CONTINUE;
if (!*range->array)
*range->array = g_ptr_array_new ();
g_ptr_array_add (*range->array, data);
- return FALSE;
+ return GCAL_TRAVERSE_CONTINUE;
}
static inline gboolean
-count_entries_at_range (guint16 start,
- guint16 end,
- gpointer data,
- gpointer user_data)
+count_entries_at_range (GDateTime *start,
+ GDateTime *end,
+ gpointer data,
+ gpointer user_data)
{
struct {
- guint16 start, end;
+ GDateTime *start, *end;
guint64 counter;
} *range = user_data;
/* Since we're traversing in order, stop here */
if (compare_intervals (range->start, range->end, start, end) > 0 &&
- start >= range->end)
+ g_date_time_compare (start, range->end) >= 0)
{
- return TRUE;
+ return GCAL_TRAVERSE_STOP;
}
/*
* If the current range doesn't overlap but we're before the desired range, keep
* traversing the tree
*/
- if (range->start >= end)
- return FALSE;
+ if (g_date_time_compare (range->start, end) >= 0)
+ return GCAL_TRAVERSE_CONTINUE;
range->counter++;
- return FALSE;
+ return GCAL_TRAVERSE_CONTINUE;
}
static void
gcal_range_tree_free (GcalRangeTree *self)
@@ -524,12 +572,13 @@ gcal_range_tree_unref (GcalRangeTree *self)
*/
void
gcal_range_tree_add_range (GcalRangeTree *self,
- guint16 start,
- guint16 end,
+ GDateTime *start,
+ GDateTime *end,
gpointer data)
{
g_return_if_fail (self);
- g_return_if_fail (end >= start);
+ g_return_if_fail (end && start);
+ g_return_if_fail (g_date_time_compare (end, start) >= 0);
self->root = insert (self->root, start, end, data);
}
@@ -545,14 +594,15 @@ gcal_range_tree_add_range (GcalRangeTree *self,
*/
void
gcal_range_tree_remove_range (GcalRangeTree *self,
- guint16 start,
- guint16 end,
+ GDateTime *start,
+ GDateTime *end,
gpointer data)
{
g_return_if_fail (self);
- g_return_if_fail (end >= start);
+ g_return_if_fail (end && start);
+ g_return_if_fail (g_date_time_compare (end, start) >= 0);
- self->root = remove (self->root, start, end, data);
+ self->root = remove_node (self->root, start, end, data);
}
/**
@@ -575,6 +625,27 @@ gcal_range_tree_traverse (GcalRangeTree *self,
traverse (self->root, type, func, user_data);
}
+/**
+ * gcal_range_tree_get_all_data:
+ * @self: a #GcalRangeTree
+ *
+ * Retrieves all the data currently stored in @self.
+ *
+ * Returns: (transfer full): a #GPtrArray with the stored elements
+ */
+GPtrArray*
+gcal_range_tree_get_all_data (GcalRangeTree *self)
+{
+ g_autoptr (GPtrArray) data = NULL;
+
+ g_return_val_if_fail (self, NULL);
+
+ data = g_ptr_array_new ();
+
+ gcal_range_tree_traverse (self, G_IN_ORDER, gather_all_data, data);
+
+ return g_steal_pointer (&data);
+}
/**
* gcal_range_tree_get_data_at_range:
@@ -589,18 +660,19 @@ gcal_range_tree_traverse (GcalRangeTree *self,
*/
GPtrArray*
gcal_range_tree_get_data_at_range (GcalRangeTree *self,
- guint16 start,
- guint16 end)
+ GDateTime *start,
+ GDateTime *end)
{
GPtrArray *data;
struct {
- guint16 start, end;
+ GDateTime *start, *end;
GPtrArray **array;
} range = { start, end, &data };
g_return_val_if_fail (self, NULL);
- g_return_val_if_fail (end >= start, NULL);
+ g_return_val_if_fail (end && start, NULL);
+ g_return_val_if_fail (g_date_time_compare (end, start) >= 0, NULL);
data = NULL;
@@ -622,16 +694,17 @@ gcal_range_tree_get_data_at_range (GcalRangeTree *self,
*/
guint64
gcal_range_tree_count_entries_at_range (GcalRangeTree *self,
- guint16 start,
- guint16 end)
+ GDateTime *start,
+ GDateTime *end)
{
struct {
- guint16 start, end;
+ GDateTime *start, *end;
guint64 counter;
} range = { start, end, 0 };
g_return_val_if_fail (self, 0);
- g_return_val_if_fail (end >= start, 0);
+ g_return_val_if_fail (end && start, 0);
+ g_return_val_if_fail (g_date_time_compare (end, start) >= 0, 0);
gcal_range_tree_traverse (self, G_IN_ORDER, count_entries_at_range, &range);
diff --git a/src/views/gcal-range-tree.h b/src/views/gcal-range-tree.h
index a9b2d473..4bd46af2 100644
--- a/src/views/gcal-range-tree.h
+++ b/src/views/gcal-range-tree.h
@@ -29,8 +29,8 @@ typedef struct _GcalRangeTree GcalRangeTree;
/**
* GcalRangeTraverseFunc:
- * @start: start of range of the entry
- * @end: end of range of the entry
+ * @start: #GDateTime with the start of range of the entry
+ * @end: #GDateTime with the end of range of the entry
* @data: (nullable): the data of the entry
* @user_data: (closure): user data passed to the function
*
@@ -38,11 +38,14 @@ typedef struct _GcalRangeTree GcalRangeTree;
*
* Returns: %TRUE to stop traversing, %FALSE to continue traversing
*/
-typedef gboolean (*GcalRangeTraverseFunc) (guint16 start,
- guint16 end,
+typedef gboolean (*GcalRangeTraverseFunc) (GDateTime *start,
+ GDateTime *end,
gpointer data,
gpointer user_data);
+#define GCAL_TRAVERSE_CONTINUE FALSE;
+#define GCAL_TRAVERSE_STOP TRUE;
+
GType gcal_range_tree_get_type (void) G_GNUC_CONST;
GcalRangeTree* gcal_range_tree_new (void);
@@ -54,13 +57,13 @@ GcalRangeTree* gcal_range_tree_ref (GcalRangeTree
void gcal_range_tree_unref (GcalRangeTree *self);
void gcal_range_tree_add_range (GcalRangeTree *self,
- guint16 start,
- guint16 end,
+ GDateTime *start,
+ GDateTime *end,
gpointer data);
void gcal_range_tree_remove_range (GcalRangeTree *self,
- guint16 start,
- guint16 end,
+ GDateTime *start,
+ GDateTime *end,
gpointer data);
void gcal_range_tree_traverse (GcalRangeTree *self,
@@ -68,13 +71,15 @@ void gcal_range_tree_traverse (GcalRangeTree
GcalRangeTraverseFunc func,
gpointer user_data);
+GPtrArray* gcal_range_tree_get_all_data (GcalRangeTree *self);
+
GPtrArray* gcal_range_tree_get_data_at_range (GcalRangeTree *self,
- guint16 start,
- guint16 end);
+ GDateTime *start,
+ GDateTime *end);
guint64 gcal_range_tree_count_entries_at_range (GcalRangeTree *self,
- guint16 start,
- guint16 end);
+ GDateTime *start,
+ GDateTime *end);
G_DEFINE_AUTOPTR_CLEANUP_FUNC (GcalRangeTree, gcal_range_tree_unref)
diff --git a/src/views/gcal-week-grid.c b/src/views/gcal-week-grid.c
index e656dc4f..5e2b7ab2 100644
--- a/src/views/gcal-week-grid.c
+++ b/src/views/gcal-week-grid.c
@@ -43,8 +43,7 @@ static const double dashed [] =
typedef struct
{
GtkWidget *widget;
- guint16 start;
- guint16 end;
+ GcalEvent *event;
} ChildData;
struct _GcalWeekGrid
@@ -83,15 +82,13 @@ static guint signals[LAST_SIGNAL] = { 0, };
/* ChildData methods */
static ChildData*
child_data_new (GtkWidget *widget,
- guint16 start,
- guint16 end)
+ GcalEvent *event)
{
ChildData *data;
data = g_new (ChildData, 1);
data->widget = widget;
- data->start = start;
- data->end = end;
+ data->event = g_object_ref (event);
return data;
}
@@ -121,65 +118,6 @@ destroy_event_widget (GcalWeekGrid *self,
}
/* Auxiliary methods */
-static void
-get_event_range (GcalWeekGrid *self,
- GcalEvent *event,
- guint16 *start,
- guint16 *end)
-{
- GDateTime *week_start;
- GTimeSpan diff;
- gboolean week_start_dst;
-
- if (!self->active_date)
- return;
-
- week_start = gcal_date_time_get_start_of_week (self->active_date);
- week_start_dst = g_date_time_is_daylight_savings (week_start);
-
- if (start)
- {
- GDateTime *event_start;
- gboolean event_start_dst;
-
- event_start = g_date_time_to_local (gcal_event_get_date_start (event));
- event_start_dst = g_date_time_is_daylight_savings (event_start);
-
- diff = g_date_time_difference (event_start, week_start);
-
- *start = CLAMP (diff / G_TIME_SPAN_MINUTE, 0, MAX_MINUTES);
- *start += 60 * (event_start_dst - week_start_dst);
-
- g_clear_pointer (&event_start, g_date_time_unref);
- }
-
- if (end)
- {
- g_autoptr (GDateTime) inclusive_end_date = NULL;
- g_autoptr (GDateTime) event_end = NULL;
- gboolean event_end_dst;
-
- inclusive_end_date = g_date_time_add_seconds (gcal_event_get_date_end (event), -1);
- event_end = g_date_time_to_local (inclusive_end_date);
- event_end_dst = g_date_time_is_daylight_savings (event_end);
-
- diff = g_date_time_difference (event_end, week_start);
-
- *end = CLAMP (diff / G_TIME_SPAN_MINUTE, 0, MAX_MINUTES);
- *end += 60 * (event_end_dst - week_start_dst);
-
- /*
- * XXX: it may happen that the event has the same start and end
- * dates. For this case, just enforce that the event is at least
- * 1 minute long.
- */
- if (start && *start == *end)
- *end = *end + 1;
- }
-
- g_clear_pointer (&week_start, g_date_time_unref);
-}
-
static inline gint
uint16_compare (gconstpointer a,
gconstpointer b)
@@ -189,8 +127,8 @@ uint16_compare (gconstpointer a,
static inline guint
get_event_index (GcalRangeTree *tree,
- guint16 start,
- guint16 end)
+ GDateTime *start,
+ GDateTime *end)
{
g_autoptr (GPtrArray) array;
gint idx, i;
@@ -216,26 +154,29 @@ get_event_index (GcalRangeTree *tree,
static guint
count_overlaps_at_range (GcalRangeTree *self,
- guint16 start,
- guint16 end)
+ GDateTime *start,
+ GDateTime *end)
{
- guint64 i, counter;
+ guint64 counter;
g_return_val_if_fail (self, 0);
- g_return_val_if_fail (end >= start, 0);
counter = 0;
- for (i = start; i < end; i++)
+ while (g_date_time_compare (start, end) < 0)
{
+ g_autoptr (GDateTime) start_plus_one = NULL;
guint n_events;
- n_events = gcal_range_tree_count_entries_at_range (self, i, i + 1);
+ start_plus_one = g_date_time_add_minutes (start, 1);
+ n_events = gcal_range_tree_count_entries_at_range (self, start, start_plus_one);
if (n_events == 0)
break;
counter = MAX (counter, n_events);
+
+ start = g_steal_pointer (&start_plus_one);
}
return counter;
@@ -243,25 +184,29 @@ count_overlaps_at_range (GcalRangeTree *self,
static guint
count_overlaps_of_event (GcalRangeTree *self,
- guint16 day_start,
- guint16 day_end,
- guint16 event_start,
- guint16 event_end)
+ GDateTime *day_start,
+ GDateTime *day_end,
+ GDateTime *event_start,
+ GDateTime *event_end)
{
- guint64 i, counter;
+ guint64 counter;
counter = count_overlaps_at_range (self, event_start, day_end);
- for (i = event_start; i > day_start; i--)
+ while (g_date_time_compare (event_start, day_start) > 0)
{
+ g_autoptr (GDateTime) start_minus_one = NULL;
guint n_events;
- n_events = gcal_range_tree_count_entries_at_range (self, i - 1, i);
+ start_minus_one = g_date_time_add_minutes (event_start, -1);
+ n_events = gcal_range_tree_count_entries_at_range (self, start_minus_one, event_start);
if (n_events == 0)
break;
counter = MAX (counter, n_events);
+
+ event_start = g_date_time_add_minutes (event_start, 1);
}
return counter;
@@ -303,14 +248,13 @@ gcal_week_grid_forall (GtkContainer *container,
guint i;
self = GCAL_WEEK_GRID (container);
- widgets_data = gcal_range_tree_get_data_at_range (self->events, 0, MAX_MINUTES);
+ widgets_data = gcal_range_tree_get_all_data (self->events);
- for (i = 0; widgets_data && i < widgets_data->len; i++)
+ for (i = 0; i < widgets_data->len; i++)
{
ChildData *data;
data = g_ptr_array_index (widgets_data, i);
-
callback (data->widget, callback_data);
}
@@ -607,6 +551,7 @@ gcal_week_grid_size_allocate (GtkWidget *widget,
GtkAllocation *allocation)
{
GcalWeekGrid *self = GCAL_WEEK_GRID (widget);
+ g_autoptr (GDateTime) week_start = NULL;
GcalRangeTree *overlaps;
gboolean ltr;
gdouble minutes_height;
@@ -636,19 +581,21 @@ gcal_week_grid_size_allocate (GtkWidget *widget,
/* Temporary range tree to hold positioned events' indexes */
overlaps = gcal_range_tree_new ();
+ week_start = gcal_date_time_get_start_of_week (self->active_date);
+
/*
* Iterate through weekdays; we don't have to worry about events that
* jump between days because they're already handled by GcalWeekHeader.
*/
for (i = 0; i < 7; i++)
{
+ g_autoptr (GDateTime) day_start = NULL;
+ g_autoptr (GDateTime) day_end = NULL;
GPtrArray *widgets_data;
- guint16 day_start;
- guint16 day_end;
guint j;
- day_start = i * MINUTES_PER_DAY;
- day_end = day_start + MINUTES_PER_DAY;
+ day_start = g_date_time_add_days (week_start, i);
+ day_end = g_date_time_add_days (day_start, 1);
widgets_data = gcal_range_tree_get_data_at_range (self->events, day_start, day_end);
for (j = 0; widgets_data && j < widgets_data->len; j++)
@@ -656,9 +603,12 @@ gcal_week_grid_size_allocate (GtkWidget *widget,
GtkStyleContext *context;
GtkAllocation child_allocation;
GtkWidget *event_widget;
+ GDateTime *event_start;
+ GDateTime *event_end;
ChildData *data;
GtkBorder margin;
guint64 events_at_range;
+ gint event_minutes;
gint natural_height;
gint widget_index;
gint offset;
@@ -667,13 +617,15 @@ gcal_week_grid_size_allocate (GtkWidget *widget,
data = g_ptr_array_index (widgets_data, j);
event_widget = data->widget;
+ event_start = gcal_event_get_date_start (data->event);
+ event_end = gcal_event_get_date_end (data->event);
context = gtk_widget_get_style_context (event_widget);
/* The total number of events available in this range */
- events_at_range = count_overlaps_of_event (self->events, day_start, day_end, data->start,
data->end);
+ events_at_range = count_overlaps_of_event (self->events, day_start, day_end, event_start,
event_end);
/* The real horizontal position of this event */
- widget_index = get_event_index (overlaps, data->start, data->end);
+ widget_index = get_event_index (overlaps, event_start, event_end);
/* Gtk complains about that */
gtk_widget_get_preferred_height (event_widget, NULL, &natural_height);
@@ -683,10 +635,11 @@ gcal_week_grid_size_allocate (GtkWidget *widget,
gtk_style_context_get_state (context),
&margin);
+ event_minutes = g_date_time_difference (event_end, event_start) / G_TIME_SPAN_MINUTE;
width = column_width / events_at_range - margin.left - margin.right;
- height = (data->end - data->start) * minutes_height - margin.top - margin.bottom;
+ height = event_minutes * minutes_height - margin.top - margin.bottom;
offset = (width + margin.left + margin.right) * widget_index;
- y = (data->start % MINUTES_PER_DAY) * minutes_height + margin.top;
+ y = (g_date_time_get_hour (event_start) * 60 + g_date_time_get_minute (event_start)) *
minutes_height + margin.top;
if (ltr)
x = column_width * i + offset + allocation->x + margin.left + 1;
@@ -711,8 +664,8 @@ gcal_week_grid_size_allocate (GtkWidget *widget,
* know how many events are already positioned in the current column.
*/
gcal_range_tree_add_range (overlaps,
- data->start,
- data->end,
+ event_start,
+ event_end,
GUINT_TO_POINTER (widget_index));
}
@@ -1149,13 +1102,9 @@ gcal_week_grid_add_event (GcalWeekGrid *self,
GcalEvent *event)
{
GtkWidget *widget;
- guint16 start, end;
g_return_if_fail (GCAL_IS_WEEK_GRID (self));
- end = 0;
- start = 0;
-
g_object_ref (event);
widget = g_object_new (GCAL_TYPE_EVENT_WIDGET,
@@ -1164,12 +1113,10 @@ gcal_week_grid_add_event (GcalWeekGrid *self,
"orientation", GTK_ORIENTATION_VERTICAL,
NULL);
- get_event_range (self, event, &start, &end);
-
gcal_range_tree_add_range (self->events,
- start,
- end,
- child_data_new (widget, start, end));
+ gcal_event_get_date_start (event),
+ gcal_event_get_date_end (event),
+ child_data_new (widget, event));
setup_event_widget (self, widget);
gtk_widget_show (widget);
@@ -1186,14 +1133,12 @@ gcal_week_grid_remove_event (GcalWeekGrid *self,
g_return_if_fail (GCAL_IS_WEEK_GRID (self));
- widgets = gcal_range_tree_get_data_at_range (self->events, 0, MAX_MINUTES);
+ widgets = gcal_range_tree_get_all_data (self->events);
for (i = 0; widgets && i < widgets->len; i++)
{
ChildData *data;
GcalEvent *event;
- guint16 event_start;
- guint16 event_end;
data = g_ptr_array_index (widgets, i);
event = gcal_event_widget_get_event (GCAL_EVENT_WIDGET (data->widget));
@@ -1201,9 +1146,10 @@ gcal_week_grid_remove_event (GcalWeekGrid *self,
if (g_strcmp0 (gcal_event_get_uid (event), uid) != 0)
continue;
- get_event_range (self, event, &event_start, &event_end);
-
- gcal_range_tree_remove_range (self->events, data->start, data->end, data);
+ gcal_range_tree_remove_range (self->events,
+ gcal_event_get_date_start (event),
+ gcal_event_get_date_end (event),
+ data);
destroy_event_widget (self, data->widget);
gtk_widget_queue_allocate (GTK_WIDGET (self));
g_object_unref (event);
@@ -1227,7 +1173,7 @@ gcal_week_grid_get_children_by_uuid (GcalWeekGrid *self,
events = NULL;
result = NULL;
- widgets = gcal_range_tree_get_data_at_range (self->events, 0, MAX_MINUTES);
+ widgets = gcal_range_tree_get_all_data (self->events);
for (i = 0; widgets && i < widgets->len; i++)
{
diff --git a/tests/meson.build b/tests/meson.build
index c6510f1e..23685b36 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -35,6 +35,7 @@ tests = [
'server',
'discoverer',
'event',
+ 'range-tree',
]
foreach test : tests
diff --git a/tests/test-range-tree.c b/tests/test-range-tree.c
new file mode 100644
index 00000000..ed9974bb
--- /dev/null
+++ b/tests/test-range-tree.c
@@ -0,0 +1,155 @@
+/* test-range-tree.c
+ *
+ * Copyright 2020 Georges Basile Stavracas Neto <georges stavracas gmail com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include "gcal-range-tree.h"
+
+/*********************************************************************************************************************/
+
+static void
+range_tree_new (void)
+{
+ g_autoptr (GcalRangeTree) range_tree = NULL;
+
+ range_tree = gcal_range_tree_new ();
+ g_assert_nonnull (range_tree);
+}
+
+/*********************************************************************************************************************/
+
+static void
+range_tree_insert (void)
+{
+ g_autoptr (GcalRangeTree) range_tree = NULL;
+ g_autoptr (GDateTime) start = NULL;
+ g_autoptr (GDateTime) end = NULL;
+
+ range_tree = gcal_range_tree_new ();
+ g_assert_nonnull (range_tree);
+
+ start = g_date_time_new_local (2020, 3, 17, 9, 30, 0);
+ end = g_date_time_add_hours (start, 1);
+
+ gcal_range_tree_add_range (range_tree, start, end, (gpointer) 0xdeadbeef);
+ g_assert_cmpint (gcal_range_tree_count_entries_at_range (range_tree, start, end), ==, 1);
+
+ gcal_range_tree_add_range (range_tree, start, end, (gpointer) 0x8badf00d);
+ g_assert_cmpint (gcal_range_tree_count_entries_at_range (range_tree, start, end), ==, 2);
+
+ gcal_range_tree_add_range (range_tree, start, end, (gpointer) 0x0badcafe);
+ g_assert_cmpint (gcal_range_tree_count_entries_at_range (range_tree, start, end), ==, 3);
+}
+
+/*********************************************************************************************************************/
+
+
+static struct {
+ const gchar *start;
+ const gchar *end;
+} ranges[] = {
+ { "2020-03-05T00:00:00", "2020-03-10T00:00:00" },
+ { "2020-03-05T00:00:00", "2020-03-10T00:00:00" },
+ { "2020-03-18T00:00:00", "2020-03-20T00:00:00" },
+ { "2020-03-05T00:00:00", "2020-03-20T00:00:00" },
+ { "2020-03-05T00:00:00", "2020-03-28T00:00:00" },
+ { "2020-03-12T00:00:00", "2020-03-20T00:00:00" },
+ { "2020-03-22T00:00:00", "2020-03-28T00:00:00" },
+};
+
+static gboolean
+traverse_func (GDateTime *start,
+ GDateTime *end,
+ gpointer data,
+ gpointer user_data)
+{
+ g_assert_cmpint (GPOINTER_TO_INT (data), >=, 0);
+ g_assert_cmpint (GPOINTER_TO_INT (data), <, G_N_ELEMENTS (ranges));
+ return GCAL_TRAVERSE_CONTINUE;
+}
+
+static void
+range_tree_traverse (void)
+{
+ g_autoptr (GcalRangeTree) range_tree = NULL;
+ g_autoptr (GTimeZone) utc = NULL;
+ gint i;
+
+ range_tree = gcal_range_tree_new ();
+ g_assert_nonnull (range_tree);
+
+ utc = g_time_zone_new_utc ();
+ for (i = 0; i < G_N_ELEMENTS (ranges); i++)
+ {
+ g_autoptr (GDateTime) start = NULL;
+ g_autoptr (GDateTime) end = NULL;
+
+ start = g_date_time_new_from_iso8601 (ranges[i].start, utc);
+ end = g_date_time_new_from_iso8601 (ranges[i].end, utc);
+
+ gcal_range_tree_add_range (range_tree, start, end, GINT_TO_POINTER (i));
+ }
+
+ gcal_range_tree_traverse (range_tree, G_PRE_ORDER, traverse_func, NULL);
+ gcal_range_tree_traverse (range_tree, G_IN_ORDER, traverse_func, NULL);
+ gcal_range_tree_traverse (range_tree, G_POST_ORDER, traverse_func, NULL);
+}
+
+/*********************************************************************************************************************/
+
+static void
+range_tree_smaller_range (void)
+{
+ g_autoptr (GcalRangeTree) range_tree = NULL;
+ g_autoptr (GDateTime) range_start = NULL;
+ g_autoptr (GDateTime) range_end = NULL;
+ g_autoptr (GDateTime) start = NULL;
+ g_autoptr (GDateTime) end = NULL;
+
+ range_tree = gcal_range_tree_new ();
+ g_assert_nonnull (range_tree);
+
+ start = g_date_time_new_local (2020, 3, 17, 9, 30, 0);
+ end = g_date_time_add_hours (start, 1);
+
+ gcal_range_tree_add_range (range_tree, start, end, (gpointer) 0xdeadbeef);
+ g_assert_cmpint (gcal_range_tree_count_entries_at_range (range_tree, start, end), ==, 1);
+
+ range_start = g_date_time_new_local (2020, 3, 20, 9, 30, 0);
+ range_end = g_date_time_add_hours (range_start, 1);
+
+ g_assert_cmpint (gcal_range_tree_count_entries_at_range (range_tree, range_start, range_end), ==, 0);
+}
+
+/*********************************************************************************************************************/
+
+gint
+main (gint argc,
+ gchar *argv[])
+{
+ g_setenv ("TZ", "UTC", TRUE);
+
+ g_test_init (&argc, &argv, NULL);
+
+ g_test_add_func ("/range-tree/new", range_tree_new);
+ g_test_add_func ("/range-tree/insert", range_tree_insert);
+ g_test_add_func ("/range-tree/traverse", range_tree_traverse);
+ g_test_add_func ("/range-tree/smaller-range", range_tree_smaller_range);
+
+ return g_test_run ();
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
