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

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