mcs/class/Mono.C5/arrays/HashedArray.cs

   1 #if NET_2_0
   2 /*
   3  Copyright (c) 2003-2004 Niels Kokholm <kokholm@itu.dk> and Peter Sestoft <sestoft@dina.kvl.dk>
   4  Permission is hereby granted, free of charge, to any person obtaining a copy
   5  of this software and associated documentation files (the "Software"), to deal
   6  in the Software without restriction, including without limitation the rights
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  copies of the Software, and to permit persons to whom the Software is
   9  furnished to do so, subject to the following conditions:
  10
  11  The above copyright notice and this permission notice shall be included in
  12  all copies or substantial portions of the Software.
  13
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  SOFTWARE.
  21 */
  22
  23 using System;
  24 using System.Diagnostics;
  25 using MSG = System.Collections.Generic;
  26 namespace C5
  27 {
  28         /// <summary>
  29         /// A set collection based on a dynamic  array combined with a hash index
  30         /// for item to index lookup.
  31         /// </summary>
  32         public class HashedArrayList<T>: ArrayList<T>, IList<T>
  33         {
  34                 #region Fields
  35
  36                 HashSet<KeyValuePair<T,int>> index;
  37
  38                 #endregion
  39
  40                 #region Util
  41
  42                 private void reindex(int start) { reindex(start, underlyingsize); }
  43
  44
  45                 private void reindex(int start, int end)
  46                 {
  47                         for (int j = start; j < end; j++)
  48                                 index.Update(new KeyValuePair<T,int>(array[j], j));
  49                 }
  50
  51
  52                 /// <summary>
  53                 /// Internal version of IndexOf without modification checks.
  54                 /// </summary>
  55                 /// <param name="item">Item to look for</param>
  56                 /// <returns>The index of first occurrence</returns>
  57                 protected override int indexOf(T item)
  58                 {
  59                         KeyValuePair<T,int> p = new KeyValuePair<T,int>(item);
  60
  61                         if (!index.Find(ref p) || p.value < offset || p.value >= offset + size)
  62                                 return -1;
  63
  64                         return p.value - offset;
  65                 }
  66
  67
  68                 /// <summary>
  69                 /// Internal version of LastIndexOf without modification checks.
  70                 /// </summary>
  71                 /// <param name="item">Item to look for</param>
  72                 /// <returns>The index of last occurrence</returns>
  73                 protected override int lastIndexOf(T item) { return indexOf(item); }
  74
  75
  76                 /// <summary>
  77                 /// Internal version of Insert with no modification checks.
  78                 /// <exception cref="ArgumentException"/> if item already in list.
  79                 /// </summary>
  80                 /// <param name="i">Index to insert at</param>
  81                 /// <param name="item">Item to insert</param>
  82                 protected override void insert(int i, T item)
  83                 {
  84                         KeyValuePair<T,int> p = new KeyValuePair<T,int>(item, offset + i);
  85
  86                         if (index.FindOrAdd(ref p))
  87                                 throw new ArgumentException("Item already in indexed list");
  88
  89                         base.insert(i, item);
  90                         reindex(i + 1);
  91                 }
  92
  93
  94                 /// <summary>
  95                 /// Internal version of RemoveAt with no modification checks.
  96                 /// </summary>
  97                 /// <param name="i">Index to remove at</param>
  98                 /// <returns>The removed item</returns>
  99                 protected override T removeAt(int i)
 100                 {
 101                         T val = base.removeAt(i);
 102
 103                         index.Remove(new KeyValuePair<T,int>(val));
 104                         reindex(offset + i);
 105                         return val;
 106                 }
 107
 108
 109
 110                 #endregion
 111
 112                 #region Constructors
 113                 /// <summary>
 114                 /// Create a hashed array list with the natural hasher
 115                 /// </summary>
 116                 public HashedArrayList() : this(8) { }
 117
 118
 119                 /// <summary>
 120                 /// Create a hashed array list with the natural hasher and specified capacity
 121                 /// </summary>
 122                 /// <param name="cap">The initial capacity</param>
 123                 public HashedArrayList(int cap) : this(cap,HasherBuilder.ByPrototype<T>.Examine()) { }
 124
 125
 126                 /// <summary>
 127                 /// Create a hashed array list with an external hasher
 128                 /// </summary>
 129                 /// <param name="hasher">The external hasher</param>
 130                 public HashedArrayList(IHasher<T> hasher) : this(8,hasher) { }
 131
 132
 133                 /// <summary>
 134                 /// Create a hashed array list with an external hasher and specified capacity
 135                 /// </summary>
 136                 /// <param name="capacity">The initial capacity</param>
 137                 /// <param name="hasher">The external hasher</param>
 138                 public HashedArrayList(int capacity, IHasher<T> hasher) : base(capacity, hasher)
 139                 {
 140                         index = new HashSet<KeyValuePair<T,int>>(new KeyValuePairHasher<T,int>(hasher));
 141                 }
 142
 143                 #endregion
 144
 145                 #region IList<T> Members
 146
 147                 /// <summary>
 148                 /// Insert into this list all items from an enumerable collection starting
 149                 /// at a particular index.
 150                 /// <exception cref="IndexOutOfRangeException"/> if i is negative or
 151                 /// &gt; the size of the collection.
 152                 /// <exception cref="InvalidOperationException"/> if one of the items to insert is
 153                 /// already in the list.
 154                 /// </summary>
 155                 /// <param name="i">Index to start inserting at</param>
 156                 /// <param name="items">Items to insert</param>
 157                 [Tested]
 158                 public override void InsertAll(int i, MSG.IEnumerable<T> items)
 159                 {
 160                         updatecheck();
 161                         if (i < 0 || i > size)
 162                                 throw new IndexOutOfRangeException();
 163
 164                         i += offset;
 165
 166                         int j = i, toadd;
 167                         KeyValuePair<T,int> p = new KeyValuePair<T,int>();
 168
 169                         foreach (T item in items)
 170                         {
 171                                 p.key = item;
 172                                 p.value = j;
 173                                 if (!index.FindOrAdd(ref p))    j++;
 174                         }
 175
 176                         toadd = j - i;
 177                         if (toadd + underlyingsize > array.Length)
 178                                 expand(toadd + underlyingsize, underlyingsize);
 179
 180                         if (underlyingsize > i)
 181                                 Array.Copy(array, i, array, j, underlyingsize - i);
 182
 183                         foreach (T item in items)
 184                         {
 185                                 p.key = item;
 186                                 index.Find(ref p);
 187                                 if (i <= p.value && p.value < i + toadd)
 188                                         array[p.value] = item;
 189                         }
 190
 191                         addtosize(toadd);
 192                         reindex(j);
 193                 }
 194
 195         internal override void InsertAll<U>(int i, MSG.IEnumerable<U> items) //where U:T
 196         {
 197             updatecheck();
 198             if (i < 0 || i > size)
 199                 throw new IndexOutOfRangeException();
 200
 201             i += offset;
 202
 203             int j = i, toadd;
 204             KeyValuePair<T, int> p = new KeyValuePair<T, int>();
 205
 206             foreach (T item in items)
 207             {
 208                 p.key = item;
 209                 p.value = j;
 210                 if (!index.FindOrAdd(ref p)) j++;
 211             }
 212
 213             toadd = j - i;
 214             if (toadd + underlyingsize > array.Length)
 215                 expand(toadd + underlyingsize, underlyingsize);
 216
 217             if (underlyingsize > i)
 218                 Array.Copy(array, i, array, j, underlyingsize - i);
 219
 220             foreach (T item in items)
 221             {
 222                 p.key = item;
 223                 index.Find(ref p);
 224                 if (i <= p.value && p.value < i + toadd)
 225                     array[p.value] = item;
 226             }
 227
 228             addtosize(toadd);
 229             reindex(j);
 230         }
 231
 232         /// <summary>
 233                 /// Insert an item right before the first occurrence of some target item.
 234                 /// <exception cref="ArgumentException"/> if target     is not found.
 235                 /// <exception cref="InvalidOperationException"/> if the item to insert is
 236                 /// already in the list.
 237                 /// </summary>
 238                 /// <param name="item">The item to insert.</param>
 239                 /// <param name="target">The target before which to insert.</param>
 240                 [Tested]
 241                 public override void InsertBefore(T item, T target)
 242                 {
 243                         updatecheck();
 244
 245                         int ind = indexOf(target);
 246
 247                         if (ind < 0)
 248                                 throw new ArgumentException("Target item not found");
 249
 250                         insert(ind, item);
 251                 }
 252
 253
 254                 /// <summary>
 255                 /// Insert an item right after the last(???) occurrence of some target item.
 256                 /// <exception cref="ArgumentException"/> if target     is not found.
 257                 /// <exception cref="InvalidOperationException"/> if the item to insert is
 258                 /// already in the list.
 259                 /// </summary>
 260                 /// <param name="item">The item to insert.</param>
 261                 /// <param name="target">The target after which to insert.</param>
 262                 [Tested]
 263                 public override void InsertAfter(T item, T target)
 264                 {
 265                         updatecheck();
 266
 267                         int ind = indexOf(target);
 268
 269                         if (ind < 0)
 270                                 throw new ArgumentException("Target item not found");
 271
 272                         insert(ind + 1, item);
 273                 }
 274
 275
 276                 /// <summary>
 277                 /// Create a list view on this list.
 278                 /// <exception cref="ArgumentOutOfRangeException"/> if the view would not fit into
 279                 /// this list.
 280                 /// </summary>
 281                 /// <param name="start">The index in this list of the start of the view.</param>
 282                 /// <param name="count">The size of the view.</param>
 283                 /// <returns>The new list view.</returns>
 284                 [Tested]
 285                 public override IList<T> View(int start, int count)
 286                 {
 287                         HashedArrayList<T> retval = (HashedArrayList<T>)MemberwiseClone();
 288
 289                         retval.underlying = underlying != null ? underlying : this;
 290                         retval.offset = start;
 291                         retval.size = count;
 292                         return retval;
 293                 }
 294
 295
 296                 /// <summary>
 297                 /// Reverst part of the list so the items are in the opposite sequence order.
 298                 /// <exception cref="ArgumentException"/> if the count is negative.
 299                 /// <exception cref="ArgumentOutOfRangeException"/> if the part does not fit
 300                 /// into the list.
 301                 /// </summary>
 302                 /// <param name="start">The index of the start of the part to reverse.</param>
 303                 /// <param name="count">The size of the part to reverse.</param>
 304                 [Tested]
 305                 public override void Reverse(int start, int count)
 306                 {
 307                         base.Reverse(start, count);
 308                         reindex(offset + start, offset + start + count);
 309                 }
 310
 311
 312                 /// <summary>
 313                 /// Sort the items of the list according to a specific sorting order.
 314                 /// </summary>
 315                 /// <param name="c">The comparer defining the sorting order.</param>
 316                 [Tested]
 317                 public override void Sort(IComparer<T> c)
 318                 {
 319                         base.Sort(c);
 320                         reindex(offset, offset + size);
 321                 }
 322
 323                 /// <summary>
 324                 /// Shuffle the items of this list according to a specific random source.
 325                 /// </summary>
 326                 /// <param name="rnd">The random source.</param>
 327                 public override void Shuffle(Random rnd)
 328                 {
 329                         base.Shuffle(rnd);
 330                         reindex(offset, offset + size);
 331                 }
 332
 333                 #endregion
 334
 335                 #region IIndexed<T> Members
 336
 337
 338                 /// <summary>
 339                 /// Remove all items in an index interval.
 340                 /// <exception cref="IndexOutOfRangeException"/>???.
 341                 /// </summary>
 342                 /// <param name="start">The index of the first item to remove.</param>
 343                 /// <param name="count">The number of items to remove.</param>
 344                 [Tested]
 345                 public override void RemoveInterval(int start, int count)
 346                 {
 347                         updatecheck();
 348
 349                         KeyValuePair<T,int> p = new KeyValuePair<T,int>();
 350
 351                         for (int i = offset + start, end = offset + start + count; i < end; i++)
 352                         {
 353                                 p.key = array[i];
 354                                 index.Remove(p);
 355                         }
 356
 357                         base.RemoveInterval(start, count);
 358                         reindex(offset + start);
 359                 }
 360
 361                 #endregion
 362
 363                 #region ISequenced<T> Members
 364
 365                 int ISequenced<T>.GetHashCode()
 366                 { modifycheck(); return sequencedhashcode(); }
 367
 368
 369                 bool ISequenced<T>.Equals(ISequenced<T> that)
 370                 { modifycheck(); return sequencedequals(that); }
 371
 372
 373         #endregion
 374
 375                 #region IEditableCollection<T> Members
 376
 377                 /// <summary>
 378                 /// The value is symbolic indicating the type of asymptotic complexity
 379                 /// in terms of the size of this collection (expected).
 380                 /// </summary>
 381                 /// <value>Speed.Constant</value>
 382                 [Tested]
 383                 public override Speed ContainsSpeed { [Tested]get { return Speed.Constant; } }
 384
 385
 386                 /// <summary>
 387                 /// Check if this collection contains (an item equivalent to according to the
 388                 /// itemhasher) a particular value.
 389                 /// </summary>
 390                 /// <param name="item">The value to check for.</param>
 391                 /// <returns>True if the items is in this collection.</returns>
 392                 [Tested]
 393                 public override bool Contains(T item)
 394                 { modifycheck(); return indexOf(item) >= 0; }
 395
 396
 397                 /// <summary>
 398                 /// Remove the first copy of a particular item from this collection.
 399                 /// </summary>
 400                 /// <param name="item">The value to remove.</param>
 401                 /// <returns>True if the item was found (and removed).</returns>
 402                 [Tested]
 403                 public override bool Remove(T item)
 404                 {
 405                         updatecheck();
 406
 407                         int ind = indexOf(item);
 408
 409                         if (ind < 0)
 410                                 return false;
 411
 412                         removeAt(ind);
 413                         return true;
 414                 }
 415
 416
 417                 /// <summary>
 418                 /// Remove all items in another collection from this one, taking multiplicities into account.
 419                 /// Matching items will be removed from the front. Current implementation is not optimal.
 420                 /// </summary>
 421                 /// <param name="items">The items to remove.</param>
 422                 [Tested]
 423                 public override void RemoveAll(MSG.IEnumerable<T> items)
 424                 {
 425                         updatecheck();
 426
 427                         KeyValuePair<T,int> p = new KeyValuePair<T,int>();
 428
 429                         foreach (T item in items)
 430                         {
 431                                 p.key = item;
 432                                 if (index.Find(ref p) && offset <= p.value && p.value < offset + size)
 433                                         index.Remove(p);
 434                         }
 435
 436                         int removed = underlyingsize - index.Count, j = offset;
 437
 438                         for (int i = offset; i < underlyingsize; i++)
 439                         {
 440                                 p.key = array[i];
 441                                 p.value = j;
 442                                 if (index.Update(p)) { array[j++] = p.key; }
 443                         }
 444
 445                         addtosize(-removed);
 446                         Array.Clear(array, underlyingsize, removed);
 447                 }
 448
 449
 450                 /// <summary>
 451                 /// Remove all items from this collection, resetting internal array size.
 452                 /// </summary>
 453                 [Tested]
 454                 public override void Clear()
 455                 {
 456                         updatecheck();
 457                         if (underlying == null)
 458                         {
 459                                 index.Clear();
 460                                 base.Clear();
 461                         }
 462                         else
 463                         {
 464                                 for (int i = offset, end = offset + size; i < end; i++)
 465                                         index.Remove(new KeyValuePair<T,int>(array[i]));
 466
 467                                 base.Clear();
 468                                 reindex(offset);
 469                         }
 470                 }
 471
 472
 473                 /// <summary>
 474                 /// Remove all items not in some other collection from this one.
 475                 /// </summary>
 476                 /// <param name="items">The items to retain.</param>
 477                 [Tested]
 478                 public override void RetainAll(MSG.IEnumerable<T> items)
 479                 {
 480                         updatecheck();
 481
 482                         HashSet<T> toretain = new HashSet<T>(itemhasher);
 483                         KeyValuePair<T,int> p = new KeyValuePair<T,int>();
 484
 485                         foreach (T item in items)
 486                         {
 487                                 p.key = item;
 488                                 if (index.Find(ref p) && offset <= p.value && p.value < offset + size)
 489                                         toretain.Add(item);
 490                         }
 491
 492                         int removed = size - toretain.Count, j = offset;
 493
 494                         for (int i = offset; i < offset + size; i++)
 495                         {
 496                                 p.key = array[i];
 497                                 p.value = j;
 498                                 if (toretain.Contains(p.key))
 499                                 {
 500                                         index.Update(p);
 501                                         array[j++] = p.key;
 502                                 }
 503                                 else
 504                                 {
 505                                         index.Remove(p);
 506                                 }
 507                         }
 508
 509                         Array.Copy(array, offset + size, array, j, underlyingsize - offset - size);
 510                         addtosize(-removed);
 511                         reindex(j);
 512                         Array.Clear(array, underlyingsize, removed);
 513                 }
 514
 515
 516                 /// <summary>
 517                 /// Check if this collection contains all the values in another collection.
 518                 /// </summary>
 519                 /// <param name="items">The </param>
 520                 /// <returns>True if all values in <code>items</code>is in this collection.</returns>
 521                 [Tested]
 522                 public override bool ContainsAll(MSG.IEnumerable<T> items)
 523                 {
 524                         modifycheck();
 525                         foreach (T item in items)
 526                                 if (indexOf(item) < 0)
 527                                         return false;
 528
 529                         return true;
 530                 }
 531
 532
 533                 /// <summary>
 534                 /// Count the number of items of the collection equal to a particular value.
 535                 /// Returns 0 if and only if the value is not in the collection.
 536                 /// </summary>
 537                 /// <param name="item">The value to count.</param>
 538                 /// <returns>The number of copies found (0 or 1).</returns>
 539                 [Tested]
 540                 public override int ContainsCount(T item)
 541                 { modifycheck(); return indexOf(item) >= 0 ? 1 : 0; }
 542
 543
 544                 /// <summary>
 545                 /// Remove all items equal to a given one.
 546                 /// </summary>
 547                 /// <param name="item">The value to remove.</param>
 548                 [Tested]
 549                 public override void RemoveAllCopies(T item) { Remove(item); }
 550
 551
 552                 /// <summary>
 553                 /// Check the integrity of the internal data structures of this array list.
 554                 /// </summary>
 555                 /// <returns>True if check does not fail.</returns>
 556                 [Tested]
 557                 public override bool Check()
 558                 {
 559                         if (!base.Check())
 560                                 return false;
 561
 562                         bool retval = true;
 563
 564                         if (underlyingsize != index.Count)
 565                         {
 566                                 Console.WriteLine("size ({0})!= index.Count ({1})", size, index.Count);
 567                                 retval = false;
 568                         }
 569
 570                         for (int i = 0; i < underlyingsize; i++)
 571                         {
 572                                 KeyValuePair<T,int> p = new KeyValuePair<T,int>(array[i]);
 573
 574                                 if (!index.Find(ref p))
 575                                 {
 576                                         Console.WriteLine("Item {1} at {0} not in hashindex", i, array[i]);
 577                                         retval = false;
 578                                 }
 579
 580                                 if (p.value != i)
 581                                 {
 582                                         Console.WriteLine("Item {1} at {0} has hashindex {2}", i, array[i], p.value);
 583                                         retval = false;
 584                                 }
 585                         }
 586
 587                         return retval;
 588                 }
 589
 590
 591                 int ICollection<T>.GetHashCode() { return unsequencedhashcode(); }
 592
 593
 594                 bool ICollection<T>.Equals(ICollection<T> that)
 595                 { return unsequencedequals(that); }
 596
 597                 #endregion
 598
 599                 #region ISink<T> Members
 600
 601                 /// <summary>
 602                 ///
 603                 /// </summary>
 604                 /// <value>False, indicating hashed array list has set semantics.</value>
 605                 [Tested]
 606                 public override bool AllowsDuplicates { [Tested]get { return false; } }
 607
 608
 609                 /// <summary>
 610                 /// Add an item to end of this list if not already in list.
 611                 /// </summary>
 612                 /// <param name="item">The item to add.</param>
 613                 /// <returns>True if item was added</returns>
 614                 [Tested]
 615                 public override bool Add(T item)
 616                 {
 617                         updatecheck();
 618
 619                         KeyValuePair<T,int> p = new KeyValuePair<T,int>(item, size);
 620
 621                         if (index.FindOrAdd(ref p))
 622                                 return false;
 623
 624                         base.insert(size, item);
 625                         reindex(size);
 626                         return true;
 627                 }
 628
 629                 #endregion
 630
 631                 #region IDirectedEnumerable<T> Members
 632
 633                 IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards() { return Backwards(); }
 634
 635                 #endregion
 636         }
 637 }
 638 #endif