mcs/class/Mono.C5/current/Test/Sorting.cs

   1 /*\r
   2  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
   3  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   4  of this software and associated documentation files (the "Software"), to deal\r
   5  in the Software without restriction, including without limitation the rights\r
   6  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   7  copies of the Software, and to permit persons to whom the Software is\r
   8  furnished to do so, subject to the following conditions:\r
   9  \r
  10  The above copyright notice and this permission notice shall be included in\r
  11  all copies or substantial portions of the Software.\r
  12  \r
  13  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  14  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  15  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  16  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  17  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  18  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  19  SOFTWARE.\r
  20 */\r
  21 \r
  22 using System;\r
  23 using C5;\r
  24 using NUnit.Framework;\r
  25 using SCG = System.Collections.Generic;\r
  26 \r
  27 namespace C5UnitTests.SortingTests\r
  28 {\r
  29         [TestFixture]\r
  30         public class SortRandom\r
  31         {\r
  32                 IC ic;\r
  33 \r
  34                 Random ran;\r
  35 \r
  36                 int[] a;\r
  37 \r
  38                 int length;\r
  39 \r
  40 \r
  41                 [SetUp]\r
  42                 public void Init()\r
  43                 {\r
  44                         ic = new IC();\r
  45                         ran = new Random(3456);\r
  46                         length = 100000;\r
  47                         a = new int[length];\r
  48                         for (int i = 0; i < length; i++)\r
  49                                 a[i] = ran.Next();\r
  50                 }\r
  51 \r
  52 \r
  53                 [Test]\r
  54                 public void HeapSort()\r
  55                 {\r
  56                         Sorting.HeapSort<int>(a, 0, length, ic);\r
  57                         for (int i = 1; i < length; i++)\r
  58                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
  59                 }\r
  60 \r
  61 \r
  62                 [Test]\r
  63                 public void IntroSort()\r
  64                 {\r
  65                         Sorting.IntroSort<int>(a, 0, length, ic);\r
  66                         for (int i = 1; i < length; i++)\r
  67                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
  68                 }\r
  69 \r
  70 \r
  71                 [Test]\r
  72                 public void InsertionSort()\r
  73                 {\r
  74                         length = 1000;\r
  75                         Sorting.InsertionSort<int>(a, 0, length, ic);\r
  76                         for (int i = 1; i < length; i++)\r
  77                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
  78 \r
  79                         Sorting.InsertionSort<int>(a, length, 2 * length, ic);\r
  80                         for (int i = length + 1; i < 2 * length; i++)\r
  81                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
  82                 }\r
  83 \r
  84 \r
  85                 [TearDown]\r
  86                 public void Dispose() { ic = null; }\r
  87         }\r
  88 \r
  89 \r
  90 \r
  91         [TestFixture]\r
  92         public class SortRandomDuplicates\r
  93         {\r
  94                 IC ic;\r
  95 \r
  96                 Random ran;\r
  97 \r
  98                 int[] a;\r
  99 \r
 100                 int length;\r
 101 \r
 102 \r
 103                 [SetUp]\r
 104                 public void Init()\r
 105                 {\r
 106                         ic = new IC();\r
 107                         ran = new Random(3456);\r
 108                         length = 100000;\r
 109                         a = new int[length];\r
 110                         for (int i = 0; i < length; i++)\r
 111                                 a[i] = ran.Next(3, 23);\r
 112                 }\r
 113 \r
 114 \r
 115                 [Test]\r
 116                 public void HeapSort()\r
 117                 {\r
 118                         Sorting.HeapSort<int>(a, 0, length, ic);\r
 119                         for (int i = 1; i < length; i++)\r
 120                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 121                 }\r
 122 \r
 123 \r
 124                 [Test]\r
 125                 public void IntroSort()\r
 126                 {\r
 127                         Sorting.IntroSort<int>(a, 0, length, ic);\r
 128                         for (int i = 1; i < length; i++)\r
 129                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 130                 }\r
 131 \r
 132 \r
 133                 [Test]\r
 134                 public void InsertionSort()\r
 135                 {\r
 136                         length = 1000;\r
 137                         Sorting.InsertionSort<int>(a, 0, length, ic);\r
 138                         for (int i = 1; i < length; i++)\r
 139                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 140 \r
 141                         Sorting.InsertionSort<int>(a, length, 2 * length, ic);\r
 142                         for (int i = length + 1; i < 2 * length; i++)\r
 143                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 144                 }\r
 145 \r
 146 \r
 147                 [TearDown]\r
 148                 public void Dispose() { ic = null; a = null; ran = null; }\r
 149         }\r
 150 \r
 151 \r
 152 \r
 153         [TestFixture]\r
 154         public class SortIncreasing\r
 155         {\r
 156                 IC ic;\r
 157 \r
 158                 int[] a;\r
 159 \r
 160                 int length;\r
 161 \r
 162 \r
 163                 [SetUp]\r
 164                 public void Init()\r
 165                 {\r
 166                         ic = new IC();\r
 167                         length = 100000;\r
 168                         a = new int[length];\r
 169                         for (int i = 0; i < length; i++)\r
 170                                 a[i] = i;\r
 171                 }\r
 172 \r
 173 \r
 174                 [Test]\r
 175                 public void HeapSort()\r
 176                 {\r
 177                         Sorting.HeapSort<int>(a, 0, length, ic);\r
 178                         for (int i = 1; i < length; i++)\r
 179                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 180                 }\r
 181 \r
 182 \r
 183                 [Test]\r
 184                 public void IntroSort()\r
 185                 {\r
 186                         Sorting.IntroSort<int>(a, 0, length, ic);\r
 187                         for (int i = 1; i < length; i++)\r
 188                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 189                 }\r
 190 \r
 191 \r
 192                 [Test]\r
 193                 public void InsertionSort()\r
 194                 {\r
 195                         length = 1000;\r
 196                         Sorting.InsertionSort<int>(a, 0, length, ic);\r
 197                         for (int i = 1; i < length; i++)\r
 198                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 199 \r
 200                         Sorting.InsertionSort<int>(a, length, 2 * length, ic);\r
 201                         for (int i = length + 1; i < 2 * length; i++)\r
 202                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 203                 }\r
 204 \r
 205 \r
 206                 [TearDown]\r
 207                 public void Dispose() { ic = null; a = null; }\r
 208         }\r
 209 \r
 210 \r
 211 \r
 212         [TestFixture]\r
 213         public class SortDecreasing\r
 214         {\r
 215                 IC ic;\r
 216 \r
 217                 int[] a;\r
 218 \r
 219                 int length;\r
 220 \r
 221 \r
 222                 [SetUp]\r
 223                 public void Init()\r
 224                 {\r
 225                         ic = new IC();\r
 226                         length = 100000;\r
 227                         a = new int[length];\r
 228                         for (int i = 0; i < length; i++)\r
 229                                 a[i] = -i;\r
 230                 }\r
 231 \r
 232 \r
 233                 [Test]\r
 234                 public void HeapSort()\r
 235                 {\r
 236                         Sorting.HeapSort<int>(a, 0, length, ic);\r
 237                         for (int i = 1; i < length; i++)\r
 238                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 239                 }\r
 240 \r
 241 \r
 242                 [Test]\r
 243                 public void IntroSort()\r
 244                 {\r
 245                         Sorting.IntroSort<int>(a, 0, length, ic);\r
 246                         for (int i = 1; i < length; i++)\r
 247                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 248                 }\r
 249 \r
 250 \r
 251                 [Test]\r
 252                 public void InsertionSort()\r
 253                 {\r
 254                         length = 1000;\r
 255                         Sorting.InsertionSort<int>(a, 0, length, ic);\r
 256                         for (int i = 1; i < length; i++)\r
 257                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 258 \r
 259                         Sorting.InsertionSort<int>(a, length, 2 * length, ic);\r
 260                         for (int i = length + 1; i < 2 * length; i++)\r
 261                                 Assert.IsTrue(a[i - 1] <= a[i], "Inversion at " + i);\r
 262                 }\r
 263 \r
 264 \r
 265                 [TearDown]\r
 266                 public void Dispose() { ic = null; a = null; }\r
 267         }\r
 268 }