# include "Slip.h" /** * @brief gSlip equivalent to N:YMATCH function in MAD-Slip * * Pattern matching is done by comparing the input rule against * a list. For the nonce, the list does not contain any sublist. * This interpretation seems consistent with the example given * in MAD_SLIPManual.pdf, in that the example and definition do * not separately specify any mechanicism which can recognize * and process a sublist. * * The comparison is done in a linear fashion, starting at the * first cell in the rule and the input list. The code logic * seems to be: * 1. If the spec cell is an integer * a. If the spec is zero, create a sublist containing * all input list cells from the current cell to the * last cell in the input list. Append this sublist * to the result and advance the input list 'pointer' * and the rule 'pointer' to the ends of their respective * lists. * b. If the spec is a number > 0, then create a sublist * containing that number of cells from the input list * and append this list to the result. Advance the * input list 'pointer' to the number of cells copied * and the rule list by 1. * c. If the spec is a number > 0 and there are less than * number of cells left in the input list, then we fail. * d. If the number < 0, then fail. * * 2. If the spec cell is a literal (as defined in MAD_Slip * a literal is a string) then: * a. If there is no match to the current input cell, then * continue searching. This logic can be changed. * b. If there is a match to the currect input cell, then * create a sublist and append it to the result. Advance * the input list 'pointer' by 1 and the rule list 'pointer' * by 1. * * 3. If the rule list is a sublist, then advance over it (ignore * all sublists). * * 4. If the input list is a sublist, then advance over it * (ignore all sublists). * * 5. Terminate processing when either the rule list is empty * or the input list is empty. Note 'empty' means that the * list 'pointer' points to the list header. It does not * mean that the original list contains no elements. * * Some Notes: * 1. The algorithm is non-destructive. The input list parameters * are unchanged. * 2. The algorithm is primed by advancing over the input list * parameters to the first cell in the list. If the list is * empty, then the first cell in the list is the list header * and this terminates processing. * 3. The list 'pointer' is never seen by the application. The * application only sees the current list cell being proessed. * 4. Step 1.a. implies that an input spec of zero (0) must be * the last spec in the input rules. * 5. Step 1.c. this condition is not specified in MAD_SLIPManual. * It is assumed to be the intent of the writer. An alternative * would be to declare this an error and take fixup, but there * is no way to report an error back to the caller. * 6. Rule comparison is linear. It goes from left to right (start * to finish) without backup. Once a comparison is made and is * successful, the rule advances. * 7. Step 2 is the nub of the argument. This specifies the exact * mechanism for comparing rule to the input list. Part of this * is that a failure comparison between a rule literal and the * input list cell causes the input list to advance but the * rule list to stay where it is. * 8. No mechanism is specified in MAD_SLIPManual to treat sublists. * It is assumed that sublists are not entered but that if the * input spec is a number, then sublists are copied. * 9. There is an assumption that the output result is an empty * list on entry. * 10. On error, the output result is not emptied. * * @param[IN] rule rename L1 * @param[IN] list rename L2 * @param[OUT] result rename L3 */ int YMATCH(SlipHeader rule, SlipHeader list, SlipHeader result) { SlipSequencer cell(list); //!< linear iterator for input list SlipSequencer spec(rule); //!< linear iterator for rule //!< advance in the rule for ( cell.advanceLER() //!< advance to first slip cell , spec.advanceLER() //!< advnace to first rule ; !cell.isHeader() && !spec.isHeadaer(); spec.advanceLWR() ) { if (spec.isSublist()) continue; //!< sublists in the rule are excluded if (cell.isSublist()) continue; //!< sublists in the input list are excluded if (spec.isNumber()) { if (spec < 0) continue; SlipHeader& head = *new SlipHeader(); if (spec == 0) { for (; !cell.isHeader(); cell.advanceLWR()) { head.enqueue(cell.currentCell); } } else { int i; for (i = 0; (i < spec) && !cell.isHeader(); cell.advanceLWR()) { head.enqueue(cell.currentCell); } if (i != spec) return 1; } cell.advanceLWL(); // we went too far result.enqueue(head); // put a sublist into the result // The assumption is that we search until a string // match is found. If the requirement is that the // next string in the input list must be the literal // in the spec, then the for loop is replaced by a // conditional. } else if (spec.isString() { // spec must be a literal // replace if 'if' as required for (; !cell.isHeader() && cell != spec; cell.advanceLWR()); if (cell.isHeader()) return 1; // a string match was not found if (cell.isHeader()) return 1; // a string match was not found if (cell != spec) return 1; // a string match was not found SlipHeader& head = *new SlipHeader(); head.enqueue(cell.currentCell); result.enqueue(head); } else { // action unspecified } } return (int)result.isEmpty(); } // int YMATCH(SlipHeader rule, SlipHeader list, SlipHeader result) # include "Slip.h" /** * * @brief Create a list from a rule and a list. * * THIS IS NOT A GOOD IMPLEMENTATION (period). * * The rule determines the order of assembly and the new list contest. * The input list determines what text strings can be used in the new list. * * Rules * 1. Literals (strings). Insert the string into the current list position. * Advance the rule and the input list pointers * a.Insert the string into the output list. * b. Advance the rule 'pointer'. * * 2. Number. The number must be positive and less than the size of the * input list. The number represents the ordinal position of a sublist * in the input list. * a. If the number is negative or zero (0) then fail. * b. If the number is greater than the input list size then fail. * c. If the number is the same as the last number, then append * the sublist contents into the output list. * d. If the number is less than the last number, then search bacwards * (to the left) in the input list until the indexed sublist and * then append the sublist contents into the output list. * e. If the number is more than the last number, then search forwards * (to the right) in the input list until the indexed sublist and * then append the sublist contents into the output list. * f. During any search if a SlipDatum cell is detected, fail. * g. Advance the rule 'pointer'. * * 3. If the rule list is empty, return. * * 4. If the input list is empty, return. * * Some Notes: * 1. The algorithm is non-destructive. The input list parameters * are unchanged. * 2. The algorithm is primed by advancing over the input list * parameters to the first cell in the list. If the list is * empty, then the first cell in the list is the list header * and this terminates processing. * 3. The list 'pointer' is never seen by the application. The * application only sees the current list cell being proessed. * 4. Indexing starts at one (1). The first cell in the input list * is the oneth element not the zeroth element in the list. * 5. The algorithm does lazy input validation. Checking that the * current cell of the input list is not a datum is deferred. * This is a minor optimization over checking at each loop * iteration. It's defect is that validating the correctness * of the input list is deferred until the last possible * moment. * 6. Why this is not a good implementation. Consider a list with * 1,000,000 sublists and the index order is (500,000, 750,000, * 250,000). The algorithm used requires that a linear search * be done for the first item (500,000 probes), the second item * (250,000 probes) and the last item (500,000 probes) for a * total search of 1,250,000 probes. * * There are several optimization procedurs that can be used. * None of them work well in all cases, but then we can "mix * and match", do a pre-scan of the rules and input list to * determine the 'best' search order. This adds complexity and * time (cost) which is burdensome for small lists or unnecessary * for rules containing monotonically increasing list indexes. * * We can take another approach and create an array of the same * size as the input list, and populate it with refrences to input * list sublists, in our little case that would be an array of * size 1,000,000. We can even optimize use by not doing a prepass * to fill the array but rather do an on-the-fly insert. On-the-fly * inserts have the advantage that back references are always * supported. We can even do a prepass over the rules to determine * if there are backwards references and then not create or use * an array of references. * * None of this has been done with this algorithm. This * algorithm's purpose is to provide a simple solution to the * issue of there being no available source code for this * function. It is not designed to provide the best solution. * * * @param[IN] rule rename L1 * @param[IN] list rename L2 * @param[OUT] result rename L3 * */ void ASSMBL(SlipHeader rule, SlipHeader list, SlipHeader result) { size_t listIndex = 1; //!< index into the input list SlipSequencer cell(list); //!< linear iterator for input list SlipSequencer spec(rule); //!< linear iterator for rule //!< advance in the rule for ( cell.advanceLER() //!< advance to first slip cell , spec.advanceLER() //!< advnace to first rule ; !cell.isHeader() && !spec.isHeadaer(); spec.advanceLWR() ) { if (spec.isSublist()) return; // RULES can not have sublists // there are only two choice for a RULE: // either it is a number or a string if (spec.isString()) result.enqueue(spec.currentCell()); else if (cell.isDatum()) return; // lists can not have data else { // it is a number size_t diffNDX = spec.currentCell() - listIndex; // differential position listIndex += diffNDX; if (listIndex < 1) return; // went back too far else if (listIndex > cell.size()) // went forward too far else if (diffNDX >= 0) { for (; diffNDX > 0); cell.advanceLER(), diffNDX--) if (cell.isDatum()) return; if (cell.isDatum()) return; } else { // diffNDX < 0 for (; diffNDX < 0); cell.advanceLEl(), diffNDX++); } SlipSequencer sublist((SlipHeader)cell.currentCell()); for(sublist.advanceLER(); !sliblist.isHeader(); sublist.advanceLER(){ if sublist.currentCell().isSublist()) return; result.enqueue(sliplist.currentCell()); } } } } // void ASSMBL(SlipHeader rule, SlipHeader list, SlipHeader result)