Friendly IT Consultant with 8+ years experience
Various notes and resources regarding how to encapsulate functions in C# (ex. for passing algorithms as function parameters).
In particular, this collection provides resources for allowing any alternative replacement algorithm to be implemented by the client and used by the cache in the "n-way set-associative cache" coding challenge.
To solve the coding challenge mentioned for this collection, either a Delegate or an Interface can be used to define an algorithm. This is useful to allow the user to specify a custom replacement algorithm as a single parameter in the Cache constructor, but it is important to understand what these are and how they work before implementing your own.
Explains what an interface is, how it is useful, and what it is used for in C#.
Explains what a delegate is and how to use it in C#.
Both can be used for similar situations, and this link lists the main differences between the two.
Gives a good overview of "inheritance" - what it is, when it should be used, and how to use it. One of the few video tutorials that I found to go over the "interface", "abstract", and "virtual" keywords in C# (including what these are and how to use them).
Note: this tutorial is geared towards programming games in the Unity game engine, and classes such as "MonoBehaviour" are Unity-specific and not important for you to know about for this coding challenge.
When working with interfaces or delegates, where custom code can be provided and executed as a named function, it is useful to know about different types of data sets available to you.
ArrayList, Stack, Queue, and LinkedList are all subclasses of "Collections" in C# - this video gives a good overview of some of these data types, and when/how to use each.
This is the "LinkedList" data type in C#, which effectively supports being used as both a Stack and a Queue. This video explains the concept with some helpful diagrams and good explanations.
Note: code examples are in Java, and basically show how you can create your own doubly linked list. In C#, we can use the "LinkedList" data type, and don't have to implement any of this code ourselves.
"Provide a way for any alternative replacement algorithm to be implemented by the client and used by the cache."
As with almost any problem, the first step is to break it down into smaller sub-problems:
1) How can a replacement algorithm be represented?
2) How can the user specify their own replacement algorithm?
3) How can the cache use this replacement algorithm?
To solve this problem, we first need some way to pass a function (or set of functions) as a parameter. In C#, there are two main ways to do this: delegates and interfaces.
A delegate is the "direct" way to pass a function, although if you want to pass multiple functions together in a single group it is generally better to define an interface which contains all of the methods that will be needed.
Using interfaces, the user can pass an instance of an implementation of the interface (which you have defined) as as the parameter for the custom replacement algorithm. Your interface would have certain methods specified, which the custom implementation would have to specify the actual code for.
Now, with regards to your current code, I mentioned during our last call that having two separate data structures to deal with MRU and LRU makes creating a solution for requirement #5 a bit more difficult. That is because if you had a single LinkedList (for example) that you used for both LRU and MRU, you could then have this same LinkedList be used for the custom replacement algorithm too.
Or, as another way to think of it, imagine if we had a 6th requirement to allow a user to switch from LRU to MRU after a cache is created and populated with values - right now, you would have to create a "switch" function to copy values to/from the stack/queue, whereas with a single data structure holding the cache for either algorithm this wouldn't be necessary.
However, you don't necessarily have to change your MRU and LRU code before implementing #5!
As one option, you could just do something like "if MRU then A, else if LRU then B, else C", where "C" is a function that works for custom algorithms.
Or, to use the more "object-oriented" approach, you can take advantage of the fact that Stack, Queue, and LinkedList are all subclasses of "Collection" in C#. That is, using either delegates or interfaces, you can define functions for the replacement algorithm that accept a "Collection" type parameter.
Choosing this "object-oriented" option, you can then adapt your existing LRU and MRU functions to pass in the corresponding stack/queue to this function, such that LRU, MRU, and custom algorithms will all work with the same interface/delegate solution that you create.
Explains what "Dependency Injection" is, and when you should use it.
Note: uses Java for examples, but a good overview regardless.
Wondering how the actual code looks to pass a custom replacement algorithm to a function in C# (where this algorithm is represented by a user-defined implementation of an interface)? If so, the code examples shown in this tutorial are a good reference to get started!