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

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