#!/usr/bin/python

def fair_share(scheduables, totalCapacity):
  print "demand:%s totalCapacity:%s" % (scheduables, totalCapacity)

  totalDemand = reduce(lambda a, b: int(a) + int(b), [x['demand'] for x in scheduables])
  cap = min(totalDemand, totalCapacity)

  weightSlotRatio = 1.0

  while slots_used_with_ratio(scheduables, weightSlotRatio) < cap:
    weightSlotRatio *= 2.0

  left = 0
  right = weightSlotRatio

  for i in range(0, 25):
    mid = (left + right) / 2.0
    if slots_used_with_ratio(scheduables, mid) < cap:
      left = mid
    else:
      right = mid

  slots = slots_used_with_ratio(scheduables, right)

  for scheduable in scheduables:
    scheduable['share'] = compute_share(scheduable, right)

  print "totalDemand:%s cap:%s scheduables:%s slots:%s weightSlotRatio:%s" % (totalDemand, cap, scheduables, slots, right)

def slots_used_with_ratio(scheduables, weightSlotRatio):
  shares = [compute_share(x, weightSlotRatio) for x in scheduables]
  slots = reduce(lambda a, b: a + b, shares)

  #print "weightSlotRatio:%s shares:%s slots:%s" % (weightSlotRatio, shares, slots)

  return slots

def compute_share(scheduable, weightSlotRatio):
  share = scheduable['weight'] * weightSlotRatio
  share = max(share, scheduable['minshare'])
  share = min(share, scheduable['demand'])

  #print "scheduable:%s weightSlotRatio:%s share:%s" % (scheduable, weightSlotRatio, share)

  return share

if __name__ == '__main__':
  total = 180
  scheduables = [
    { 'demand': 30, 'minshare': 40, 'weight': 1.0 },
    { 'demand': 40, 'minshare': 0, 'weight': 1.0 },
    { 'demand': 120, 'minshare': 50, 'weight': 1.0 }
  ]

  fair_share(scheduables, total)