# Name: Alice Liang
# EID: axl84
# Unique Section Number: 84825
# Assignment: #9
# Date: 7/12/20

# Input: box_list is a list of boxes that have already been sorted
#        sub_set is a list that is the current subset of boxes
#        idx is an index in the list box_list
#        all_box_subsets is a 3-D list that has all the subset of boxes
# Output: generates all subsets of boxes and stores them in all_box_subsets
def sub_sets_boxes(box_list, sub_set, idx, all_box_subsets):

    hi = len(box_list)
    if(idx >= hi):
        # box = box_list[idx]
        # sub_set.append(box)
        all_box_subsets.append(sub_set)
    else:
        c = sub_set[:]
        sub_set.append(box_list[idx])
        sub_sets_boxes(box_list, sub_set, idx + 1, all_box_subsets)
        sub_sets_boxes(box_list, c, idx + 1, all_box_subsets)
    return all_box_subsets

# Input: all_box_subsets is a 3-D list that has a subset of boxes
#        largest_size keeps track what the largest subset is
# Output: goes through all the subset of boxes and only stores the
#         largest subsets that nest in the 3-D list all_nesting_boxes


def largest_nesting_subsets(all_box_subsets, largest_size, all_nesting_boxes):

    hi = len(box_list)
    if(idx == hi):
        box = box_list[idx-1]
        n = len(all_box_subsets)
        if n == 0:
            all_box_subsets.append(box)
        else:
            lastSubsetBox = all_box_subsets[n-1]
            if does_fit(lastSubsetBox, box):
                all_box_subsets.append(box)
    else:
        c = sub_set[:]
        sub_set.append(box_list[idx])
        sub_sets_boxes(box_list, sub_set, idx + 1, all_box_subsets)
        sub_sets_boxes(box_list, c, idx + 1, all_box_subsets)
    return all_box_subsets


# # Input: box1 and box2 are the dimensions of two boxes
# # Output: returns True if box1 fits inside box2
def does_fit(box1, box2):

    return (box1[0] < box2[0] and box1[1] < box2[1] and box1[2] < box2[2])


def main():
    # open the file for reading
    in_file = open("./boxes.in", "r")

    # read the number of boxes
    line = in_file.readline()
    line = line.strip()
    num_boxes = int(line)

    # create an empty list for the boxes
    box_list = []

    # read the boxes from the file
    for i in range(num_boxes):
        line = in_file.readline()
        line = line.strip()
        box = line.split()
        for j in range(len(box)):
            box[j] = int(box[j])
        box.sort()
        box_list.append(box)

    # close the file
    in_file.close()

    # print (box_list)
    # print()

    # sort the box list
    box_list.sort()
    # print (box_list)
    # print()

    # create an empty list to hold all subset of boxes
    all_box_subsets = []

    # create a list to hold a single subset of boxes
    sub_set = []

    # generate all subsets of boxes and store them in all_box_subsets
    s = sub_sets_boxes(box_list, sub_set, 0, all_box_subsets)
    return s

    # initialize the size of the largest sub-set of nesting boxes
    #largest_size = 0

    # create a list to hold the largest subsets of nesting boxes
    #all_nesting_boxes = []

    # go through all the subset of boxes and only store the
    # largest subsets that nest in all_nesting_boxes
    #largest_nesting_subsets (all_box_subsets, largest_size, all_nesting_boxes)

    # print all the largest subset of boxes


if __name__ == "__main__":
    main()
