Skip to content

Instantly share code, notes, and snippets.

/lfu.cs Secret

Created Dec 18, 2016
Embed
What would you like to do?
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication3
{
class UsageNode<TKey>
{
public int Usage { get; set; }
public LinkedList<KeyNode<TKey>> KeyList { get; set; }
}
class KeyNode<TKey>
{
public TKey Key { get; set; }
public LinkedListNode<UsageNode<TKey>> ParentUsage { get; set; }
}
class DataNode<TKey, TValue>
{
public TValue Value { get; set; }
public LinkedListNode<KeyNode<TKey>> KeyNode { get; set; }
}
class LFUCache<TKey, TValue>
{
private readonly int cacheSize;
private readonly Dictionary<TKey, DataNode<TKey, TValue>> _data;
private readonly LinkedList<UsageNode<TKey>> _usageList;
public int Count => _data.Count;
public LFUCache(int cacheSize)
{
this.cacheSize = cacheSize;
_data = new Dictionary<TKey, DataNode<TKey, TValue>>(this.cacheSize);
_usageList = new LinkedList<UsageNode<TKey>>();
}
public void Set(TKey key, TValue value)
{
if (_data.ContainsKey(key))
{
var node = _data[key].KeyNode.Value;
_data.Remove(key);
node.ParentUsage.Value.KeyList.Remove(node);
if (node.ParentUsage.Value.KeyList.Count == 0)
{
_usageList.Remove(node.ParentUsage);
}
}
if (_data.Count >= this.cacheSize)
{
//removing a key from usage tree
var first = _usageList.First.Value.KeyList.First;
_data.Remove(first.Value.Key);
_usageList.First.Value.KeyList.Remove(first);
if (_usageList.First.Value.KeyList.Count == 0)
{
_usageList.Remove(_usageList.First);
}
}
if (_usageList.Count == 0 || _usageList.First.Value.Usage != 1)
{
var usageHead = new UsageNode<TKey>
{
Usage = 1,
KeyList = new LinkedList<KeyNode<TKey>>()
};
_usageList.AddFirst(usageHead);
}
var newKeyNode = new KeyNode<TKey>()
{
Key = key,
ParentUsage = _usageList.First
};
var newUsageNode = _usageList.First.Value.KeyList.AddFirst(newKeyNode);
_data.Add(key, new DataNode<TKey, TValue>
{
Value = value,
KeyNode = newUsageNode
});
}
public TValue Get(TKey key)
{
if (!_data.ContainsKey(key))
{
throw new ArgumentException("No such key");
}
var returnValue = _data[key];
var usageCurrent = returnValue.KeyNode.Value.ParentUsage;
LinkedListNode<UsageNode<TKey>> usageNext = null;
if (usageCurrent.Next == null || (usageCurrent.Next.Value.Usage != usageCurrent.Value.Usage + 1))
{
var usagenode = new UsageNode<TKey>()
{
Usage = usageCurrent.Value.Usage + 1,
KeyList = new LinkedList<KeyNode<TKey>>()
};
usageNext = _usageList.AddAfter(usageCurrent, usagenode);
}
else
{
usageNext = usageCurrent.Next;
}
returnValue.KeyNode.Value.ParentUsage.Value.KeyList.Remove(returnValue.KeyNode);
if (returnValue.KeyNode.Value.ParentUsage.Value.KeyList.Count == 0)
{
_usageList.Remove(returnValue.KeyNode.Value.ParentUsage);
}
usageNext.Value.KeyList.AddFirst(returnValue.KeyNode);
returnValue.KeyNode.Value.ParentUsage = usageNext;
return returnValue.Value;
}
public Dictionary<TKey, TValue> ToDictionary()
{
return _data.ToDictionary(x => x.Key, x => x.Value.Value);
}
}
class Program
{
static void Main(string[] args)
{
var cache = new LFUCache<string, int>(2);
cache.Set("a", 1);
Console.WriteLine(cache.Get("a"));
Console.WriteLine(cache.Get("a"));
cache.Set("b", 2);
cache.Get("b");
cache.Set("c", 3);
foreach (var kv in cache.ToDictionary())
{
Console.WriteLine($"K: {kv.Key} V:{kv.Value}");
}
Console.WriteLine($"Count {cache.Count}");
Console.ReadKey(true);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment