mcs/class/System.XML/System.Xml.XPath/Iterator.cs

   1 //
   2 // System.Xml.XPath.BaseIterator
   3 //
   4 // Author:
   5 //   Piers Haken (piersh@friskit.com)
   6 //   Atsushi Enomoto (atsushi@ximian.com)
   7 //
   8 // (C) 2002 Piers Haken
   9 // (C) 2003 Atsushi Enomoto
  10 //
  11
  12 //
  13 // Permission is hereby granted, free of charge, to any person obtaining
  14 // a copy of this software and associated documentation files (the
  15 // "Software"), to deal in the Software without restriction, including
  16 // without limitation the rights to use, copy, modify, merge, publish,
  17 // distribute, sublicense, and/or sell copies of the Software, and to
  18 // permit persons to whom the Software is furnished to do so, subject to
  19 // the following conditions:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31 //
  32
  33 using System;
  34 using System.Collections;
  35 using System.Xml;
  36 using System.Xml.XPath;
  37 using System.Xml.Xsl;
  38
  39 #if NET_2_0
  40 using NSResolver = System.Xml.IXmlNamespaceResolver;
  41 #else
  42 using NSResolver = System.Xml.XmlNamespaceManager;
  43 #endif
  44
  45 namespace System.Xml.XPath
  46 {
  47         internal abstract class BaseIterator : XPathNodeIterator
  48         {
  49                 NSResolver _nsm;
  50                 int position;
  51
  52                 internal BaseIterator (BaseIterator other)
  53                 {
  54                         _nsm = other._nsm;
  55                         position = other.position;
  56                 }
  57                 internal BaseIterator (NSResolver nsm)
  58                 {
  59                         _nsm = nsm;
  60                 }
  61
  62                 public NSResolver NamespaceManager
  63                 {
  64                         get { return _nsm; }
  65                         set { _nsm = value; }
  66                 }
  67
  68                 public virtual bool ReverseAxis {
  69                         get { return false; }
  70                 }
  71
  72                 public int ComparablePosition {
  73                         get {
  74                                 if (ReverseAxis) {
  75                                         int diff = Count - CurrentPosition + 1;
  76                                         return diff < 1 ? 1 : diff;
  77                                 }
  78                                 else
  79                                         return CurrentPosition;
  80                         }
  81                 }
  82
  83                 public override int CurrentPosition {
  84                         get { return position; }
  85                 }
  86
  87                 internal void SetPosition (int pos)
  88                 {
  89                         position = pos;
  90                 }
  91
  92                 public override bool MoveNext ()
  93                 {
  94 // FIXME: enable this line once I found the culprit of a breakage in WrapperIterator. And remove it again in the final stage.
  95 //if (CurrentPosition == 0 && Current != null) throw new Exception (GetType ().FullName);
  96                         if (!MoveNextCore ())
  97                                 return false;
  98                         position++;
  99                         return true;
 100                 }
 101
 102                 public abstract bool MoveNextCore ();
 103
 104                 internal XPathNavigator PeekNext ()
 105                 {
 106                         XPathNodeIterator i = Clone ();
 107                         return i.MoveNext () ? i.Current : null;
 108                 }
 109
 110                 public override string ToString ()
 111                 {
 112                         if (Current != null)
 113                                 return Current.NodeType.ToString () + "[" + CurrentPosition + "] : " + Current.Name + " = " + Current.Value;
 114                         else
 115                                 return this.GetType().ToString () + "[" + CurrentPosition + "]";
 116                 }
 117         }
 118
 119         internal class WrapperIterator : BaseIterator
 120         {
 121                 XPathNodeIterator iter;
 122
 123                 public WrapperIterator (XPathNodeIterator iter, NSResolver nsm)
 124                         : base (nsm)
 125                 {
 126                         this.iter = iter;
 127                 }
 128
 129                 private WrapperIterator (WrapperIterator other)
 130                         : base (other)
 131                 {
 132                         iter = other.iter.Clone ();
 133                 }
 134
 135                 public override XPathNodeIterator Clone ()
 136                 {
 137                         return new WrapperIterator (this);
 138                 }
 139
 140                 public override bool MoveNextCore ()
 141                 {
 142                         return iter.MoveNext ();
 143                 }
 144
 145                 public override XPathNavigator Current {
 146                         get { return iter.Current; }
 147                 }
 148         }
 149
 150         internal abstract class SimpleIterator : BaseIterator
 151         {
 152                 protected readonly XPathNavigator _nav;
 153                 protected XPathNavigator _current;
 154                 bool skipfirst;
 155
 156                 public SimpleIterator (BaseIterator iter) : base (iter.NamespaceManager)
 157                 {
 158                         if (iter.CurrentPosition == 0) {
 159                                 skipfirst = true;
 160                                 iter.MoveNext ();
 161                         }
 162                         if (iter.CurrentPosition > 0)
 163                                 _nav = iter.Current.Clone ();
 164                 }
 165                 protected SimpleIterator (SimpleIterator other, bool clone) : base (other)
 166                 {
 167                         if (other._nav != null)
 168                                 _nav = clone ? other._nav.Clone () : other._nav;
 169                         skipfirst = other.skipfirst;
 170                 }
 171                 public SimpleIterator (XPathNavigator nav, NSResolver nsm) : base (nsm)
 172                 {
 173                         _nav = nav.Clone ();
 174                 }
 175
 176                 public override bool MoveNext ()
 177                 {
 178                         if (skipfirst) {
 179                                 if (_nav == null)
 180                                         return false; // empty
 181                                 skipfirst = false;
 182                                 base.SetPosition (1);
 183                                 return true;
 184                         } else {
 185                                 return base.MoveNext ();
 186                         }
 187                 }
 188
 189                 public override XPathNavigator Current {
 190                         get {
 191                                 if (CurrentPosition == 0)
 192                                         return null;
 193                                 _current = _nav;
 194                                 return _current;
 195                         }
 196                 }
 197         }
 198
 199         internal class SelfIterator : SimpleIterator
 200         {
 201                 public SelfIterator (BaseIterator iter) : base (iter) {}
 202                 public SelfIterator (XPathNavigator nav, NSResolver nsm) : base (nav, nsm) {}
 203                 protected SelfIterator (SelfIterator other, bool clone) : base (other, true)
 204                 {
 205                 }
 206
 207                 public override XPathNodeIterator Clone () { return new SelfIterator (this, true); }
 208                 public override bool MoveNextCore ()
 209                 {
 210                         if (CurrentPosition == 0)
 211                         {
 212                                 return true;
 213                         }
 214                         return false;
 215                 }
 216
 217                 public override XPathNavigator Current {
 218                         get { return CurrentPosition == 0 ? null : _nav; }
 219                 }
 220         }
 221
 222         internal class NullIterator : SelfIterator
 223         {
 224                 public NullIterator (BaseIterator iter) : base (iter) {}
 225                 public NullIterator (XPathNavigator nav) : this (nav, null) {}
 226                 public NullIterator (XPathNavigator nav, NSResolver nsm) : base (nav, nsm) {}
 227                 private NullIterator (NullIterator other) : base (other, true) {}
 228                 public override XPathNodeIterator Clone () { return new NullIterator (this); }
 229                 public override bool MoveNextCore ()
 230                 {
 231                         return false;
 232                 }
 233
 234                 public override int CurrentPosition {
 235                         get { return 1; }
 236                 }
 237
 238                 public override XPathNavigator Current {
 239                         get { return _nav; }
 240                 }
 241         }
 242
 243         internal class ParensIterator : BaseIterator
 244         {
 245                 BaseIterator _iter;
 246
 247                 public ParensIterator (BaseIterator iter) : base (iter.NamespaceManager)
 248                 {
 249                         _iter = iter;
 250                 }
 251                 private ParensIterator (ParensIterator other) : base (other)
 252                 {
 253                         _iter = (BaseIterator) other._iter.Clone ();
 254                 }
 255                 public override XPathNodeIterator Clone () { return new ParensIterator (this); }
 256                 public override bool MoveNextCore ()
 257                 {
 258                         return _iter.MoveNext ();
 259                 }
 260
 261                 public override XPathNavigator Current { get { return _iter.Current; }}
 262
 263                 public override int Count { get { return _iter.Count; } }
 264         }
 265
 266         internal class ParentIterator : SimpleIterator
 267         {
 268                 bool canMove;
 269                 public ParentIterator (BaseIterator iter) : base (iter)
 270                 {
 271                         canMove = _nav.MoveToParent ();
 272                         //_current = _nav;
 273                 }
 274                 private ParentIterator (ParentIterator other, bool dummy) : base (other, true)
 275                 {
 276                         //_current = _nav;
 277                         canMove = other.canMove;
 278                 }
 279                 public ParentIterator (XPathNavigator nav, NSResolver nsm) : base (nav, nsm) {}
 280                 public override XPathNodeIterator Clone () { return new ParentIterator (this, true); }
 281                 public override bool MoveNextCore ()
 282                 {
 283                         if (!canMove)
 284                                 return false;
 285                         canMove = false;
 286                         return true;
 287                 }
 288         }
 289
 290         internal class ChildIterator : BaseIterator
 291         {
 292                 XPathNavigator _nav;
 293
 294                 public ChildIterator (BaseIterator iter) : base (iter.NamespaceManager)
 295                 {
 296                         _nav = iter.CurrentPosition == 0 ? iter.PeekNext () : iter.Current;
 297                         if (_nav != null && _nav.HasChildren)
 298                                 _nav = _nav.Clone ();
 299                         else
 300                                 _nav = null;
 301                 }
 302                 private ChildIterator (ChildIterator other) : base (other)
 303                 {
 304                         _nav = other._nav == null ? null : other._nav.Clone ();
 305                 }
 306
 307                 public override XPathNodeIterator Clone () { return new ChildIterator (this); }
 308
 309                 public override bool MoveNextCore ()
 310                 {
 311                         if (_nav == null)
 312                                 return false;
 313
 314                         return (CurrentPosition == 0) ? _nav.MoveToFirstChild () : _nav.MoveToNext ();
 315                 }
 316
 317                 public override XPathNavigator Current {
 318                         get {
 319                                 if (CurrentPosition == 0)
 320                                         return null;
 321                                 return _nav;
 322                         }
 323                 }
 324         }
 325
 326         internal class FollowingSiblingIterator : SimpleIterator
 327         {
 328                 public FollowingSiblingIterator (BaseIterator iter) : base (iter) {}
 329                 private FollowingSiblingIterator (FollowingSiblingIterator other) : base (other, true) {}
 330                 public override XPathNodeIterator Clone () { return new FollowingSiblingIterator (this); }
 331                 public override bool MoveNextCore ()
 332                 {
 333                         switch (_nav.NodeType) {
 334                         case XPathNodeType.Attribute:
 335                         case XPathNodeType.Namespace:
 336                                 // They have no siblings.
 337                                 return false;
 338                         }
 339                         if (_nav.MoveToNext ())
 340                         {
 341 //                              Current.MoveTo (_nav);
 342                                 return true;
 343                         }
 344                         return false;
 345                 }
 346         }
 347
 348         internal class PrecedingSiblingIterator : SimpleIterator
 349         {
 350                 bool finished;
 351                 bool started;
 352                 XPathNavigator startPosition;
 353
 354                 public PrecedingSiblingIterator (BaseIterator iter) : base (iter)
 355                 {
 356                         startPosition = iter.Current.Clone ();
 357                 }
 358                 private PrecedingSiblingIterator (PrecedingSiblingIterator other) : base (other, true)
 359                 {
 360                         startPosition = other.startPosition;
 361                         started = other.started;
 362                         finished = other.finished;
 363                 }
 364
 365                 public override XPathNodeIterator Clone () { return new PrecedingSiblingIterator (this); }
 366                 public override bool MoveNextCore ()
 367                 {
 368                         if (finished)
 369                                 return false;
 370                         if (!started) {
 371                                 started = true;
 372                                 switch (_nav.NodeType) {
 373                                 case XPathNodeType.Attribute:
 374                                 case XPathNodeType.Namespace:
 375                                         // They have no siblings.
 376                                         finished = true;
 377                                         return false;
 378                                 }
 379
 380                                 _nav.MoveToFirst ();
 381                                 if (!_nav.IsSamePosition (startPosition)) {
 382 //                                      Current.MoveTo (_nav);
 383                                         return true;
 384                                 }
 385                         } else {
 386                                 if (!_nav.MoveToNext ()) {
 387                                         finished = true;
 388                                         return false;
 389                                 }
 390                         }
 391                         if (_nav.ComparePosition (startPosition) != XmlNodeOrder.Before) {
 392                                 // Note that if _nav contains only 1 node, it won't be Same.
 393                                 finished = true;
 394                                 return false;
 395                         } else {
 396 //                              Current.MoveTo (_nav);
 397                                 return true;
 398                         }
 399                 }
 400                 public override bool ReverseAxis {
 401                         get { return true; }
 402                 }
 403         }
 404
 405         internal class AncestorIterator : SimpleIterator
 406         {
 407                 int currentPosition;
 408                 ArrayList navigators;
 409                 XPathNavigator startPosition;
 410
 411                 public AncestorIterator (BaseIterator iter) : base (iter)
 412                 {
 413                         startPosition = iter.Current.Clone ();
 414                 }
 415
 416                 private AncestorIterator (AncestorIterator other)
 417                         : base (other, true)
 418                 {
 419                         startPosition = other.startPosition;
 420                         if (other.navigators != null)
 421                                 navigators = (ArrayList) other.navigators;
 422                         currentPosition = other.currentPosition;
 423                 }
 424
 425                 public override XPathNodeIterator Clone ()
 426                 {
 427                         return new AncestorIterator (this);
 428                 }
 429
 430                 private void CollectResults ()
 431                 {
 432                         navigators = new ArrayList ();
 433
 434                         XPathNavigator ancestors = startPosition.Clone ();
 435                         while (ancestors.NodeType != XPathNodeType.Root && ancestors.MoveToParent ())
 436                                 navigators.Add (ancestors.Clone ());
 437                         currentPosition = navigators.Count;
 438                 }
 439
 440                 public override bool MoveNextCore ()
 441                 {
 442                         if (navigators == null)
 443                                 CollectResults ();
 444                         if (currentPosition == 0)
 445                                 return false;
 446                         _nav.MoveTo ((XPathNavigator) navigators [--currentPosition]);
 447 //                      Current.MoveTo (_nav);
 448                         return true;
 449                 }
 450
 451                 public override bool ReverseAxis {
 452                         get { return true; }
 453                 }
 454
 455                 public override int Count {
 456                         get {
 457                                 if (navigators == null)
 458                                         CollectResults ();
 459                                 return navigators.Count;
 460                         }
 461                 }
 462         }
 463
 464         internal class AncestorOrSelfIterator : SimpleIterator
 465         {
 466                 int currentPosition;
 467                 ArrayList navigators;
 468                 XPathNavigator startPosition;
 469
 470                 public AncestorOrSelfIterator (BaseIterator iter) : base (iter)
 471                 {
 472                         startPosition = iter.Current.Clone ();
 473                 }
 474
 475                 private AncestorOrSelfIterator (AncestorOrSelfIterator other)
 476                         : base (other, true)
 477                 {
 478                         startPosition = other.startPosition;
 479                         if (other.navigators != null)
 480                                 navigators = (ArrayList) other.navigators.Clone ();
 481                         currentPosition = other.currentPosition;
 482                 }
 483
 484                 public override XPathNodeIterator Clone ()
 485                 {
 486                         return new AncestorOrSelfIterator (this);
 487                 }
 488
 489                 private void CollectResults ()
 490                 {
 491                         navigators = new ArrayList ();
 492
 493                         XPathNavigator ancestors = startPosition.Clone ();
 494                         if (!ancestors.MoveToParent ())
 495                                 return;
 496                         while (ancestors.NodeType != XPathNodeType.Root) {
 497                                 navigators.Add (ancestors.Clone ());
 498                                 ancestors.MoveToParent ();
 499                         }
 500                         currentPosition = navigators.Count;
 501                 }
 502
 503                 public override bool MoveNextCore ()
 504                 {
 505                         if (navigators == null) {
 506                                 CollectResults ();
 507                                 if (startPosition.NodeType != XPathNodeType.Root) {
 508                                         // First time it returns Root
 509                                         _nav.MoveToRoot ();
 510 //                                      Current.MoveTo (_nav);
 511                                         return true;
 512                                 }
 513                         }
 514                         if (currentPosition == -1)
 515                                 return false;
 516                         if (currentPosition-- == 0) {
 517                                 _nav.MoveTo (startPosition);
 518 //                              Current.MoveTo (_nav);
 519                                 return true; // returns self.
 520                         }
 521                         _nav.MoveTo ((XPathNavigator) navigators [currentPosition]);
 522 //                      Current.MoveTo (_nav);
 523                         return true;
 524                 }
 525
 526                 public override bool ReverseAxis {
 527                         get { return true; }
 528                 }
 529
 530                 public override int Count {
 531                         get {
 532                                 if (navigators == null)
 533                                         CollectResults ();
 534                                 return navigators.Count + 1;
 535                         }
 536                 }
 537         }
 538
 539         internal class DescendantIterator : SimpleIterator
 540         {
 541                 private int _depth;
 542                 private bool _finished;
 543
 544                 public DescendantIterator (BaseIterator iter) : base (iter) {}
 545
 546                 private DescendantIterator (DescendantIterator other) : base (other, true)
 547                 {
 548                         _depth = other._depth;
 549                         _finished = other._finished;
 550                 }
 551
 552                 public override XPathNodeIterator Clone () { return new DescendantIterator (this); }
 553
 554                 public override bool MoveNextCore ()
 555                 {
 556                         if (_finished)
 557                                 return false;
 558
 559                         if (_nav.MoveToFirstChild ())
 560                         {
 561                                 _depth ++;
 562 //                              Current.MoveTo (_nav);
 563                                 return true;
 564                         }
 565                         while (_depth != 0)
 566                         {
 567                                 if (_nav.MoveToNext ())
 568                                 {
 569 //                                      Current.MoveTo (_nav);
 570                                         return true;
 571                                 }
 572                                 if (!_nav.MoveToParent ())      // should NEVER fail!
 573                                         throw new XPathException ("Current node is removed while it should not be, or there are some bugs in the XPathNavigator implementation class: " + _nav.GetType ());
 574                                 _depth --;
 575                         }
 576                         _finished = true;
 577                         return false;
 578                 }
 579         }
 580
 581         internal class DescendantOrSelfIterator : SimpleIterator
 582         {
 583                 private int _depth;
 584                 private bool _finished;
 585
 586                 public DescendantOrSelfIterator (BaseIterator iter) : base (iter) {}
 587
 588                 private DescendantOrSelfIterator (DescendantOrSelfIterator other) : base (other, true)
 589                 {
 590                         _depth = other._depth;
 591                 }
 592
 593                 public override XPathNodeIterator Clone () { return new DescendantOrSelfIterator (this); }
 594
 595                 public override bool MoveNextCore ()
 596                 {
 597                         if (_finished)
 598                                 return false;
 599
 600                         if (CurrentPosition == 0)
 601                         {
 602                                 // self
 603 //                              Current.MoveTo (_nav);
 604                                 return true;
 605                         }
 606                         if (_nav.MoveToFirstChild ())
 607                         {
 608                                 _depth ++;
 609 //                              Current.MoveTo (_nav);
 610                                 return true;
 611                         }
 612                         while (_depth != 0)
 613                         {
 614                                 if (_nav.MoveToNext ())
 615                                 {
 616 //                                      Current.MoveTo (_nav);
 617                                         return true;
 618                                 }
 619                                 if (!_nav.MoveToParent ())      // should NEVER fail!
 620                                         throw new XPathException ("Current node is removed while it should not be, or there are some bugs in the XPathNavigator implementation class: " + _nav.GetType ());
 621                                 _depth --;
 622                         }
 623                         _finished = true;
 624                         return false;
 625                 }
 626         }
 627
 628         internal class FollowingIterator : SimpleIterator
 629         {
 630                 private bool _finished = false;
 631                 public FollowingIterator (BaseIterator iter) : base (iter) {}
 632                 private FollowingIterator (FollowingIterator other) : base (other, true) {}
 633                 public override XPathNodeIterator Clone () { return new FollowingIterator (this); }
 634                 public override bool MoveNextCore ()
 635                 {
 636                         if (_finished)
 637                                 return false;
 638                         bool checkChildren = true;
 639                         if (CurrentPosition == 0)
 640                         {
 641                                 checkChildren = false;
 642                                 switch (_nav.NodeType) {
 643                                 case XPathNodeType.Attribute:
 644                                 case XPathNodeType.Namespace:
 645                                         _nav.MoveToParent ();
 646                                         checkChildren = true;
 647                                         break;
 648                                 default:
 649                                         if (_nav.MoveToNext ())
 650                                         {
 651 //                                              Current.MoveTo (_nav);
 652                                                 return true;
 653                                         } else {
 654                                                 while (_nav.MoveToParent ()) {
 655                                                         if (_nav.MoveToNext ()) {
 656 //                                                              Current.MoveTo (_nav);
 657                                                                 return true;
 658                                                         }
 659                                                 }
 660                                         }
 661                                         break;
 662                                 }
 663                         }
 664                         if (checkChildren)
 665                         {
 666                                 if (_nav.MoveToFirstChild ())
 667                                 {
 668 //                                      Current.MoveTo (_nav);
 669                                         return true;
 670                                 }
 671                                 do
 672                                 {
 673                                         if (_nav.MoveToNext ())
 674                                         {
 675 //                                              Current.MoveTo (_nav);
 676                                                 return true;
 677                                         }
 678                                 }
 679                                 while (_nav.MoveToParent ());
 680                         }
 681                         _finished = true;
 682                         return false;
 683                 }
 684         }
 685
 686         internal class PrecedingIterator : SimpleIterator
 687         {
 688                 bool finished;
 689                 bool started;
 690                 XPathNavigator startPosition;
 691
 692                 public PrecedingIterator (BaseIterator iter) : base (iter)
 693                 {
 694                         startPosition = iter.Current.Clone ();
 695                 }
 696                 private PrecedingIterator (PrecedingIterator other) : base (other, true)
 697                 {
 698                         startPosition = other.startPosition;
 699                         started = other.started;
 700                         finished = other.finished;
 701                 }
 702                 public override XPathNodeIterator Clone () { return new PrecedingIterator (this); }
 703                 public override bool MoveNextCore ()
 704                 {
 705                         if (finished)
 706                                 return false;
 707                         if (!started) {
 708                                 started = true;
 709                                 _nav.MoveToRoot ();
 710                         }
 711                         bool loop = true;
 712                         while (loop) {
 713                                 while (!_nav.MoveToFirstChild ()) {
 714                                         while (!_nav.MoveToNext ()) {
 715                                                 if (!_nav.MoveToParent ()) { // Should not finish, at least before startPosition.
 716                                                         finished = true;
 717                                                         return false;
 718                                                 }
 719                                         }
 720                                         break;
 721                                 }
 722                                 if (_nav.IsDescendant (startPosition))
 723                                         continue;
 724                                 loop = false;
 725                                 break;
 726                         }
 727                         if (_nav.ComparePosition (startPosition) != XmlNodeOrder.Before) {
 728                                 // Note that if _nav contains only 1 node, it won't be Same.
 729                                 finished = true;
 730                                 return false;
 731                         } else {
 732 //                              Current.MoveTo (_nav);
 733                                 return true;
 734                         }
 735                 }
 736                 public override bool ReverseAxis {
 737                         get { return true; }
 738                 }
 739         }
 740
 741         internal class NamespaceIterator : SimpleIterator
 742         {
 743                 public NamespaceIterator (BaseIterator iter) : base (iter) {}
 744                 private NamespaceIterator (NamespaceIterator other) : base (other, true) {}
 745                 public override XPathNodeIterator Clone () { return new NamespaceIterator (this); }
 746                 public override bool MoveNextCore ()
 747                 {
 748                         if (CurrentPosition == 0)
 749                         {
 750                                 if (_nav.MoveToFirstNamespace ())
 751                                 {
 752 //                                      Current.MoveTo (_nav);
 753                                         return true;
 754                                 }
 755                         }
 756                         else if (_nav.MoveToNextNamespace ())
 757                         {
 758 //                              Current.MoveTo (_nav);
 759                                 return true;
 760                         }
 761                         return false;
 762                 }
 763         }
 764
 765         internal class AttributeIterator : SimpleIterator
 766         {
 767                 public AttributeIterator (BaseIterator iter) : base (iter) {}
 768                 private AttributeIterator (AttributeIterator other) : base (other, true) {}
 769                 public override XPathNodeIterator Clone () { return new AttributeIterator (this); }
 770                 public override bool MoveNextCore ()
 771                 {
 772                         if (CurrentPosition == 0)
 773                         {
 774                                 if (_nav.MoveToFirstAttribute ())
 775                                 {
 776 //                                      Current.MoveTo (_nav);
 777                                         return true;
 778                                 }
 779                         }
 780                         else if (_nav.MoveToNextAttribute ())
 781                         {
 782 //                              Current.MoveTo (_nav);
 783                                 return true;
 784                         }
 785                         return false;
 786                 }
 787         }
 788
 789         internal class AxisIterator : BaseIterator
 790         {
 791                 private BaseIterator _iter;
 792                 private NodeTest _test;
 793
 794                 //string name, ns;
 795                 //XPathNodeType matchType;
 796
 797                 public AxisIterator (BaseIterator iter, NodeTest test) : base (iter.NamespaceManager)
 798                 {
 799                         _iter = iter;
 800                         _test = test;
 801                         //test.GetInfo (out name, out ns, out matchType, NamespaceManager);
 802 //                      if (name != null)
 803 //                              name = Current.NameTable.Add (name);
 804
 805 //                      if (ns != null)
 806 //                              ns = Current.NameTable.Add (ns);
 807                 }
 808
 809                 private AxisIterator (AxisIterator other) : base (other)
 810                 {
 811                         _iter = (BaseIterator) other._iter.Clone ();
 812                         _test = other._test;
 813                         //name = other.name;
 814                         //ns = other.ns;
 815                         //matchType = other.matchType;
 816                 }
 817                 public override XPathNodeIterator Clone () { return new AxisIterator (this); }
 818
 819                 public override bool MoveNextCore ()
 820                 {
 821                         while (_iter.MoveNext ())
 822                         {
 823                                 if (_test.Match (NamespaceManager, _iter.Current))
 824                                 {
 825                                         return true;
 826                                 }
 827                         }
 828                         return false;
 829                 }
 830                 public override XPathNavigator Current { get { return CurrentPosition == 0 ? null : _iter.Current; }}
 831
 832                 public override bool ReverseAxis {
 833                         get { return _iter.ReverseAxis; }
 834                 }
 835         }
 836
 837         internal class SimpleSlashIterator : BaseIterator
 838         {
 839                 private NodeSet _expr;
 840                 private BaseIterator _left, _right;
 841                 private XPathNavigator _current;
 842
 843                 public SimpleSlashIterator (BaseIterator left, NodeSet expr)
 844                         : base (left.NamespaceManager)
 845                 {
 846                         this._left = left;
 847                         this._expr = expr;
 848                 }
 849
 850                 private SimpleSlashIterator (SimpleSlashIterator other)
 851                         : base (other)
 852                 {
 853                         _expr = other._expr;
 854                         _left = (BaseIterator) other._left.Clone ();
 855                         if (other._right != null)
 856                                 _right = (BaseIterator) other._right.Clone ();
 857                 }
 858
 859                 public override XPathNodeIterator Clone () { return new SimpleSlashIterator (this); }
 860
 861                 public override bool MoveNextCore ()
 862                 {
 863                         while (_right == null || !_right.MoveNext ()) {
 864                                 if (!_left.MoveNext ())
 865                                         return false;
 866                                 _right = _expr.EvaluateNodeSet (_left);
 867                         }
 868                         if (_current == null)
 869                                 _current = _right.Current.Clone ();
 870                         else
 871                                 if (! _current.MoveTo (_right.Current) )
 872                                         _current = _right.Current.Clone ();
 873                         return true;
 874                 }
 875
 876                 public override XPathNavigator Current {
 877                         get { return _current; }
 878                 }
 879         }
 880
 881         internal class SortedIterator : BaseIterator
 882         {
 883                 ArrayList list;
 884
 885                 public SortedIterator (BaseIterator iter) : base (iter.NamespaceManager)
 886                 {
 887                         list = new ArrayList ();
 888                         while (iter.MoveNext ())
 889                                 list.Add (iter.Current.Clone ());
 890
 891                         // sort
 892                         if (list.Count == 0)
 893                                 return;
 894                         XPathNavigator prev = (XPathNavigator) list [0];
 895                         list.Sort (XPathNavigatorComparer.Instance);
 896                         for (int i = 1; i < list.Count; i++) {
 897                                 XPathNavigator n = (XPathNavigator) list [i];
 898                                 if (prev.IsSamePosition (n)) {
 899                                         list.RemoveAt (i);
 900                                         i--;
 901                                 }
 902                                 else
 903                                         prev = n;
 904                         }
 905                 }
 906
 907                 public SortedIterator (SortedIterator other) : base (other)
 908                 {
 909                         this.list = other.list;
 910                         SetPosition (other.CurrentPosition);
 911                 }
 912
 913                 public override XPathNodeIterator Clone () { return new SortedIterator (this); }
 914
 915                 public override bool MoveNextCore ()
 916                 {
 917                         return CurrentPosition < list.Count;
 918                 }
 919
 920                 public override XPathNavigator Current {
 921                         get { return CurrentPosition == 0 ? null : (XPathNavigator) list [CurrentPosition - 1]; }
 922                 }
 923
 924                 public override int Count {
 925                         get { return list.Count; }
 926                 }
 927         }
 928
 929         // NOTE: it is *not* sorted. Do not directly use it without checking sorting requirement.
 930         internal class SlashIterator : BaseIterator
 931         {
 932                 private BaseIterator _iterLeft;
 933                 private BaseIterator _iterRight;
 934                 private NodeSet _expr;
 935                 SortedList _iterList;
 936                 bool _finished;
 937                 BaseIterator _nextIterRight;
 938
 939                 public SlashIterator (BaseIterator iter, NodeSet expr) : base (iter.NamespaceManager)
 940                 {
 941                         _iterLeft = iter;
 942                         _expr = expr;
 943                 }
 944
 945                 private SlashIterator (SlashIterator other) : base (other)
 946                 {
 947                         _iterLeft = (BaseIterator) other._iterLeft.Clone ();
 948                         if (other._iterRight != null)
 949                                 _iterRight = (BaseIterator) other._iterRight.Clone ();
 950                         _expr = other._expr;
 951                         if (other._iterList != null)
 952                                 _iterList = (SortedList) other._iterList.Clone ();
 953                         _finished = other._finished;
 954                         if (other._nextIterRight != null)
 955                                 _nextIterRight = (BaseIterator) other._nextIterRight.Clone ();
 956                 }
 957                 public override XPathNodeIterator Clone () { return new SlashIterator (this); }
 958
 959                 public override bool MoveNextCore ()
 960                 {
 961                         if (_finished)
 962                                 return false;
 963
 964                         if (_iterRight == null) { // First time
 965                                 if (!_iterLeft.MoveNext ())
 966                                         return false;
 967                                 _iterRight = _expr.EvaluateNodeSet (_iterLeft);
 968                                 _iterList = new SortedList (XPathIteratorComparer.Instance);
 969                         }
 970
 971                         while (true) {
 972                                 while (!_iterRight.MoveNext ()) {
 973                                         if (_iterList.Count > 0) {
 974                                                 int last = _iterList.Count - 1;
 975                                                 _iterRight = (BaseIterator) _iterList.GetByIndex (last);
 976                                                 _iterList.RemoveAt (last);
 977                                                 break;
 978                                         } else if (_nextIterRight != null) {
 979                                                 _iterRight = _nextIterRight;
 980                                                 _nextIterRight = null;
 981                                                 break;
 982                                         } else if (!_iterLeft.MoveNext ()) {
 983                                                 _finished = true;
 984                                                 return false;
 985                                         }
 986                                         else
 987                                                 _iterRight = _expr.EvaluateNodeSet (_iterLeft);
 988                                 }
 989                                 bool loop = true;
 990                                 while (loop) {
 991                                         loop = false;
 992                                         if (_nextIterRight == null) {
 993                                                 bool noMoreNext = false;
 994                                                 while (_nextIterRight == null || !_nextIterRight.MoveNext ()) {
 995                                                         if(_iterLeft.MoveNext ())
 996                                                                 _nextIterRight = _expr.EvaluateNodeSet (_iterLeft);
 997                                                         else {
 998                                                                 noMoreNext = true;
 999                                                                 break;
1000                                                         }
1001                                                 }
1002                                                 if (noMoreNext)
1003                                                         _nextIterRight = null; // FIXME: More efficient code. Maybe making noMoreNext class scope would be better.
1004                                         }
1005                                         if (_nextIterRight != null) {
1006                                                 switch (_iterRight.Current.ComparePosition (_nextIterRight.Current)) {
1007                                                 case XmlNodeOrder.After:
1008                                                         _iterList [_iterRight] = _iterRight;
1009                                                         _iterRight = _nextIterRight;
1010                                                         _nextIterRight = null;
1011                                                         loop = true;
1012                                                         break;
1013                                                 case XmlNodeOrder.Same:
1014                                                         if (!_nextIterRight.MoveNext ())
1015                                                                 _nextIterRight = null;
1016
1017                                                         else {
1018                                                                 int last = _iterList.Count;
1019                                                                 _iterList [_nextIterRight] = _nextIterRight;
1020                                                                 if (last != _iterList.Count) {
1021                                                                         _nextIterRight = (BaseIterator) _iterList.GetByIndex (last);
1022                                                                         _iterList.RemoveAt (last);
1023                                                                 }
1024                                                         }
1025
1026                                                         loop = true;
1027                                                         break;
1028                                                 }
1029                                         }
1030                                 }
1031                                 return true;
1032                         }
1033                 }
1034
1035                 public override XPathNavigator Current {
1036                         get {
1037                                 return (CurrentPosition == 0) ? null : _iterRight.Current;
1038                         }
1039                 }
1040         }
1041
1042         internal class PredicateIterator : BaseIterator
1043         {
1044                 private BaseIterator _iter;
1045                 private Expression _pred;
1046                 private XPathResultType resType;
1047                 private bool finished;
1048
1049                 public PredicateIterator (BaseIterator iter, Expression pred) : base (iter.NamespaceManager)
1050                 {
1051                         _iter = iter;
1052                         _pred = pred;
1053                         resType = pred.GetReturnType (iter);
1054                 }
1055
1056                 private PredicateIterator (PredicateIterator other) : base (other)
1057                 {
1058                         _iter = (BaseIterator) other._iter.Clone ();
1059                         _pred = other._pred;
1060                         resType = other.resType;
1061                         finished = other.finished;
1062                 }
1063                 public override XPathNodeIterator Clone () { return new PredicateIterator (this); }
1064
1065                 public override bool MoveNextCore ()
1066                 {
1067                         if (finished)
1068                                 return false;
1069                         while (_iter.MoveNext ())
1070                         {
1071                                 switch (resType) {
1072                                         case XPathResultType.Number:
1073                                                 if (_pred.EvaluateNumber (_iter) != _iter.ComparablePosition)
1074                                                         continue;
1075                                                 break;
1076                                         case XPathResultType.Any: {
1077                                                 object result = _pred.Evaluate (_iter);
1078                                                 if (result is double)
1079                                                 {
1080                                                         if ((double) result != _iter.ComparablePosition)
1081                                                                 continue;
1082                                                 }
1083                                                 else if (!XPathFunctions.ToBoolean (result))
1084                                                         continue;
1085                                         }
1086                                                 break;
1087                                         default:
1088                                                 if (!_pred.EvaluateBoolean (_iter))
1089                                                         continue;
1090                                                 break;
1091                                 }
1092
1093                                 return true;
1094                         }
1095                         finished = true;
1096                         return false;
1097                 }
1098                 public override XPathNavigator Current {
1099                         get { return CurrentPosition == 0 ? null : _iter.Current; }}
1100                 public override bool ReverseAxis {
1101                         get { return _iter.ReverseAxis; }
1102                 }
1103 public override string ToString () { return _iter.GetType ().FullName; }
1104         }
1105
1106         internal class ListIterator : BaseIterator
1107         {
1108                 private IList _list;
1109
1110                 public ListIterator (BaseIterator iter, IList list) : base (iter.NamespaceManager)
1111                 {
1112                         _list = list;
1113                 }
1114
1115                 public ListIterator (IList list, NSResolver nsm) : base (nsm)
1116                 {
1117                         _list = list;
1118                 }
1119
1120                 private ListIterator (ListIterator other) : base (other)
1121                 {
1122                         _list = other._list;
1123                 }
1124                 public override XPathNodeIterator Clone () { return new ListIterator (this); }
1125
1126                 public override bool MoveNextCore ()
1127                 {
1128                         if (CurrentPosition >= _list.Count)
1129                                 return false;
1130                         return true;
1131                 }
1132                 public override XPathNavigator Current {
1133                         get {
1134                                 if (_list.Count == 0 || CurrentPosition == 0)
1135                                         return null;
1136                                 return (XPathNavigator) _list [CurrentPosition - 1];
1137                         }
1138                 }
1139
1140                 public override int Count { get { return _list.Count; } }
1141         }
1142
1143
1144         internal class UnionIterator : BaseIterator
1145         {
1146                 private BaseIterator _left, _right;
1147                 private bool keepLeft;
1148                 private bool keepRight;
1149                 XPathNavigator _current;
1150
1151                 public UnionIterator (BaseIterator iter, BaseIterator left, BaseIterator right) : base (iter.NamespaceManager)
1152                 {
1153                         _left = left;
1154                         _right = right;
1155                 }
1156
1157                 private UnionIterator (UnionIterator other) : base (other)
1158                 {
1159                         _left = (BaseIterator) other._left.Clone ();
1160                         _right = (BaseIterator) other._right.Clone ();
1161                         keepLeft = other.keepLeft;
1162                         keepRight = other.keepRight;
1163                         if (other._current != null)
1164                                 _current = other._current.Clone ();
1165                 }
1166                 public override XPathNodeIterator Clone () { return new UnionIterator (this); }
1167
1168                 public override bool MoveNextCore ()
1169                 {
1170                         if (!keepLeft)
1171                                 keepLeft = _left.MoveNext ();
1172                         if (!keepRight)
1173                                 keepRight = _right.MoveNext ();
1174
1175                         if (!keepLeft && !keepRight)
1176                                 return false;
1177
1178                         if (!keepRight) {
1179                                 keepLeft = false;
1180                                 SetCurrent (_left);
1181                                 return true;
1182                         } else if (!keepLeft) {
1183                                 keepRight = false;
1184                                 SetCurrent (_right);
1185                                 return true;
1186                         }
1187
1188                         switch (_left.Current.ComparePosition (_right.Current)) {
1189                         case XmlNodeOrder.Same:
1190                                 // consume both. i.e. don't output duplicate result.
1191                                 keepLeft = keepRight = false;
1192                                 SetCurrent (_right);
1193                                 return true;
1194                         case XmlNodeOrder.Before:
1195                         case XmlNodeOrder.Unknown: // Maybe happen because of "document(a) | document(b)"
1196                                 keepLeft = false;
1197                                 SetCurrent (_left);
1198                                 return true;
1199                         case XmlNodeOrder.After:
1200                                 keepRight = false;
1201                                 SetCurrent (_right);
1202                                 return true;
1203                         default:
1204                                 throw new InvalidOperationException ("Should not happen.");
1205                         }
1206                 }
1207
1208                 private void SetCurrent (XPathNodeIterator iter)
1209                 {
1210                         if (_current == null)
1211                                 _current = iter.Current.Clone ();
1212                         else
1213                                 if (! _current.MoveTo (iter.Current) )
1214                                         _current = iter.Current.Clone ();
1215                 }
1216
1217                 public override XPathNavigator Current
1218                 {
1219                         get { return CurrentPosition > 0 ? _current : null; }
1220                 }
1221         }
1222
1223         internal class OrderedIterator : BaseIterator
1224         {
1225                 BaseIterator iter;
1226                 ArrayList list;
1227                 int index = -1;
1228
1229                 public OrderedIterator (BaseIterator iter)
1230                         : base (iter.NamespaceManager)
1231                 {
1232 //                      if (iter.Ordered)
1233 //                      if (false)
1234 //                              this.iter = iter;
1235 //                      else
1236                         {
1237                                 list = new ArrayList ();
1238                                 while (iter.MoveNext ())
1239                                         list.Add (iter.Current);
1240                                 list.Sort (XPathNavigatorComparer.Instance);
1241                         }
1242                 }
1243
1244                 private OrderedIterator (OrderedIterator other, bool dummy)
1245                         : base (other)
1246                 {
1247                         if (other.iter != null)
1248                                 iter = (BaseIterator) other.iter.Clone ();
1249                         list = other.list;
1250                         index = other.index;
1251                 }
1252
1253                 public override XPathNodeIterator Clone ()
1254                 {
1255                         return new OrderedIterator (this);
1256                 }
1257
1258                 public override bool MoveNextCore ()
1259                 {
1260                         if (iter != null)
1261                                 return iter.MoveNext ();
1262                         else if (index++ < list.Count)
1263                                 return true;
1264                         index--;
1265                         return false;
1266                 }
1267
1268                 public override XPathNavigator Current {
1269                         get { return iter != null ? iter.Current : index < 0 ? null : (XPathNavigator) list [index]; }
1270                 }
1271         }
1272 }