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