Swift Generics – Cache

Generics are awesome. In fact, they are insanely cool when it comes to writing reusable code. To demonstrate their usefulness, let’s build a generic Cache storage.

Our cache should meet the following requirements:

  • Should be fast (read, write) – O(1)
  • Support hashable data type (NSData, UIImage, String, Int, etc)
  • Support custom size to allow for initialization based on memory limitations
  • Should keep track and clear out oldest objects before adding new ones
  • Should keep recently accessed data by marking it as the most recent

Before writing code, let’s talk about implementation. For starters, I will use a dictionary to store the actual data. Reason behind using a dictionary (or a hash table) should be rather obvious… both the lookup and insertion of data takes constant time. This will be especially useful when dealing with large cache size.

I will also use a second data structure – NSMutableOrderedSet as a queue – to keep track of the oldest data. The lookup and insertion of data is similar to the one of a dictionary. The issue with using a standard Set, is that sets are unordered collections… there is no way to guarantee the order of elements – well, unless we use NSMutableOrderedSet – Objective-C Foundation to the rescue.

By using Dictionary and NSMutableOrderedSet we can write a very efficient implementation of our cache.

Let’s begin by declaring a new generic class called Cache.

The above declaration simply states that our cache could be instantiated using any object thats hashable. Let’s also add a few properties to store the data and transactions.

The database will contain the actual data.

The size variable will be used to keep our database from growing out of control.

Also, if you look closely, you’ll notice both the database and the transactions initialized with capacity – this is just an optimization thing (if you know how arrays implemented, for example, this will make sense).

Next, let’s implement the write function.

The above function does a few things. First of all, it checks to see if our database is full by checking transactions log count. If the count is less then specified size of our cache, we are simply adding data to our database as well as appending key to the transaction log. Both operations will take constant time – very efficient.

If the database if full, I am getting first element (key) from the transactions set which can be used to lookup an object in the dictionary and remove that object from our database. Logic afterwards is straight forward, I am using recursion to add the new data to the database.

Let’s implement the read function.

We are first checking to see if our database contains object for specified key. If it does, we check transactions for specified key as well – and since lookup time in a Set is O(1), both the data and transaction log lookup will take constant time to complete. If the transaction is found, we are simply “moving” it to the bottom of the transactions log, making it the most recent.

Feel free to implement a print() function and test the functionality:

Test code:

This implementation is very simple yet effective. It satisfies our requirements and most of all is very efficient. It is implemented using Generics which means it will work on any hashable type – really nice.

Swift Generics – Cache