mcs/class/Mono.C5/C5/Interfaces.cs

   1 #if NET_2_0\r
   2 /*\r
   3  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
   4  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   5  of this software and associated documentation files (the "Software"), to deal\r
   6  in the Software without restriction, including without limitation the rights\r
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   8  copies of the Software, and to permit persons to whom the Software is\r
   9  furnished to do so, subject to the following conditions:\r
  10  \r
  11  The above copyright notice and this permission notice shall be included in\r
  12  all copies or substantial portions of the Software.\r
  13  \r
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  20  SOFTWARE.\r
  21 */\r
  22 \r
  23 using System;\r
  24 using SCG = System.Collections.Generic;\r
  25 namespace C5\r
  26 {\r
  27   /// <summary>\r
  28   /// A generic collection, that can be enumerated backwards.\r
  29   /// </summary>\r
  30   public interface IDirectedEnumerable<T> : SCG.IEnumerable<T>\r
  31   {\r
  32     /// <summary>\r
  33     /// Create a collection containing the same items as this collection, but\r
  34     /// whose enumerator will enumerate the items backwards. The new collection\r
  35     /// will become invalid if the original is modified. Method typically used as in\r
  36     /// <code>foreach (T x in coll.Backwards()) {...}</code>\r
  37     /// </summary>\r
  38     /// <returns>The backwards collection.</returns>\r
  39     IDirectedEnumerable<T> Backwards();\r
  40 \r
  41 \r
  42     /// <summary>\r
  43     /// <code>Forwards</code> if same, else <code>Backwards</code>\r
  44     /// </summary>\r
  45     /// <value>The enumeration direction relative to the original collection.</value>\r
  46     EnumerationDirection Direction { get;}\r
  47   }\r
  48 \r
  49   /// <summary>\r
  50   /// A generic collection that may be enumerated and can answer\r
  51   /// efficiently how many items it contains. Like <code>IEnumerable&lt;T&gt;</code>,\r
  52   /// this interface does not prescribe any operations to initialize or update the \r
  53   /// collection. The main usage for this interface is to be the return type of \r
  54   /// query operations on generic collection.\r
  55   /// </summary>\r
  56   public interface ICollectionValue<T> : SCG.IEnumerable<T>, IShowable\r
  57   {\r
  58     /// <summary>\r
  59     /// A flag bitmap of the events subscribable to by this collection.\r
  60     /// </summary>\r
  61     /// <value></value>\r
  62     EventTypeEnum ListenableEvents { get;}\r
  63 \r
  64     /// <summary>\r
  65     /// A flag bitmap of the events currently subscribed to by this collection.\r
  66     /// </summary>\r
  67     /// <value></value>\r
  68     EventTypeEnum ActiveEvents { get;}\r
  69 \r
  70     /// <summary>\r
  71     /// The change event. Will be raised for every change operation on the collection.\r
  72     /// </summary>\r
  73     event CollectionChangedHandler<T> CollectionChanged;\r
  74 \r
  75     /// <summary>\r
  76     /// The change event. Will be raised for every clear operation on the collection.\r
  77     /// </summary>\r
  78     event CollectionClearedHandler<T> CollectionCleared;\r
  79 \r
  80     /// <summary>\r
  81     /// The item added  event. Will be raised for every individual addition to the collection.\r
  82     /// </summary>\r
  83     event ItemsAddedHandler<T> ItemsAdded;\r
  84 \r
  85     /// <summary>\r
  86     /// The item inserted  event. Will be raised for every individual insertion to the collection.\r
  87     /// </summary>\r
  88     event ItemInsertedHandler<T> ItemInserted;\r
  89 \r
  90     /// <summary>\r
  91     /// The item removed event. Will be raised for every individual removal from the collection.\r
  92     /// </summary>\r
  93     event ItemsRemovedHandler<T> ItemsRemoved;\r
  94 \r
  95     /// <summary>\r
  96     /// The item removed at event. Will be raised for every individual removal at from the collection.\r
  97     /// </summary>\r
  98     event ItemRemovedAtHandler<T> ItemRemovedAt;\r
  99 \r
 100     /// <summary>\r
 101     /// \r
 102     /// </summary>\r
 103     /// <value>True if this collection is empty.</value>\r
 104     bool IsEmpty { get;}\r
 105 \r
 106     /// <summary>\r
 107     /// \r
 108     /// </summary>\r
 109     /// <value>The number of items in this collection</value>\r
 110     int Count { get;}\r
 111 \r
 112     /// <summary>\r
 113     /// The value is symbolic indicating the type of asymptotic complexity\r
 114     /// in terms of the size of this collection (worst-case or amortized as\r
 115     /// relevant).\r
 116     /// </summary>\r
 117     /// <value>A characterization of the speed of the \r
 118     /// <code>Count</code> property in this collection.</value>\r
 119     Speed CountSpeed { get;}\r
 120 \r
 121     /// <summary>\r
 122     /// Copy the items of this collection to a contiguous part of an array.\r
 123     /// </summary>\r
 124     /// <param name="array">The array to copy to</param>\r
 125     /// <param name="index">The index at which to copy the first item</param>\r
 126     void CopyTo(T[] array, int index);\r
 127 \r
 128     /// <summary>\r
 129     /// Create an array with the items of this collection (in the same order as an\r
 130     /// enumerator would output them).\r
 131     /// </summary>\r
 132     /// <returns>The array</returns>\r
 133     T[] ToArray();\r
 134 \r
 135     /// <summary>\r
 136     /// Apply a delegate to all items of this collection.\r
 137     /// </summary>\r
 138     /// <param name="action">The delegate to apply</param>\r
 139     void Apply(Act<T> action);\r
 140 \r
 141 \r
 142     /// <summary>\r
 143     /// Check if there exists an item  that satisfies a\r
 144     /// specific predicate in this collection.\r
 145     /// </summary>\r
 146     /// <param name="predicate">A  delegate \r
 147     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
 148     /// <returns>True is such an item exists</returns>\r
 149     bool Exists(Fun<T, bool> predicate);\r
 150 \r
 151     /// <summary>\r
 152     /// Check if there exists an item  that satisfies a\r
 153     /// specific predicate in this collection and return the first one in enumeration order.\r
 154     /// </summary>\r
 155     /// <param name="predicate">A delegate \r
 156     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
 157     /// <param name="item"></param>\r
 158     /// <returns>True is such an item exists</returns>\r
 159     bool Find(Fun<T, bool> predicate, out T item);\r
 160 \r
 161 \r
 162     /// <summary>\r
 163     /// Check if all items in this collection satisfies a specific predicate.\r
 164     /// </summary>\r
 165     /// <param name="predicate">A delegate \r
 166     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
 167     /// <returns>True if all items satisfies the predicate</returns>\r
 168     bool All(Fun<T, bool> predicate);\r
 169 \r
 170     /// <summary>\r
 171     /// Choose some item of this collection. \r
 172     /// <para>Implementations must assure that the item \r
 173     /// returned may be efficiently removed.</para>\r
 174     /// <para>Implementors may decide to implement this method in a way such that repeated\r
 175     /// calls do not necessarily give the same result, i.e. so that the result of the following \r
 176     /// test is undetermined:\r
 177     /// <code>coll.Choose() == coll.Choose()</code></para>\r
 178     /// </summary>\r
 179     /// <exception cref="NoSuchItemException">if collection is empty.</exception>\r
 180     /// <returns></returns>\r
 181     T Choose();\r
 182 \r
 183     /// <summary>\r
 184     /// Create an enumerable, enumerating the items of this collection that satisfies \r
 185     /// a certain condition.\r
 186     /// </summary>\r
 187     /// <param name="filter">The T->bool filter delegate defining the condition</param>\r
 188     /// <returns>The filtered enumerable</returns>\r
 189     SCG.IEnumerable<T> Filter(Fun<T, bool> filter);\r
 190   }\r
 191 \r
 192 \r
 193 \r
 194   /// <summary>\r
 195   /// A sized generic collection, that can be enumerated backwards.\r
 196   /// </summary>\r
 197   public interface IDirectedCollectionValue<T> : ICollectionValue<T>, IDirectedEnumerable<T>\r
 198   {\r
 199     /// <summary>\r
 200     /// Create a collection containing the same items as this collection, but\r
 201     /// whose enumerator will enumerate the items backwards. The new collection\r
 202     /// will become invalid if the original is modified. Method typically used as in\r
 203     /// <code>foreach (T x in coll.Backwards()) {...}</code>\r
 204     /// </summary>\r
 205     /// <returns>The backwards collection.</returns>\r
 206     new IDirectedCollectionValue<T> Backwards();\r
 207 \r
 208     /// <summary>\r
 209     /// Check if there exists an item  that satisfies a\r
 210     /// specific predicate in this collection and return the first one in enumeration order.\r
 211     /// </summary>\r
 212     /// <param name="predicate">A delegate \r
 213     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
 214     /// <param name="item"></param>\r
 215     /// <returns>True is such an item exists</returns>\r
 216     bool FindLast(Fun<T, bool> predicate, out T item);\r
 217   }\r
 218 \r
 219 \r
 220   /// <summary>\r
 221   /// A generic collection to which one may add items. This is just the intersection\r
 222   /// of the main stream generic collection interfaces and the priority queue interface,\r
 223   /// <see cref="T:C5.ICollection`1"/> and <see cref="T:C5.IPriorityQueue`1"/>.\r
 224   /// </summary>\r
 225   public interface IExtensible<T> : ICollectionValue<T>, ICloneable\r
 226   {\r
 227     /// <summary>\r
 228     /// If true any call of an updating operation will throw an\r
 229     /// <code>ReadOnlyCollectionException</code>\r
 230     /// </summary>\r
 231     /// <value>True if this collection is read-only.</value>\r
 232     bool IsReadOnly { get;}\r
 233 \r
 234     //TODO: wonder where the right position of this is\r
 235     /// <summary>\r
 236     /// \r
 237     /// </summary>\r
 238     /// <value>False if this collection has set semantics, true if bag semantics.</value>\r
 239     bool AllowsDuplicates { get;}\r
 240 \r
 241     //TODO: wonder where the right position of this is. And the semantics.\r
 242     /// <summary>\r
 243     /// (Here should be a discussion of the role of equalityComparers. Any ). \r
 244     /// </summary>\r
 245     /// <value>The equalityComparer used by this collection to check equality of items. \r
 246     /// Or null (????) if collection does not check equality at all or uses a comparer.</value>\r
 247     SCG.IEqualityComparer<T> EqualityComparer { get;}\r
 248 \r
 249     //ItemEqualityTypeEnum ItemEqualityType {get ;}\r
 250 \r
 251     //TODO: find a good name\r
 252 \r
 253     /// <summary>\r
 254     /// By convention this is true for any collection with set semantics.\r
 255     /// </summary>\r
 256     /// <value>True if only one representative of a group of equal items \r
 257     /// is kept in the collection together with the total count.</value>\r
 258     bool DuplicatesByCounting { get;}\r
 259 \r
 260     /// <summary>\r
 261     /// Add an item to this collection if possible. If this collection has set\r
 262     /// semantics, the item will be added if not already in the collection. If\r
 263     /// bag semantics, the item will always be added.\r
 264     /// </summary>\r
 265     /// <param name="item">The item to add.</param>\r
 266     /// <returns>True if item was added.</returns>\r
 267     bool Add(T item);\r
 268 \r
 269     /// <summary>\r
 270     /// Add the elements from another collection with a more specialized item type \r
 271     /// to this collection. If this\r
 272     /// collection has set semantics, only items not already in the collection\r
 273     /// will be added.\r
 274     /// </summary>\r
 275     /// <typeparam name="U">The type of items to add</typeparam>\r
 276     /// <param name="items">The items to add</param>\r
 277     void AddAll<U>(SCG.IEnumerable<U> items) where U : T;\r
 278 \r
 279     //void Clear(); // for priority queue\r
 280     //int Count why not?\r
 281     /// <summary>\r
 282     /// Check the integrity of the internal data structures of this collection.\r
 283     /// <i>This is only relevant for developers of the library</i>\r
 284     /// </summary>\r
 285     /// <returns>True if check was passed.</returns>\r
 286     bool Check();\r
 287   }\r
 288 \r
 289   /// <summary>\r
 290   /// The simplest interface of a main stream generic collection\r
 291   /// with lookup, insertion and removal operations. \r
 292   /// </summary>\r
 293   public interface ICollection<T> : IExtensible<T>\r
 294   {\r
 295     //This is somewhat similar to the RandomAccess marker itf in java\r
 296     /// <summary>\r
 297     /// The value is symbolic indicating the type of asymptotic complexity\r
 298     /// in terms of the size of this collection (worst-case or amortized as\r
 299     /// relevant). \r
 300     /// <para>See <see cref="T:C5.Speed"/> for the set of symbols.</para>\r
 301     /// </summary>\r
 302     /// <value>A characterization of the speed of lookup operations\r
 303     /// (<code>Contains()</code> etc.) of the implementation of this collection.</value>\r
 304     Speed ContainsSpeed { get;}\r
 305 \r
 306     /// <summary>\r
 307     /// The unordered collection hashcode is defined as the sum of \r
 308     /// <code>h(hashcode(item))</code> over the items\r
 309     /// of the collection, where the function <code>h</code> is a function from \r
 310     /// int to int of the form <code> t -> (a0*t+b0)^(a1*t+b1)^(a2*t+b2)</code>, where \r
 311     /// the ax and bx are the same for all collection classes. \r
 312     /// <para>The current implementation uses fixed values for the ax and bx, \r
 313     /// specified as constants in the code.</para>\r
 314     /// </summary>\r
 315     /// <returns>The unordered hashcode of this collection.</returns>\r
 316     int GetUnsequencedHashCode();\r
 317 \r
 318 \r
 319     /// <summary>\r
 320     /// Compare the contents of this collection to another one without regards to\r
 321     /// the sequence order. The comparison will use this collection's itemequalityComparer\r
 322     /// to compare individual items.\r
 323     /// </summary>\r
 324     /// <param name="otherCollection">The collection to compare to.</param>\r
 325     /// <returns>True if this collection and that contains the same items.</returns>\r
 326     bool UnsequencedEquals(ICollection<T> otherCollection);\r
 327 \r
 328 \r
 329     /// <summary>\r
 330     /// Check if this collection contains (an item equivalent to according to the\r
 331     /// itemequalityComparer) a particular value.\r
 332     /// </summary>\r
 333     /// <param name="item">The value to check for.</param>\r
 334     /// <returns>True if the items is in this collection.</returns>\r
 335     bool Contains(T item);\r
 336 \r
 337 \r
 338     /// <summary>\r
 339     /// Count the number of items of the collection equal to a particular value.\r
 340     /// Returns 0 if and only if the value is not in the collection.\r
 341     /// </summary>\r
 342     /// <param name="item">The value to count.</param>\r
 343     /// <returns>The number of copies found.</returns>\r
 344     int ContainsCount(T item);\r
 345 \r
 346     /// <summary>\r
 347     /// \r
 348     /// </summary>\r
 349     /// <returns></returns>\r
 350     ICollectionValue<T> UniqueItems();\r
 351 \r
 352     /// <summary>\r
 353     /// \r
 354     /// </summary>\r
 355     /// <returns></returns>\r
 356     ICollectionValue<KeyValuePair<T, int>> ItemMultiplicities();\r
 357 \r
 358     /// <summary>\r
 359     /// Check whether this collection contains all the values in another collection.\r
 360     /// If this collection has bag semantics (<code>AllowsDuplicates==true</code>)\r
 361     /// the check is made with respect to multiplicities, else multiplicities\r
 362     /// are not taken into account.\r
 363     /// </summary>\r
 364     /// <param name="items">The </param>\r
 365     /// <typeparam name="U"></typeparam>\r
 366     /// <returns>True if all values in <code>items</code>is in this collection.</returns>\r
 367     bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T;\r
 368 \r
 369 \r
 370     /// <summary>\r
 371     /// Check if this collection contains an item equivalent according to the\r
 372     /// itemequalityComparer to a particular value. If so, return in the ref argument (a\r
 373     /// binary copy of) the actual value found.\r
 374     /// </summary>\r
 375     /// <param name="item">The value to look for.</param>\r
 376     /// <returns>True if the items is in this collection.</returns>\r
 377     bool Find(ref T item);\r
 378 \r
 379 \r
 380     //This should probably just be bool Add(ref T item); !!!\r
 381     /// <summary>\r
 382     /// Check if this collection contains an item equivalent according to the\r
 383     /// itemequalityComparer to a particular value. If so, return in the ref argument (a\r
 384     /// binary copy of) the actual value found. Else, add the item to the collection.\r
 385     /// </summary>\r
 386     /// <param name="item">The value to look for.</param>\r
 387     /// <returns>True if the item was found (hence not added).</returns>\r
 388     bool FindOrAdd(ref T item);\r
 389 \r
 390 \r
 391     /// <summary>\r
 392     /// Check if this collection contains an item equivalent according to the\r
 393     /// itemequalityComparer to a particular value. If so, update the item in the collection \r
 394     /// with a (binary copy of) the supplied value. If the collection has bag semantics,\r
 395     /// it depends on the value of DuplicatesByCounting if this updates all equivalent copies in\r
 396     /// the collection or just one.\r
 397     /// </summary>\r
 398     /// <param name="item">Value to update.</param>\r
 399     /// <returns>True if the item was found and hence updated.</returns>\r
 400     bool Update(T item);\r
 401 \r
 402     /// <summary>\r
 403     /// Check if this collection contains an item equivalent according to the\r
 404     /// itemequalityComparer to a particular value. If so, update the item in the collection \r
 405     /// with a (binary copy of) the supplied value. If the collection has bag semantics,\r
 406     /// it depends on the value of DuplicatesByCounting if this updates all equivalent copies in\r
 407     /// the collection or just one.\r
 408     /// </summary>\r
 409     /// <param name="item">Value to update.</param>\r
 410     /// <param name="olditem">On output the olditem, if found.</param>\r
 411     /// <returns>True if the item was found and hence updated.</returns>\r
 412     bool Update(T item, out T olditem);\r
 413 \r
 414 \r
 415     /// <summary>\r
 416     /// Check if this collection contains an item equivalent according to the\r
 417     /// itemequalityComparer to a particular value. If so, update the item in the collection \r
 418     /// to with a binary copy of the supplied value; else add the value to the collection. \r
 419     /// </summary>\r
 420     /// <param name="item">Value to add or update.</param>\r
 421     /// <returns>True if the item was found and updated (hence not added).</returns>\r
 422     bool UpdateOrAdd(T item);\r
 423 \r
 424 \r
 425     /// <summary>\r
 426     /// Check if this collection contains an item equivalent according to the\r
 427     /// itemequalityComparer to a particular value. If so, update the item in the collection \r
 428     /// to with a binary copy of the supplied value; else add the value to the collection. \r
 429     /// </summary>\r
 430     /// <param name="item">Value to add or update.</param>\r
 431     /// <param name="olditem">On output the olditem, if found.</param>\r
 432     /// <returns>True if the item was found and updated (hence not added).</returns>\r
 433     bool UpdateOrAdd(T item, out T olditem);\r
 434 \r
 435     /// <summary>\r
 436     /// Remove a particular item from this collection. If the collection has bag\r
 437     /// semantics only one copy equivalent to the supplied item is removed. \r
 438     /// </summary>\r
 439     /// <param name="item">The value to remove.</param>\r
 440     /// <returns>True if the item was found (and removed).</returns>\r
 441     bool Remove(T item);\r
 442 \r
 443 \r
 444     /// <summary>\r
 445     /// Remove a particular item from this collection if found. If the collection\r
 446     /// has bag semantics only one copy equivalent to the supplied item is removed,\r
 447     /// which one is implementation dependent. \r
 448     /// If an item was removed, report a binary copy of the actual item removed in \r
 449     /// the argument.\r
 450     /// </summary>\r
 451     /// <param name="item">The value to remove.</param>\r
 452     /// <param name="removeditem">The value removed if any.</param>\r
 453     /// <returns>True if the item was found (and removed).</returns>\r
 454     bool Remove(T item, out T removeditem);\r
 455 \r
 456 \r
 457     /// <summary>\r
 458     /// Remove all items equivalent to a given value.\r
 459     /// </summary>\r
 460     /// <param name="item">The value to remove.</param>\r
 461     void RemoveAllCopies(T item);\r
 462 \r
 463 \r
 464     /// <summary>\r
 465     /// Remove all items in another collection from this one. If this collection\r
 466     /// has bag semantics, take multiplicities into account.\r
 467     /// </summary>\r
 468     /// <typeparam name="U"></typeparam>\r
 469     /// <param name="items">The items to remove.</param>\r
 470     void RemoveAll<U>(SCG.IEnumerable<U> items) where U : T;\r
 471 \r
 472     //void RemoveAll(Fun<T, bool> predicate);\r
 473 \r
 474     /// <summary>\r
 475     /// Remove all items from this collection.\r
 476     /// </summary>\r
 477     void Clear();\r
 478 \r
 479 \r
 480     /// <summary>\r
 481     /// Remove all items not in some other collection from this one. If this collection\r
 482     /// has bag semantics, take multiplicities into account.\r
 483     /// </summary>\r
 484     /// <typeparam name="U"></typeparam>\r
 485     /// <param name="items">The items to retain.</param>\r
 486     void RetainAll<U>(SCG.IEnumerable<U> items) where U : T;\r
 487 \r
 488     //void RetainAll(Fun<T, bool> predicate);\r
 489     //IDictionary<T> UniqueItems()\r
 490   }\r
 491 \r
 492 \r
 493 \r
 494   /// <summary>\r
 495   /// An editable collection maintaining a definite sequence order of the items.\r
 496   ///\r
 497   /// <i>Implementations of this interface must compute the hash code and \r
 498   /// equality exactly as prescribed in the method definitions in order to\r
 499   /// be consistent with other collection classes implementing this interface.</i>\r
 500   /// <i>This interface is usually implemented by explicit interface implementation,\r
 501   /// not as ordinary virtual methods.</i>\r
 502   /// </summary>\r
 503   public interface ISequenced<T> : ICollection<T>, IDirectedCollectionValue<T>\r
 504   {\r
 505     /// <summary>\r
 506     /// The hashcode is defined as <code>h(...h(h(h(x1),x2),x3),...,xn)</code> for\r
 507     /// <code>h(a,b)=CONSTANT*a+b</code> and the x's the hash codes of the items of \r
 508     /// this collection.\r
 509     /// </summary>\r
 510     /// <returns>The sequence order hashcode of this collection.</returns>\r
 511     int GetSequencedHashCode();\r
 512 \r
 513 \r
 514     /// <summary>\r
 515     /// Compare this sequenced collection to another one in sequence order.\r
 516     /// </summary>\r
 517     /// <param name="otherCollection">The sequenced collection to compare to.</param>\r
 518     /// <returns>True if this collection and that contains equal (according to\r
 519     /// this collection's itemequalityComparer) in the same sequence order.</returns>\r
 520     bool SequencedEquals(ISequenced<T> otherCollection);\r
 521   }\r
 522 \r
 523 \r
 524 \r
 525   /// <summary>\r
 526   /// A sequenced collection, where indices of items in the order are maintained\r
 527   /// </summary>\r
 528   public interface IIndexed<T> : ISequenced<T>\r
 529   {\r
 530     /// <summary>\r
 531     /// </summary>\r
 532     /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
 533     /// &gt;= the size of the collection.</exception>\r
 534     /// <value>The <code>index</code>'th item of this list.</value>\r
 535     /// <param name="index">the index to lookup</param>\r
 536     T this[int index] { get;}\r
 537 \r
 538     /// <summary>\r
 539     /// \r
 540     /// </summary>\r
 541     /// <value></value>\r
 542     Speed IndexingSpeed { get;}\r
 543 \r
 544     /// <summary>\r
 545     /// </summary>\r
 546     /// <exception cref="ArgumentOutOfRangeException"></exception>\r
 547     /// <value>The directed collection of items in a specific index interval.</value>\r
 548     /// <param name="start">The low index of the interval (inclusive).</param>\r
 549     /// <param name="count">The size of the range.</param>\r
 550     IDirectedCollectionValue<T> this[int start, int count] { get;}\r
 551 \r
 552 \r
 553     /// <summary>\r
 554     /// Searches for an item in the list going forwards from the start. \r
 555     /// </summary>\r
 556     /// <param name="item">Item to search for.</param>\r
 557     /// <returns>Index of item from start. A negative number if item not found, \r
 558     /// namely the two-complement of the index at which the Add operation would put the item.</returns>\r
 559     int IndexOf(T item);\r
 560 \r
 561 \r
 562     /// <summary>\r
 563     /// Searches for an item in the list going backwards from the end.\r
 564     /// </summary>\r
 565     /// <param name="item">Item to search for.</param>\r
 566     /// <returns>Index of of item from the end. A negative number if item not found, \r
 567     /// namely the two-complement of the index at which the Add operation would put the item.</returns>\r
 568     int LastIndexOf(T item);\r
 569 \r
 570     /// <summary>\r
 571     /// Check if there exists an item  that satisfies a\r
 572     /// specific predicate in this collection and return the index of the first one.\r
 573     /// </summary>\r
 574     /// <param name="predicate">A delegate \r
 575     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
 576     /// <returns>the index, if found, a negative value else</returns>\r
 577     int FindIndex(Fun<T, bool> predicate);\r
 578 \r
 579     /// <summary>\r
 580     /// Check if there exists an item  that satisfies a\r
 581     /// specific predicate in this collection and return the index of the last one.\r
 582     /// </summary>\r
 583     /// <param name="predicate">A delegate \r
 584     /// (<see cref="T:C5.Fun`2"/> with <code>R == bool</code>) defining the predicate</param>\r
 585     /// <returns>the index, if found, a negative value else</returns>\r
 586     int FindLastIndex(Fun<T, bool> predicate);\r
 587 \r
 588 \r
 589     /// <summary>\r
 590     /// Remove the item at a specific position of the list.\r
 591     /// </summary>\r
 592     /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
 593     /// &gt;= the size of the collection.</exception>\r
 594     /// <param name="index">The index of the item to remove.</param>\r
 595     /// <returns>The removed item.</returns>\r
 596     T RemoveAt(int index);\r
 597 \r
 598 \r
 599     /// <summary>\r
 600     /// Remove all items in an index interval.\r
 601     /// </summary>\r
 602     /// <exception cref="ArgumentOutOfRangeException"> if start or count \r
 603     /// is negative or start+count &gt; the size of the collection.</exception>\r
 604     /// <param name="start">The index of the first item to remove.</param>\r
 605     /// <param name="count">The number of items to remove.</param>\r
 606     void RemoveInterval(int start, int count);\r
 607   }\r
 608 \r
 609   //TODO: decide if this should extend ICollection\r
 610   /// <summary>\r
 611   /// The interface describing the operations of a LIFO stack data structure.\r
 612   /// </summary>\r
 613   /// <typeparam name="T">The item type</typeparam>\r
 614   public interface IStack<T> : IDirectedCollectionValue<T>\r
 615   {\r
 616     /// <summary>\r
 617     /// \r
 618     /// </summary>\r
 619     /// <value></value>\r
 620     bool AllowsDuplicates { get;}\r
 621     /// <summary>\r
 622     /// Get the <code>index</code>'th element of the stack.  The bottom of the stack has index 0.\r
 623     /// </summary>\r
 624     /// <param name="index"></param>\r
 625     /// <returns></returns>\r
 626     T this[int index] { get;}\r
 627     /// <summary>\r
 628     /// Push an item to the top of the stack.\r
 629     /// </summary>\r
 630     /// <param name="item">The item</param>\r
 631     void Push(T item);\r
 632     /// <summary>\r
 633     /// Pop the item at the top of the stack from the stack.\r
 634     /// </summary>\r
 635     /// <returns>The popped item.</returns>\r
 636     T Pop();\r
 637   }\r
 638 \r
 639   /// <summary>\r
 640   /// The interface describing the operations of a FIFO queue data structure.\r
 641   /// </summary>\r
 642   /// <typeparam name="T">The item type</typeparam>\r
 643   public interface IQueue<T> : IDirectedCollectionValue<T>\r
 644   {\r
 645     /// <summary>\r
 646     /// \r
 647     /// </summary>\r
 648     /// <value></value>\r
 649     bool AllowsDuplicates { get;}\r
 650     /// <summary>\r
 651     /// Get the <code>index</code>'th element of the queue.  The front of the queue has index 0.\r
 652     /// </summary>\r
 653     /// <param name="index"></param>\r
 654     /// <returns></returns>\r
 655     T this[int index] { get;}\r
 656     /// <summary>\r
 657     /// Enqueue an item at the back of the queue. \r
 658     /// </summary>\r
 659     /// <param name="item">The item</param>\r
 660     void Enqueue(T item);\r
 661     /// <summary>\r
 662     /// Dequeue an item from the front of the queue.\r
 663     /// </summary>\r
 664     /// <returns>The item</returns>\r
 665     T Dequeue();\r
 666   }\r
 667 \r
 668 \r
 669   /// <summary>\r
 670   /// This is an indexed collection, where the item order is chosen by \r
 671   /// the user at insertion time.\r
 672   ///\r
 673   /// NBNBNB: we need a description of the view functionality here!\r
 674   /// </summary>\r
 675   public interface IList<T> : IIndexed<T>, IDisposable\r
 676   {\r
 677     /// <summary>\r
 678     /// </summary>\r
 679     /// <exception cref="NoSuchItemException"> if this list is empty.</exception>\r
 680     /// <value>The first item in this list.</value>\r
 681     T First { get;}\r
 682 \r
 683     /// <summary>\r
 684     /// </summary>\r
 685     /// <exception cref="NoSuchItemException"> if this list is empty.</exception>\r
 686     /// <value>The last item in this list.</value>\r
 687     T Last { get;}\r
 688 \r
 689     /// <summary>\r
 690     /// Since <code>Add(T item)</code> always add at the end of the list,\r
 691     /// this describes if list has FIFO or LIFO semantics.\r
 692     /// </summary>\r
 693     /// <value>True if the <code>Remove()</code> operation removes from the\r
 694     /// start of the list, false if it removes from the end.</value>\r
 695     bool FIFO { get; set;}\r
 696 \r
 697     /// <summary>\r
 698     /// \r
 699     /// </summary>\r
 700     bool IsFixedSize { get; }\r
 701 \r
 702     /// <summary>\r
 703     /// On this list, this indexer is read/write.\r
 704     /// </summary>\r
 705     /// <exception cref="IndexOutOfRangeException"> if index is negative or\r
 706     /// &gt;= the size of the collection.</exception>\r
 707     /// <value>The index'th item of this list.</value>\r
 708     /// <param name="index">The index of the item to fetch or store.</param>\r
 709     new T this[int index] { get; set;}\r
 710 \r
 711     /// <summary>\r
 712     /// Insert an item at a specific index location in this list. \r
 713     /// </summary>\r
 714     /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
 715     /// &gt; the size of the collection.</exception>\r
 716     /// <exception cref="DuplicateNotAllowedException"> if the list has\r
 717     /// <code>AllowsDuplicates==false</code> and the item is \r
 718     /// already in the list.</exception>\r
 719     /// <param name="index">The index at which to insert.</param>\r
 720     /// <param name="item">The item to insert.</param>\r
 721     void Insert(int index, T item);\r
 722 \r
 723     /// <summary>\r
 724     /// Insert an item at the end of a compatible view, used as a pointer.\r
 725     /// <para>The <code>pointer</code> must be a view on the same list as\r
 726     /// <code>this</code> and the endpoitn of <code>pointer</code> must be\r
 727     /// a valid insertion point of <code>this</code></para>\r
 728     /// </summary>\r
 729     /// <exception cref="IncompatibleViewException">If <code>pointer</code> \r
 730     /// is not a view on the same list as <code>this</code></exception>\r
 731     /// <exception cref="IndexOutOfRangeException"><b>??????</b> if the endpoint of \r
 732     ///  <code>pointer</code> is not inside <code>this</code></exception>\r
 733     /// <exception cref="DuplicateNotAllowedException"> if the list has\r
 734     /// <code>AllowsDuplicates==false</code> and the item is \r
 735     /// already in the list.</exception>\r
 736     /// <param name="pointer"></param>\r
 737     /// <param name="item"></param>\r
 738     void Insert(IList<T> pointer, T item);\r
 739 \r
 740     /// <summary>\r
 741     /// Insert an item at the front of this list.\r
 742     /// <exception cref="DuplicateNotAllowedException"/> if the list has\r
 743     /// <code>AllowsDuplicates==false</code> and the item is \r
 744     /// already in the list.\r
 745     /// </summary>\r
 746     /// <param name="item">The item to insert.</param>\r
 747     void InsertFirst(T item);\r
 748 \r
 749     /// <summary>\r
 750     /// Insert an item at the back of this list.\r
 751     /// <exception cref="DuplicateNotAllowedException"/> if the list has\r
 752     /// <code>AllowsDuplicates==false</code> and the item is \r
 753     /// already in the list.\r
 754     /// </summary>\r
 755     /// <param name="item">The item to insert.</param>\r
 756     void InsertLast(T item);\r
 757 \r
 758     /// <summary>\r
 759     /// Insert into this list all items from an enumerable collection starting \r
 760     /// at a particular index.\r
 761     /// </summary>\r
 762     /// <exception cref="IndexOutOfRangeException"> if <code>index</code> is negative or\r
 763     /// &gt; the size of the collection.</exception>\r
 764     /// <exception cref="DuplicateNotAllowedException"> if the list has \r
 765     /// <code>AllowsDuplicates==false</code> and one of the items to insert is\r
 766     /// already in the list.</exception>\r
 767     /// <param name="index">Index to start inserting at</param>\r
 768     /// <param name="items">Items to insert</param>\r
 769     /// <typeparam name="U"></typeparam>\r
 770     void InsertAll<U>(int index, SCG.IEnumerable<U> items) where U : T;\r
 771 \r
 772     /// <summary>\r
 773     /// Create a new list consisting of the items of this list satisfying a \r
 774     /// certain predicate.\r
 775     /// </summary>\r
 776     /// <param name="filter">The filter delegate defining the predicate.</param>\r
 777     /// <returns>The new list.</returns>\r
 778     IList<T> FindAll(Fun<T, bool> filter);\r
 779 \r
 780     /// <summary>\r
 781     /// Create a new list consisting of the results of mapping all items of this\r
 782     /// list. The new list will use the default equalityComparer for the item type V.\r
 783     /// </summary>\r
 784     /// <typeparam name="V">The type of items of the new list</typeparam>\r
 785     /// <param name="mapper">The delegate defining the map.</param>\r
 786     /// <returns>The new list.</returns>\r
 787     IList<V> Map<V>(Fun<T, V> mapper);\r
 788 \r
 789     /// <summary>\r
 790     /// Create a new list consisting of the results of mapping all items of this\r
 791     /// list. The new list will use a specified equalityComparer for the item type.\r
 792     /// </summary>\r
 793     /// <typeparam name="V">The type of items of the new list</typeparam>\r
 794     /// <param name="mapper">The delegate defining the map.</param>\r
 795     /// <param name="equalityComparer">The equalityComparer to use for the new list</param>\r
 796     /// <returns>The new list.</returns>\r
 797     IList<V> Map<V>(Fun<T, V> mapper, SCG.IEqualityComparer<V> equalityComparer);\r
 798 \r
 799     /// <summary>\r
 800     /// Remove one item from the list: from the front if <code>FIFO</code>\r
 801     /// is true, else from the back.\r
 802     /// <exception cref="NoSuchItemException"/> if this list is empty.\r
 803     /// </summary>\r
 804     /// <returns>The removed item.</returns>\r
 805     T Remove();\r
 806 \r
 807     /// <summary>\r
 808     /// Remove one item from the front of the list.\r
 809     /// <exception cref="NoSuchItemException"/> if this list is empty.\r
 810     /// </summary>\r
 811     /// <returns>The removed item.</returns>\r
 812     T RemoveFirst();\r
 813 \r
 814     /// <summary>\r
 815     /// Remove one item from the back of the list.\r
 816     /// <exception cref="NoSuchItemException"/> if this list is empty.\r
 817     /// </summary>\r
 818     /// <returns>The removed item.</returns>\r
 819     T RemoveLast();\r
 820 \r
 821     /// <summary>\r
 822     /// Create a list view on this list. \r
 823     /// <exception cref="ArgumentOutOfRangeException"/> if the view would not fit into\r
 824     /// this list.\r
 825     /// </summary>\r
 826     /// <param name="start">The index in this list of the start of the view.</param>\r
 827     /// <param name="count">The size of the view.</param>\r
 828     /// <returns>The new list view.</returns>\r
 829     IList<T> View(int start, int count);\r
 830 \r
 831     /// <summary>\r
 832     /// Create a list view on this list containing the (first) occurrence of a particular item. \r
 833     /// <exception cref="NoSuchItemException"/> if the item is not in this list.\r
 834     /// </summary>\r
 835     /// <param name="item">The item to find.</param>\r
 836     /// <returns>The new list view.</returns>\r
 837     IList<T> ViewOf(T item);\r
 838 \r
 839     /// <summary>\r
 840     /// Create a list view on this list containing the last occurrence of a particular item. \r
 841     /// <exception cref="NoSuchItemException"/> if the item is not in this list.\r
 842     /// </summary>\r
 843     /// <param name="item">The item to find.</param>\r
 844     /// <returns>The new list view.</returns>\r
 845     IList<T> LastViewOf(T item);\r
 846 \r
 847     /// <summary>\r
 848     /// Null if this list is not a view.\r
 849     /// </summary>\r
 850     /// <value>Underlying list for view.</value>\r
 851     IList<T> Underlying { get;}\r
 852 \r
 853     /// <summary>\r
 854     /// </summary>\r
 855     /// <value>Offset for this list view or 0 for an underlying list.</value>\r
 856     int Offset { get;}\r
 857 \r
 858     /// <summary>\r
 859     /// \r
 860     /// </summary>\r
 861     /// <value></value>\r
 862     bool IsValid { get;}\r
 863 \r
 864     /// <summary>\r
 865     /// Slide this list view along the underlying list.\r
 866     /// </summary>\r
 867     /// <exception cref="NotAViewException"> if this list is not a view.</exception>\r
 868     /// <exception cref="ArgumentOutOfRangeException"> if the operation\r
 869     /// would bring either end of the view outside the underlying list.</exception>\r
 870     /// <param name="offset">The signed amount to slide: positive to slide\r
 871     /// towards the end.</param>\r
 872     IList<T> Slide(int offset);\r
 873 \r
 874     /// <summary>\r
 875     /// Slide this list view along the underlying list, changing its size.\r
 876     /// \r
 877     /// </summary>\r
 878     /// <exception cref="NotAViewException"> if this list is not a view.</exception>\r
 879     /// <exception cref="ArgumentOutOfRangeException"> if the operation\r
 880     /// would bring either end of the view outside the underlying list.</exception>\r
 881     /// <param name="offset">The signed amount to slide: positive to slide\r
 882     /// towards the end.</param>\r
 883     /// <param name="size">The new size of the view.</param>\r
 884     IList<T> Slide(int offset, int size);\r
 885 \r
 886     /// <summary>\r
 887     /// \r
 888     /// </summary>\r
 889     /// <param name="offset"></param>\r
 890     /// <returns></returns>\r
 891     bool TrySlide(int offset);\r
 892 \r
 893     /// <summary>\r
 894     /// \r
 895     /// </summary>\r
 896     /// <param name="offset"></param>\r
 897     /// <param name="size"></param>\r
 898     /// <returns></returns>\r
 899     bool TrySlide(int offset, int size);\r
 900 \r
 901     /// <summary>\r
 902     /// \r
 903     /// <para>Returns null if <code>otherView</code> is strictly to the left of this view</para>\r
 904     /// </summary>\r
 905     /// <param name="otherView"></param>\r
 906     /// <exception cref="IncompatibleViewException">If otherView does not have the same underlying list as this</exception>\r
 907     /// <exception cref="ArgumentOutOfRangeException">If <code>otherView</code> is strictly to the left of this view</exception>\r
 908     /// <returns></returns>\r
 909     IList<T> Span(IList<T> otherView);\r
 910 \r
 911     /// <summary>\r
 912     /// Reverse the list so the items are in the opposite sequence order.\r
 913     /// </summary>\r
 914     void Reverse();\r
 915 \r
 916     /// <summary>\r
 917     /// Check if this list is sorted according to the default sorting order\r
 918     /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class \r
 919     /// </summary>\r
 920     /// <exception cref="NotComparableException">if T is not comparable</exception>\r
 921     /// <returns>True if the list is sorted, else false.</returns>\r
 922     bool IsSorted();\r
 923 \r
 924     /// <summary>\r
 925     /// Check if this list is sorted according to a specific sorting order.\r
 926     /// </summary>\r
 927     /// <param name="comparer">The comparer defining the sorting order.</param>\r
 928     /// <returns>True if the list is sorted, else false.</returns>\r
 929     bool IsSorted(SCG.IComparer<T> comparer);\r
 930 \r
 931     /// <summary>\r
 932     /// Sort the items of the list according to the default sorting order\r
 933     /// for the item type T, as defined by the <see cref="T:C5.Comparer`1"/> class \r
 934     /// </summary>\r
 935     /// <exception cref="NotComparableException">if T is not comparable</exception>\r
 936     void Sort();\r
 937 \r
 938     /// <summary>\r
 939     /// Sort the items of the list according to a specified sorting order.\r
 940     /// <para>The sorting does not perform duplicate elimination or identify items\r
 941     /// according to the comparer or itemequalityComparer. I.e. the list as an \r
 942     /// unsequenced collection with binary equality, will not change.\r
 943     /// </para>\r
 944     /// </summary>\r
 945     /// <param name="comparer">The comparer defining the sorting order.</param>\r
 946     void Sort(SCG.IComparer<T> comparer);\r
 947 \r
 948 \r
 949     /// <summary>\r
 950     /// Randomly shuffle the items of this list. \r
 951     /// </summary>\r
 952     void Shuffle();\r
 953 \r
 954 \r
 955     /// <summary>\r
 956     /// Shuffle the items of this list according to a specific random source.\r
 957     /// </summary>\r
 958     /// <param name="rnd">The random source.</param>\r
 959     void Shuffle(Random rnd);\r
 960   }\r
 961 \r
 962 \r
 963   /// <summary>\r
 964   /// The base type of a priority queue handle\r
 965   /// </summary>\r
 966   /// <typeparam name="T"></typeparam>\r
 967   public interface IPriorityQueueHandle<T>\r
 968   {\r
 969     //TODO: make abstract and prepare for double dispatch:\r
 970     //public virtual bool Delete(IPriorityQueue<T> q) { throw new InvalidFooException();}\r
 971     //bool Replace(T item);\r
 972   }\r
 973 \r
 974 \r
 975   /// <summary>\r
 976   /// A generic collection of items prioritized by a comparison (order) relation.\r
 977   /// Supports adding items and reporting or removing extremal elements. \r
 978   /// <para>\r
 979   /// \r
 980   /// </para>\r
 981   /// When adding an item, the user may choose to have a handle allocated for this item in the queue. \r
 982   /// The resulting handle may be used for deleting the item even if not extremal, and for replacing the item.\r
 983   /// A priority queue typically only holds numeric priorities associated with some objects\r
 984   /// maintained separately in other collection objects.\r
 985   /// </summary>\r
 986   public interface IPriorityQueue<T> : IExtensible<T>\r
 987   {\r
 988     /// <summary>\r
 989     /// Find the current least item of this priority queue.\r
 990     /// </summary>\r
 991     /// <returns>The least item.</returns>\r
 992     T FindMin();\r
 993 \r
 994 \r
 995     /// <summary>\r
 996     /// Remove the least item from this  priority queue.\r
 997     /// </summary>\r
 998     /// <returns>The removed item.</returns>\r
 999     T DeleteMin();\r
1000 \r
1001 \r
1002     /// <summary>\r
1003     /// Find the current largest item of this priority queue.\r
1004     /// </summary>\r
1005     /// <returns>The largest item.</returns>\r
1006     T FindMax();\r
1007 \r
1008 \r
1009     /// <summary>\r
1010     /// Remove the largest item from this priority queue.\r
1011     /// </summary>\r
1012     /// <returns>The removed item.</returns>\r
1013     T DeleteMax();\r
1014 \r
1015     /// <summary>\r
1016     /// The comparer object supplied at creation time for this collection\r
1017     /// </summary>\r
1018     /// <value>The comparer</value>\r
1019     SCG.IComparer<T> Comparer { get;}\r
1020     /// <summary>\r
1021     /// Get or set the item corresponding to a handle. Throws exceptions on \r
1022     /// invalid handles.\r
1023     /// </summary>\r
1024     /// <param name="handle"></param>\r
1025     /// <returns></returns>\r
1026     T this[IPriorityQueueHandle<T> handle] { get; set;}\r
1027 \r
1028     /// <summary>\r
1029     /// Check if the entry corresponding to a handle is in the priority queue.\r
1030     /// </summary>\r
1031     /// <param name="handle"></param>\r
1032     /// <param name="item"></param>\r
1033     /// <returns></returns>\r
1034     bool Find(IPriorityQueueHandle<T> handle, out T item);\r
1035 \r
1036     /// <summary>\r
1037     /// Add an item to the priority queue, receiving a \r
1038     /// handle for the item in the queue, \r
1039     /// or reusing an existing unused handle.\r
1040     /// </summary>\r
1041     /// <param name="handle">On output: a handle for the added item. \r
1042     /// On input: null for allocating a new handle, or a currently unused handle for reuse. \r
1043     /// A handle for reuse must be compatible with this priority queue, \r
1044     /// by being created by a priority queue of the same runtime type, but not \r
1045     /// necessarily the same priority queue object.</param>\r
1046     /// <param name="item"></param>\r
1047     /// <returns></returns>\r
1048     bool Add(ref IPriorityQueueHandle<T> handle, T item);\r
1049 \r
1050     /// <summary>\r
1051     /// Delete an item with a handle from a priority queue\r
1052     /// </summary>\r
1053     /// <param name="handle">The handle for the item. The handle will be invalidated, but reusable.</param>\r
1054     /// <returns>The deleted item</returns>\r
1055     T Delete(IPriorityQueueHandle<T> handle);\r
1056 \r
1057     /// <summary>\r
1058     /// Replace an item with a handle in a priority queue with a new item. \r
1059     /// Typically used for changing the priority of some queued object.\r
1060     /// </summary>\r
1061     /// <param name="handle">The handle for the old item</param>\r
1062     /// <param name="item">The new item</param>\r
1063     /// <returns>The old item</returns>\r
1064     T Replace(IPriorityQueueHandle<T> handle, T item);\r
1065 \r
1066     /// <summary>\r
1067     /// Find the current least item of this priority queue.\r
1068     /// </summary>\r
1069     /// <param name="handle">On return: the handle of the item.</param>\r
1070     /// <returns>The least item.</returns>\r
1071     T FindMin(out IPriorityQueueHandle<T> handle);\r
1072 \r
1073     /// <summary>\r
1074     /// Find the current largest item of this priority queue.\r
1075     /// </summary>\r
1076     /// <param name="handle">On return: the handle of the item.</param>\r
1077     /// <returns>The largest item.</returns>\r
1078 \r
1079     T FindMax(out IPriorityQueueHandle<T> handle);\r
1080 \r
1081     /// <summary>\r
1082     /// Remove the least item from this  priority queue.\r
1083     /// </summary>\r
1084     /// <param name="handle">On return: the handle of the removed item.</param>\r
1085     /// <returns>The removed item.</returns>\r
1086 \r
1087     T DeleteMin(out IPriorityQueueHandle<T> handle);\r
1088 \r
1089     /// <summary>\r
1090     /// Remove the largest item from this  priority queue.\r
1091     /// </summary>\r
1092     /// <param name="handle">On return: the handle of the removed item.</param>\r
1093     /// <returns>The removed item.</returns>\r
1094     T DeleteMax(out IPriorityQueueHandle<T> handle);\r
1095   }\r
1096 \r
1097 \r
1098 \r
1099   /// <summary>\r
1100   /// A sorted collection, i.e. a collection where items are maintained and can be searched for in sorted order.\r
1101   /// Thus the sequence order is given as a sorting order.\r
1102   /// \r
1103   /// <para>The sorting order is defined by a comparer, an object of type IComparer&lt;T&gt; \r
1104   /// (<see cref="T:C5.IComparer`1"/>). Implementors of this interface will normally let the user \r
1105   /// define the comparer as an argument to a constructor. \r
1106   /// Usually there will also be constructors without a comparer argument, in which case the \r
1107   /// comparer should be the defalt comparer for the item type, <see cref="P:C5.Comparer`1.Default"/>.</para>\r
1108   /// \r
1109   /// <para>The comparer of the sorted collection is available as the <code>Comparer</code> property \r
1110   /// (<see cref="P:C5.ISorted`1.Comparer"/>).</para>\r
1111   /// \r
1112   /// <para>The methods are grouped according to\r
1113   /// <list>\r
1114   /// <item>Extrema: report or report and delete an extremal item. This is reminiscent of simplified priority queues.</item>\r
1115   /// <item>Nearest neighbor: report predecessor or successor in the collection of an item. Cut belongs to this group.</item>\r
1116   /// <item>Range: report a view of a range of elements or remove all elements in a range.</item>\r
1117   /// <item>AddSorted: add a collection of items known to be sorted in the same order (should be faster) (to be removed?)</item>\r
1118   /// </list>\r
1119   /// </para>\r
1120   /// \r
1121   /// <para>Since this interface extends ISequenced&lt;T&gt;, sorted collections will also have an \r
1122   /// item equalityComparer (<see cref="P:C5.IExtensible`1.EqualityComparer"/>). This equalityComparer will not be used in connection with \r
1123   /// the inner workings of the sorted collection, but will be used if the sorted collection is used as \r
1124   /// an item in a collection of unsequenced or sequenced collections, \r
1125   /// (<see cref="T:C5.ICollection`1"/> and <see cref="T:C5.ISequenced`1"/>)</para>\r
1126   /// \r
1127   /// <para>Note that code may check if two sorted collections has the same sorting order \r
1128   /// by checking if the Comparer properties are equal. This is done a few places in this library\r
1129   /// for optimization purposes.</para>\r
1130   /// </summary>\r
1131   public interface ISorted<T> : ISequenced<T>\r
1132   {\r
1133     /// <summary>\r
1134     /// Find the current least item of this sorted collection.\r
1135     /// </summary>\r
1136     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1137     /// <returns>The least item.</returns>\r
1138     T FindMin();\r
1139 \r
1140 \r
1141     /// <summary>\r
1142     /// Remove the least item from this sorted collection.\r
1143     /// </summary>\r
1144     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1145     /// <returns>The removed item.</returns>\r
1146     T DeleteMin();\r
1147 \r
1148 \r
1149     /// <summary>\r
1150     /// Find the current largest item of this sorted collection.\r
1151     /// </summary>\r
1152     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1153     /// <returns>The largest item.</returns>\r
1154     T FindMax();\r
1155 \r
1156 \r
1157     /// <summary>\r
1158     /// Remove the largest item from this sorted collection.\r
1159     /// </summary>\r
1160     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1161     /// <returns>The removed item.</returns>\r
1162     T DeleteMax();\r
1163 \r
1164     /// <summary>\r
1165     /// The comparer object supplied at creation time for this sorted collection.\r
1166     /// </summary>\r
1167     /// <value>The comparer</value>\r
1168     SCG.IComparer<T> Comparer { get;}\r
1169 \r
1170     /// <summary>\r
1171     /// Find the strict predecessor in the sorted collection of a particular value,\r
1172     /// that is, the largest item in the collection less than the supplied value.\r
1173     /// </summary>\r
1174     /// <exception cref="NoSuchItemException"> if no such element exists (the\r
1175     /// supplied  value is less than or equal to the minimum of this collection.)</exception>\r
1176     /// <param name="item">The item to find the predecessor for.</param>\r
1177     /// <returns>The predecessor.</returns>\r
1178     T Predecessor(T item);\r
1179 \r
1180 \r
1181     /// <summary>\r
1182     /// Find the strict successor in the sorted collection of a particular value,\r
1183     /// that is, the least item in the collection greater than the supplied value.\r
1184     /// </summary>\r
1185     /// <exception cref="NoSuchItemException"> if no such element exists (the\r
1186     /// supplied  value is greater than or equal to the maximum of this collection.)</exception>\r
1187     /// <param name="item">The item to find the successor for.</param>\r
1188     /// <returns>The successor.</returns>\r
1189     T Successor(T item);\r
1190 \r
1191 \r
1192     /// <summary>\r
1193     /// Find the weak predecessor in the sorted collection of a particular value,\r
1194     /// that is, the largest item in the collection less than or equal to the supplied value.\r
1195     /// </summary>\r
1196     /// <exception cref="NoSuchItemException"> if no such element exists (the\r
1197     /// supplied  value is less than the minimum of this collection.)</exception>\r
1198     /// <param name="item">The item to find the weak predecessor for.</param>\r
1199     /// <returns>The weak predecessor.</returns>\r
1200     T WeakPredecessor(T item);\r
1201 \r
1202 \r
1203     /// <summary>\r
1204     /// Find the weak successor in the sorted collection of a particular value,\r
1205     /// that is, the least item in the collection greater than or equal to the supplied value.\r
1206     /// </summary>\r
1207     /// <exception cref="NoSuchItemException"> if no such element exists (the\r
1208     /// supplied  value is greater than the maximum of this collection.)</exception>\r
1209     ///<param name="item">The item to find the weak successor for.</param>\r
1210     /// <returns>The weak successor.</returns>\r
1211     T WeakSuccessor(T item);\r
1212 \r
1213 \r
1214     /// <summary>\r
1215     /// Given a "cut" function from the items of the sorted collection to <code>int</code>\r
1216     /// whose only sign changes when going through items in increasing order\r
1217     /// can be \r
1218     /// <list>\r
1219     /// <item>from positive to zero</item>\r
1220     /// <item>from positive to negative</item>\r
1221     /// <item>from zero to negative</item>\r
1222     /// </list>\r
1223     /// The "cut" function is supplied as the <code>CompareTo</code> method \r
1224     /// of an object <code>c</code> implementing \r
1225     /// <code>IComparable&lt;T&gt;</code>. \r
1226     /// A typical example is the case where <code>T</code> is comparable and \r
1227     /// <code>cutFunction</code> is itself of type <code>T</code>.\r
1228     /// <para>This method performs a search in the sorted collection for the ranges in which the\r
1229     /// "cut" function is negative, zero respectively positive. If <code>T</code> is comparable\r
1230     /// and <code>c</code> is of type <code>T</code>, this is a safe way (no exceptions thrown) \r
1231     /// to find predecessor and successor of <code>c</code>.\r
1232     /// </para>\r
1233     /// <para> If the supplied cut function does not satisfy the sign-change condition, \r
1234     /// the result of this call is undefined.\r
1235     /// </para>\r
1236     /// \r
1237     /// </summary>\r
1238     /// <param name="cutFunction">The cut function <code>T</code> to <code>int</code>, given\r
1239     /// by the <code>CompareTo</code> method of an object implementing \r
1240     /// <code>IComparable&lt;T&gt;</code>.</param>\r
1241     /// <param name="low">Returns the largest item in the collection, where the\r
1242     /// cut function is positive (if any).</param>\r
1243     /// <param name="lowIsValid">Returns true if the cut function is positive somewhere\r
1244     /// on this collection.</param>\r
1245     /// <param name="high">Returns the least item in the collection, where the\r
1246     /// cut function is negative (if any).</param>\r
1247     /// <param name="highIsValid">Returns true if the cut function is negative somewhere\r
1248     /// on this collection.</param>\r
1249     /// <returns>True if the cut function is zero somewhere\r
1250     /// on this collection.</returns>\r
1251     bool Cut(IComparable<T> cutFunction, out T low, out bool lowIsValid, out T high, out bool highIsValid);\r
1252 \r
1253 \r
1254     /// <summary>\r
1255     /// Query this sorted collection for items greater than or equal to a supplied value.\r
1256     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1257     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1258     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1259     /// </summary>\r
1260     /// <param name="bot">The lower bound (inclusive).</param>\r
1261     /// <returns>The result directed collection.</returns>\r
1262     IDirectedEnumerable<T> RangeFrom(T bot);\r
1263 \r
1264 \r
1265     /// <summary>\r
1266     /// Query this sorted collection for items between two supplied values.\r
1267     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1268     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1269     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1270     /// </summary>\r
1271     /// <param name="bot">The lower bound (inclusive).</param>\r
1272     /// <param name="top">The upper bound (exclusive).</param>\r
1273     /// <returns>The result directed collection.</returns>\r
1274     IDirectedEnumerable<T> RangeFromTo(T bot, T top);\r
1275 \r
1276 \r
1277     /// <summary>\r
1278     /// Query this sorted collection for items less than a supplied value.\r
1279     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1280     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1281     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1282     /// </summary>\r
1283     /// <param name="top">The upper bound (exclusive).</param>\r
1284     /// <returns>The result directed collection.</returns>\r
1285     IDirectedEnumerable<T> RangeTo(T top);\r
1286 \r
1287 \r
1288     /// <summary>\r
1289     /// Create a directed collection with the same items as this collection.\r
1290     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1291     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1292     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1293     /// </summary>\r
1294     /// <returns>The result directed collection.</returns>\r
1295     IDirectedCollectionValue<T> RangeAll();\r
1296 \r
1297 \r
1298     //TODO: remove now that we assume that we can check the sorting order?\r
1299     /// <summary>\r
1300     /// Add all the items from another collection with an enumeration order that \r
1301     /// is increasing in the items.\r
1302     /// </summary>\r
1303     /// <exception cref="ArgumentException"> if the enumerated items turns out\r
1304     /// not to be in increasing order.</exception>\r
1305     /// <param name="items">The collection to add.</param>\r
1306     /// <typeparam name="U"></typeparam>\r
1307     void AddSorted<U>(SCG.IEnumerable<U> items) where U : T;\r
1308 \r
1309 \r
1310     /// <summary>\r
1311     /// Remove all items of this collection above or at a supplied threshold.\r
1312     /// </summary>\r
1313     /// <param name="low">The lower threshold (inclusive).</param>\r
1314     void RemoveRangeFrom(T low);\r
1315 \r
1316 \r
1317     /// <summary>\r
1318     /// Remove all items of this collection between two supplied thresholds.\r
1319     /// </summary>\r
1320     /// <param name="low">The lower threshold (inclusive).</param>\r
1321     /// <param name="hi">The upper threshold (exclusive).</param>\r
1322     void RemoveRangeFromTo(T low, T hi);\r
1323 \r
1324 \r
1325     /// <summary>\r
1326     /// Remove all items of this collection below a supplied threshold.\r
1327     /// </summary>\r
1328     /// <param name="hi">The upper threshold (exclusive).</param>\r
1329     void RemoveRangeTo(T hi);\r
1330   }\r
1331 \r
1332 \r
1333 \r
1334   /// <summary>\r
1335   /// A collection where items are maintained in sorted order together\r
1336   /// with their indexes in that order.\r
1337   /// </summary>\r
1338   public interface IIndexedSorted<T> : ISorted<T>, IIndexed<T>\r
1339   {\r
1340     /// <summary>\r
1341     /// Determine the number of items at or above a supplied threshold.\r
1342     /// </summary>\r
1343     /// <param name="bot">The lower bound (inclusive)</param>\r
1344     /// <returns>The number of matcing items.</returns>\r
1345     int CountFrom(T bot);\r
1346 \r
1347 \r
1348     /// <summary>\r
1349     /// Determine the number of items between two supplied thresholds.\r
1350     /// </summary>\r
1351     /// <param name="bot">The lower bound (inclusive)</param>\r
1352     /// <param name="top">The upper bound (exclusive)</param>\r
1353     /// <returns>The number of matcing items.</returns>\r
1354     int CountFromTo(T bot, T top);\r
1355 \r
1356 \r
1357     /// <summary>\r
1358     /// Determine the number of items below a supplied threshold.\r
1359     /// </summary>\r
1360     /// <param name="top">The upper bound (exclusive)</param>\r
1361     /// <returns>The number of matcing items.</returns>\r
1362     int CountTo(T top);\r
1363 \r
1364 \r
1365     /// <summary>\r
1366     /// Query this sorted collection for items greater than or equal to a supplied value.\r
1367     /// </summary>\r
1368     /// <param name="bot">The lower bound (inclusive).</param>\r
1369     /// <returns>The result directed collection.</returns>\r
1370     new IDirectedCollectionValue<T> RangeFrom(T bot);\r
1371 \r
1372 \r
1373     /// <summary>\r
1374     /// Query this sorted collection for items between two supplied values.\r
1375     /// </summary>\r
1376     /// <param name="bot">The lower bound (inclusive).</param>\r
1377     /// <param name="top">The upper bound (exclusive).</param>\r
1378     /// <returns>The result directed collection.</returns>\r
1379     new IDirectedCollectionValue<T> RangeFromTo(T bot, T top);\r
1380 \r
1381 \r
1382     /// <summary>\r
1383     /// Query this sorted collection for items less than a supplied value.\r
1384     /// </summary>\r
1385     /// <param name="top">The upper bound (exclusive).</param>\r
1386     /// <returns>The result directed collection.</returns>\r
1387     new IDirectedCollectionValue<T> RangeTo(T top);\r
1388 \r
1389 \r
1390     /// <summary>\r
1391     /// Create a new indexed sorted collection consisting of the items of this\r
1392     /// indexed sorted collection satisfying a certain predicate.\r
1393     /// </summary>\r
1394     /// <param name="predicate">The filter delegate defining the predicate.</param>\r
1395     /// <returns>The new indexed sorted collection.</returns>\r
1396     IIndexedSorted<T> FindAll(Fun<T, bool> predicate);\r
1397 \r
1398 \r
1399     /// <summary>\r
1400     /// Create a new indexed sorted collection consisting of the results of\r
1401     /// mapping all items of this list.\r
1402     /// <exception cref="ArgumentException"/> if the map is not increasing over \r
1403     /// the items of this collection (with respect to the two given comparison \r
1404     /// relations).\r
1405     /// </summary>\r
1406     /// <param name="mapper">The delegate definging the map.</param>\r
1407     /// <param name="comparer">The comparion relation to use for the result.</param>\r
1408     /// <returns>The new sorted collection.</returns>\r
1409     IIndexedSorted<V> Map<V>(Fun<T, V> mapper, SCG.IComparer<V> comparer);\r
1410   }\r
1411 \r
1412 \r
1413 \r
1414   /// <summary>\r
1415   /// The type of a sorted collection with persistence\r
1416   /// </summary>\r
1417   public interface IPersistentSorted<T> : ISorted<T>, IDisposable\r
1418   {\r
1419     /// <summary>\r
1420     /// Make a (read-only) snap shot of this collection.\r
1421     /// </summary>\r
1422     /// <returns>The snap shot.</returns>\r
1423     ISorted<T> Snapshot();\r
1424   }\r
1425 \r
1426 \r
1427 \r
1428   /*************************************************************************/\r
1429   /// <summary>\r
1430   /// A dictionary with keys of type K and values of type V. Equivalent to a\r
1431   /// finite partial map from K to V.\r
1432   /// </summary>\r
1433   public interface IDictionary<K, V> : ICollectionValue<KeyValuePair<K, V>>, ICloneable\r
1434   {\r
1435     /// <summary>\r
1436     /// The key equalityComparer.\r
1437     /// </summary>\r
1438     /// <value></value>\r
1439     SCG.IEqualityComparer<K> EqualityComparer { get;}\r
1440 \r
1441     /// <summary>\r
1442     /// Indexer for dictionary.\r
1443     /// </summary>\r
1444     /// <exception cref="NoSuchItemException"> if no entry is found. </exception>\r
1445     /// <value>The value corresponding to the key</value>\r
1446     V this[K key] { get; set;}\r
1447 \r
1448 \r
1449     /// <summary>\r
1450     /// \r
1451     /// </summary>\r
1452     /// <value>True if dictionary is read-only</value>\r
1453     bool IsReadOnly { get;}\r
1454 \r
1455 \r
1456     /// <summary>\r
1457     /// \r
1458     /// </summary>\r
1459     /// <value>A collection containg the all the keys of the dictionary</value>\r
1460     ICollectionValue<K> Keys { get;}\r
1461 \r
1462 \r
1463     /// <summary>\r
1464     /// \r
1465     /// </summary>\r
1466     /// <value>A collection containing all the values of the dictionary</value>\r
1467     ICollectionValue<V> Values { get;}\r
1468 \r
1469     /// <summary>\r
1470     /// \r
1471     /// </summary>\r
1472     /// <value>A delegate of type <see cref="T:C5.Fun`2"/> defining the partial function from K to V give by the dictionary.</value>\r
1473     Fun<K, V> Fun { get; }\r
1474 \r
1475 \r
1476     //TODO: resolve inconsistency: Add thows exception if key already there, AddAll ignores keys already There?\r
1477     /// <summary>\r
1478     /// Add a new (key, value) pair (a mapping) to the dictionary.\r
1479     /// </summary>\r
1480     /// <exception cref="DuplicateNotAllowedException"> if there already is an entry with the same key. </exception>>\r
1481     /// <param name="key">Key to add</param>\r
1482     /// <param name="val">Value to add</param>\r
1483     void Add(K key, V val);\r
1484 \r
1485     /// <summary>\r
1486     /// Add the entries from a collection of <see cref="T:C5.KeyValuePair`2"/> pairs to this dictionary.\r
1487     /// </summary>\r
1488     /// <exception cref="DuplicateNotAllowedException"> \r
1489     /// If the input contains duplicate keys or a key already present in this dictionary.</exception>\r
1490     /// <param name="entries"></param>\r
1491     void AddAll<U, W>(SCG.IEnumerable<KeyValuePair<U, W>> entries)\r
1492         where U : K\r
1493         where W : V\r
1494       ;\r
1495 \r
1496     /// <summary>\r
1497     /// The value is symbolic indicating the type of asymptotic complexity\r
1498     /// in terms of the size of this collection (worst-case or amortized as\r
1499     /// relevant). \r
1500     /// <para>See <see cref="T:C5.Speed"/> for the set of symbols.</para>\r
1501     /// </summary>\r
1502     /// <value>A characterization of the speed of lookup operations\r
1503     /// (<code>Contains()</code> etc.) of the implementation of this dictionary.</value>\r
1504     Speed ContainsSpeed { get;}\r
1505 \r
1506     /// <summary>\r
1507     /// Check whether this collection contains all the values in another collection.\r
1508     /// If this collection has bag semantics (<code>AllowsDuplicates==true</code>)\r
1509     /// the check is made with respect to multiplicities, else multiplicities\r
1510     /// are not taken into account.\r
1511     /// </summary>\r
1512     /// <param name="items">The </param>\r
1513     /// <returns>True if all values in <code>items</code>is in this collection.</returns>\r
1514       bool ContainsAll<H>(SCG.IEnumerable<H> items) where H : K;\r
1515 \r
1516     /// <summary>\r
1517     /// Remove an entry with a given key from the dictionary\r
1518     /// </summary>\r
1519     /// <param name="key">The key of the entry to remove</param>\r
1520     /// <returns>True if an entry was found (and removed)</returns>\r
1521     bool Remove(K key);\r
1522 \r
1523 \r
1524     /// <summary>\r
1525     /// Remove an entry with a given key from the dictionary and report its value.\r
1526     /// </summary>\r
1527     /// <param name="key">The key of the entry to remove</param>\r
1528     /// <param name="val">On exit, the value of the removed entry</param>\r
1529     /// <returns>True if an entry was found (and removed)</returns>\r
1530     bool Remove(K key, out V val);\r
1531 \r
1532 \r
1533     /// <summary>\r
1534     /// Remove all entries from the dictionary\r
1535     /// </summary>\r
1536     void Clear();\r
1537 \r
1538 \r
1539     /// <summary>\r
1540     /// Check if there is an entry with a specified key\r
1541     /// </summary>\r
1542     /// <param name="key">The key to look for</param>\r
1543     /// <returns>True if key was found</returns>\r
1544     bool Contains(K key);\r
1545 \r
1546 \r
1547     /// <summary>\r
1548     /// Check if there is an entry with a specified key and report the corresponding\r
1549     /// value if found. This can be seen as a safe form of "val = this[key]".\r
1550     /// </summary>\r
1551     /// <param name="key">The key to look for</param>\r
1552     /// <param name="val">On exit, the value of the entry</param>\r
1553     /// <returns>True if key was found</returns>\r
1554     bool Find(K key, out V val);\r
1555 \r
1556     /// <summary>\r
1557     /// Check if there is an entry with a specified key and report the corresponding\r
1558     /// value if found. This can be seen as a safe form of "val = this[key]".\r
1559     /// </summary>\r
1560     /// <param name="key">The key to look for</param>\r
1561     /// <param name="val">On exit, the value of the entry</param>\r
1562     /// <returns>True if key was found</returns>\r
1563     bool Find(ref K key, out V val);\r
1564 \r
1565 \r
1566     /// <summary>\r
1567     /// Look for a specific key in the dictionary and if found replace the value with a new one.\r
1568     /// This can be seen as a non-adding version of "this[key] = val".\r
1569     /// </summary>\r
1570     /// <param name="key">The key to look for</param>\r
1571     /// <param name="val">The new value</param>\r
1572     /// <returns>True if key was found</returns>\r
1573     bool Update(K key, V val);          //no-adding                                     \r
1574 \r
1575 \r
1576     /// <summary>\r
1577     /// Look for a specific key in the dictionary and if found replace the value with a new one.\r
1578     /// This can be seen as a non-adding version of "this[key] = val" reporting the old value.\r
1579     /// </summary>\r
1580     /// <param name="key">The key to look for</param>\r
1581     /// <param name="val">The new value</param>\r
1582     /// <param name="oldval">The old value if any</param>\r
1583     /// <returns>True if key was found</returns>\r
1584     bool Update(K key, V val, out V oldval);          //no-adding                                       \r
1585 \r
1586     /// <summary>\r
1587     /// Look for a specific key in the dictionary. If found, report the corresponding value,\r
1588     /// else add an entry with the key and the supplied value.\r
1589     /// </summary>\r
1590     /// <param name="key">The key to look for</param>\r
1591     /// <param name="val">On entry the value to add if the key is not found.\r
1592     /// On exit the value found if any.</param>\r
1593     /// <returns>True if key was found</returns>\r
1594     bool FindOrAdd(K key, ref V val);   //mixture\r
1595 \r
1596 \r
1597     /// <summary>\r
1598     /// Update value in dictionary corresponding to key if found, else add new entry.\r
1599     /// More general than "this[key] = val;" by reporting if key was found.\r
1600     /// </summary>\r
1601     /// <param name="key">The key to look for</param>\r
1602     /// <param name="val">The value to add or replace with.</param>\r
1603     /// <returns>True if key was found and value updated.</returns>\r
1604     bool UpdateOrAdd(K key, V val);\r
1605 \r
1606 \r
1607     /// <summary>\r
1608     /// Update value in dictionary corresponding to key if found, else add new entry.\r
1609     /// More general than "this[key] = val;" by reporting if key was found.\r
1610     /// </summary>\r
1611     /// <param name="key">The key to look for</param>\r
1612     /// <param name="val">The value to add or replace with.</param>\r
1613     /// <param name="oldval">The old value if any</param>\r
1614     /// <returns>True if key was found and value updated.</returns>\r
1615     bool UpdateOrAdd(K key, V val, out V oldval);\r
1616 \r
1617 \r
1618     /// <summary>\r
1619     /// Check the integrity of the internal data structures of this dictionary.\r
1620     /// Only avaliable in DEBUG builds???\r
1621     /// </summary>\r
1622     /// <returns>True if check does not fail.</returns>\r
1623     bool Check();\r
1624   }\r
1625 \r
1626 \r
1627 \r
1628   /// <summary>\r
1629   /// A dictionary with sorted keys.\r
1630   /// </summary>\r
1631   public interface ISortedDictionary<K, V> : IDictionary<K, V>\r
1632   {\r
1633     /// <summary>\r
1634     /// \r
1635     /// </summary>\r
1636     /// <value></value>\r
1637     new ISorted<K> Keys { get;}\r
1638 \r
1639     /// <summary>\r
1640     /// Find the current least item of this sorted collection.\r
1641     /// </summary>\r
1642     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1643     /// <returns>The least item.</returns>\r
1644     KeyValuePair<K, V> FindMin();\r
1645 \r
1646 \r
1647     /// <summary>\r
1648     /// Remove the least item from this sorted collection.\r
1649     /// </summary>\r
1650     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1651     /// <returns>The removed item.</returns>\r
1652     KeyValuePair<K, V> DeleteMin();\r
1653 \r
1654 \r
1655     /// <summary>\r
1656     /// Find the current largest item of this sorted collection.\r
1657     /// </summary>\r
1658     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1659     /// <returns>The largest item.</returns>\r
1660     KeyValuePair<K, V> FindMax();\r
1661 \r
1662 \r
1663     /// <summary>\r
1664     /// Remove the largest item from this sorted collection.\r
1665     /// </summary>\r
1666     /// <exception cref="NoSuchItemException"> if the collection is empty.</exception>\r
1667     /// <returns>The removed item.</returns>\r
1668     KeyValuePair<K, V> DeleteMax();\r
1669 \r
1670     /// <summary>\r
1671     /// The key comparer used by this dictionary.\r
1672     /// </summary>\r
1673     /// <value></value>\r
1674     SCG.IComparer<K> Comparer { get;}\r
1675 \r
1676     /// <summary>\r
1677     /// Find the entry with the largest key less than a given key.\r
1678     /// </summary>\r
1679     /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
1680     /// <param name="key">The key to compare to</param>\r
1681     /// <returns>The entry</returns>\r
1682     KeyValuePair<K, V> Predecessor(K key);\r
1683 \r
1684 \r
1685     /// <summary>\r
1686     /// Find the entry with the least key greater than a given key.\r
1687     /// </summary>\r
1688     /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
1689     /// <param name="key">The key to compare to</param>\r
1690     /// <returns>The entry</returns>\r
1691     KeyValuePair<K, V> Successor(K key);\r
1692 \r
1693 \r
1694     /// <summary>\r
1695     /// Find the entry with the largest key less than or equal to a given key.\r
1696     /// </summary>\r
1697     /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
1698     /// <param name="key">The key to compare to</param>\r
1699     /// <returns>The entry</returns>\r
1700     KeyValuePair<K, V> WeakPredecessor(K key);\r
1701 \r
1702 \r
1703     /// <summary>\r
1704     /// Find the entry with the least key greater than or equal to a given key.\r
1705     /// </summary>\r
1706     /// <exception cref="NoSuchItemException"> if there is no such entry. </exception>\r
1707     /// <param name="key">The key to compare to</param>\r
1708     /// <returns>The entry</returns>\r
1709     KeyValuePair<K, V> WeakSuccessor(K key);\r
1710 \r
1711     /// <summary>\r
1712     /// Given a "cut" function from the items of the sorted collection to <code>int</code>\r
1713     /// whose only sign changes when going through items in increasing order\r
1714     /// can be \r
1715     /// <list>\r
1716     /// <item>from positive to zero</item>\r
1717     /// <item>from positive to negative</item>\r
1718     /// <item>from zero to negative</item>\r
1719     /// </list>\r
1720     /// The "cut" function is supplied as the <code>CompareTo</code> method \r
1721     /// of an object <code>c</code> implementing \r
1722     /// <code>IComparable&lt;K&gt;</code>. \r
1723     /// A typical example is the case where <code>K</code> is comparable and \r
1724     /// <code>c</code> is itself of type <code>K</code>.\r
1725     /// <para>This method performs a search in the sorted collection for the ranges in which the\r
1726     /// "cut" function is negative, zero respectively positive. If <code>K</code> is comparable\r
1727     /// and <code>c</code> is of type <code>K</code>, this is a safe way (no exceptions thrown) \r
1728     /// to find predecessor and successor of <code>c</code>.\r
1729     /// </para>\r
1730     /// <para> If the supplied cut function does not satisfy the sign-change condition, \r
1731     /// the result of this call is undefined.\r
1732     /// </para>\r
1733     /// \r
1734     /// </summary>\r
1735     /// <param name="cutFunction">The cut function <code>K</code> to <code>int</code>, given\r
1736     /// by the <code>CompareTo</code> method of an object implementing \r
1737     /// <code>IComparable&lt;K&gt;</code>.</param>\r
1738     /// <param name="lowEntry">Returns the largest item in the collection, where the\r
1739     /// cut function is positive (if any).</param>\r
1740     /// <param name="lowIsValid">Returns true if the cut function is positive somewhere\r
1741     /// on this collection.</param>\r
1742     /// <param name="highEntry">Returns the least item in the collection, where the\r
1743     /// cut function is negative (if any).</param>\r
1744     /// <param name="highIsValid">Returns true if the cut function is negative somewhere\r
1745     /// on this collection.</param>\r
1746     /// <returns>True if the cut function is zero somewhere\r
1747     /// on this collection.</returns>\r
1748     bool Cut(IComparable<K> cutFunction, out KeyValuePair<K, V> lowEntry, out bool lowIsValid, out KeyValuePair<K, V> highEntry, out bool highIsValid);\r
1749 \r
1750     /// <summary>\r
1751     /// Query this sorted collection for items greater than or equal to a supplied value.\r
1752     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1753     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1754     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1755     /// </summary>\r
1756     /// <param name="bot">The lower bound (inclusive).</param>\r
1757     /// <returns>The result directed collection.</returns>\r
1758     IDirectedEnumerable<KeyValuePair<K, V>> RangeFrom(K bot);\r
1759 \r
1760 \r
1761     /// <summary>\r
1762     /// Query this sorted collection for items between two supplied values.\r
1763     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1764     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1765     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1766     /// </summary>\r
1767     /// <param name="lowerBound">The lower bound (inclusive).</param>\r
1768     /// <param name="upperBound">The upper bound (exclusive).</param>\r
1769     /// <returns>The result directed collection.</returns>\r
1770     IDirectedEnumerable<KeyValuePair<K, V>> RangeFromTo(K lowerBound, K upperBound);\r
1771 \r
1772 \r
1773     /// <summary>\r
1774     /// Query this sorted collection for items less than a supplied value.\r
1775     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1776     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1777     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1778     /// </summary>\r
1779     /// <param name="top">The upper bound (exclusive).</param>\r
1780     /// <returns>The result directed collection.</returns>\r
1781     IDirectedEnumerable<KeyValuePair<K, V>> RangeTo(K top);\r
1782 \r
1783 \r
1784     /// <summary>\r
1785     /// Create a directed collection with the same items as this collection.\r
1786     /// <para>The returned collection is not a copy but a view into the collection.</para>\r
1787     /// <para>The view is fragile in the sense that changes to the underlying collection will \r
1788     /// invalidate the view so that further operations on the view throws InvalidView exceptions.</para>\r
1789     /// </summary>\r
1790     /// <returns>The result directed collection.</returns>\r
1791     IDirectedCollectionValue<KeyValuePair<K, V>> RangeAll();\r
1792 \r
1793 \r
1794     //TODO: remove now that we assume that we can check the sorting order?\r
1795     /// <summary>\r
1796     /// Add all the items from another collection with an enumeration order that \r
1797     /// is increasing in the items.\r
1798     /// </summary>\r
1799     /// <exception cref="ArgumentException"> if the enumerated items turns out\r
1800     /// not to be in increasing order.</exception>\r
1801     /// <param name="items">The collection to add.</param>\r
1802     void AddSorted(SCG.IEnumerable<KeyValuePair<K, V>> items);\r
1803 \r
1804 \r
1805     /// <summary>\r
1806     /// Remove all items of this collection above or at a supplied threshold.\r
1807     /// </summary>\r
1808     /// <param name="low">The lower threshold (inclusive).</param>\r
1809     void RemoveRangeFrom(K low);\r
1810 \r
1811 \r
1812     /// <summary>\r
1813     /// Remove all items of this collection between two supplied thresholds.\r
1814     /// </summary>\r
1815     /// <param name="low">The lower threshold (inclusive).</param>\r
1816     /// <param name="hi">The upper threshold (exclusive).</param>\r
1817     void RemoveRangeFromTo(K low, K hi);\r
1818 \r
1819 \r
1820     /// <summary>\r
1821     /// Remove all items of this collection below a supplied threshold.\r
1822     /// </summary>\r
1823     /// <param name="hi">The upper threshold (exclusive).</param>\r
1824     void RemoveRangeTo(K hi);\r
1825   }\r
1826 \r
1827 \r
1828 \r
1829   /*******************************************************************/\r
1830   /*/// <summary>\r
1831   /// The type of an item comparer\r
1832   /// <i>Implementations of this interface must asure that the method is self-consistent\r
1833   /// and defines a sorting order on items, or state precise conditions under which this is true.</i>\r
1834   /// <i>Implementations <b>must</b> assure that repeated calls of\r
1835   /// the method to the same (in reference or binary identity sense) arguments \r
1836   /// will return values with the same sign (-1, 0 or +1), or state precise conditions\r
1837   /// under which the user \r
1838   /// can be assured repeated calls will return the same sign.</i>\r
1839   /// <i>Implementations of this interface must always return values from the method\r
1840   /// and never throw exceptions.</i>\r
1841   /// <i>This interface is identical to System.Collections.Generic.IComparer&lt;T&gt;</i>\r
1842   /// </summary>\r
1843   public interface IComparer<T>\r
1844   {\r
1845     /// <summary>\r
1846     /// Compare two items with respect to this item comparer\r
1847     /// </summary>\r
1848     /// <param name="item1">First item</param>\r
1849     /// <param name="item2">Second item</param>\r
1850     /// <returns>Positive if item1 is greater than item2, 0 if they are equal, negative if item1 is less than item2</returns>\r
1851     int Compare(T item1, T item2);\r
1852   }\r
1853 \r
1854   /// <summary>\r
1855   /// The type of an item equalityComparer. \r
1856   /// <i>Implementations of this interface <b>must</b> assure that the methods are \r
1857   /// consistent, that is, that whenever two items i1 and i2 satisfies that Equals(i1,i2)\r
1858   /// returns true, then GetHashCode returns the same value for i1 and i2.</i>\r
1859   /// <i>Implementations of this interface <b>must</b> assure that repeated calls of\r
1860   /// the methods to the same (in reference or binary identity sense) arguments \r
1861   /// will return the same values, or state precise conditions under which the user \r
1862   /// can be assured repeated calls will return the same values.</i>\r
1863   /// <i>Implementations of this interface must always return values from the methods\r
1864   /// and never throw exceptions.</i>\r
1865   /// <i>This interface is similar in function to System.IKeyComparer&lt;T&gt;</i>\r
1866   /// </summary>\r
1867   public interface SCG.IEqualityComparer<T>\r
1868   {\r
1869     /// <summary>\r
1870     /// Get the hash code with respect to this item equalityComparer\r
1871     /// </summary>\r
1872     /// <param name="item">The item</param>\r
1873     /// <returns>The hash code</returns>\r
1874     int GetHashCode(T item);\r
1875 \r
1876 \r
1877     /// <summary>\r
1878     /// Check if two items are equal with respect to this item equalityComparer\r
1879     /// </summary>\r
1880     /// <param name="item1">first item</param>\r
1881     /// <param name="item2">second item</param>\r
1882     /// <returns>True if equal</returns>\r
1883     bool Equals(T item1, T item2);\r
1884   }*/\r
1885 }\r
1886 \r
1887 #endif\r