mcs/class/Mono.C5/UserGuideExamples/MultiDictionary.cs

   1 /*
   2  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
   3
   4  Permission is hereby granted, free of charge, to any person obtaining a copy
   5  of this software and associated documentation files (the "Software"), to deal
   6  in the Software without restriction, including without limitation the rights
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  copies of the Software, and to permit persons to whom the Software is
   9  furnished to do so, subject to the following conditions:
  10
  11  The above copyright notice and this permission notice shall be included in
  12  all copies or substantial portions of the Software.
  13
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  SOFTWARE.
  21 */
  22
  23 // C5 example: 2006-01-29, 2006-06-26
  24
  25 // Compile with
  26 //   csc /r:C5.dll MultiDictionary.cs
  27
  28 using System;
  29 using C5;
  30 using SCG = System.Collections.Generic;
  31
  32 namespace MultiDictionaries {
  33
  34   class MyTest {
  35     public static void Main(String[] args) {
  36       MultiDictionary1.TestIt.Run();
  37       MultiDictionary2.TestIt.Run();
  38     }
  39   }
  40 }
  41
  42 // --------------------------------------------------
  43
  44 namespace MultiDictionary1 {
  45   class TestIt {
  46     public static void Run() {
  47       {
  48         MultiHashDictionary<int,String> mdict
  49           = new MultiHashDictionary<int,String>();
  50         mdict.Add(2, "to");
  51         mdict.Add(2, "deux");
  52         mdict.Add(2, "two");
  53         mdict.Add(20, "tyve");
  54         mdict.Add(20, "twenty");
  55         Console.WriteLine(mdict);
  56         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  57         Console.WriteLine("mdict.Count (keys) is {0}",
  58                           ((IDictionary<int,ICollection<String>>)mdict).Count);
  59         Console.WriteLine("mdict[2].Count is {0}", mdict[2].Count);
  60         mdict.Remove(20, "tyve");
  61         mdict.Remove(20, "twenty");
  62         Console.WriteLine(mdict);
  63         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  64         ICollection<String> zwei = new HashSet<String>();
  65         zwei.Add("zwei");
  66         mdict[2] = zwei;
  67         mdict[-2] = zwei;
  68         Console.WriteLine(mdict);
  69         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  70         zwei.Add("kaksi");
  71         Console.WriteLine(mdict);
  72         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  73         ICollection<String> empty = new HashSet<String>();
  74         mdict[0] = empty;
  75         Console.WriteLine(mdict);
  76         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  77         Console.WriteLine("mdict contains key 0: {0}", mdict.Contains(0));
  78         mdict.Remove(-2);
  79         Console.WriteLine(mdict);
  80         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  81         zwei.Remove("kaksi");
  82         Console.WriteLine(mdict);
  83         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  84         zwei.Clear();
  85         Console.WriteLine(mdict);
  86         Console.WriteLine("mdict.Count is {0}", mdict.Count);
  87         Console.WriteLine("------------------------------");
  88       }
  89     }
  90   }
  91
  92   // Here we implement a multivalued dictionary as a hash dictionary
  93   // from keys to value collections.  The value collections may have
  94   // set or bag semantics.
  95
  96   // The value collections are externally modifiable (as in Peter
  97   // Golde's PowerCollections library), and therefore:
  98   //
  99   //  * A value collection associated with a key may be null or
 100   //  non-empty.  Hence for correct semantics, the Contains(k) method
 101   //  must check that the value collection associated with a key is
 102   //  non-null and non-empty.
 103   //
 104   //  * A value collection may be shared between two or more keys.
 105   //
 106
 107   public class MultiHashDictionary<K,V> : HashDictionary<K, ICollection<V>> {
 108
 109     // Return total count of values associated with keys.  This basic
 110     // implementation simply sums over all value collections, and so
 111     // is a linear-time operation in the total number of values.
 112
 113     public new virtual int Count {
 114       get {
 115         int count = 0;
 116         foreach (KeyValuePair<K,ICollection<V>> entry in this)
 117           if (entry.Value != null)
 118             count += entry.Value.Count;
 119         return count;
 120       }
 121     }
 122
 123     public override Speed CountSpeed {
 124       get { return Speed.Linear; }
 125     }
 126
 127     // Add a (key,value) pair
 128
 129     public virtual void Add(K k, V v) {
 130       ICollection<V> values;
 131       if (!base.Find(k, out values) || values == null) {
 132         values = new HashSet<V>();
 133         Add(k, values);
 134       }
 135       values.Add(v);
 136     }
 137
 138     // Remove a single (key,value) pair, if present; return true if
 139     // anything was removed, else false
 140
 141     public virtual bool Remove(K k, V v) {
 142       ICollection<V> values;
 143       if (base.Find(k, out values) && values != null) {
 144         if (values.Remove(v)) {
 145           if (values.IsEmpty)
 146             base.Remove(k);
 147           return true;
 148         }
 149       }
 150       return false;
 151     }
 152
 153     // Determine whether key k is associated with a value
 154
 155     public override bool Contains(K k) {
 156       ICollection<V> values;
 157       return base.Find(k, out values) && values != null && !values.IsEmpty;
 158     }
 159
 160     // Determine whether each key in ks is associated with a value
 161
 162     public override bool ContainsAll<U>(SCG.IEnumerable<U> ks) {
 163       foreach (K k in ks)
 164         if (!Contains(k))
 165           return false;
 166       return true;
 167     }
 168
 169     // Get or set the value collection associated with key k
 170
 171     public override ICollection<V> this[K k] {
 172       get {
 173         ICollection<V> values;
 174         return base.Find(k, out values) && values != null ? values : new HashSet<V>();
 175       }
 176       set {
 177         base[k] = value;
 178       }
 179     }
 180
 181     // Inherited from base class HashDictionary<K,ICollection<V>>:
 182
 183     // Add(K k, ICollection<V> values)
 184     // AddAll(IEnumerable<KeyValuePair<K,ICollection<V>>> kvs)
 185     // Clear
 186     // Clone
 187     // Find(K k, out ICollection<V> values)
 188     // Find(ref K k, out ICollection<V> values)
 189     // FindOrAdd(K k, ref ICollection<V> values)
 190     // Remove(K k)
 191     // Remove(K k, out ICollection<V> values)
 192     // Update(K k, ICollection<V> values)
 193     // Update(K k, ICollection<V> values, out ICollection<V> oldValues)
 194     // UpdateOrAdd(K k, ICollection<V> values)
 195     // UpdateOrAdd(K k, ICollection<V> values, out ICollection<V> oldValues)
 196   }
 197 }
 198
 199 // --------------------------------------------------
 200
 201 namespace MultiDictionary2 {
 202
 203   class TestIt {
 204     public static void Run() {
 205       {
 206         MultiHashDictionary<int,String> mdict
 207           = new MultiHashDictionary<int,String>();
 208         mdict.Add(2, "to");
 209         mdict.Add(2, "deux");
 210         mdict.Add(2, "two");
 211         mdict.Add(20, "tyve");
 212         mdict.Add(20, "twenty");
 213         Console.WriteLine(mdict);
 214         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 215         Console.WriteLine("mdict.Count (keys) is {0}",
 216                           ((IDictionary<int,ICollection<String>>)mdict).Count);
 217         Console.WriteLine("mdict[2].Count is {0}", mdict[2].Count);
 218         mdict.Remove(20, "tyve");
 219         mdict.Remove(20, "twenty");
 220         Console.WriteLine(mdict);
 221         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 222         ICollection<String> zwei = new HashSet<String>();
 223         zwei.Add("zwei");
 224         mdict[2] = zwei;
 225         mdict[-2] = zwei;
 226         Console.WriteLine(mdict);
 227         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 228         zwei.Add("kaksi");
 229         Console.WriteLine(mdict);
 230         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 231         ICollection<String> empty = new HashSet<String>();
 232         mdict[0] = empty;
 233         Console.WriteLine(mdict);
 234         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 235         Console.WriteLine("mdict contains key 0: {0}", mdict.Contains(0));
 236         mdict.Remove(-2);
 237         Console.WriteLine(mdict);
 238         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 239         zwei.Remove("kaksi");
 240         Console.WriteLine(mdict);
 241         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 242         zwei.Clear();
 243         Console.WriteLine(mdict);
 244         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 245         Console.WriteLine("------------------------------");
 246       }
 247       {
 248         MultiHashDictionary<int,String,HashSet<String>> mdict
 249           = new MultiHashDictionary<int,String,HashSet<String>>();
 250         mdict.Add(2, "to");
 251         mdict.Add(2, "deux");
 252         mdict.Add(2, "two");
 253         mdict.Add(20, "tyve");
 254         mdict.Add(20, "twenty");
 255         Console.WriteLine(mdict);
 256         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 257         Console.WriteLine("mdict.Count (keys) is {0}",
 258                           ((IDictionary<int,HashSet<String>>)mdict).Count);
 259         Console.WriteLine("mdict[2].Count is {0}", mdict[2].Count);
 260         mdict.Remove(20, "tyve");
 261         mdict.Remove(20, "twenty");
 262         Console.WriteLine(mdict);
 263         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 264         HashSet<String> zwei = new HashSet<String>();
 265         zwei.Add("zwei");
 266         mdict[2] = zwei;
 267         mdict[-2] = zwei;
 268         Console.WriteLine(mdict);
 269         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 270         zwei.Add("kaksi");
 271         Console.WriteLine(mdict);
 272         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 273         HashSet<String> empty = new HashSet<String>();
 274         mdict[0] = empty;
 275         Console.WriteLine(mdict);
 276         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 277         Console.WriteLine("mdict contains key 0: {0}", mdict.Contains(0));
 278         mdict.Remove(-2);
 279         Console.WriteLine(mdict);
 280         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 281         zwei.Remove("kaksi");
 282         Console.WriteLine(mdict);
 283         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 284         zwei.Clear();
 285         Console.WriteLine(mdict);
 286         Console.WriteLine("mdict.Count is {0}", mdict.Count);
 287         Console.WriteLine("------------------------------");
 288       }
 289     }
 290   }
 291
 292   // This version of the multidictionary uses event listeners to make
 293   // the Count operation constant time.
 294
 295   // The total value count for the multidictionary is cached, and
 296   // event listeners on the value collections keep this cached count
 297   // updated.  Event listeners on the dictionary make sure that event
 298   // listeners are added to and removed from value collections.
 299
 300   public class MultiHashDictionary<K,V> : HashDictionary<K, ICollection<V>> {
 301     private int count = 0;      // Cached value count, updated by events only
 302
 303     private void IncrementCount(Object sender, ItemCountEventArgs<V> args) {
 304       count += args.Count;
 305     }
 306
 307     private void DecrementCount(Object sender, ItemCountEventArgs<V> args) {
 308       count -= args.Count;
 309     }
 310
 311     private void ClearedCount(Object sender, ClearedEventArgs args) {
 312       count -= args.Count;
 313     }
 314
 315     public MultiHashDictionary() {
 316       ItemsAdded +=
 317         delegate(Object sender, ItemCountEventArgs<KeyValuePair<K,ICollection<V>>> args) {
 318           ICollection<V> values = args.Item.Value;
 319           if (values != null) {
 320             count += values.Count;
 321             values.ItemsAdded += IncrementCount;
 322             values.ItemsRemoved += DecrementCount;
 323             values.CollectionCleared += ClearedCount;
 324           }
 325         };
 326       ItemsRemoved +=
 327         delegate(Object sender, ItemCountEventArgs<KeyValuePair<K,ICollection<V>>> args) {
 328           ICollection<V> values = args.Item.Value;
 329           if (values != null) {
 330             count -= values.Count;
 331             values.ItemsAdded -= IncrementCount;
 332             values.ItemsRemoved -= DecrementCount;
 333             values.CollectionCleared -= ClearedCount;
 334           }
 335         };
 336     }
 337
 338     // Return total count of values associated with keys.
 339
 340     public new virtual int Count {
 341       get {
 342         return count;
 343       }
 344     }
 345
 346     public override Speed CountSpeed {
 347       get { return Speed.Constant; }
 348     }
 349
 350     // Add a (key,value) pair
 351
 352     public virtual void Add(K k, V v) {
 353       ICollection<V> values;
 354       if (!base.Find(k, out values) || values == null) {
 355         values = new HashSet<V>();
 356         Add(k, values);
 357       }
 358       values.Add(v);
 359     }
 360
 361     // Remove a single (key,value) pair, if present; return true if
 362     // anything was removed, else false
 363
 364     public virtual bool Remove(K k, V v) {
 365       ICollection<V> values;
 366       if (base.Find(k, out values) && values != null) {
 367         if (values.Remove(v)) {
 368           if (values.IsEmpty)
 369             base.Remove(k);
 370           return true;
 371         }
 372       }
 373       return false;
 374     }
 375
 376     // Determine whether key k is associated with a value
 377
 378     public override bool Contains(K k) {
 379       ICollection<V> values;
 380       return Find(k, out values) && values != null && !values.IsEmpty;
 381     }
 382
 383     // Determine whether each key in ks is associated with a value
 384
 385     public override bool ContainsAll<U>(SCG.IEnumerable<U> ks) {
 386       foreach (K k in ks)
 387         if (!Contains(k))
 388           return false;
 389       return true;
 390     }
 391
 392     // Get or set the value collection associated with key k
 393
 394     public override ICollection<V> this[K k] {
 395       get {
 396         ICollection<V> values;
 397         return base.Find(k, out values) && values != null ? values : new HashSet<V>();
 398       }
 399       set {
 400         base[k] = value;
 401       }
 402     }
 403
 404     // Clearing the multidictionary should remove event listeners
 405
 406     public override void Clear() {
 407       foreach (ICollection<V> values in Values)
 408         if (values != null) {
 409           count -= values.Count;
 410           values.ItemsAdded -= IncrementCount;
 411           values.ItemsRemoved -= DecrementCount;
 412           values.CollectionCleared -= ClearedCount;
 413         }
 414       base.Clear();
 415     }
 416   }
 417
 418   // --------------------------------------------------
 419
 420   // This version of the multidictionary also uses event listeners to
 421   // make the Count operation constant time.
 422
 423   // The difference relative to the preceding version is that each
 424   // value collection must be an instance of some type VS that has an
 425   // argumentless constructor and that implements ICollection<V>.
 426   // This provides additional flexibility: The creator of a
 427   // multidictionary instance can determine the collection class VC
 428   // used for value collections, instead of having to put up with the
 429   // choice made by the multidictionary implementation.
 430
 431   public class MultiHashDictionary<K,V,VC> : HashDictionary<K, VC>
 432     where VC : ICollection<V>, new()
 433   {
 434     private int count = 0;      // Cached value count, updated by events only
 435
 436     private void IncrementCount(Object sender, ItemCountEventArgs<V> args) {
 437       count += args.Count;
 438     }
 439
 440     private void DecrementCount(Object sender, ItemCountEventArgs<V> args) {
 441       count -= args.Count;
 442     }
 443
 444     private void ClearedCount(Object sender, ClearedEventArgs args) {
 445       count -= args.Count;
 446     }
 447
 448     public MultiHashDictionary() {
 449       ItemsAdded +=
 450         delegate(Object sender, ItemCountEventArgs<KeyValuePair<K,VC>> args) {
 451           VC values = args.Item.Value;
 452           if (values != null) {
 453             count += values.Count;
 454             values.ItemsAdded += IncrementCount;
 455             values.ItemsRemoved += DecrementCount;
 456             values.CollectionCleared += ClearedCount;
 457           }
 458         };
 459       ItemsRemoved +=
 460         delegate(Object sender, ItemCountEventArgs<KeyValuePair<K,VC>> args) {
 461           VC values = args.Item.Value;
 462           if (values != null) {
 463             count -= values.Count;
 464             values.ItemsAdded -= IncrementCount;
 465             values.ItemsRemoved -= DecrementCount;
 466             values.CollectionCleared -= ClearedCount;
 467           }
 468         };
 469     }
 470
 471     // Return total count of values associated with keys.
 472
 473     public new virtual int Count {
 474       get {
 475         return count;
 476       }
 477     }
 478
 479     public override Speed CountSpeed {
 480       get { return Speed.Constant; }
 481     }
 482
 483     // Add a (key,value) pair
 484
 485     public virtual void Add(K k, V v) {
 486       VC values;
 487       if (!base.Find(k, out values) || values == null) {
 488         values = new VC();
 489         Add(k, values);
 490       }
 491       values.Add(v);
 492     }
 493
 494     // Remove a single (key,value) pair, if present; return true if
 495     // anything was removed, else false
 496
 497     public virtual bool Remove(K k, V v) {
 498       VC values;
 499       if (base.Find(k, out values) && values != null) {
 500         if (values.Remove(v)) {
 501           if (values.IsEmpty)
 502             base.Remove(k);
 503           return true;
 504         }
 505       }
 506       return false;
 507     }
 508
 509     // Determine whether key k is associated with a value
 510
 511     public override bool Contains(K k) {
 512       VC values;
 513       return Find(k, out values) && values != null && !values.IsEmpty;
 514     }
 515
 516     // Determine whether each key in ks is associated with a value
 517
 518     public override bool ContainsAll<U>(SCG.IEnumerable<U> ks) {
 519       foreach (K k in ks)
 520         if (!Contains(k))
 521           return false;
 522       return true;
 523     }
 524
 525     // Get or set the value collection associated with key k
 526
 527     public override VC this[K k] {
 528       get {
 529         VC values;
 530         return base.Find(k, out values) && values != null ? values : new VC();
 531       }
 532       set {
 533         base[k] = value;
 534       }
 535     }
 536
 537     public override void Clear() {
 538       foreach (VC values in Values)
 539         if (values != null) {
 540           count -= values.Count;
 541           values.ItemsAdded -= IncrementCount;
 542           values.ItemsRemoved -= DecrementCount;
 543           values.CollectionCleared -= ClearedCount;
 544         }
 545       base.Clear();
 546     }
 547   }
 548 }