xmlRelaxNGValidateInterleave(xmlRelaxNGValidCtxtPtr ctxt,
                             xmlRelaxNGDefinePtr define)
{
    int ret = 0, i, nbgroups;
    int errNr = ctxt->errNr;
    int oldflags;

    xmlRelaxNGValidStatePtr oldstate;
    xmlRelaxNGPartitionPtr partitions;
    xmlRelaxNGInterleaveGroupPtr group = NULL;
    xmlNodePtr cur, start, last = NULL, lastchg = NULL, lastelem;
    xmlNodePtr *list = NULL, *lasts = NULL;

    if (define->data != NULL) {
        partitions = (xmlRelaxNGPartitionPtr) define->data;
        nbgroups = partitions->nbgroups;
    } else {
        VALID_ERR(XML_RELAXNG_ERR_INTERNODATA);
        return (-1);
    }
    /*
     * Optimizations for MIXED
     */
    oldflags = ctxt->flags;
    if (define->dflags & IS_MIXED) {
        ctxt->flags |= FLAGS_MIXED_CONTENT;
        if (nbgroups == 2) {
            /*
             * this is a pure <mixed> case
             */
            if (ctxt->state != NULL)
                ctxt->state->seq = xmlRelaxNGSkipIgnored(ctxt,
                                                         ctxt->state->seq);
            if (partitions->groups[0]->rule->type == XML_RELAXNG_TEXT)
                ret = xmlRelaxNGValidateDefinition(ctxt,
                                                   partitions->groups[1]->
                                                   rule);
            else
                ret = xmlRelaxNGValidateDefinition(ctxt,
                                                   partitions->groups[0]->
                                                   rule);
            if (ret == 0) {
                if (ctxt->state != NULL)
                    ctxt->state->seq = xmlRelaxNGSkipIgnored(ctxt,
                                                             ctxt->state->
                                                             seq);
            }
            ctxt->flags = oldflags;
            return (ret);
        }
    }

    /*
     * Build arrays to store the first and last node of the chain
     * pertaining to each group
     */
    list = (xmlNodePtr *) xmlMalloc(nbgroups * sizeof(xmlNodePtr));
    if (list == NULL) {
        xmlRngVErrMemory(ctxt, "validating\n");
        return (-1);
    }
    memset(list, 0, nbgroups * sizeof(xmlNodePtr));
    lasts = (xmlNodePtr *) xmlMalloc(nbgroups * sizeof(xmlNodePtr));
    if (lasts == NULL) {
        xmlRngVErrMemory(ctxt, "validating\n");
        return (-1);
    }
    memset(lasts, 0, nbgroups * sizeof(xmlNodePtr));

    /*
     * Walk the sequence of children finding the right group and
     * sorting them in sequences.
     */
    cur = ctxt->state->seq;
    cur = xmlRelaxNGSkipIgnored(ctxt, cur);
    start = cur;
    while (cur != NULL) {
        ctxt->state->seq = cur;
        if ((partitions->triage != NULL) &&
            (partitions->flags & IS_DETERMINIST)) {
            void *tmp = NULL;

            if ((cur->type == XML_TEXT_NODE) ||
                (cur->type == XML_CDATA_SECTION_NODE)) {
                tmp = xmlHashLookup2(partitions->triage, BAD_CAST "#text",
                                     NULL);
            } else if (cur->type == XML_ELEMENT_NODE) {
                if (cur->ns != NULL) {
                    tmp = xmlHashLookup2(partitions->triage, cur->name,
                                         cur->ns->href);
                    if (tmp == NULL)
                        tmp = xmlHashLookup2(partitions->triage,
                                             BAD_CAST "#any",
                                             cur->ns->href);
                } else
                    tmp =
                        xmlHashLookup2(partitions->triage, cur->name,
                                       NULL);
                if (tmp == NULL)
                    tmp =
                        xmlHashLookup2(partitions->triage, BAD_CAST "#any",
                                       NULL);
            }

            if (tmp == NULL) {
                i = nbgroups;
            } else {
                i = ((long) tmp) - 1;
                if (partitions->flags & IS_NEEDCHECK) {
                    group = partitions->groups[i];
                    if (!xmlRelaxNGNodeMatchesList(cur, group->defs))
                        i = nbgroups;
                }
            }
        } else {
            for (i = 0; i < nbgroups; i++) {
                group = partitions->groups[i];
                if (group == NULL)
                    continue;
                if (xmlRelaxNGNodeMatchesList(cur, group->defs))
                    break;
            }
        }
        /*
         * We break as soon as an element not matched is found
         */
        if (i >= nbgroups) {
            break;
        }
        if (lasts[i] != NULL) {
            lasts[i]->next = cur;
            lasts[i] = cur;
        } else {
            list[i] = cur;
            lasts[i] = cur;
        }
        if (cur->next != NULL)
            lastchg = cur->next;
        else
            lastchg = cur;
        cur = xmlRelaxNGSkipIgnored(ctxt, cur->next);
    }
    if (ret != 0) {
        VALID_ERR(XML_RELAXNG_ERR_INTERSEQ);
        ret = -1;
        goto done;
    }
    lastelem = cur;
    oldstate = ctxt->state;
    for (i = 0; i < nbgroups; i++) {
        ctxt->state = xmlRelaxNGCopyValidState(ctxt, oldstate);
	if (ctxt->state == NULL) {
	    ret = -1;
	    break;
	}
        group = partitions->groups[i];
        if (lasts[i] != NULL) {
            last = lasts[i]->next;
            lasts[i]->next = NULL;
        }
        ctxt->state->seq = list[i];
        ret = xmlRelaxNGValidateDefinition(ctxt, group->rule);
        if (ret != 0)
            break;
        if (ctxt->state != NULL) {
            cur = ctxt->state->seq;
            cur = xmlRelaxNGSkipIgnored(ctxt, cur);
            xmlRelaxNGFreeValidState(ctxt, oldstate);
            oldstate = ctxt->state;
            ctxt->state = NULL;
            if (cur != NULL) {
                VALID_ERR2(XML_RELAXNG_ERR_INTEREXTRA, cur->name);
                ret = -1;
                ctxt->state = oldstate;
                goto done;
            }
        } else if (ctxt->states != NULL) {
            int j;
            int found = 0;
	    int best = -1;
	    int lowattr = -1;

	    /*
	     * PBM: what happen if there is attributes checks in the interleaves
	     */

            for (j = 0; j < ctxt->states->nbState; j++) {
                cur = ctxt->states->tabState[j]->seq;
                cur = xmlRelaxNGSkipIgnored(ctxt, cur);
                if (cur == NULL) {
		    if (found == 0) {
		        lowattr = ctxt->states->tabState[j]->nbAttrLeft;
			best = j;
		    }
                    found = 1;
		    if (ctxt->states->tabState[j]->nbAttrLeft <= lowattr) {
		        /* try  to keep the latest one to mach old heuristic */
		        lowattr = ctxt->states->tabState[j]->nbAttrLeft;
			best = j;
		    }
                    if (lowattr == 0)
		        break;
                } else if (found == 0) {
                    if (lowattr == -1) {
		        lowattr = ctxt->states->tabState[j]->nbAttrLeft;
			best = j;
		    } else
		    if (ctxt->states->tabState[j]->nbAttrLeft <= lowattr)  {
		        /* try  to keep the latest one to mach old heuristic */
		        lowattr = ctxt->states->tabState[j]->nbAttrLeft;
			best = j;
		    }
		}
            }
	    /*
	     * BIG PBM: here we pick only one restarting point :-(
	     */
            if (ctxt->states->nbState > 0) {
                xmlRelaxNGFreeValidState(ctxt, oldstate);
		if (best != -1) {
		    oldstate = ctxt->states->tabState[best];
		    ctxt->states->tabState[best] = NULL;
		} else {
		    oldstate =
			ctxt->states->tabState[ctxt->states->nbState - 1];
                    ctxt->states->tabState[ctxt->states->nbState - 1] = NULL;
                    ctxt->states->nbState--;
		}
            }
            for (j = 0; j < ctxt->states->nbState ; j++) {
                xmlRelaxNGFreeValidState(ctxt, ctxt->states->tabState[j]);
            }
            xmlRelaxNGFreeStates(ctxt, ctxt->states);
            ctxt->states = NULL;
            if (found == 0) {
                if (cur == NULL) {
		    VALID_ERR2(XML_RELAXNG_ERR_INTEREXTRA,
			       (const xmlChar *) "noname");
                } else {
                    VALID_ERR2(XML_RELAXNG_ERR_INTEREXTRA, cur->name);
                }
                ret = -1;
                ctxt->state = oldstate;
                goto done;
            }
        } else {
            ret = -1;
            break;
        }
        if (lasts[i] != NULL) {
            lasts[i]->next = last;
        }
    }
    if (ctxt->state != NULL)
        xmlRelaxNGFreeValidState(ctxt, ctxt->state);
    ctxt->state = oldstate;
    ctxt->state->seq = lastelem;
    if (ret != 0) {
        VALID_ERR(XML_RELAXNG_ERR_INTERSEQ);
        ret = -1;
        goto done;
    }

  done:
    ctxt->flags = oldflags;
    /*
     * builds the next links chain from the prev one
     */
    cur = lastchg;
    while (cur != NULL) {
        if ((cur == start) || (cur->prev == NULL))
            break;
        cur->prev->next = cur;
        cur = cur->prev;
    }
    if (ret == 0) {
        if (ctxt->errNr > errNr)
            xmlRelaxNGPopErrors(ctxt, errNr);
    }

    xmlFree(list);
    xmlFree(lasts);
    return (ret);
}