Search for an algorithm for efficient layout of calendar event banners
I am looking for an algorithm to effectively place event banners throughout the day and multiple days, just like in the month view in Outlook or Google Calendar. I have multiple events with start and end dates sorted in ascending order of start (and then end) date (or whatever order I give you, I collect events from a database table). I would like to minimize the average amount of vertical space used, because after the event banners, I will only need to post other events for that day (they always appear after the banners on a given date). So, for example, if I had two events, one 1 / 10-1 / 11 and one 1 / 11-1 / 15, I would prefer to arrange them like this (each column one day):
bbbbb
aa
and don't like:
aa
bbbbb
because when I add events for the day only (x, y and z), I can do this (I would prefer the first, don't want the second):
bbbbb vs. aa
aa xyz bbbbb
xyz
But this is not as easy as transferring longer events, because from 1 / 10-1 / 11, 1 / 13-1 / 14 and 1 / 11-1 / 13, I would like to:
aa cc
bbb
Unlike:
bbb
aa cc
because this will allow events x and y to be received:
aa cc vs. bbb
xbbby aa cc
x y
And of course I would prefer to do it in one pass. For the data structure, I am currently using a date to list map, where for each day of the event, I add the event to the appropriate list. Thus, a three-day event appears in three lists, each of which is on one of the days on the map. It's a handy structure for converting a result to visual output, but I'm open to other data structures too. I am currently using a greedy algorithm where I just add each event to the order, but this can lead to unwanted artifacts, for example:
aa ccc
bbbbb
dd
eeeeeeeeeeeeeeeee
This takes up a lot of space for most "e" days.
Any ideas?
source to share
Here is a high level sketch of one possible solution (using whole days of the week rather than full dates). This interface:
public interface IEvent {
public abstract int getFirst(); // first day of event
public abstract int getLast(); // last day of event
public abstract int getLength(); // total number of days
public abstract char getLabel(); // one-char identifier
// true if this and that have NO days in common
public abstract boolean isCompatible(IEvent that);
// true if this is is compatible with all events
public abstract boolean isCompatibleWith(Collection<IEvent> events);
}
must be implemented to use the algorithm expressed in the method layout
below.
In addition, the concrete class must implement Comparable
to create a natural ordering when longer events precede shorter events. (My example implementation uses descending length order, then ascending start date, then ascending label for the demonstration below.)
The method layout
takes a collection of instances IEvent
and returns Map
, which assigns each row in the view to a set of events that can be shown on that row.
public Map<Integer,Set<IEvent>> layout(Collection<IEvent> events) {
Set<IEvent> remainingEvents = new TreeSet<IEvent>(events);
Map<Integer,Set<IEvent>> result = new TreeMap<Integer,Set<IEvent>>();
int day = 0;
while (0 < remainingEvents.size()) {
Set<IEvent> dayEvents = new TreeSet<IEvent>();
for(IEvent e : remainingEvents) {
if (e.isCompatibleWith(dayEvents)) {
dayEvents.add(e);
}
}
remainingEvents.removeAll(dayEvents);
result.put(day, dayEvents);
++day;
}
return result;
}
Each row consists of a selection of the longest remaining event and a gradual selection of all additional events (in the order described above) that are compatible with the previously selected events for the current row. The effect is that all events "float" upward as far as possible without collision.
The following demo shows two scenarios for your question along with a randomly generated set of events.
Event collection:
x(1):4
b(5):2..6
y(1):5
a(2):1..2
z(1):6
Result of layout:
0 -> {b(5):2..6}
1 -> {a(2):1..2, x(1):4, y(1):5, z(1):6}
Visual presentation:
bbbbb
aa xyz
Event collection:
x(1):1
b(3):2..4
a(2):1..2
c(2):4..5
y(1):5
Result of layout:
0 -> {b(3):2..4, x(1):1, y(1):5}
1 -> {a(2):1..2, c(2):4..5}
Visual presentation:
xbbby
aa cc
Event collection:
f(2):1..2
h(2):1..2
d(4):1..4
e(4):2..5
c(1):6
a(2):5..6
g(4):2..5
b(2):0..1
Result of layout:
0 -> {d(4):1..4, a(2):5..6}
1 -> {e(4):2..5, b(2):0..1, c(1):6}
2 -> {g(4):2..5}
3 -> {f(2):1..2}
4 -> {h(2):1..2}
Visual presentation:
ddddaa
bbeeeec
gggg
ff
hh
source to share
I think that in a situation like this, you are much better off making sure your data is ordered correctly first and then rendering it. I know you want to go through one pass, but I think the results will be much better.
For example, organize the data in the rows that you need to have for a given day, and organize the events in the best possible way, starting with the longest events (you don't need to display first, but they need to be organized first) and move on to the shortest events. This will allow you to draw your conclusion accordingly, without wasting space, and avoiding those days of "e" events. Additionally:
bbb
aa cc
or
aa cc
bbb
does not matter, because x
and y
can always go on either side of bbb
or even between aa
andcc
I hope you find it helpful.
source to share