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

   1 //
   2 // SortedSet.cs
   3 //
   4 // Authors:
   5 //  Jb Evain  <jbevain@novell.com>
   6 //
   7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using System;
  30 using System.Collections;
  31 using System.Collections.Generic;
  32 using System.Linq;
  33 using System.Runtime.Serialization;
  34 using System.Runtime.InteropServices;
  35 using System.Security;
  36 using System.Security.Permissions;
  37 using System.Diagnostics;
  38
  39 // SortedSet is basically implemented as a reduction of SortedDictionary<K, V>
  40
  41 #if NET_4_0
  42
  43 namespace System.Collections.Generic {
  44
  45         [Serializable]
  46         [DebuggerDisplay ("Count={Count}")]
  47         [DebuggerTypeProxy (typeof (CollectionDebuggerView))]
  48         public class SortedSet<T> : ISet<T>, ICollection, ISerializable, IDeserializationCallback
  49         {
  50                 class Node : RBTree.Node {
  51
  52                         public T item;
  53
  54                         public Node (T item)
  55                         {
  56                                 this.item = item;
  57                         }
  58
  59                         public override void SwapValue (RBTree.Node other)
  60                         {
  61                                 var o = (Node) other;
  62                                 var i = this.item;
  63                                 this.item = o.item;
  64                                 o.item = i;
  65                         }
  66                 }
  67
  68                 class NodeHelper : RBTree.INodeHelper<T> {
  69
  70                         static NodeHelper Default = new NodeHelper (Comparer<T>.Default);
  71
  72                         public IComparer<T> comparer;
  73
  74                         public int Compare (T item, RBTree.Node node)
  75                         {
  76                                 return comparer.Compare (item, ((Node) node).item);
  77                         }
  78
  79                         public RBTree.Node CreateNode (T item)
  80                         {
  81                                 return new Node (item);
  82                         }
  83
  84                         NodeHelper (IComparer<T> comparer)
  85                         {
  86                                 this.comparer = comparer;
  87                         }
  88
  89                         public static NodeHelper GetHelper (IComparer<T> comparer)
  90                         {
  91                                 if (comparer == null || comparer == Comparer<T>.Default)
  92                                         return Default;
  93
  94                                 return new NodeHelper (comparer);
  95                         }
  96                 }
  97
  98                 RBTree tree;
  99                 NodeHelper helper;
 100                 SerializationInfo si;
 101
 102                 public SortedSet ()
 103                         : this (Comparer<T>.Default)
 104                 {
 105                 }
 106
 107                 public SortedSet (IEnumerable<T> collection)
 108                         : this (collection, Comparer<T>.Default)
 109                 {
 110                 }
 111
 112                 public SortedSet (IEnumerable<T> collection, IComparer<T> comparer)
 113                         : this (comparer)
 114                 {
 115                         if (collection == null)
 116                                 throw new ArgumentNullException ("collection");
 117
 118                         foreach (var item in collection)
 119                                 Add (item);
 120                 }
 121
 122                 public SortedSet (IComparer<T> comparer)
 123                 {
 124                         this.helper = NodeHelper.GetHelper (comparer);
 125                         this.tree = new RBTree (this.helper);
 126                 }
 127
 128                 protected SortedSet (SerializationInfo info, StreamingContext context)
 129                 {
 130                         this.si = info;
 131                 }
 132
 133                 public IComparer<T> Comparer {
 134                         get { return helper.comparer; }
 135                 }
 136
 137                 public int Count {
 138                         get { return tree.Count; }
 139                 }
 140
 141                 public T Max {
 142                         get { return GetMax (); }
 143                 }
 144
 145                 public T Min {
 146                         get {  return GetMin (); }
 147                 }
 148
 149                 internal virtual T GetMax ()
 150                 {
 151                         if (tree.Count == 0)
 152                                 return default (T);
 153
 154                         return GetItem (tree.Count - 1);
 155                 }
 156
 157                 internal virtual T GetMin ()
 158                 {
 159                         if (tree.Count == 0)
 160                                 return default (T);
 161
 162                         return GetItem (0);
 163                 }
 164
 165                 T GetItem (int index)
 166                 {
 167                         return ((Node) tree [index]).item;
 168                 }
 169
 170                 public bool Add (T item)
 171                 {
 172                         return TryAdd (item);
 173                 }
 174
 175                 internal virtual bool TryAdd (T item)
 176                 {
 177                         var node = new Node (item);
 178                         return tree.Intern (item, node) == node;
 179                 }
 180
 181                 public virtual void Clear ()
 182                 {
 183                         tree.Clear ();
 184                 }
 185
 186                 public virtual bool Contains (T item)
 187                 {
 188                         return tree.Lookup (item) != null;
 189                 }
 190
 191                 public void CopyTo (T [] array)
 192                 {
 193                         CopyTo (array, 0, Count);
 194                 }
 195
 196                 public void CopyTo (T [] array, int index)
 197                 {
 198                         CopyTo (array, index, Count);
 199                 }
 200
 201                 public void CopyTo (T [] array, int index, int count)
 202                 {
 203                         if (array == null)
 204                                 throw new ArgumentNullException ("array");
 205                         if (index < 0)
 206                                 throw new ArgumentOutOfRangeException ("index");
 207                         if (index > array.Length)
 208                                 throw new ArgumentException ("index larger than largest valid index of array");
 209                         if (array.Length - index < count)
 210                                 throw new ArgumentException ("destination array cannot hold the requested elements");
 211
 212                         foreach (Node node in tree) {
 213                                 if (count-- == 0)
 214                                         break;
 215
 216                                 array [index++] = node.item;
 217                         }
 218                 }
 219
 220                 public bool Remove (T item)
 221                 {
 222                         return TryRemove (item);
 223                 }
 224
 225                 internal virtual bool TryRemove (T item)
 226                 {
 227                         return tree.Remove (item) != null;
 228                 }
 229
 230                 public int RemoveWhere (Predicate<T> match)
 231                 {
 232                         var array = ToArray ();
 233
 234                         int count = 0;
 235                         foreach (var item in array) {
 236                                 if (!match (item))
 237                                         continue;
 238
 239                                 Remove (item);
 240                                 count++;
 241                         }
 242
 243                         return count;
 244                 }
 245
 246                 public IEnumerable<T> Reverse ()
 247                 {
 248                         for (int i = tree.Count - 1; i >= 0; i--)
 249                                 yield return GetItem (i);
 250                 }
 251
 252                 T [] ToArray ()
 253                 {
 254                         var array = new T [this.Count];
 255                         CopyTo (array);
 256                         return array;
 257                 }
 258
 259                 public Enumerator GetEnumerator ()
 260                 {
 261                         return new Enumerator (this);
 262                 }
 263
 264                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 265                 {
 266                         return new Enumerator (this);
 267                 }
 268
 269                 IEnumerator IEnumerable.GetEnumerator ()
 270                 {
 271                         return new Enumerator (this);
 272                 }
 273
 274                 public static IEqualityComparer<SortedSet<T>> CreateSetComparer ()
 275                 {
 276                         return CreateSetComparer (EqualityComparer<T>.Default);
 277                 }
 278
 279                 [MonoTODO]
 280                 public static IEqualityComparer<SortedSet<T>> CreateSetComparer (IEqualityComparer<T> memberEqualityComparer)
 281                 {
 282                         throw new NotImplementedException ();
 283                 }
 284
 285                 [MonoTODO]
 286                 protected virtual void GetObjectData (SerializationInfo info, StreamingContext context)
 287                 {
 288                         throw new NotImplementedException ();
 289                 }
 290
 291                 void ISerializable.GetObjectData (SerializationInfo info, StreamingContext context)
 292                 {
 293                         GetObjectData (info, context);
 294                 }
 295
 296                 [MonoTODO]
 297                 protected virtual void OnDeserialization (object sender)
 298                 {
 299                         if (si == null)
 300                                 return;
 301
 302                         throw new NotImplementedException ();
 303                 }
 304
 305                 void IDeserializationCallback.OnDeserialization (object sender)
 306                 {
 307                         OnDeserialization (sender);
 308                 }
 309
 310                 [MonoTODO]
 311                 public void ExceptWith (IEnumerable<T> other)
 312                 {
 313                         throw new NotImplementedException ();
 314                 }
 315
 316                 public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
 317                 {
 318                         if (Comparer.Compare (lowerValue, upperValue) > 0)
 319                                 throw new ArgumentException ("The lowerValue is bigger than upperValue");
 320
 321                         return new SortedSubSet (this, lowerValue, upperValue);
 322                 }
 323
 324                 [MonoTODO]
 325                 public virtual void IntersectWith (IEnumerable<T> other)
 326                 {
 327                         throw new NotImplementedException ();
 328                 }
 329
 330                 [MonoTODO]
 331                 public bool IsProperSubsetOf (IEnumerable<T> other)
 332                 {
 333                         throw new NotImplementedException ();
 334                 }
 335
 336                 [MonoTODO]
 337                 public bool IsProperSupersetOf (IEnumerable<T> other)
 338                 {
 339                         throw new NotImplementedException ();
 340                 }
 341
 342                 [MonoTODO]
 343                 public bool IsSubsetOf (IEnumerable<T> other)
 344                 {
 345                         throw new NotImplementedException ();
 346                 }
 347
 348                 [MonoTODO]
 349                 public bool IsSupersetOf (IEnumerable<T> other)
 350                 {
 351                         throw new NotImplementedException ();
 352                 }
 353
 354                 [MonoTODO]
 355                 public bool Overlaps (IEnumerable<T> other)
 356                 {
 357                         throw new NotImplementedException ();
 358                 }
 359
 360                 [MonoTODO]
 361                 public bool SetEquals (IEnumerable<T> other)
 362                 {
 363                         throw new NotImplementedException ();
 364                 }
 365
 366                 [MonoTODO]
 367                 public void SymmetricExceptWith (IEnumerable<T> other)
 368                 {
 369                         throw new NotImplementedException ();
 370                 }
 371
 372                 [MonoTODO]
 373                 public void UnionWith (IEnumerable<T> other)
 374                 {
 375                         throw new NotImplementedException ();
 376                 }
 377
 378                 void ICollection<T>.Add (T item)
 379                 {
 380                         Add (item);
 381                 }
 382
 383                 void ICollection<T>.CopyTo (T [] array, int index)
 384                 {
 385                         CopyTo (array, index, Count);
 386                 }
 387
 388                 bool ICollection<T>.IsReadOnly {
 389                         get { return false; }
 390                 }
 391
 392                 void ICollection.CopyTo (Array array, int index)
 393                 {
 394                         if (Count == 0)
 395                                 return;
 396                         if (array == null)
 397                                 throw new ArgumentNullException ("array");
 398                         if (index < 0 || array.Length <= index)
 399                                 throw new ArgumentOutOfRangeException ("index");
 400                         if (array.Length - index < Count)
 401                                 throw new ArgumentException ();
 402
 403                         foreach (Node node in tree)
 404                                 array.SetValue (node.item, index++);
 405                 }
 406
 407                 bool ICollection.IsSynchronized {
 408                         get { return false; }
 409                 }
 410
 411                 // TODO:Is this correct? If this is wrong,please fix.
 412                 object ICollection.SyncRoot {
 413                         get { return this; }
 414                 }
 415
 416                 [Serializable]
 417                 public struct Enumerator : IEnumerator<T>, IDisposable {
 418
 419                         RBTree.NodeEnumerator host;
 420
 421                         T current;
 422
 423                         internal Enumerator (SortedSet<T> set)
 424                         {
 425                                 host = set.tree.GetEnumerator ();
 426                                 current = default (T);
 427                         }
 428
 429                         public T Current {
 430                                 get { return current; }
 431                         }
 432
 433                         object IEnumerator.Current {
 434                                 get {
 435                                         host.check_current ();
 436                                         return ((Node) host.Current).item;
 437                                 }
 438                         }
 439
 440                         public bool MoveNext ()
 441                         {
 442                                 if (!host.MoveNext ())
 443                                         return false;
 444
 445                                 current = ((Node) host.Current).item;
 446                                 return true;
 447                         }
 448
 449                         public void Dispose ()
 450                         {
 451                                 host.Dispose ();
 452                         }
 453
 454                         void IEnumerator.Reset ()
 455                         {
 456                                 host.Reset ();
 457                         }
 458                 }
 459
 460                 [Serializable]
 461                 sealed class SortedSubSet : SortedSet<T>, IEnumerable<T>, IEnumerable {
 462
 463                         SortedSet<T> set;
 464                         T lower;
 465                         T upper;
 466
 467                         public SortedSubSet (SortedSet<T> set, T lower, T upper)
 468                                 : base (set.Comparer)
 469                         {
 470                                 this.set = set;
 471                                 this.lower = lower;
 472                                 this.upper = upper;
 473                         }
 474
 475                         internal override T GetMin ()
 476                         {
 477                                 for (int i = 0; i < set.tree.Count; i++) {
 478                                         var item = set.GetItem (i);
 479                                         if (InRange (item))
 480                                                 return item;
 481                                 }
 482
 483                                 return default (T);
 484                         }
 485
 486                         internal override T GetMax ()
 487                         {
 488                                 for (int i = set.tree.Count - 1; i >= 0; i--) {
 489                                         var item = set.GetItem (i);
 490                                         if (InRange (item))
 491                                                 return item;
 492                                 }
 493
 494                                 return default (T);
 495                         }
 496
 497                         internal override bool TryAdd (T item)
 498                         {
 499                                 if (!InRange (item))
 500                                         throw new ArgumentOutOfRangeException ("item");
 501
 502                                 return set.TryAdd (item);
 503                         }
 504
 505                         internal override bool TryRemove (T item)
 506                         {
 507                                 if (!InRange (item))
 508                                         return false;
 509
 510                                 return set.TryRemove (item);
 511                         }
 512
 513                         public override bool Contains (T item)
 514                         {
 515                                 if (!InRange (item))
 516                                         return false;
 517
 518                                 return set.Contains (item);
 519                         }
 520
 521                         public override void Clear ()
 522                         {
 523                                 set.RemoveWhere (InRange);
 524                         }
 525
 526                         bool InRange (T item)
 527                         {
 528                                 return Comparer.Compare (item, lower) >= 0
 529                                         && Comparer.Compare (item, upper) <= 0;
 530                         }
 531
 532                         public override SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
 533                         {
 534                                 if (Comparer.Compare (lowerValue, upperValue) > 0)
 535                                         throw new ArgumentException ("The lowerValue is bigger than upperValue");
 536                                 if (!InRange (lowerValue))
 537                                         throw new ArgumentOutOfRangeException ("lowerValue");
 538                                 if (!InRange (upperValue))
 539                                         throw new ArgumentOutOfRangeException ("upperValue");
 540
 541                                 return new SortedSubSet (set, lowerValue, upperValue);
 542                         }
 543
 544                         public IEnumerator<T> GetEnumerator ()
 545                         {
 546                                 var yielding = false;
 547
 548                                 foreach (Node node in set.tree) {
 549                                         var item = node.item;
 550
 551                                         if (InRange (item)) {
 552                                                 yield return item;
 553                                                 yielding = true;
 554                                         } else if (yielding)
 555                                                 yield break;
 556                                 }
 557                         }
 558
 559                         IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 560                         {
 561                                 return GetEnumerator ();
 562                         }
 563
 564                         IEnumerator IEnumerable.GetEnumerator ()
 565                         {
 566                                 return GetEnumerator ();
 567                         }
 568                 }
 569         }
 570 }
 571
 572 #endif