Re: Recursive structures

[Scott David Daniels]

Thomas Guettler wrote:
code to do the test
The following transformation of his code shows how exceptions
can be used to make code read more clearly.  There are a few
issues (such as AVOIDITER) to decide on, and usually you are
inquiring about your own data structures (which you'll know
more about).  Recursive data structures, like deepcopy, are
matters of interpretation of data, and cannot really be answered
without knowing what you mean by your data (and possibly why you
are inquiring).  I have also done a few things to speed up the
code (my premature optimization sin) such as lifting constant
expressions to module load time.
from types import *
MethodWrapperType = type([].__delattr__)
LEAVES = set([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])
FORCELIST = set([GeneratorType, SliceType])
        # these are dicey: can cause lots of side-effects
AVOIDITER = set()
        # Here go things like itertools.count -- infinite generators
class RecursionFoundError(Exception): pass
def walks(obj, seen):
    identity = id(obj)
    if identity in seen:
        raise RecursionFoundError, obj
    mytype = type(obj)
    if mytype in LEAVES:
        return
    seen = seen.copy()  # (obj, obj) is not recursive, so new copy
    seen.add(identity)
    if mytype in FORCELIST:
        obj = list(obj) # this is a new obj, so not in the structure
        mytype = ListType
    for attr in dir(obj):
        walks(getattr(obj, attr), seen)
    if mytype not in AVOIDITER:
        try:
            for item in obj:
                walks(item, seen)
        except TypeError:
            pass
    try:
        for key, value in obj.items():
            walks(key, seen)  # Key might be object w/ hash method
            walks(value, seen)
    except AttributeError:
        pass
def isrecursive(obj):
    try:
        walks(obj, set())
    except RecursionFoundError, err:
        return True    # err.args[0] is the looping object
    return False
--Scott David Daniels
[EMAIL PROTECTED]
--
http://mail.python.org/mailman/listinfo/python-list