from copy import copy

# allCombinations looks for these to know where there are multiple possibilities
class oneOf(object):
    def __init__(self, *options):
        self.options = options

# signifies that the element shouldn't be there at all. Don't add it to the list,
# the key shouldn't be there, the attribute shouldn't be there, and so forth.
class leaveOut():
    pass

# needed (I think) for handling dicts; we walk the object many times, so we have to make sure
# that we visit the keys in the same order. There's no guarantee of dict key order in Python
# perhaps there's a guarantee that it'll be the same order per run of the program, but I'm not
# banking on that

def order_by_hash(a, b):
    h_a = hash(a)
    h_b = hash(b)
    # for some reason at some points hash(a) - hash(b) always returns 0, but not if you set to variables first.
    # also in some cases, the sort function complains that we're returning longs, so we're just going to return -1 or 1
    if h_a > h_b:
        return 1
    else:
        return -1

# take a list of lists of possibilities for each slot, and returns the list of all possible
# combinations. Sortof hard to explain, here's an example:
#
# combo_helper( [[1, 2], [5, 6], ["a", "b"]] )
# returns
# [ [1,5, "a"], [1,5, "b"], [1,6, "a"], [1,6, "b"], [2,5, "a"], [2,5, "b"], [2,6, "a"], [2,6, "b"] ]

def _combo_helper(lst):
    if len(lst) == 1:
        all_combos = [[x] for x in lst[0]]
    else:
        lower_combos = _combo_helper(lst[1:])
        all_combos = []
        for x in lst[0]:
            all_combos += [ [x] + combo for combo in lower_combos ]
    return all_combos


# Here's the main function

def allCombinations(struct):

    def walkWith(struct, replace, action):
        if isinstance(struct, oneOf):
            return action(struct, replace)
        elif isinstance(struct, list):
            newlist = []
            for item in struct:
                newitem, replace = walkWith(item, replace, action)
                if newitem != leaveOut:
                    newlist.append(newitem)
            return newlist, replace
        elif isinstance(struct, tuple):
            newlist = [] # using a list because a tuple can't change size
            for item in struct:
                newitem, replace = walkWith(item, replace, action)
                if newitem != leaveOut:
                    newlist.append(newitem)
            return tuple(newlist), replace
        elif isinstance(struct, dict):
            newdict = {}
            sorted_keys = sorted(struct.keys(), order_by_hash) # ensuring the same order every time
            for key in sorted_keys:
                newval, replace = walkWith(struct[key], replace, action)
                if newval != leaveOut:
                    newdict[key] = newval
            return newdict, replace
        elif hasattr(struct, "__dict__"):
            new_struct = copy(struct)
            new_struct.__dict__, replace = walkWith(struct.__dict__, replace, action)
            return new_struct, replace
        else:
            return struct, replace

    def getReplacements(struct, replace):
        replace.append(struct.options)
        return None, replace

    def copyStruct(struct, replace):
        return replace[0], replace[1:]

    _, allreplacements = walkWith(struct, [], getReplacements)
    if allreplacements == []:
        return [struct]
    return [walkWith(struct, replacement, copyStruct)[0] for replacement in _combo_helper(allreplacements)]


def test1():
    class A():
        def __repr__(self):
            return "A(" + self.__dict__.__repr__() + ")"

    a = A()
    a.x = oneOf(1, leaveOut)
    print allCombinations({5:a, 7:oneOf(2, leaveOut)})



def test2():
    print allCombinations({5:"a", 7:2})

def test3():
    print allCombinations([1, oneOf() ])