mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.DataStructures.Patricia/BranchNode.cs

   1 //
   2 // BranchNode.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 System;
  30 using System.Collections.Generic;
  31 using System.IO;
  32 using System.Text;
  33
  34 namespace Mono.CodeContracts.Static.DataStructures.Patricia
  35 {
  36     internal class BranchNode<T> : PatriciaTrieNode<T>
  37     {
  38         private readonly int count;
  39
  40         public readonly int Prefix;
  41         public readonly int BranchingBit;
  42         public readonly PatriciaTrieNode<T> Left;
  43         public readonly PatriciaTrieNode<T> Right;
  44
  45         public override int Key { get { return Prefix; } }
  46         public override int Count { get { return count; } }
  47
  48         public BranchNode(int prefix, int branchingBit, PatriciaTrieNode<T> left, PatriciaTrieNode<T> right)
  49         {
  50             Prefix = prefix;
  51             BranchingBit = branchingBit;
  52             Left = left;
  53             Right = right;
  54
  55             count = left.Count + right.Count;
  56         }
  57
  58         public override bool Contains(int key)
  59         {
  60             if (!MatchPrefix(key, Prefix, BranchingBit))
  61                 return false;
  62
  63             var child = IsZeroBitAt(key, BranchingBit) ? Left : Right;
  64
  65             return child.Contains(key);
  66         }
  67
  68         public override IImmutableIntMap<T> Add(int key, T value)
  69         {
  70             if (!MatchPrefix(key, Prefix, BranchingBit))
  71                 return Join(new LeafNode<T>(key, value), this);
  72
  73             if (IsZeroBitAt(key, BranchingBit))
  74                 return new BranchNode<T>(Prefix, BranchingBit, (PatriciaTrieNode<T>)Left.Add(key, value), Right);
  75
  76             return new BranchNode<T>(Prefix, BranchingBit, Left, (PatriciaTrieNode<T>)Right.Add(key, value));
  77         }
  78
  79         public override IImmutableIntMap<T> Remove(int key)
  80         {
  81             var left = Left;
  82             var right = Right;
  83             if (IsZeroBitAt(key, BranchingBit))
  84             {
  85                 left = (PatriciaTrieNode<T>)left.Remove(key);
  86                 if (left.Count == 0)
  87                     return right;
  88             }
  89             else
  90             {
  91                 right = (PatriciaTrieNode<T>)right.Remove(key);
  92                 if (right.Count == 0)
  93                     return left;
  94             }
  95
  96             return Join(left, right);
  97         }
  98
  99         public override void Visit(Action<T> action)
 100         {
 101             Left.Visit(action);
 102             Right.Visit(action);
 103         }
 104
 105         public override void Visit(Action<int, T> action)
 106         {
 107             Left.Visit(action);
 108             Right.Visit(action);
 109         }
 110
 111         public override T Lookup(int key)
 112         {
 113             BranchNode<T> current = this;
 114
 115             PatriciaTrieNode<T> child;
 116             do
 117             {
 118                 child = IsZeroBitAt(key, current.BranchingBit) ? current.Left : current.Right;
 119                 current = child as BranchNode<T>;
 120             }
 121             while (current != null);
 122
 123             return child.Lookup(key);
 124         }
 125
 126         protected internal override void FillKeysTo(List<int> list)
 127         {
 128             Left.FillKeysTo(list);
 129             Right.FillKeysTo(list);
 130         }
 131
 132         protected internal override void FillValuesTo(List<T> list)
 133         {
 134             Left.FillValuesTo(list);
 135             Right.FillValuesTo(list);
 136         }
 137
 138         protected internal override void AppendToBuilder(StringBuilder sb)
 139         {
 140             Left.AppendToBuilder(sb);
 141             Right.AppendToBuilder(sb);
 142         }
 143
 144         protected internal override void Dump(TextWriter tw, string prefix)
 145         {
 146             tw.WriteLine(prefix + "<Branch Prefix={0} BranchingBit={1}>", Prefix, BranchingBit);
 147             Left.Dump(tw, prefix + "  ");
 148             Right.Dump(tw, prefix + "  ");
 149             tw.WriteLine(prefix + "</Branch>");
 150         }
 151     }
 152 }