Sophie

Sophie

distrib > Fedora > 14 > x86_64 > by-pkgid > a0995fd4c38add851d8e9994a3499e40 > files > 418

ghc-darcs-devel-2.4.4-3.fc14.x86_64.rpm

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!--Rendered using the Haskell Html Library v0.2-->
<HTML
><HEAD
><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"
><TITLE
>Lcs</TITLE
><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"
><SCRIPT SRC="haddock-util.js" TYPE="text/javascript"
></SCRIPT
><SCRIPT TYPE="text/javascript"
>window.onload = function () {setSynopsis("mini_Lcs.html")};</SCRIPT
></HEAD
><BODY
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="topbar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "
></TD
><TD CLASS="title"
>darcs-2.4.4: a distributed, interactive, smart revision control system</TD
><TD CLASS="topbut"
><A HREF="src/Lcs.html"
>Source code</A
></TD
><TD CLASS="topbut"
><A HREF="index.html"
>Contents</A
></TD
><TD CLASS="topbut"
><A HREF="doc-index.html"
>Index</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="modulebar"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD
><FONT SIZE="6"
>Lcs</FONT
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Description</TD
></TR
><TR
><TD CLASS="doc"
><P
>LCS stands for Longest Common Subsequence, and it is a relatively
 challenging problem to find an LCS efficiently.  This module implements
 the algorithm described in:
</P
><P
><A HREF="An O(ND) Difference Algorithm and its Variations.html"
>An O(ND) Difference Algorithm and its Variations</A
>, Eugene Myers,
   Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
   especially the variation described in section 4.2 and most refinements
   implemented in GNU diff (D is the edit-distance).
</P
><P
>There is currently no heuristic to reduce the running time and produce
 suboptimal output for large inputs with many differences. It behaves like
 GNU diff with the -d option in this regard.
</P
><P
>In the first step, a hash value for every line is calculated and collisions
 are marked with a special value. This reduces a string comparison to an
 int comparison for line tuples where at least one of the hash values is
 not equal to the special value. After that, lines which only exists in one
 of the files are removed and marked as changed which reduces the running
 time of the following difference algorithm. GNU diff additionally removes
 lines that appear very often in the other file in some cases.
 The last step tries to create longer changed regions and line up deletions
 in the first file to insertions in the second by shifting changed lines
 forward and backward.
</P
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Synopsis</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="body"
><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"
><TR
><TD CLASS="decl"
><A HREF="#v%3AgetChanges"
>getChanges</A
> :: [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>] -&gt; [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>] -&gt; [(<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
>, [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>], [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>])]</TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AaLen"
>aLen</A
> :: <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array-IArray.html#t%3AIArray"
>IArray</A
> a e =&gt; a <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> e -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>type</SPAN
> <A HREF="#t%3ABArray"
>BArray</A
> = <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array-Unboxed.html#t%3AUArray"
>UArray</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>type</SPAN
> <A HREF="#t%3APArray"
>PArray</A
> = <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray"
>Array</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> <A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><SPAN CLASS="keyword"
>type</SPAN
> <A HREF="#t%3ABSTArray"
>BSTArray</A
> s = <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array-ST.html#t%3ASTUArray"
>STUArray</A
> s <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool"
>Bool</A
></TD
></TR
><TR
><TD CLASS="s8"
></TD
></TR
><TR
><TD CLASS="decl"
><A HREF="#v%3AshiftBoundaries"
>shiftBoundaries</A
> ::  <A HREF="Lcs.html#t%3ABSTArray"
>BSTArray</A
> s -&gt; <A HREF="Lcs.html#t%3ABSTArray"
>BSTArray</A
> s -&gt; <A HREF="Lcs.html#t%3APArray"
>PArray</A
> -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad-ST.html#t%3AST"
>ST</A
> s <A HREF="/usr/share/doc/ghc/html/libraries/ghc-prim-0.2.0.0/GHC-Unit.html#t%3A%28%29"
>()</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="section1"
>Documentation</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="topdecl"
><TABLE CLASS="declbar"
><TR
><TD CLASS="declname"
><A NAME="v:getChanges"
><A NAME="v%3AgetChanges"
></A
></A
><B
>getChanges</B
> :: [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>] -&gt; [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>] -&gt; [(<A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
>, [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>], [<A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
>])]</TD
><TD CLASS="declbut"
><A HREF="src/Lcs.html#getChanges"
>Source</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="doc"
>create a list of changes between a and b, each change has the form
   (starta, lima, startb, limb) which means that a[starta, lima)
   has to be replaced by b[startb, limb)
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="topdecl"
><TABLE CLASS="declbar"
><TR
><TD CLASS="declname"
><A NAME="v:aLen"
><A NAME="v%3AaLen"
></A
></A
><B
>aLen</B
> :: <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array-IArray.html#t%3AIArray"
>IArray</A
> a e =&gt; a <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> e -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
></TD
><TD CLASS="declbut"
><A HREF="src/Lcs.html#aLen"
>Source</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="topdecl"
><TABLE CLASS="declbar"
><TR
><TD CLASS="declname"
><SPAN CLASS="keyword"
>type</SPAN
> <A NAME="t:BArray"
><A NAME="t%3ABArray"
></A
></A
><B
>BArray</B
> = <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array-Unboxed.html#t%3AUArray"
>UArray</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool"
>Bool</A
></TD
><TD CLASS="declbut"
><A HREF="src/Lcs.html#BArray"
>Source</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="topdecl"
><TABLE CLASS="declbar"
><TR
><TD CLASS="declname"
><SPAN CLASS="keyword"
>type</SPAN
> <A NAME="t:PArray"
><A NAME="t%3APArray"
></A
></A
><B
>PArray</B
> = <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array.html#t%3AArray"
>Array</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> <A HREF="/usr/share/doc/ghc/html/libraries/bytestring-0.9.1.7/Data-ByteString.html#t%3AByteString"
>ByteString</A
></TD
><TD CLASS="declbut"
><A HREF="src/Lcs.html#PArray"
>Source</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="topdecl"
><TABLE CLASS="declbar"
><TR
><TD CLASS="declname"
><SPAN CLASS="keyword"
>type</SPAN
> <A NAME="t:BSTArray"
><A NAME="t%3ABSTArray"
></A
></A
><B
>BSTArray</B
> s = <A HREF="/usr/share/doc/ghc/html/libraries/array-0.3.0.1/Data-Array-ST.html#t%3ASTUArray"
>STUArray</A
> s <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Bool.html#t%3ABool"
>Bool</A
></TD
><TD CLASS="declbut"
><A HREF="src/Lcs.html#BSTArray"
>Source</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="topdecl"
><TABLE CLASS="declbar"
><TR
><TD CLASS="declname"
><A NAME="v:shiftBoundaries"
><A NAME="v%3AshiftBoundaries"
></A
></A
><B
>shiftBoundaries</B
> ::  <A HREF="Lcs.html#t%3ABSTArray"
>BSTArray</A
> s -&gt; <A HREF="Lcs.html#t%3ABSTArray"
>BSTArray</A
> s -&gt; <A HREF="Lcs.html#t%3APArray"
>PArray</A
> -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Data-Int.html#t%3AInt"
>Int</A
> -&gt; <A HREF="/usr/share/doc/ghc/html/libraries/base-4.2.0.2/Control-Monad-ST.html#t%3AST"
>ST</A
> s <A HREF="/usr/share/doc/ghc/html/libraries/ghc-prim-0.2.0.0/GHC-Unit.html#t%3A%28%29"
>()</A
></TD
><TD CLASS="declbut"
><A HREF="src/Lcs.html#shiftBoundaries"
>Source</A
></TD
></TR
></TABLE
></TD
></TR
><TR
><TD CLASS="doc"
>try to create nicer diffs by shifting around regions of changed lines
</TD
></TR
><TR
><TD CLASS="s15"
></TD
></TR
><TR
><TD CLASS="botbar"
>Produced by <A HREF="http://www.haskell.org/haddock/"
>Haddock</A
> version 2.6.1</TD
></TR
></TABLE
></BODY
></HTML
>

Perl :: Catalyst :: PostgreSQL :: RPM Valid HTML 4.01 Transitional