fuzzy_group_by

fuzzy_group_by.py

def fuzzy_group_by(keys, items, key, dist=None):
  """Returns a dictionary with all items mapped to dates

     keys: list of items that can be used as keys in dict
     items: items which will be mapped to a key
     key: a function computing a key value for each element in items
     dist: returns distance between objects (default: lambda x, y: abs(x - y))
  """
  if not dist:
    dist = lambda x, y: abs(x - y)

  keys = sorted(keys)
  groups = dict((d, []) for d in keys)

  for item in items:
    k = key(item)

    i = bisect(keys, k)
    if not i == len(keys) and (i == 0 or dist(keys[i], k) < dist(keys[i - 1], k)):
      d = keys[i]
    else:
      d = keys[i-1]
    groups[d].append(item)

  return groups