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

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