Ordered List now available
Charles Goodwin <[email protected]> Thu, 16 Oct 2003 16:22:40 +0100
| Newsgroups | gmane.comp.java.xwt.widgets |
|---|---|
| Organization | XWT Foundation |
| Message-ID | <[email protected]> |
I've knocked together an ordered array in xwt.util.list so that you can
have the convenience of a hash with the flexibility of an array!
<!-- Copyright 2003 Charles Goodwin
LGPL - see COPYING for details -->
<xwt>
xwt.util.list
An ordered array for quick removal and retreival of elements.
It uses
binary insertion to keep the array ordered, and a binary
retrieval to
quickly find an elements position in the ordered array.
Usage
Call xwt.static.util.list.newList() to create and return a new
list,
optionally passing it an array of elements to initialise the
list with.
<static>
// inserts an element at the correct position in the list
var elementInsert = function( v, list ) {
// initial checks to see whether position lies within the list
if ( list[0] > v ) list.unshift( v );
else if ( v >= list[list.length - 1] ) list.push( v );
// find our position within the list
else {
var low, mid = 0;
var end = list.length - 1;
while ( true ) {
mid = xwt.math.floor( low + ( end - low ) / 2 );
if ( list[mid] > v )
if ( v > list[low] ) end = mid;
else list.splice( low + 1, 0, [v] );
else if ( v > list[mid] ) low = mid;
else list.splice( mid + 1, 0, [v] );
}
}
}
// returns an elements position in the list
var elementPosition = function( v ) {
if ( list[0] > v || v > list[list.length - 1] ) return null;
else {
var low, mid = 0;
var end = list.length - 1;
while ( true ) {
mid = xwt.math.floor( low + ( end - low ) / 2 );
if( list[mid] > v )
if ( v > list[low] ) end = mid;
else return low;
else if ( v > list[mid] )
if ( lost[end] > v ) low = mid;
else return end;
else return mid;
}
}
}
// removes an element from the list
var elementRemove = function( v, list ) {
list.splice( elementPosition( v ), 1 );
}
// creates and returns a new list, with optional initial elements
var newList += function( v ) {
// create and store list
var nl = xwt.box.apply( "xwt.util.list" );
// insert elements if given
if ( arguments.length )
for ( var i = 0; v.length > i; i++ )
nl.elementInsert( v[i] );
// return newly created list
return nl;
}
</static>
<template redirect="null">
thisbox.elements = [];
thisbox.length += function() { return elements.length; }
thisbox.insert += function( v ) { static.elementInsert( v,
elements ); }
thisbox.remove += function( v ) { static.elementRemove( v,
elements ); }
thisbox.position = function( v ) { return
static.elementPosition( v ); }
</template>
</xwt>