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; private set; }
55 public CacheRemovedEventArgs(KeyValuePair<TKey, TValue> item)
60 public event EventHandler<CacheRemovedEventArgs> CacheRemoved;
62 internal LinkedList<KeyValuePair<TKey, TValue>> innerList;
63 internal Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> innerDict;
65 internal int accessCount = 0;
67 public LRUCacheDictionary()
68 : this(trimLimit: int.MaxValue, autoTrimCount: int.MaxValue)
72 public LRUCacheDictionary(int trimLimit, int autoTrimCount)
74 this.TrimLimit = trimLimit;
75 this.AutoTrimCount = autoTrimCount;
77 this.innerList = new LinkedList<KeyValuePair<TKey, TValue>>();
78 this.innerDict = new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();
82 /// innerList の並び順を最近アクセスがあった順に維持するために、
83 /// 辞書内のアイテムが参照する度に呼び出されるメソッド。
85 protected void UpdateAccess(LinkedListNode<KeyValuePair<TKey, TValue>> node)
87 this.innerList.Remove(node);
88 this.innerList.AddFirst(node);
93 if (this.Count <= this.TrimLimit) return false;
95 for (int i = this.Count; i > this.TrimLimit; i--)
97 var node = this.innerList.Last;
98 this.innerList.Remove(node);
99 this.innerDict.Remove(node.Value.Key);
101 if (this.CacheRemoved != null)
102 this.CacheRemoved(this, new CacheRemovedEventArgs(node.Value));
108 internal bool AutoTrim()
110 if (this.accessCount < this.AutoTrimCount) return false;
112 this.accessCount = 0; // カウンターをリセット
117 public void Add(TKey key, TValue value)
119 this.Add(new KeyValuePair<TKey, TValue>(key, value));
122 public void Add(KeyValuePair<TKey, TValue> item)
124 var node = new LinkedListNode<KeyValuePair<TKey, TValue>>(item);
125 this.innerList.AddFirst(node);
126 this.innerDict.Add(item.Key, node);
132 public bool ContainsKey(TKey key)
134 return this.innerDict.ContainsKey(key);
137 public bool Contains(KeyValuePair<TKey, TValue> item)
139 LinkedListNode<KeyValuePair<TKey, TValue>> node;
140 if (!this.innerDict.TryGetValue(item.Key, out node)) return false;
142 return node.Value.Value.Equals(item.Value);
145 public bool Remove(TKey key)
147 LinkedListNode<KeyValuePair<TKey, TValue>> node;
148 if (!this.innerDict.TryGetValue(key, out node)) return false;
150 this.innerList.Remove(node);
152 return this.innerDict.Remove(key);
155 public bool Remove(KeyValuePair<TKey, TValue> item)
157 LinkedListNode<KeyValuePair<TKey, TValue>> node;
158 if (!this.innerDict.TryGetValue(item.Key, out node)) return false;
160 if (!node.Value.Value.Equals(item.Value)) return false;
162 this.innerList.Remove(node);
164 return this.innerDict.Remove(item.Key);
167 public bool TryGetValue(TKey key, out TValue value)
169 LinkedListNode<KeyValuePair<TKey, TValue>> node;
171 var ret = this.innerDict.TryGetValue(key, out node);
175 value = default(TValue);
179 this.UpdateAccess(node);
180 value = node.Value.Value;
188 public ICollection<TKey> Keys
190 get { return this.innerDict.Keys; }
193 public ICollection<TValue> Values
195 get { return this.innerDict.Values.Select(x => x.Value.Value).ToList(); }
198 public TValue this[TKey key]
202 var node = this.innerDict[key];
203 this.UpdateAccess(node);
208 return node.Value.Value;
212 LinkedListNode<KeyValuePair<TKey, TValue>> node;
214 var pair = new KeyValuePair<TKey, TValue>(key, value);
216 if (this.innerDict.TryGetValue(key, out node))
218 this.innerList.Remove(node);
223 node = new LinkedListNode<KeyValuePair<TKey, TValue>>(pair);
224 this.innerDict[key] = node;
227 this.innerList.AddFirst(node);
236 this.innerList.Clear();
237 this.innerDict.Clear();
240 public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
243 throw new ArgumentNullException("array");
245 throw new ArgumentOutOfRangeException("arrayIndex");
246 if (arrayIndex >= array.Length)
247 throw new ArgumentException("arrayIndex is equal to or greater than array.Length.", "arrayIndex");
248 if (array.Length - arrayIndex < this.Count)
249 throw new ArgumentException("The destination array is too small.", "array");
251 foreach (var pair in this)
252 array[arrayIndex++] = pair;
257 get { return this.innerDict.Count; }
260 public bool IsReadOnly
262 get { return false; }
265 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
267 return this.innerDict.Select(x => x.Value.Value).GetEnumerator();
270 IEnumerator IEnumerable.GetEnumerator()
272 return this.GetEnumerator();