1 /**
  2  * @fileoverview Context information about nodes in their node-set.
  3  */
  4 
  5 goog.provide('xrx.xpath.NodeSet');
  6 
  7 goog.require('goog.dom');
  8 goog.require('xrx.node');
  9 
 10 
 11 
 12 /**
 13  * A set of nodes sorted by their prefix order in the document.
 14  *
 15  * @constructor
 16  */
 17 xrx.xpath.NodeSet = function() {
 18   // In violation of standard Closure practice, we initialize properties to
 19   // immutable constants in the constructor instead of on the prototype,
 20   // because we have empirically measured better performance by doing so.
 21 
 22   /**
 23    * A pointer to the first node in the linked list.
 24    *
 25    * @private
 26    * @type {xrx.xpath.NodeSet.Entry_}
 27    */
 28   this.first_ = null;
 29 
 30   /**
 31    * A pointer to the last node in the linked list.
 32    *
 33    * @private
 34    * @type {xrx.xpath.NodeSet.Entry_}
 35    */
 36   this.last_ = null;
 37 
 38   /**
 39    * Length of the linked list.
 40    *
 41    * @private
 42    * @type {number}
 43    */
 44   this.length_ = 0;
 45 };
 46 
 47 
 48 
 49 /**
 50  * A entry for a node in a linked list
 51  *
 52  * @param {!xrx.node} node The node to be added.
 53  * @constructor
 54  * @private
 55  */
 56 xrx.xpath.NodeSet.Entry_ = function(node) {
 57   // In violation of standard Closure practice, we initialize properties to
 58   // immutable constants in the constructor instead of on the prototype,
 59   // because we have empirically measured better performance by doing so.
 60 
 61   /**
 62    * @type {!xrx.node}
 63    */
 64   this.node = node;
 65 
 66   /**
 67    * @type {xrx.xpath.NodeSet.Entry_}
 68    */
 69   this.prev = null;
 70 
 71   /**
 72    * @type {xrx.xpath.NodeSet.Entry_}
 73    */
 74   this.next = null;
 75 };
 76 
 77 
 78 /**
 79  * Merges two node-sets, removing duplicates. This function may modify both
 80  * node-sets, and will return a reference to one of the two.
 81  *
 82  * <p> Note: We assume that the two node-sets are already sorted in DOM order.
 83  *
 84  * @param {!xrx.xpath.NodeSet} a The first node-set.
 85  * @param {!xrx.xpath.NodeSet} b The second node-set.
 86  * @return {!xrx.xpath.NodeSet} The merged node-set.
 87  */
 88 xrx.xpath.NodeSet.merge = function(a, b) {
 89   if (!a.first_) {
 90     return b;
 91   } else if (!b.first_) {
 92     return a;
 93   }
 94   var aCurr = a.first_;
 95   var bCurr = b.first_;
 96   var merged = a, tail = null, next = null, length = 0;
 97   while (aCurr && bCurr) {
 98     if (aCurr.node.sameAs(bCurr.node)) {
 99       next = aCurr;
100       aCurr = aCurr.next;
101       bCurr = bCurr.next;
102     } else {
103       var compareResult = xrx.node.compareOrder(
104           /** @type {!Node} */ (aCurr.node),
105           /** @type {!Node} */ (bCurr.node));
106       if (compareResult > 0) {
107         next = bCurr;
108         bCurr = bCurr.next;
109       } else {
110         next = aCurr;
111         aCurr = aCurr.next;
112       }
113     }
114     next.prev = tail;
115     if (tail) {
116       tail.next = next;
117     } else {
118       merged.first_ = next;
119     }
120     tail = next;
121     length++;
122   }
123   next = aCurr || bCurr;
124   while (next) {
125     next.prev = tail;
126     tail.next = next;
127     tail = next;
128     length++;
129     next = next.next;
130   }
131   merged.last_ = tail;
132   merged.length_ = length;
133   return merged;
134 };
135 
136 
137 /**
138  * Prepends a node to this node-set.
139  *
140  * @param {!xrx.node} node The node to be added.
141  */
142 xrx.xpath.NodeSet.prototype.unshift = function(node) {
143   var entry = new xrx.xpath.NodeSet.Entry_(node);
144   entry.next = this.first_;
145   if (!this.last_) {
146     this.first_ = this.last_ = entry;
147   } else {
148     this.first_.prev = entry;
149   }
150   this.first_ = entry;
151   this.length_++;
152 };
153 
154 
155 /**
156  * Adds a node to this node-set.
157  *
158  * @param {!xrx.node} node The node to be added.
159  */
160 xrx.xpath.NodeSet.prototype.add = function(node) {
161   var entry = new xrx.xpath.NodeSet.Entry_(node);
162   entry.prev = this.last_;
163   if (!this.first_) {
164     this.first_ = this.last_ = entry;
165   } else {
166     this.last_.next = entry;
167   }
168   this.last_ = entry;
169   this.length_++;
170 };
171 
172 
173 /**
174  * Returns the first node of the node-set.
175  *
176  * @return {?xrx.node} The first node of the nodeset
177                                      if the nodeset is non-empty;
178  *     otherwise null.
179  */
180 xrx.xpath.NodeSet.prototype.getFirst = function() {
181   var first = this.first_;
182   if (first) {
183     return first.node;
184   } else {
185     return null;
186   }
187 };
188 
189 
190 /**
191  * Return the length of this node-set.
192  *
193  * @return {number} The length of the node-set.
194  */
195 xrx.xpath.NodeSet.prototype.getLength = function() {
196   return this.length_;
197 };
198 
199 
200 /**
201  * Returns the string representation of this node-set.
202  *
203  * @return {string} The string representation of this node-set.
204  */
205 xrx.xpath.NodeSet.prototype.string = function() {
206   var node = this.getFirst();
207   return node ? xrx.node.getValueAsString(node) : '';
208 };
209 
210 
211 /**
212  * Returns the number representation of this node-set.
213  *
214  * @return {number} The number representation of this node-set.
215  */
216 xrx.xpath.NodeSet.prototype.number = function() {
217   return +this.string();
218 };
219 
220 
221 /**
222  * Returns an iterator over this nodeset. Once this iterator is made, DO NOT
223  *     add to this nodeset until the iterator is done.
224  *
225  * @param {boolean=} opt_reverse Whether to iterate right to left or vice versa.
226  * @return {!xrx.xpath.NodeSet.Iterator} An iterator over the nodes.
227  */
228 xrx.xpath.NodeSet.prototype.iterator = function(opt_reverse) {
229   return new xrx.xpath.NodeSet.Iterator(this, !!opt_reverse);
230 };
231 
232 
233 
234 /**
235  * An iterator over the nodes of this nodeset.
236  *
237  * @param {!xrx.xpath.NodeSet} nodeset The nodeset to be iterated over.
238  * @param {boolean} reverse Whether to iterate in ascending or descending
239  *     order.
240  * @constructor
241  */
242 xrx.xpath.NodeSet.Iterator = function(nodeset, reverse) {
243   // In violation of standard Closure practice, we initialize properties to
244   // immutable constants in the constructor instead of on the prototype,
245   // because we have empirically measured better performance by doing so.
246 
247   /**
248    * @type {!xrx.xpath.NodeSet}
249    * @private
250    */
251   this.nodeset_ = nodeset;
252 
253   /**
254    * @type {boolean}
255    * @private
256    */
257   this.reverse_ = reverse;
258 
259   /**
260    * @type {xrx.xpath.NodeSet.Entry_}
261    * @private
262    */
263   this.current_ = reverse ? nodeset.last_ : nodeset.first_;
264 
265   /**
266    * @type {xrx.xpath.NodeSet.Entry_}
267    * @private
268    */
269   this.lastReturned_ = null;
270 };
271 
272 
273 /**
274  * Returns the next value of the iteration or null if passes the end.
275  *
276  * @return {?xrx.node} The next node from this iterator.
277  */
278 xrx.xpath.NodeSet.Iterator.prototype.next = function() {
279   var current = this.current_;
280   if (current == null) {
281     return null;
282   } else {
283     var lastReturned = this.lastReturned_ = current;
284     if (this.reverse_) {
285       this.current_ = current.prev;
286     } else {
287       this.current_ = current.next;
288     }
289     return lastReturned.node;
290   }
291 };
292 
293 
294 /**
295  * Deletes the last node that was returned from this iterator.
296  */
297 xrx.xpath.NodeSet.Iterator.prototype.remove = function() {
298   var nodeset = this.nodeset_;
299   var entry = this.lastReturned_;
300   if (!entry) {
301     throw Error('Next must be called at least once before remove.');
302   }
303   var prev = entry.prev;
304   var next = entry.next;
305 
306   // Modify the pointers of prev and next
307   if (prev) {
308     prev.next = next;
309   } else {
310     // If there was no prev node entry must've been first_, so update first_.
311     nodeset.first_ = next;
312   }
313   if (next) {
314     next.prev = prev;
315   } else {
316     // If there was no prev node entry must've been last_, so update last_.
317     nodeset.last_ = prev;
318   }
319   nodeset.length_--;
320   this.lastReturned_ = null;
321 };
322