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

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