从消耗时间的项和不消耗但仍需要空间的项生成线性的、基于时间的表示

Question

这是一个关于为一组并行数据生成图像或任何其他表示的问题。不是关于绘图或GUI编程，而是计算位置。 首先，我将解释一下我现在的立场，第二张图片和示例展示了我的问题。在

现状

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

我有一个一维的物体，但它们是通过把它们放在平行的“直线”上对齐的。我们把这个一维对象称为“事件”，它以“持续时间”为时间单位。 这些事件有一个变量，其中没有发生任何事情，对象没有数据，只有持续时间；一个“间隙”对象。在

因此，我们得到了一个由事件和间隙组成的模拟对象的时间表，它很容易作为三个对象列表来处理。 可视化也很简单：在列表上循环并根据其持续时间绘制每个对象。在

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.     

问题

现在是问题。有些对象需要图形空间，但持续时间为零。 我称之为“位移”。在

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

或者我们需要有持续时间但也有位移的物体。 当我们只有一行时，这仍然不是问题，但是同步行更复杂，我没有解决方案。在

在上图中，红色方块的持续时间为零，并被替换。蓝色方块有持续时间，也会被取代。在

示例： *想象一下一个会议的时间表，每小时有不同的演讲者时段（我们的时段）。每一行代表一个不同的会议室。在

• 黑色方块是演讲稿，可能有一个简短的主题（以图形方式）写在里面。

• 蓝色方块也是演讲稿，但主题太长，写不下，所以我们需要更多的空间。

• 红色是房间号码的变化。它们不需要自己花时间，而是与后面的所有项目相关。*

任务是从上面的函数中找到一种计算像素计数器的方法，这样每一行都是正确的，但是一行中的位移会影响所有其他行，并在那里创建额外的空间。 目标是在每一行中固定和对齐持续时间。任何应该开始的事件或间隔，例如，单位计数4，都应该从相同的绝对位置开始。在

这意味着，任何零持续时间/置换对象从实际时间/持续时间点开始，但不会消耗任何时间/持续时间本身，因此所有后续项目都从相同的持续时间开始，直到包含下一个实际持续时间事件。从另一个角度来看，这也意味着零持续时间项总是在具有持续时间的事件之前开始。在

在图中，我们可以在第2列看到一个相当简单的情况，这也意味着这将开始第二个持续时间槽。尽管该列中有三个实际事件被右移，因为那里有一个置换项。 第4列有一个持续时间项，它也有位移。同样，所有从插槽5开始的项目都会向右移动。 哥伦布6是最有趣也是我真正的问题，我在这里找不到解决办法。同样，第6列中的所有实际事件都向右移动，并且仍然同时开始。但是这里我们有两排位移物体和两个物体，两个物体在彼此后面。 所以，对于真实事件来说，知道完整的位移是很重要的，但是对于第三排的第二个物体来说，知道在它前面还有一个位移项也是很重要的。在

警告：图形表示可能建议使用基于表的方法，其中每个列都有单独的宽度。但这就是这个例子的结尾。实际应用程序处理的公共持续时间为300-10000个事件，但持续时间不太可能为1，但在技术上是可能的。因此表的列宽为一个持续时间。考虑到我们进了十万完整持续时间（乘以行数）这可能会降低性能。在

这张照片的数据应该是这样的。如何用这些数据绘制第二幅图像？或者需要改变的地方，我愿意接受所有的建议。在

非常感谢您的时间和兴趣。如果你不知道一个解决方案，请不要犹豫，问我问题，或让我看看我的概念的缺陷，这将有助于我思考。在

^{pr2}$

Answer 1

你需要一个函数把你的时间映射到x坐标。困难的是，你有时需要更多的空间。这可以用一个对象列表来解决，说明何时需要以及需要多少额外空间。在

function timeToLocation(t)
  location = t * scale
  for (o : extraSpaceList)
    if o.when < t
      location = location + o.space
  return location

每当您试图放置一个对象，并注意到没有足够的空间（因为元素重叠），只需在需要的时刻插入一些空间，extraSpaceList.add({when=2s,space=4pixels})。逐个处理所有行，然后再次为最终位置处理所有行。在

如果将对象变换为具有开始时间和图形大小，则这会更容易。那么差距和事件就没有区别了。在

Answer 2

我不太确定，但我想你想要的是：

• 开始时间相同的不同行上的位移是同步的，即水平位置相同（每行的第一个位移与其他行的第一个位移同步）
• 具有相同开始时间的“真实”事件和间隙是同步的，并且在具有相同开始时间的位移之后
• 事件的宽度取决于它的持续时间（可能还有它的位移），但是不是取决于其他行上的位移，即结束时间不同步

如果你想让结束时间同步，你必须解释如何同步；但是我看不到明显的方法。在

然后得到原始问题的以下解决方案（大写=事件，小写字母=位移，点=间隙，空格=“等待同步”，数字是事件的开始时间）：

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

在以下示例中可以看到结束时间不同步：

^{pr2}$

还有一个更大的随机例子：

                         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

现在代码（抱歉，太长了，请看Timetable.__init__中有趣的部分，其余大部分都是打印出来的）。在

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

Answer 3

如果我理解你的问题。。。在

对于每一列，在对每一行进行初始处理时，跟踪行的“零持续时间”框的最大宽度。当您最终绘制每个实际事件时，它从其列的max width值的末尾开始。（我假设您已经在计算列的开始位置。）

在上面的彩色图中，处理第1行将为您提供最大的零持续宽度（例如）[0，10，0，0，0，10，0]。第二排不会改变它。第3行将其更改为[0，10，0，0，0，20，0]。在

当您绘制一个真实事件时，它将从它的column\u start+column max zero duration width开始。在