mcs/class/System/System.Collections.Generic/SortedSet.cs

   1 //
   2 // SortedSet.cs
   3 //
   4 // Authors:
   5 //  Jb Evain  <jbevain@novell.com>
   6 //
   7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
   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;
  31 using System.Collections.Generic;
  32 using System.Linq;
  33 using System.Runtime.Serialization;
  34 using System.Runtime.InteropServices;
  35 using System.Security;
  36 using System.Security.Permissions;
  37 using System.Diagnostics;
  38
  39 // SortedSet is basically implemented as a reduction of SortedDictionary<K, V>
  40
  41 #if NET_4_0
  42
  43 namespace System.Collections.Generic {
  44
  45         [Serializable]
  46         [DebuggerDisplay ("Count={Count}")]
  47         [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
  48         public class SortedSet<T> : ISet<T>, ICollection, ISerializable, IDeserializationCallback
  49         {
  50                 class Node : RBTree.Node {
  51
  52                         public T item;
  53
  54                         public Node (T item)
  55                         {
  56                                 this.item = item;
  57                         }
  58
  59                         public override void SwapValue (RBTree.Node other)
  60                         {
  61                                 var o = (Node) other;
  62                                 var i = this.item;
  63                                 this.item = o.item;
  64                                 o.item = i;
  65                         }
  66                 }
  67
  68                 class NodeHelper : RBTree.INodeHelper<T> {
  69
  70                         static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
  71
  72                         public IComparer<T> comparer;
  73
  74                         public int Compare (T item, RBTree.Node node)
  75                         {
  76                                 return comparer.Compare (item, ((Node) node).item);
  77                         }
  78
  79                         public RBTree.Node CreateNode (T item)
  80                         {
  81                                 return new Node (item);
  82                         }
  83
  84                         NodeHelper (IComparer<T> comparer)
  85                         {
  86                                 this.comparer = comparer;
  87                         }
  88
  89                         public static NodeHelper GetHelper (IComparer<T> comparer)
  90                         {
  91                                 if (comparer == null || comparer == Comparer<T>.Default)
  92                                         return Default;
  93
  94                                 return new NodeHelper (comparer);
  95                         }
  96                 }
  97
  98                 RBTree tree;
  99                 NodeHelper helper;
 100                 SerializationInfo si;
 101
 102                 public SortedSet ()
 103                         : this (Comparer<T>.Default)
 104                 {
 105                 }
 106
 107                 public SortedSet (IEnumerable<T> collection)
 108                         : this (collection, Comparer<T>.Default)
 109                 {
 110                 }
 111
 112                 public SortedSet (IEnumerable<T> collection, IComparer<T> comparer)
 113                         : this (comparer)
 114                 {
 115                         if (collection == null)
 116                                 throw new ArgumentNullException ("collection");
 117
 118                         foreach (var item in collection)
 119                                 Add (item);
 120                 }
 121
 122                 public SortedSet (IComparer<T> comparer)
 123                 {
 124                         this.helper = NodeHelper.GetHelper (comparer);
 125                         this.tree = new RBTree (this.helper);
 126                 }
 127
 128                 protected SortedSet (SerializationInfo info, StreamingContext context)
 129                 {
 130                         this.si = info;
 131                 }
 132
 133                 public IComparer<T> Comparer {
 134                         get { return helper.comparer; }
 135                 }
 136
 137                 public int Count {
 138                         get { return tree.Count; }
 139                 }
 140
 141                 public T Max {
 142                         get { return GetMax (); }
 143                 }
 144
 145                 public T Min {
 146                         get {  return GetMin (); }
 147                 }
 148
 149                 internal virtual T GetMax ()
 150                 {
 151                         if (tree.Count == 0)
 152                                 return default (T);
 153
 154                         return GetItem (tree.Count - 1);
 155                 }
 156
 157                 internal virtual T GetMin ()
 158                 {
 159                         if (tree.Count == 0)
 160                                 return default (T);
 161
 162                         return GetItem (0);
 163                 }
 164
 165                 T GetItem (int index)
 166                 {
 167                         return ((Node) tree [index]).item;
 168                 }
 169
 170                 public bool Add (T item)
 171                 {
 172                         return TryAdd (item);
 173                 }
 174
 175                 internal virtual bool TryAdd (T item)
 176                 {
 177                         var node = new Node (item);
 178                         return tree.Intern (item, node) == node;
 179                 }
 180
 181                 public virtual void Clear ()
 182                 {
 183                         tree.Clear ();
 184                 }
 185
 186                 public virtual bool Contains (T item)
 187                 {
 188                         return tree.Lookup (item) != null;
 189                 }
 190
 191                 public void CopyTo (T [] array)
 192                 {
 193                         CopyTo (array, 0, Count);
 194                 }
 195
 196                 public void CopyTo (T [] array, int index)
 197                 {
 198                         CopyTo (array, index, Count);
 199                 }
 200
 201                 public void CopyTo (T [] array, int index, int count)
 202                 {
 203                         if (array == null)
 204                                 throw new ArgumentNullException ("array");
 205                         if (index < 0)
 206                                 throw new ArgumentOutOfRangeException ("index");
 207                         if (index > array.Length)
 208                                 throw new ArgumentException ("index larger than largest valid index of array");
 209                         if (array.Length - index < count)
 210                                 throw new ArgumentException ("destination array cannot hold the requested elements");
 211
 212                         foreach (Node node in tree) {
 213                                 if (count-- == 0)
 214                                         break;
 215
 216                                 array [index++] = node.item;
 217                         }
 218                 }
 219
 220                 public bool Remove (T item)
 221                 {
 222                         return TryRemove (item);
 223                 }
 224
 225                 internal virtual bool TryRemove (T item)
 226                 {
 227                         return tree.Remove (item) != null;
 228                 }
 229
 230                 public int RemoveWhere (Predicate<T> match)
 231                 {
 232                         var array = ToArray ();
 233
 234                         int count = 0;
 235                         foreach (var item in array) {
 236                                 if (!match (item))
 237                                         continue;
 238
 239                                 Remove (item);
 240                                 count++;
 241                         }
 242
 243                         return count;
 244                 }
 245
 246                 public IEnumerable<T> Reverse ()
 247                 {
 248                         for (int i = tree.Count - 1; i >= 0; i--)
 249                                 yield return GetItem (i);
 250                 }
 251
 252                 T [] ToArray ()
 253                 {
 254                         var array = new T [this.Count];
 255                         CopyTo (array);
 256                         return array;
 257                 }
 258
 259                 public Enumerator GetEnumerator ()
 260                 {
 261                         return new Enumerator (this);
 262                 }
 263
 264                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 265                 {
 266                         return new Enumerator (this);
 267                 }
 268
 269                 IEnumerator IEnumerable.GetEnumerator ()
 270                 {
 271                         return new Enumerator (this);
 272                 }
 273
 274                 public static IEqualityComparer<SortedSet<T>> CreateSetComparer ()
 275                 {
 276                         return CreateSetComparer (EqualityComparer<T>.Default);
 277                 }
 278
 279                 [MonoTODO]
 280                 public static IEqualityComparer<SortedSet<T>> CreateSetComparer (IEqualityComparer<T> memberEqualityComparer)
 281                 {
 282                         throw new NotImplementedException ();
 283                 }
 284
 285                 [MonoTODO]
 286                 protected virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 287                 {
 288                         throw new NotImplementedException ();
 289                 }
 290
 291                 void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
 292                 {
 293                         GetObjectData (info, context);
 294                 }
 295
 296                 [MonoTODO]
 297                 protected virtual void OnDeserialization (object sender)
 298                 {
 299                         if (si == null)
 300                                 return;
 301
 302                         throw new NotImplementedException ();
 303                 }
 304
 305                 void IDeserializationCallback.OnDeserialization (object sender)
 306                 {
 307                         OnDeserialization (sender);
 308                 }
 309
 310                 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
 311                 public void ExceptWith (IEnumerable<T> other)
 312                 {
 313                         CheckArgumentNotNull (other, "other");
 314                         foreach (T item in other)
 315                                 Remove (item);
 316                 }
 317
 318                 public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
 319                 {
 320                         if (Comparer.Compare (lowerValue, upperValue) > 0)
 321                                 throw new ArgumentException ("The lowerValue is bigger than upperValue");
 322
 323                         return new SortedSubSet (this, lowerValue, upperValue);
 324                 }
 325
 326                 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
 327                 public virtual void IntersectWith (IEnumerable<T> other)
 328                 {
 329                         CheckArgumentNotNull (other, "other");
 330
 331                         RBTree newtree = new RBTree (helper);
 332                         foreach (T item in other) {
 333                                 var node = tree.Remove (item);
 334                                 if (node != null)
 335                                         newtree.Intern (item, node);
 336                         }
 337                         tree = newtree;
 338                 }
 339
 340                 public bool IsProperSubsetOf (IEnumerable<T> other)
 341                 {
 342                         CheckArgumentNotNull (other, "other");
 343
 344                         if (Count == 0) {
 345                                 foreach (T item in other)
 346                                         return true; // this idiom means: if 'other' is non-empty, return true
 347                                 return false;
 348                         }
 349
 350                         return is_subset_of (other, true);
 351                 }
 352
 353                 public bool IsProperSupersetOf (IEnumerable<T> other)
 354                 {
 355                         CheckArgumentNotNull (other, "other");
 356
 357                         if (Count == 0)
 358                                 return false;
 359
 360                         return is_superset_of (other, true);
 361                 }
 362
 363                 public bool IsSubsetOf (IEnumerable<T> other)
 364                 {
 365                         CheckArgumentNotNull (other, "other");
 366
 367                         if (Count == 0)
 368                                 return true;
 369
 370                         return is_subset_of (other, false);
 371                 }
 372
 373                 public bool IsSupersetOf (IEnumerable<T> other)
 374                 {
 375                         CheckArgumentNotNull (other, "other");
 376
 377                         if (Count == 0) {
 378                                 foreach (T item in other)
 379                                         return false; // this idiom means: if 'other' is non-empty, return false
 380                                 return true;
 381                         }
 382
 383                         return is_superset_of (other, false);
 384                 }
 385
 386                 // Precondition: Count != 0, other != null
 387                 bool is_subset_of (IEnumerable<T> other, bool proper)
 388                 {
 389                         SortedSet<T> that = nodups (other);
 390
 391                         if (Count > that.Count)
 392                                 return false;
 393                         // Count != 0 && Count <= that.Count => that.Count != 0
 394                         if (proper && Count == that.Count)
 395                                 return false;
 396                         return that.covers (this);
 397                 }
 398
 399                 // Precondition: Count != 0, other != null
 400                 bool is_superset_of (IEnumerable<T> other, bool proper)
 401                 {
 402                         SortedSet<T> that = nodups (other);
 403
 404                         if (that.Count == 0)
 405                                 return true;
 406                         if (Count < that.Count)
 407                                 return false;
 408                         if (proper && Count == that.Count)
 409                                 return false;
 410                         return this.covers (that);
 411                 }
 412
 413                 public bool Overlaps (IEnumerable<T> other)
 414                 {
 415                         CheckArgumentNotNull (other, "other");
 416
 417                         if (Count == 0)
 418                                 return false;
 419
 420                         // Don't use 'nodups' here.  Only optimize the SortedSet<T> case
 421                         SortedSet<T> that = other as SortedSet<T>;
 422                         if (that != null && that.Comparer != Comparer)
 423                                 that = null;
 424
 425                         if (that != null)
 426                                 return that.Count != 0 && overlaps (that);
 427
 428                         foreach (T item in other)
 429                                 if (Contains (item))
 430                                         return true;
 431                         return false;
 432                 }
 433
 434                 public bool SetEquals (IEnumerable<T> other)
 435                 {
 436                         CheckArgumentNotNull (other, "other");
 437
 438                         if (Count == 0) {
 439                                 foreach (T item in other)
 440                                         return false;
 441                                 return true;
 442                         }
 443
 444                         SortedSet<T> that = nodups (other);
 445
 446                         if (Count != that.Count)
 447                                 return false;
 448
 449                         using (var t = that.GetEnumerator ()) {
 450                                 foreach (T item in this) {
 451                                         if (!t.MoveNext ())
 452                                                 throw new SystemException ("count wrong somewhere: this longer than that");
 453                                         if (Comparer.Compare (item, t.Current) != 0)
 454                                                 return false;
 455                                 }
 456                                 if (t.MoveNext ())
 457                                         throw new SystemException ("count wrong somewhere: this shorter than that");
 458                                 return true;
 459                         }
 460                 }
 461
 462                 SortedSet<T> nodups (IEnumerable<T> other)
 463                 {
 464                         SortedSet<T> that = other as SortedSet<T>;
 465                         if (that != null && that.Comparer == Comparer)
 466                                 return that;
 467                         return new SortedSet<T> (other, Comparer);
 468                 }
 469
 470                 bool covers (SortedSet<T> that)
 471                 {
 472                         using (var t = that.GetEnumerator ()) {
 473                                 if (!t.MoveNext ())
 474                                         return true;
 475                                 foreach (T item in this) {
 476                                         int cmp = Comparer.Compare (item, t.Current);
 477                                         if (cmp > 0)
 478                                                 return false;
 479                                         if (cmp == 0 && !t.MoveNext ())
 480                                                 return true;
 481                                 }
 482                                 return false;
 483                         }
 484                 }
 485
 486                 bool overlaps (SortedSet<T> that)
 487                 {
 488                         using (var t = that.GetEnumerator ()) {
 489                                 if (!t.MoveNext ())
 490                                         return false;
 491                                 foreach (T item in this) {
 492                                         int cmp;
 493                                         while ((cmp = Comparer.Compare (item, t.Current)) > 0) {
 494                                                 if (!t.MoveNext ())
 495                                                         return false;
 496                                         }
 497                                         if (cmp == 0)
 498                                                 return true;
 499                                 }
 500                                 return false;
 501                         }
 502                 }
 503
 504                 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
 505                 public void SymmetricExceptWith (IEnumerable<T> other)
 506                 {
 507                         SortedSet<T> that_minus_this = new SortedSet<T> (Comparer);
 508
 509                         // compute this - that and that - this in parallel
 510                         foreach (T item in nodups (other))
 511                                 if (!Remove (item))
 512                                         that_minus_this.Add (item);
 513
 514                         UnionWith (that_minus_this);
 515                 }
 516
 517                 [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
 518                 public void UnionWith (IEnumerable<T> other)
 519                 {
 520                         CheckArgumentNotNull (other, "other");
 521
 522                         foreach (T item in other)
 523                                 Add (item);
 524                 }
 525
 526                 static void CheckArgumentNotNull (object arg, string name)
 527                 {
 528                         if (arg == null)
 529                                 throw new ArgumentNullException (name);
 530                 }
 531
 532                 void ICollection<T>.Add (T item)
 533                 {
 534                         Add (item);
 535                 }
 536
 537                 void ICollection<T>.CopyTo (T [] array, int index)
 538                 {
 539                         CopyTo (array, index, Count);
 540                 }
 541
 542                 bool ICollection<T>.IsReadOnly {
 543                         get { return false; }
 544                 }
 545
 546                 void ICollection.CopyTo (Array array, int index)
 547                 {
 548                         if (Count == 0)
 549                                 return;
 550                         if (array == null)
 551                                 throw new ArgumentNullException ("array");
 552                         if (index < 0 || array.Length <= index)
 553                                 throw new ArgumentOutOfRangeException ("index");
 554                         if (array.Length - index < Count)
 555                                 throw new ArgumentException ();
 556
 557                         foreach (Node node in tree)
 558                                 array.SetValue (node.item, index++);
 559                 }
 560
 561                 bool ICollection.IsSynchronized {
 562                         get { return false; }
 563                 }
 564
 565                 // TODO:Is this correct? If this is wrong,please fix.
 566                 object ICollection.SyncRoot {
 567                         get { return this; }
 568                 }
 569
 570                 [Serializable]
 571                 public struct Enumerator : IEnumerator<T>, IDisposable {
 572
 573                         RBTree.NodeEnumerator host;
 574
 575                         T current;
 576
 577                         internal Enumerator (SortedSet<T> set)
 578                         {
 579                                 host = set.tree.GetEnumerator ();
 580                                 current = default (T);
 581                         }
 582
 583                         public T Current {
 584                                 get { return current; }
 585                         }
 586
 587                         object IEnumerator.Current {
 588                                 get {
 589                                         host.check_current ();
 590                                         return ((Node) host.Current).item;
 591                                 }
 592                         }
 593
 594                         public bool MoveNext ()
 595                         {
 596                                 if (!host.MoveNext ())
 597                                         return false;
 598
 599                                 current = ((Node) host.Current).item;
 600                                 return true;
 601                         }
 602
 603                         public void Dispose ()
 604                         {
 605                                 host.Dispose ();
 606                         }
 607
 608                         void IEnumerator.Reset ()
 609                         {
 610                                 host.Reset ();
 611                         }
 612                 }
 613
 614                 [Serializable]
 615                 sealed class SortedSubSet : SortedSet<T>, IEnumerable<T>, IEnumerable {
 616
 617                         SortedSet<T> set;
 618                         T lower;
 619                         T upper;
 620
 621                         public SortedSubSet (SortedSet<T> set, T lower, T upper)
 622                                 : base (set.Comparer)
 623                         {
 624                                 this.set = set;
 625                                 this.lower = lower;
 626                                 this.upper = upper;
 627                         }
 628
 629                         internal override T GetMin ()
 630                         {
 631                                 for (int i = 0; i < set.tree.Count; i++) {
 632                                         var item = set.GetItem (i);
 633                                         if (InRange (item))
 634                                                 return item;
 635                                 }
 636
 637                                 return default (T);
 638                         }
 639
 640                         internal override T GetMax ()
 641                         {
 642                                 for (int i = set.tree.Count - 1; i >= 0; i--) {
 643                                         var item = set.GetItem (i);
 644                                         if (InRange (item))
 645                                                 return item;
 646                                 }
 647
 648                                 return default (T);
 649                         }
 650
 651                         internal override bool TryAdd (T item)
 652                         {
 653                                 if (!InRange (item))
 654                                         throw new ArgumentOutOfRangeException ("item");
 655
 656                                 return set.TryAdd (item);
 657                         }
 658
 659                         internal override bool TryRemove (T item)
 660                         {
 661                                 if (!InRange (item))
 662                                         return false;
 663
 664                                 return set.TryRemove (item);
 665                         }
 666
 667                         public override bool Contains (T item)
 668                         {
 669                                 if (!InRange (item))
 670                                         return false;
 671
 672                                 return set.Contains (item);
 673                         }
 674
 675                         public override void Clear ()
 676                         {
 677                                 set.RemoveWhere (InRange);
 678                         }
 679
 680                         bool InRange (T item)
 681                         {
 682                                 return Comparer.Compare (item, lower) >= 0
 683                                         && Comparer.Compare (item, upper) <= 0;
 684                         }
 685
 686                         public override SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
 687                         {
 688                                 if (Comparer.Compare (lowerValue, upperValue) > 0)
 689                                         throw new ArgumentException ("The lowerValue is bigger than upperValue");
 690                                 if (!InRange (lowerValue))
 691                                         throw new ArgumentOutOfRangeException ("lowerValue");
 692                                 if (!InRange (upperValue))
 693                                         throw new ArgumentOutOfRangeException ("upperValue");
 694
 695                                 return new SortedSubSet (set, lowerValue, upperValue);
 696                         }
 697
 698                         public IEnumerator<T> GetEnumerator ()
 699                         {
 700                                 var yielding = false;
 701
 702                                 foreach (Node node in set.tree) {
 703                                         var item = node.item;
 704
 705                                         if (InRange (item)) {
 706                                                 yield return item;
 707                                                 yielding = true;
 708                                         } else if (yielding)
 709                                                 yield break;
 710                                 }
 711                         }
 712
 713                         IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 714                         {
 715                                 return GetEnumerator ();
 716                         }
 717
 718                         IEnumerator IEnumerable.GetEnumerator ()
 719                         {
 720                                 return GetEnumerator ();
 721                         }
 722
 723                         public override void IntersectWith (IEnumerable<T> other)
 724                         {
 725                                 CheckArgumentNotNull (other, "other");
 726
 727                                 var slice = new SortedSet<T> (this);
 728                                 slice.IntersectWith (other);
 729
 730                                 Clear ();
 731                                 set.UnionWith (slice);
 732                         }
 733                 }
 734         }
 735 }
 736
 737 #endif