php-set-data-structure

A PHP implementation of a Java-like Set data structure.

A set is simply a group of unique things that can be iterated by the order they were inserted. So, a significant characteristic of any set is that it does not contain duplicates.

Implementation is based on the MDN JS Reference for Sets in EMCA 6 JavaScript.

Sets require a min PHP version of 7.4.

Installation
Basic usage:
Set Iteration
Set operations
Set family operations
- Family Union
- Family Intersection

Installation

You can download the latest release via the releases link on this page.

PHP-Sets is available via Composer by running the following command:

composer require jakewhiteley/php-sets

then include the library in your project like so:

include('vendor/autoload.php');

use PhpSets\Set;

Basic Usage

Creating a Set

When you create a set, you can insert initial values or keep it empty.

$set = new Set(1, 2, 3);
$emptySet = new Set();

Sets cannot contain duplicate values, and values are stored in insertion order.

// $set contains [1, 2, 3] as duplicates are not stored
$set = new Set(1, 2, 1, 3, 2);

If you have an array of elements, you can either pass in the array directly, or splat the array.

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

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

Adding values

Values of any type (Including Objects, arrays, and other Sets) are added to a set via the add() method.

It is worth noting that uniqueness is on a strict type basis, so (string) '1' !== (int) 1 !== (float) 1.0. This also is true for Objects within the set and an object with a classA is not equal to an object with classB, even if the properties etc are the same.

// create empty Set
$set = new Set(); 

$set->add('a');
// $set => ['a']

$set->add(1);
// $set => ['a', 1]

As Sets implements the ArrayAccess interface, you can also add values as you would with a standard Array.

$set = new Set();

$set[] = 1;
$set[] = 'foo';
// $set => [1, 'foo']


// You can also replace values by key, provided the new value is unique within the Set
$set[0] = 2;
// $set => [2, 'foo']

// If a key is not currently in the array, the value is appended to maintain insertion order
$set[4] = 'foo';
// $newSet => [2, 'foo', 'foo']

Removing values

Values can be removed individually via delete(), or all at once via the clear() method.

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

$set->delete(2);
// $set => [1, 3]

$set->clear();
// $set => []

You can also delete methods via ArrayAccess:

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

unset($set[0]);
// $set => [2, 3]

Testing if a value is present

You can easily test if a Set contains a value via the has($value) method.

As with the other methods, this is a strict type test.

$set = new Set('a', [1, 2], 1.0);

$set->has('a');      // true
$set->has([1, 2]);   // true
$set->has(1);        // false
$set->has([1, '2']); // false
$set->has('foo');    // false

Counting items

This is done using the count method:

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

echo $set->count(); // 3

Iteration

There are many ways to iterate a Set:

Like a traditional PHP array
Using entries() to return an instance of PHP's ArrayIterator
Using each() and a provided callback function
Using values() which returns a traditional PHP Array version of the Set

As a traditional Array

The Set object extends an ArrayObject, and can be iterated like a normal array:

$set = new Set(1, 2);

foreach ($set as $val) {
    print($val);
}

Or if you want, you can iterate $set->values() instead.

Using `entries()`

The entries() method returns an ArrayIterator object.

$iterator = $set->entries();

while ($iterator->valid()) {
    echo $iterator->current();
    $iterator->next();
}

Using `each($callback, ...$args)`

You can also iterate a Set via a provided callable method.

The callback is called with the current item as parameter 1, with any additional specified params passed after.

function cb($item, $parameter) {
  echo $item * $parameter;
}

$set = new Set(1, 2);

$set->each('cb', 10);
// prints 10 20

Set operations

Union

Appends a second Set onto a given Set without creating duplicates:

$a = new Set(1, 2, 3);
$b = new Set(2, 3, 4);

$merged = $a->union($b);

print_r($merged->values()); // [1, 2, 3, 4]

Difference

The difference() method will return a new Set containing values present in the original Set but not present in another.

This is also known as the relative complement.

$a = new Set(1, 2, 3, 4);
$b = new Set(3, 4, 5, 6);

print_r($a->difference($b)->values()); // [1, 2]
print_r($b->difference($a)->values()); // [5, 6]

Symmetric Difference

The symmetricDifference() method also returns a new Set but differs to the difference method in that it will return all uncommon values between both Sets.

$a = new Set(1, 2, 3, 4);
$b = new Set(3, 4, 5, 6);

print_r($a->symmetricDifference($b)->values()); // [1, 2, 5, 6]

Intersect

Returns a new Set containing the items common (present in both) between two sets:

$a = new Set(1, 2, 3);
$b = new Set(2, 3, 4);

$intersect = $a->intersect($b);

print_r($intersect->values()); // [2, 3]

Subsets

The isSupersetOf method returns a bool indicating if a given Set is a subset of the current Set.

The order of values does not matter, but a subset must only contain items present in the original Set:

$a = new Set(1, 2, 3);
$b = new Set(2, 3);

var_Dump($b->isSupersetOf($a)); // true
var_Dump($a->isSupersetOf($b)); // false

Set family operations

If we have a collection of sets, for example { { 1,2,3 }, { 3,4,5 } , { 3, 5, 6, 7 } }, often called a family of sets in Set Theory, we can take the union and intersection of the family. That is, ( { 1, 2, 3 } union { 3, 4, 5 } ) union { 3, 5, 6, 7 } and likewise for intersection. In Set Theory a large union and intersection symbol is used for this purpose.

Note that, at present, these operations are implemented naively by iteratively calling the union and intersect methods above. More efficient implementations are possible and welcome.

Union of a Family of Sets

At present the family of sets needs to be in an array of Set objects:

$set1 = Set(1, 2, 3);
$set2 = Set(3, 4, 5);
$set2 = Set(5, 1, 6);

$set_union = Set::familyUnion([$set1, $set2]); // [1, 2, 3, 4, 5, 6]

Intersection of a Family of Sets

As with familyUnion, the family of sets needs to be in an array of Set objects:

$set1 = Set(1,2,3);
$set2 = Set(3,4,5);
$set_family = [ $set1, $set2 ];
$set_intersection = Set::familyIntersection($set_family);

Note that, contrary to Set Theory, the result of taking the intersection of an empty array results in an empty array. (In Set Theory the intersection of an empty family is undefined as it would be the 'set of all sets'.)

Contributing

Contributions and changes welcome! Just open an issue or submit a PR 💪

jakewhiteley/php-sets