Improve Flash MPEG-4 AVC Seeking With Binary Search

/**
 * Copyright 2007-2008 (c) , Brooks Andrus
 * 
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 * 
 */
package com.brooksandrus.utils
{
    public class BinarySearch
    {
        private var _upperBounds:int;
        private var _lowerBounds:int;
 
        public function BinarySearch()
        {
 
        }
 
        /**
         * Recursively scans through an array of seekpoints to find a requested time. 
         * If the value is found within the array of seekpoints the index at which 
         * the value is found is returned. If an exact match is not found, -1 is returned 
         * and the the upper and lower indices between which the value falls are set 
         * (so you can determine the closest indice, or seek to to the nearest indexed 
         * time behind or forward in the array of seekpoints.
         * 
         * Seekpoints array must be sorted.
         * 
         * @param value  the requested seek time to find
         * @param range the array of seekpoints collected from an MPEG-4 AVC NetStream metadata event
         * @param the low index within the range we'd like to scan
         * @param the high index within the range we'd like to scan
         * 
         */
        public function search( value:Number, range:Array, low:int, high:int ):int
        {
            if ( high == low )
            {
                if ( range[high].time == value )
                {
                    _lowerBounds = low;
                    return value
                }
                else
                {
                    _lowerBounds = low - 1;
                    return -1;
                }
            }
 
            var median:int = ( low + high ) / 2;
 
            if ( range[median].time > value )
            {
                _upperBounds = median;
                return search( value, range, low, median );
            }
            else if ( range[median].time < value )
            {
                _lowerBounds = median + 1;
                return search( value, range, median + 1, high );
            }
            else
            {
                _upperBounds = median;
                _lowerBounds = median;
                return median;
            }
        }
 
        public function get lowerBounds():int
        {
            return _lowerBounds;
        }
 
        public function get upperBounds():int
        {
            return _upperBounds;
        }
    }
}

5 Responses to “ “Improve Flash MPEG-4 AVC Seeking With Binary Search”

1. Zohar Babin says:

   November 21, 2008 at 7:34 am

   nice work,

   though I don’t get why use recursive (which is known to be expensive in flash) instead of just looping through the Array.

   by the way, in Kaltura we created a similar implementation for enhancing the seek experience for progressive download streams in the flv. Seeking was wired if you seek between keyframes where you’ll wait for the “not always working” invalid seek time. When you seek exactly to a kayframe the response is better and the event shows the right time.
2. Brooks says:

   November 22, 2008 at 7:50 pm

   @ Zohar – I felt like the recursive method was a bit more readable and there wasn’t any noticeable performance hit. That said its a piece of cake to implement binary search via a loop rather than recursively. Here’s an example:

   /**
    * Loops through an array of seekpoints to find a requested time. 
    * If the value is found within the array of seekpoints the index at which 
    * the value is found is returned. If an exact match is not found, -1 is returned 
    * and the the upper and lower indices between which the value falls are set 
    * (so you can determine the closest indice, or seek to to the nearest indexed 
    * time behind or forward in the array of seekpoints.
    * 
    * Seekpoints array must be sorted.
    * 
    * @param value  the requested seek time to find
    * @param range the array of seekpoints collected from an MPEG-4 AVC NetStream metadata event
    * @param the low index within the range we'd like to scan
    * @param the high index within the range we'd like to scan
    * 
    */
   public function search( value:Number, range:Array, low:int, high:int ):int
   {
       var val:int = -1;
       var time:Number;
       while ( low < = time  )
       {
          var median:int = ( low + high ) / 2;
          time = range[median].time;
          if ( value > time  )
          {
             low = median + 1;
          }
          else if ( value < time  )
          {
             high = median - 1;
          }
          else // found a match
          {
             low = median;
             high = median;
             val = median;
             break;
          }
      }
      _upperBounds = low;
      _lowerBounds = high;
      return val; // failed to find value. Look at the upper / lower bounds
   }
3. Zohar Babin says:

   November 23, 2008 at 10:43 am

   :) maybe a personal preference, but it looks much cleaner.
   running recursive calls is more heavy due to the need of keeping the stack and calling the function. I don’t if it’s still apply, in earlier versions of flash the recursion was also limited (though for binary search you shouldn’t reach this limit anyway).
4. Tom Sirgedas says:

   December 8, 2008 at 11:35 am

   Your -1 return value for an exact match bugs me. Just return the greatest index whose value doesn’t exceed “value”. If you really want to check for an exact match, the caller can do that easily.

   Here’s my implementation:

   // x         -- the value to find
   // arr       -- sorted array of Numbers
   // [lo, hi)  -- the range of indices to search, lo is inclusive, hi is exclusive
   //              so [5, 10) means consider 5,6,7,8,9
   //
   // The return value is the largest arr index whose value does not exceed x.
   // e.g.  binarySearch_( 33.3, [0,10,20,30,40,50], 0, 6 ) returns 3
   // e.g.  binarySearch_( 30.0, [0,10,20,30,40,50], 0, 6 ) returns 3
   // e.g.  binarySearch_( 90  , [0,10,20,30,40,50], 0, 6 ) returns 5
   // e.g.  binarySearch_( 0   , [0,10,20,30,40,50], 0, 6 ) returns 0
   // e.g.  binarySearch_( -90 , [0,10,20,30,40,50], 0, 6 ) returns -1
   function binarySearch_( x:Number, arr:Array, lo:Number, hi:Number ) : Number
   {
   	if ( hi - lo < = 1 )
   	      return x < arr[lo] || hi - lo < 1 ? -1 : lo;
   	var mid:Number = Math.floor((lo+hi)/2);
   	return x< arr[mid] ? binarySearch_( x, arr, lo, mid )
   	                   : binarySearch_( x, arr, mid, hi );
   }
    
   // wrapper
   function binarySearch( x:Number, arr:Array ) : Number
   {
   	return binarySearch_( x, arr, 0, arr.length );
   }
    
   trace( binarySearch( 33.3 , [0,10,20,30,40,50] ) ); // 3
   trace( binarySearch( 30.0 , [0,10,20,30,40,50] ) ); // 3
   trace( binarySearch( 90   , [0,10,20,30,40,50] ) ); // 5
   trace( binarySearch( 0    , [0,10,20,30,40,50] ) ); // 0
   trace( binarySearch( -90  , [0,10,20,30,40,50] ) ); // -1
   stop();
5. Flex and Flash Developer – Jesse Warden dot Kizz-ohm » Blog Archive » Wish List for Flash Player 11 says:

   August 8, 2009 at 11:29 pm

   [...] I have many video projects where NetStream breaks, and I need to fix it. Â Additionally, I have many cool video scrubbing, pausing, and DVD like controls I’d like to [...]