#!/bin/sh
# version 2007.09.24
# D. J. Bernstein
# Public domain.

original-awk -F: '
  BEGIN {
    nextv = 1
  }
  BEGIN {
    y[0] = 0
  }
  {
    if ($1 == "vertex") {
      if ($2 >= nextv) nextv = $2 + 1
      if ($3 == "x") {
        x[$2] = $4
      } else {
        if ($3 == "y") y[$2] = -$4
	print
      }
    } else if ($1 == "edge") {
      enum = enum + 1
      estart[enum] = $2
      eend[enum] = $3
      eflipped[enum] = $4
    } else {
      print
    }
  }
  END {
    for (v in y)
      maxtarget[v] = y[v]
    for (i = 1;i <= enum;++i) {
      if (y[eend[i]] > maxtarget[estart[i]])
        maxtarget[estart[i]] = y[eend[i]]
    }
    for (v in y) {
      from = v
      for (j = y[v] + 1;j < maxtarget[v];++j) {
	extension[v"/"j] = nextv
        print "vertex:"nextv":label:=:"
        print "vertex:"nextv":y:-"j":"
	x[nextv] = x[v]
	print "edge:"from":"nextv":0:"
	from = nextv
	nextv = nextv + 1
      }
    }
    for (i = 1;i <= enum;++i) {
      if (y[estart[i]] < y[eend[i]] - 1)
        estart[i] = extension[estart[i]"/"(y[eend[i]]-1)]
    }
    for (i = 1;i <= enum;++i) {
      print "edge:"estart[i]":"eend[i]":"eflipped[i]":"
    }
    for (v in x)
      print "vertex:"v":x:"x[v]":"
  }
'