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

   1 /*
   2 //
   3 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
   4 //
   5 // Permission is hereby granted, free of charge, to any person obtaining
   6 // a copy of this software and associated documentation files (the
   7 // "Software"), to deal in the Software without restriction, including
   8 // without limitation the rights to use, copy, modify, merge, publish,
   9 // distribute, sublicense, and/or sell copies of the Software, and to
  10 // permit persons to whom the Software is furnished to do so, subject to
  11 // the following conditions:
  12 //
  13 // The above copyright notice and this permission notice shall be
  14 // included in all copies or substantial portions of the Software.
  15 //
  16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  17 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  19 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  20 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  21 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  22 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23 //
  24 using System;
  25 using System.Collections;
  26
  27 namespace System.Data
  28 {
  29         /// <summary>
  30         /// Summary description for Index.
  31         /// </summary>
  32         internal class Index1
  33         {
  34
  35                 // fields
  36                 private DataTable _table;
  37                 private DataColumn[] _columns;
  38                 private bool _unique;
  39                 private Node _root;
  40                 private string _indexName;
  41
  42
  43
  44                 internal Index1 (string name, DataTable table, DataColumn[] columns,
  45                         bool unique)
  46                 {
  47
  48                         _indexName = name;
  49                         _table = table;
  50                         _columns = columns;
  51                         _unique = unique;
  52                 }
  53
  54                 internal void SetUnique (bool unique)
  55                 {
  56                         _unique = unique;
  57                 }
  58
  59                 internal Node Root
  60                 {
  61                         get
  62                         {
  63                                 return _root;
  64                         }
  65
  66                         set
  67                         {
  68                                 _root = value;
  69                         }
  70                 }
  71
  72                 internal string Name
  73                 {
  74                         get
  75                         {
  76                                 return _indexName;
  77                         }
  78
  79                         set
  80                         {
  81
  82                         }
  83                 }
  84
  85                 internal bool IsUnique
  86                 {
  87                         get
  88                         {
  89                                 return _unique;
  90                         }
  91                 }
  92
  93                 internal DataColumn[] Columns
  94                 {
  95                         get
  96                         {
  97                                 return _columns;    // todo: this gives back also primary key field!
  98                         }
  99                 }
 100
 101                 internal bool IsEquivalent (Index index)
 102                 {
 103
 104                         if (_unique == index._unique
 105                                 && _columns.Length == index._columns.Length) {
 106                                 for (int j = 0; j < _columns.Length; j++) {
 107                                         if (_columns[j] != index._columns[j]) {
 108                                                 return false;
 109                                         }
 110                                 }
 111
 112                                 return true;
 113                         }
 114
 115                         return false;
 116                 }
 117
 118                 internal void Insert (Node i, DataRowVersion version)
 119                 {
 120                         DataRow  data  = i.Row;
 121                         Node    n       = _root,
 122                                 x       = n;
 123                         bool way     = true;
 124                         int     compare = -1;
 125                         bool needBalance = true;
 126
 127                         while (true) {
 128                                 if (n == null) {
 129                                         if (x == null) {
 130                                                 _root = i;
 131
 132                                                 return;
 133                                         }
 134
 135                                         Set(x, way, i);
 136
 137                                         break;
 138                                 }
 139
 140                                 DataRow nData = n.Row;
 141
 142                                 if (data == nData)      {
 143                                         //Set(x, way, i);
 144                                         needBalance = false;
 145                                         break;
 146                                 }
 147
 148                                 compare = CompareRow(data, version, nData);
 149
 150                                 if (compare == 0) {
 151                                         throw new ConstraintException("Unique key violation");
 152                                 }
 153
 154                                 way = compare < 0;
 155                                 x   = n;
 156                                 n   = Child(x, way);
 157                         }
 158
 159                         if(needBalance) {
 160                                 Balance(x, way);
 161                         }
 162                 }
 163
 164                 private void Balance(Node x, bool way)
 165                 {
 166
 167                         while (true) {
 168
 169                                 int sign = way ? 1
 170                                         : -1;
 171
 172                                 switch (x.GetBalance() * sign) {
 173
 174                                         case 1 :
 175                                                 x.SetBalance(0);
 176
 177                                                 return;
 178
 179                                         case 0 :
 180                                                 x.SetBalance(-sign);
 181                                                 break;
 182
 183                                         case -1 :
 184                                                 Node l = Child(x, way);
 185
 186                                                 if (l.GetBalance() == -sign) {
 187                                                         Replace(x, l);
 188                                                         Set(x, way, Child(l, !way));
 189                                                         Set(l, !way, x);
 190                                                         x.SetBalance(0);
 191                                                         l.SetBalance(0);
 192                                                 }
 193                                                 else {
 194                                                         Node r = Child(l, !way);
 195
 196                                                         Replace(x, r);
 197                                                         Set(l, !way, Child(r, way));
 198                                                         Set(r, way, l);
 199                                                         Set(x, way, Child(r, !way));
 200                                                         Set(r, !way, x);
 201
 202                                                         int rb = r.GetBalance();
 203
 204                                                         x.SetBalance((rb == -sign) ? sign
 205                                                                 : 0);
 206                                                         l.SetBalance((rb == sign) ? -sign
 207                                                                 : 0);
 208                                                         r.SetBalance(0);
 209                                                 }
 210
 211                                                 return;
 212                                 }
 213
 214                                 if (x.Equals(_root)) {
 215                                         return;
 216                                 }
 217
 218                                 way = x.From();
 219                                 x   = x.Parent;
 220                         }
 221                 }
 222
 223                 internal void Delete (DataRow row)
 224                 {
 225                         Node x = Search(row,DataRowVersion.Current);
 226                         Delete (x);
 227                 }
 228
 229                 internal void Delete(Node x)
 230                 {
 231                         if (x == null) {
 232                                 return;
 233                         }
 234
 235                         Node n;
 236
 237                         if (x.Left == null) {
 238                                 n = x.Right;
 239                         }
 240                         else if (x.Right == null) {
 241                                 n = x.Left;
 242                         }
 243                         else {
 244                                 Node d = x;
 245
 246                                 x = x.Left;
 247
 248                                 // todo: this can be improved
 249                                 while (x.Right != null) {
 250                                         x = x.Right;
 251                                 }
 252
 253                                 // x will be replaced with n later
 254                                 n = x.Left;
 255
 256                                 // swap d and x
 257                                 int b = x.GetBalance();
 258
 259                                 x.SetBalance(d.GetBalance());
 260                                 d.SetBalance(b);
 261
 262                                 // set x.parent
 263                                 Node xp = x.Parent;
 264                                 Node dp = d.Parent;
 265
 266                                 if (d == _root) {
 267                                         _root = x;
 268                                 }
 269
 270                                 x.Parent = dp;
 271
 272                                 if (dp != null) {
 273                                         if (dp.Right.Equals(d)) {
 274                                                 dp.Right = x;
 275                                         }
 276                                         else {
 277                                                 dp.Left = x;
 278                                         }
 279                                 }
 280
 281                                 // for in-memory tables we could use: d.rData=x.rData;
 282                                 // but not for cached tables
 283                                 // relink d.parent, x.left, x.right
 284                                 if (xp == d) {
 285                                         d.Parent = x;
 286
 287                                         if (d.Left.Equals(x)) {
 288                                                 x.Left = d;
 289                                                 x.Right = d.Right;
 290                                         }
 291                                         else {
 292                                                 x.Right = d;
 293                                                 x.Left = d.Left;
 294                                         }
 295                                 }
 296                                 else {
 297                                         d.Parent = xp;
 298                                         xp.Right = d;
 299                                         x.Right = d.Right;
 300                                         x.Left = d.Left;
 301                                 }
 302
 303                                 x.Right.Parent = x;
 304                                 x.Left.Parent = x;
 305
 306                                 // set d.left, d.right
 307                                 d.Left = n;
 308
 309                                 if (n != null) {
 310                                         n.Parent = d;
 311                                 }
 312
 313                                 d.Right = null;
 314
 315                                 x = d;
 316                         }
 317
 318                         bool way = x.From();
 319
 320                         Replace(x, n);
 321
 322                         n = x.Parent;
 323                         x.Delete();
 324
 325                         while (n != null) {
 326                                 x = n;
 327
 328                                 int sign = way ? 1
 329                                         : -1;
 330
 331                                 switch (x.GetBalance() * sign)  {
 332
 333                                         case -1 :
 334                                                 x.SetBalance(0);
 335                                                 break;
 336
 337                                         case 0 :
 338                                                 x.SetBalance(sign);
 339
 340                                                 return;
 341
 342                                         case 1 :
 343                                                 Node r = Child(x, !way);
 344                                                 int  b = r.GetBalance();
 345
 346                                                 if (b * sign >= 0) {
 347                                                         Replace(x, r);
 348                                                         Set(x, !way, Child(r, way));
 349                                                         Set(r, way, x);
 350
 351                                                         if (b == 0) {
 352                                                                 x.SetBalance(sign);
 353                                                                 r.SetBalance(-sign);
 354
 355                                                                 return;
 356                                                         }
 357
 358                                                         x.SetBalance(0);
 359                                                         r.SetBalance(0);
 360
 361                                                         x = r;
 362                                                 }
 363                                                 else {
 364                                                         Node l = Child(r, way);
 365
 366                                                         Replace(x, l);
 367
 368                                                         b = l.GetBalance();
 369
 370                                                         Set(r, way, Child(l, !way));
 371                                                         Set(l, !way, r);
 372                                                         Set(x, !way, Child(l, way));
 373                                                         Set(l, way, x);
 374                                                         x.SetBalance((b == sign) ? -sign
 375                                                                 : 0);
 376                                                         r.SetBalance((b == -sign) ? sign
 377                                                                 : 0);
 378                                                         l.SetBalance(0);
 379
 380                                                         x = l;
 381                                                 }
 382                                                 break;
 383                                 }
 384
 385                                 way = x.From();
 386                                 n   = x.Parent;
 387                         }
 388                 }
 389
 390                 internal Node[] FindAllSimple(DataColumn[] relatedColumns, int index)
 391                 {
 392                         if (_columns.Length == 0) {
 393                                 return new Node[0];
 394                         }
 395
 396                         int tmpRecord = _columns[0].Table.RecordCache.NewRecord();
 397
 398                         try {
 399                                 for (int i = 0; i < relatedColumns.Length && i < _columns.Length; i++) {
 400                                         // according to MSDN: the DataType value for both columns must be identical.
 401                                         _columns[i].DataContainer.CopyValue(relatedColumns[i].DataContainer, index, tmpRecord);
 402                                 }
 403
 404                                 return FindAllSimple(tmpRecord, relatedColumns.Length);
 405                         }
 406                         finally {
 407                                 _columns[0].Table.RecordCache.DisposeRecord(tmpRecord);
 408                         }
 409                 }
 410
 411                 internal Node[] FindAllSimple(int index, int length)
 412                 {
 413                         ArrayList nodes = new ArrayList();
 414                         Node n = FindSimple (index, length, true);
 415                         if (n == null)
 416                                 return new Node[0];
 417                         while (n != null && ComparePartialRowNonUnique(index, n.Row.IndexFromVersion(DataRowVersion.Current), length) == 0) {
 418                                 nodes.Add (n);
 419                                 n = Next (n);
 420                         }
 421
 422                         return (Node[])nodes.ToArray (typeof (Node));
 423                 }
 424
 425                 internal Node FindSimple(int index, int length, bool first)
 426                 {
 427                         Node x      = _root, n;
 428                         Node result = null;
 429
 430                         if (_columns.Length > 0 && _columns[0].DataContainer.IsNull(index)) {
 431                                 return null;
 432                         }
 433
 434                         while (x != null) {
 435
 436                                 int i = this.ComparePartialRowNonUnique(index, x.Row.IndexFromVersion(DataRowVersion.Current), length);
 437
 438                                 if (i == 0) {
 439                                         if (first == false) {
 440                                                 result = x;
 441                                                 break;
 442                                         }
 443                                         else if (result == x) {
 444                                                 break;
 445                                         }
 446                                         result = x;
 447                                         n      = x.Left;
 448                                 }
 449                                 else if (i > 0) {
 450                                         n = x.Right;
 451                                 }
 452                                 else {
 453                                         n = x.Left;
 454                                 }
 455
 456                                 if (n == null)
 457                                 {
 458                                         break;
 459                                 }
 460
 461                                 x = n;
 462                         }
 463
 464                         return result;
 465                 }
 466
 467                 internal Node Find(DataRow data, DataRowVersion version)
 468                 {
 469
 470                         Node x = _root, n;
 471
 472                         while (x != null) {
 473                                 int i = CompareRow(data, version, x.Row);
 474
 475                                 if (i == 0) {
 476                                         return x;
 477                                 }
 478                                 else if (i > 0) {
 479                                         n = x.Right;
 480                                 }
 481                                 else {
 482                                         n = x.Left;
 483                                 }
 484
 485                                 if (n == null) {
 486                                         return null;
 487                                 }
 488
 489                                 x = n;
 490                         }
 491
 492                         return null;
 493                 }
 494
 495                 //              internal Node FindFirst(Object value, int compare)
 496                 //              {
 497                 //                      Node x     = _root;
 498                 //                      int  iTest = 1;
 499                 //
 500                 //                      //        if (compare == Expression.BIGGER) {
 501                 //                      //            iTest = 0;
 502                 //                      //        }
 503                 //
 504                 //                      while (x != null) {
 505                 //                              bool t = CompareValue(value, x.GetData()[0]) >= iTest;
 506                 //
 507                 //                              if (t) {
 508                 //                                      Node r = x.Right;
 509                 //
 510                 //                                      if (r == null)
 511                 //                                      {
 512                 //                                              break;
 513                 //                                      }
 514                 //
 515                 //                                      x = r;
 516                 //                              }
 517                 //                              else {
 518                 //                                      Node l = x.Left;
 519                 //
 520                 //                                      if (l == null) {
 521                 //                                              break;
 522                 //                                      }
 523                 //
 524                 //                                      x = l;
 525                 //                              }
 526                 //                      }
 527                 //
 528                 //                      while (x != null && CompareValue(value, x.GetData()[0]) >= iTest) {
 529                 //                              x = Next(x);
 530                 //                      }
 531                 //
 532                 //                      return x;
 533                 //              }
 534
 535                 //              internal Node First()
 536                 //              {
 537                 //
 538                 //                      Node x = _root,
 539                 //                      l = x;
 540                 //
 541                 //                      while (l != null) {
 542                 //
 543                 //                              x = l;
 544                 //                              l = x.Left;
 545                 //                      }
 546                 //
 547                 //                      return x;
 548                 //              }
 549
 550                 internal Node Next(Node x)
 551                 {
 552
 553                         if (x == null) {
 554                                 return null;
 555                         }
 556
 557                         Node r = x.Right;
 558
 559                         if (r != null) {
 560                                 x = r;
 561
 562                                 Node l = x.Left;
 563
 564                                 while (l != null) {
 565                                         x = l;
 566                                         l = x.Left;
 567                                 }
 568
 569                                 return x;
 570                         }
 571
 572                         Node ch = x;
 573
 574                         x = x.Parent;
 575
 576                         while (x != null && ch.Equals(x.Right)) {
 577
 578                                 ch = x;
 579                                 x  = x.Parent;
 580                         }
 581
 582                         return x;
 583                 }
 584
 585                 private Node Child(Node x, bool w)
 586                 {
 587                         return w ? x.Left
 588                                 : x.Right;
 589                 }
 590
 591                 private void Replace(Node x, Node n)
 592                 {
 593
 594                         if (x.Equals(_root)) {
 595                                 _root = n;
 596
 597                                 if (n != null) {
 598                                         n.Parent = null;
 599                                 }
 600                         }
 601                         else {
 602                                 Set(x.Parent, x.From(), n);
 603                         }
 604                 }
 605
 606                 private void Set(Node x, bool w, Node n)
 607                 {
 608                         if (w) {
 609                                 x.Left = n;
 610                         }
 611                         else {
 612                                 x.Right = n;
 613                         }
 614
 615                         if (n != null) {
 616                                 n.Parent = x;
 617                         }
 618                 }
 619
 620                 private Node Search(DataRow r,DataRowVersion version)
 621                 {
 622
 623                         Node x = _root;
 624
 625                         while (x != null) {
 626                                 int c = CompareRow(r, version,  x.Row);
 627
 628                                 if (c == 0) {
 629                                         return x;
 630                                 }
 631                                 else if (c < 0) {
 632                                         x = x.Left;
 633                                 }
 634                                 else {
 635                                         x = x.Right;
 636                                 }
 637                         }
 638
 639                         return null;
 640                 }
 641
 642                 internal int ComparePartialRowNonUnique(int index1, int index2, int length)
 643                 {
 644                         int i = _columns[0].CompareValues(index1, index2);
 645
 646                         if (i != 0) {
 647                                 return i;
 648                         }
 649
 650                         int fieldcount = _columns.Length;
 651
 652                         for (int j = 1; j < length && j < fieldcount; j++) {
 653                                 DataColumn column = _columns[j];
 654
 655                                 if (column.DataContainer.IsNull(index1)) {
 656                                         continue;
 657                                 }
 658
 659                                 i = column.CompareValues(index1, index2);
 660
 661                                 if (i != 0) {
 662                                         return i;
 663                                 }
 664                         }
 665
 666                         return 0;
 667                 }
 668
 669                 //              private int CompareRowNonUnique(DataRow a, DataRow b)
 670                 //              {
 671                 //                      if (a == b)
 672                 //                              return 0;
 673                 //
 674                 //                      int i = DataColumn.CompareValues(a[0], GetNodeValue(b,0), _columns[0].DataType, !_columns[0].Table.CaseSensitive);
 675                 //
 676                 //                      if (i != 0) {
 677                 //                              return i;
 678                 //                      }
 679                 //
 680                 //                      int fieldcount = _columns.Length;
 681                 //
 682                 //                      for (int j = 1; j < fieldcount; j++) {
 683                 //                              i = DataColumn.CompareValues(a[_columns[j].Ordinal], b[_columns[j].Ordinal], _columns[j].DataType, !_columns[j].Table.CaseSensitive);
 684                 //
 685                 //                              if (i != 0) {
 686                 //                                      return i;
 687                 //                              }
 688                 //                      }
 689                 //
 690                 //                      return 0;
 691                 //              }
 692
 693                 private int CompareRow(DataRow a, DataRowVersion version, DataRow b)
 694                 {
 695                         //                      if (a == b)
 696                         //                              return 0;
 697
 698                         int index1 = a.IndexFromVersion(version);
 699                         int index2 = b.IndexFromVersion(DataRowVersion.Current);
 700                         for (int j = 0; j < _columns.Length; j++) {
 701                                 int i = _columns[j].DataContainer.CompareValues(index1, index2);
 702
 703                                 if (i != 0) {
 704                                         return i;
 705                                 }
 706                         }
 707
 708                         return 0;
 709                 }
 710
 711                 //              private int CompareValue(Object a, Object b)
 712                 //              {
 713                 //                      if (a == DBNull.Value) {
 714                 //                              if (b == DBNull.Value)
 715                 //                                      return 0;
 716                 //                              return -1;
 717                 //                      }
 718                 //
 719                 //                      if (b == DBNull.Value)
 720                 //                              return 1;
 721                 //
 722                 //                      return System.Data.Common.DBComparerFactory.GetComparer(b.GetType(), false).Compare(a, b);
 723                 //              }
 724
 725                 //              /// <summary>
 726                 //              /// When we are inspectiong node (row) value in the index
 727                 //              /// we are alway referencing its Current value
 728                 //              /// </summary>
 729                 //              private object GetNodeValue(DataRow row,DataColumn column)
 730                 //              {
 731                 //                      return row[column,DataRowVersion.Current];
 732                 //              }
 733                 //
 734                 //              /// <summary>
 735                 //              /// When we are inspectiong node (row) value in the index
 736                 //              /// we are alway referencing its Current value
 737                 //              /// </summary>
 738                 //              private object GetNodeValue(DataRow row,index idx)
 739                 //              {
 740                 //                      return row[idx,DataRowVersion.Current];
 741                 //              }
 742
 743 //              internal String GetString()
 744 //              {
 745 //                      System.Text.StringBuilder sb = new System.Text.StringBuilder();
 746 //                      for(int i =0; i < this._columns.Length; i++) {
 747 //                              sb.Append("[ " + _columns[i].ColumnName + " ]  ");
 748 //                      }
 749 //                      sb.Append("\n");
 750 //                      if(this.Root != null) {
 751 //                              this.Root.CollectString(sb,0);
 752 //                      }
 753 //                      return sb.ToString();
 754 //              }
 755         }
 756 } */