Skip to content

Commit d1e7df0

Browse files
m3m0r7m3m0r7
committed
Add quick sort algorithm
1 parent 299f4b5 commit d1e7df0

9 files changed

Lines changed: 161 additions & 9 deletions

File tree

‎src/Kernel/Mnemonics/_areturn.php‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,6 @@ final class _areturn implements OperationInterface
1111

1212
public function execute()
1313
{
14-
return new \PHPJava\Imitation\java\lang\_String((string) $this->popFromOperandStack());
14+
return $this->popFromOperandStack();
1515
}
1616
}

‎src/Kernel/Mnemonics/_if_icmple.php‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@ public function execute(): void
1717
$rightOperand = Extractor::realValue($this->popFromOperandStack());
1818
$leftOperand = Extractor::realValue($this->popFromOperandStack());
1919

20-
if ($leftOperand < $rightOperand) {
20+
if ($leftOperand <= $rightOperand) {
2121
$this->setOffset($this->getProgramCounter() + $offset);
2222
}
2323
}

‎src/Kernel/Types/_Array/Collection.php‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33

44
use PHPJava\Exceptions\TypeException;
55
use PHPJava\Kernel\Types\Type;
6+
use PHPJava\Utilities\Extractor;
67
use PHPJava\Utilities\TypeResolver;
78

89
class Collection implements \ArrayAccess
@@ -19,7 +20,9 @@ public function getType($default = null): ?string
1920
if (!isset($this->data[0])) {
2021
return $default;
2122
}
22-
return TypeResolver::resolveFromPHPType($this->data[0]) ?? $default;
23+
return TypeResolver::resolveFromPHPType(
24+
Extractor::realValue($this->data[0])
25+
) ?? $default;
2326
}
2427

2528
public function toArray()

‎src/Utilities/TypeResolver.php‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -93,7 +93,7 @@ public static function resolveFromPHPType($value)
9393
if ($type === 'L') {
9494
return substr(static::PHP_TYPE_MAP[$type], 1);
9595
}
96-
return static::SIGNATURE_MAP[$type];
96+
return static::SIGNATURE_MAP[$type] ?? null;
9797
}
9898

9999
/**

‎tests/QuickSortTest.php‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
<?php
2+
namespace PHPJava\Tests;
3+
4+
use PHPJava\Core\JavaArchive;
5+
use PHPUnit\Framework\TestCase;
6+
7+
class QuickSortTest extends Base
8+
{
9+
protected $fixtures = [
10+
'QuickSortTest',
11+
];
12+
13+
public function testQuickSortAsc()
14+
{
15+
ob_start();
16+
$calculatedValue = $this->initiatedJavaClasses['QuickSortTest']
17+
->getInvoker()
18+
->getStatic()
19+
->getMethods()
20+
->call(
21+
'asc',
22+
[-14, 5, 111, 44, 2, 9999, 99, 123, 1, -10, 33, -50]
23+
);
24+
$result = ob_get_clean();
25+
$this->assertEquals(
26+
file_get_contents(__DIR__ . '/templates/QuickSortAsc.txt'),
27+
$result
28+
);
29+
}
30+
31+
public function testQuickSortDesc()
32+
{
33+
ob_start();
34+
$calculatedValue = $this->initiatedJavaClasses['QuickSortTest']
35+
->getInvoker()
36+
->getStatic()
37+
->getMethods()
38+
->call(
39+
'desc',
40+
[-14, 5, 111, 44, 2, 9999, 99, 123, 1, -10, 33, -50]
41+
);
42+
$result = ob_get_clean();
43+
$this->assertEquals(
44+
file_get_contents(__DIR__ . '/templates/QuickSortDesc.txt'),
45+
$result
46+
);
47+
}
48+
}

‎tests/fixtures/java/InsertionSortTest.java‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ public static void asc()
55
int[] array = {-14, 5, 111, 44, 2, 9999, 99, 123, 1, -10, 33, -50};
66
for(int i = 1; i < array.length; i++){
77
int j = i;
8-
while(j >= 1 && array[j-1] > array[j]){
8+
while(j >= 1 && array[j-1] > array[j]) {
99
int tmp = array[j];
1010
array[j] = array[j - 1];
1111
array[j - 1] = tmp;
@@ -25,7 +25,7 @@ public static void desc()
2525
int[] array = {-14, 5, 111, 44, 2, 9999, 99, 123, 1, -10, 33, -50};
2626
for(int i = 1; i < array.length; i++){
2727
int j = i;
28-
while(j >= 1 && array[j - 1] < array[j]){
28+
while(j >= 1 && array[j - 1] < array[j]) {
2929
int tmp = array[j];
3030
array[j] = array[j - 1];
3131
array[j - 1] = tmp;
@@ -41,9 +41,9 @@ public static void desc()
4141

4242
public static void ascByParam(int[] array)
4343
{
44-
for(int i = 1; i < array.length; i++){
44+
for(int i = 1; i < array.length; i++) {
4545
int j = i;
46-
while(j >= 1 && array[j - 1] > array[j]){
46+
while(j >= 1 && array[j - 1] > array[j]) {
4747
int tmp = array[j];
4848
array[j] = array[j - 1];
4949
array[j - 1] = tmp;
@@ -62,7 +62,7 @@ public static void descByParam(int[] array)
6262
{
6363
for(int i = 1; i < array.length; i++){
6464
int j = i;
65-
while(j >= 1 && array[j - 1] < array[j]){
65+
while(j >= 1 && array[j - 1] < array[j]) {
6666
int tmp = array[j];
6767
array[j] = array[j - 1];
6868
array[j - 1] = tmp;

‎tests/fixtures/java/QuickSortTest.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
class QuickSortTest
2+
{
3+
4+
public static void asc(int[] array)
5+
{
6+
array = ascQuickSort(array, 0, array.length - 1);
7+
for (int i = 0; i < array.length; i++) {
8+
System.out.println(array[i]);
9+
}
10+
}
11+
12+
public static void desc(int[] array)
13+
{
14+
array = descQuickSort(array, 0, array.length - 1);
15+
for (int i = 0; i < array.length; i++) {
16+
System.out.println(array[i]);
17+
}
18+
}
19+
20+
public static int[] ascQuickSort(int[] array, int left, int right)
21+
{
22+
int tmp;
23+
if (left < right) {
24+
int i = left;
25+
int j = right;
26+
int pivot = array[i + (j - i) / 2];
27+
while (true) {
28+
while (array[i] < pivot) {
29+
i++;
30+
}
31+
while (pivot < array[j]) {
32+
j--;
33+
}
34+
if (i >= j) {
35+
break;
36+
}
37+
tmp = array[i];
38+
array[i] = array[j];
39+
array[j] = tmp;
40+
i++;
41+
j--;
42+
}
43+
ascQuickSort(array, left, i - 1);
44+
ascQuickSort(array, j + 1, right);
45+
}
46+
return array;
47+
}
48+
49+
public static int[] descQuickSort(int[] array, int left, int right)
50+
{
51+
int tmp;
52+
if (left < right) {
53+
int i = left;
54+
int j = right;
55+
int pivot = array[i + (j - i) / 2];
56+
while (true) {
57+
while (array[i] > pivot) {
58+
i++;
59+
}
60+
while (pivot > array[j]) {
61+
j--;
62+
}
63+
if (i >= j) {
64+
break;
65+
}
66+
tmp = array[i];
67+
array[i] = array[j];
68+
array[j] = tmp;
69+
i++;
70+
j--;
71+
}
72+
descQuickSort(array, left, i - 1);
73+
descQuickSort(array, j + 1, right);
74+
}
75+
return array;
76+
}
77+
}

‎tests/templates/QuickSortAsc.txt‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
-50
2+
-14
3+
-10
4+
1
5+
2
6+
5
7+
33
8+
44
9+
99
10+
111
11+
123
12+
9999

‎tests/templates/QuickSortDesc.txt‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
9999
2+
123
3+
111
4+
99
5+
44
6+
33
7+
5
8+
2
9+
1
10+
-10
11+
-14
12+
-50

0 commit comments

Comments
 (0)