path: root/calendar/gui/e-day-view-layout.c

/*
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) version 3.
 *
 * 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with the program; if not, see <http://www.gnu.org/licenses/>
 *
 *
 * Authors:
 *      Damon Chaplin <damon@ximian.com>
 *
 * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
 *
 */

/*
 * Lays out events for the Day & Work-Week views of the calendar. It is also
 * used for printing.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "e-day-view-layout.h"

static void e_day_view_layout_long_event (EDayViewEvent   *event,
                      guint8      *grid,
                      gint         days_shown,
                      time_t      *day_starts,
                      gint        *rows_in_top_display);

static void e_day_view_layout_day_event (EDayViewEvent    *event,
                     EBitArray       **grid,
                     guint16      *group_starts,
                     guint8       *cols_per_row,
                     gint          rows,
                     gint          mins_per_row,
                     gint              max_cols);
static void e_day_view_expand_day_event (EDayViewEvent    *event,
                     EBitArray       **grid,
                     guint8       *cols_per_row,
                     gint          mins_per_row);
static void e_day_view_recalc_cols_per_row (gint           rows,
                        guint8    *cols_per_row,
                        guint16       *group_starts);

void
e_day_view_layout_long_events (GArray *events,
                               gint days_shown,
                               time_t *day_starts,
                               gint *rows_in_top_display)
{
    EDayViewEvent *event;
    gint event_num;
    guint8 *grid;

    /* This is a temporary 2-d grid which is used to place events.
     * Each element is 0 if the position is empty, or 1 if occupied.
     * We allocate the maximum size possible here, assuming that each
     * event will need its own row. */
    grid = g_new0 (guint8, events->len * E_DAY_VIEW_MAX_DAYS);

    /* Reset the number of rows in the top display to 0. It will be
     * updated as events are layed out below. */
    *rows_in_top_display = 0;

    /* Iterate over the events, finding which days they cover, and putting
     * them in the first free row available. */
    for (event_num = 0; event_num < events->len; event_num++) {
        event = &g_array_index (events, EDayViewEvent, event_num);
        e_day_view_layout_long_event (
            event, grid,
            days_shown, day_starts,
            rows_in_top_display);
    }

    /* Free the grid. */
    g_free (grid);
}

static void
e_day_view_layout_long_event (EDayViewEvent *event,
                              guint8 *grid,
                              gint days_shown,
                              time_t *day_starts,
                              gint *rows_in_top_display)
{
    gint start_day, end_day, free_row, day, row;

    event->num_columns = 0;

    if (!e_day_view_find_long_event_days (event,
                          days_shown, day_starts,
                          &start_day, &end_day))
        return;

    /* Try each row until we find a free one. */
    row = 0;
    do {
        free_row = row;
        for (day = start_day; day <= end_day; day++) {
            if (grid[row * E_DAY_VIEW_MAX_DAYS + day]) {
                free_row = -1;
                break;
            }
        }
        row++;
    } while (free_row == -1);

    event->start_row_or_col = free_row;
    event->num_columns = 1;

    /* Mark the cells as full. */
    for (day = start_day; day <= end_day; day++) {
        grid[free_row * E_DAY_VIEW_MAX_DAYS + day] = 1;
    }

    /* Update the number of rows in the top canvas if necessary. */
    *rows_in_top_display = MAX (*rows_in_top_display, free_row + 1);
}

/* returns maximum number of columns among all rows */
gint
e_day_view_layout_day_events (GArray *events,
                              gint rows,
                              gint mins_per_row,
                              guint8 *cols_per_row,
                              gint max_cols)
{
    EDayViewEvent *event;
    gint row, event_num, res;
    EBitArray **grid;

    /* This is a temporary array which keeps track of rows which are
     * connected. When an appointment spans multiple rows then the number
     * of columns in each of these rows must be the same (i.e. the maximum
     * of all of them). Each element in the array corresponds to one row
     * and contains the index of the first row in the group of connected
     * rows. */
    guint16 group_starts[12 * 24];

    /* This is a temporary 2-d grid which is used to place events.
     * Each element is 0 if the position is empty, or 1 if occupied. */
    grid = g_new0 (EBitArray *, rows);

    /* Reset the cols_per_row array, and initialize the connected rows so
     * that all rows are not connected - each row is the start of a new
     * group. */
    for (row = 0; row < rows; row++) {
        cols_per_row[row] = 0;
        group_starts[row] = row;

        /* row doesn't contain any event at the moment */
        grid[row] = e_bit_array_new (0);
    }

    /* Iterate over the events, finding which rows they cover, and putting
     * them in the first free column available. Increment the number of
     * events in each of the rows it covers, and make sure they are all
     * in one group. */
    for (event_num = 0; event_num < events->len; event_num++) {
        event = &g_array_index (events, EDayViewEvent, event_num);

        e_day_view_layout_day_event (
            event, grid, group_starts,
            cols_per_row, rows, mins_per_row, max_cols);
    }

    /* Recalculate the number of columns needed in each row. */
    e_day_view_recalc_cols_per_row (rows, cols_per_row, group_starts);

    /* Iterate over the events again, trying to expand events horizontally
     * if there is enough space. */
    for (event_num = 0; event_num < events->len; event_num++) {
        event = &g_array_index (events, EDayViewEvent, event_num);
        e_day_view_expand_day_event (
            event, grid, cols_per_row,
            mins_per_row);
    }

    /* Free the grid and compute maximum number of columns used. */
    res = 0;
    for (row = 0; row < rows; row++) {
        res = MAX (res, e_bit_array_bit_count (grid[row]));
        g_object_unref (grid[row]);
    }
    g_free (grid);

    return res;
}

/* Finds the first free position to place the event in.
 * Increments the number of events in each of the rows it covers, and makes
 * sure they are all in one group. */
static void
e_day_view_layout_day_event (EDayViewEvent *event,
                             EBitArray **grid,
                             guint16 *group_starts,
                             guint8 *cols_per_row,
                             gint rows,
                             gint mins_per_row,
                             gint max_cols)
{
    gint start_row, end_row, free_col, col, row, group_start;

    start_row = event->start_minute / mins_per_row;
    end_row = (event->end_minute - 1) / mins_per_row;
    if (end_row < start_row)
        end_row = start_row;

    event->num_columns = 0;

    /* If the event can't currently be seen, just return. */
    if (start_row >= rows || end_row < 0)
        return;

    /* Make sure we don't go outside the visible times. */
    start_row = CLAMP (start_row, 0, rows - 1);
    end_row = CLAMP (end_row, 0, rows - 1);

    /* Try each column until we find a free one. */
    for (col = 0; max_cols <= 0 || col < max_cols; col++) {
        free_col = col;
        for (row = start_row; row <= end_row; row++) {
            if (e_bit_array_bit_count (grid[row]) > col &&
                e_bit_array_value_at (grid[row], col)) {
                free_col = -1;
                break;
            }
        }

        if (free_col != -1)
            break;
    }

    /* If we can't find space for the event, just return. */
    if (free_col == -1)
        return;

    /* The event is assigned 1 col initially, but may be expanded later. */
    event->start_row_or_col = free_col;
    event->num_columns = 1;

    /* Determine the start index of the group. */
    group_start = group_starts[start_row];

    /* Increment number of events in each of the rows the event covers.
     * We use the cols_per_row array for this. It will be sorted out after
     * all the events have been layed out. Also make sure all the rows that
     * the event covers are in one group. */
    for (row = start_row; row <= end_row; row++) {
        /* resize the array if necessary */
        if (e_bit_array_bit_count (grid[row]) <= free_col)
            e_bit_array_insert (
                grid[row], e_bit_array_bit_count (grid[row]),
                free_col - e_bit_array_bit_count (grid[row]) + 1);

        e_bit_array_change_one_row (grid[row], free_col, TRUE);
        cols_per_row[row]++;
        group_starts[row] = group_start;
    }

    /* If any following rows should be in the same group, add them. */
    for (row = end_row + 1; row < rows; row++) {
        if (group_starts[row] > end_row)
            break;
        group_starts[row] = group_start;
    }
}

/* For each group of rows, find the max number of events in all the
 * rows, and set the number of cols in each of the rows to that. */
static void
e_day_view_recalc_cols_per_row (gint rows,
                                guint8 *cols_per_row,
                                guint16 *group_starts)
{
    gint start_row = 0, row, next_start_row, max_events;

    while (start_row < rows) {
        max_events = 0;
        for (row = start_row; row < rows && group_starts[row] == start_row; row++)
            max_events = MAX (max_events, cols_per_row[row]);

        next_start_row = row;

        for (row = start_row; row < next_start_row; row++)
            cols_per_row[row] = max_events;

        start_row = next_start_row;
    }
}

/* Expands the event horizontally to fill any free space. */
static void
e_day_view_expand_day_event (EDayViewEvent *event,
                             EBitArray **grid,
                             guint8 *cols_per_row,
                             gint mins_per_row)
{
    gint start_row, end_row, col, row;
    gboolean clashed;

    start_row = event->start_minute / mins_per_row;
    end_row = (event->end_minute - 1) / mins_per_row;
    if (end_row < start_row)
        end_row = start_row;

    /* Try each column until we find a free one. */
    clashed = FALSE;
    for (col = event->start_row_or_col + 1; col < cols_per_row[start_row]; col++) {
        for (row = start_row; row <= end_row; row++) {
            if (e_bit_array_bit_count (grid[row]) > col &&
                e_bit_array_value_at (grid[row], col)) {
                clashed = TRUE;
                break;
            }
        }

        if (clashed)
            break;

        event->num_columns++;
    }
}

/* Find the start and end days for the event. */
gboolean
e_day_view_find_long_event_days (EDayViewEvent *event,
                                 gint days_shown,
                                 time_t *day_starts,
                                 gint *start_day_return,
                                 gint *end_day_return)
{
    gint day, start_day, end_day;

    start_day = -1;
    end_day = -1;

    for (day = 0; day < days_shown; day++) {
        if (start_day == -1
            && event->start < day_starts[day + 1])
            start_day = day;
        if (event->end > day_starts[day])
            end_day = day;
    }

    /* Sanity check. */
    if (start_day < 0 || start_day >= days_shown
        || end_day < 0 || end_day >= days_shown
        || end_day < start_day) {
        g_warning ("Invalid date range for event");
        return FALSE;
    }

    *start_day_return = start_day;
    *end_day_return = end_day;

    return TRUE;
}