import fnmatch


def _match_in_cache(cache_tree, list_of_names):
    """
    :type cache_tree: defaultdict
    :description cache_tree: a defaultdict initialized with the tree() function.  Contains names
                             of entries in the kairosdb, separated by "." per the graphite convention.

    :type list_of_names: list
    :description list_of_names: list of strings, in order, that will be sought after in the cache tree.

    :rtype: list
    :return: A list of matches, possibly empty.

    Given a cache_tree, and a prefix, returns all of the values associated with that prefix,
    that is, the keys that reside under the prefix.
    """
    head_item = list_of_names[0]
    # print "head_item is {0}".format(head_item)
    head_item_matches = [ m for m in cache_tree.keys() if fnmatch.fnmatch(m, head_item) ]
    if head_item not in cache_tree.keys():
        # print "A"
        return [] # Empty List to signify we're done here
    elif len(list_of_names) == 1:
        # print "B"
        return cache_tree[head_item].keys()
    else:
        # print "C"
        tail_list = list_of_names[1:]
        return _match_in_cache(cache_tree[head_item], tail_list)