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