Return to oh_sets.rr CVS log

Up to [local] / OpenXM / src / asir-contrib / packages / src

Renaming:
 bench-1 --> bench-1.rr
 beta    --> beta.rr
 fourier-0 --> edu_fourier_0.rr
 hg21 --> taka_hg21.rr
 igraph --> igraph.rr
 sets --> oh_sets.rr
 uldet --> uldet.rr

/* -*- mode: C -*- */
/* $OpenXM: OpenXM/src/asir-contrib/packages/src/oh_sets.rr,v 1.1 2005/04/08 06:25:12 takayama Exp $ */
/* Old: sets, see Attic */
/* beta-nbc-asir/sets */

/* This program treats a SET for Asir by identifying a SET with a list.  
   Namely, it ignores the order of elements in a list.
 */

load("gr")$

/* compute (SupSet - Subset) */
def sets_setMinus(SupSet, SubSet) {
    LenSup = length(SupSet);
    X = [];
    for (I = 0; I < LenSup; I++) {
        if (!sets_elementOfSet_p(SupSet[I], SubSet))
            X = cons(SupSet[I], X);
    }
    return reverse(X);
}

/* Is given list sorted? */
def sets_static_sortedList_p(List) {
    V1 = newvect(length(List), List);
    V2 = newvect(length(List), List);
    return V1 == qsort(V2);
}

/* deleting unsorted sets */
def sets_chooseSortedLists(Lists) {
    Len = length(Lists);
    SortedLists = [];
    for (I = 0; I < Len; I++) {
        if (sets_static_sortedList_p(Lists[I])) {
            SortedLists = cons(Lists[I], SortedLists);
        }
    }
    return SortedLists;
}  

def sets_getAllSortedLists(HSize) {
    ASLists = [];
    SLists = [ [] ];
    for (I = 0; I < HSize; I++) {
        SLists = sets_getSubOrders(SLists, HSize);
        SLists = sets_chooseSortedLists(SLists);
        ASLists = cons(SLists, ASLists);
    }
    return ASLists;
}

def sets_getSortedListsWithDepth(HSize, Depth) {
    ASLists = [];
    SLists = [ [] ];
    for (I = 0; I < Depth; I++) {
        SLists = sets_getSubOrders(SLists, HSize);
        SLists = sets_chooseSortedLists(SLists);
        ASLists = cons(SLists, ASLists);
    }
    return ASLists;
}

/* non-used */
def sets_getIntersectables2(Rank, IGraph) {
    Indep = getIndependentSets(IGraph);
    return igRank(Indep, Rank);
}

def sets_getSortedLists(Rank, HSize) {
    Lists = [ [] ];
    for (I = 0; I < Rank; I++) {
        Lists = sets_getSubOrders(Lists, HSize);
        Lists = sets_chooseSortedLists(Lists);
    }
    return Lists;
}  

def sets_getSubOrders(SubOrders, HSize) {
    Len = length(SubOrders);
    X = [];
    for (I=0; I<Len; I++) {
        for (J=1; J<=HSize; J++) {
            if (!sets_elementOfSet_p(J, SubOrders[I])) {
                X = cons(cons(J, SubOrders[I]), X);
            }
        }
    }
    return X;
}

def sets_getOrders(HSize) {
    Orders = [ [] ];
    for (I=0; I<HSize; I++) {
        Orders = sets_getSubOrders(Orders, HSize);
    }
    return sets_sort(Orders);
}

/* set ``Object'' to N-th element of given list. */
def sets_listSetObject(List, Object, N) {
    V = newvect(length(List), List);
    V[N] = Object;
    return vtol(V);
}

/* delete N-th element of given list. */
def sets_listDeleteNth(List, N) {
    V = newvect(length(List)-1, cdr(List));
    for (I = 0; I < N; I++) {
        V[I] = List[I];
    }
    return vtol(V);
}

/* Is ``Element'' included in ``Set''? */
def sets_elementOfSet_p(Element, Set) {
    Len = length(Set);
    for (I = 0; I < Len; I++) {
        if (Element == Set[I])
            return 1;
    }
    return 0;
}

/* Is ``Set'' a proper subset of ``SupSet''? */
def sets_properSubSet_p(Set, SupSet) {
    return (sets_subset_p(Set, SupSet) && length(Set) < length(SupSet));
}

/* Is ``Set'' a subset of ``SupSet''? */
def sets_subset_p(Set, SupSet) {
    Len = length(Set);
    for (I = 0; I < Len; I++) {
        if (!sets_elementOfSet_p(Set[I], SupSet)) {
            return 0;
        }
    }
    return 1;
}

/* Is ``Set'' a subset of subset of ``SupSupSet''? */
def sets_subset_of_subset_p(Set, SupSupSet) {
    Len = length(SupSupSet);
    for (I = 0; I < Len; I++) {
        if (sets_subset_p(Set, SupSupSet[I])) {
            return 1;
        }
    }
    return 0;
}

def sets_sort(List) {
    V = newvect(length(List), List);
    return vtol(qsort(V));
}

/* compute the sign of a permutation ``append(SortedList, [Object])''. */
def sets_static_signSub(SortedList, Object) {
    X = [];
    while ((L = car(SortedList)) != [] && L < Object) {
        X = cons(L, X);
        SortedList = cdr(SortedList);
    }
    X = cons(Object, X);
    return [append(reverse(X), SortedList), length(SortedList)];
}

/* compute the sign of a permutation ``List'' */
def sets_sign(List) {
    Sorted = [];
    Sign = 0;
    while ((L = car(List)) != []) {
        X = sets_static_signSub(Sorted, L);
        Sorted = X[0];
        Sign += X[1];
        List = cdr(List);
    }
    return (Sign % 2) ? -1 : 1;
}

end$