I have a data structure, containing time span nodes, with the following properties:

  • Nodes are sorted ascending
  • Time spans will not overlap, but may have gaps between them
  • Each node will have a start datetime and a finish datetime
  • The last node's finish may also be null (not finished yet)

I want to be able to find the node that intersects a given datetime, or return false if no match is found — basically resembling the following sql query for a sql table with similar properties as my data structure:

SELECT t.*
FROM table t
WHERE t.start <= @probeDate AND
    ( t.finish >= @probeDate OR
      t.finish IS NULL )

I've concluded that a (variation of a) binary search is probably the most efficient search algorithm. So, this is what I have come up with so far:

<?php
class Node
{
    protected $start;
    protected $finish;

    public function __construct( DateTime $start, DateTime $finish = null )
    {
        $this->start  = $start;
        $this->finish = $finish;
    }

    public function getStart()
    {
        return $this->start;
    }

    public function getFinish()
    {
        return $this->finish;
    }

    public function __toString()
    {
        /* for easy displaying of the timespan */
        return $this->start->format( 'H:i:s' ) . ' - ' . ( null !== $this->finish ? $this->finish->format( 'H:i:s' ) : '∞' );
    }
}

class NodeList
{
    protected $nodes;

    public function __construct( array $nodes = array() )
    {
        $this->nodes = $nodes;
    }

    public function find( DateTime $date )
    {
        $min = 0;
        $max = count( $this->nodes ) - 1;

        return $this->binarySearch( $date, $min, $max );
    }

    protected function binarySearch( $date, $min, $max )
    {
        if( $max < $min )
        {
            return false;
        }
        else
        {
            $mid = floor( $min + ( ( $max - $min ) / 2 ) );    
            $node   = $this->nodes[ $mid ];
            $start  = $node->getStart();
            $finish = $node->getFinish();
            if( $date < $start )
            {
                return $this->binarySearch( $date, $min, $mid - 1 );
            }
            else if( $date > $finish )
            {
                if( $finish == null )
                {
                    return $node;
                }
                else
                {
                    return $this->binarySearch( $date, $mid + 1, $max );
                }
            }
            else
            {
                return $node;
            }
        }
    }
}

I am testing it with the following:

$nodes = array(
    new Node( new DateTime( '01:01:00' ), new DateTime( '01:05:00' ) ),
    new Node( new DateTime( '01:06:00' ), new DateTime( '01:10:00' ) ),
    new Node( new DateTime( '01:11:00' ), new DateTime( '01:15:00' ) ),
    new Node( new DateTime( '01:16:00' ), new DateTime( '01:20:00' ) ),
    new Node( new DateTime( '01:21:00' ), new DateTime( '01:25:00' ) ),
    new Node( new DateTime( '01:26:00' ), new DateTime( '01:30:00' ) ),
    new Node( new DateTime( '01:31:00' ), new DateTime( '01:35:00' ) ),
    new Node( new DateTime( '01:36:00' ), new DateTime( '01:40:00' ) ),
    new Node( new DateTime( '01:41:00' ) )
);

$list = new NodeList( $nodes );

$date = new DateTime( '01:00:00' );
for( $i = 0; $i < 100; $i++, $date->modify( '+30 seconds' ) )
{
    $node = $list->find( $date );
    echo 'find: ' . $date->format( 'H:i:s' ) . PHP_EOL;
    echo ( $node !== false ? (string) $node : 'false' ) . PHP_EOL . PHP_EOL;
}

Do you see any inherent flaws and/or ways to improve this algorithm? Perhaps you even know of a more time efficient algorithm to accomplish the same?

PS.: Don't worry about the internal integrity of NodeList and Node (checking for invalid nodes, invalid min and max datetimes, checking overlaps, etc.) — this is just a quick and dirty concept. I'm primarily interested in the search algorithm in NodeList::find() and consequently NodeList::binarySearch().

  • You will probably get better luck with algorithms on either SO or Programmers.SO. This site is more geared towards code review, not algorithm review. I wish I could help more, but I was absolutely terrible when I took algorithms. Best of luck – mseancole Dec 26 '12 at 14:52

Flatter code is less arrow-shaped

In cases like this:

if( $max < $min )
{
    return false;
}
else
{
    // more deeply nested conditions ...
}

When the if branch ends with a return statement, you can eliminate the else branch, making the code flatter and less arrow-shaped, which often makes it easier to read:

if( $max < $min )
{
    return false;
}

// more code ...

Fishy comparison

Although this is apparently valid PHP, comparing a date against a null value using the > operator seems like a dirty hack:

else if( $date > $finish )
{
    if( $finish == null )

I would reorganize the conditions in that piece of code:

if( $max < $min )
{
    return false;
}

$mid = floor( $min + ( ( $max - $min ) / 2 ) );    
$node   = $this->nodes[ $mid ];
$start  = $node->getStart();
$finish = $node->getFinish();

if( $date < $start )
{
    return $this->binarySearch( $date, $min, $mid - 1 );
}

if( $finish == null )
{
    return $node;
}

if( $date > $finish )
{
    return $this->binarySearch( $date, $mid + 1, $max );
}

return $node;

Minor optimization

The find method recalculates the size of $this->nodes, even though it cannot change after construction. It would be better to calculate the size once, at construction time.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.