1 // OpenTween - Client of Twitter
2 // Copyright (c) 2013 kim_upsilon (@kim_upsilon) <https://upsilo.net/~upsilon/>
3 // All rights reserved.
5 // This file is part of OpenTween.
7 // This program is free software; you can redistribute it and/or modify it
8 // under the terms of the GNU General Public License as published by the Free
9 // Software Foundation; either version 3 of the License, or (at your option)
12 // This program is distributed in the hope that it will be useful, but
13 // WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 // You should have received a copy of the GNU General Public License along
18 // with this program. If not, see <http://www.gnu.org/licenses/>, or write to
19 // the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
20 // Boston, MA 02110-1301, USA.
23 using System.Collections.Generic;
26 using System.Collections;
31 /// LRU によるキャッシュを行うための辞書クラス
33 class LRUCacheDictionary<TKey, TValue> : IDictionary<TKey, TValue>
39 /// TrimLimit を上回る個数のアイテムが格納されている場合は Trim メソッド実行時に除去される。
41 public int TrimLimit { get; set; }
44 /// 自動で Trim メソッドを実行する、参照回数の閾値
47 /// AutoTrimCount で指定された回数だけアイテムが参照される度に Trim メソッドが実行される。
49 public int AutoTrimCount { get; set; }
51 public class CacheRemovedEventArgs : EventArgs
53 public KeyValuePair<TKey, TValue> Item { get; }
55 public CacheRemovedEventArgs(KeyValuePair<TKey, TValue> item)
58 public event EventHandler<CacheRemovedEventArgs> CacheRemoved;
60 internal LinkedList<KeyValuePair<TKey, TValue>> innerList;
61 internal Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> innerDict;
63 internal int accessCount = 0;
65 public LRUCacheDictionary()
66 : this(trimLimit: int.MaxValue, autoTrimCount: int.MaxValue)
70 public LRUCacheDictionary(int trimLimit, int autoTrimCount)
72 this.TrimLimit = trimLimit;
73 this.AutoTrimCount = autoTrimCount;
75 this.innerList = new LinkedList<KeyValuePair<TKey, TValue>>();
76 this.innerDict = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
80 /// innerList の並び順を最近アクセスがあった順に維持するために、
81 /// 辞書内のアイテムが参照する度に呼び出されるメソッド。
83 protected void UpdateAccess(LinkedListNode<KeyValuePair<TKey, TValue>> node)
85 this.innerList.Remove(node);
86 this.innerList.AddFirst(node);
91 if (this.Count <= this.TrimLimit) return false;
93 for (int i = this.Count; i > this.TrimLimit; i--)
95 var node = this.innerList.Last;
96 this.innerList.Remove(node);
97 this.innerDict.Remove(node.Value.Key);
99 this.CacheRemoved?.Invoke(this, new CacheRemovedEventArgs(node.Value));
105 internal bool AutoTrim()
107 if (this.accessCount < this.AutoTrimCount) return false;
109 this.accessCount = 0; // カウンターをリセット
114 public void Add(TKey key, TValue value)
115 => this.Add(new KeyValuePair<TKey, TValue>(key, value));
117 public void Add(KeyValuePair<TKey, TValue> item)
119 var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(item);
120 this.innerList.AddFirst(node);
121 this.innerDict.Add(item.Key, node);
127 public bool ContainsKey(TKey key)
128 => this.innerDict.ContainsKey(key);
130 public bool Contains(KeyValuePair<TKey, TValue> item)
132 if (!this.innerDict.TryGetValue(item.Key, out var node)) return false;
134 return node.Value.Value.Equals(item.Value);
137 public bool Remove(TKey key)
139 if (!this.innerDict.TryGetValue(key, out var node)) return false;
141 this.innerList.Remove(node);
143 return this.innerDict.Remove(key);
146 public bool Remove(KeyValuePair<TKey, TValue> item)
148 if (!this.innerDict.TryGetValue(item.Key, out var node)) return false;
150 if (!node.Value.Value.Equals(item.Value)) return false;
152 this.innerList.Remove(node);
154 return this.innerDict.Remove(item.Key);
157 public bool TryGetValue(TKey key, out TValue value)
159 var ret = this.innerDict.TryGetValue(key, out var node);
163 value = default(TValue);
167 this.UpdateAccess(node);
168 value = node.Value.Value;
176 public ICollection<TKey> Keys
177 => this.innerDict.Keys;
179 public ICollection<TValue> Values
180 => this.innerDict.Values.Select(x => x.Value.Value).ToList();
182 public TValue this[TKey key]
186 var node = this.innerDict[key];
187 this.UpdateAccess(node);
192 return node.Value.Value;
196 var pair = new KeyValuePair<TKey, TValue>(key, value);
198 if (this.innerDict.TryGetValue(key, out var node))
200 this.innerList.Remove(node);
205 node = new LinkedListNode<KeyValuePair<TKey, TValue>>(pair);
206 this.innerDict[key] = node;
209 this.innerList.AddFirst(node);
218 this.innerList.Clear();
219 this.innerDict.Clear();
222 public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
225 throw new ArgumentNullException(nameof(array));
227 throw new ArgumentOutOfRangeException(nameof(arrayIndex));
228 if (arrayIndex >= array.Length)
229 throw new ArgumentException("arrayIndex is equal to or greater than array.Length.", nameof(arrayIndex));
230 if (array.Length - arrayIndex < this.Count)
231 throw new ArgumentException("The destination array is too small.", nameof(array));
233 foreach (var pair in this)
234 array[arrayIndex++] = pair;
238 => this.innerDict.Count;
240 public bool IsReadOnly
243 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
244 => this.innerDict.Select(x => x.Value.Value).GetEnumerator();
246 IEnumerator IEnumerable.GetEnumerator()
247 => this.GetEnumerator();