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