mcs/class/Mono.CodeContracts/Test/Mono.CodeContracts.Static/PatriciaTrieTests.cs

   1 //
   2 // PatriciaTrieTests.cs
   3 //
   4 // Authors:
   5 //      Alexander Chebaturkin (chebaturkin@gmail.com)
   6 //
   7 // Copyright (C) 2012 Alexander Chebaturkin
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using Mono.CodeContracts.Static.DataStructures;
  30 using Mono.CodeContracts.Static.DataStructures.Patricia;
  31
  32 using NUnit.Framework;
  33
  34 namespace MonoTests.Mono.CodeContracts {
  35         [TestFixture]
  36         public class PatriciaTrieTests {
  37                 readonly IImmutableIntMap<string> empty = ImmutableIntMap<string>.Empty;
  38
  39                 [Test]
  40                 public void AddOnEmptyShouldCreateLeafNode ()
  41                 {
  42                         var one = this.empty.Add (1, "hello") as LeafNode<string>;
  43
  44                         Assert.That (one.Key, Is.EqualTo (1));
  45                         Assert.That (one.Value, Is.EqualTo ("hello"));
  46                         Assert.That (one.Count, Is.EqualTo (1));
  47                 }
  48
  49                 [Test]
  50                 public void AddOnLeafShouldCreateAnotherLeafIfKeysAreEqual ()
  51                 {
  52                         var leaf = new LeafNode<string> (1, "hello");
  53
  54                         var result = (LeafNode<string>) leaf.Add (1, "there");
  55
  56                         Assert.That (result.Key, Is.EqualTo (1));
  57                         Assert.That (result.Value, Is.EqualTo ("there"));
  58                         Assert.That (result.Count, Is.EqualTo (1));
  59                 }
  60
  61                 [Test]
  62                 public void AddOnLeafShouldCreateBranchIfKeysAreDifferent ()
  63                 {
  64                         var leaf = new LeafNode<string> (5, "hello"); //101
  65
  66                         var branch = (BranchNode<string>) leaf.Add (7, "there"); //111
  67
  68                         Assert.That (branch.Prefix, Is.EqualTo (1)); //x*1
  69                         Assert.That (branch.BranchingBit, Is.EqualTo (2)); //
  70                         Assert.That (branch.Left, Is.SameAs (leaf));
  71
  72                         var right = (branch.Right as LeafNode<string>);
  73                         Assert.That (right, Is.Not.Null);
  74                         Assert.That (right.Key, Is.EqualTo (7));
  75                         Assert.That (right.Value, Is.EqualTo ("there"));
  76                 }
  77
  78                 [Test]
  79                 public void RemoveFromBranchWithLeafKeyEqualToArgumentShouldStayAnotherChild ()
  80                 {
  81                         IImmutableIntMap<string> left = this.empty.Add (5, "hello");
  82                         IImmutableIntMap<string> branch = left.Add (7, "there");
  83
  84                         IImmutableIntMap<string> node1 = branch.Remove (7);
  85                         Assert.That (node1, Is.SameAs (left));
  86
  87                         IImmutableIntMap<string> node2 = branch.Remove (5);
  88                         Assert.That (node2 is LeafNode<string>);
  89                         Assert.That ((node2 as LeafNode<string>).Key, Is.EqualTo (7));
  90                         Assert.That ((node2 as LeafNode<string>).Value, Is.EqualTo ("there"));
  91                 }
  92
  93                 [Test]
  94                 public void RemoveOnEmptyShouldStayEmpty ()
  95                 {
  96                         var one = (EmptyNode<string>) this.empty.Remove (1);
  97
  98                         Assert.That (one, Is.SameAs (this.empty));
  99                 }
 100
 101                 [Test]
 102                 public void RemoveOnLeafShouldCreateEmptyIfKeysAreEqual ()
 103                 {
 104                         var leaf = new LeafNode<string> (1, "hello");
 105
 106                         var result = (EmptyNode<string>) leaf.Remove (1);
 107
 108                         Assert.That (result.Count, Is.EqualTo (0));
 109                 }
 110
 111                 [Test]
 112                 public void RemoveOnLeafShouldStayTheSameIfKeysAreDifferent ()
 113                 {
 114                         var leaf = new LeafNode<string> (1, "hello");
 115
 116                         var result = (LeafNode<string>) leaf.Remove (2);
 117
 118                         Assert.That (result, Is.SameAs (leaf));
 119                 }
 120         }
 121 }