Generating a linear, timeline-based, representation from items that consume time and items which do not, but still need space to be drawn on

Question

This is a question about generating an image, or any other representations, for a set of parallel data. Is is not about drawing or GUI programming but calculating positions. First I'll explain a bit where I stand right now and the second image and example shows my problem.

Current Status

exampleOne-Easy http://www.wargsang.de/text3935.png

I have one-dimensional objects but they are aligned by placing them on parallel "lines". Let's call this one-dimensional objects "events" which have a "Duration" as a unit of time. These events have a variant where nothing happens, objects with no data but a duration; A "gap"-object.

So we get a timetable with simulatanious objects consisting of events and gaps, which is pretty easy to handle as three lists of objects. The visualization is simple as well: Loop over the lists and draw each object according to its duration.

class Event():
    def __init__(self, duration, displacement = 0):  #displacement is explained in the second example and the core problem of this question
        self.duration = duration
        self.displacement = displacement
        #additional data

    def self.draw(self, start_coordinate):
        """draw duration * 10 pixels in black"""
        #drawing code using start_coordinate to place the drawn object. see example graphic
        return duration * 10


class Gap():
    def __init__(self, duration, displacement = 0):
        self.duration = duration
        self.displacement = displacement
        #no data

    def self.draw(self, start_coordinate):
        """draw duration * 10 pixels in transparent"""
        #drawing code using start_coordinate to place the drawn object. see example graphic
        return duration * 10

row_one = [Event(1), Gap(1), Event(1), Gap(1), Event(1), Gap(1), Event(2)]
row_two = [Event(1), Gap(2), Event(1), Event(1), Gap(1), Event(1), Gap(1), ]
row_thr = [Gap(1), Event(1), Gap(1), Event(1), Gap(1), Event(3),]

timetable = [row_one, row_two, row_thr]

for row in timetable:
    pixelcounter = 0 # the current position.
    for item in row:
        ret = item.draw(pixelcounter) #draw on the current position. Get how width the item was
        pixelcounter += ret #save width for the next iteration        
    #instructions to move the "drawing cursor" down a few pixels so the next row does not overlap.     

The Problem

Now to the problem. There are objects which need a graphical space but have zero duration. I call this "Displacement".

exampleTwo-Problematic http://www.wargsang.de/text4120.png

Or we need objects which have duration but also have displacement. This is still not a problem when we only have a single row, but synchronizing the rows is more complex and I don't have a solution for this.

In the picture above the red blocks have zero duration and are displaced. Blue blocks have duration and are displaced, too.

Example: *Imagine a timetable for a conference with different speaker slots each hour (our duration-slots). Each row represents a different conference-room.

• The black blocks are speeches and maybe have a short topic written within them (graphically).

• Blue blocks are speeches, too, but the topic was too long to write so we need more space once.

• Red are notes like a room-number change. They don't take time of their own but relate to all items which come after them.*

The task is to find a way to calulate the pixelcounter from the function above so that it is correct for each row alone but also that displacement in one row affects all other rows and creates additional space there. The goal is that durations are fixed and aligned in each row. Any event or gap that should start on, for example, unit-count 4, should begin at the same absolute position.

This means that any zero-duration/displacement object starts at a real point in time/duration but does not consume any time/duration itself so that all subsequent items start on the very same duration until the next real duration event is included. From another point of view that also means that zero-duration items start always before the events which have duration.

In the picture we can see a rather simple case in column 2, which also means this starts the second duration slot. Eventhough there are three real events in that column that are shifted to the right because a displace item is there. Column 4 has a duration item which has displacement as well. Again, All items that start in slot 5 are shifted to the right. Colum 6 is the most interesting and my real problem, I can't find a solution here. Again, all real events in column 6 are shifted to the right and still start at the same time. But here we have a)Displacement-Objects in two rows and two b) two objects right behind each other. So it is important for the real events to know the complete displacement but also important for the second object in the third row to know that there is one more displacement item before it.

Warning: The graphical representation may suggest a table-based approach where each column has an individual width. But this is where this example ends. The real application deals with common duration of 300-10,000 per event but durations of 1 are unlikely but technically possible. So the table would have a column-width of one duration. Considering we got into the hundred thousands of complete duration (times the number of rows) this may drag down the performance.

The data of this picture would look like this. How can I draw the second image with this data? Or what needs to be changed, I am open for all suggestions.

Thank you very much for your time and interest. If you don't know a solution please don't hesitate to ask me questions or show me flaws of my concept, it will help me think as well.

row_one = [ Event(1), #1
            Event(0,1), Event(1), #2
            Gap(1), #3
            Event(1), #4
            Gap(1), #5
            Event(0,1), Event(1), #6
            Event(1), #7
            ] 
row_two = [ Event(1), #1
            Event(1), #2
            Gap(1), #3
            Event(1, 0.5), #4, 0,5 is not important. we can also simply to just ints. The important bit is that it has both values.
            Event(1), #5
            Event(1), #6
            Event(1), #7
            ] 
row_thr = [ Event(1), #1
            Event(1), #2
            Event(1), #3            
            Event(1), #4
            Event(1), #5            
            Event(0,1), Event(0,1), Event(1), #6   #Please pay attention to this case.
            Event(1), #7
            ] 

Answer 1

I'm not completely sure, but I think what you want is:

• displacements on different rows that have the same starting time are synchronized, i.e. have the same horizontal position (the first displacement on each row is synchronized with the first displacements on other rows)
• "real" events and gaps that have the same starting time are synchronized, and come after the displacements with the same starting time
• the width of an event depends on its duration (and possibly its displacement), but not on displacements on other rows, i.e. the ending times are not synchronized

If you want ending times to be synchronized, you'd have to explain how; but I see no obvious way.

Then you get the following solution for your original problem (capitals = events, lowercase letters = displacements, dots = gaps, space = "waiting for synchronization", numbers are starting times of events):

0 123 4  567
AbC.D .e FG
A B.CcD  EF
A BCD EfgHI

You can see that ending times are not synchronized in the following example:

0  12
AAa
Aa B
AaaB

And a larger random example:

                         11    11  1 1     1     1  1   1  22 22   2     2  22  22   33    333    3  3  3 3   3 4   44444  4   4   4  45
    01 2 34   5678    9  01    23  4 5     6     7  8   9  01 23   4     5  67  89   01    234    5  6  7 8   9 0   12345  6   7   8  90
    AAAA  BB   CCC  dd..  EEe   Fff..      GGGGGg           ....         ...    HHH   ....        IIii  JJJ     ...   KKK  LLLLl
abbbCCC  DDDDDdd ..      EEEEE       Fff   GGG          HHH   IIIii      JJJjj  KKKK       LLLl   Mno.  PPP    qR   SSSSSs TT   uuuVV
    ...  AAAAA   BBB      CC    DDDD             ...       EE FFFF          GHhhIIII       JJ.    K  Lll.m....       NNNO  ....
    ......     AAAA      ..    ....        BBB          CCCCCc     DDDDDd        Ee  FFFFff  G hhhIIIII         JJJ   KLLLLLll        M
    .. AAA    BBBCcc  DD  EE    ..   FFF           gH   IIIIIi     J     KKk LL  MMMMM       NNNNNn           OOo   PPQQQQ  rrr...
    AAAAa .   BBBBbb  CCCCC        DDDDDd            eeeFFFFF      GG       HH  .....       IIIII         JJ    K   LM.NNNNN          .
    AAAaaBBB   CCCcc  DDDDDdd      EeFF          ...       GGgHHHH          III  JJJJ       KKK    llMMMm  nnnOOOO    PPPp ...        Q
    AAAAA     BBBBB      CCCC      .....                DDD   EEEEE          FFFff   ....    GGGG         HHHHhh     II....     j  .  .
    AAAaa..   BBBBbb  CccDDDDD       ....               EEE   .F   GgghhhII  Jj KKKK       ...    ...     LLll  ...   MMMM     N   OooP
    ....  Aa  ..BCCC      .....            DDD          EEEe  FFf  .....         GGGG       HIIIIIii          . JJ   ....  KKk     LL
    AAAAAa  bbC.....      DDDDD            ....          eeFFFFff  GGGGG         ...    hh IIJJJ        KKK     L   MMMMMmmNNNN
    ..aBBB    CCCCc   .....        .....                ...   D.   E     FFFFFff   ggHHhiiiJKKKk     LLLLL       mmmNNNOP  Q   RRR
    AA BbCCCC   DD    Ee FFFFFff     GGGGG                 HH IIIi       JjjK..  LLLll     MMMMmm    ....       .   NNNOOOOOoo        P
    AB CCCCC    .....        ddEEEE     fffGgg   HHHHHhh      II jjKKKK         LLLL       MMMM    nn..   OO    PPPPPpp QQQQQqq
    AAA  BBB   CCCC      DDdd  EE  FFF        gggHh IIIii   JJJJ         K  LLLLl    MMm   NNOOOO         .   PP    .QQQRRRRR

And now the code (sorry it's so long, look at Timetable.__init__ for the interesting part, the rest is mostly pretty printing).

from heapq import merge
from itertools import groupby, cycle, chain
from collections import defaultdict
from operator import attrgetter
from string import ascii_uppercase

# events are processed in this order:
# increasing start time, displacements (duration=0) first, and grouped by row_id
ev_sort_attrs = attrgetter("time", "duration", "row_id")


class Event:

    def __init__(self, duration, displacement=0, visible=True, time=None, row_id=None):
        self.duration = duration
        self.displacement = displacement
        self.visible = visible
        self.time = time
        self.row_id = row_id
        self.pos = None

    def draw(self, char):
        return char * self.duration + char.lower() * self.displacement

    def __lt__(self, other):
        return ev_sort_attrs(self) < ev_sort_attrs(other)


def Gap(duration):
    return Event(duration, visible=False)


class Timetable(list):
    def __init__(self, *args):
        """ compute positions for a list of rows of events """
        list.__init__(self, *args)

        # compute times for the events, and give them row_ids
        for i, row in enumerate(self):
            t = 0
            for ev in row:
                ev.time = t
                t += ev.duration
                ev.row_id = i

        # map times to position for displacements and event
        t2pos_disp = defaultdict(int) # maps times to position of synchronized start of displacements
        t2pos_ev = defaultdict(int) # maps times to position of synchronized start of events and gaps

        # the real work is done in the following loop
        t_prev = 0
        for t, g in groupby(merge(*self), key=attrgetter("time")):

            # different times should have a minimum distance corresponding to their difference
            t2pos_ev[t] = t2pos_disp[t] = max(t2pos_ev[t], t2pos_ev[t_prev] + t - t_prev)
            t_prev = t

            for (duration, row_id), g_row in groupby(g, key=attrgetter("duration", "row_id")): # process all displacements first, then the events
                pos_ev = t2pos_ev[t] if duration > 0 else t2pos_disp[t] # events and displacements start at different
                for ev in g_row:
                    ev.pos = pos_ev
                    pos_ev += ev.duration + ev.displacement
                t2pos_ev[t + ev.duration] = max(t2pos_ev[t + ev.duration], pos_ev)

        # keep our results...
        self.t2pos_ev = t2pos_ev
        self.t2pos_disp = t2pos_disp


    @staticmethod
    def str_row(row):
        """ draw row, uppercase letters for real events, lower case letters for
        displacements, dots for gaps"""

        ev_chars = cycle(ascii_uppercase)
        out = []
        l = 0
        for ev in row:
            if ev.pos > l:
                out.append(" " * (ev.pos - l))
            out.append(ev.draw(next(ev_chars) if ev.visible else "."))
            l = ev.pos + len(out[-1])
        return "".join(out)

    def __str__(self):
        max_t, max_p = max(self.t2pos_ev.items())
        w = len(str(max_t))
        header_temp = [" " * w] * (max_p + 1)
        for t, p in self.t2pos_ev.items():
            header_temp[p] = "%*d" % (w, t)
        headers = ("".join(header) for header in zip(*header_temp))

        rows = (self.str_row(row) for row in self)

        return "\n".join(chain(headers, rows))


if __name__ == "__main__":
    # original example
    row_one = [Event(1), Event(0,1), Event(1), Gap(1), Event(1), Gap(1), Event(0,1), Event(1), Event(1)]
    row_two = [Event(1), Event(1), Gap(1), Event(1, 1), Event(1), Event(1), Event(1)]
    row_thr = [Event(1), Event(1), Event(1), Event(1), Event(1), Event(0,1), Event(0,1), Event(1), Event(1)]

    timetable = Timetable([row_one, row_two, row_thr])
    print(timetable)

    print("-" * 80)

    # short example, shows ending times are not synchronized
    print(Timetable([[Event(2, 1)], [Event(1, 1), Event(1)], [Event(1, 2), Event(1)]]))

    print("-" * 80)

    # larger random example
    def random_row(l):
        import random
        res = []
        t = 0
        while t < l:
            x = random.random()
            if x < 0.1: res.append(Event(0, random.randint(1, 3)))
            elif x < 0.8: res.append(Event(min(random.randint(1, 5), l - t), random.randint(0, 1) * random.randint(0, 2)))
            else: res.append(Gap(min(random.randint(1, 5), l - t)))
            t += res[-1].duration
        return res

    print(Timetable([random_row(50) for _ in range(15)]))