OpenTween.Tests/LRUCacheDictionaryTest.cs

   1 // OpenTween - Client of Twitter
   2 // Copyright (c) 2013 kim_upsilon (@kim_upsilon) <https://upsilo.net/~upsilon/>
   3 // All rights reserved.
   4 //
   5 // This file is part of OpenTween.
   6 //
   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)
  10 // any later version.
  11 //
  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
  15 // for more details.
  16 //
  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.
  21
  22 using System;
  23 using System.Collections;
  24 using System.Collections.Generic;
  25 using System.Linq;
  26 using System.Text;
  27 using Xunit;
  28 using Xunit.Extensions;
  29
  30 namespace OpenTween
  31 {
  32     public class LRUCacheDictionaryTest
  33     {
  34         private static AnyOrderComparer<string> collComparer = AnyOrderComparer<string>.Instance;
  35
  36         [Fact]
  37         public void InnerListTest()
  38         {
  39             var dict = new LRUCacheDictionary<string, string>
  40             {
  41                 ["key1"] = "value1",
  42                 ["key2"] = "value2",
  43                 ["key3"] = "value3",
  44             };
  45
  46             var node = dict.innerList.First;
  47             Assert.Equal("key3", node.Value.Key);
  48             node = node.Next;
  49             Assert.Equal("key2", node.Value.Key);
  50             node = node.Next;
  51             Assert.Equal("key1", node.Value.Key);
  52
  53             // 2 -> 3 -> 1 の順に値を参照
  54             var x = dict["key2"];
  55             x = dict["key3"];
  56             x = dict["key1"];
  57
  58             // 直近に参照した順で並んでいるかテスト
  59             node = dict.innerList.First;
  60             Assert.Equal("key1", node.Value.Key);
  61             node = node.Next;
  62             Assert.Equal("key3", node.Value.Key);
  63             node = node.Next;
  64             Assert.Equal("key2", node.Value.Key);
  65         }
  66
  67         [Theory]
  68         [InlineData(1)]
  69         [InlineData(2)]
  70         [InlineData(3)]
  71         [InlineData(4)]
  72         [InlineData(5)]
  73         public void TrimLimitTest(int trimLimit)
  74         {
  75             var dict = new LRUCacheDictionary<string, string>()
  76             {
  77                 ["key1"] = "value1",
  78                 ["key2"] = "value2",
  79                 ["key3"] = "value3",
  80             };
  81
  82             dict.TrimLimit = trimLimit;
  83             var ret = dict.Trim();
  84
  85             if (trimLimit >= 3)
  86             {
  87                 // trimLimit がアイテムの件数より大きい場合、Trim メソッドは動作せずに false を返す。
  88                 Assert.False(ret);
  89                 Assert.Equal(3, dict.Count);
  90             }
  91             else
  92             {
  93                 Assert.True(ret);
  94                 Assert.Equal(trimLimit, dict.Count);
  95             }
  96         }
  97
  98         [Fact]
  99         public void TrimOrderTest()
 100         {
 101             var dict = new LRUCacheDictionary<string, string>()
 102             {
 103                 ["key1"] = "value1",
 104                 ["key2"] = "value2",
 105                 ["key3"] = "value3",
 106                 ["key4"] = "value4",
 107                 ["key5"] = "value5",
 108             };
 109
 110             // 4 -> 2 -> 3 -> 1 -> 5 の順で参照
 111             var x = dict["key4"];
 112             x = dict["key2"];
 113             x = dict["key3"];
 114             x = dict["key1"];
 115             x = dict["key5"];
 116
 117             // 3 個までに縮小
 118             dict.TrimLimit = 3;
 119             dict.Trim();
 120
 121             // 直近に参照された 3 -> 1 -> 5 のみ残っているはず
 122             Assert.True(dict.ContainsKey("key1"));
 123             Assert.False(dict.ContainsKey("key2"));
 124             Assert.True(dict.ContainsKey("key3"));
 125             Assert.False(dict.ContainsKey("key4"));
 126             Assert.True(dict.ContainsKey("key5"));
 127         }
 128
 129         [Fact]
 130         public void AutoTrimTest()
 131         {
 132             var dict = new LRUCacheDictionary<string, string>();
 133
 134             dict.AutoTrimCount = 4; // 4アクセス毎に
 135             dict.TrimLimit = 3; // 3個を越えるアイテムを削除する
 136
 137             dict["key1"] = "value1"; // 1アクセス目
 138             dict["key2"] = "value2"; // 2アクセス目
 139             dict["key3"] = "value3"; // 3アクセス目
 140             dict["key4"] = "value4"; // 4アクセス目 (この直後にTrim)
 141
 142             // 1 -> 2 -> 3 -> 4 の順にアクセスしたため、直近 3 件の 2, 3, 4 だけが残る
 143             Assert.Equal(new[] { "key2", "key3", "key4" }, dict.innerDict.Keys, collComparer);
 144
 145             dict["key5"] = "value5";         // 5アクセス目
 146             dict.Add("key6", "value6");      // 6アクセス目
 147             var x = dict["key2"];            // 7アクセス目
 148             dict.TryGetValue("key4", out x); // 8アクセス目 (この直後にTrim)
 149
 150             // 5 -> 6 -> 2 -> 4 の順でアクセスしたため、直近 3 件の 6, 2, 4 だけが残る
 151             Assert.Equal(new[] { "key6", "key2", "key4" }, dict.innerDict.Keys, collComparer);
 152         }
 153
 154         [Fact]
 155         public void CacheRemovedEventTest()
 156         {
 157             var dict = new LRUCacheDictionary<string, string>();
 158
 159             dict["key1"] = "value1";
 160             dict["key2"] = "value2";
 161             dict["key3"] = "value3";
 162             dict["key4"] = "value4";
 163
 164             // イベント設定
 165             var removedList = new List<string>();
 166             dict.CacheRemoved += (s, e) =>
 167             {
 168                 removedList.Add(e.Item.Key);
 169             };
 170
 171             // 2 個までに縮小
 172             dict.TrimLimit = 2;
 173             dict.Trim();
 174
 175             // 直近に参照された 3, 4 以外のアイテムに対してイベントが発生しているはず
 176             Assert.Equal(new[] { "key1", "key2" }, removedList, collComparer);
 177         }
 178
 179         // ここから下は IDictionary としての機能が正しく動作するかのテスト
 180
 181         [Fact]
 182         public void AddTest()
 183         {
 184             var dict = new LRUCacheDictionary<string, string>();
 185
 186             dict.Add("key1", "value1");
 187
 188             Assert.Equal(1, dict.innerDict.Count);
 189             Assert.True(dict.innerDict.ContainsKey("key1"));
 190             var internalNode = dict.innerDict["key1"];
 191             Assert.Equal("key1", internalNode.Value.Key);
 192             Assert.Equal("value1", internalNode.Value.Value);
 193
 194             dict.Add("key2", "value2");
 195
 196             Assert.Equal(2, dict.innerDict.Count);
 197             Assert.True(dict.innerDict.ContainsKey("key2"));
 198             internalNode = dict.innerDict["key2"];
 199             Assert.Equal("key2", internalNode.Value.Key);
 200             Assert.Equal("value2", internalNode.Value.Value);
 201         }
 202
 203         [Fact]
 204         public void ContainsKeyTest()
 205         {
 206             var dict = new LRUCacheDictionary<string, string>
 207             {
 208                 ["key1"] = "value1",
 209                 ["key2"] = "value2",
 210                 ["key3"] = "value3",
 211             };
 212
 213             Assert.True(dict.ContainsKey("key1"));
 214             Assert.True(dict.ContainsKey("key3"));
 215             Assert.False(dict.ContainsKey("value1"));
 216             Assert.False(dict.ContainsKey("hogehoge"));
 217         }
 218
 219         [Fact]
 220         public void ContainsTest()
 221         {
 222             var dict = new LRUCacheDictionary<string, string>
 223             {
 224                 ["key1"] = "value1",
 225                 ["key2"] = "value2",
 226                 ["key3"] = "value3",
 227             };
 228
 229             Assert.True(dict.Contains(new KeyValuePair<string, string>("key1", "value1")));
 230             Assert.False(dict.Contains(new KeyValuePair<string, string>("key3", "value2")));
 231             Assert.False(dict.Contains(new KeyValuePair<string, string>("value3", "key3")));
 232             Assert.False(dict.Contains(new KeyValuePair<string, string>("hogehoge", "hogehoge")));
 233         }
 234
 235         [Fact]
 236         public void RemoveTest()
 237         {
 238             var dict = new LRUCacheDictionary<string, string>
 239             {
 240                 ["key1"] = "value1",
 241                 ["key2"] = "value2",
 242                 ["key3"] = "value3",
 243             };
 244
 245             var ret = dict.Remove("key1");
 246
 247             Assert.True(ret);
 248             Assert.Equal(2, dict.innerDict.Count);
 249             Assert.Equal(2, dict.innerList.Count);
 250             Assert.False(dict.innerDict.ContainsKey("key1"));
 251             Assert.True(dict.innerDict.ContainsKey("key2"));
 252             Assert.True(dict.innerDict.ContainsKey("key3"));
 253
 254             dict.Remove("key2");
 255             dict.Remove("key3");
 256
 257             Assert.Empty(dict.innerDict);
 258             Assert.Empty(dict.innerList);
 259
 260             ret = dict.Remove("hogehoge");
 261             Assert.False(ret);
 262         }
 263
 264         [Fact]
 265         public void Remove2Test()
 266         {
 267             var dict = new LRUCacheDictionary<string, string>
 268             {
 269                 ["key1"] = "value1",
 270                 ["key2"] = "value2",
 271                 ["key3"] = "value3",
 272             };
 273
 274             var ret = dict.Remove(new KeyValuePair<string, string>("key1", "value1"));
 275
 276             Assert.True(ret);
 277             Assert.Equal(2, dict.innerDict.Count);
 278             Assert.Equal(2, dict.innerList.Count);
 279             Assert.False(dict.innerDict.ContainsKey("key1"));
 280             Assert.True(dict.innerDict.ContainsKey("key2"));
 281             Assert.True(dict.innerDict.ContainsKey("key3"));
 282
 283             ret = dict.Remove(new KeyValuePair<string, string>("key2", "hogehoge"));
 284             Assert.False(ret);
 285
 286             dict.Remove(new KeyValuePair<string, string>("key2", "value2"));
 287             dict.Remove(new KeyValuePair<string, string>("key3", "value3"));
 288
 289             Assert.Empty(dict.innerDict);
 290             Assert.Empty(dict.innerList);
 291
 292             ret = dict.Remove(new KeyValuePair<string, string>("hogehoge", "hogehoge"));
 293             Assert.False(ret);
 294         }
 295
 296         public void GetterTest()
 297         {
 298             var dict = new LRUCacheDictionary<string, string>
 299             {
 300                 ["key1"] = "value1",
 301                 ["key2"] = "value2",
 302                 ["key3"] = "value3",
 303             };
 304
 305             Assert.Equal("value1", dict["key1"]);
 306             Assert.Equal("value2", dict["key2"]);
 307             Assert.Equal("value3", dict["key3"]);
 308
 309             Assert.Throws<KeyNotFoundException>(() => { var x = dict["hogehoge"]; });
 310         }
 311
 312         [Fact]
 313         public void SetterTest()
 314         {
 315             var dict = new LRUCacheDictionary<string, string>
 316             {
 317                 ["key1"] = "value1",
 318                 ["key2"] = "value2",
 319                 ["key3"] = "value3",
 320             };
 321
 322             dict["key1"] = "foo";
 323             Assert.Equal("foo", dict.innerDict["key1"].Value.Value);
 324
 325             dict["hogehoge"] = "bar";
 326             Assert.True(dict.innerDict.ContainsKey("hogehoge"));
 327             Assert.Equal("bar", dict.innerDict["hogehoge"].Value.Value);
 328         }
 329
 330         [Fact]
 331         public void TryGetValueTest()
 332         {
 333             var dict = new LRUCacheDictionary<string, string>
 334             {
 335                 ["key1"] = "value1",
 336                 ["key2"] = "value2",
 337                 ["key3"] = "value3",
 338             };
 339
 340             string value;
 341             var ret = dict.TryGetValue("key1", out value);
 342             Assert.True(ret);
 343             Assert.Equal("value1", value);
 344
 345             ret = dict.TryGetValue("hogehoge", out value);
 346             Assert.False(ret);
 347             Assert.Null(value);
 348         }
 349
 350         [Fact]
 351         public void KeysTest()
 352         {
 353             var dict = new LRUCacheDictionary<string, string>
 354             {
 355                 ["key1"] = "value1",
 356                 ["key2"] = "value2",
 357                 ["key3"] = "value3",
 358             };
 359
 360             Assert.Equal(new[] { "key1", "key2", "key3" }, dict.Keys, collComparer);
 361
 362             dict.Add("foo", "bar");
 363             Assert.Equal(new[] { "key1", "key2", "key3", "foo" }, dict.Keys, collComparer);
 364
 365             dict.Remove("key2");
 366             Assert.Equal(new[] { "key1", "key3", "foo" }, dict.Keys, collComparer);
 367
 368             dict.Clear();
 369             Assert.Empty(dict.Keys);
 370         }
 371
 372         [Fact]
 373         public void ValuesTest()
 374         {
 375             var dict = new LRUCacheDictionary<string, string>
 376             {
 377                 ["key1"] = "value1",
 378                 ["key2"] = "value2",
 379                 ["key3"] = "value3",
 380             };
 381
 382             Assert.Equal(new[] { "value1", "value2", "value3" }, dict.Values, collComparer);
 383
 384             dict.Add("foo", "bar");
 385             Assert.Equal(new[] { "value1", "value2", "value3", "bar" }, dict.Values, collComparer);
 386
 387             dict.Remove("key2");
 388             Assert.Equal(new[] { "value1", "value3", "bar" }, dict.Values, collComparer);
 389
 390             dict.Clear();
 391             Assert.Empty(dict.Values);
 392         }
 393
 394         [Fact]
 395         public void CountTest()
 396         {
 397             var dict = new LRUCacheDictionary<string, string>();
 398
 399             Assert.Equal(0, dict.Count);
 400
 401             dict.Add("key1", "value1");
 402             Assert.Equal(1, dict.Count);
 403
 404             dict.Add("key2", "value2");
 405             Assert.Equal(2, dict.Count);
 406
 407             dict.Remove("key1");
 408             Assert.Equal(1, dict.Count);
 409
 410             dict.Clear();
 411             Assert.Equal(0, dict.Count);
 412         }
 413
 414         [Fact]
 415         public void CopyToTest()
 416         {
 417             var dict = new LRUCacheDictionary<string, string>
 418             {
 419                 ["key1"] = "value1",
 420                 ["key2"] = "value2",
 421                 ["key3"] = "value3",
 422             };
 423
 424             var array = new KeyValuePair<string, string>[5];
 425             dict.CopyTo(array, 0);
 426             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), array[0]);
 427             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), array[1]);
 428             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), array[2]);
 429             Assert.Equal(new KeyValuePair<string, string>(), array[3]);
 430             Assert.Equal(new KeyValuePair<string, string>(), array[4]);
 431
 432             array = new KeyValuePair<string, string>[5];
 433             dict.CopyTo(array, 1);
 434             Assert.Equal(new KeyValuePair<string, string>(), array[0]);
 435             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), array[1]);
 436             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), array[2]);
 437             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), array[3]);
 438             Assert.Equal(new KeyValuePair<string, string>(), array[4]);
 439
 440             array = new KeyValuePair<string, string>[5];
 441             Assert.Throws<ArgumentException>(() => dict.CopyTo(array, 3));
 442             Assert.Throws<ArgumentException>(() => dict.CopyTo(array, 5));
 443             Assert.Throws<ArgumentOutOfRangeException>(() => dict.CopyTo(array, -1));
 444             Assert.Throws<ArgumentNullException>(() => dict.CopyTo(null, 0));
 445         }
 446
 447         [Fact]
 448         public void IsReadOnlyTest()
 449         {
 450             var dict = new LRUCacheDictionary<string, string>();
 451
 452             Assert.False(dict.IsReadOnly);
 453         }
 454
 455         [Fact]
 456         public void EnumeratorTest()
 457         {
 458             var dict = new LRUCacheDictionary<string, string>
 459             {
 460                 ["key1"] = "value1",
 461                 ["key2"] = "value2",
 462                 ["key3"] = "value3",
 463             };
 464
 465             var enumerator = dict.GetEnumerator();
 466
 467             Assert.True(enumerator.MoveNext());
 468             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), enumerator.Current);
 469             Assert.True(enumerator.MoveNext());
 470             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), enumerator.Current);
 471             Assert.True(enumerator.MoveNext());
 472             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), enumerator.Current);
 473             Assert.False(enumerator.MoveNext());
 474         }
 475
 476         [Fact]
 477         public void Enumerator2Test()
 478         {
 479             var dict = new LRUCacheDictionary<string, string>
 480             {
 481                 ["key1"] = "value1",
 482                 ["key2"] = "value2",
 483                 ["key3"] = "value3",
 484             };
 485
 486             var enumerator = ((IEnumerable)dict).GetEnumerator();
 487
 488             Assert.True(enumerator.MoveNext());
 489             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), enumerator.Current);
 490             Assert.True(enumerator.MoveNext());
 491             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), enumerator.Current);
 492             Assert.True(enumerator.MoveNext());
 493             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), enumerator.Current);
 494             Assert.False(enumerator.MoveNext());
 495         }
 496     }
 497 }