# This program is written by whaack solely to help myself understand V

# This program intentionally does not use python's class structure and instead
# represents data as tuples, creating simple functions to serve as constructors
# and the like.

### FILEMETADATA CONSTRUCTOR, ACCESSORS, & METHODS ###

# Filemetadata is a tuple containing the path to the file in the first index
# and the hash of the file's contents in the second index.
def new_filemetadata(filepath, filehash):
    return (filepath, filehash)

# Returns True if the filehash of the filemetadata is the string 'false', False otherwise.
# The convention of giving a deleted file a hash of string 'false' is based
# off of the vdiff tool found on thebitcoin.foundation website.
def filemetadata_is_deleted(filemetadata):
    return filemetadata[1] == 'false'

### END FILEMETADATA CONSTRUCTOR, ACCESSORS, & METHODS ###


### VPATCH CONSTRUCTOR, ACCESSORS, & METHODS ###

# name is the name of the vpatch
# antecedents and descendants are lists of filemetadata
# antecedents share the same index with their correspoding descendant
# Note: For a full vtron, a vpatch would also need the data containing the diffs of file content
# between the antecedent and descendant.
def new_vpatch(name, antecedents, descendants):
    return (name, antecedents, descendants)

def vpatch_get_name(vpatch):
    return vpatch[0]

def vpatch_get_antecedents(vpatch):
    return vpatch[1]

def vpatch_get_descendants(vpatch):
    return vpatch[2]

# Takes a list of vpatches and returns the concatenation of their tuples of antecedents.
def get_all_antecedents(vpatches):
    return reduce(lambda l1, l2: l1 + l2, map(lambda vpatch: vpatch_get_antecedents(vpatch), vpatches), ())

# Takes a vpatch and a set of other_vpatches, which can include the vpatch in the first argument.
# Returns True if vpatch is not a parent of any of other_vpatches, False otherwise.
# We consider a vpatch to be a parent of another vpatch if any one of the vpatch's descendants
# are equivilant to any one of the other vpatch's antecedents. This is perhaps the wrong way to
# do this. Any vpatch that reverts a file causes the set of vpatches to be considered cyclic.
# We explicitly prevent this case from happening when the reversion is the deletion of a file,
# because that will cause the graph to be cyclic by making the reversion vpatch a parent of the
# genesis patch. However this is not a great solution because a vpatch may very well indeed
# have only a deletion of a file while being a parent of vpatch that is not the genesis vpatch.
def vpatch_is_childless(vpatch, other_vpatches):
    descendants = vpatch_get_descendants(vpatch)
    antecedents = get_all_antecedents(other_vpatches)
    def has_children(d):
        return not filemetadata_is_deleted(d) and d in antecedents
    return not reduce(lambda x, y: x or y, map(lambda d: has_children(d), descendants), False)

### END VPATCH CONSTRUCTOR & ACCESSORS ###

# Takes a list of vpatches and returns a tuple of them topologically sorted.
# To perform the topological sort, a vpatch is considered to have an edge directed
# to another vpatch if the first vpatch has a descendant that equals the antecedent of
# the other vpatch.
def topo_sort_vpatches(vpatches):
    unsorted = list(vpatches)
    topo_sorted = []
    while unsorted:
        to_remove = filter(lambda vp: vpatch_is_childless(vp, unsorted), unsorted)
        if not to_remove:
            raise Exception('Cyclic Graph')
        topo_sorted += to_remove
        map(lambda vp: unsorted.remove(vp), to_remove)
    return tuple(topo_sorted[::-1]) # [::-1] is Python sugar for returning a copy of a reversed list.