mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.DataStructures/ImmutableMap.cs

   1 //
   2 // ImmutableMap.cs
   3 //
   4 // Authors:
   5 //      Alexander Chebaturkin (chebaturkin@gmail.com)
   6 //
   7 // Copyright (C) 2011 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.Linq;
  32
  33 namespace Mono.CodeContracts.Static.DataStructures {
  34         class ImmutableMap<K, V> : IImmutableMap<K, V>
  35                 where K : IEquatable<K> {
  36                 public static readonly ImmutableMap<K, V> Empty = new ImmutableMap<K, V> (ImmutableIntMap<Sequence<Pair<K, V>>>.Empty, 0, null);
  37
  38                 private readonly int count;
  39                 private readonly IImmutableIntMap<Sequence<Pair<K, V>>> immutable_int_map;
  40                 private readonly Sequence<K> keys;
  41
  42                 private ImmutableMap (IImmutableIntMap<Sequence<Pair<K, V>>> map, int count, Sequence<K> keys)
  43                 {
  44                         this.keys = keys;
  45                         this.count = count;
  46                         this.immutable_int_map = map;
  47                 }
  48
  49                 #region Implementation of IImmutableMap<K,V>
  50                 public V this [K key]
  51                 {
  52                         get
  53                         {
  54                             V value;
  55                             return TryGetValue (key, out value) ? value : default(V);
  56                         }
  57                 }
  58
  59             public bool TryGetValue (K key, out V value)
  60             {
  61                 for (Sequence<Pair<K, V>> list = this.immutable_int_map[key.GetHashCode ()]; list != null; list = list.Tail)
  62                 {
  63                     K k = list.Head.Key;
  64                     if (key.Equals (k))
  65                         return true.With (list.Head.Value, out value);
  66                 }
  67                 return false.Without (out value);
  68             }
  69
  70             public K AnyKey
  71                 {
  72                         get { return this.keys.Head; }
  73                 }
  74
  75                 public IEnumerable<K> Keys
  76                 {
  77                         get { return this.keys.AsEnumerable (); }
  78                 }
  79
  80                 public int Count
  81                 {
  82                         get { return this.immutable_int_map.Count; }
  83                 }
  84
  85                 public IImmutableMap<K, V> EmptyMap
  86                 {
  87                         get { return Empty; }
  88                 }
  89
  90                 public IImmutableMap<K, V> Add (K key, V value)
  91                 {
  92                         int hashCode = key.GetHashCode ();
  93                         Sequence<Pair<K, V>> cur = this.immutable_int_map [hashCode];
  94                         Sequence<Pair<K, V>> newList = Remove (cur, key).Cons (new Pair<K, V> (key, value));
  95                         int diff = newList.Length () - cur.Length ();
  96                         Sequence<K> newKeys = diff == 0 ? this.keys : this.keys.Cons (key);
  97
  98                         return new ImmutableMap<K, V> (this.immutable_int_map.Add (hashCode, newList), this.count + diff, newKeys);
  99                 }
 100
 101                 public IImmutableMap<K, V> Remove (K key)
 102                 {
 103                         int hashCode = key.GetHashCode ();
 104                         Sequence<Pair<K, V>> from = this.immutable_int_map [hashCode];
 105                         if (from == null)
 106                                 return this;
 107                         Sequence<Pair<K, V>> newList = Remove (from, key);
 108                         if (newList == from)
 109                                 return this;
 110
 111                         Sequence<K> newKeys = RemoveKey (key, this.keys);
 112                         if (newList == null)
 113                                 return new ImmutableMap<K, V> (this.immutable_int_map.Remove (hashCode), this.count - 1, newKeys);
 114                         return new ImmutableMap<K, V> (this.immutable_int_map.Add (hashCode, newList), this.count - 1, newKeys);
 115                 }
 116
 117                 public bool ContainsKey (K key)
 118                 {
 119                         return this.immutable_int_map [key.GetHashCode ()].AsEnumerable ().Any (pair => key.Equals (pair.Key));
 120                 }
 121
 122                 public void Visit (Func<K, V, VisitStatus> func)
 123                 {
 124                         this.immutable_int_map.Visit (list => {
 125                                                         foreach (var pair in list.AsEnumerable ())
 126                                                                 func (pair.Key, pair.Value);
 127                                                       });
 128                 }
 129
 130             private Sequence<Pair<K, V>> Remove (Sequence<Pair<K, V>> from, K key)
 131                 {
 132                         if (from == null)
 133                                 return null;
 134                         if (key.Equals (from.Head.Key))
 135                                 return from.Tail;
 136                         Sequence<Pair<K, V>> tail = Remove (from.Tail, key);
 137                         return tail == from.Tail ? from : tail.Cons (from.Head);
 138                 }
 139
 140                 private static Sequence<K> RemoveKey (K key, Sequence<K> keys)
 141                 {
 142                         if (keys == null)
 143                                 throw new InvalidOperationException ();
 144
 145                         if (key.Equals (keys.Head))
 146                                 return keys.Tail;
 147
 148                         return RemoveKey (key, keys.Tail).Cons (keys.Head);
 149                 }
 150                 #endregion
 151
 152         public IImmutableMapFactory<K, V> Factory ()
 153             {
 154                 return new MapFactory ();
 155             }
 156
 157         private class MapFactory : IImmutableMapFactory<K, V>
 158         {
 159             public IImmutableMap<K, V> Empty { get { return ImmutableMap<K,V>.Empty;}}
 160         }
 161         }
 162 }