Phabstractic: Set Data Type

I am proud to announce the addition of a set data type to the asherwunk/phabstractic project.

Set Data Type

A set data type can be summed up by Wikipedia:

In computer science, a set is an abstract data type that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.

In many respects I have tried to implement the most useful parts of the Set data type description by Wikipedia.  Not all methods listed in the article are necessarily available in this implementation.

As well, it is possible to store multiple copies of the same value in the Set data type given the correct configuration (see below) making it a ‘multi-set’:

A generalization of the notion of a set is that of a multiset or bag, which is similar to a set but allows repeated (“equal”) values (duplicates). (Wikipedia)

Basic Sets (Variable Type)

The core of the Set data type is the data private property.  All the following methods act on this data.  This is implemented in PHP as a simple array.  However, rather than just add set elements using $this->data[] = ...;  the Set data type implements the Identity Trait Feature which assigns a unique handle to any added element.  This handle is then assigned as the key in the $data property array.  The handle is returned by the Phabstractic\Data\Type\Set::add[Reference](...)  method call, allowing direct reference from outside the class.  Although it is not encouraged to keep track of exact indices in a Set data type, this comes in handy when there are duplicate values and you want to remove only one of them.  Following are the abridged class definition, constructor, and adding methods:

Notice in Phabstractic\Data\Types\Set::checkUniqueValues()  that we don’t use ArrayUtilities, but array_unique() .  Future versions may incorporate ArrayUtilities::elementComparison() .  We also only call the uniqueness check if the option ‘unique’ is set.  You won’t get a Phabstractic\Data\Types\Exception\RangeException  on a pre-existing element value unless ‘unique’ is set.

Mutable Capabilities of the Set

In addition to Phabstractic\Data\Types\Set::add()  and Phabstractic\Data\Types\Set::addReference() , which make the sets mutable to begin with, there are other methods for altering the set as it stands:

Note how ->add and ->addReference return an identifier?  See above:

However, rather than just add set elements using  $this->data[] = ...;  the Set data type implements the Identity Trait Feature which assigns a unique handle to any added element.

This is very important when it comes to Phabstractic\Data\Types\Set::removeByIdentifier($identity) .  When you add a value to a set you get back a unique identifier that points to that element in that set object.  This is handy if say, you add a duplicate element and then want to get rid of that element.  That’s where Phabstractic\Data\Types\Set::removeByIdentifier($identity)  comes in.  As you can see in this Unit Test (github), here’s what it would look like in implementation:

 

Set Operations

If you have a set, it’s likely that you’ll want to do some basic operations with it.  Basic operations for sets, as say in set theory, include such things as a union, an intersection, and a difference.  Other mathematical/algorithmic things you might want to do is map, filter, or reduce.  The Set abstract data type has support for all of these things.  You can find more about core Set operations on wikipedia.

Union, Intersection, and Difference

All operations for our sets are defined in static methods declared on the Set data type class.  Below is the code for the union operation, intersection operation, and difference operation. What’s nice about these operations is that they are variadic functions, and operate on a mixture of arrays, scalars, and Phabstractic\Data\Types\Resource\SetInterface ‘s.

You’ll notice of course that the standard measure of comparison between elements in the set has been standardized in the latest version of Set to use Phabstractic\Resource\ArrayUtilities::elementComparison() , a move I hope to continue when revising the other abstract data types as I move forward.  Refer to it’s own blog post, Array Utilities, for more information.

Map, Fold, Filter, and Walk

Sometimes you just want to do some functional programming on your Sets, you know what I mean?  Mapping will apply a function to each element, Folding will reduce a Sets elements, Filter will return only qualifying elements, and Walking is like Mapping and Folding at the same time.  For more information on these additional Set operators, take a gander at Wikipedia.  Well, we have you covered:

I know, I had to do a lot of heavy lifting there… right? Did you see?  Right.

Individual Set Operations and Comparisons (Subsets)

Sets themselves have operations that are specific to their own instances.  Here’s a rundown:

There is one VERY handy static element that compares two given sets.  I didn’t include it in the core Set operations I outlined earlier because I tend to think of this type of operation as acting on specific individual sets.  Here is that code:

NOTE: As of this writing subset doesn’t support or use Phabstractic\Resource\ArrayUtilities::elementComparison() , as the above operations do.  This may change in the future.

Static Instantiation

Want a set in a real jiffy?  Just build one!

Build-A-Bear, Build-A-Set, a gift for your math lover.

Conclusion

Sets are very important mathematical constructions, and enable the computation of many other abstract data types.  A set can have singularly exclusive values, or can have multiples of the same value in them.  Sets can be compared using algebraic operators, and can exist as subsets of other sets.  Set abstract data types can hold references as the data of an element, enabling some interesting behavior.

Thanks for reading!

View on GitHub

This is part of the Phabstractic Library.

If you appreciate my programming please help support me through my Patreon.

photo credit: Television Set at European Parliament via photopin (license)

Liked it? Take a second to support kadar on Patreon!

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

1 Response

  1. March 14, 2017

    […] handles the implementation of the tags and categories as Sets (see the asherwunk/phabstractic abstract data type Sets post).  As well, it handles all the non-implementation specific property setting and getting that we […]

Leave a Reply

%d bloggers like this: