import itertools

def flatten(x):
    """flatten(sequence) -> list

    Returns a single, flat list which contains all elements retrieved
    from the sequence and all recursively contained sub-sequences
    (iterables).

    Examples:
    >>> [1, 2, [3,4], (5,6)]
    [1, 2, [3, 4], (5, 6)]
    >>> flatten([[[1,2,3], (42,None)], [4,5], [6], 7, MyVector(8,9,10)])
    [1, 2, 3, 42, None, 4, 5, 6, 7, 8, 9, 10]

    http://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks"""

    result = []
    for el in x:
        if hasattr(el, '__iter__') and not isinstance(el, basestring):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

def populate_fk_caches(model, objects_to_populate, fields=None):
    """
    Populates caches for the given related Model in instances of objects
    which have a ForeignKey relationship to it, specified as a list of
    (object list, related attribute name list) two-tuples.

    If a list of field names is given, only the given fields will be
    looked up and related object caches will be populated with a dict of
    the specified fields. This list shouldn't include the primary key
    attribute for the related mode, as this can be determined from its
    Model's Options.

    If field names are not given, complete related objects will be
    retrieved and cached.
    """
    # Get all related object ids for the appropriate fields
    related_object_ids = []
    for objects, attrs in objects_to_populate:
        related_object_ids.append(tuple(tuple(getattr(obj, '%s_id' % attr)
                                              for attr in attrs)
                                  for obj in objects))

    # Get unique related object ids
    unique_ids = tuple(set(pk for pk in flatten(related_object_ids) if pk))

    # Retrieve related object details
    if fields is None:
        related_objects = model._default_manager.in_bulk(unique_ids)
    else:
        id_attribute = model._meta.pk.attname
        related_objects = dict((obj[id_attribute], obj)
            for obj in model._default_manager.filter(id__in=unique_ids).values(
                *itertools.chain((id_attribute,), fields)))

    # Fill related object caches
    for (objects, attrs), related_ids in itertools.izip(objects_to_populate,
                                                        related_object_ids):
        for obj, related_ids_for_obj in itertools.izip(objects,
                                                       related_ids):
            for attr, related_object in itertools.izip(attrs, (related_objects.get(pk, None)
                                                               for pk in related_ids_for_obj)):
                setattr(obj, '_%s_cache' % attr, related_object)