LongestCommonSubsequenceTest.php 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199
  1. <?php
  2. /*
  3. * This file is part of sebastian/diff.
  4. *
  5. * (c) Sebastian Bergmann <sebastian@phpunit.de>
  6. *
  7. * For the full copyright and license information, please view the LICENSE
  8. * file that was distributed with this source code.
  9. */
  10. namespace SebastianBergmann\Diff\LCS;
  11. use PHPUnit\Framework\TestCase;
  12. abstract class LongestCommonSubsequenceTest extends TestCase
  13. {
  14. /**
  15. * @var LongestCommonSubsequence
  16. */
  17. private $implementation;
  18. /**
  19. * @var string
  20. */
  21. private $memoryLimit;
  22. /**
  23. * @var int[]
  24. */
  25. private $stress_sizes = array(1, 2, 3, 100, 500, 1000, 2000);
  26. protected function setUp()
  27. {
  28. $this->memoryLimit = \ini_get('memory_limit');
  29. \ini_set('memory_limit', '256M');
  30. $this->implementation = $this->createImplementation();
  31. }
  32. /**
  33. * @return LongestCommonSubsequence
  34. */
  35. abstract protected function createImplementation();
  36. protected function tearDown()
  37. {
  38. \ini_set('memory_limit', $this->memoryLimit);
  39. }
  40. public function testBothEmpty()
  41. {
  42. $from = array();
  43. $to = array();
  44. $common = $this->implementation->calculate($from, $to);
  45. $this->assertEquals(array(), $common);
  46. }
  47. public function testIsStrictComparison()
  48. {
  49. $from = array(
  50. false, 0, 0.0, '', null, array(),
  51. true, 1, 1.0, 'foo', array('foo', 'bar'), array('foo' => 'bar')
  52. );
  53. $to = $from;
  54. $common = $this->implementation->calculate($from, $to);
  55. $this->assertEquals($from, $common);
  56. $to = array(
  57. false, false, false, false, false, false,
  58. true, true, true, true, true, true
  59. );
  60. $expected = array(
  61. false,
  62. true,
  63. );
  64. $common = $this->implementation->calculate($from, $to);
  65. $this->assertEquals($expected, $common);
  66. }
  67. public function testEqualSequences()
  68. {
  69. foreach ($this->stress_sizes as $size) {
  70. $range = \range(1, $size);
  71. $from = $range;
  72. $to = $range;
  73. $common = $this->implementation->calculate($from, $to);
  74. $this->assertEquals($range, $common);
  75. }
  76. }
  77. public function testDistinctSequences()
  78. {
  79. $from = array('A');
  80. $to = array('B');
  81. $common = $this->implementation->calculate($from, $to);
  82. $this->assertEquals(array(), $common);
  83. $from = array('A', 'B', 'C');
  84. $to = array('D', 'E', 'F');
  85. $common = $this->implementation->calculate($from, $to);
  86. $this->assertEquals(array(), $common);
  87. foreach ($this->stress_sizes as $size) {
  88. $from = \range(1, $size);
  89. $to = \range($size + 1, $size * 2);
  90. $common = $this->implementation->calculate($from, $to);
  91. $this->assertEquals(array(), $common);
  92. }
  93. }
  94. public function testCommonSubsequence()
  95. {
  96. $from = array('A', 'C', 'E', 'F', 'G');
  97. $to = array('A', 'B', 'D', 'E', 'H');
  98. $expected = array('A', 'E');
  99. $common = $this->implementation->calculate($from, $to);
  100. $this->assertEquals($expected, $common);
  101. $from = array('A', 'C', 'E', 'F', 'G');
  102. $to = array('B', 'C', 'D', 'E', 'F', 'H');
  103. $expected = array('C', 'E', 'F');
  104. $common = $this->implementation->calculate($from, $to);
  105. $this->assertEquals($expected, $common);
  106. foreach ($this->stress_sizes as $size) {
  107. $from = $size < 2 ? array(1) : \range(1, $size + 1, 2);
  108. $to = $size < 3 ? array(1) : \range(1, $size + 1, 3);
  109. $expected = $size < 6 ? array(1) : \range(1, $size + 1, 6);
  110. $common = $this->implementation->calculate($from, $to);
  111. $this->assertEquals($expected, $common);
  112. }
  113. }
  114. public function testSingleElementSubsequenceAtStart()
  115. {
  116. foreach ($this->stress_sizes as $size) {
  117. $from = \range(1, $size);
  118. $to = \array_slice($from, 0, 1);
  119. $common = $this->implementation->calculate($from, $to);
  120. $this->assertEquals($to, $common);
  121. }
  122. }
  123. public function testSingleElementSubsequenceAtMiddle()
  124. {
  125. foreach ($this->stress_sizes as $size) {
  126. $from = \range(1, $size);
  127. $to = \array_slice($from, (int) $size / 2, 1);
  128. $common = $this->implementation->calculate($from, $to);
  129. $this->assertEquals($to, $common);
  130. }
  131. }
  132. public function testSingleElementSubsequenceAtEnd()
  133. {
  134. foreach ($this->stress_sizes as $size) {
  135. $from = \range(1, $size);
  136. $to = \array_slice($from, $size - 1, 1);
  137. $common = $this->implementation->calculate($from, $to);
  138. $this->assertEquals($to, $common);
  139. }
  140. }
  141. public function testReversedSequences()
  142. {
  143. $from = array('A', 'B');
  144. $to = array('B', 'A');
  145. $expected = array('A');
  146. $common = $this->implementation->calculate($from, $to);
  147. $this->assertEquals($expected, $common);
  148. foreach ($this->stress_sizes as $size) {
  149. $from = \range(1, $size);
  150. $to = \array_reverse($from);
  151. $common = $this->implementation->calculate($from, $to);
  152. $this->assertEquals(array(1), $common);
  153. }
  154. }
  155. public function testStrictTypeCalculate()
  156. {
  157. $diff = $this->implementation->calculate(array('5'), array('05'));
  158. $this->assertInternalType('array', $diff);
  159. $this->assertCount(0, $diff);
  160. }
  161. }