/trunk/api/js/dojo/src/collections/SortedList.js |
---|
New file |
0,0 → 1,169 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.SortedList"); |
dojo.require("dojo.collections.Collections"); |
dojo.collections.SortedList = function (dictionary) { |
var _this = this; |
var items = {}; |
var q = []; |
var sorter = function (a, b) { |
if (a.key > b.key) { |
return 1; |
} |
if (a.key < b.key) { |
return -1; |
} |
return 0; |
}; |
var build = function () { |
q = []; |
var e = _this.getIterator(); |
while (!e.atEnd()) { |
q.push(e.get()); |
} |
q.sort(sorter); |
}; |
var testObject = {}; |
this.count = q.length; |
this.add = function (k, v) { |
if (!items[k]) { |
items[k] = new dojo.collections.DictionaryEntry(k, v); |
this.count = q.push(items[k]); |
q.sort(sorter); |
} |
}; |
this.clear = function () { |
items = {}; |
q = []; |
this.count = q.length; |
}; |
this.clone = function () { |
return new dojo.collections.SortedList(this); |
}; |
this.contains = this.containsKey = function (k) { |
if (testObject[k]) { |
return false; |
} |
return (items[k] != null); |
}; |
this.containsValue = function (o) { |
var e = this.getIterator(); |
while (!e.atEnd()) { |
var item = e.get(); |
if (item.value == o) { |
return true; |
} |
} |
return false; |
}; |
this.copyTo = function (arr, i) { |
var e = this.getIterator(); |
var idx = i; |
while (!e.atEnd()) { |
arr.splice(idx, 0, e.get()); |
idx++; |
} |
}; |
this.entry = function (k) { |
return items[k]; |
}; |
this.forEach = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.forEach) { |
Array.forEach(q, fn, s); |
} else { |
for (var i = 0; i < q.length; i++) { |
fn.call(s, q[i], i, q); |
} |
} |
}; |
this.getByIndex = function (i) { |
return q[i].valueOf(); |
}; |
this.getIterator = function () { |
return new dojo.collections.DictionaryIterator(items); |
}; |
this.getKey = function (i) { |
return q[i].key; |
}; |
this.getKeyList = function () { |
var arr = []; |
var e = this.getIterator(); |
while (!e.atEnd()) { |
arr.push(e.get().key); |
} |
return arr; |
}; |
this.getValueList = function () { |
var arr = []; |
var e = this.getIterator(); |
while (!e.atEnd()) { |
arr.push(e.get().value); |
} |
return arr; |
}; |
this.indexOfKey = function (k) { |
for (var i = 0; i < q.length; i++) { |
if (q[i].key == k) { |
return i; |
} |
} |
return -1; |
}; |
this.indexOfValue = function (o) { |
for (var i = 0; i < q.length; i++) { |
if (q[i].value == o) { |
return i; |
} |
} |
return -1; |
}; |
this.item = function (k) { |
if (k in items && !testObject[k]) { |
return items[k].valueOf(); |
} |
return undefined; |
}; |
this.remove = function (k) { |
delete items[k]; |
build(); |
this.count = q.length; |
}; |
this.removeAt = function (i) { |
delete items[q[i].key]; |
build(); |
this.count = q.length; |
}; |
this.replace = function (k, v) { |
if (!items[k]) { |
this.add(k, v); |
return false; |
} else { |
items[k] = new dojo.collections.DictionaryEntry(k, v); |
q.sort(sorter); |
return true; |
} |
}; |
this.setByIndex = function (i, o) { |
items[q[i].key].value = o; |
build(); |
this.count = q.length; |
}; |
if (dictionary) { |
var e = dictionary.getIterator(); |
while (!e.atEnd()) { |
var item = e.get(); |
q[q.length] = items[item.key] = new dojo.collections.DictionaryEntry(item.key, item.value); |
} |
q.sort(sorter); |
} |
}; |
/trunk/api/js/dojo/src/collections/Store.js |
---|
New file |
0,0 → 1,291 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.Store"); |
dojo.require("dojo.lang.common"); |
dojo.collections.Store = function (jsonArray) { |
var data = []; |
var items = {}; |
this.keyField = "Id"; |
this.get = function () { |
return data; |
}; |
this.getByKey = function (key) { |
return items[key]; |
}; |
this.getByIndex = function (idx) { |
return data[idx]; |
}; |
this.getIndexOf = function (key) { |
for (var i = 0; i < data.length; i++) { |
if (data[i].key == key) { |
return i; |
} |
} |
return -1; |
}; |
this.getData = function () { |
var arr = []; |
for (var i = 0; i < data.length; i++) { |
arr.push(data[i].src); |
} |
return arr; |
}; |
this.getDataByKey = function (key) { |
if (items[key] != null) { |
return items[key].src; |
} |
return null; |
}; |
this.getIndexOfData = function (obj) { |
for (var i = 0; i < data.length; i++) { |
if (data[i].src == obj) { |
return i; |
} |
} |
return -1; |
}; |
this.getDataByIndex = function (idx) { |
if (data[idx]) { |
return data[idx].src; |
} |
return null; |
}; |
this.update = function (obj, fieldPath, val, bDontFire) { |
var parts = fieldPath.split("."), i = 0, o = obj, field; |
if (parts.length > 1) { |
field = parts.pop(); |
do { |
if (parts[i].indexOf("()") > -1) { |
var temp = parts[i++].split("()")[0]; |
if (!o[temp]) { |
dojo.raise("dojo.collections.Store.getField(obj, '" + field + "'): '" + temp + "' is not a property of the passed object."); |
} else { |
o = o[temp](); |
} |
} else { |
o = o[parts[i++]]; |
} |
} while (i < parts.length && o != null); |
} else { |
field = parts[0]; |
} |
obj[field] = val; |
if (!bDontFire) { |
this.onUpdateField(obj, fieldPath, val); |
} |
}; |
this.forEach = function (fn) { |
if (Array.forEach) { |
Array.forEach(data, fn, this); |
} else { |
for (var i = 0; i < data.length; i++) { |
fn.call(this, data[i]); |
} |
} |
}; |
this.forEachData = function (fn) { |
if (Array.forEach) { |
Array.forEach(this.getData(), fn, this); |
} else { |
var a = this.getData(); |
for (var i = 0; i < a.length; i++) { |
fn.call(this, a[i]); |
} |
} |
}; |
this.setData = function (arr, bDontFire) { |
data = []; |
for (var i = 0; i < arr.length; i++) { |
var o = {key:arr[i][this.keyField], src:arr[i]}; |
data.push(o); |
items[o.key] = o; |
} |
if (!bDontFire) { |
this.onSetData(); |
} |
}; |
this.clearData = function (bDontFire) { |
data = []; |
items = {}; |
if (!bDontFire) { |
this.onClearData(); |
} |
}; |
this.addData = function (obj, key, bDontFire) { |
var k = key || obj[this.keyField]; |
if (items[k] != null) { |
var o = items[k]; |
o.src = obj; |
} else { |
var o = {key:k, src:obj}; |
data.push(o); |
items[o.key] = o; |
} |
if (!bDontFire) { |
this.onAddData(o); |
} |
}; |
this.addDataRange = function (arr, bDontFire) { |
var objects = []; |
for (var i = 0; i < arr.length; i++) { |
var k = arr[i][this.keyField]; |
if (items[k] != null) { |
var o = items[k]; |
o.src = arr[i]; |
} else { |
var o = {key:k, src:arr[i]}; |
data.push(o); |
items[k] = o; |
} |
objects.push(o); |
} |
if (!bDontFire) { |
this.onAddDataRange(objects); |
} |
}; |
this.addDataByIndex = function (obj, idx, key, bDontFire) { |
var k = key || obj[this.keyField]; |
if (items[k] != null) { |
var i = this.getIndexOf(k); |
var o = data.splice(i, 1); |
o.src = obj; |
} else { |
var o = {key:k, src:obj}; |
items[k] = o; |
} |
data.splice(idx, 0, o); |
if (!bDontFire) { |
this.onAddData(o); |
} |
}; |
this.addDataRangeByIndex = function (arr, idx, bDontFire) { |
var objects = []; |
for (var i = 0; i < arr.length; i++) { |
var k = arr[i][this.keyField]; |
if (items[k] != null) { |
var j = this.getIndexOf(k); |
var o = data.splice(j, 1); |
o.src = arr[i]; |
} else { |
var o = {key:k, src:arr[i]}; |
items[k] = o; |
} |
objects.push(o); |
} |
data.splice(idx, 0, objects); |
if (!bDontFire) { |
this.onAddDataRange(objects); |
} |
}; |
this.removeData = function (obj, bDontFire) { |
var idx = -1; |
var o = null; |
for (var i = 0; i < data.length; i++) { |
if (data[i].src == obj) { |
idx = i; |
o = data[i]; |
break; |
} |
} |
if (!bDontFire) { |
this.onRemoveData(o); |
} |
if (idx > -1) { |
data.splice(idx, 1); |
delete items[o.key]; |
} |
}; |
this.removeDataRange = function (idx, range, bDontFire) { |
var ret = data.splice(idx, range); |
for (var i = 0; i < ret.length; i++) { |
delete items[ret[i].key]; |
} |
if (!bDontFire) { |
this.onRemoveDataRange(ret); |
} |
return ret; |
}; |
this.removeDataByKey = function (key, bDontFire) { |
this.removeData(this.getDataByKey(key), bDontFire); |
}; |
this.removeDataByIndex = function (idx, bDontFire) { |
this.removeData(this.getDataByIndex(idx), bDontFire); |
}; |
if (jsonArray && jsonArray.length && jsonArray[0]) { |
this.setData(jsonArray, true); |
} |
}; |
dojo.extend(dojo.collections.Store, {getField:function (obj, field) { |
var parts = field.split("."), i = 0, o = obj; |
do { |
if (parts[i].indexOf("()") > -1) { |
var temp = parts[i++].split("()")[0]; |
if (!o[temp]) { |
dojo.raise("dojo.collections.Store.getField(obj, '" + field + "'): '" + temp + "' is not a property of the passed object."); |
} else { |
o = o[temp](); |
} |
} else { |
o = o[parts[i++]]; |
} |
} while (i < parts.length && o != null); |
if (i < parts.length) { |
dojo.raise("dojo.collections.Store.getField(obj, '" + field + "'): '" + field + "' is not a property of the passed object."); |
} |
return o; |
}, getFromHtml:function (meta, body, fnMod) { |
var rows = body.rows; |
var ctor = function (row) { |
var obj = {}; |
for (var i = 0; i < meta.length; i++) { |
var o = obj; |
var data = row.cells[i].innerHTML; |
var p = meta[i].getField(); |
if (p.indexOf(".") > -1) { |
p = p.split("."); |
while (p.length > 1) { |
var pr = p.shift(); |
o[pr] = {}; |
o = o[pr]; |
} |
p = p[0]; |
} |
var type = meta[i].getType(); |
if (type == String) { |
o[p] = data; |
} else { |
if (data) { |
o[p] = new type(data); |
} else { |
o[p] = new type(); |
} |
} |
} |
return obj; |
}; |
var arr = []; |
for (var i = 0; i < rows.length; i++) { |
var o = ctor(rows[i]); |
if (fnMod) { |
fnMod(o, rows[i]); |
} |
arr.push(o); |
} |
return arr; |
}, onSetData:function () { |
}, onClearData:function () { |
}, onAddData:function (obj) { |
}, onAddDataRange:function (arr) { |
}, onRemoveData:function (obj) { |
}, onRemoveDataRange:function (arr) { |
}, onUpdateField:function (obj, field, val) { |
}}); |
/trunk/api/js/dojo/src/collections/Collections.js |
---|
New file |
0,0 → 1,90 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.Collections"); |
dojo.collections.DictionaryEntry = function (k, v) { |
this.key = k; |
this.value = v; |
this.valueOf = function () { |
return this.value; |
}; |
this.toString = function () { |
return String(this.value); |
}; |
}; |
dojo.collections.Iterator = function (arr) { |
var a = arr; |
var position = 0; |
this.element = a[position] || null; |
this.atEnd = function () { |
return (position >= a.length); |
}; |
this.get = function () { |
if (this.atEnd()) { |
return null; |
} |
this.element = a[position++]; |
return this.element; |
}; |
this.map = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.map) { |
return Array.map(a, fn, s); |
} else { |
var arr = []; |
for (var i = 0; i < a.length; i++) { |
arr.push(fn.call(s, a[i])); |
} |
return arr; |
} |
}; |
this.reset = function () { |
position = 0; |
this.element = a[position]; |
}; |
}; |
dojo.collections.DictionaryIterator = function (obj) { |
var a = []; |
var testObject = {}; |
for (var p in obj) { |
if (!testObject[p]) { |
a.push(obj[p]); |
} |
} |
var position = 0; |
this.element = a[position] || null; |
this.atEnd = function () { |
return (position >= a.length); |
}; |
this.get = function () { |
if (this.atEnd()) { |
return null; |
} |
this.element = a[position++]; |
return this.element; |
}; |
this.map = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.map) { |
return Array.map(a, fn, s); |
} else { |
var arr = []; |
for (var i = 0; i < a.length; i++) { |
arr.push(fn.call(s, a[i])); |
} |
return arr; |
} |
}; |
this.reset = function () { |
position = 0; |
this.element = a[position]; |
}; |
}; |
/trunk/api/js/dojo/src/collections/Graph.js |
---|
New file |
0,0 → 1,149 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.Graph"); |
dojo.require("dojo.collections.Collections"); |
dojo.experimental("dojo.collections.Graph"); |
dojo.collections.Graph = function (nodes) { |
function node(key, data, neighbors) { |
this.key = key; |
this.data = data; |
this.neighbors = neighbors || new adjacencyList(); |
this.addDirected = function () { |
if (arguments[0].constructor == edgeToNeighbor) { |
this.neighbors.add(arguments[0]); |
} else { |
var n = arguments[0]; |
var cost = arguments[1] || 0; |
this.neighbors.add(new edgeToNeighbor(n, cost)); |
} |
}; |
} |
function nodeList() { |
var d = new dojo.collections.Dictionary(); |
function nodelistiterator() { |
var o = []; |
var e = d.getIterator(); |
while (e.get()) { |
o[o.length] = e.element; |
} |
var position = 0; |
this.element = o[position] || null; |
this.atEnd = function () { |
return (position >= o.length); |
}; |
this.get = function () { |
if (this.atEnd()) { |
return null; |
} |
this.element = o[position++]; |
return this.element; |
}; |
this.map = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.map) { |
return Array.map(o, fn, s); |
} else { |
var arr = []; |
for (var i = 0; i < o.length; i++) { |
arr.push(fn.call(s, o[i])); |
} |
return arr; |
} |
}; |
this.reset = function () { |
position = 0; |
this.element = o[position]; |
}; |
} |
this.add = function (node) { |
d.add(node.key, node); |
}; |
this.clear = function () { |
d.clear(); |
}; |
this.containsKey = function (key) { |
return d.containsKey(key); |
}; |
this.getIterator = function () { |
return new nodelistiterator(this); |
}; |
this.item = function (key) { |
return d.item(key); |
}; |
this.remove = function (node) { |
d.remove(node.key); |
}; |
} |
function edgeToNeighbor(node, cost) { |
this.neighbor = node; |
this.cost = cost; |
} |
function adjacencyList() { |
var d = []; |
this.add = function (o) { |
d.push(o); |
}; |
this.item = function (i) { |
return d[i]; |
}; |
this.getIterator = function () { |
return new dojo.collections.Iterator([].concat(d)); |
}; |
} |
this.nodes = nodes || new nodeList(); |
this.count = this.nodes.count; |
this.clear = function () { |
this.nodes.clear(); |
this.count = 0; |
}; |
this.addNode = function () { |
var n = arguments[0]; |
if (arguments.length > 1) { |
n = new node(arguments[0], arguments[1]); |
} |
if (!this.nodes.containsKey(n.key)) { |
this.nodes.add(n); |
this.count++; |
} |
}; |
this.addDirectedEdge = function (uKey, vKey, cost) { |
var uNode, vNode; |
if (uKey.constructor != node) { |
uNode = this.nodes.item(uKey); |
vNode = this.nodes.item(vKey); |
} else { |
uNode = uKey; |
vNode = vKey; |
} |
var c = cost || 0; |
uNode.addDirected(vNode, c); |
}; |
this.addUndirectedEdge = function (uKey, vKey, cost) { |
var uNode, vNode; |
if (uKey.constructor != node) { |
uNode = this.nodes.item(uKey); |
vNode = this.nodes.item(vKey); |
} else { |
uNode = uKey; |
vNode = vKey; |
} |
var c = cost || 0; |
uNode.addDirected(vNode, c); |
vNode.addDirected(uNode, c); |
}; |
this.contains = function (n) { |
return this.nodes.containsKey(n.key); |
}; |
this.containsKey = function (k) { |
return this.nodes.containsKey(k); |
}; |
}; |
/trunk/api/js/dojo/src/collections/SkipList.js |
---|
New file |
0,0 → 1,167 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.SkipList"); |
dojo.require("dojo.collections.Collections"); |
dojo.require("dojo.experimental"); |
dojo.experimental("dojo.collections.SkipList"); |
dojo.collections.SkipList = function () { |
function node(height, val) { |
this.value = val; |
this.height = height; |
this.nodes = new nodeList(height); |
this.compare = function (val) { |
if (this.value > val) { |
return 1; |
} |
if (this.value < val) { |
return -1; |
} |
return 0; |
}; |
this.incrementHeight = function () { |
this.nodes.incrementHeight(); |
this.height++; |
}; |
this.decrementHeight = function () { |
this.nodes.decrementHeight(); |
this.height--; |
}; |
} |
function nodeList(height) { |
var arr = []; |
this.height = height; |
for (var i = 0; i < height; i++) { |
arr[i] = null; |
} |
this.item = function (i) { |
return arr[i]; |
}; |
this.incrementHeight = function () { |
this.height++; |
arr[this.height] = null; |
}; |
this.decrementHeight = function () { |
arr.splice(arr.length - 1, 1); |
this.height--; |
}; |
} |
function iterator(list) { |
this.element = list.head; |
this.atEnd = function () { |
return (this.element == null); |
}; |
this.get = function () { |
if (this.atEnd()) { |
return null; |
} |
this.element = this.element.nodes[0]; |
return this.element; |
}; |
this.reset = function () { |
this.element = list.head; |
}; |
} |
function chooseRandomHeight(max) { |
var level = 1; |
while (Math.random() < PROB && level < max) { |
level++; |
} |
return level; |
} |
var PROB = 0.5; |
var comparisons = 0; |
this.head = new node(1); |
this.count = 0; |
this.add = function (val) { |
var updates = []; |
var current = this.head; |
for (var i = this.head.height; i >= 0; i--) { |
if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) { |
comparisons++; |
} |
while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) { |
current = current.nodes[i]; |
comparisons++; |
} |
updates[i] = current; |
} |
if (current.nodes[0] != null && current.nodes[0].compare(val) == 0) { |
return; |
} |
var n = new node(val, chooseRandomHeight(this.head.height + 1)); |
this.count++; |
if (n.height > this.head.height) { |
this.head.incrementHeight(); |
this.head.nodes[this.head.height - 1] = n; |
} |
for (i = 0; i < n.height; i++) { |
if (i < updates.length) { |
n.nodes[i] = updates[i].nodes[i]; |
updates[i].nodes[i] = n; |
} |
} |
}; |
this.contains = function (val) { |
var current = this.head; |
var i; |
for (i = this.head.height - 1; i >= 0; i--) { |
while (current.item(i) != null) { |
comparisons++; |
var result = current.nodes[i].compare(val); |
if (result == 0) { |
return true; |
} else { |
if (result < 0) { |
current = current.nodes[i]; |
} else { |
break; |
} |
} |
} |
} |
return false; |
}; |
this.getIterator = function () { |
return new iterator(this); |
}; |
this.remove = function (val) { |
var updates = []; |
var current = this.head; |
for (var i = this.head.height - 1; i >= 0; i--) { |
if (!(current.nodes[i] != null && current.nodes[i].compare(val) < 0)) { |
comparisons++; |
} |
while (current.nodes[i] != null && current.nodes[i].compare(val) < 0) { |
current = current.nodes[i]; |
comparisons++; |
} |
updates[i] = current; |
} |
current = current.nodes[0]; |
if (current != null && current.compare(val) == 0) { |
this.count--; |
for (var i = 0; i < this.head.height; i++) { |
if (updates[i].nodes[i] != current) { |
break; |
} else { |
updates[i].nodes[i] = current.nodes[i]; |
} |
} |
if (this.head.nodes[this.head.height - 1] == null) { |
this.head.decrementHeight(); |
} |
} |
}; |
this.resetComparisons = function () { |
comparisons = 0; |
}; |
}; |
/trunk/api/js/dojo/src/collections/BinaryTree.js |
---|
New file |
0,0 → 1,255 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.BinaryTree"); |
dojo.require("dojo.collections.Collections"); |
dojo.require("dojo.experimental"); |
dojo.experimental("dojo.collections.BinaryTree"); |
dojo.collections.BinaryTree = function (data) { |
function node(data, rnode, lnode) { |
this.value = data || null; |
this.right = rnode || null; |
this.left = lnode || null; |
this.clone = function () { |
var c = new node(); |
if (this.value.value) { |
c.value = this.value.clone(); |
} else { |
c.value = this.value; |
} |
if (this.left) { |
c.left = this.left.clone(); |
} |
if (this.right) { |
c.right = this.right.clone(); |
} |
}; |
this.compare = function (n) { |
if (this.value > n.value) { |
return 1; |
} |
if (this.value < n.value) { |
return -1; |
} |
return 0; |
}; |
this.compareData = function (d) { |
if (this.value > d) { |
return 1; |
} |
if (this.value < d) { |
return -1; |
} |
return 0; |
}; |
} |
function inorderTraversalBuildup(current, a) { |
if (current) { |
inorderTraversalBuildup(current.left, a); |
a.add(current); |
inorderTraversalBuildup(current.right, a); |
} |
} |
function preorderTraversal(current, sep) { |
var s = ""; |
if (current) { |
s = current.value.toString() + sep; |
s += preorderTraversal(current.left, sep); |
s += preorderTraversal(current.right, sep); |
} |
return s; |
} |
function inorderTraversal(current, sep) { |
var s = ""; |
if (current) { |
s = inorderTraversal(current.left, sep); |
s += current.value.toString() + sep; |
s += inorderTraversal(current.right, sep); |
} |
return s; |
} |
function postorderTraversal(current, sep) { |
var s = ""; |
if (current) { |
s = postorderTraversal(current.left, sep); |
s += postorderTraversal(current.right, sep); |
s += current.value.toString() + sep; |
} |
return s; |
} |
function searchHelper(current, data) { |
if (!current) { |
return null; |
} |
var i = current.compareData(data); |
if (i == 0) { |
return current; |
} |
if (i > 0) { |
return searchHelper(current.left, data); |
} else { |
return searchHelper(current.right, data); |
} |
} |
this.add = function (data) { |
var n = new node(data); |
var i; |
var current = root; |
var parent = null; |
while (current) { |
i = current.compare(n); |
if (i == 0) { |
return; |
} |
parent = current; |
if (i > 0) { |
current = current.left; |
} else { |
current = current.right; |
} |
} |
this.count++; |
if (!parent) { |
root = n; |
} else { |
i = parent.compare(n); |
if (i > 0) { |
parent.left = n; |
} else { |
parent.right = n; |
} |
} |
}; |
this.clear = function () { |
root = null; |
this.count = 0; |
}; |
this.clone = function () { |
var c = new dojo.collections.BinaryTree(); |
c.root = root.clone(); |
c.count = this.count; |
return c; |
}; |
this.contains = function (data) { |
return this.search(data) != null; |
}; |
this.deleteData = function (data) { |
var current = root; |
var parent = null; |
var i = current.compareData(data); |
while (i != 0 && current != null) { |
if (i > 0) { |
parent = current; |
current = current.left; |
} else { |
if (i < 0) { |
parent = current; |
current = current.right; |
} |
} |
i = current.compareData(data); |
} |
if (!current) { |
return; |
} |
this.count--; |
if (!current.right) { |
if (!parent) { |
root = current.left; |
} else { |
i = parent.compare(current); |
if (i > 0) { |
parent.left = current.left; |
} else { |
if (i < 0) { |
parent.right = current.left; |
} |
} |
} |
} else { |
if (!current.right.left) { |
if (!parent) { |
root = current.right; |
} else { |
i = parent.compare(current); |
if (i > 0) { |
parent.left = current.right; |
} else { |
if (i < 0) { |
parent.right = current.right; |
} |
} |
} |
} else { |
var leftmost = current.right.left; |
var lmParent = current.right; |
while (leftmost.left != null) { |
lmParent = leftmost; |
leftmost = leftmost.left; |
} |
lmParent.left = leftmost.right; |
leftmost.left = current.left; |
leftmost.right = current.right; |
if (!parent) { |
root = leftmost; |
} else { |
i = parent.compare(current); |
if (i > 0) { |
parent.left = leftmost; |
} else { |
if (i < 0) { |
parent.right = leftmost; |
} |
} |
} |
} |
} |
}; |
this.getIterator = function () { |
var a = []; |
inorderTraversalBuildup(root, a); |
return new dojo.collections.Iterator(a); |
}; |
this.search = function (data) { |
return searchHelper(root, data); |
}; |
this.toString = function (order, sep) { |
if (!order) { |
var order = dojo.collections.BinaryTree.TraversalMethods.Inorder; |
} |
if (!sep) { |
var sep = " "; |
} |
var s = ""; |
switch (order) { |
case dojo.collections.BinaryTree.TraversalMethods.Preorder: |
s = preorderTraversal(root, sep); |
break; |
case dojo.collections.BinaryTree.TraversalMethods.Inorder: |
s = inorderTraversal(root, sep); |
break; |
case dojo.collections.BinaryTree.TraversalMethods.Postorder: |
s = postorderTraversal(root, sep); |
break; |
} |
if (s.length == 0) { |
return ""; |
} else { |
return s.substring(0, s.length - sep.length); |
} |
}; |
this.count = 0; |
var root = this.root = null; |
if (data) { |
this.add(data); |
} |
}; |
dojo.collections.BinaryTree.TraversalMethods = {Preorder:1, Inorder:2, Postorder:3}; |
/trunk/api/js/dojo/src/collections/Queue.js |
---|
New file |
0,0 → 1,65 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.Queue"); |
dojo.require("dojo.collections.Collections"); |
dojo.collections.Queue = function (arr) { |
var q = []; |
if (arr) { |
q = q.concat(arr); |
} |
this.count = q.length; |
this.clear = function () { |
q = []; |
this.count = q.length; |
}; |
this.clone = function () { |
return new dojo.collections.Queue(q); |
}; |
this.contains = function (o) { |
for (var i = 0; i < q.length; i++) { |
if (q[i] == o) { |
return true; |
} |
} |
return false; |
}; |
this.copyTo = function (arr, i) { |
arr.splice(i, 0, q); |
}; |
this.dequeue = function () { |
var r = q.shift(); |
this.count = q.length; |
return r; |
}; |
this.enqueue = function (o) { |
this.count = q.push(o); |
}; |
this.forEach = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.forEach) { |
Array.forEach(q, fn, s); |
} else { |
for (var i = 0; i < q.length; i++) { |
fn.call(s, q[i], i, q); |
} |
} |
}; |
this.getIterator = function () { |
return new dojo.collections.Iterator(q); |
}; |
this.peek = function () { |
return q[0]; |
}; |
this.toArray = function () { |
return [].concat(q); |
}; |
}; |
/trunk/api/js/dojo/src/collections/Dictionary.js |
---|
New file |
0,0 → 1,99 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.Dictionary"); |
dojo.require("dojo.collections.Collections"); |
dojo.collections.Dictionary = function (dictionary) { |
var items = {}; |
this.count = 0; |
var testObject = {}; |
this.add = function (k, v) { |
var b = (k in items); |
items[k] = new dojo.collections.DictionaryEntry(k, v); |
if (!b) { |
this.count++; |
} |
}; |
this.clear = function () { |
items = {}; |
this.count = 0; |
}; |
this.clone = function () { |
return new dojo.collections.Dictionary(this); |
}; |
this.contains = this.containsKey = function (k) { |
if (testObject[k]) { |
return false; |
} |
return (items[k] != null); |
}; |
this.containsValue = function (v) { |
var e = this.getIterator(); |
while (e.get()) { |
if (e.element.value == v) { |
return true; |
} |
} |
return false; |
}; |
this.entry = function (k) { |
return items[k]; |
}; |
this.forEach = function (fn, scope) { |
var a = []; |
for (var p in items) { |
if (!testObject[p]) { |
a.push(items[p]); |
} |
} |
var s = scope || dj_global; |
if (Array.forEach) { |
Array.forEach(a, fn, s); |
} else { |
for (var i = 0; i < a.length; i++) { |
fn.call(s, a[i], i, a); |
} |
} |
}; |
this.getKeyList = function () { |
return (this.getIterator()).map(function (entry) { |
return entry.key; |
}); |
}; |
this.getValueList = function () { |
return (this.getIterator()).map(function (entry) { |
return entry.value; |
}); |
}; |
this.item = function (k) { |
if (k in items) { |
return items[k].valueOf(); |
} |
return undefined; |
}; |
this.getIterator = function () { |
return new dojo.collections.DictionaryIterator(items); |
}; |
this.remove = function (k) { |
if (k in items && !testObject[k]) { |
delete items[k]; |
this.count--; |
return true; |
} |
return false; |
}; |
if (dictionary) { |
var e = dictionary.getIterator(); |
while (e.get()) { |
this.add(e.element.key, e.element.value); |
} |
} |
}; |
/trunk/api/js/dojo/src/collections/Stack.js |
---|
New file |
0,0 → 1,65 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.Stack"); |
dojo.require("dojo.collections.Collections"); |
dojo.collections.Stack = function (arr) { |
var q = []; |
if (arr) { |
q = q.concat(arr); |
} |
this.count = q.length; |
this.clear = function () { |
q = []; |
this.count = q.length; |
}; |
this.clone = function () { |
return new dojo.collections.Stack(q); |
}; |
this.contains = function (o) { |
for (var i = 0; i < q.length; i++) { |
if (q[i] == o) { |
return true; |
} |
} |
return false; |
}; |
this.copyTo = function (arr, i) { |
arr.splice(i, 0, q); |
}; |
this.forEach = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.forEach) { |
Array.forEach(q, fn, s); |
} else { |
for (var i = 0; i < q.length; i++) { |
fn.call(s, q[i], i, q); |
} |
} |
}; |
this.getIterator = function () { |
return new dojo.collections.Iterator(q); |
}; |
this.peek = function () { |
return q[(q.length - 1)]; |
}; |
this.pop = function () { |
var r = q.pop(); |
this.count = q.length; |
return r; |
}; |
this.push = function (o) { |
this.count = q.push(o); |
}; |
this.toArray = function () { |
return [].concat(q); |
}; |
}; |
/trunk/api/js/dojo/src/collections/__package__.js |
---|
New file |
0,0 → 1,13 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.kwCompoundRequire({common:["dojo.collections.Collections", "dojo.collections.SortedList", "dojo.collections.Dictionary", "dojo.collections.Queue", "dojo.collections.ArrayList", "dojo.collections.Stack", "dojo.collections.Set"]}); |
dojo.provide("dojo.collections.*"); |
/trunk/api/js/dojo/src/collections/ArrayList.js |
---|
New file |
0,0 → 1,112 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.ArrayList"); |
dojo.require("dojo.collections.Collections"); |
dojo.collections.ArrayList = function (arr) { |
var items = []; |
if (arr) { |
items = items.concat(arr); |
} |
this.count = items.length; |
this.add = function (obj) { |
items.push(obj); |
this.count = items.length; |
}; |
this.addRange = function (a) { |
if (a.getIterator) { |
var e = a.getIterator(); |
while (!e.atEnd()) { |
this.add(e.get()); |
} |
this.count = items.length; |
} else { |
for (var i = 0; i < a.length; i++) { |
items.push(a[i]); |
} |
this.count = items.length; |
} |
}; |
this.clear = function () { |
items.splice(0, items.length); |
this.count = 0; |
}; |
this.clone = function () { |
return new dojo.collections.ArrayList(items); |
}; |
this.contains = function (obj) { |
for (var i = 0; i < items.length; i++) { |
if (items[i] == obj) { |
return true; |
} |
} |
return false; |
}; |
this.forEach = function (fn, scope) { |
var s = scope || dj_global; |
if (Array.forEach) { |
Array.forEach(items, fn, s); |
} else { |
for (var i = 0; i < items.length; i++) { |
fn.call(s, items[i], i, items); |
} |
} |
}; |
this.getIterator = function () { |
return new dojo.collections.Iterator(items); |
}; |
this.indexOf = function (obj) { |
for (var i = 0; i < items.length; i++) { |
if (items[i] == obj) { |
return i; |
} |
} |
return -1; |
}; |
this.insert = function (i, obj) { |
items.splice(i, 0, obj); |
this.count = items.length; |
}; |
this.item = function (i) { |
return items[i]; |
}; |
this.remove = function (obj) { |
var i = this.indexOf(obj); |
if (i >= 0) { |
items.splice(i, 1); |
} |
this.count = items.length; |
}; |
this.removeAt = function (i) { |
items.splice(i, 1); |
this.count = items.length; |
}; |
this.reverse = function () { |
items.reverse(); |
}; |
this.sort = function (fn) { |
if (fn) { |
items.sort(fn); |
} else { |
items.sort(); |
} |
}; |
this.setByIndex = function (i, obj) { |
items[i] = obj; |
this.count = items.length; |
}; |
this.toArray = function () { |
return [].concat(items); |
}; |
this.toString = function (delim) { |
return items.join((delim || ",")); |
}; |
}; |
/trunk/api/js/dojo/src/collections/Set.js |
---|
New file |
0,0 → 1,112 |
/* |
Copyright (c) 2004-2006, The Dojo Foundation |
All Rights Reserved. |
Licensed under the Academic Free License version 2.1 or above OR the |
modified BSD license. For more information on Dojo licensing, see: |
http://dojotoolkit.org/community/licensing.shtml |
*/ |
dojo.provide("dojo.collections.Set"); |
dojo.require("dojo.collections.Collections"); |
dojo.require("dojo.collections.ArrayList"); |
dojo.collections.Set = new function () { |
this.union = function (setA, setB) { |
if (setA.constructor == Array) { |
var setA = new dojo.collections.ArrayList(setA); |
} |
if (setB.constructor == Array) { |
var setB = new dojo.collections.ArrayList(setB); |
} |
if (!setA.toArray || !setB.toArray) { |
dojo.raise("Set operations can only be performed on array-based collections."); |
} |
var result = new dojo.collections.ArrayList(setA.toArray()); |
var e = setB.getIterator(); |
while (!e.atEnd()) { |
var item = e.get(); |
if (!result.contains(item)) { |
result.add(item); |
} |
} |
return result; |
}; |
this.intersection = function (setA, setB) { |
if (setA.constructor == Array) { |
var setA = new dojo.collections.ArrayList(setA); |
} |
if (setB.constructor == Array) { |
var setB = new dojo.collections.ArrayList(setB); |
} |
if (!setA.toArray || !setB.toArray) { |
dojo.raise("Set operations can only be performed on array-based collections."); |
} |
var result = new dojo.collections.ArrayList(); |
var e = setB.getIterator(); |
while (!e.atEnd()) { |
var item = e.get(); |
if (setA.contains(item)) { |
result.add(item); |
} |
} |
return result; |
}; |
this.difference = function (setA, setB) { |
if (setA.constructor == Array) { |
var setA = new dojo.collections.ArrayList(setA); |
} |
if (setB.constructor == Array) { |
var setB = new dojo.collections.ArrayList(setB); |
} |
if (!setA.toArray || !setB.toArray) { |
dojo.raise("Set operations can only be performed on array-based collections."); |
} |
var result = new dojo.collections.ArrayList(); |
var e = setA.getIterator(); |
while (!e.atEnd()) { |
var item = e.get(); |
if (!setB.contains(item)) { |
result.add(item); |
} |
} |
return result; |
}; |
this.isSubSet = function (setA, setB) { |
if (setA.constructor == Array) { |
var setA = new dojo.collections.ArrayList(setA); |
} |
if (setB.constructor == Array) { |
var setB = new dojo.collections.ArrayList(setB); |
} |
if (!setA.toArray || !setB.toArray) { |
dojo.raise("Set operations can only be performed on array-based collections."); |
} |
var e = setA.getIterator(); |
while (!e.atEnd()) { |
if (!setB.contains(e.get())) { |
return false; |
} |
} |
return true; |
}; |
this.isSuperSet = function (setA, setB) { |
if (setA.constructor == Array) { |
var setA = new dojo.collections.ArrayList(setA); |
} |
if (setB.constructor == Array) { |
var setB = new dojo.collections.ArrayList(setB); |
} |
if (!setA.toArray || !setB.toArray) { |
dojo.raise("Set operations can only be performed on array-based collections."); |
} |
var e = setB.getIterator(); |
while (!e.atEnd()) { |
if (!setA.contains(e.get())) { |
return false; |
} |
} |
return true; |
}; |
}(); |