DBToPerm.c

void addEntry(Permutation *new_perm_ptr, Permutation old_perm, int i, int d)
/* old_perm is an array of length d - 1 whose entries give a permutation
 of {0,1, ... ,d-2}.  new_perm is malloced, and set to an array of length d, obtained from
 old_perm by inserting d-1 between entries i-1 and i, or first if i = 0, or last if i = d-1. */

{
    int j;

    if (( i < 0) || (i > d-1))
    {
        printf ("Bad call to addEntry, d = %d, i = %d\n", d, i);
        exit(0);
    }

    initialisePermutation(new_perm_ptr, d);

    for (j=0; j<i; j++)
        (*new_perm_ptr)[j] = old_perm[j];

    (*new_perm_ptr)[i] = d - 1;

    for (j = i; j < d - 1; j++)
        (*new_perm_ptr)[j + 1] = old_perm[j];
}

int isAllowed(DataBase* db_ptr, Permutation perm, int i, int d, int degree)
/* The permutation perm of degree d < degree obeys the conditions stored in *db_ptr.
 Will it continue to do so if we insert d between entries i-1 and i? (0 <= i <= d) */
{
    int a;
    int b;
    int j;

    if (( i < 0) || (i > d))
    {
        printf ("Bad call to isAllowed, d = %d, i = %d\n", d, i);
        exit(0);
    }

    for (j = i; j < d; j++)
    {
        if (greater(d, perm[j], db_ptr, degree))
        {
            //printf("First return: j = %d\n",j);
            return 0;
        }
    }

    for (j = 0; j < i; j++)
    {
        if (greater(perm[j], d, db_ptr, degree))
        {
            //printf("Second return: j = %d\n",j);
            return 0;
        }
    }

    for (j = 0; j < i; j++)
        for (a = 1; a < d; a++)
            for (b = 0; b < a; b++)
            {
                if (greaterImplies(d, perm[j], perm[b], perm[a], db_ptr, degree))
                {
                    //printf("Third return: j = %d / a = %d / b = %d\n",j,a,b);
                    return 0;
                }
            }

    for (j = i; j < d; j++)
        for (a = 1; a < d; a++)
            for (b = 0; b < a; b++)
            {
                if (greaterImplies(perm[j], d, perm[b], perm[a], db_ptr, degree))
                {
                    //printf("Fourth return: j = %d / a = %d / b = %d\n",j,a,b);
                    return 0;
                }
            }
    //printf("\n Is allowed: i is %d, d is %d\n", i, d);
    //printPermutation(perm, d);
    return 1;
}


void initialisePermSet(SmallPermset** sps_ptr_ptr, DataBase *db_ptr, int degree)
/* Create a small permutation set consisting of the permutations (0,1),
 and, if the database does not require 1 > 0, the permutation (1,0).
 It must not require 0 > 1.  See preamble to DBToPerm.h.
 */
{
    Permutation perm1;
    Permutation perm2;

    if (greater(0, 1, db_ptr, degree))
    {
        printf("Bad call to initialisePermSet.  *db_ptr requires 0 > 1.\n");
        printf("See preamble to DBToPerm.h\n");
        exit(0);
    }

    *sps_ptr_ptr = NULL;

    initialisePermutation(&perm1, 2);

    perm1[0] = 0;
    perm1[1] = 1;
    permInSmallPermset(sps_ptr_ptr, perm1, 2);

    if(!greater(1, 0, db_ptr, degree))
    {
        initialisePermutation(&perm2, 2);
        perm2[0] = 1;
        perm2[1] = 0;
        permInSmallPermset(sps_ptr_ptr, perm2, 2);
    }
}

void printPermutation(Permutation perm, int degree)
{
    int i;

    for (i = 0; i < degree; i++)
    {
        printf("%d ", perm[i]);
    }

    printf("\n");
}

void printSmallPermset(SmallPermset* sps_ptr, int degree)
{
    SmallPermset* next_ptr;
    next_ptr = sps_ptr;

    //printf("Entering printSmallPermSet.\n");

    while (next_ptr != NULL)
    {
        // printf("%p\n",next_ptr->entry);
        printPermutation(next_ptr->entry,degree);
        next_ptr = next_ptr->next;
    }
}

void permInSmallPermset(SmallPermset** sps_ptr_ptr, Permutation perm, int degree)
/* Inserts perm at the end of ** sps_ptr_ptr. */
{
    SmallPermset *pointer;
    SmallPermset *sps_p;

    //printf("Entering permInSmallPermset.\n");

    if (! (sps_p = malloc(sizeof(SmallPermset))))
    {
        printf("Malloc failed in permInSmallPermset\n");
        exit(0);
    }

    *sps_p = smallPermsetEntry(perm, degree);

    if (*sps_ptr_ptr == NULL)
    {
        *sps_ptr_ptr = sps_p;
        return;
    }

    pointer = *sps_ptr_ptr;

    while (pointer -> next != NULL) pointer = pointer -> next;

    pointer -> next = sps_p;
}

void expand(SmallPermset** new_sps_ptr_ptr, Permutation perm, int d, DataBase* db_ptr, int degree)
/* perm is a permutation of degree d-1, 3 <= d <= degree.
 Insert d-1 in all slots allowed by the data base *db_ptr, and add the resulting permutations of degree d
 to the small permutation set **new_sps_ptr_ptr.  */
{
    int i;
    Permutation new_perm;

    if ((d < 3) || (d > degree))
    {
        printf("Bad call to extend.  d = %d, degree = %d.\n", d, degree);
        exit(0);
    }
    for (i = 0; i < d; i++)
    {
        if (isAllowed(db_ptr, perm, i, d-1, degree))
        {
            addEntry(&new_perm,perm,i,d);  // Adds d-1 between entries i-1 and i.
            permInSmallPermset(new_sps_ptr_ptr,new_perm,d);
        }
    }
}

void initialisePermutation(Permutation *perm_ptr, int degree)
{
    int i;

    if (! (*perm_ptr = malloc(degree * sizeof(int))))
    {
        printf("Error in initialisePermutation: malloc failed.\n");
        exit(0);
    }

    for (i = 0; i < degree; i++)
    {
        (*perm_ptr)[i] = 0;
    }

}

void copyPermutation(Permutation orig_perm, Permutation copy_perm, int degree)
{
    int i;

    for (i = 0; i < degree; i++)
    {
        copy_perm[i] = orig_perm[i];
    }
}

SmallPermset smallPermsetEntry(Permutation perm, int degree)
/* Essentially the same as setHashEntry in HasTable.c in Code in con_parallel. */

{
    SmallPermset sps;

    initialisePermutation(&(sps.entry), degree);
    copyPermutation(perm, sps.entry, degree);

    sps.next = NULL;

    return sps;
}

void freeSPS(SmallPermset *sps_ptr)
{
    SmallPermset *sps_p;
    while (sps_ptr)
    {
        sps_p = sps_ptr;
        sps_ptr = sps_ptr -> next;
        free(sps_p -> entry);
        free(sps_p);
    }
}

SmallPermset* dbToPerm(DataBase *db_ptr, int degree)
/* The principal procedure for this file.  See DBToPerm.c.  */
{
    SmallPermset *sps1_ptr, *sps2_ptr;
    int d;

    initialisePermSet(&sps1_ptr, db_ptr, degree);

    sps2_ptr = NULL;

    for(d=3; d<=degree; d++)
    {
        while(sps1_ptr != NULL)
        {
            expand(&sps2_ptr, sps1_ptr -> entry, d, db_ptr, degree);
            sps1_ptr = sps1_ptr -> next;
        }
        free (sps1_ptr);
        sps1_ptr = sps2_ptr;
        sps2_ptr = NULL;
    }
    return sps1_ptr;
}