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>