# -*- coding: utf-8 -*-
"""
Created on Tue May  9 00:23:32 2023

@author: Bruno Andreotti
"""

import math as m
import itertools



#
# Generate the labeled downset {0,1,2,...n}
#
def zermelo(n):
    zermelo_n = {0}
    for i in range(1,n+1):
        zermelo_n = zermelo_n.union({i})
    return zermelo_n



#
# Generate list of all permutations of {0,1,2,...n}.
# This funtion returns the permutation group of n as a list of tuples.
#
def permutations(n):
    return list(itertools.permutations(range(n)))


#
# Return the bitwise rank of a natural number n.
# Count 1s in the binary representation of n to return the bitwise rank of n.
#
def bit_rank(n):
    rank = 0
    while(n != 0):
        n = n & (n-1)
        rank += 1
    return(rank)



#
# Return the bitwise downward closure of a set of natural numbers X.
#
def bit_down_close(X):
    downset = X
    for x in X:
        for i in range(max(X)):
            if i|x == x:
                downset = downset.union({i})              
    return downset



#
# Get the bitwise vertices of a set X -- the powers of 2 underlying X.
#
def bit_vertices(X):
    # Down close X
    X = bit_down_close(X)
    # Get the atoms of the downset (powers of 2)
    X_vertices = set()
    for x in X:
        if bit_rank(x) == 1:
            X_vertices = X_vertices.union({x})
    return X_vertices



#
# Return the maximal elements of a set of natural numbers under the bitwise
# ordering. This is an upward antichain closure.
#
def bit_max(X):
    # Set output to empty set for now
    antichain = set()
    # Check each x in the ds
    for x in X:
        # Set the upset to emptyset
        upset_x = set()
        # Check if ds contains anything above x
        for y in X:
            # Add any y > x to the upset of x
            if x|y == y and x != y:
                upset_x = upset_x.union({y})
        # If nothing is above x, add x to antichain
        if upset_x == set():
            antichain = antichain.union({x})
    return antichain



#
# Get minimal elements of a set X. This is the downward antichain closure.
# Used alongside rel_complement to get a set of possible next steps for 
# the procedural generation of FD(n).
#
def bit_min(X):
    # Set output to empty set for now
    antichain = set()
    # Check each x in X
    for x in X:
        # Set the downset of x to emptyset
        downset_x = set()
        # Check if X contains anything below x
        for y in X:
            # Add any y < x to the downset of x
            if x|y == x and x != y:
                downset_x = downset_x.union({y})
        # If nothing is below x, add x to minimal elements of X
        if downset_x == set():
            antichain = antichain.union({x})
    return antichain



#
# Return the monotone Boolean function associated with the upward antichain
# closure of a set X.
#
def set_to_mbool(X):
    # Get the antichain of ds
    antichain = bit_max(X)    
    # Get a list of vertices for each antichain, compile into a list of lists
    antichain_vertices = []
    for x in antichain:
        # Each element of an antichain is a unique bitwise join of its atoms
        x_vertices = bit_vertices({x})
        x_vertex_list = []
        # We store this information as positions on an n-tuple of inputs
        # rather than as atoms themselves. The permutations are what
        # establishes links between tuple positions and specific atoms.
        for y in x_vertices:
            # The log base 2 of an atom returns its position on the list of atoms.
            y = int(m.log(y,2))
            x_vertex_list.append(y)
        antichain_vertices.append(x_vertex_list)
    # We can now define the monotone Boolean function associated with ds
    def mbool(permutation):
        # Take a permutation of 0 to n-1, turn it into a tuple of powers of 2
        permutation_powers = [2**i for i in permutation]
        # Output initially emptyset
        output_antichain = set()
        for i in antichain_vertices:
            # Calculate ith member of antichain under current permutation
            ith_antichain = 0
            for j in i:
                # Iteratively join each member of the ith set of atoms
                ith_antichain = ith_antichain|permutation_powers[j]
            # Add ith term to the output antichain
            output_antichain = output_antichain.union({ith_antichain})
        return(output_antichain)
    # Abstract output variable over permutations of generator set
    output_mbool = lambda permutation:mbool(permutation)
    return output_mbool



#
# Generate conjugacy class of the antichain closure of a set X.
#
def permutate(X, permutations):
    # Get the monotone Boolean function associated with X
    X_mbool = set_to_mbool(X) 
    # Set initially empty list of conjugates of X
    X_conjugate_list = []
    # Try each permutation
    for permutation in permutations:
        X_conjugate = X_mbool(permutation)
        # Only keep new permutation if it's actually new
        if X_conjugate in X_conjugate_list:
            continue
        else:
            X_conjugate_list.append(X_conjugate)   
    return X_conjugate_list



#
# Get the coefficient for the nth natural downset
#
def nth_natds_c(n):
    natds_vertices = bit_vertices(zermelo(n))
    minimal_lattice_order =len(natds_vertices)
    minimal_perms = permutations(minimal_lattice_order)
    return len(permutate(zermelo(n),minimal_perms))



#
# Get a list of natural downset coefficients from 0 to n
#
def natds_c_list(n,start=0):
    return [[i,nth_natds_c(i)] for i in range(start,n)]