Implementing the Set Data Structure in PHP

Unlike Javascript,
PHP does not have a native Set object built in. So let us implement one!

What are Set objects good for

In short: a Set is a data structure which only holds unique values. They can be mixed types (language depending), but all are unique and only values are present, no keys.
Good use cases for sets include;

1. A list of usernames.
2. Filtering out unique values in a data set (eg. all locations from a csv)

The interface

The interface for a set object looks like;

interface SetInterface
{
    public function has($item);

    public function add($item);

    public function delete($item);

    public function clear();
    
    public function values();
}

The API

The API for this data structure will look like;

$set = new Set([1, 2, 'three', 'four'])
echo $set->has('three'); // true
echo $set->has('FIVE'); // false
$set-put('FIVE');
echo $set->has('FIVE'); // true

$set-put('FIVE');
$set-put('FIVE');
$set-put('FIVE');
$set-put('FIVE');

foreach($set as $item) {
    // do something with $item
}

// OR export the unique values into an array
// notice that we pushed 'FIVE' four times,
// but it only appears once

$set->values(); // [1, 2, 'three', 'four', 'FIVE']

The Code

<?php

class Set implements \ArrayAccess, SetInterface {

    public $length;
    protected $data;
    protected $stub = 1; // this is used as the value in the assoc array, we are disinterested in this

    public function __construct(Array $arr) {
        $this->length = count($arr);
        foreach ($arr as $item) {
            // We are using a pointer to save on memory
            $this->data[$item] = &$this->stub;
        }
    }

    public function has($item) {
        return isset($this->data[$item]);
    }

    public function add($item) {
        $this->data[$item] = &$this->stub;
        $this->length = count($this->data);
    }

    public function delete($item) {
        unset($this->data[$item]);
        $this->length = count($this->data);
    }

    public function clear() {
        $this->data = [];
        $this->length = 0;
    }

    public function values() {
        return array_keys($this->data);
    }

    public function offsetSet($offset, $value) {
        if (is_null($offset)) {
            $this->data[] = $value;
        } else {
            $this->data[$offset] = $value;
        }
    }

    public function offsetExists($offset) {
        return isset($this->data[$offset]);
    }

    public function offsetUnset($offset) {
        unset($this->data[$offset]);
    }

    public function offsetGet($offset) {
        return isset($this->data[$offset]) ? $this->data[$offset] : null;
    }
}

A note on ArrayAccess

Implementing the ArrayAccess interface allows us to loop around our object as though it were an array, and can come in pretty handy.

$set = new Set([1,2,3,4]);

foreach($set as $item) {
    // do something with $item
}