Alla ricerca di un algoritmo per il layout efficiente dei banner degli eventi del calendario

Question

Sto cercando un algoritmo per posizionare in modo efficiente banner per tutto il giorno / più giorni, proprio come la visualizzazione del mese in Outlook o Google Calendar. Ho un certo numero di eventi con una data di inizio e di fine, ordinati aumentando la data di inizio (e poi la fine) (o qualsiasi altro ordine per favore, sto raccogliendo eventi da una tabella del database). Vorrei ridurre al minimo la quantità media di spazio verticale esaurito, perché dopo i banner degli eventi dovrò posizionare altri eventi solo per quel giorno (questi vengono sempre dopo i banner per una determinata data). Quindi, per esempio, se avessi avuto due eventi, uno 1 / 10-1 / 11 e uno 1 / 11-1 / 15, preferirei organizzarli in questo modo (ogni colonna è un singolo giorno):

 bbbbb
aa

e non come:

aa
 bbbbb

perché quando aggiungo gli eventi solo per il giorno (x, ye z), posso farlo (preferirei il primo, non voglio il secondo):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

Ma non è semplice come posizionare prima gli eventi più lunghi, perché con 1 / 10-1 / 11, 1 / 13-1 / 14 e 1 / 11-1 / 13, vorrei:

aa cc
 bbb

al contrario di:

 bbb
aa cc

perché ciò consentirebbe gli eventi xey:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

E ovviamente preferirei farlo in un unico passaggio. Per la struttura dei dati, attualmente sto usando una mappa dalla data all'elenco, dove per ogni giorno di un evento aggiungo l'evento all'elenco corrispondente. Quindi un evento di tre giorni appare in tre elenchi, ognuno sotto uno dei giorni nella mappa. Questa è una struttura conveniente per trasformare il risultato in output visivo, ma sono aperto anche ad altre strutture di dati. Attualmente sto usando un algoritmo avido, in cui aggiungo semplicemente ogni evento in ordine, ma che può produrre artefatti indesiderati come:

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

Questo spreca un lotto di spazio per la maggior parte di " e " giorni dell'evento.

Qualche idea?

Answer 1

Ecco uno schizzo di alto livello di una possibile soluzione (utilizzando numeri interi del giorno della settimana anziché date complete). Questa interfaccia:

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);

}

deve essere implementato per utilizzare l'algoritmo espresso nel metodo layout di seguito.

Inoltre, la classe concreta deve implementare Comparable per creare un ordine naturale in cui eventi più lunghi precedono eventi più brevi. (La mia implementazione di esempio per la demo di seguito ha utilizzato un ordine di lunghezza decrescente, quindi data di inizio crescente, quindi etichetta crescente.)

Il metodo layout prende una raccolta di istanze IEvent e restituisce una Mappa che assegna a ciascuna riga della presentazione l'insieme di eventi che può essere mostrato in quella riga.

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;
}

Ogni riga è composta selezionando l'evento rimanente più lungo e progressivamente selezionando tutti gli eventi aggiuntivi (nell'ordine sopra descritto) che sono compatibili con gli eventi precedentemente selezionati per la riga corrente. L'effetto è che tutti gli eventi "float" verso l'alto il più possibile senza collisione.

La seguente demo mostra i due scenari nella tua domanda, insieme a una serie di eventi creati casualmente.

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    

Answer 2

Penso che in una situazione come questa, stai molto meglio assicurandoti che i tuoi dati siano prima organizzati in modo corretto e poi renderizzati. So che vuoi un singolo passaggio, ma penso che i risultati sarebbero molto meglio.

Ad esempio, organizza i dati nelle righe necessarie per un determinato giorno e organizza gli eventi nel modo migliore possibile, iniziando con gli eventi più lunghi (non è necessario che vengano visualizzati per primi, ma devono essere organizzato per primo) e passare agli eventi più brevi. Ciò ti consentirà di eseguire il rendering dell'output di conseguenza senza sprecare spazio ed evitando quelli "e" giorni dell'evento. Inoltre, quindi:

 bbb
aa cc

o

aa cc
 bbb

non importa perché x e y possono sempre andare su entrambi i lati di bbb o anche tra aa e cc

Spero che questo ti sia utile.