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

   1 //
   2 // PatriciaTrieNode.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     public abstract class PatriciaTrieNode<T> : IImmutableIntMap<T>
  37     {
  38         public T this[int key]
  39         {
  40             get { return this.Lookup(key); }
  41         }
  42
  43         public T Any { get; private set; }
  44
  45         public abstract bool Contains(int key);
  46
  47         public abstract int Key { get; }
  48         public abstract int Count { get; }
  49         public abstract IImmutableIntMap<T> Add(int key, T value);
  50         public abstract IImmutableIntMap<T> Remove(int key);
  51
  52         public abstract void Visit(Action<T> action);
  53         public abstract void Visit(Action<int, T> action);
  54
  55         public abstract T Lookup(int key);
  56
  57         public IEnumerable<int> Keys
  58         {
  59             get
  60             {
  61                 var list = new List<int>(this.Count);
  62                 FillKeysTo(list);
  63                 return list;
  64             }
  65         }
  66
  67         public IEnumerable<T> Values
  68         {
  69             get
  70             {
  71                 var list = new List<T>(this.Count);
  72                 FillValuesTo(list);
  73                 return list;
  74             }
  75         }
  76
  77         public void Dump(TextWriter tw)
  78         {
  79             Dump(tw, string.Empty);
  80         }
  81
  82         protected internal abstract void FillKeysTo(List<int> list);
  83         protected internal abstract void FillValuesTo(List<T> list);
  84         protected internal abstract void AppendToBuilder(StringBuilder sb);
  85         protected internal abstract void Dump(TextWriter tw, string prefix);
  86
  87         public override string ToString()
  88         {
  89             var sb = new StringBuilder();
  90             AppendToBuilder(sb);
  91             return sb.ToString();
  92         }
  93
  94         protected static IImmutableIntMap<T> Join(PatriciaTrieNode<T> left, PatriciaTrieNode<T> right)
  95         {
  96             int keyLeft = left.Key;
  97             int keyRight = right.Key;
  98
  99             int branchingBit = BranchingBit(keyLeft, keyRight);
 100             var prefix = MaskWithBit(keyLeft, branchingBit);
 101
 102             if (IsZeroBitAt(keyLeft, branchingBit))
 103                 return new BranchNode<T>(prefix, branchingBit, left, right);
 104
 105             return new BranchNode<T>(prefix, branchingBit, right, left);
 106         }
 107
 108         protected static bool IsZeroBitAt(int key, int branchingBit)
 109         {
 110             return (key & branchingBit) == 0;
 111         }
 112
 113         private static int BranchingBit(int left, int right)
 114         {
 115             return LowestBit(left ^ right);
 116         }
 117
 118         private static int LowestBit(int x)
 119         {
 120             return x & -x;
 121         }
 122
 123         private static int MaskWithBit(int key, int mask)
 124         {
 125             return key & (mask - 1);
 126         }
 127
 128         protected static bool MatchPrefix(int key, int prefix, int maskBit)
 129         {
 130             return MaskWithBit(key, maskBit) == prefix;
 131         }
 132     }
 133 }