Cache.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading;
using Waher.Events;
 
namespace Waher.Runtime.Cache
{
    public class Cache<KeyType, ValueType> : ICache, IDictionary<KeyType, ValueType>
    {
        private readonly Guid id = Guid.NewGuid();
        private readonly Dictionary<KeyType, CacheItem<KeyType, ValueType>> valuesByKey = new Dictionary<KeyType, CacheItem<KeyType, ValueType>>();
        private readonly SortedDictionary<DateTime, KeyType> keysByLastUsage = new SortedDictionary<DateTime, KeyType>();
        private readonly SortedDictionary<DateTime, KeyType> keysByCreation = new SortedDictionary<DateTime, KeyType>();
        private readonly Random rnd = new Random();
        private readonly object synchObject = new object();
        private readonly int maxItems;
        private readonly bool standalone;
        private TimeSpan maxTimeUsed;
        private TimeSpan maxTimeUnused;
        private Timer timer;
 
        public Cache(int MaxItems, TimeSpan MaxTimeUsed, TimeSpan MaxTimeUnused)
            : this(MaxItems, MaxTimeUsed, MaxTimeUnused, false)
        {
        }
 
        public Cache(int MaxItems, TimeSpan MaxTimeUsed, TimeSpan MaxTimeUnused, bool Standalone)
        {
            this.maxItems = MaxItems;
            this.maxTimeUsed = MaxTimeUsed;
            this.maxTimeUnused = MaxTimeUnused;
            this.standalone = Standalone;
 
            Caches.Register(this.id, this);
        }
 
        private void CreateTimerLocked()
        {
            if (this.maxTimeUsed < TimeSpan.MaxValue || this.maxTimeUnused < TimeSpan.MaxValue)
            {
                int Interval = Math.Min((int)((this.maxTimeUnused.TotalMilliseconds / 2) + 0.5), 5000);
                if (Interval < 100)
                    Interval = 100;
 
                this.timer = new Timer(this.TimerCallback, null, Interval, Interval);
            }
            else
                this.timer = null;
        }
 
        public void Dispose()
        {
            Caches.Unregister(this.id);
            this.Clear();
        }
 
        public bool Standalone => this.standalone;
 
        private void TimerCallback(object state)
        {
            LinkedList<CacheItem<KeyType, ValueType>> ToRemove1 = null;
            LinkedList<CacheItem<KeyType, ValueType>> ToRemove2 = null;
            DateTime Now = DateTime.Now;
            DateTime Limit;
 
            try
            {
                lock (this.synchObject)
                {
                    if (this.maxTimeUnused < TimeSpan.MaxValue)
                    {
                        Limit = Now - this.maxTimeUnused;
 
                        foreach (KeyValuePair<DateTime, KeyType> P in this.keysByLastUsage)
                        {
                            if (P.Key > Limit)
                                break;
 
                            if (ToRemove1 is null)
                                ToRemove1 = new LinkedList<CacheItem<KeyType, ValueType>>();
 
                            ToRemove1.AddLast(this.valuesByKey[P.Value]);
                        }
 
                        if (!(ToRemove1 is null))
                        {
                            foreach (CacheItem<KeyType, ValueType> Item in ToRemove1)
                            {
                                this.valuesByKey.Remove(Item.Key);
                                this.keysByCreation.Remove(Item.Created);
                                this.keysByLastUsage.Remove(Item.LastUsed);
                            }
 
                            if (this.valuesByKey.Count == 0)
                            {
                                this.timer?.Dispose();
                                this.timer = null;
                            }
                        }
                    }
 
                    if (this.maxTimeUsed < TimeSpan.MaxValue)
                    {
                        Limit = Now - this.maxTimeUsed;
 
                        foreach (KeyValuePair<DateTime, KeyType> P in this.keysByCreation)
                        {
                            if (P.Key > Limit)
                                break;
 
                            if (ToRemove2 is null)
                                ToRemove2 = new LinkedList<CacheItem<KeyType, ValueType>>();
 
                            ToRemove2.AddLast(this.valuesByKey[P.Value]);
                        }
 
                        if (!(ToRemove2 is null))
                        {
                            foreach (CacheItem<KeyType, ValueType> Item in ToRemove2)
                            {
                                this.valuesByKey.Remove(Item.Key);
                                this.keysByCreation.Remove(Item.Created);
                                this.keysByLastUsage.Remove(Item.LastUsed);
                            }
 
                            if (this.valuesByKey.Count == 0)
                            {
                                this.timer?.Dispose();
                                this.timer = null;
                            }
                        }
                    }
                }
 
                if (!(ToRemove1 is null))
                    this.OnRemoved(ToRemove1, RemovedReason.NotUsed);
 
                if (!(ToRemove2 is null))
                    this.OnRemoved(ToRemove2, RemovedReason.Old);
            }
            catch (Exception ex)
            {
                Log.Exception(ex);
            }
        }
 
        public int MaxItems => this.maxItems;
 
        public TimeSpan MaxTimeUsed
        {
            get => this.maxTimeUsed;
            set => this.maxTimeUsed = value;
        }
 
        public TimeSpan MaxTimeUnused
        {
            get => this.maxTimeUnused;
            set => this.maxTimeUnused = value;
        }
 
        public bool TryGetValue(KeyType Key, out ValueType Value)
        {
            lock (this.synchObject)
            {
                if (this.valuesByKey.TryGetValue(Key, out CacheItem<KeyType, ValueType> Item))
                {
                    Value = Item.Value;
 
                    this.keysByLastUsage.Remove(Item.LastUsed);
                    Item.LastUsed = this.GetLastUsageTimeLocked();
                    this.keysByLastUsage[Item.LastUsed] = Key;
 
                    return true;
                }
                else
                {
                    Value = default;
                    return false;
                }
            }
        }
 
        public int Count
        {
            get
            {
                lock (this.synchObject)
                {
                    return this.valuesByKey.Count;
                }
            }
        }
 
        public ICollection<KeyType> Keys => this.GetKeys();
 
        public ICollection<ValueType> Values => this.GetValues();
 
        public bool IsReadOnly => false;
 
        public KeyType[] GetKeys()
        {
            KeyType[] Result;
 
            lock (this.synchObject)
            {
                Result = new KeyType[this.valuesByKey.Count];
                this.valuesByKey.Keys.CopyTo(Result, 0);
            }
 
            return Result;
        }
 
        public ValueType[] GetValues()
        {
            ValueType[] Result;
            int i = 0;
 
            lock (this.synchObject)
            {
                Result = new ValueType[this.valuesByKey.Count];
 
                foreach (CacheItem<KeyType, ValueType> Rec in this.valuesByKey.Values)
                    Result[i++] = Rec.Value;
            }
 
            return Result;
        }
 
        public bool ContainsKey(KeyType Key)
        {
            return (this.TryGetValue(Key, out ValueType _));
        }
 
        private DateTime GetLastUsageTimeLocked()
        {
            DateTime TP = DateTime.Now;
 
            while (this.keysByLastUsage.ContainsKey(TP))
                TP = TP.AddTicks(this.rnd.Next(1, 10));
 
            return TP;
        }
 
        public ValueType this[KeyType Key]
        {
            get
            {
                if (this.TryGetValue(Key, out ValueType Result))
                    return Result;
                else
                    throw new ArgumentException("Value not found.", nameof(Key));
            }
 
            set
            {
                this.Add(Key, value);
            }
        }
 
        public void Add(KeyType Key, ValueType Value)
        {
            CacheItem<KeyType, ValueType> Prev;
            CacheItem<KeyType, ValueType> Item;
            RemovedReason Reason;
 
            lock (this.synchObject)
            {
                if (this.valuesByKey.TryGetValue(Key, out Prev))
                {
                    this.valuesByKey.Remove(Key);
                    this.keysByCreation.Remove(Prev.Created);
                    this.keysByLastUsage.Remove(Prev.LastUsed);
                    Reason = RemovedReason.Replaced;
                }
                else
                {
                    Reason = RemovedReason.Space;
 
                    if (this.valuesByKey.Count >= this.maxItems)
                    {
                        KeyType OldKey = default;
                        bool Found = false;
 
                        foreach (KeyType Key2 in this.keysByLastUsage.Values)
                        {
                            OldKey = Key2;
                            Found = true;
                            break;
                        }
 
                        if (Found)
                        {
                            Prev = this.valuesByKey[OldKey];
 
                            this.valuesByKey.Remove(OldKey);
                            this.keysByCreation.Remove(Prev.Created);
                            this.keysByLastUsage.Remove(Prev.LastUsed);
                        }
                        else
                            Prev = null;
                    }
                    else
                        Prev = null;
                }
 
                DateTime TP = DateTime.Now;
 
                while (this.keysByCreation.ContainsKey(TP) || this.keysByLastUsage.ContainsKey(TP))
                    TP = TP.AddTicks(this.rnd.Next(1, 10));
 
                Item = new CacheItem<KeyType, ValueType>(Key, Value, TP);
 
                this.valuesByKey[Key] = Item;
                this.keysByCreation[TP] = Key;
                this.keysByLastUsage[TP] = Key;
 
                if (this.timer is null)
                    this.CreateTimerLocked();
            }
 
            if (!(Prev is null))
                this.OnRemoved(Key, Prev.Value, Reason);
        }
 
        private async void OnRemoved(KeyType Key, ValueType Value, RemovedReason Reason)
        {
            CacheItemEventHandler<KeyType, ValueType> h = this.Removed;
 
            if (!(h is null))
            {
                try
                {
                    await h(this, new CacheItemEventArgs<KeyType, ValueType>(Key, Value, Reason));
                }
                catch (Exception ex)
                {
                    Log.Exception(ex);
                }
            }
        }
 
        private async void OnRemoved(IEnumerable<CacheItem<KeyType, ValueType>> Items, RemovedReason Reason)
        {
            CacheItemEventHandler<KeyType, ValueType> h = this.Removed;
            try
            {
                if (!(h is null))
                {
                    foreach (CacheItem<KeyType, ValueType> Item in Items)
                    {
                        try
                        {
                            await h(this, new CacheItemEventArgs<KeyType, ValueType>(Item.Key, Item.Value, Reason));
                        }
                        catch (Exception ex)
                        {
                            Log.Exception(ex);
                        }
                    }
                }
            }
            catch (Exception ex)
            {
                Log.Exception(ex);
            }
        }
 
        public bool Remove(KeyType Key)
        {
            CacheItem<KeyType, ValueType> Item;
 
            lock (this.synchObject)
            {
                if (!this.valuesByKey.TryGetValue(Key, out Item))
                    return false;
 
                this.valuesByKey.Remove(Item.Key);
                this.keysByCreation.Remove(Item.Created);
                this.keysByLastUsage.Remove(Item.LastUsed);
 
                if (this.valuesByKey.Count == 0)
                {
                    this.timer?.Dispose();
                    this.timer = null;
                }
            }
 
            this.OnRemoved(Key, Item.Value, RemovedReason.Manual);
 
            return true;
        }
 
        public event CacheItemEventHandler<KeyType, ValueType> Removed = null;
 
        public void Clear()
        {
            CacheItem<KeyType, ValueType>[] Values;
 
            lock (this.synchObject)
            {
                Values = new CacheItem<KeyType, ValueType>[this.valuesByKey.Count];
                this.valuesByKey.Values.CopyTo(Values, 0);
                this.valuesByKey.Clear();
                this.keysByLastUsage.Clear();
                this.keysByCreation.Clear();
 
                this.timer?.Dispose();
                this.timer = null;
            }
 
            this.OnRemoved(Values, RemovedReason.Manual);
        }
 
        public void Add(KeyValuePair<KeyType, ValueType> item)
        {
            this.Add(item.Key, item.Value);
        }
 
        public bool Contains(KeyValuePair<KeyType, ValueType> item)
        {
            return this.TryGetValue(item.Key, out ValueType Value) && Value.Equals(item.Value);
        }
 
        public void CopyTo(KeyValuePair<KeyType, ValueType>[] array, int arrayIndex)
        {
            lock (this.synchObject)
            {
                foreach (CacheItem<KeyType, ValueType> Item in this.valuesByKey.Values)
                    array[arrayIndex++] = new KeyValuePair<KeyType, ValueType>(Item.Key, Item.Value);
            }
        }
 
        public KeyValuePair<KeyType, ValueType>[] ToArray()
        {
            KeyValuePair<KeyType, ValueType>[] Result;
            int i = 0;
 
            lock (this.synchObject)
            {
                Result = new KeyValuePair<KeyType, ValueType>[this.valuesByKey.Count];
 
                foreach (CacheItem<KeyType, ValueType> Item in this.valuesByKey.Values)
                    Result[i++] = new KeyValuePair<KeyType, ValueType>(Item.Key, Item.Value);
            }
 
            return Result;
        }
 
        public bool Remove(KeyValuePair<KeyType, ValueType> item)
        {
            if (this.TryGetValue(item.Key, out ValueType Value) && Value.Equals(item.Value))
                return this.Remove(item.Key);
            else
                return false;
        }
 
        public IEnumerator<KeyValuePair<KeyType, ValueType>> GetEnumerator()
        {
            IEnumerable<KeyValuePair<KeyType, ValueType>> Array = this.ToArray();
            return Array.GetEnumerator();
        }
 
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.ToArray().GetEnumerator();
        }
    }
}