Recursive structures

Thomas Guettler guettli at thomas-guettler.de
Mon Dec 20 16:49:01 CET 2004


Am Mon, 20 Dec 2004 04:22:24 -0800 schrieb bearophileHUGS:

> I've seen that I'd like to
> have a function that tells me if a given data structure contains one or
> more cyclic references

Hi,

does this help you?

from types import *

def isrecursive(obj, dict=None):
    if dict==None:
        dict={}
    mytype=type(obj)
    if mytype in [GeneratorType, SliceType]:
        obj=list(obj)
        mytype=ListType

    l=[]
    MethodWrapperType=type(l.__delattr__)
    
    if type(obj) in [NoneType, TypeType, BooleanType, IntType, LongType, FloatType, ComplexType,
                     StringType, UnicodeType, FunctionType, CodeType, ClassType, MethodType,
                     UnboundMethodType, BuiltinMethodType, BuiltinFunctionType,
                     ModuleType, FileType, XRangeType,
                     EllipsisType, TracebackType, FrameType, BufferType, StringType, MethodWrapperType,
                     MethodWrapperType]:
        return 0
    myid=id(obj)
    if dict.has_key(myid):
        return 1
    dict[myid]=1
    for attr in dir(obj):
        value=getattr(obj, attr)
        if isrecursive(value, dict):
            return 1
    try:
        for item in obj:
            if isrecursive(item, dict):
                return 1
    except TypeError:
        pass

    try:
        for key, value in obj.items():
            if isrecursive(value, dict):
                return 1
    except AttributeError:
        pass

    return 0

def test_isrecursive():
    s="sdf"
    assert(not isrecursive(s))

    
    l=[]
    assert(not isrecursive(l))

    l.append(l)
    assert(isrecursive(l))
    print "OK"

    d={}
    assert(not isrecursive(d))
    d["foo"]=()
    assert(not isrecursive(d))
    d["foo2"]="foo2"
    assert(not isrecursive(d))
    d["foo3"]=d
    assert(isrecursive(d))
    
if __name__=="__main__":
    test_isrecursive()


-- 
Thomas Güttler, http://www.thomas-guettler.de/





More information about the Python-list mailing list