From 3b1a500fd323b3f3908477f3df66f1ab0ad7674b Mon Sep 17 00:00:00 2001 From: Arturo Espinosa Date: Thu, 8 Oct 1998 00:21:47 +0000 Subject: Doh, add the files - Federico svn path=/trunk/; revision=433 --- calendar/gui/layout.c | 268 ++++++++++++++++++++++++++++++++++++++++++++++++++ calendar/gui/layout.h | 25 +++++ 2 files changed, 293 insertions(+) create mode 100644 calendar/gui/layout.c create mode 100644 calendar/gui/layout.h (limited to 'calendar/gui') diff --git a/calendar/gui/layout.c b/calendar/gui/layout.c new file mode 100644 index 0000000000..03fac94cc6 --- /dev/null +++ b/calendar/gui/layout.c @@ -0,0 +1,268 @@ +/* Event layout engine for Gnomecal + * + * Copyright (C) 1998 The Free Software Foundation + * + * Authors: Miguel de Icaza + * Federico Mena + */ + +#include "layout.h" + + +/* 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 time_t * +build_partition (GList *events, int num_events, int *num_rows) +{ + 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; + + /* Fill the rows with the times */ + + rows = g_new (time_t, *num_rows); + + for (list = events, p = rows; list; list = list->next) { + co = list->data; + *p++ = co->ev_start; + *p++ = co->ev_end; + } + + /* Do a sort | uniq on the array */ + + qsort (rows, *num_rows, sizeof (time_t), compare_time_t); + + p = rows; + q = rows + 1; + unique_vals = 1; + + for (i = 1; i < *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 */ + + *num_rows = unique_vals; + return 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) +{ + int i; + + for (i = 0; ; i++) + if (partition[i] == t) + return i; +} + +#define xy(slot_array, x, y) slot_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) +{ + int i; + + for (i = find_index (partition, start); partition[i] < end; i++) + if (xy (slot_array, slot, i) != -1) + return FALSE; + + return TRUE; +} + +/* 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) +{ + int i; + + for (i = find_index (partition, start); partition[i] < end; i++) + xy (slot_array, 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) +{ + CalendarObject *co; + int i; + int slot; + int num_slots; + + num_slots = 0; + + for (i = 0; events; events = events->next, i++) { + co = events->data; + + /* Start with no allocation, no columns */ + + allocations[i] = -1; + columns_used[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); + + allocations[i] = slot; + columns_used[i] = 1; + + if ((slot + 1) > num_slots) + num_slots = slot + 1; + + break; + } + } + + return 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) +{ + int cols; + int slot; + int i_start; + int i; + + cols = 0; + + i_start = find_index (partition, 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) + return cols; + + cols++; + } + + return cols; +} + +/* Expands an event to occupy 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) +{ + int i, j; + int slot; + + for (i = find_index (partition, start); partition[i] < end; i++) { + slot = allocations[ev_num] + 1; + + for (j = 0; j < num_cols; j++) + xy (slot_array, 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 (GList *events, time_t *partition, int *slot_array, int num_slots, int *allocations, int *columns_used) +{ + int i; + CalendarObject *co; + int cols; + + for (i = 0; events; events = events->next, i++) { + co = events->data; + + cols = columns_to_expand (partition, slot_array, allocations, num_slots, i, co->ev_start, co->ev_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); + + columns_used[i] += cols; + } +} + +void +layout_events (GList *events, int *num_slots, int **allocations, int **slots) +{ + time_t *time_partition; + int *slot_array; + int num_events; + int num_rows; + 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; + } + + num_events = g_list_length (events); + + /* Build the partition of the time range, and then build the array of slots */ + + time_partition = build_partition (events, num_events, &num_rows); + + 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 */ + + /* Build the arrays for allocations and columns used */ + + *allocations = g_new (int, num_events); + *slots = g_new (int, num_events); + + /* Perform initial allocation -- each event gets one column */ + + *num_slots = initial_allocate (events, time_partition, slot_array, *allocations, *slots); + + /* Expand the events to as many columns as possible */ + + expand_events (events, time_partition, slot_array, *num_slots, *allocations, *slots); + + g_free (slot_array); +} diff --git a/calendar/gui/layout.h b/calendar/gui/layout.h new file mode 100644 index 0000000000..b87cf7e36b --- /dev/null +++ b/calendar/gui/layout.h @@ -0,0 +1,25 @@ +/* Event layout engine for Gnomecal + * + * Copyright (C) 1998 The Free Software Foundation + * + * Authors: Miguel de Icaza + * Federico Mena + */ + +#ifndef LAYOUT_H +#define LAYOUT_H + +#include "calendar.h" + + +/* This is the main layout function for overlapping events. You pass in a list of CalendarObject + * structures and it will calculate a nice non-overlapping layout for them. + * + * It returns the number of slots ("columns") that you need to take into account when actually + * painting the events, the array of the first slot index that each event occupies, and the array of + * number of slots that each event occupies. You have to free both arrays. + */ +void layout_events (GList *events, int *num_slots, int **allocations, int **slots); + + +#endif -- cgit v1.2.3