title: Android - What data structure to store video subtitles to get them in O(1) time
body: <p>I am playing a video in my application and I have to show subtitles on top of that. subtitles are in a separate smi file which is some sort of XML markup that provides subtitle information. the subtitle file looks something like this:</p>
  
  <pre><code>.
  .
  .
  &lt;sync start=104600&gt;
              &lt;P Class=GBR&gt;&lt;i&gt;&lt;/i&gt;&lt;span ID=style1_0&gt;&lt;i&gt;Born of cold and winter air&lt;/i&gt; &lt;/span&gt;&lt;br&gt;&lt;i&gt;&lt;/i&gt;&lt;span ID=style1_0&gt;&lt;i&gt;and mountain rain combining.&lt;/i&gt; &lt;/span&gt;&lt;/P&gt;
          &lt;/sync&gt;
          &lt;sync start=107080&gt;
              &lt;P Class=MYS&gt;&amp;nbsp;&lt;br&gt;&lt;/P&gt;
          &lt;/sync&gt;
          &lt;sync start=107200&gt;
              &lt;P Class=MYS&gt;&lt;i&gt;&lt;/i&gt;&lt;span ID=style2_0&gt;&lt;i&gt;...serta hujan di pergunungan.&lt;/i&gt; &lt;/span&gt;&lt;/P&gt;
          &lt;/sync&gt;
          &lt;sync start=110840&gt;
              &lt;P Class=MYS&gt;&amp;nbsp;&lt;br&gt;&lt;/P&gt;
              &lt;P Class=GBR&gt;&amp;nbsp;&lt;br&gt;&lt;/P&gt;
          &lt;/sync&gt;
          &lt;sync start=111160&gt;
              &lt;P Class=SIM&gt;&amp;nbsp;&lt;br&gt;&lt;/P&gt;
          &lt;/sync&gt;
          &lt;sync start=111480&gt;
              &lt;P Class=GBR&gt;&lt;i&gt;&lt;/i&gt;&lt;span ID=style1_0&gt;&lt;i&gt;This icy force&lt;/i&gt; &lt;/span&gt;&lt;br&gt;&lt;i&gt;&lt;/i&gt;&lt;span ID=style1_0&gt;&lt;i&gt;both foul and fair...&lt;/i&gt; &lt;/span&gt;&lt;/P&gt;
          &lt;/sync&gt;
  .
  .
  .
  .
  </code></pre>
  
  <p>the <code>start</code> is the time in milliseconds when to show the subtitle on top of the video. Now I am parsing the using regex and creating a <code>ArrayList</code> of <code>SubtitleChunk</code> which contains the startTime and content associated with it.</p>
  
  <pre><code>class SubtitleChunk {
      long startTime;
      String content;
  }
  </code></pre>
  
  <p>Now while showing the video I have started a separate thread which I am using get the subtitle from array and show it. Following is the logic</p>
  
  <pre><code>public void run() {
      while (!isFinished_) {
              if (subtitleContent != null &amp;&amp; subtitleContent.content_ != null) {
                  for (int i = 0; i &lt; length; i++) {
                      SubtitleChunk subChunk1 = null;
                      SubtitleChunk subChunk2 = null;
                      try {
                          subChunk1 = subtitleContent.content_.get(i);
                          subChunk2 = subtitleContent.content_.get(i + 1);
  
                          long cTime = moviePlayer_.getCurrentTimeMillis();
                          if (cTime &gt; subChunk1.startTime &amp;&amp; (subChunk2 == null || cTime &lt; subChunk2.startTime)) {
                              currentSub = subChunk1.content;
                              currentChunk = subChunk1;
                              break;
                          }
                      } catch (Exception e) {
                          DebugUtil.printLogException(VIEW_LOG_TAG, e);
                          currentSub = "";
                      }
                  }
              } else {
                  currentSub = "";
              }
  
          } catch (InterruptedException e) {
              e.printStackTrace();
          } catch (Exception e) {
              e.printStackTrace();
          }
  
          new Handler(Looper.getMainLooper()).post(new Runnable() {
              public void run() {
                  if (moviePlayer_.isPlaying()) {
                      subtitleTextView.setText(Html.fromHtml(currentSub));
                  } else {
  
                  }
              }
          });
      }
  }
  </code></pre>
  
  <p>As you can see, I am running a loop on the ArrayList and comparing the time of the subtitles with the <code>moviePlayer_.getCurrentTimeMillis()</code> which I feel is too expensive. and subtitles are lagging and not in sync with the video.</p>
  
  <p>All above was the explaination of the issue. and Now the question.. How can I improve it? to get the Subtitle for a specific time in O(1) time. </p>
  
  <h1>EDITED</h1>
  
  <p>I went with Interval Trees, thats what I needed to put the subtitles in: I got it from here: <a href="https://github.com/phishman3579/java-algorithms-implementation" rel="nofollow">https://github.com/phishman3579/java-algorithms-implementation</a></p>