title: Building a Timeline from Lossy Time Stamps
body: <p>I'm working with a product from Velodyne called the VLP-16 (the manual is available from their website with details) and I'm trying to build a timeline of the data it sends. The data it sends comes through a UDP transmission (UDP packets may appear out of order) and each packet is time-stamped with a 32-bit microsecond value. The microsecond value is synced with UTC time. This means that the timestamp will wrap around back to zero after each hour in UTC time. Since UDP packets may technically appear out of order, it is difficult to know what hour a packet may belong to.</p>
  <p>Here's a snippet of code that generally describes the problem at hand:</p>
  <pre class="lang-cpp prettyprint-override"><code>struct LidarPacket
  {
    uint32_t microsecond;
  
    /* other data */
  };
  
  struct LidarTimelineEntry
  {
    uint32_t hour;
    LidarPacket packet;
  };
  
  using LidarTimeline = std::vector&lt;LidarTimelineEntry&gt;;
  
  void InsertAndSort(LidarTimeline&amp; timeline, uint32_t hour, const LidarPacket&amp;);
  
  void OnLidarPacket(LidarTimeline &amp;timeline, LidarPacket&amp; newestPacket)
  {
    /* Where to insert 'newestPacket'? */
  }
  </code></pre>
  <p>The simplest approach would be to assume that the packets come in order.</p>
  <pre class="lang-cpp prettyprint-override"><code>void OnLidarPacket(LidarTimeline &amp;timeline, LidarPacket&amp; newestPacket)
  {
    if (timeline.empty()) {
      timeline.emplace_back(LidarTimelineEntry{0, newestPacket});
      return;
    }
  
    auto &amp;lastEntry = timeline.back();
  
    if (newestPacket.microsecond &lt; lastEntry.packet.microsecond) {
      InsertAndSort(timeline, lastEntry.hour + 1, newestPacket);
    } else {
      InsertAndSort(timeline, lastEntry.hour, newestPacket);
    }
  }
  </code></pre>
  <p>This approach will fail if even one packet is out of order though. A slightly more robust way is to also check to see if the wrap occurs near the end of the hour.</p>
  <pre class="lang-cpp prettyprint-override"><code>bool NearEndOfHour(const LidarPacket&amp; lidarPacket)
  {
    const uint32_t packetDuration = 1344; // &lt;- approximate duration of one packet.
  
    const uint32_t oneHour = 3600000000; // &lt;- one hour in microseconds
  
    return (lidarPacket.microsecond &lt; packetDuration) || (lidarPacket.microsecond &gt; (oneHour - packetDuration));
  }
  
  void OnLidarPacket(LidarTimeline &amp;timeline, LidarPacket&amp; newestPacket)
  {
    if (timeline.empty()) {
      timeline.emplace_back(LidarTimelineEntry{0, newestPacket});
      return;
    }
  
    auto &amp;lastEntry = timeline.back();
  
    if ((newestPacket.microsecond &lt; lastEntry.packet.microsecond) &amp;&amp; NearEndOfHour(lastEntry.packet)) {
      InsertAndSort(timeline, lastEntry.hour + 1, newestPacket);
    } else {
      InsertAndSort(timeline, lastEntry.hour, newestPacket);
    }
  }
  </code></pre>
  <p>But it's difficult to tell if this is really going to cut it. What is the best way to build a multi-hour timeline from microsecond-stamped data coming from a UDP stream?</p>
  <p><em>Doesn't have to be answered in C++</em></p>