Embedded Development in a Language You've Never Heard Of.

Implementing a HashSet in Brightscript

An associative array in brightscript (roAssociativeArray) is a data structure than can function as a map, dictionary, or hash table – each element is a key and is mapped to an associated value. An array in brightscript is equally as versatile – it can function as an array, stack or queue without having to either be instantiated as, or remain, a single type of data structure.

In one of the channels I work with, we are using the same API that their website uses, so I am forced to work around designs that were not set up to facilitate Roku needs. In this channel, users can purchase whole movies, or purchase just a single scene from that movie. When loading the movie item page, the channel needs to know if the user owns that movie, or if the user owns any of that movie’s scenes, in order to show the correct option set for that episode (play or purchase). In the API, this information is returned as a comma separated string of episode id numbers when we load the movie content metadata.

To correctly indicate whether the user owns a scene from it’s parent movie, the id number for that scene must be checked against the comma separated list of id numbers in the initial data call. When a user is on the movie page, and selects the “view scenes” option, we must check each item against this list, giving us a nested loop with a runtime of \(O(n^2)\), which is not very desirable, especially in low performing roku models where poor runtime values can induce a lag in lists populating.

The solution to this in any modern language you’re used to is a hashset, which has a read time of \(O(c)\), so looping through this list and performing a lookup on each item gives a runtime of \(O(n)\), which for larger lists is significantly better than \(O(n^2)\). The problem is that brightscript does not have an implementation of a hashset, only the dictionary-style roAssociativeArray mentioned above, so I wrote a wrapper for the roAssociativeArray to function as a classic hashset that only relies on the keys of that object, not the key-value pairs as they were designed.

The new hashset functionality is implemented by creating an instance of the hashset, passing in the string of id numbers, passing in the delimiter used in the string, and then for each item when the page loads, simply calling the HashSet_Contains(id) function to do a lookup on it to see if the id is in the hashset of purchased scenes. We can now run this check against very large lists of scenes and not induce screen loading lag or screen flicker on slower Roku models.

The code can be viewed on my github here.

Next Post

Previous Post

Leave a Reply

© 2020

Theme by Anders Norén