priority.m4

   1 divert(-1)dnl -*- m4 -*-
   2 # Minimum Priority Queue implementations for Dijkstra/A* searching
   3 # assumes common.m4 is already loaded
   4
   5 # Each implementation has a common interface:
   6 # insert(priority, data) queues up data with a priority 0-99999
   7 # pop() returns the lowest-such queued data, or nothing if queue is empty
   8 # clearall() reclaims all memory in the priority queue
   9
  10 # In general, implementation 5 performs best, although 2 has less overhead
  11 # if all current priorities fall in a narrow range; while 1, 3, and 4 are
  12 # more for demonstrations of other techniques
  13
  14 ifdef(`priority', `', `define(`priority', 5)')
  15 ifelse(priority, 1, `
  16 output(1, `Using O(log n) insertion priority queue')
  17
  18 define(`oops', `output(0, `error: unexpected priority $1')m4exit(1)')
  19 define(`prio', `')
  20 define(`priolen', 0)
  21 define(`insert', `ifelse(eval(len(`$1')>5), 1, `oops($1)')ifdef(`prio$1', `',
  22   `_$0(substr(`$1     ', 0, 5), locate($1, 0, priolen))')pushdef(`prio$1',
  23   `$@')')
  24 define(`_insert', `define(`prio', substr(prio, 0, $2)$1substr(prio,
  25   $2))define(`priolen', eval(priolen + 5))')
  26 define(`locate', `ifelse($2, $3, $2, `_$0($@, eval(($2 + $3) / 10 * 5))')')
  27 define(`_locate', `ifelse(eval(substr(prio, $4, 5) < $1), 1, `locate($1,
  28   eval($4 + 5), $3)', `locate($1, $2, $4)')')
  29 define(`pop', `ifelse(priolen, 0, `', `_$0(eval(substr(prio, 0, 5)))')')
  30 define(`_pop', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
  31   `define(`prio', substr(prio, 5))define(`priolen', eval(priolen - 5))')')
  32 define(`clearall', `foreach(`_$0', translit(prio, ` ', `,'))define(`priolen',
  33   0)define(`prio', `')')
  34 define(`_clearall', `ifelse($1, `', `', `undefine(`prio$1')')')
  35
  36 ', priority, 2, `
  37 output(1, `Using pushdef stack priority queue')
  38
  39 define(`insert', `ifdef(`prio$1', `', `saveto($1)restore()')pushdef(`prio$1',
  40   `$@')')
  41 define(`saveto', `ifdef(`prio', `ifelse(prio, $1, `', eval(prio < $1), 1,
  42   `pushdef(`tmp', prio)popdef(`prio')$0($1)', `pushdef(`prio', $1)')',
  43   `pushdef(`prio', $1)')')
  44 define(`restore', `ifdef(`tmp', `pushdef(`prio', tmp)popdef(`tmp')$0()')')
  45 define(`pop', `ifdef(`prio', `_$0(prio)')')
  46 define(`_pop', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
  47   `popdef(`prio')')')
  48 define(`clearall', `ifdef(`prio', `undefine(`prio'prio)popdef(`prio')$0()')')
  49
  50 ', priority, 3, `
  51 output(1, `Using unsorted list plus cache for priority queue')
  52
  53 define(`insert', `ifdef(`prio$1', `', `_$0($1)')pushdef(`prio$1', `$@')')
  54 define(`_insert', `ifdef(`prio', `define(`prio', `$1,'defn(`prio'))ifelse(
  55   ifdef(`cache', `eval($1 < cache)'), 1, `define(`cache', $1)')',
  56   `define(`prio', $1)define(`cache', $1)')')
  57 define(`pop', `ifdef(`prio', `_$0(ifdef(`cache', `',
  58   `rebuild()')defn(`cache'))')')
  59 define(`_pop', `ifelse($1, `', `', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
  60   `popdef(`cache')')')')
  61 define(`rebuild', `foreach(`_$0', prio()popdef(`prio'))')
  62 define(`_rebuild', `ifdef(`prio$1', `_insert($1)')')
  63 define(`clearall', `ifdef(`prio', `foreach(`_$0', prio())popdef(`prio')')')
  64 define(`_clearall', `undefine(`prio$1')')
  65
  66 ', priority, 4, `
  67 output(1, `Using sorted list for priority queue')
  68
  69 define(`prio')
  70 define(`insert', `ifdef(`prio$1', `', `_$0($1)')pushdef(`prio$1', `$@')')
  71 define(`_insert', `pushdef(`t', $1)define(`prio', foreach(`$0_',
  72   prio))popdef(`t')')
  73 define(`_insert_', `ifelse(t`$1', `', `', t, `', `$1`,'', $1, `', `t`,'',
  74   eval(t + 0 < $1 + 0), 1, `t`,'define(`t')$1`,'', `$1`,'')')
  75 define(`pop', `_$0(prio)')
  76 define(`_pop', `ifelse($1, `', `', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
  77   `define(`prio', quote(shift(prio)))')')')
  78 define(`clearall', `foreach(`_$0', prio)define(`prio')')
  79 define(`_clearall', `ifelse(`$1', `', `', `undefine(`prio$1')')')
  80
  81 ', priority, 5, `
  82 output(1, `Using min-heap array for priority queue')
  83
  84 define(`prlen', 0)
  85 define(`insert', `ifdef(`prio$1', `pushdef(`prio$1', `$@')', `define(`prio$1',
  86   `$@')define(`prlen', incr(prlen))define(`pr'prlen, $1)prup(prlen)')')
  87 define(`prswap', `define(`pr$2', pr$1`'define(`pr$1', pr$2))')
  88 define(`prup', `ifelse($1, 1, `', `_$0($1, eval($1/2))')')
  89 define(`_prup', `ifelse(eval(pr$1 < pr$2), 1, `prswap($1, $2)prup($2)')')
  90 define(`pop', `ifelse(prlen, 0, `', `_$0(pr1, prlen)')')
  91 define(`_pop', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `', `define(`pr1',
  92   pr$2)popdef(`pr$2')define(`prlen', decr($2))prdown(1, prlen)')')
  93 define(`prdown', `_$0_1($1, pr$1, eval(2*$1), $2)')
  94 define(`_prdown_1', `ifelse(eval($3 <= $4), 1, `_prdown_2($1, ifelse(eval(
  95   pr$3 < $2), 1, `$3, pr$3', `$1, $2'), incr($3), $4)')')
  96 define(`_prdown_2', `_prdown_3($1, ifelse(eval($4 <= $5 && defn(`pr$4')+0 < $3),
  97   1, $4, $2), $5)')
  98 define(`_prdown_3', `ifelse($1, $2, `', `prswap($1, $2)prdown($2, $3)')')
  99 define(`clearall', `ifelse(prlen, 0, `', `forloop_arg(1, prlen, `_$0')define(
 100   `prlen', 0)')')
 101 define(`_clearall', `undefine(`prio'pr$1)popdef(`pr$1')')
 102
 103 ', `output(0, `unknown priority')m4exit(1)')