From 2389bd7bedc9b1caf3e9f34631c70c8ddf3fb306 Mon Sep 17 00:00:00 2001 From: Federico Mena Quintero Date: Thu, 8 Oct 1998 17:19:43 +0000 Subject: Do some cleanup; now we pass a struct with the layout algorithm's state 1998-10-08 Federico Mena Quintero * layout.c: Do some cleanup; now we pass a struct with the layout algorithm's state instead of passing a trillion parameters around. * gncal-full-day.c (layout_children): Use the new generic layout engine. (child_compare): Sort keys are start time then end time, not just start time. This produces somewhat nicer results for the layout algorithm. The new layout code uses a partition of the time range occupied by the events, rather than using a fixed time granularity. This is better since the different parts of the program that use the layout module will have different semantics regarding snapping the event bounds to a fixed "time grid". svn path=/trunk/; revision=434 --- calendar/layout.c | 155 ++++++++++++++++++++++++++++++------------------------ 1 file changed, 86 insertions(+), 69 deletions(-) (limited to 'calendar/layout.c') diff --git a/calendar/layout.c b/calendar/layout.c index 03fac94cc6..f97f0d5ffd 100644 --- a/calendar/layout.c +++ b/calendar/layout.c @@ -6,9 +6,25 @@ * Federico Mena */ +#include +#include #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. */ @@ -35,37 +51,35 @@ compare_time_t (const void *a, const void *b) /* 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 time_t * -build_partition (GList *events, int num_events, int *num_rows) +static void +build_partition (struct layout_info *li) { time_t *rows, *p, *q; GList *list; - CalendarObject *co; int i, unique_vals; /* This is the maximum number of rows we would need */ - *num_rows = num_events * 2; + li->num_rows = li->num_events * 2; /* Fill the rows with the times */ - rows = g_new (time_t, *num_rows); + rows = g_new (time_t, li->num_rows); - for (list = events, p = rows; list; list = list->next) { - co = list->data; - *p++ = co->ev_start; - *p++ = co->ev_end; + 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, *num_rows, sizeof (time_t), compare_time_t); + qsort (rows, li->num_rows, sizeof (time_t), compare_time_t); p = rows; q = rows + 1; unique_vals = 1; - for (i = 1; i < *num_rows; i++, q++) + for (i = 1; i < li->num_rows; i++, q++) if (*q != *p) { unique_vals++; p++; @@ -74,33 +88,33 @@ build_partition (GList *events, int num_events, int *num_rows) /* Return the number of unique values in the partition and the partition array itself */ - *num_rows = unique_vals; - return rows; + li->num_rows = unique_vals; + li->partition = rows; } /* Returns the index of the element in the partition that corresponds to the specified time */ int -find_index (time_t *partition, time_t t) +find_index (struct layout_info *li, time_t t) { int i; for (i = 0; ; i++) - if (partition[i] == t) + if (li->partition[i] == t) return i; } -#define xy(slot_array, x, y) slot_array[(y * MAX_EVENTS_PER_ROW) + (x)] +#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 (time_t *partition, int *slot_array, int slot, time_t start, time_t end) +range_is_empty (struct layout_info *li, int slot, time_t start, time_t end) { int i; - for (i = find_index (partition, start); partition[i] < end; i++) - if (xy (slot_array, slot, i) != -1) + for (i = find_index (li, start); li->partition[i] < end; i++) + if (xy (li, slot, i) != -1) return FALSE; return TRUE; @@ -108,43 +122,44 @@ range_is_empty (time_t *partition, int *slot_array, int slot, time_t start, time /* Allocates a time in the slot array for the specified event's index */ static void -range_allocate (time_t *partition, int *slot_array, int slot, time_t start, time_t end, int ev_num) +range_allocate (struct layout_info *li, int slot, time_t start, time_t end, int ev_num) { int i; - for (i = find_index (partition, start); partition[i] < end; i++) - xy (slot_array, slot, i) = ev_num; + 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 int -initial_allocate (GList *events, time_t *partition, int *slot_array, int *allocations, int *columns_used) +static void +initial_allocate (struct layout_info *li) { - CalendarObject *co; + GList *events; int i; int slot; int num_slots; + time_t start, end; num_slots = 0; - for (i = 0; events; events = events->next, i++) { - co = events->data; + for (i = 0, events = li->events; events; events = events->next, i++) { + (* li->func) (events, &start, &end); /* Start with no allocation, no columns */ - allocations[i] = -1; - columns_used[i] = 0; + 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 (partition, slot_array, slot, co->ev_start, co->ev_end)) { - range_allocate (partition, slot_array, slot, co->ev_start, co->ev_end, i); + if (range_is_empty (li, slot, start, end)) { + range_allocate (li, slot, start, end, i); - allocations[i] = slot; - columns_used[i] = 1; + li->allocations[i] = slot; + li->slots[i] = 1; if ((slot + 1) > num_slots) num_slots = slot + 1; @@ -153,13 +168,12 @@ initial_allocate (GList *events, time_t *partition, int *slot_array, int *alloca } } - return num_slots; + 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 (time_t *partition, int *slot_array, int *allocations, int num_slots, int ev_num, - time_t start, time_t end) +columns_to_expand (struct layout_info *li, int ev_num, time_t start, time_t end) { int cols; int slot; @@ -168,11 +182,11 @@ columns_to_expand (time_t *partition, int *slot_array, int *allocations, int num cols = 0; - i_start = find_index (partition, start); + i_start = find_index (li, start); - for (slot = allocations[ev_num] + 1; slot < num_slots; slot++) { - for (i = i_start; partition[i] < end; i++) - if (xy (slot_array, slot, i) != -1) + 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++; @@ -181,18 +195,18 @@ columns_to_expand (time_t *partition, int *slot_array, int *allocations, int num return cols; } -/* Expands an event to occupy the specified number of columns */ +/* Expands an event by the specified number of columns */ static void -do_expansion (time_t *partition, int *slot_array, int *allocations, int ev_num, time_t start, time_t end, int num_cols) +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 (partition, start); partition[i] < end; i++) { - slot = allocations[ev_num] + 1; + 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 (slot_array, slot + j, i) = ev_num; + xy (li, slot + j, i) = ev_num; } } @@ -200,33 +214,31 @@ do_expansion (time_t *partition, int *slot_array, int *allocations, int ev_num, * pass of the layout algorithm. */ static void -expand_events (GList *events, time_t *partition, int *slot_array, int num_slots, int *allocations, int *columns_used) +expand_events (struct layout_info *li) { + GList *events; + time_t start, end; int i; - CalendarObject *co; int cols; - for (i = 0; events; events = events->next, i++) { - co = events->data; + for (i = 0, events = li->events; events; events = events->next, i++) { + (* li->func) (events, &start, &end); - cols = columns_to_expand (partition, slot_array, allocations, num_slots, i, co->ev_start, co->ev_end); + cols = columns_to_expand (li, i, start, end); if (cols == 0) continue; /* We can't expand this event */ - do_expansion (partition, slot_array, allocations, i, co->ev_start, co->ev_end, cols); + do_expansion (li, i, start, end, cols); - columns_used[i] += cols; + li->slots[i] += cols; } } void -layout_events (GList *events, int *num_slots, int **allocations, int **slots) +layout_events (GList *events, LayoutQueryTimeFunc func, int *num_slots, int **allocations, int **slots) { - time_t *time_partition; - int *slot_array; - int num_events; - int num_rows; + struct layout_info li; int i; g_return_if_fail (num_slots != NULL); @@ -241,28 +253,33 @@ layout_events (GList *events, int *num_slots, int **allocations, int **slots) return; } - num_events = g_list_length (events); + 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 */ - time_partition = build_partition (events, num_events, &num_rows); + build_partition (&li); - slot_array = g_new (int, num_rows * MAX_EVENTS_PER_ROW); - for (i = 0; i < (num_rows * MAX_EVENTS_PER_ROW); i++) - slot_array[i] = -1; /* This is our 'empty' value */ + 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 */ - *allocations = g_new (int, num_events); - *slots = g_new (int, num_events); + li.allocations = g_new (int, li.num_events); + li.slots = g_new (int, li.num_events); - /* Perform initial allocation -- each event gets one column */ + /* Perform initial allocation and then expand the events to as many slots as they can occupy */ - *num_slots = initial_allocate (events, time_partition, slot_array, *allocations, *slots); + initial_allocate (&li); + expand_events (&li); - /* Expand the events to as many columns as possible */ + /* Clean up and return values */ - expand_events (events, time_partition, slot_array, *num_slots, *allocations, *slots); + g_free (li.array); - g_free (slot_array); + *num_slots = li.num_slots; + *allocations = li.allocations; + *slots = li.slots; } -- cgit