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 readonly 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             _ = dict["key2"];
  55             _ = dict["key3"];
  56             _ = 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             _ = dict["key4"];
 112             _ = dict["key2"];
 113             _ = dict["key3"];
 114             _ = dict["key1"];
 115             _ = 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             _ = dict["key2"];                // 7アクセス目
 148             dict.TryGetValue("key4", out _); // 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) => removedList.Add(e.Item.Key);
 167
 168             // 2 個までに縮小
 169             dict.TrimLimit = 2;
 170             dict.Trim();
 171
 172             // 直近に参照された 3, 4 以外のアイテムに対してイベントが発生しているはず
 173             Assert.Equal(new[] { "key1", "key2" }, removedList, collComparer);
 174         }
 175
 176         // ここから下は IDictionary としての機能が正しく動作するかのテスト
 177
 178         [Fact]
 179         public void AddTest()
 180         {
 181             var dict = new LRUCacheDictionary<string, string>();
 182
 183             dict.Add("key1", "value1");
 184
 185             Assert.Single(dict.innerDict);
 186             Assert.True(dict.innerDict.ContainsKey("key1"));
 187             var internalNode = dict.innerDict["key1"];
 188             Assert.Equal("key1", internalNode.Value.Key);
 189             Assert.Equal("value1", internalNode.Value.Value);
 190
 191             dict.Add("key2", "value2");
 192
 193             Assert.Equal(2, dict.innerDict.Count);
 194             Assert.True(dict.innerDict.ContainsKey("key2"));
 195             internalNode = dict.innerDict["key2"];
 196             Assert.Equal("key2", internalNode.Value.Key);
 197             Assert.Equal("value2", internalNode.Value.Value);
 198         }
 199
 200         [Fact]
 201         public void ContainsKeyTest()
 202         {
 203             var dict = new LRUCacheDictionary<string, string>
 204             {
 205                 ["key1"] = "value1",
 206                 ["key2"] = "value2",
 207                 ["key3"] = "value3",
 208             };
 209
 210             Assert.True(dict.ContainsKey("key1"));
 211             Assert.True(dict.ContainsKey("key3"));
 212             Assert.False(dict.ContainsKey("value1"));
 213             Assert.False(dict.ContainsKey("hogehoge"));
 214         }
 215
 216         [Fact]
 217         public void ContainsTest()
 218         {
 219             var dict = new LRUCacheDictionary<string, string>
 220             {
 221                 ["key1"] = "value1",
 222                 ["key2"] = "value2",
 223                 ["key3"] = "value3",
 224             };
 225
 226             Assert.Contains(new KeyValuePair<string, string>("key1", "value1"), dict);
 227             Assert.DoesNotContain(new KeyValuePair<string, string>("key3", "value2"), dict);
 228             Assert.DoesNotContain(new KeyValuePair<string, string>("value3", "key3"), dict);
 229             Assert.DoesNotContain(new KeyValuePair<string, string>("hogehoge", "hogehoge"), dict);
 230         }
 231
 232         [Fact]
 233         public void RemoveTest()
 234         {
 235             var dict = new LRUCacheDictionary<string, string>
 236             {
 237                 ["key1"] = "value1",
 238                 ["key2"] = "value2",
 239                 ["key3"] = "value3",
 240             };
 241
 242             var ret = dict.Remove("key1");
 243
 244             Assert.True(ret);
 245             Assert.Equal(2, dict.innerDict.Count);
 246             Assert.Equal(2, dict.innerList.Count);
 247             Assert.False(dict.innerDict.ContainsKey("key1"));
 248             Assert.True(dict.innerDict.ContainsKey("key2"));
 249             Assert.True(dict.innerDict.ContainsKey("key3"));
 250
 251             dict.Remove("key2");
 252             dict.Remove("key3");
 253
 254             Assert.Empty(dict.innerDict);
 255             Assert.Empty(dict.innerList);
 256
 257             ret = dict.Remove("hogehoge");
 258             Assert.False(ret);
 259         }
 260
 261         [Fact]
 262         public void Remove2Test()
 263         {
 264             var dict = new LRUCacheDictionary<string, string>
 265             {
 266                 ["key1"] = "value1",
 267                 ["key2"] = "value2",
 268                 ["key3"] = "value3",
 269             };
 270
 271             var ret = dict.Remove(new KeyValuePair<string, string>("key1", "value1"));
 272
 273             Assert.True(ret);
 274             Assert.Equal(2, dict.innerDict.Count);
 275             Assert.Equal(2, dict.innerList.Count);
 276             Assert.False(dict.innerDict.ContainsKey("key1"));
 277             Assert.True(dict.innerDict.ContainsKey("key2"));
 278             Assert.True(dict.innerDict.ContainsKey("key3"));
 279
 280             ret = dict.Remove(new KeyValuePair<string, string>("key2", "hogehoge"));
 281             Assert.False(ret);
 282
 283             dict.Remove(new KeyValuePair<string, string>("key2", "value2"));
 284             dict.Remove(new KeyValuePair<string, string>("key3", "value3"));
 285
 286             Assert.Empty(dict.innerDict);
 287             Assert.Empty(dict.innerList);
 288
 289             ret = dict.Remove(new KeyValuePair<string, string>("hogehoge", "hogehoge"));
 290             Assert.False(ret);
 291         }
 292
 293         [Fact]
 294         public void GetterTest()
 295         {
 296             var dict = new LRUCacheDictionary<string, string>
 297             {
 298                 ["key1"] = "value1",
 299                 ["key2"] = "value2",
 300                 ["key3"] = "value3",
 301             };
 302
 303             Assert.Equal("value1", dict["key1"]);
 304             Assert.Equal("value2", dict["key2"]);
 305             Assert.Equal("value3", dict["key3"]);
 306
 307             Assert.Throws<KeyNotFoundException>(() => { var x = dict["hogehoge"]; });
 308         }
 309
 310         [Fact]
 311         public void SetterTest()
 312         {
 313             var dict = new LRUCacheDictionary<string, string>
 314             {
 315                 ["key1"] = "value1",
 316                 ["key2"] = "value2",
 317                 ["key3"] = "value3",
 318             };
 319
 320             dict["key1"] = "foo";
 321             Assert.Equal("foo", dict.innerDict["key1"].Value.Value);
 322
 323             dict["hogehoge"] = "bar";
 324             Assert.True(dict.innerDict.ContainsKey("hogehoge"));
 325             Assert.Equal("bar", dict.innerDict["hogehoge"].Value.Value);
 326         }
 327
 328         [Fact]
 329         public void TryGetValueTest()
 330         {
 331             var dict = new LRUCacheDictionary<string, string>
 332             {
 333                 ["key1"] = "value1",
 334                 ["key2"] = "value2",
 335                 ["key3"] = "value3",
 336             };
 337
 338             var ret = dict.TryGetValue("key1", out var value);
 339             Assert.True(ret);
 340             Assert.Equal("value1", value);
 341
 342             ret = dict.TryGetValue("hogehoge", out value);
 343             Assert.False(ret);
 344             Assert.Null(value);
 345         }
 346
 347         [Fact]
 348         public void KeysTest()
 349         {
 350             var dict = new LRUCacheDictionary<string, string>
 351             {
 352                 ["key1"] = "value1",
 353                 ["key2"] = "value2",
 354                 ["key3"] = "value3",
 355             };
 356
 357             Assert.Equal(new[] { "key1", "key2", "key3" }, dict.Keys, collComparer);
 358
 359             dict.Add("foo", "bar");
 360             Assert.Equal(new[] { "key1", "key2", "key3", "foo" }, dict.Keys, collComparer);
 361
 362             dict.Remove("key2");
 363             Assert.Equal(new[] { "key1", "key3", "foo" }, dict.Keys, collComparer);
 364
 365             dict.Clear();
 366             Assert.Empty(dict.Keys);
 367         }
 368
 369         [Fact]
 370         public void ValuesTest()
 371         {
 372             var dict = new LRUCacheDictionary<string, string>
 373             {
 374                 ["key1"] = "value1",
 375                 ["key2"] = "value2",
 376                 ["key3"] = "value3",
 377             };
 378
 379             Assert.Equal(new[] { "value1", "value2", "value3" }, dict.Values, collComparer);
 380
 381             dict.Add("foo", "bar");
 382             Assert.Equal(new[] { "value1", "value2", "value3", "bar" }, dict.Values, collComparer);
 383
 384             dict.Remove("key2");
 385             Assert.Equal(new[] { "value1", "value3", "bar" }, dict.Values, collComparer);
 386
 387             dict.Clear();
 388             Assert.Empty(dict.Values);
 389         }
 390
 391         [Fact]
 392         public void CountTest()
 393         {
 394             var dict = new LRUCacheDictionary<string, string>();
 395
 396             Assert.Empty(dict);
 397
 398             dict.Add("key1", "value1");
 399             Assert.Single(dict);
 400
 401             dict.Add("key2", "value2");
 402             Assert.Equal(2, dict.Count);
 403
 404             dict.Remove("key1");
 405             Assert.Single(dict);
 406
 407             dict.Clear();
 408             Assert.Empty(dict);
 409         }
 410
 411         [Fact]
 412         public void CopyToTest()
 413         {
 414             var dict = new LRUCacheDictionary<string, string>
 415             {
 416                 ["key1"] = "value1",
 417                 ["key2"] = "value2",
 418                 ["key3"] = "value3",
 419             };
 420
 421             var array = new KeyValuePair<string, string>[5];
 422             dict.CopyTo(array, 0);
 423             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), array[0]);
 424             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), array[1]);
 425             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), array[2]);
 426             Assert.Equal(new KeyValuePair<string, string>(), array[3]);
 427             Assert.Equal(new KeyValuePair<string, string>(), array[4]);
 428
 429             array = new KeyValuePair<string, string>[5];
 430             dict.CopyTo(array, 1);
 431             Assert.Equal(new KeyValuePair<string, string>(), array[0]);
 432             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), array[1]);
 433             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), array[2]);
 434             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), array[3]);
 435             Assert.Equal(new KeyValuePair<string, string>(), array[4]);
 436
 437             array = new KeyValuePair<string, string>[5];
 438             Assert.Throws<ArgumentException>(() => dict.CopyTo(array, 3));
 439             Assert.Throws<ArgumentException>(() => dict.CopyTo(array, 5));
 440             Assert.Throws<ArgumentOutOfRangeException>(() => dict.CopyTo(array, -1));
 441             Assert.Throws<ArgumentNullException>(() => dict.CopyTo(null, 0));
 442         }
 443
 444         [Fact]
 445         public void IsReadOnlyTest()
 446         {
 447             var dict = new LRUCacheDictionary<string, string>();
 448
 449             Assert.False(dict.IsReadOnly);
 450         }
 451
 452         [Fact]
 453         public void EnumeratorTest()
 454         {
 455             var dict = new LRUCacheDictionary<string, string>
 456             {
 457                 ["key1"] = "value1",
 458                 ["key2"] = "value2",
 459                 ["key3"] = "value3",
 460             };
 461
 462             var enumerator = dict.GetEnumerator();
 463
 464             Assert.True(enumerator.MoveNext());
 465             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), enumerator.Current);
 466             Assert.True(enumerator.MoveNext());
 467             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), enumerator.Current);
 468             Assert.True(enumerator.MoveNext());
 469             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), enumerator.Current);
 470             Assert.False(enumerator.MoveNext());
 471         }
 472
 473         [Fact]
 474         public void Enumerator2Test()
 475         {
 476             var dict = new LRUCacheDictionary<string, string>
 477             {
 478                 ["key1"] = "value1",
 479                 ["key2"] = "value2",
 480                 ["key3"] = "value3",
 481             };
 482
 483             var enumerator = ((IEnumerable)dict).GetEnumerator();
 484
 485             Assert.True(enumerator.MoveNext());
 486             Assert.Equal(new KeyValuePair<string, string>("key1", "value1"), enumerator.Current);
 487             Assert.True(enumerator.MoveNext());
 488             Assert.Equal(new KeyValuePair<string, string>("key2", "value2"), enumerator.Current);
 489             Assert.True(enumerator.MoveNext());
 490             Assert.Equal(new KeyValuePair<string, string>("key3", "value3"), enumerator.Current);
 491             Assert.False(enumerator.MoveNext());
 492         }
 493     }
 494 }