Phabstractic: Self-Sorting List Data Type

asherwunk/phabstractic now has lists that sort themselves according to a given user method

Self-Sorting Lists

I’ve written previously about the Restricted List data type.  Self-Sorting Lists inherit from Restricted Lists so that the list can be sure that it only holds values that are comparable using the comparison function.  First, let’s review the structure of a list in the phabstractic library.  Every list implements the ListInterface (github):

We add and remove elements onto the list using  ->push()  and  ->pop() , and we index into the list using  ->index()  and  ->indexReference() .  In our implementation we’re going to have more methods than this, in fact, we inherit from AbstractList (github):

For this particular list implementation, it doesn’t really matter if we’re a Stack or a Queue, since we just worry about everything being in order.  Self-sorting lists actually inherit from AbstractRestrictedList in order to ensure proper data types are stored and compared (github):

Remember that these implemented abstract methods are meant to be called using parent:: to check certain values, but the actual addition of the data to the list should be done in the implementation.

The thing about a self-sorting list is that you’d expect to sort the list every time someone adds something to the list, however, though that makes sense intuitively it doesn’t make as much sense practically.  What happens if something outside the list edits the data in the list?  This can happen if we allow the data in the list to be set using a reference, which we do.  So if we change the value of a referenced piece of data in the list we might be out of order.  There’s no way to monitor the contents of the list variables so that it updates on a change, that would be odd.

The solution?  Sort the list every time it is requested and make sure you can only request the list through the object (thus ensuring the sorting code can be done).

As well, a self-sorting list has to have some way that it knows how to put things in order.  As well, just because a list has restrictions, doesn’t mean that the list may only have one data type in it.  We’ve demonstrated in the past that a restrictions can specify multiple classes or data types.

What makes this class really useful is that you can specify the method by which things are sorted.  You do this by implementing the compare function in the implementation of the class.  We set all this up, the automatic sorting, and the placeholder for the sorting code in AbstractSortedList (github):

Much like the Restricted List abstract class (above) most of these methods that are implemented in the abstract class are meant to be called through parent::  Note that these methods are for ‘getting’ the list, not when someone puts things on the list, otherwise we’d also call parent:: to access the RestrictedList functionality.

Lexicographic List

An example self-sorting list is the Lexicographic List.  The idea behind a lexicographic list is that it is a list of strings sorted lexicographically (as PHP puts it).  Pretty much, this means, that they are sorted alphabetically.  The comparison function is very simple:

Essentially it is a wrapper around the built-in PHP comparison for strings.  We can rest assure that they’re all strings because of the constructor:

Note here that we do allow other types to be substituted in.  This works as long as the type of data substituted in can be compared using the built-in PHP comparison functions as above.

One thing we MUST note about an implementation such as LexicographicList is that if we do implement \ArrayAccess we MUST include the sorting functionality manually:

You can see the entire LexicographicList on github if you want to see the full implementation.

Usage

AbstractSortedList is meant to be implemented, and can’t actually be instantiated on its own.  A simple and straight-forward implementation is LexicographicList as shown above.  To use the LexicographicList you simply use it like any other list:

But here’s where things get a little tricky, when we retrieve the list it’s different than how we started:

You’ll note that three comes before two.  This is because ‘three’ comes before the word ‘two’ alphabetically.  But what happens if we retrieve a reference and then change the data?  Turns out, because we sort by request, that doesn’t matter:

Conclusion

Self-sorting lists can be very handy.  For instance, we could easily implement a priority queue by utilizing a sorted list, and that’s something we’re going to do, simply using the comparison method on competing priorities.  PriorityQueue’s are usually implemented with a heap and a binary tree and so on, but I thought it would be easier to implement using a self-sorting array.  Self-sorting arrays make putting everything in order in a messaging queue fairly simple.

This is part of the Phabstractic Library.

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

photo credit: Day 092/366 – To Do List via photopin (license)

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...

Leave a Reply

%d bloggers like this: