LeastRecentlyUsedCache.cs

// <copyright file="LeastRecentlyUsedCache.cs" company="http://www.sinbadsoft.com">
// Copyright (c) Chaker Nakhli 2013
// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the
// License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by
// applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language
// governing permissions and limitations under the License. 
// </copyright>
// <author>Chaker Nakhli</author>
// <email>Chaker.Nakhli@sinbadsoft.com</email>
// <date>2013/09/24</date>
using System;
using System.Collections.Generic;

public class LeastRecentlyUsedCache<TKey, TValue>
{
    private readonly Dictionary<TKey, Node> entries;
    private readonly int capacity;
    private Node head;
    private Node tail;        

    private class Node
    {
        public Node Next { get; set; }
        public Node Previous { get; set; }
        public TKey Key { get; set; }
        public TValue Value { get; set; }
    }

    public int Count { get { return entries.Count; } }

    public LeastRecentlyUsedCache(int capacity = 16)
    {
        if (capacity <= 0) 
            throw new ArgumentOutOfRangeException(
                "capacity", 
                "Capacity should be greater than zero");
        this.capacity = capacity;
        entries = new Dictionary<TKey, Node>();
        head = null;
    }

    public void Set(TKey key, TValue value)
    {
        Node entry;
        if (!entries.TryGetValue(key, out entry))
        {
            entry = new Node { Key = key, Value = value };
            if (entries.Count == capacity)
            {
                entries.Remove(tail.Key);
                tail = tail.Previous;
                if (tail != null) tail.Next = null;
            }
            entries.Add(key, entry);
        }

        entry.Value = value;
        MoveToHead(entry);
        if (tail == null) tail = head;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        value = default(TValue);
        Node entry;
        if (!entries.TryGetValue(key, out entry)) return false;
        MoveToHead(entry);
        value = entry.Value;
        return true;
    }

    private void MoveToHead(Node entry)
    {
        if (entry == head || entry == null) return;

        var next = entry.Next;
        var previous = entry.Previous;

        if (next != null) next.Previous = entry.Previous;
        if (previous != null) previous.Next = entry.Next;

        entry.Previous = null;
        entry.Next = head;

        if (head != null) head.Previous = entry;
        head = entry;

        if (tail == entry) tail = previous;
    }
}