LRU cache with Generic Circular doubly linked list C#

Question

I am new with using Generics and trying to implement a LRU cache using Generic Circular doubly linked list in C#. I am having couple of issues. Please help me out

1) In my LRUCache constructor am doing this

    head = new Node<T>(default(T), default(T)); 

which is not right, I want to initialize my head with some default keyvalue pair(-1,-1) data instead of Types default values.

2)In my get I am checking node is null based on the key and returning default(T). But I want to return null itself.

Here is my code

 public class Node<T>
{
    public KeyValuePair<T, T> KeyValue { get; set; }
    public Node<T> Next { get; set; }
    public Node<T> Previous { get; set; }
    public Node(T key, T value)
    {
        this.KeyValue = new KeyValuePair<T, T>(key, value);
        Next = null;
        Previous = null;
    }
}
public class LRUCache<T>
{
    private readonly int capacity;
    private int count;
    private readonly Node<T> head;
    private readonly Dictionary<T, Node<T>> myDictionary;
    public LRUCache(int capacity)
    {
        head = new Node<T>(default(T), default(T));
        head.Next = head;
        head.Previous = head;
        this.capacity = capacity;
        myDictionary = new Dictionary<T, Node<T>>();
    }
 public void set(T key, T value)
  {
   Node<T> node;
        myDictionary.TryGetValue(key, out node);
        if (node == null)
        {
            if (this.count == this.capacity)
            {
                // remove the last element
                myDictionary.Remove(head.Previous.KeyValue.Key);
                head.Previous = head.Previous.Previous;
                head.Previous.Next = head;
                count--;
            }
            // create new node and add to dictionary
            var newNode = new Node<T>(key, value);
            myDictionary[key] = newNode;
            this.InsertAfterTheHead(newNode);
            // increase count
            count++;
        }
        else
        {
            node.KeyValue = new KeyValuePair<T, T>(key, value);
            this.MoveToFirstElementAfterHead(node);
        }
  }
 public T get(T key)
 {
        Node<T> node;
        myDictionary.TryGetValue(key, out node);
        if (node == null)
        {
            return default(T);

        }
        this.MoveItToFirstElementAfterHead(node);
        return node.KeyValue.Value;
 }
}

Answer 1

Assuming that the value contained in the nodes are classes that contain a property that is used as the key, try this:

public abstract class Node<TNode, TNodeSupport, TKey, TValue>
    where TNode : Node<TNode, TNodeSupport, TKey, TValue>
    where TNodeSupport : Node<TNode, TNodeSupport, TKey, TValue>.BaseNodeSupport, new()
    where TValue : class
{
    protected static readonly TNodeSupport Support = new TNodeSupport();

    public KeyValuePair<TKey, TValue> KeyValue { get; set; }
    public TNode Next { get; set; }
    public TNode Previous { get; set; }
    protected Node(TValue value)
    {
        this.KeyValue = new KeyValuePair<TKey, TValue>(Support.GetKeyFromValue(value), value);
        Next = null;
        Previous = null;
    }

    public class LRUCache
    {
        private readonly int capacity;
        private int count;
        private readonly TNode head;
        private readonly Dictionary<TKey, TNode> myDictionary;
        public LRUCache(int capacity)
        {
            head = Support.CreateHeadNode();
            head.Next = head;
            head.Previous = head;
            this.capacity = capacity;
            myDictionary = new Dictionary<TKey, TNode>();
        }
        public void set(TValue value)
        {
           TKey key = Support.GetKeyFromValue(value);
           TNode node;
           myDictionary.TryGetValue(key, out node);
           if (node == null)
           {
              if (this.count == this.capacity)
              {
                    // remove the last element
                   myDictionary.Remove(head.Previous.KeyValue.Key);
                   head.Previous = head.Previous.Previous;
                   head.Previous.Next = head;
                   count--;
               }
               // create new node and add to dictionary
               var newNode = Support.CreateNodeFromValue(value);
               myDictionary[key] = newNode;
               this.InsertAfterTheHead(newNode);
               // increase count
               count++;
           }
           else
           {
               node.KeyValue = new KeyValuePair<TKey, TValue>(key, value);
                this.MoveToFirstElementAfterHead(node);
           }
        }
        public TValue get(TKey key)
        {
            TNode node;
            myDictionary.TryGetValue(key, out node);
            if (node == null)
            {
                return null;

            }
            this.MoveItToFirstElementAfterHead(node);
            return node.KeyValue.Value;
        }
    }

    public abstract class BaseNodeSupport
    {
        public abstract TKey GetKeyFromValue(TValue value);
        public abstract TNode CreateNodeFromValue(TValue value);
        public abstract TNode CreateHeadNode();
    }

}

Define your nodes and items like this:

public class Item
{
    public Guid Id;
    public String Data;
}
public class ItemNode : Node<ItemNode, ItemNode.Support, Guid, Item>
{
    public class NodeSupport : BaseNodeSupport
    {
        public override Guid GetKeyFromValue(Item value) { return value.Id; }
        public override ItemNode CreateNodeFromValue(Item value) {return new ItemNode(value)
        public override ItemNode CreateHeadNode() { return new ItemNode(new Item(){Id = Guid.Empty, Data = String.Empty}); }
    }
    public ItemNode(Item item) : base(item) {}
}

Use it like this:

public class Program
{
    static void Main()
    {
        var cache = new ItemNode.LRUCache(100);
    }
}

In this solution, Node is a class and a generic/parametric namespace that holds items sourced either from third party libraries or locally defined.

The TNodeSupport class is used as a singleton that provides three supporting functions used throughout the Node namespace. The first function accepts an item and returns the key from the item. The second function creates a TNode from a item. The third function creates default head nodes with a default empty item.

The LRUCache is contained within the Node generic namespace so that it can access the generic type parameters that it needs in order to function. The LRUCache logical implementation is mostly identical to the author's original implementation.

In the example of the defining a subclassed Node, ItemNode is a parameterized subclass/subnamespace. ItemNode specifies itself for the TNode parameter, ItemNode.NodeSupport for the TNodeSupport parameter, Guid for the TKey parameter and Item for the TValue parameter.

The Item class is a contrived class to contain some data along with an Id that will be used as the key to the item.

The Item.NodeSupport class derives from the Node.BaseNodeSupport class and overrides the three supporting functions. In the GetKeyFromValue method it returns the Id property of the Item instance provided. In the CreateNodeFromValue method it returns an ItemNode constructed with the Item instance provided. In the CreateHeadNode method it returns a new ItemNode constructed with a new Item containing a Guid.Empty for the Id and a String.Empty for the data.

In the Program class we instantiate an ItemNode.LRUCache to contain ItemNode instances that contain Items.