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