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 #  (negative ranges would need GNU m4; implementation 1 is width-limited)
   8 # pop() returns the lowest-such queued data, or nothing if queue is empty
   9 # clearall() reclaims all memory in the priority queue
  10
  11 # Under the hood, each implementation stores nodes with the same key in
  12 # a pushdef stack `prio$1'; this means implementing a lower() interface to
  13 # move an already-queued item to a lower priority would be O(n) in the
  14 # number of items with the old priority; instead, I went with the idea that
  15 # it is easier to check after pop() whether a node was already visited at a
  16 # lower priority.  The implemenations do not guarantee whether pop() will see
  17 # LIFO or FIFO order for multiple insertions at the same priority.  The real
  18 # meat of each implementation is how the set of current distinct priorities
  19 # is stored (tradeoffs between insertion vs. retrieval efforts)
  20
  21 # In general, implementation 5 performs best, although 0 and 2 have less
  22 # overhead if all current priorities fall in a narrow range; while 1, 3,
  23 # and 4 are more for demonstrations of other techniques
  24 # (For grins, see also implementation 6 in 2023/day17.m4 that uses syscmd
  25 # for external sorting, to demonstrate why an implementation in m4 matters)
  26
  27 ifdef(`priority', `', `define(`priority', 5)')
  28 ifelse(priority, 0, `
  29 output(1, `Using radix-sorted buckets as priority queue')
  30 # O(1) insertion, worst-case O(range) pop, when searching for the next
  31 # bucket; but this approaches amortized O(1) when the range is small.
  32 # limited overhead, works well when spread of min to max is small
  33 define(`insert', `ifelse(ifdef(`prlo', `eval($1<prlo)', 1), 1, `define(`prlo',
  34   $1)')ifelse(ifdef(`prhi', `eval($1>prhi)', 1), 1, `define(`prhi',
  35   $1)')pushdef(`prio$1', `$@')')
  36 define(`pop', `ifdef(`prlo', `_$0(prlo)')')
  37 define(`_pop', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `', `ifelse($1, prhi,
  38   `popdef(`prlo')popdef(`prhi')', `define(`prlo', prfind(incr($1)))')')')
  39 define(`prfind', `ifdef(`prio$1', `$1', `$0(incr($1))')')
  40 define(`clearall', `ifdef(`prlo', `forloop(prlo, prhi, `undefine(`prio'',
  41   `)')popdef(`prlo')popdef(`prhi')')')
  42
  43 ', priority, 1, `
  44 output(1, `Using O(log n) insertion priority queue')
  45 # Binary search of list of priorities for algorithmic O(log n) insertion;
  46 # algorithmic O(1) pop; but both insertion and pop suffer from O(n) overhead
  47 # of parsing the list in full
  48
  49 define(`oops', `output(0, `error: unexpected priority $1')m4exit(1)')
  50 define(`prio', `')
  51 define(`priolen', 0)
  52 define(`insert', `ifelse(eval(len(`$1')>5), 1, `oops($1)')ifdef(`prio$1', `',
  53   `_$0(substr(`$1     ', 0, 5), locate($1, 0, priolen))')pushdef(`prio$1',
  54   `$@')')
  55 define(`_insert', `define(`prio', substr(prio, 0, $2)$1substr(prio,
  56   $2))define(`priolen', eval(priolen + 5))')
  57 define(`locate', `ifelse($2, $3, $2, `_$0($@, eval(($2 + $3) / 10 * 5))')')
  58 define(`_locate', `ifelse(eval(substr(prio, $4, 5) < $1), 1, `locate($1,
  59   eval($4 + 5), $3)', `locate($1, $2, $4)')')
  60 define(`pop', `ifelse(priolen, 0, `', `_$0(eval(substr(prio, 0, 5)))')')
  61 define(`_pop', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
  62   `define(`prio', substr(prio, 5))define(`priolen', eval(priolen - 5))')')
  63 define(`clearall', `foreach(`_$0', translit(prio, ` ', `,'))define(`priolen',
  64   0)define(`prio', `')')
  65 define(`_clearall', `ifelse($1, `', `', `undefine(`prio$1')')')
  66
  67 ', priority, 2, `
  68 output(1, `Using pushdef stack priority queue')
  69 # O(n) insertion by storing priorities in sorted order, O(1) pop
  70 # minimal overhead, works well when spread of min to max is small
  71
  72 define(`insert', `ifdef(`prio$1', `', `saveto($1)restore()')pushdef(`prio$1',
  73   `$@')')
  74 define(`saveto', `ifdef(`prio', `ifelse(prio, $1, `', eval(prio < $1), 1,
  75   `pushdef(`tmp', prio)popdef(`prio')$0($1)', `pushdef(`prio', $1)')',
  76   `pushdef(`prio', $1)')')
  77 define(`restore', `ifdef(`tmp', `pushdef(`prio', tmp)popdef(`tmp')$0()')')
  78 define(`pop', `ifdef(`prio', `_$0(prio)')')
  79 define(`_pop', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
  80   `popdef(`prio')')')
  81 define(`clearall', `ifdef(`prio', `undefine(`prio'prio)popdef(`prio')$0()')')
  82
  83 ', priority, 3, `
  84 output(1, `Using unsorted list plus cache for priority queue')
  85 # algorithmic O(1) insertion, while pop is worst-case O(n) to rebuild,
  86 # but closer to amortized O(1) the fewer times a rebuild is needed
  87
  88 define(`insert', `ifdef(`prio$1', `', `_$0($1)')pushdef(`prio$1', `$@')')
  89 define(`_insert', `ifdef(`prio', `define(`prio', `$1,'defn(`prio'))ifelse(
  90   ifdef(`cache', `eval($1 < cache)'), 1, `define(`cache', $1)')',
  91   `define(`prio', $1)define(`cache', $1)')')
  92 define(`pop', `ifdef(`prio', `_$0(ifdef(`cache', `',
  93   `rebuild()')defn(`cache'))')')
  94 define(`_pop', `ifelse($1, `', `', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
  95   `popdef(`cache')')')')
  96 define(`rebuild', `foreach(`_$0', prio()popdef(`prio'))')
  97 define(`_rebuild', `ifdef(`prio$1', `_insert($1)')')
  98 define(`clearall', `ifdef(`prio', `foreach(`_$0', prio())popdef(`prio')')')
  99 define(`_clearall', `undefine(`prio$1')')
 100
 101 ', priority, 4, `
 102 output(1, `Using sorted list for priority queue')
 103 # O(n) insertion, algorithmic O(1) pop coupled with m4 O(n) parse effects
 104
 105 define(`prio')
 106 define(`insert', `ifdef(`prio$1', `', `_$0($1)')pushdef(`prio$1', `$@')')
 107 define(`_insert', `pushdef(`t', $1)define(`prio', foreach(`$0_',
 108   prio))popdef(`t')')
 109 define(`_insert_', `ifelse(t`$1', `', `', t, `', `$1`,'', $1, `', `t`,'',
 110   eval(t + 0 < $1 + 0), 1, `t`,'define(`t')$1`,'', `$1`,'')')
 111 define(`pop', `_$0(prio)')
 112 define(`_pop', `ifelse($1, `', `', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `',
 113   `define(`prio', quote(shift(prio)))')')')
 114 define(`clearall', `foreach(`_$0', prio)define(`prio')')
 115 define(`_clearall', `ifelse(`$1', `', `', `undefine(`prio$1')')')
 116
 117 ', priority, 5, `
 118 output(1, `Using min-heap array for priority queue')
 119 # textbook min-heap priority queue, using sequential NNNN in prNNNNN to
 120 # serve as an underlying array. True O(log n) insertion, and amortized
 121 # O(1) pop, but requires more macro overhead to maintain bookkeeping
 122
 123 define(`prlen', 0)
 124 define(`insert', `ifdef(`prio$1', `pushdef(`prio$1', `$@')', `define(`prio$1',
 125   `$@')define(`prlen', incr(prlen))define(`pr'prlen, $1)prup(prlen)')')
 126 define(`prswap', `define(`pr$2', pr$1`'define(`pr$1', pr$2))')
 127 define(`prup', `ifelse($1, 1, `', `_$0($1, eval($1/2))')')
 128 define(`_prup', `ifelse(eval(pr$1 < pr$2), 1, `prswap($1, $2)prup($2)')')
 129 define(`pop', `ifelse(prlen, 0, `', `_$0(pr1, prlen)')')
 130 define(`_pop', `prio$1`'popdef(`prio$1')ifdef(`prio$1', `', `define(`pr1',
 131   pr$2)popdef(`pr$2')define(`prlen', decr($2))prdown(1, prlen)')')
 132 define(`prdown', `_$0_1($1, pr$1, eval(2*$1), $2)')
 133 define(`_prdown_1', `ifelse(eval($3 <= $4), 1, `_prdown_2($1, ifelse(eval(
 134   pr$3 < $2), 1, `$3, pr$3', `$1, $2'), incr($3), $4)')')
 135 define(`_prdown_2', `_prdown_3($1, ifelse(eval($4 <= $5 && defn(`pr$4')+0 < $3),
 136   1, $4, $2), $5)')
 137 define(`_prdown_3', `ifelse($1, $2, `', `prswap($1, $2)prdown($2, $3)')')
 138 define(`clearall', `ifelse(prlen, 0, `', `forloop_arg(1, prlen, `_$0')define(
 139   `prlen', 0)')')
 140 define(`_clearall', `undefine(`prio'pr$1)popdef(`pr$1')')
 141
 142 ', `output(0, `unknown priority')m4exit(1)')