| 1937 | # a core building block for some CPU-intensive generator applications. |
| 1938 | |
| 1939 | def conjoin(gs): |
| 1940 | |
| 1941 | n = len(gs) |
| 1942 | values = [None] * n |
| 1943 | |
| 1944 | # Do one loop nest at time recursively, until the # of loop nests |
| 1945 | # remaining is divisible by 3. |
| 1946 | |
| 1947 | def gen(i): |
| 1948 | if i >= n: |
| 1949 | yield values |
| 1950 | |
| 1951 | elif (n-i) % 3: |
| 1952 | ip1 = i+1 |
| 1953 | for values[i] in gs[i](): |
| 1954 | for x in gen(ip1): |
| 1955 | yield x |
| 1956 | |
| 1957 | else: |
| 1958 | for x in _gen3(i): |
| 1959 | yield x |
| 1960 | |
| 1961 | # Do three loop nests at a time, recursing only if at least three more |
| 1962 | # remain. Don't call directly: this is an internal optimization for |
| 1963 | # gen's use. |
| 1964 | |
| 1965 | def _gen3(i): |
| 1966 | assert i < n and (n-i) % 3 == 0 |
| 1967 | ip1, ip2, ip3 = i+1, i+2, i+3 |
| 1968 | g, g1, g2 = gs[i : ip3] |
| 1969 | |
| 1970 | if ip3 >= n: |
| 1971 | # These are the last three, so we can yield values directly. |
| 1972 | for values[i] in g(): |
| 1973 | for values[ip1] in g1(): |
| 1974 | for values[ip2] in g2(): |
| 1975 | yield values |
| 1976 | |
| 1977 | else: |
| 1978 | # At least 6 loop nests remain; peel off 3 and recurse for the |
| 1979 | # rest. |
| 1980 | for values[i] in g(): |
| 1981 | for values[ip1] in g1(): |
| 1982 | for values[ip2] in g2(): |
| 1983 | for x in _gen3(ip3): |
| 1984 | yield x |
| 1985 | |
| 1986 | for x in gen(0): |
| 1987 | yield x |
| 1988 | |
| 1989 | # And one more approach: For backtracking apps like the Knight's Tour |
| 1990 | # solver below, the number of backtracking levels can be enormous (one |