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

Related tags

Laravel lists php algorithm algorithms datastructures php7 maps cracking-the-coding-interview gayle-laakmann-mcdowell
Overview

PHPAlgorithms

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

You can find the package on Packagist: https://packagist.org/packages/doganoo/php-algorithms

Why Using PHPAlgorithms?

"Algorithms + Data Structures = Programs"

Algorithms are a part of the basic toolkit for solving problems. Data Structures organize data in an efficient way. The combination of both allow the creation of smart and efficient software.

Installation

You can install the package via composer:

composer require doganoo/php-algorithms

Usage

Here's an Binary Tree example:

use doganoo\PHPAlgorithms\Datastructure\Graph\Tree\BinaryTree;

$binaryTree = new BinaryTree();
$binaryTree->insertValue(50);
$binaryTree->insertValue(25);
$binaryTree->insertValue(75);
$binaryTree->insertValue(10);
$binaryTree->insertValue(100);

echo json_encode($binaryTree);

produces

{"nodes":{"value":50,"left":{"value":25,"left":{"value":10,"left":null,"right":null},"right":null},"right":{"value":75,"left":null,"right":{"value":100,"left":null,"right":null}}}}

Contributions

Feel free to send a pull request to add more algorithms and data structures. Please make sure that you read https://github.com/doganoo/PHPAlgorithms/wiki/Best-Practices before opening a PR. Please also consider https://github.com/doganoo/PHPAlgorithms/blob/master/CONTRIBUTING.md.

Maintainer/Creator

Doğan Uçar (@doganoo)

License

MIT

Comments
  • unit-test to catch a TimSort issue

    unit-test to catch a TimSort issue

    Description

    This is a failing test to prove TimSort is badly implemented.

    Motivation and Context

    Current implementation of TimSort works for arrays up to 32 items only.

    How Has This Been Tested?

    I've just generated a list of 42 numbers, from 1 to 42, shuffled it and sorted it with TimSort. The result should equal the initial sorted array.

    opened by duzun 4
  • Migrate from plural to singular names in namespaces

    Migrate from plural to singular names in namespaces

    Description

    Renamed following namespaces:

    • doganoo\PHPAlgorithms\Datastructure\Lists\{ArrayLists => ArrayList}\ArrayList
    • doganoo\PHPAlgorithms\Datastructure\Lists\{ArrayLists => ArrayList}\StringBuilder
    • doganoo\PHPAlgorithms\Datastructure\Lists\{LinkedLists => LinkedList}\DoublyLinkedList
    • doganoo\PHPAlgorithms\Datastructure\Lists\{LinkedLists => LinkedList}\SinglyLinkedList
    • doganoo\PHPAlgorithms\Datastructure\{Maps => Map}\HashMap
    • doganoo\PHPAlgorithms\Datastructure\{Maps => Map}\IntegerVector
    • doganoo\PHPAlgorithms\Datastructure\{Maps => Map}\Map
    • doganoo\PHPAlgorithms\Datastructure\{Sets => Set}\HashSet
    • doganoo\PHPAlgorithms\{Maps => Map}\HashMapTest
    • doganoo\PHPAlgorithms\{Maps => Map}\NodeTest
    • doganoo\PHPAlgorithms\{Sets => Set}\HashSetTest

    Related Issue

    #6

    Motivation and Context

    #6

    NB! Following namespace left in plural names:

    • doganoo\PHPAlgorithms\Datastructure\Lists
    • doganoo\PHPAlgorithms\Common\Abstracts
    • doganoo\PHPAlgorithms\Common\Interfaces

    These namespaces cannot be renamed to singular form, because list, abstract and interface are reserved words in PHP

    How Has This Been Tested?

    By running PHPUnit tests

    $ phpunit
PHPUnit 6.5.0 by Sebastian Bergmann and contributors.

.....S...........S............................................... 65 / 94 ( 69%)
.............................                                     94 / 94 (100%)
    opened by krlv 4
  • Bucket Sort implementation

    Bucket Sort implementation

    Description

    Bucket Sort implementation.

    Related Issue

    Motivation and Context

    How Has This Been Tested?

    Tests are done similarly to the existing tests for sorting algorithms.

    Screenshots (if appropriate):

    opened by tuqqu 3
  • Use $size instead of counting on each iteration in QuickSort

    Use $size instead of counting on each iteration in QuickSort

    Description

    Use $size instead of counting on each iteration in QuickSort

    Related Issue

    Motivation and Context

    How Has This Been Tested?

    Screenshots (if appropriate):

    opened by berezuev 2
  • Improved single character permutation in stringPermutations

    Improved single character permutation in stringPermutations

    Strings with a single permutation would call Permutation.permute due to wrong comparison in Permutation.stringPermutations.

    Description

    Due to a wrong comparison in Permutation.php#L54, a call to private function private was issued when single character permutations were required.

    This PR fixes the comparison, which is of course just a minor improvement on an edge case.

    Related Issue

    Closes #9

    Motivation and Context

    It fixes a minor edge case, adding negligible performance gain.

    How Has This Been Tested?

    Added additional test cases.

    opened by flavioheleno 1
  • Wrong comparison expression in String Permutations

    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.

    opened by flavioheleno 1
  • make sure that all class methods accept interfaces instead of class implementations

    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

    bug enhancement good first issue 
    opened by doganoo 1
  • fix subList slicing

    fix subList slicing

    Description

    fixing a bug where sublisting an array list does not return all elements

    Related Issue

    https://github.com/doganoo/PHPAlgorithms/issues/8

    Motivation and Context

    • bugfix
    • release 1.0.0

    How Has This Been Tested?

    • unit tests
    opened by doganoo 0
  • add strict_types

    add strict_types

    Description

    adds strict_types to each file

    Related Issue

    https://github.com/doganoo/PHPAlgorithms/issues/13

    Motivation and Context

    • 1.0.0 release

    How Has This Been Tested?

    • unit tests
    opened by doganoo 0
  • remove deprecated code

    remove deprecated code

    Description

    removing deprecated code

    Related Issue

    https://github.com/doganoo/PHPAlgorithms/issues/7

    Motivation and Context

    • 1.0.0 milestone

    How Has This Been Tested?

    • unit tests are green
    opened by doganoo 0
  • return spl_object_hash for object keys

    return spl_object_hash for object keys

    Description

    Fixing an exception that occurs when trying to serialize an PDO object while using it as an HashTable key

    Related Issue

    https://github.com/doganoo/PHPAlgorithms/issues/4

    Motivation and Context

    • bug fixing
    • 1.0.0 milestone

    How Has This Been Tested?

    • no test, since there must be an integration test for PDO objects which does not exists yet
    opened by doganoo 0
  • Implement Consistent HashTable

    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.

    opened by doganoo 0
  • Broken TimSort class

    Broken TimSort class

    Describe the bug According to https://github.com/doganoo/PHPAlgorithms/pull/22, the TimSort sorting algorithm is broken under certain circumstances.

    To Reproduce Check the PR code which tests broken code

    opened by doganoo 0
  • implement RedBlackTree

    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)

    opened by doganoo 0
  • implement AVLTree

    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

    enhancement 
    opened by doganoo 0
Releases(2.1.0)
Owner
Doğan Can Uçar
Software Developer and hobby photographer.
Doğan Can Uçar
GitHub
A PHP package that provides common Data and Value Objects, that are Laravel castable.

Common Casts A PHP package that provides common Data and Value Objects, that are Laravel castable. Installation composer require juststeveking/common-

Steve McDougall 2 Sep 21, 2022
Laravel Common Password Validator

laravel-common-password-validator Laravel Common Password Validator An optimized and secure validator to check if a given password is too common. By d

WedgeHR 1 Nov 6, 2021
Blacksmith is a code generation tool which automates the creation of common files that you'd typically create for each entity in your application.

Blacksmith is a code generation tool which automates the creation of common files that you'd typically create for each entity in your application.

Indatus 197 Dec 30, 2022
Tasty TADS 3 recipes for solving common and uncommon problems.

TADS 3 Cookbook Tasty TADS 3 recipes for solving common and uncommon problems when writing interactive fiction. There are two aspects of the TADS 3 Co

Jim Nelson 9 Apr 17, 2022
Foreman is a Laravel scaffolding application that automates common tasks you typically perform with each new Laravel app you create

Foreman is a Laravel scaffolding application that automates common tasks you typically perform with each new Laravel app you create. The directives you want Forman to perform are outlined in a JSON based template file.

Indatus 145 Apr 13, 2022
A package to filter laravel model based on query params or retrieved model collection

Laravel Filterable A package to filter laravel model based on query params or retrived model collection. Installation Require/Install the package usin

Touhidur Rahman 17 Jan 20, 2022
PHP components - collection of cross-project PHP classes

PHP components Collection of cross-project PHP classes. Install: $ composer require ansas/php-component Ansas\Component\Convert\ConvertPrice Convert "

null 1 Jan 5, 2022
A collection of useful traits for working with PHP 8.1 Enums

A library of helper traits for working with PHP 8.1 enums This package provides a series of traits that allows you to: RestorableFromName Trait Create

Mark Baker 24 Nov 24, 2022
Collection of agnostic PHP Functions and helpers with zero dependencies to use as foundation in packages and other project

Collection of agnostic PHP Functions and helpers This package provides a lot of very usefull agnostic helpers to use as foundation in packages and oth

padosoft 54 Sep 21, 2022
A set of useful Laravel collection macros

A set of useful Laravel collection macros This repository contains some useful collection macros. Spatie is a webdesign agency based in Antwerp, Belgi

Spatie 1.5k Dec 31, 2022
Collection of the Laravel/Eloquent Model classes that allows you to get data directly from a Magento 2 database.

Laragento LAravel MAgento Micro services Magento 2 has legacy code based on abandoned Zend Framework 1 with really ugly ORM on top of outdated Zend_DB

Egor Shitikov 87 Nov 26, 2022
A collection of helper functions that I use across my projects.

A collection of helper functions that I use across my projects. This package includes some of the helper functions that I tend to use in all of my pro

Ryan Chandler 33 Oct 18, 2022
A collection of generators for Lumen and Laravel 5.

Lumen generators A collection of generators for Lumen and Laravel 5. Contents Why ? Installation Quick Usage Detailed Usage Model Generator Migration

Amine Ben hammou 349 Mar 24, 2022
Base library for repeated layout fields, content builders and other collection components

laravel-flexible-content This package's only purpose is to build custom repeated layout components, such as Laravel Nova's Flexible Content field or y

Whitecube 5 May 31, 2022
A collection of extensions for Laravel development in Visual Studio Code

Laravel Extension Pack for Visual Studio Code Includes the basic extensions to get started with Laravel development in Visual Studio Code. Laravel Ext

Winnie Lin 24 Dec 25, 2022
Collection of classes you can use to standardize data formats in your Laravel application.

Laravel Formatters This package is a collection of classes you can use to standardize data formats in your Laravel application. It uses the Service Co

Michael Rubel 88 Dec 23, 2022
A collection of classes to be extended/used in laravel apps for quick development

laraquick A collection of classes to be extended/used in laravel applications for quick development. Introduction The library contains traits with wel

Ezra Obiwale 35 Dec 13, 2022
Collection of scripts, thoughts about CSP (Content Security Policy)

CSP useful, a collection of scripts, thoughts about CSP I'm testing and using CSP (Content Security Policy), and here are some thoughts, resources, sc

Nicolas Hoffmann 417 Jan 3, 2023
Collection of Google Maps API Web Services for Laravel

Collection of Google Maps API Web Services for Laravel Provides convenient way of setting up and making requests to Maps API from Laravel application.

Alexander Pechkarev 467 Jan 5, 2023