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