|
Struts example source code file (SkipList.js)
The Struts SkipList.js source code/* 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; }; }; Other Struts examples (source code examples)Here is a short list of links related to this Struts SkipList.js source code file: |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.