import math


def bucketize(seq, nbuckets, key=lambda d: d):
  """
  Equiwidth bucketing
  Augments _copies_ of objects with the following keys:

    bucket_perc
    bucket_perc_str
    bucket (key value)
    lower (key val)
    upper (key val)


  @param seq a list of objects
  @param key function to compute a numerical value to define bucket sizes
  """
  vals = list(map(key, seq))
  val_range = max(vals) - min(vals)
  bucket_size = int(math.ceil(float(val_range) / nbuckets))
  ret = []
  for i in range(nbuckets):
    l, u = bucket_size * (i), bucket_size * (i+1)
    f = lambda d: key(d) >= l and key(d) < u
    if i == nbuckets - 1:
      f = lambda d: key(d) >= l and key(d) <= u
    for d in filter(f, seq):
      d = dict(d)
      d.update({
        "bucket_perc": int(100. * i / nbuckets),
        "bucket_perc_str": "%d-%d%%" % (int(100. * i / nbuckets),int(100. * (1+i) / nbuckets)),
        "bucket": i,
        "lower": l,
        "upper": u,
      })
      ret.append(d)
  return ret