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