TimeEfficientImplementationTest.php

<?php
/*
 * This file is part of the Diff package.
 *
 * (c) Sebastian Bergmann <sebastian@phpunit.de>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace SebastianBergmann\Diff\LCS;

use PHPUnit_Framework_TestCase;

/**
 * Some of these tests are volontary stressfull, in order to give some approximative benchmark hints.
 */
class TimeEfficientImplementationTest extends PHPUnit_Framework_TestCase
{
    private $implementation;
    private $memory_limit;
    private $stress_sizes = array(1, 2, 3, 100, 500, 1000, 2000);

    protected function setUp()
    {
        $this->memory_limit = ini_get('memory_limit');
        ini_set('memory_limit', '256M');

        $this->implementation = new TimeEfficientImplementation;
    }

    protected function tearDown()
    {
        ini_set('memory_limit', $this->memory_limit);
    }

    public function testBothEmpty()
    {
        $from   = array();
        $to     = array();
        $common = $this->implementation->calculate($from, $to);

        $this->assertEquals(array(), $common);
    }

    public function testIsStrictComparison()
    {
        $from = array(
            false, 0, 0.0, '', null, array(),
            true, 1, 1.0, 'foo', array('foo', 'bar'), array('foo' => 'bar')
        );
        $to     = $from;
        $common = $this->implementation->calculate($from, $to);

        $this->assertEquals($from, $common);

        $to = array(
            false, false, false, false, false, false,
            true, true, true, true, true, true
        );
        $expected = array(
            false,
            true,
        );
        $common = $this->implementation->calculate($from, $to);

        $this->assertEquals($expected, $common);
    }

    public function testEqualSequences()
    {
        foreach ($this->stress_sizes as $size) {
            $range  = range(1, $size);
            $from   = $range;
            $to     = $range;
            $common = $this->implementation->calculate($from, $to);

            $this->assertEquals($range, $common);
        }
    }

    public function testDistinctSequences()
    {
        $from   = array('A');
        $to     = array('B');
        $common = $this->implementation->calculate($from, $to);
        $this->assertEquals(array(), $common);

        $from   = array('A', 'B', 'C');
        $to     = array('D', 'E', 'F');
        $common = $this->implementation->calculate($from, $to);
        $this->assertEquals(array(), $common);

        foreach ($this->stress_sizes as $size) {
            $from   = range(1, $size);
            $to     = range($size + 1, $size * 2);
            $common = $this->implementation->calculate($from, $to);
            $this->assertEquals(array(), $common);
        }
    }

    public function testCommonSubsequence()
    {
        $from     = array('A',      'C',      'E', 'F', 'G');
        $to       = array('A', 'B',      'D', 'E',           'H');
        $expected = array('A',                'E');
        $common   = $this->implementation->calculate($from, $to);
        $this->assertEquals($expected, $common);

        $from     = array('A',      'C',      'E', 'F', 'G');
        $to       = array('B', 'C', 'D', 'E', 'F',      'H');
        $expected = array('C',                'E', 'F');
        $common   = $this->implementation->calculate($from, $to);
        $this->assertEquals($expected, $common);

        foreach ($this->stress_sizes as $size) {
            $from     = $size < 2 ? array(1) : range(1, $size + 1, 2);
            $to       = $size < 3 ? array(1) : range(1, $size + 1, 3);
            $expected = $size < 6 ? array(1) : range(1, $size + 1, 6);
            $common   = $this->implementation->calculate($from, $to);

            $this->assertEquals($expected, $common);
        }
    }

    public function testSingleElementSubsequenceAtStart()
    {
        foreach ($this->stress_sizes as $size) {
            $from   = range(1, $size);
            $to     = array_slice($from, 0, 1);
            $common = $this->implementation->calculate($from, $to);

            $this->assertEquals($to, $common);
        }
    }

    public function testSingleElementSubsequenceAtMiddle()
    {
        foreach ($this->stress_sizes as $size) {
            $from   = range(1, $size);
            $to     = array_slice($from, (int) $size / 2, 1);
            $common = $this->implementation->calculate($from, $to);

            $this->assertEquals($to, $common);
        }
    }

    public function testSingleElementSubsequenceAtEnd()
    {
        foreach ($this->stress_sizes as $size) {
            $from   = range(1, $size);
            $to     = array_slice($from, $size - 1, 1);
            $common = $this->implementation->calculate($from, $to);

            $this->assertEquals($to, $common);
        }
    }

    public function testReversedSequences()
    {
        $from     = array('A', 'B');
        $to       = array('B', 'A');
        $expected = array('A');
        $common   = $this->implementation->calculate($from, $to);
        $this->assertEquals($expected, $common);

        foreach ($this->stress_sizes as $size) {
            $from   = range(1, $size);
            $to     = array_reverse($from);
            $common = $this->implementation->calculate($from, $to);

            $this->assertEquals(array(1), $common);
        }
    }
}