For many programming languages and software packages, data structures such as linked lists and maps, and sorting algorithms like quicksort, are things that come built-in.

In terms of performance and working on higher levels, these built-in packages are a really good idea. In the case of languages like PHP, they are likely faster or better optimized than anything you could write in the language itself due to the internal being written in C.

However, when you want to look under the hood and understand a bit more what you’ve been learning in that Algorithms & Data Structures? class, programming your own data structures can be both fun and satisfying.

So that’s exactly what I ended up doing: Writing my own implementation of popular data structures and sorting algorithms in, oddly enough, PHP.

PHP is like a sweet spot between Java and JavaScript. You get an interpreted language without strict typing, but with the added benefit of OOP features like Interfaces and Traits.

The project structure is simple: a bunch of classes neatly organized into namespaces according to the concept they represent, interfaces (for future expandability), and many unit tests to back everything up.

Code quality

Working on this project also reassured me the importance of testing your code, but also of avoiding to repeating your self:

For this project I had decided to try a cool-looking site, CodeClimate, which promised to provide automated code review. Given that this is just a personal experiment and that their service is free for public repositories, I decided to give it a try.

After a few commits, their website pointed out the obvious: many of my unit tests had duplicated code. This led to think about ways of combining logic in unit tests, which is not something I have attempted to do before.

Having setup a namespace for tests, which can be properly defined in Composer using the require-dev key, really helped in getting this done.

After identifying common logic and some refactoring, I had some abstract tests and inheritance setup, which removed most of the warnings on Code Climate, and made it simpler to write new similar tests.

Complexity

Linked lists, Quicksort, Stacks, Insertion sort were all very simple and straightforward to implement, possibly thanks to the fact that they have been mentioned on many lectures back in school.

However, out of all the data structures I’ve worked on (at least at the time of writing), HashMap was the most complicated one.

I attribute this to the fact that a simple implementation of HashMaps require the use of another data structure to handle collisions and has to be able to grow and shrink depending on the load factor.

Unit testing, again, provided to be very useful since it allowed me to be sure that the HashMap class was working as I expected.

Using my testing approach, I was unable to directly test that the growing and shrinking of the HashMap’s internal array was happening correctly. Given that these are internal operations of the data structure, there are no public methods for querying the status or altering its behavior, and adding methods just for the sake of code coverage seemed wrong, almost like cheating.

So the current tests mainly tries to simulate a real-world scenario in which the HashMap has to expand and contract multiple times, while making assurances that it still works and hasn’t lost data.

Looking ahead

So far this has been an interesting exercise, and I plan to keep adding more data structures/sorting algorithms in the future just to keep my coding skills sharp.

You can take a look at the code or fork it and play with it on GitHub: https://github.com/etcinit/structures

Examples

Here are some usage examples:

use Chromabits\Structures\Map\HashMap;

$map = new HashMap();

$map->set('hello', 'world');

$map->has('hello');
>> true

$map->get('hello');
>> 'hello'

$map->toArray();
>> ['hello' => 'world']

Basic quicksort algorithm comparing strings:

use Chromabits\Sorting\Quicksort\QuicksortSorter;
use Chromabits\Sorting\Comparators\StringComparator;

$sorter = new QuicksortSorter(new StringComparator());

$sorter->sort(['z', 'g', 'c', 'a']);
>> ['a', 'c', 'g', 'z']

Introduction

I’ve been using Laravel 5 for a few months now. One of the main changes in the new framework is the extesive use of dependency injection on classes and controllers.

Many packages made for Laravel 4 have two main incompatibilities on Laravel 5:

• Version 4.x.x is hardcoded in the composer.json file
• Most services are available as Facades, instead of using DI (which won’t prevent your from suing the library but it does defeat the purpose of DI)

Dependency injection is much nicer since PHP IDEs are able to perform autocompletion and type hinting.

Porting Purifier to Laravel 5

A package that I use frequently on Laravel 4 projects is the HTMLPurifier Service Provider, which simplifies setup for using the PHP HTMLPurifier library.

HTMLPurifier allows you to clean input before it is store or displayed on your application. Though it also has a few nice tricks like converting lines into <p>...</p> elements or only allowing certain tags and attributes.

The problem: this library hasn’t been updated in a while and it’s not possible to use it on Laravel 5 due to the composer.json issue.

So I decided to rewrite parts of it and port it into Laravel 5

WARNING: Laravel 5 is still under active development. This library or the framework itself might stop working at any point. I’ll try to keep it updated.

Once you get the library setup on your project, using the purfifier is as simple as defining the depency on oyur class constructor and using the clean method:

// ...
$cleanInput = $this->purifier->clean($dirtyInput);

Setting it up on your project

Step 1: Add Composer dependency

The first step is to add the dependency on your project’s composer.json:

{
  "require": {
    "laravel/framework": "5.0.*",
    "chromabits/purifier": "dev-master"
  },
  "minimum-stability": "dev"
}

and run composer update.

Alternatively, you can run: composer require chromabits/purifier dev-master

Step 2: Use service provider

Then, load the service into your application by adding into your config/app.php:

return [
	// ...
	'providers' => [
		// ...
		'Chromabits\Purifier\PurifierServiceProvider'
	]
];

Step 3: Use within a controller

Using the service in your controller or class can be done by requiring the “Contract” (aka interface) on the constructor:

<?php

namespace Http\Controllers;

use Chromabits\Purifier\Constracts\Purifier;
use HTMLPurifier_Config;
use Illuminate\Http\Request;

/**
 * Class IndexController
 *
 * @package App\Http\Controllers;
 */
class IndexController {
    /**
     * @var Purifier
     */
    protected $purifier;

    /**
     * Construct an instance of MyClass
     *
     * @param Purifier $purifier
     */
    public function __construct(Purifier $purifier) {
        // Inject dependencies
        $this->purifier = $purifier;
    }

    /**
     * Get index page
     *
     * @param Request $request
     */
    public function getIndex(Request $request)
    {
        return $this->purifier->clean($request->input('first_name'));
    }
}

Source Code

The source code is available on GitHub and the package is available on Packagist

Here’s a little mixin I’ve been using on React.js for interacting with the Mousetrap library (a library for handling keyboard shortcuts on the browser). It automatically unbinds shortcuts once the component unmounts and provides some convenience methods for avoiding interacting with Mousetrap directly on m components.

NOTE: The following code is formatted for Browserify. You might need to make some changes for using it without Browserify

To use it, require the module and add the mixing to your component:

// ...
var MoustrapMixin = require('/path/to/MoustrapMixin.jsx');

MyComponent = React.createClass({
    // ...
    mixins: [MoustrapMixin],

    componentDidMount: function () {
        this.bindShortcut('esc', function () { // Handle shortcut });
    }
    // ...
});

MoustrapMixin.jsx: