list.md

@include "au"
@include "math"
@include "meta"

list

push(lst,x) : add x to the end of lst.

function push(i,v) { i[length(i) + 1] = v }

top(lst) : return last item in lst.

function top(i)    { return i[ length(i) ] }

median(lst) : return middle number of lst (assumes it is sorted).

function median(l,    m,n,l1) {
  n = length(l)
  m = int(n/2)
  l1 = l[m+1]
  return (n % 2) ? l1 : (l[m] + l1)/2
}

bsearch(lst,goal,[approx,lt,gt]) : search lst for goal

By default, lst contains numbers but this function can handle arbitray strcures (by adjustung the lt and gt functions).

  • finds the index of goal in lst;
  • approx is a boolean. If 1 then if there is no exact match, then return the nearest item.
  • lt and gt are the less than and greater than functions that guide the binary search. They accept two arguments.
function bsearch(lst,x,approx,lt,gt,
                 lo,mid,hi,val) {
  lo = 1
  hi = length(lst)
  lt = either(lt,"lt")
  gt = either(gt,"gt")
  while (lo <= hi) {
    mid = int(lo + (hi - lo) / 2)
    val = lst[mid]
    if     (@gt(val,x)) hi = mid - 1
    else if(@lt(val,x)) lo = mid + 1  
    else return mid
  }
  return approx ? mid : error("bsearch: ["x"] not found")
}

dump(lst,prefix) : present lst in a one list string

function dump(lst,  n,s,i) {
  n = length(lst)
  s = lst[1]
  for(i = 2; i<=n; i++) s = s "," lst[i]
  return s
}

o(lst,prefix,order) : print nested lists

  • prefix is txt to show before each item;
  • order is a sorting function to order the lists, e.g. ind_num_asc for lists of numbers.
function o(l,prefix,order,
           indent,
           old,i) {
  old = PROCINFO["sorted_in"]
  prefix=either(prefix,"o ")
  if(! isarray(l)) {
    print "not array",prefix,l
    return 0}
  if(!order)
    for(i in l) {
      if (isnum(i))
        order = "@ind_num_asc"
      else
        order = "@ind_str_asc"
      break
    }
   PROCINFO["sorted_in"]= order
   for(i in l)
     if (isarray(l[i])) {
       print prefix  indent "[" i "]"
       o(l[i],prefix,order, indent ":   ")
     } else
       print prefix  indent "[" i"]  = (" l[i] ")"
   PROCINFO["sorted_in"]  = old
}