/home/mark/model/software/ScrumPy/ScrumPy/Util/Set.py

"""

ScrumPy -- Metabolic Modelling with Python

Copyright Mark Poolman 1995 - 2002

 This file is part of ScrumPy.

    ScrumPy is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    ScrumPy is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with ScrumPy; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

"""
__doc__ = """
M.G.Poolman 15/1/01 Set.py - basic set operations

Sets are lists with the precondition that :
    1 - all elements are unique
    2 - all elements are comparable with == and !=
    3 - no assumption is made as to the ordering of elements """


def Union(a, b):
    rv = a[:]
    for el in b:
        if not el in a:
            rv.append(el)

    return rv


def Intersect(a, b):
    """ Intersection of a pair of sets """
    rv = []
    for el in a:
        if el in b:
            rv.append(el)

    return rv

def Intersects(setl):
    """ pre: setl is a list of sets, len(setl) > 1
       post: the intersection of all sets in setl """

    rv = setl[0]
    for s in setl[1:]:
        rv = Intersect(rv,s)
    return rv

def Difference(a,b):
    union = Union(a,b)
    intersect = Intersect(a,b)
    return Complement(union, intersect)

def Distance(a,b):
    union = Union(a,b)
    intersect = Intersect(a,b)
    diff =  Complement(union, intersect)
    return float(len(diff))/len(union)


    # a\b
def Complement(a, b):
    rv = []
    for el in a:
        if el not in b:
            rv.append(el)

    return rv



def DoesIntersect(a,b):
    for el in a:
        if el in b:
            return True
    return False

   # a is subset of b
def IsSubset(a, b):
    for el in a:
        if not el in b:
            return False

    return True


def IsEqual(a, b):

    return IsSubset(a, b) and len(a) == len(b)



def Merge(SetList, __first=True):
    """ Pre: SetList is a list of sets, __first is private
       Post: Merge(SetList) == list of of sets, such that intersection in SetList are mereged,
               e.g. Merge([[1,2],[2,3],[4,5]]) => [[1,2,3],[4,5]]
    """

    if __first:
        SetList = SetList[:]
        __first = False

    Seen = 0   # not a set, so won't be in SetList from User
    lensets = len(SetList)
    rv = []
    for idx1 in range(lensets):
        if SetList[idx1] != Seen:
            newset = SetList[idx1]
            SetList[idx1] = Seen
            for idx2 in range(idx1+1, lensets):
                s2 = SetList[idx2]
                if s2 != Seen and DoesIntersect(newset, s2):
                    newset = Union(newset,s2)
                    SetList[idx2] = Seen
            rv.append(newset)
    if len(rv) < lensets:
            return Merge(rv, __first)
    else:
            return rv

def ElimSubs(SetList ):
    """ Pre: SetList is a list of sets
       Post: ElimSubs(sl) == a subset of the sets in SetList such that no set is a subset of any other
    """


    rv = []
    ssidxs = {}
    LenSetList = len(SetList)
    for i1 in range(LenSetList):
        for i2 in range(i1+1, LenSetList):
            s1 = SetList[i1]
            s2 = SetList[i2]
            if IsSubset(s1,s2):
                ssidxs[i1] = 1
            elif IsSubset(s2, s1):
                ssidxs[i2] = 1

    ssidxs = ssidxs.keys()
    for i1 in range(LenSetList):
        if not i1 in ssidxs:
            rv.append(SetList[i1])
    return rv

"""
    SetList = SetList[:]
    rv = []
    while len(SetList) > 0:
        set = SetList.pop()
        KeepIt = True
        for set2 in SetList:
            if IsSubset(set, set2):
                KeepIt = False
                break
            if IsSubset(set2, set):
                SetList.remove(set2)
                SetList.append(set)
                KeepIt = False
        if KeepIt:
            rv.append(set)
    return rv
"""