mcs/class/System.Data/System.Data.Common/Index.cs

   1 //\r
   2 // System.Data.Common.Key.cs\r
   3 //\r
   4 // Author:\r
   5 //   Boris Kirzner  <borisk@mainsoft.com>\r
   6 //   Konstantin Triger (kostat@mainsoft.com)\r
   7 //\r
   8 \r
   9 /*\r
  10   * Copyright (c) 2002-2004 Mainsoft Corporation.\r
  11   *\r
  12   * Permission is hereby granted, free of charge, to any person obtaining a\r
  13   * copy of this software and associated documentation files (the "Software"),\r
  14   * to deal in the Software without restriction, including without limitation\r
  15   * the rights to use, copy, modify, merge, publish, distribute, sublicense,\r
  16   * and/or sell copies of the Software, and to permit persons to whom the\r
  17   * Software is furnished to do so, subject to the following conditions:\r
  18   *\r
  19   * The above copyright notice and this permission notice shall be included in\r
  20   * all copies or substantial portions of the Software.\r
  21   *\r
  22   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  23   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  24   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  25   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  26   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING\r
  27   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER\r
  28   * DEALINGS IN THE SOFTWARE.\r
  29   */\r
  30 \r
  31 using System;\r
  32 using System.Collections;\r
  33 \r
  34 using System.Text;\r
  35 \r
  36 namespace System.Data.Common\r
  37 {\r
  38         enum IndexDuplicatesState { Unknown, True, False }; \r
  39         /// <summary>\r
  40         /// Summary description for Index.\r
  41         /// </summary>\r
  42         internal class Index\r
  43         {\r
  44                 #region Fields\r
  45 \r
  46                 int[] _array;\r
  47                 int _size;\r
  48                 Key _key;\r
  49                 int _refCount = 0;\r
  50                 IndexDuplicatesState _hasDuplicates;\r
  51 \r
  52                 #endregion // Fields\r
  53 \r
  54                 #region Constructors\r
  55 \r
  56                 internal Index(Key key)\r
  57                 {\r
  58                         _key = key;\r
  59                         Reset();\r
  60                 }\r
  61 \r
  62                 #endregion // Constructors\r
  63 \r
  64                 #region Properties\r
  65 \r
  66                 internal Key Key \r
  67                 {\r
  68                         get {\r
  69                                 return _key;\r
  70                         }\r
  71                 }\r
  72 \r
  73                 internal int Size\r
  74                 {\r
  75                         get {\r
  76                                 EnsureArray();\r
  77                                 return _size;\r
  78                         }\r
  79                 }\r
  80 \r
  81                 internal int RefCount\r
  82                 {\r
  83                         get {\r
  84                                 return _refCount;\r
  85                         }\r
  86                 }\r
  87 \r
  88                 internal int IndexToRecord(int index){\r
  89                         return index < 0 ? index : Array[index];\r
  90                 }\r
  91 \r
  92                 private int[] Array\r
  93                 {\r
  94                         get {\r
  95                                 EnsureArray();\r
  96                                 return _array;\r
  97                         }\r
  98                 }\r
  99 \r
 100                 internal bool HasDuplicates\r
 101                 {\r
 102                         get {\r
 103                                 if (_array == null || _hasDuplicates == IndexDuplicatesState.Unknown) {\r
 104                                         EnsureArray();\r
 105                                         if (_hasDuplicates == IndexDuplicatesState.Unknown) {\r
 106                                                 // check for duplicates\r
 107                                                 _hasDuplicates = IndexDuplicatesState.False;\r
 108                                                 for(int i = 0; i < Size - 1; i++) {\r
 109                                                         if (Key.CompareRecords(Array[i],Array[i+1]) == 0) {\r
 110                                                                 _hasDuplicates = IndexDuplicatesState.True;\r
 111                                                                 break;\r
 112                                                         }\r
 113                                                 }\r
 114                                         }\r
 115                                 }\r
 116                                 return (_hasDuplicates == IndexDuplicatesState.True);\r
 117                         }\r
 118                 }\r
 119 \r
 120                 #endregion // Properties\r
 121 \r
 122                 #region Methods\r
 123 \r
 124                 internal int[] Duplicates {\r
 125                         get {\r
 126                                 if (!HasDuplicates)\r
 127                                         return null;\r
 128 \r
 129                                 ArrayList dups = new ArrayList();\r
 130 \r
 131                                 bool inRange = false;\r
 132                                 for(int i = 0; i < Size - 1; i++) {\r
 133                                         if (Key.CompareRecords(Array[i],Array[i+1]) == 0){\r
 134                                                 if (!inRange) {\r
 135                                                         dups.Add(Array[i]);\r
 136                                                         inRange = true;\r
 137                                                 }\r
 138 \r
 139                                                 dups.Add(Array[i+1]);\r
 140                                         }\r
 141                                         else\r
 142                                                 inRange = false;\r
 143                                 }\r
 144 \r
 145                                 return (int[])dups.ToArray(typeof(int));\r
 146                         }\r
 147                 }\r
 148 \r
 149                 private void EnsureArray()\r
 150                 {\r
 151                         if (_array == null) {\r
 152                                 RebuildIndex();\r
 153                         }\r
 154                 }\r
 155 \r
 156                 internal int[] GetAll()\r
 157                 {\r
 158                         return Array;\r
 159                 }\r
 160 \r
 161                 internal DataRow[] GetAllRows ()\r
 162                 {\r
 163                         DataRow[] list = new DataRow [Size];\r
 164                         for (int i=0; i < Size; ++i)\r
 165                                 list [i] = Key.Table.RecordCache [Array [i]];\r
 166                         return list;\r
 167                 }\r
 168 \r
 169                 internal DataRow[] GetDistinctRows () \r
 170                 {\r
 171                         ArrayList list = new ArrayList ();\r
 172                         list.Add (Key.Table.RecordCache [Array [0]]);\r
 173                         int currRecord = Array [0];\r
 174                         for (int i=1; i <  Size; ++i) {\r
 175                                 if (Key.CompareRecords (currRecord, Array [i]) == 0)\r
 176                                         continue;\r
 177                                 list.Add (Key.Table.RecordCache [Array [i]]);\r
 178                                 currRecord = Array [i];\r
 179                         }\r
 180                         return (DataRow[])list.ToArray (typeof (DataRow));\r
 181                 }\r
 182 \r
 183                 internal void Reset()\r
 184                 {\r
 185                         _array = null;\r
 186                         RebuildIndex();\r
 187                 }\r
 188 \r
 189                 private void RebuildIndex()\r
 190                 {\r
 191                         // consider better capacity approximation\r
 192                         _array = new int[Key.Table.RecordCache.CurrentCapacity];\r
 193                         _size = 0;\r
 194                         foreach(DataRow row in Key.Table.Rows) {\r
 195                                 int record = Key.GetRecord(row);\r
 196                                 if (record != -1) {\r
 197                                         _array[_size++] = record;\r
 198                                 }\r
 199                         }\r
 200                         _hasDuplicates = IndexDuplicatesState.False;\r
 201                         // Note : MergeSort may update hasDuplicates to True\r
 202                         Sort();\r
 203                 }\r
 204 \r
 205                 private void Sort()\r
 206                 {\r
 207                         //QuickSort(Array,0,Size-1);\r
 208                         MergeSort(Array,Size);\r
 209                 }\r
 210                 \r
 211                 /*\r
 212                  * Returns record number of the record equal to the key values supplied \r
 213                  * in the meaning of index key, or -1 if no equal record found.\r
 214                  */\r
 215                 internal int Find(object[] keys)\r
 216                 {\r
 217                         int index = FindIndex(keys);\r
 218                         return IndexToRecord(index);\r
 219                 }\r
 220 \r
 221                 /*\r
 222                  * Returns record index (location) of the record equal to the key values supplied \r
 223                  * in the meaning of index key, or -1 if no equal record found.\r
 224                  */\r
 225                 internal int FindIndex(object[] keys)\r
 226                 {\r
 227                         if (keys == null || keys.Length != Key.Columns.Length) {\r
 228                                 throw new ArgumentException("Expecting " + Key.Columns.Length + " value(s) for the key being indexed, " +\r
 229                                         "but received " + ((keys == null) ? 0 : keys.Length) + " value(s).");\r
 230                         }\r
 231 \r
 232                         int tmp = Key.Table.RecordCache.NewRecord();\r
 233                         try {\r
 234                                 // init key values for temporal record\r
 235                                 for(int i = 0; i < Key.Columns.Length; i++) {\r
 236                                         Key.Columns[i].DataContainer[tmp] = keys[i];\r
 237                                 }\r
 238                                 return FindIndex(tmp);\r
 239                         }\r
 240 //                      catch(FormatException) {\r
 241 //                              return -1;\r
 242 //                      }\r
 243 //                      catch(InvalidCastException) {\r
 244 //                              return -1;\r
 245 //                      }\r
 246                         finally {\r
 247                                 Key.Table.RecordCache.DisposeRecord(tmp);\r
 248                         }\r
 249                 }\r
 250 \r
 251                 /*\r
 252                  * Returns record number of the record equal to the record supplied \r
 253                  * in the meaning of index key, or -1 if no equal record found.\r
 254                  */\r
 255                 internal int Find(int record)\r
 256                 {\r
 257                         int index = FindIndex(record);\r
 258                         return IndexToRecord(index);\r
 259                 }\r
 260 \r
 261                 /*\r
 262                  * Returns array of record numbers of the records equal equal to the key values supplied \r
 263                  * in the meaning of index key, or -1 if no equal record found.\r
 264                  */\r
 265                 internal int[] FindAll(object[] keys)\r
 266                 {\r
 267                         int[] indexes = FindAllIndexes(keys);\r
 268                         IndexesToRecords(indexes);\r
 269                         return indexes;\r
 270                 }\r
 271 \r
 272                 /*\r
 273                  * Returns array of indexes of the records inside the index equal equal to the key values supplied \r
 274                  * in the meaning of index key, or -1 if no equal record found.\r
 275                  */\r
 276                 internal int[] FindAllIndexes(object[] keys)\r
 277                 {\r
 278                         if (keys == null || keys.Length != Key.Columns.Length) {\r
 279                                 throw new ArgumentException("Expecting " + Key.Columns.Length + " value(s) for the key being indexed," +\r
 280                                         "but received " + ((keys == null) ? 0 : keys.Length) + " value(s).");\r
 281                         }\r
 282 \r
 283                         int tmp = Key.Table.RecordCache.NewRecord();\r
 284                         try {\r
 285                                 // init key values for temporal record\r
 286                                 for(int i = 0; i < Key.Columns.Length; i++) {\r
 287                                         Key.Columns[i].DataContainer[tmp] = keys[i];\r
 288                                 }\r
 289                                 return FindAllIndexes(tmp);\r
 290                         }\r
 291                         catch(FormatException) {\r
 292                                 return new int[0];\r
 293                         }\r
 294                         catch(InvalidCastException) {\r
 295                                 return new int[0];\r
 296                         }\r
 297                         finally {\r
 298                                 Key.Table.RecordCache.DisposeRecord(tmp);\r
 299                         }\r
 300                 }\r
 301 \r
 302                 /*\r
 303                  * Returns array of record numbers of the records equal to the record supplied \r
 304                  * in the meaning of index key, or empty list if no equal records found.\r
 305                  */\r
 306                 internal int[] FindAll(int record)\r
 307                 {\r
 308                         int[] indexes = FindAllIndexes(record);\r
 309             IndexesToRecords(indexes);\r
 310                         return indexes;\r
 311                 }\r
 312 \r
 313                 /*\r
 314                  * Returns array of indexes of the records inside the index that equal to the record supplied \r
 315                  * in the meaning of index key, or empty list if no equal records found.\r
 316                  */\r
 317                 internal int[] FindAllIndexes(int record)\r
 318                 {\r
 319                         int index = FindIndex(record);\r
 320 \r
 321                         if (index == -1) {\r
 322                                 return new int[0];\r
 323                         }\r
 324 \r
 325                         int startIndex = index++;\r
 326                         int endIndex = index;\r
 327                         \r
 328                         for(;startIndex >= 0 && Key.CompareRecords(Array[startIndex],record) == 0;startIndex--);\r
 329                         for(;endIndex < Size && Key.CompareRecords(Array[endIndex],record) == 0;endIndex++);\r
 330                         \r
 331                         int length = endIndex - startIndex - 1;\r
 332                         int[] indexes = new int[length];\r
 333                         \r
 334                         for(int i = 0; i < length; i++) {\r
 335                                 indexes[i] = ++startIndex;\r
 336                         }\r
 337                         \r
 338                         return indexes;\r
 339                 }\r
 340 \r
 341                 /*\r
 342                  * Returns index inside the array where record number of the record equal to the record supplied \r
 343                  * in the meaning of index key is sored, or -1 if no equal record found.\r
 344                  */\r
 345                 private int FindIndex(int record)\r
 346                 {\r
 347                         if (Size == 0) {\r
 348                                 return -1;\r
 349                         }\r
 350                         return BinarySearch(Array,0,Size - 1,record);\r
 351                 }\r
 352 \r
 353                 /*\r
 354                  * Finds exact location of the record specified\r
 355                  */ \r
 356                 private int FindIndexExact(int record)\r
 357                 {\r
 358                         for (int i = 0, size = Size; i < size; i++)\r
 359                                 if (Array[i] == record)\r
 360                                         return i;\r
 361 \r
 362                         return -1;\r
 363                 }\r
 364 \r
 365                 /*\r
 366                  * Returns array of records from the indexes (locations) inside the index\r
 367                  */\r
 368                 private void IndexesToRecords(int[] indexes)\r
 369                 {\r
 370                         for(int i = 0; i < indexes.Length; i++) {\r
 371                                 indexes[i] = Array[indexes[i]];\r
 372                         }\r
 373                 }\r
 374 \r
 375                 internal void Delete(DataRow row)\r
 376                 {\r
 377                         int oldRecord = Key.GetRecord(row);\r
 378 \r
 379                         Delete(oldRecord);\r
 380                 }\r
 381 \r
 382                 internal void Delete(int oldRecord)\r
 383                 {\r
 384                         if (oldRecord == -1)\r
 385                                 return;\r
 386 \r
 387                         int index = FindIndexExact(oldRecord);\r
 388                         if (index != -1) {\r
 389                                 if ((_hasDuplicates == IndexDuplicatesState.True)) {\r
 390                                         int c1 = 1;\r
 391                                         int c2 = 1;\r
 392 \r
 393                                         if (index > 0) {\r
 394                                                 c1 = Key.CompareRecords(Array[index - 1],oldRecord);\r
 395                                         }\r
 396                                         if (index < Size - 1) {\r
 397                                                 c2 = Key.CompareRecords(Array[index + 1],oldRecord);\r
 398                                         }\r
 399 \r
 400                                         if (c1 == 0 ^ c2 == 0) {\r
 401                                                 _hasDuplicates = IndexDuplicatesState.Unknown;\r
 402                                         }\r
 403                                 }\r
 404                                 Remove(index);\r
 405                         }\r
 406                 }\r
 407 \r
 408                 private void Remove(int index)\r
 409                 {\r
 410                         if (Size > 1) {\r
 411                                 System.Array.Copy(Array,index+1,Array,index,Size - index - 1);\r
 412                         }\r
 413                         _size--;\r
 414                 }\r
 415 \r
 416 \r
 417                 internal void Update(DataRow row,int oldRecord, DataRowVersion oldVersion, DataRowState oldState)\r
 418                 {                       \r
 419                         bool contains = Key.ContainsVersion (oldState, oldVersion);\r
 420                         int newRecord = Key.GetRecord(row);     \r
 421                         // the record did not appeared in the index before update\r
 422                         if (oldRecord == -1 || Size == 0 || !contains) {\r
 423                                 if (newRecord >= 0) {\r
 424                                         if (FindIndexExact(newRecord) < 0)\r
 425                                                 Add(row,newRecord);\r
 426                                 }\r
 427                                 return;\r
 428                         }\r
 429                         \r
 430                         // the record will not appeare in the index after update\r
 431                         if (newRecord < 0 || !Key.CanContain (newRecord)) {\r
 432                                 Delete (oldRecord);\r
 433                                 return;\r
 434                         }\r
 435 \r
 436                         int oldIdx = FindIndexExact(oldRecord);\r
 437 \r
 438                         if( oldIdx == -1 ) {\r
 439                                 Add(row,newRecord);\r
 440                                 return;\r
 441                         }\r
 442                                 \r
 443                         int newIdx = -1;\r
 444                         int compare = Key.CompareRecords(Array[oldIdx],newRecord);\r
 445                         int start,end;\r
 446 \r
 447                         int c1 = 1;\r
 448                         int c2 = 1;\r
 449 \r
 450                         if (compare == 0) {\r
 451                                 if (Array[oldIdx] == newRecord) {\r
 452                                         // we deal with the same record that didn't change\r
 453                                         // in the context of current index.\r
 454                                         // so , do nothing.\r
 455                                         return;\r
 456                                 }\r
 457                         }\r
 458                         else {\r
 459                                 if ((_hasDuplicates == IndexDuplicatesState.True)) {\r
 460                                         if (oldIdx > 0) {\r
 461                                                 c1 = Key.CompareRecords(Array[oldIdx - 1],newRecord);\r
 462                                         }\r
 463                                         if (oldIdx < Size - 1) {\r
 464                                                 c2 = Key.CompareRecords(Array[oldIdx + 1],newRecord);\r
 465                                         }\r
 466 \r
 467                                         if ((c1 == 0 ^ c2 == 0) && compare != 0) {\r
 468                                                 _hasDuplicates = IndexDuplicatesState.Unknown;\r
 469                                         }\r
 470                                 }\r
 471                         }\r
 472                         \r
 473                         if ((oldIdx == 0 && compare > 0) || (oldIdx == (Size - 1) && compare < 0) || (compare == 0)) {\r
 474                                 // no need to switch cells\r
 475                                 newIdx = oldIdx;\r
 476                         }\r
 477                         else {\r
 478                                 if (compare < 0) {\r
 479                                         // search after the old place\r
 480                                         start = oldIdx + 1;\r
 481                                         end = Size - 1;\r
 482                                 }\r
 483                                 else {\r
 484                                         // search before the old palce\r
 485                                         start = 0;\r
 486                                         end = oldIdx - 1;\r
 487                                 }\r
 488 \r
 489                                 newIdx = LazyBinarySearch(Array,start,end,newRecord);                                   \r
 490 \r
 491                                 if (oldIdx < newIdx) {\r
 492                                         System.Array.Copy(Array,oldIdx + 1,Array,oldIdx,newIdx - oldIdx);\r
 493                                         if (Key.CompareRecords (Array [newIdx], newRecord) > 0)\r
 494                                                 --newIdx;\r
 495                                 }\r
 496                                 else if (oldIdx > newIdx){\r
 497                                         System.Array.Copy(Array,newIdx,Array,newIdx + 1,oldIdx - newIdx);\r
 498                                         if (Key.CompareRecords (Array [newIdx], newRecord) < 0)\r
 499                                                 ++newIdx;\r
 500                                 }\r
 501                         }                       \r
 502                         Array[newIdx] = newRecord;\r
 503 \r
 504                         if (compare != 0) {\r
 505                                 if (!(_hasDuplicates == IndexDuplicatesState.True)) {\r
 506                                         if (newIdx > 0) {\r
 507                                                 c1 = Key.CompareRecords(Array[newIdx - 1],newRecord);\r
 508                                         }\r
 509                                         if (newIdx < Size - 1) {\r
 510                                                 c2 = Key.CompareRecords(Array[newIdx + 1],newRecord);\r
 511                                         }\r
 512 \r
 513                                         if (c1 == 0 || c2 == 0) {\r
 514                                                 _hasDuplicates = IndexDuplicatesState.True;\r
 515                                         }\r
 516                                 }\r
 517                         }\r
 518                 }\r
 519 \r
 520                 internal void Add(DataRow row) {\r
 521                         Add(row, Key.GetRecord(row));\r
 522                 }\r
 523 \r
 524                 private void Add(DataRow row,int newRecord)\r
 525                 {\r
 526                         int newIdx;\r
 527 \r
 528                         if (newRecord < 0 || !Key.CanContain (newRecord))\r
 529                                 return;\r
 530 \r
 531                         if (Size == 0) {\r
 532                                 newIdx = 0;\r
 533                         }\r
 534                         else {\r
 535                                 newIdx = LazyBinarySearch(Array,0,Size - 1,newRecord);\r
 536                                 // if newl value is greater - insert afer old value\r
 537                                 // else - insert before old value\r
 538                                 if (Key.CompareRecords(Array[newIdx],newRecord) < 0) {\r
 539                                         newIdx++;\r
 540                                 }\r
 541                         }\r
 542                                         \r
 543                         Insert(newIdx,newRecord);\r
 544 \r
 545                         int c1 = 1;\r
 546                         int c2 = 1;\r
 547                         if (!(_hasDuplicates == IndexDuplicatesState.True)) {\r
 548                                 if (newIdx > 0) {\r
 549                                         c1 = Key.CompareRecords(Array[newIdx - 1],newRecord);\r
 550                                 }\r
 551                                 if (newIdx < Size - 1) {\r
 552                                         c2 = Key.CompareRecords(Array[newIdx + 1],newRecord);\r
 553                                 }\r
 554 \r
 555                                 if (c1 == 0 || c2 == 0) {\r
 556                                         _hasDuplicates = IndexDuplicatesState.True;\r
 557                                 }\r
 558                         }\r
 559                 }\r
 560 \r
 561                 private void Insert(int index,int r)\r
 562                 {\r
 563                         if (Array.Length == Size) {\r
 564                                 int[] tmp = (Size == 0) ? new int[16] : new int[Size << 1];\r
 565                                 System.Array.Copy(Array,0,tmp,0,index);\r
 566                                 tmp[index] = r;\r
 567                                 System.Array.Copy(Array,index,tmp,index + 1,Size - index);\r
 568                                 _array = tmp;\r
 569                         }\r
 570                         else {\r
 571                                 System.Array.Copy(Array,index,Array,index + 1,Size - index);\r
 572                                 Array[index] = r;\r
 573                         }\r
 574                         _size++;\r
 575                 }\r
 576 \r
 577                 private void MergeSort(int[] to, int length)\r
 578         {\r
 579             int[] from = new int[length];\r
 580             System.Array.Copy(to, 0, from, 0, from.Length);\r
 581 \r
 582             MergeSort(from, to, 0, from.Length);\r
 583         }\r
 584 \r
 585         private void MergeSort(int[] from, int[] to,int p, int r)\r
 586         {\r
 587             int q = (p + r) >> 1;\r
 588                 if (q == p) {\r
 589                 return;\r
 590             }        \r
 591 \r
 592             MergeSort(to, from, p, q);\r
 593             MergeSort(to, from, q, r);\r
 594 \r
 595             // merge\r
 596             for (int middle = q, current = p;;) {\r
 597                                 int res = Key.CompareRecords(from[p],from[q]);\r
 598                 if (res > 0) {\r
 599                     to[current++] = from[q++];\r
 600 \r
 601                     if (q == r) {\r
 602                         while( p < middle) {\r
 603                                 to[current++] = from[p++];\r
 604                                                 }\r
 605                         break;\r
 606                     }\r
 607                 }\r
 608                 else {\r
 609 \r
 610                                         if (res == 0) {\r
 611                                                 _hasDuplicates = IndexDuplicatesState.True;\r
 612                                         }\r
 613 \r
 614                     to[current++] = from[p++];\r
 615 \r
 616                     if (p == middle) {\r
 617                         while( q < r) {\r
 618                                 to[current++] = from[q++];\r
 619                                                 }\r
 620                         break;\r
 621                     }\r
 622                 }\r
 623             }\r
 624                 }\r
 625 \r
 626                 private void QuickSort(int[] a,int p,int r)\r
 627                 {\r
 628                         if (p < r) {\r
 629                                 int q = Partition(a,p,r);\r
 630                                 QuickSort(a,p,q);\r
 631                                 QuickSort(a,q+1,r);\r
 632                         }\r
 633                 }\r
 634 \r
 635                 private int Partition(int[] a,int p,int r)\r
 636                 {\r
 637                         int x = a[p];\r
 638                         int i = p - 1;\r
 639                         int j = r + 1;\r
 640 \r
 641                         while(true) {\r
 642                                 // decrement upper limit while values are greater then border value\r
 643                                 do {\r
 644                                         j--;\r
 645                                 }\r
 646                                 while(Key.CompareRecords(a[j],x) > 0);  //while(a[j] > x);\r
 647 \r
 648                                 do {\r
 649                                         i++;\r
 650                                 }\r
 651                                 while(Key.CompareRecords(a[i],x) < 0);  //while(a[i] < x);\r
 652                                 \r
 653                                 if (i<j) {\r
 654                                         int tmp = a[j];\r
 655                                         a[j] = a[i];\r
 656                                         a[i] = tmp;\r
 657                                 }\r
 658                                 else {\r
 659                                         return j;\r
 660                                 }\r
 661                         }\r
 662                 }\r
 663 \r
 664                 private int BinarySearch(int[] a, int p, int r,int b)\r
 665                 {\r
 666                         int i = LazyBinarySearch(a,p,r,b);\r
 667 \r
 668                         return (Key.CompareRecords(a[i],b) == 0) ? i : -1;\r
 669                 }\r
 670 \r
 671                 // Lazy binary search only returns the cell number the search finished in,\r
 672                 // but does not checks that the correct value was actually found\r
 673                 private int LazyBinarySearch(int[] a, int p, int r,int b)\r
 674                 {\r
 675                         if ( p == r ) {\r
 676                                 return p;\r
 677                         }\r
 678 \r
 679                         int q = (p+r) >> 1;\r
 680 \r
 681                         int compare = Key.CompareRecords(a[q],b);\r
 682                         if (compare < 0) { // if (a[q] < b) {\r
 683                                 return LazyBinarySearch(a,q+1,r,b);\r
 684                         }\r
 685                         else if (compare > 0) { // a[q] > b\r
 686                                 return LazyBinarySearch(a,p,q,b);\r
 687                         }       \r
 688                         else { // a[q] == b\r
 689                                 return q;\r
 690                         }\r
 691                 }\r
 692 \r
 693                 internal void AddRef()\r
 694                 {\r
 695                         _refCount++;\r
 696                 }\r
 697 \r
 698                 internal void RemoveRef()\r
 699                 {\r
 700                         _refCount--;\r
 701                 }\r
 702 \r
 703                 /*\r
 704                 // Prints indexes. For debugging.\r
 705                 internal void Print ()\r
 706                 {\r
 707                         for (int i=0; i < Size; i++) {\r
 708                                 Console.Write ("Index {0} record {1}: ", i, Array [i]);\r
 709                                 for (int j=0; j < Key.Table.Columns.Count; j++) {\r
 710                                         DataColumn col = Key.Table.Columns [j];\r
 711                                         if (Array [i] >= 0)\r
 712                                                 Console.Write ("{0,15} ", col [Array [i]]);\r
 713                                 }\r
 714                                 Console.WriteLine ();\r
 715                         }\r
 716                 }\r
 717                 */\r
 718                 \r
 719                 #endregion // Methods\r
 720         }\r
 721 }\r