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