sed2d.py

#!/usr/bin/python
from argparse import ArgumentParser
import re
from sys import stdin

RE_META = re.compile(r'#')
RE_POSITION = re.compile(r'#P[\t\040]+([-0-9]+)[\t\040]+([-0-9]+)')

def parse_pattern(file):
  x0, y0 = 0, 0

  pattern = dict()

  for line in file:
    line = line.rstrip()
    if RE_META.match(line):
      match = RE_POSITION.match(line)
      if match:
        x0, y0 = int(match.group(1)), int(match.group(2))
      continue

    for c, x in zip(line, range(0, len(line))):
      if c == ' ':
        continue
      pattern[x0 + x, y0] = c

    y0 += 1

  return pattern

def get_pattern_bounding_box(pattern):
  coords = pattern.keys()
  xmin, ymin, xmax, ymax = coords[0] * 2
  for x, y in coords:
    if x < xmin:
      xmin = x
    elif x > xmax:
      xmax = x
    if y < ymin:
      ymin = y
    elif y > ymax:
      ymax = y

  return xmin, ymin, xmax, ymax

def linearize_pattern(pattern):
  xmin, ymin, xmax, ymax = get_pattern_bounding_box(pattern)

  result = [ [ '.' for _ in range(xmax - xmin + 1) ] for _ in range(ymax - ymin + 1) ]
  for (x, y), c in pattern.iteritems():
    result[y - ymin][x - xmin] = c
  return '!'.join(''.join(line).rstrip('.') for line in result) + '!'

def replace_subpattern(needle, replacement, haystack, g):
  pivot = None
  for (x, y), c in needle.iteritems():
    if c != '.':
      pivot = x, y
      break

  if not pivot:
    return None

  haystack = { (x, y): c for (x, y), c in haystack.iteritems() if c != '.' }
  if not haystack:
    return None

  matches = []
  for x, y in haystack.keys():
    failed = False

    for (i, j), c in needle.iteritems():
      p, q = x+i-pivot[0], y+j-pivot[1]
      if c == '.':
        if (p, q) in haystack:
          failed = True
          break
      elif haystack.get((p, q)) != c:
        failed = True
        break

    if failed:
      continue

    matches.append((x, y))
    if not g:
      break

  if not matches:
    return haystack

  result = dict(haystack)
  for (x, y) in matches:
    for (i, j), c in replacement.iteritems():
      p, q = x+i-pivot[0], y+j-pivot[1]
      if replacement[i, j] == '.':
        result.pop((p, q), None)
      else:
        result[p, q] = replacement[i, j]

  return result

parser = ArgumentParser(description='Two-dimensional match/replace.')
parser.add_argument('matchfile', help='pattern to match')
parser.add_argument('substfile', help='substitution pattern')
parser.add_argument('-F', type=int, default=0, metavar='field', help='field to modify (default=0)')
parser.add_argument('-g', action='store_true', help='replace all occurrences')
args = parser.parse_args()

needle_file = open(args.matchfile, 'r')
needle = parse_pattern(needle_file)
needle_file.close()

replacement_file = open(args.substfile, 'r')
replacement = parse_pattern(replacement_file)
replacement_file.close()

for line in stdin:
  meta = line.rstrip().split(' ')
  pattern = meta.pop(args.F)
  result = replace_subpattern(needle, replacement, parse_pattern(pattern.split('!')), args.g)
  if result:
    meta.insert(args.F, linearize_pattern(result))
    print ' '.join(meta)