#! /usr/bin/gawk -f
# Last edited on 2003-08-30 18:02:23 by stolfi

BEGIN {
  usage = ( ARGV[0] " \\\n" \
    "  [ -v xbase=NNNN ] [ -v ybase=NNNN ] \\\n" \
    "  [ -v maxstep=NNN ] \\\n" \
    "  < INFILE.dat > OUTFILE.rnt " );

  # Converts a SAGRE road network file (road centerlines only) 
  # to a graph format.  Subtracts "xbase" and "ybase" from all 
  # vertex coordinates, and rounds them to integers.
  # Inserts new vertices as needed to ensure that 
  # no edge is longer than "maxstep". Deletes zero-degree vertices.

  abort = -1;

  # Provide defaults for parameters, and force them numeric:
  if (xbase == "") { xbase = 0; }      xbase += 0;
  if (ybase == "") { ybase = 0; }      ybase += 0;
  if (maxstep == "") { maxstep = 0; }  maxstep += 0;
  
  # Vertex tables, indexed by vertex ID:
  split("", vx);  # Vertex X-coordinate (relative, rounded).
  split("", vy);  # Vertex Y-coordinate (relative, rounded).
  split("", vin); # In-degree.
  split("", vot); # Out-degree.
  nv = 0;  # Number of vertices 
  
  # Vertex lookup table, indexed by pair (x,y);
  split("", vid); # Vertex ID number.

  # Edges:
  split("", eorg);  # ID of origin vertex.
  split("", edst);  # ID of destination vertex.
  split("", etrn);  # Transitability (0 = OK, 1 = no travel).
  ne = 0;  # Number of edges 
  
  # ID and coordinates of previous vertex on SAGRE polyline
  vprev = -1; xprev = 0; yprev = 0;
  
  # Edges from current SAGRE edge:
  split("", path);
  np = 0;
  
  # SAGRE polyline counter:
  npoly = 0;
}
  
(abort >= 0) { exit abort; }

/./ {
  gsub(/[\015\377\277]/, "", $0);
  gsub(/[,]/, " ", $0);
}

/^ *$/{ next; }

# Spacing between polylines:

/^004 A/ { printf " " > "/dev/stderr"; }
/^004 [A-D]/ { printf "%s", $2 > "/dev/stderr"; }

/^004 A/{
  # Start of new road centerline (a polyline).
  npoly++;
  x = $3; y = $4;
  vthis = find_vertex(x,y);
  if (vprev >= 0) { data_error("missing C record"); }
  if (np != 0) { data_error("missing D record"); }
  vprev = vthis; xprev = x; yprev = y;
  next;
}

/^004 B/{
  # Additional point along road centerline.
  x = $3; y = $4;
  if (vprev < 0) { data_error("B line without previous A"); }
  add_edges(x, y);
  next;
}

/^004 C/{
  # Last point of road centerline.
  x = $3; y = $4;
  if (vprev < 0) { data_error("C line without previous A"); }
  add_edges(x, y);
  vprev = -1;
  next;
}

/^004 D/{
  if (np == 0) 
    { data_warning("zero-length polyline"); 
      vprev = -1;
      next;
    }
  if (vprev >= 0)
    { data_error("missing C record"); }
  restr = $6;
  if ((restr != "0") && (restr != "1")) { data_error(("bad restricao = " restr)); }
  for (ip = 0; ip < np; ip++)
    { ie = path[i]; 
      etrn[ie] = restr;
    }
  np = 0;
  if ((npoly % 10) == 0) { printf "\n" > "/dev/stderr"; }
  next;
}

/^004 [E-L]/{
  next;
}

/^000 [A-C]/{
  next;
}

END {
  if (abort >= 0) { exit abort; }
  if (vprev >= 0) { data_error("missing C record"); }
  if (np != 0) { data_error("missing D record"); }
  if ((npoly % 10) != 0) { printf "\n" > "/dev/stderr"; }
  printf "read %d SAGRE polylines.\n", npoly > "/dev/stderr";
  remove_isolated_vertices();
  output_graph();
  printf "wrote %d vertices and %d edges.\n", nv, ne > "/dev/stderr";
}

function find_vertex(x, y,    i,id,dx,dy,d,ilo,ihi,xmin,xhi)
  {
    # Returns the ID of the vertex with coordinates (x,y).
    
    # Simplify coordinates:
    x = int(x - xbase);
    y = int(y - ybase);
    
    if ((x,y) in vid)
      { # Old vertex:
        id = vid[x,y];
        if ((x != vx[id]) || (y != vy[id])) { prog_error("inconsistent table"); }
      }
    else
      { # New vertex, assign its ID:
        id = nv;
        vx[id] = x;
        vy[id] = y;
        vid[x,y] = id;
        vin[id] = 0;
        vot[id] = 0;
        nv++;
        if ((nv % 500) == 0) { printf "[%dv]", nv > "/dev/stderr"; }
      }

    return id;
  }

function add_edges(x,y,    px,py,dx,dy,d2,ns,k,t)
{
  # Adds one or more edges from vertex "vprev" with coordinates "(xprev,yprev)"
  # to the point "(x,y)", and appends them to the current "path".
  # Also sets "vprev", "xprev", "yprev" to the last vertex.
  
  # Decide number "ns" of edges to add:
  if (maxstep > 0) 
    { dx = xprev - x; dy = yprev - y;
      d2 = dx*dx + dy*dy;
      if (d2 < maxstep * maxstep)
        { ns = 1; }
      else
        { ns = int(sqrt(d2)/maxstep + 0.5); }
    }
  else
    { ns = 1; }
  
  if (ns > 1) { printf "(%d)", ns > "/dev/stderr"; }
  xprev; yprev;
  for (k = 1; k <= ns; k++) 
    { t = k/ns;
      px = t*x + (1-t)*xprev;
      py = t*y + (1-t)*yprev;
      vthis = find_vertex(px,py);
      ie = add_edge(vprev, vthis);
      if (ie >= 0) { path[np] = ie; np++; }
      vprev = vthis;
    }
  xprev = x; yprev = y; 
}
      
function add_edge(ov,dv,    ie)
  {
    # Checks edge (ov,dv); returns its index
    # in the eorg/edst tables if new and OK, or -1 if not.
    
    if (ov == dv) 
      { data_warning(("zero-length edge = (" ov "," dv ")"));
        return -1;
      }
    for (ie = 0; ie < ne; ie++)
      { if ((ov == eorg[ie]) && (dv == edst[ie]))
          { data_warning(("parallel edge = (" ov "," dv ")"));
            return -1;
          }
        if ((dv == eorg[ie]) && (ov == edst[ie]))
          { data_warning(("antiparallel edge = (" ov "," dv ")"));
            return -1;
          }
      }
    ie = ne;
    eorg[ie] = ov;
    edst[ie] = dv;
    ne++;
    vin[dv]++;
    vot[ov]++;
    return ie;
  }
  
function remove_isolated_vertices(    id)
  { # Removes isolated vertices, relabeling the rest. 
    id = 0;
    while (id < nv) 
      { if (vin[id]+vot[id] == 0) 
          { printf "removing isolated vertex %d\n", id > "/dev/stderr"; 
            remove_vertex(id);
          }
        else
          { id++; }
      }
  }

function remove_vertex(id,    ido,ie)
  { # Removes vertex {id}, and renames the rest. Vertices {0..id-1} 
    # are not affected.
    
    # Delete any edges that reference vertex {id}: 
    ie = 0;
    while (ie < ne)
      { if ((eorg[ie] == id) || (edst[ie] == id))
          { remove_edge(ie); }
        else
          { ie++; }
      }
    # Now rename last vertex as {id}:
    ido = nv-1;
    if (id < ido)
      { # Copy attributes of vertex {ido} to vertex {id}
        vin[id] = vin[ido]; vout[id] = voud[ido];
        vx[id] = vx[ido]; vy[id] = vy[ido];
        # The vertex at that position changed name:
        vid[vx[id],vy[id]] = ido;
        # Fix edges: 
        for (ie = 0; ie < ne; ie++) 
          { if (eorg[ie] == ido) { eorg[ie] = id; }
            if (edst[ie] == ido) { edst[ie] = id; }
          }
      }
    nv--;
  }
  
function remove_edge(ie,    ieo)
  {
    # Removes edge {ie}, updates {vin,vot}, renumbers the rest.
    # Edges {0..ie-1} are not affected.
    
    # Updates {vin,vot}:
    vot[eorg[ie]]--;
    vin[edst[ie]]--;
    # Fill hole with the last edge:
    ieo = ne-1;
    if (ie < ieo)
      { eorg[ie] = eorg[ieo];
        edst[ie] = edst[ieo];
        etrn[ie] = etrn[ieo];
      }
    ne--;
  }

function output_graph(    ie,id)
  {
    printf "p street-graph %d %d\n", nv, ne;
    # Print vertices
    for (id = 0; id < nv; id++) 
      { if ((vin[id] < 0) || (vot[id] < 0))
          { map_error(("bad degrees - vertex " id " = (" vin[id] "," vot[id] ")")); }
        printf "v %5d %5d %5d %1d %1d\n", id, vx[id], vy[id], vin[id], vot[id];
      }
    
    # Print edges and costs:
    for (ie = 0; ie < ne; ie++)
      { 
        printf "a %5d %5d %d\n", eorg[ie], edst[ie], etrn[ie];
      }
  }
  
function data_warning(msg)
  {
    printf "line %d: warning - %s\n", FNR, msg > "/dev/stderr"; 
  }
  
function data_error(msg)
  {
    printf "line %d: %s\n", FNR, msg > "/dev/stderr"; 
    abort = 1;
    exit abort;
  }
  
function map_error(msg)
  {
    printf "%s\n", FNR, msg > "/dev/stderr"; 
    abort = 1;
    exit abort;
  }
  
function prog_error(msg)
  {
    printf "line %d: prog error - %s\n", FNR, msg > "/dev/stderr"; 
    abort = 1;
    exit abort;
  }