1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// removeSubsets
// Given an array of nodes, remove any member that is contained by another.
exports.removeSubsets = function(nodes) {
var idx = nodes.length, node, ancestor, replace;
// Check if each node (or one of its ancestors) is already contained in the
// array.
while (--idx > -1) {
node = ancestor = nodes[idx];
// Temporarily remove the node under consideration
nodes[idx] = null;
replace = true;
while (ancestor) {
if (nodes.indexOf(ancestor) > -1) {
replace = false;
nodes.splice(idx, 1);
break;
}
ancestor = ancestor.parent;
}
// If the node has been found to be unique, re-insert it.
if (replace) {
nodes[idx] = node;
}
}
return nodes;
};
// Source: http://dom.spec.whatwg.org/#dom-node-comparedocumentposition
var POSITION = {
DISCONNECTED: 1,
PRECEDING: 2,
FOLLOWING: 4,
CONTAINS: 8,
CONTAINED_BY: 16
};
// Compare the position of one node against another node in any other document.
// The return value is a bitmask with the following values:
//
// document order:
// > There is an ordering, document order, defined on all the nodes in the
// > document corresponding to the order in which the first character of the
// > XML representation of each node occurs in the XML representation of the
// > document after expansion of general entities. Thus, the document element
// > node will be the first node. Element nodes occur before their children.
// > Thus, document order orders element nodes in order of the occurrence of
// > their start-tag in the XML (after expansion of entities). The attribute
// > nodes of an element occur after the element and before its children. The
// > relative order of attribute nodes is implementation-dependent./
// Source:
// http://www.w3.org/TR/DOM-Level-3-Core/glossary.html#dt-document-order
//
// @argument {Node} nodaA The first node to use in the comparison
// @argument {Node} nodeB The second node to use in the comparison
//
// @return {Number} A bitmask describing the input nodes' relative position.
// See http://dom.spec.whatwg.org/#dom-node-comparedocumentposition for
// a description of these values.
var comparePos = exports.compareDocumentPosition = function(nodeA, nodeB) {
var aParents = [];
var bParents = [];
var current, sharedParent, siblings, aSibling, bSibling, idx;
if (nodeA === nodeB) {
return 0;
}
current = nodeA;
while (current) {
aParents.unshift(current);
current = current.parent;
}
current = nodeB;
while (current) {
bParents.unshift(current);
current = current.parent;
}
idx = 0;
while (aParents[idx] === bParents[idx]) {
idx++;
}
if (idx === 0) {
return POSITION.DISCONNECTED;
}
sharedParent = aParents[idx - 1];
siblings = sharedParent.children;
aSibling = aParents[idx];
bSibling = bParents[idx];
if (siblings.indexOf(aSibling) > siblings.indexOf(bSibling)) {
if (sharedParent === nodeB) {
return POSITION.FOLLOWING | POSITION.CONTAINED_BY;
}
return POSITION.FOLLOWING;
} else {
if (sharedParent === nodeA) {
return POSITION.PRECEDING | POSITION.CONTAINS;
}
return POSITION.PRECEDING;
}
};
// Sort an array of nodes based on their relative position in the document and
// remove any duplicate nodes. If the array contains nodes that do not belong
// to the same document, sort order is unspecified.
//
// @argument {Array} nodes Array of DOM nodes
//
// @returns {Array} collection of unique nodes, sorted in document order
exports.uniqueSort = function(nodes) {
var idx = nodes.length, node, position;
nodes = nodes.slice();
while (--idx > -1) {
node = nodes[idx];
position = nodes.indexOf(node);
if (position > -1 && position < idx) {
nodes.splice(idx, 1);
}
}
nodes.sort(function(a, b) {
var relative = comparePos(a, b);
if (relative & POSITION.PRECEDING) {
return -1;
} else if (relative & POSITION.FOLLOWING) {
return 1;
}
return 0;
});
return nodes;
};
|
