1 files changed, 309 insertions, 0 deletions
diff --git a/calendar/gui/layout.c b/calendar/gui/layout.c
new file mode 100644
index 0000000000..c8dfde6bdb
--- /dev/null
+++ b/calendar/gui/layout.c
@@ -0,0 +1,309 @@
+/* Evolution calendar - Event layout engine
+ *
+ * Copyright (C) 2000 Helix Code, Inc.
+ *
+ * Authors: Miguel de Icaza <miguel@helixcode.com>
+ *          Federico Mena-Quintero <federico@helixcode.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 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#include <config.h>
+#include <stdlib.h>
+#include "layout.h"
+
+
+
+/* This structure is used to pass around layout information among the internal
+ * layout functions.
+ */
+struct layout_info {
+	GList *events;			/* List of events from client */
+	int num_events;			/* The number of events (length of the list) */
+	LayoutQueryTimeFunc func;	/* Function to convert a list item to a start/end time pair */
+	int num_rows;			/* Size of the time partition */
+	time_t *partition;		/* The time partition containing start and end time values */
+	int *array;			/* Working array of free and allocated time slots */
+	int *allocations;		/* Returned array of slot allocations */
+	int *slots;			/* Returned array of slots used */
+	int num_slots;			/* Number of slots used */
+};
+
+
+
+/* This defines the maximum number of events to overlap per row.  More than that
+ * number of events will not be displayed.  This is not ideal, so sue me.
+ */
+#define MAX_EVENTS_PER_ROW 32
+
+
+/* Compares two time_t values, used for qsort() */
+static int
+compare_time_t (const void *a, const void *b)
+{
+	time_t ta, tb;
+
+	ta = *((time_t *) a);
+	tb = *((time_t *) b);
+
+	if (ta < tb)
+		return -1;
+	else if (ta > tb)
+		return 1;
+	else
+		return 0;
+}
+
+/* Builds a partition of the time range occupied by the events in the list.  It returns an array
+ * with the times that define the partition and the number of items in the partition.
+ */
+static void
+build_partition (struct layout_info *li)
+{
+	time_t *rows, *p, *q;
+	GList *list;
+	int i, unique_vals;
+
+	/* This is the maximum number of rows we would need */
+
+	li->num_rows = li->num_events * 2;
+
+	/* Fill the rows with the times */
+
+	rows = g_new (time_t, li->num_rows);
+
+	for (list = li->events, p = rows; list; list = list->next) {
+		(* li->func) (list, &p[0], &p[1]);
+		p += 2;
+	}
+
+	/* Do a sort | uniq on the array */
+
+	qsort (rows, li->num_rows, sizeof (time_t), compare_time_t);
+
+	p = rows;
+	q = rows + 1;
+	unique_vals = 1;
+
+	for (i = 1; i < li->num_rows; i++, q++)
+		if (*q != *p) {
+			unique_vals++;
+			p++;
+			*p = *q;
+		}
+
+	/* Return the number of unique values in the partition and the partition array itself */
+
+	li->num_rows = unique_vals;
+	li->partition = rows;
+}
+
+/* Returns the index of the element in the partition that corresponds to the specified time */
+static int
+find_index (struct layout_info *li, time_t t)
+{
+	int i;
+
+	for (i = 0; ; i++)
+		if (li->partition[i] == t)
+			return i;
+
+	g_assert_not_reached ();
+}
+
+#define xy(li, x, y) li->array[(y * MAX_EVENTS_PER_ROW) + (x)]
+
+/* Checks that all the cells in the slot array at the specified slot column are free to use by an
+ * event that has the specified range.
+ */
+static int
+range_is_empty (struct layout_info *li, int slot, time_t start, time_t end)
+{
+	int i;
+
+	for (i = find_index (li, start); li->partition[i] < end; i++)
+		if (xy (li, slot, i) != -1)
+			return FALSE;
+
+	return TRUE;
+}
+
+/* Allocates a time in the slot array for the specified event's index */
+static void
+range_allocate (struct layout_info *li, int slot, time_t start, time_t end, int ev_num)
+{
+	int i;
+
+	for (i = find_index (li, start); li->partition[i] < end; i++)
+		xy (li, slot, i) = ev_num;
+}
+
+/* Performs the initial allocation of slots for events.  Each event gets one column; they will be
+ * expanded in a later stage.  Returns the number of columns used.
+ */
+static void
+initial_allocate (struct layout_info *li)
+{
+	GList *events;
+	int i;
+	int slot;
+	int num_slots;
+	time_t start, end;
+
+	num_slots = 0;
+
+	for (i = 0, events = li->events; events; events = events->next, i++) {
+		(* li->func) (events, &start, &end);
+
+		/* Start with no allocation, no columns */
+
+		li->allocations[i] = -1;
+		li->slots[i] = 0;
+
+		/* Find a free column for the event */
+
+		for (slot = 0; slot < MAX_EVENTS_PER_ROW; slot++)
+			if (range_is_empty (li, slot, start, end)) {
+				range_allocate (li, slot, start, end, i);
+
+				li->allocations[i] = slot;
+				li->slots[i] = 1;
+
+				if ((slot + 1) > num_slots)
+					num_slots = slot + 1;
+
+				break;
+			}
+	}
+
+	li->num_slots = num_slots;
+}
+
+/* Returns the maximum number of columns that an event can expanded by in the slot array */
+static int
+columns_to_expand (struct layout_info *li, int ev_num, time_t start, time_t end)
+{
+	int cols;
+	int slot;
+	int i_start;
+	int i;
+
+	cols = 0;
+
+	i_start = find_index (li, start);
+
+	for (slot = li->allocations[ev_num] + 1; slot < li->num_slots; slot++) {
+		for (i = i_start; li->partition[i] < end; i++)
+			if (xy (li, slot, i) != -1)
+				return cols;
+
+		cols++;
+	}
+
+	return cols;
+}
+
+/* Expands an event by the specified number of columns */
+static void
+do_expansion (struct layout_info *li, int ev_num, time_t start, time_t end, int num_cols)
+{
+	int i, j;
+	int slot;
+
+	for (i = find_index (li, start); li->partition[i] < end; i++) {
+		slot = li->allocations[ev_num] + 1;
+
+		for (j = 0; j < num_cols; j++)
+			xy (li, slot + j, i) = ev_num;
+	}
+}
+
+/* Expands the events in the slot array to occupy as many columns as possible.  This is the second
+ * pass of the layout algorithm.
+ */
+static void
+expand_events (struct layout_info *li)
+{
+	GList *events;
+	time_t start, end;
+	int i;
+	int cols;
+
+	for (i = 0, events = li->events; events; events = events->next, i++) {
+		(* li->func) (events, &start, &end);
+
+		cols = columns_to_expand (li, i, start, end);
+
+		if (cols == 0)
+			continue; /* We can't expand this event */
+
+		do_expansion (li, i, start, end, cols);
+
+		li->slots[i] += cols;
+	}
+}
+
+void
+layout_events (GList *events, LayoutQueryTimeFunc func,
+	       int *num_slots, int **allocations, int **slots)
+{
+	struct layout_info li;
+	int i;
+
+	g_return_if_fail (num_slots != NULL);
+	g_return_if_fail (allocations != NULL);
+	g_return_if_fail (slots != NULL);
+
+	if (!events) {
+		*num_slots = 0;
+		*allocations = NULL;
+		*slots = NULL;
+
+		return;
+	}
+
+	li.events = events;
+	li.num_events = g_list_length (events);
+	li.func = func;
+
+	/* Build the partition of the time range, and then build the array of slots */
+
+	build_partition (&li);
+
+	li.array = g_new (int, li.num_rows * MAX_EVENTS_PER_ROW);
+	for (i = 0; i < (li.num_rows * MAX_EVENTS_PER_ROW); i++)
+		li.array[i] = -1; /* This is our 'empty' value */
+
+	/* Build the arrays for allocations and columns used */
+
+	li.allocations = g_new (int, li.num_events);
+	li.slots = g_new (int, li.num_events);
+
+	/* Perform initial allocation and then expand the events to as many
+         * slots as they can occupy.
+	 */
+
+	initial_allocate (&li);
+	expand_events (&li);
+
+	/* Clean up and return values */
+
+	g_free (li.partition);
+	g_free (li.array);
+
+	*num_slots = li.num_slots;
+	*allocations = li.allocations;
+	*slots = li.slots;
+}