doganoo/phpalgorithms

A collection of common algorithms implemented in PHP. The collection is based on "Cracking the Coding Interview" by Gayle Laakmann McDowell

phpalgorithms's Issues

implement BinaryTree

Is your feature request related to a problem? Please describe.
BinaryTree extends actually BinarySearchTree. Needs to be implemented

remove deprecated code

PDOException when trying to serialize an instance of PDO in MapUtil

Expected Behavior

creating an index for HashMap class

Current Behavior

throws an PDOException with message: You cannot serialize or unserialize PDO instances

Possible Solution

??

Steps to Reproduce

1. create HashMap / HashSet instance
2. add class that is/has instance of PDO

add declare(strict_types=1) to each file and test

As PHPAlgorithms should be type safe, we should add strict_types declaration to each file. Doing this, we need to ensure that current functionality is still given (method calls, unit tests).

It would also be glad to create unit tests for each file that does not have a test, but not a must-have yet.

subList() in ArrayList does not work as expected

The subList() method in ArrayList class does not work as expected. When slicing an array list at an index, the slicing should happen from 0 to index and from index+1 to the end.

Expected Behavior

slice properly

Current Behavior

slices at a wrong index

Possible Solution

Steps to Reproduce

$anyList = new ArrayList();
$anyList->add(1);
$anyList->add(2);
$anyList->add(3);
$anyList->add(4);
$anyList->add(5);

$upperList = $anyList->subList(0, $index);
$lowerList = $anyList->subList($index+1, $anyList->length());

$list = new ArrayList();
$list->addAll($upperList);
$list->add($value);
$list->addAll($lowerList);

print_r($list);

Possible Implementation

not tested, but in subList() method:

$array = \array_slice($this->array, $start, $end - $start -1, true);

Wrong comparison expression in String Permutations

There is a wrong comparison in Permutation.php#L54, requiring a call to permutation for single character string permutations.

Expected Behavior

Single character string permutations should return early in Permutation.stringPermutations.

Current Behavior

Single character string permutations require a call to permutation, adding a minor overhead to Permutation.stringPermutations.

Possible Solution

Replace (1 === $string) with (1 === $strLen).

Steps to Reproduce

1. Disable the private function Permutation.permute
2. Run the code below

use doganoo\PHPAlgorithms\Algorithm\Various\Permutation;

$permutation  = new Permutation();
$permutations = $permutation->stringPermutations("a");

Context (Environment)

I was reviewing the code out of curiosity and found the issue.

migrate from plural to singular names in namespaces

Expected Behavior

singular names in namespaces

Current Behavior

mixed names

implement AVLTree

Is your feature request related to a problem? Please describe.
There is https://github.com/doganoo/PHPAlgorithms/blob/master/src/Datastructure/Graph/Tree/AVLTree/Node.php and https://github.com/doganoo/PHPAlgorithms/blob/master/src/Datastructure/Graph/Tree/AVLTree.php which are not implemented fully yet (buggy).

Describe the solution you'd like
implement AVLTree and write tests

implement RedBlackTree

Is your feature request related to a problem? Please describe.
There is https://github.com/doganoo/PHPAlgorithms/blob/master/src/Datastructure/Graph/Tree/AVLTree.php and https://github.com/doganoo/PHPAlgorithms/blob/master/src/Datastructure/Graph/Tree/RedBlackTree/Node.php which are not fully implemented yet (buggy).

Describe the solution you'd like
Implement and test (unit test)

Broken TimSort class

Describe the bug
According to #22, the TimSort sorting algorithm is broken under certain circumstances.

To Reproduce
Check the PR code which tests broken code

extend tests

add new unit tests and extend to cover all cases

make sure that all class methods accept interfaces instead of class implementations

Expected Behavior

all class methods should accept interfaces instead of classes

Current Behavior

some classes accept implementations

Possible Solution

reviewing the whole code

Implement Consistent HashTable

Is your feature request related to a problem? Please describe.
ConsistentHashTable is not implemented yet.

Describe the solution you'd like
Implement a consistent HashTable. Have a look here: https://medium.com/system-design-blog/consistent-hashing-b9134c8a9062#:~:text=Consistent%20Hashing%20is%20a%20distributed,without%20affecting%20the%20overall%20system.