TreeDictionaryTests.cs
1 using NUnit.Framework; 2 using Ryujinx.Common.Collections; 3 using System; 4 using System.Collections.Generic; 5 6 namespace Ryujinx.Tests.Collections 7 { 8 class TreeDictionaryTests 9 { 10 [Test] 11 public void EnsureAddIntegrity() 12 { 13 TreeDictionary<int, int> dictionary = new(); 14 15 Assert.AreEqual(dictionary.Count, 0); 16 17 dictionary.Add(2, 7); 18 dictionary.Add(1, 4); 19 dictionary.Add(10, 2); 20 dictionary.Add(4, 1); 21 dictionary.Add(3, 2); 22 dictionary.Add(11, 2); 23 dictionary.Add(5, 2); 24 25 Assert.AreEqual(dictionary.Count, 7); 26 27 List<KeyValuePair<int, int>> list = dictionary.AsLevelOrderList(); 28 29 /* 30 * Tree Should Look as Follows After Rotations 31 * 32 * 2 33 * 1 4 34 * 3 10 35 * 5 11 36 * 37 */ 38 39 Assert.AreEqual(list.Count, dictionary.Count); 40 Assert.AreEqual(list[0].Key, 2); 41 Assert.AreEqual(list[1].Key, 1); 42 Assert.AreEqual(list[2].Key, 4); 43 Assert.AreEqual(list[3].Key, 3); 44 Assert.AreEqual(list[4].Key, 10); 45 Assert.AreEqual(list[5].Key, 5); 46 Assert.AreEqual(list[6].Key, 11); 47 } 48 49 [Test] 50 public void EnsureRemoveIntegrity() 51 { 52 TreeDictionary<int, int> dictionary = new(); 53 54 Assert.AreEqual(dictionary.Count, 0); 55 56 dictionary.Add(2, 7); 57 dictionary.Add(1, 4); 58 dictionary.Add(10, 2); 59 dictionary.Add(4, 1); 60 dictionary.Add(3, 2); 61 dictionary.Add(11, 2); 62 dictionary.Add(5, 2); 63 dictionary.Add(7, 2); 64 dictionary.Add(9, 2); 65 dictionary.Add(8, 2); 66 dictionary.Add(13, 2); 67 dictionary.Add(24, 2); 68 dictionary.Add(6, 2); 69 Assert.AreEqual(dictionary.Count, 13); 70 71 List<KeyValuePair<int, int>> list = dictionary.AsLevelOrderList(); 72 73 /* 74 * Tree Should Look as Follows After Rotations 75 * 76 * 4 77 * 2 10 78 * 1 3 7 13 79 * 5 9 11 24 80 * 6 8 81 */ 82 83 foreach (KeyValuePair<int, int> node in list) 84 { 85 Console.WriteLine($"{node.Key} -> {node.Value}"); 86 } 87 Assert.AreEqual(list.Count, dictionary.Count); 88 Assert.AreEqual(list[0].Key, 4); 89 Assert.AreEqual(list[1].Key, 2); 90 Assert.AreEqual(list[2].Key, 10); 91 Assert.AreEqual(list[3].Key, 1); 92 Assert.AreEqual(list[4].Key, 3); 93 Assert.AreEqual(list[5].Key, 7); 94 Assert.AreEqual(list[6].Key, 13); 95 Assert.AreEqual(list[7].Key, 5); 96 Assert.AreEqual(list[8].Key, 9); 97 Assert.AreEqual(list[9].Key, 11); 98 Assert.AreEqual(list[10].Key, 24); 99 Assert.AreEqual(list[11].Key, 6); 100 Assert.AreEqual(list[12].Key, 8); 101 102 list.Clear(); 103 104 dictionary.Remove(7); 105 106 /* 107 * Tree Should Look as Follows After Removal 108 * 109 * 4 110 * 2 10 111 * 1 3 6 13 112 * 5 9 11 24 113 * 8 114 */ 115 116 list = dictionary.AsLevelOrderList(); 117 foreach (KeyValuePair<int, int> node in list) 118 { 119 Console.WriteLine($"{node.Key} -> {node.Value}"); 120 } 121 Assert.AreEqual(list[0].Key, 4); 122 Assert.AreEqual(list[1].Key, 2); 123 Assert.AreEqual(list[2].Key, 10); 124 Assert.AreEqual(list[3].Key, 1); 125 Assert.AreEqual(list[4].Key, 3); 126 Assert.AreEqual(list[5].Key, 6); 127 Assert.AreEqual(list[6].Key, 13); 128 Assert.AreEqual(list[7].Key, 5); 129 Assert.AreEqual(list[8].Key, 9); 130 Assert.AreEqual(list[9].Key, 11); 131 Assert.AreEqual(list[10].Key, 24); 132 Assert.AreEqual(list[11].Key, 8); 133 134 list.Clear(); 135 136 dictionary.Remove(10); 137 138 list = dictionary.AsLevelOrderList(); 139 /* 140 * Tree Should Look as Follows After Removal 141 * 142 * 4 143 * 2 9 144 * 1 3 6 13 145 * 5 8 11 24 146 * 147 */ 148 foreach (KeyValuePair<int, int> node in list) 149 { 150 Console.WriteLine($"{node.Key} -> {node.Value}"); 151 } 152 Assert.AreEqual(list[0].Key, 4); 153 Assert.AreEqual(list[1].Key, 2); 154 Assert.AreEqual(list[2].Key, 9); 155 Assert.AreEqual(list[3].Key, 1); 156 Assert.AreEqual(list[4].Key, 3); 157 Assert.AreEqual(list[5].Key, 6); 158 Assert.AreEqual(list[6].Key, 13); 159 Assert.AreEqual(list[7].Key, 5); 160 Assert.AreEqual(list[8].Key, 8); 161 Assert.AreEqual(list[9].Key, 11); 162 Assert.AreEqual(list[10].Key, 24); 163 } 164 165 [Test] 166 public void EnsureOverwriteIntegrity() 167 { 168 TreeDictionary<int, int> dictionary = new(); 169 170 Assert.AreEqual(dictionary.Count, 0); 171 172 dictionary.Add(2, 7); 173 dictionary.Add(1, 4); 174 dictionary.Add(10, 2); 175 dictionary.Add(4, 1); 176 dictionary.Add(3, 2); 177 dictionary.Add(11, 2); 178 dictionary.Add(5, 2); 179 dictionary.Add(7, 2); 180 dictionary.Add(9, 2); 181 dictionary.Add(8, 2); 182 dictionary.Add(13, 2); 183 dictionary.Add(24, 2); 184 dictionary.Add(6, 2); 185 Assert.AreEqual(dictionary.Count, 13); 186 187 List<KeyValuePair<int, int>> list = dictionary.AsLevelOrderList(); 188 189 foreach (KeyValuePair<int, int> node in list) 190 { 191 Console.WriteLine($"{node.Key} -> {node.Value}"); 192 } 193 194 /* 195 * Tree Should Look as Follows After Rotations 196 * 197 * 4 198 * 2 10 199 * 1 3 7 13 200 * 5 9 11 24 201 * 6 8 202 */ 203 204 Assert.AreEqual(list.Count, dictionary.Count); 205 Assert.AreEqual(list[0].Key, 4); 206 Assert.AreEqual(list[1].Key, 2); 207 Assert.AreEqual(list[2].Key, 10); 208 Assert.AreEqual(list[3].Key, 1); 209 Assert.AreEqual(list[4].Key, 3); 210 Assert.AreEqual(list[5].Key, 7); 211 Assert.AreEqual(list[6].Key, 13); 212 Assert.AreEqual(list[7].Key, 5); 213 Assert.AreEqual(list[8].Key, 9); 214 Assert.AreEqual(list[9].Key, 11); 215 Assert.AreEqual(list[10].Key, 24); 216 Assert.AreEqual(list[11].Key, 6); 217 Assert.AreEqual(list[12].Key, 8); 218 219 Assert.AreEqual(list[4].Value, 2); 220 221 dictionary.Add(3, 4); 222 223 list = dictionary.AsLevelOrderList(); 224 225 Assert.AreEqual(list[4].Value, 4); 226 227 228 // Assure that none of the nodes locations have been modified. 229 Assert.AreEqual(list[0].Key, 4); 230 Assert.AreEqual(list[1].Key, 2); 231 Assert.AreEqual(list[2].Key, 10); 232 Assert.AreEqual(list[3].Key, 1); 233 Assert.AreEqual(list[4].Key, 3); 234 Assert.AreEqual(list[5].Key, 7); 235 Assert.AreEqual(list[6].Key, 13); 236 Assert.AreEqual(list[7].Key, 5); 237 Assert.AreEqual(list[8].Key, 9); 238 Assert.AreEqual(list[9].Key, 11); 239 Assert.AreEqual(list[10].Key, 24); 240 Assert.AreEqual(list[11].Key, 6); 241 Assert.AreEqual(list[12].Key, 8); 242 } 243 } 244 }