(use eggdoc) (define doc `((eggdoc:begin (name "npdiff") (description "Compute the longest common subsequence of two sequences, " "and generate a script to transform one sequence into the other.") (author (url "http://chicken.wiki.br/users/ivan-raikov" "Ivan Raikov")) (history (version "1.10" "Eliminated dependency on matchable") (version "1.9" "Ported to Chicken 4") (version "1.8" "Added missing files to the file manifest") (version "1.7" "Removed dependence on stack egg") (version "1.5" "Build script updated for better cross-platform compatibility") (version "1.4" "eggdoc documentation fix") (version "1.3" "License upgrade to GPL v3") (version "1.2" "Added license text to source files") (version "1.1" "Documentation fixes") (version "1.0" "Initial release")) (requires (url "datatype.html" "datatype")) (usage "(require-extension npdiff)") (download "npdiff.egg") (documentation (p "The npdiff library is an implementation of an algorithm for " "sequence comparison that has a worst-case running time of " (tt "O(N*P)") ", where " (tt "P") " is the number of deletions " "required by the shortest edit script between the two sequences. " " The algorithm is described in the following paper: " (pre "Sun Wu, Udi Manber, Eugene Myers, and Webb Miller. " "An O(NP) sequence comparison algorithm. " "In Information Processing Letters, volume 35, pages " "317--323, September 1990.")) (p "This library defines a data type that describes the three " "basic operations of an edit script (remove, insert, change) " "and a procedure that implements the algorithm for sequences of " "an arbitrary type, provided an equality predicate for that type, " "and accessors for the sequence.") (subsection "Data types" ,(eggdoc:make-defsig 'datatype "(define-datatype diffop diffop? ...)" `(p "Representation of the three diff operations: insert, remove, change. " "The target in each operation is an index or a range of indices in " "the sequence being transformed (target sequence), " "and the source is a range of indices in the sequence being read from " "(source sequence). The operation definitions are: " (symbol-table (describe "(Insert target source seq context)" (p "Insert operation; " (ul (li (tt "TARGET") " is the index at which the insertion takes place; ") (li (tt "SOURCE") " is a range in the form (x . y) " "that specifies the indices of those elements in the source sequence " "that are inserted in the target sequence; ") (li (tt "SEQ") " is the target sequence, and ") (li (tt "CONTEXT") " is an optional context provided " " in the form " (tt "(BEFORE . AFTER)") " where " (tt "BEFORE") " is a sequence of elements from the source " "preceding the elements being inserted, and " (tt "AFTER") " is a sequence of elements from the source " "that follow the elements being inserted. ")))) (describe "(Remove target seq context)" (p "Remove operation; " (ul (li (tt "TARGET") " is a range of elements in the form (x . y) " "that are being deleted from the target sequence; " ) (li (tt "SEQ") " is the target sequence, and ") (li (tt "CONTEXT") " is an optional context provided " " in the form " (tt "(BEFORE . AFTER)") " where " (tt "BEFORE") " is a sequence of elements from the target " "preceding the elements being deleted, and " (tt "AFTER") " is a sequence of elements from the target " "that follow the elements being deleted. ")))) (describe "(Change target source seqin seqout contextin contextout)" (p "Change operation; " (ul (li (tt "TARGET") " is a range of elements in the form (x . y) " "that are being modified in the target sequence; " ) (li (tt "SOURCE") " is a range of elements in the form (x . y) " "from the source sequence that are replacing " "the specified elements in the target sequence; " ) (li (tt "SEQIN") " is the source sequence, and " (tt "SEQOUT") " is the target sequence; ") (li (tt "CONTEXTOUT") " is an optional context provided " " in the form " (tt "(BEFORE . AFTER)") " where " (tt "BEFORE") " is a sequence of elements from the target " "preceding the elements being changed (SEQOUT), and " (tt "AFTER") " is a sequence of element from the target " "that follow the elements being changed (SEQOUT); " (tt "CONTEXTIN") " is an optional context provided " " in the form " (tt "(BEFORE . AFTER)") " where " (tt "BEFORE") " is a sequence of elements from the source " "preceding the replacement elements (SEQIN), and " (tt "AFTER") " is a sequence of elements from the source " "that follow the replacement elements (SEQIN); ")))))))) (subsection "Procedures" (procedure "make-diff:: EQUAL? SEQ-REF SEQ-LENGTH HUNKS-PROC -> DIFF-PROC" (p "create a diff procedure, where " (ul (li (tt "EQUAL?") " is an equality predicate for " "elements of the type being compared; ") (li (tt "SEQ-REF") " is a procedure of the form " (tt "LAMBDA SEQ INDEX -> ELEMENT") " which returns element " (tt "INDEX") " from sequence " (tt "SEQ") "; ") (li (tt "SEQ-LENGTH") " is a procedure of the form " (tt "LAMBDA SEQ -> LEN") " which returns the length " " of sequence " (tt "SEQ") "; ") (li (tt "HUNKS") " is a procedure of the type created by " (tt "make-hunks") ", which is described below.")) "The returned procedure is of the form " (tt "LAMBDA A B [CONTEXT-LEN] -> (HUNK ... )") " where " (tt "A") " and " (tt "B") " are two sequences to be compared, " "and " (tt "CONTEXT-LEN") " is an optional context length, which is used " "by the " (tt "HUNKS") " procedure to create context in the hunks of the " "edit script")) (procedure "make-hunks:: SEQ-REF SEQ-LENGTH SEQ-SLICE -> HUNKS-PROC" (p "create a procedure that creates insert/remove/change hunks " "given a stack of matching index ranges that is produced by the " (tt "diff") " procedure above." (ul (li (tt "SEQ-REF") " is a procedure of the form " (tt "LAMBDA SEQ INDEX -> ELEMENT") " which returns element " (tt "INDEX") " from sequence " (tt "SEQ") "; ") (li (tt "SEQ-LENGTH") " is a procedure of the form " (tt "LAMBDA SEQ -> LEN") " which returns the length " " of sequence " (tt "SEQ") "; ") (li (tt "SEQ-SLICE") " is a procedure of the form " (tt "LAMBDA SEQ START END -> SEQ") " which returns a list " " with the elements contained within the specified range " "in the input sequence " (tt "SEQ") "; ")) "The returned procedure is of the form " (tt "LAMBDA A B CSS [CONTEXT] -> (HUNK ... )") " where " (tt "A") " and " (tt "B") " are the two sequences compared, " (tt "CSS") " is the stack of matching ranges returned by " (tt "diff") ", " "and " (tt "CONTEXT") " is an optional argument that is used to add " "context to the generated hunks, if specified.")))) (examples (pre #<vector text1)) (B (list->vector text2))) ((make-npdiff string=? vector-ref vector-length (make-hunks vector-ref vector-length (compose vector->list vector-copy))) A B context-len)))) EOF )) (license "Copyright 2007-2009 Ivan Raikov. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the GPL license can be found at .")))) (if (eggdoc->html doc) (void))