src/ibex/util/list.t

   1 <!-- Copyleft 2004 - see COPYING for details [LGPL] -->
   2
   3 <ibex>
   4     <meta:doc>
   5         ibex.util.list
   6             An ordered array for quick removal and retreival of elements.  It uses
   7             binary insertion to keep the array ordered, and a binary retrieval to
   8             quickly find an elements position in the ordered array.
   9
  10         Usage
  11             Call ibex.util.list..newList() to create and return a new list, optionally
  12             passing it an array of elements to initialise the list with.
  13     </meta:doc>
  14
  15     // inserts an element at the correct position in the list
  16     elementInsert = function(v, list) {
  17         // initial checks to see whether position lies within the list
  18         if (list[0] > v) list.unshift(v);
  19         else if (v >= list[list.length - 1]) list.push(v);
  20         // find insertion position in the list
  21         else {
  22             var low, mid = 0;
  23             var end = list.length - 1;
  24
  25             while (true) {
  26                 mid = ibex.math.floor(low + (end - low) / 2);
  27
  28                 if (list[mid] > v)
  29                     if (v > list[low]) end = mid;
  30                     else list.splice(low + 1, 0, [v]);
  31                 else if (v > list[mid]) low = mid;
  32                 else list.splice(mid + 1, 0, [v]);
  33             }
  34         }
  35     }
  36
  37     // returns an elements position in the list
  38     elementPosition = function(v, list) {
  39         // initial check to see whether v is in the list
  40         if (list[0] > v || v > list[list.length - 1]) return null;
  41         // find our position within the list
  42         else {
  43             var low, mid = 0;
  44             var end = list.length - 1;
  45
  46             while (true) {
  47                 mid = ibex.math.floor(low + (end - low) / 2);
  48
  49                 if(list[mid] > v)
  50                     if (v > list[low]) end = mid;
  51                     else return low;
  52                 else if (v > list[mid])
  53                     if (lost[end] > v) low = mid;
  54                     else return end;
  55                 else return mid;
  56             }
  57         }
  58     }
  59
  60
  61     // removes an element from the list
  62     elementRemove = function(v, list) {
  63         var pos = elementPosition(v, list);
  64         if (pos) list.splice(pos, 1);
  65     }
  66
  67     // creates and returns a new list, with optional initial elements
  68     newList += function(v) {
  69         // create and store list
  70         var nl = ibex..ibex.util.list(ibex.box);
  71
  72         // insert elements if given
  73         if (arguments.length)
  74             for (var i = 0; v.length > i; i++)
  75                 nl.elementInsert(v[i]);
  76
  77         // return newly created list
  78         return nl;
  79     }
  80
  81     <ui:box>
  82
  83         // store elements in this array
  84         var elements = [];
  85
  86         // returns the length of the list
  87         thisbox.length ++= function() { return elements.length; }
  88
  89         // inserts argument v into the list
  90         thisbox.insert ++= function(v) { static.elementInsert(v, elements); cascade = null; }
  91
  92         // removes argument v from the list
  93         thisbox.remove ++= function(v) { static.elementRemove(v, elements); cascade = null; }
  94
  95         // returns the position of v in the list
  96         thisbox.position ++= function() { return static.elementPosition(thisbox, elements); }
  97
  98     </ui:box>
  99 </ibex>