<!DOCTYPE html PUBLIC “-//W3C//DTD XHTML 1.0 Transitional//EN” “www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd”> <html lang=‘en’ xml:lang=‘en’ xmlns=‘www.w3.org/1999/xhtml’>

<head>
  <title>rcov/ruby/1.8/gems/diff-lcs-1.1.2/lib/diff/lcs.rb</title>
  <link href="screen.css" media="all" rel="stylesheet" type="text/css" />
  <link href="print.css" media="print" rel="stylesheet" type="text/css" />

  <meta http-equiv="Content-type" content="text/html;charset=UTF-8" />
  <script type="text/javascript" src="rcov.js"></script>
</head>
<body>
  <h1>Rspec Steps C0 Coverage Information - RCov</h1>
  <h2>rcov/ruby/1.8/gems/diff-lcs-1.1.2/lib/diff/lcs.rb</h2>

  <div class="report_table_wrapper">
    <table class='report' id='report_table'>
      <thead>
        <tr>
          <th class="left_align">Name</th>
          <th class="right_align">Total Lines</th>
          <th class="right_align">Lines of Code</th>
          <th class="left_align">Total Coverage</th>
          <th class="left_align">Code Coverage</th>
        </tr>
      </thead>
      <tbody>
        <tr>
          <td class="left_align"><a href="rcov-ruby-1_8-gems-diff-lcs-1_1_2-lib-diff-lcs_rb.html">rcov/ruby/1.8/gems/diff-lcs-1.1.2/lib/diff/lcs.rb</a></td>
          <td class='right_align'><tt>1105</tt></td>
          <td class='right_align'><tt>553</tt></td>
          <td class="left_align"><div class="percent_graph_legend"><tt class=''>46.33%</tt></div>
        <div class="percent_graph">
          <div class="covered" style="width:46px"></div>
          <div class="uncovered" style="width:54px"></div>
        </div></td>
          <td class="left_align"><div class="percent_graph_legend"><tt class=''>6.51%</tt></div>
        <div class="percent_graph">
          <div class="covered" style="width:7px"></div>
          <div class="uncovered" style="width:93px"></div>
        </div></td>
        </tr>
      </tbody>
    </table>
  </div>

  <h3>Key</h3>

  <div class="key"><pre><span class='marked'>Code reported as executed by Ruby looks like this...</span><span class='marked1'>and this: this line is also marked as covered.</span><span class='inferred'>Lines considered as run by rcov, but not reported by Ruby, look like this,</span><span class='inferred1'>and this: these lines were inferred by rcov (using simple heuristics).</span><span class='uncovered'>Finally, here's a line marked as not executed.</span></pre></div>

  <h3>Coverage Details</h3>

  <table class="details">
    <tbody>

        <tr class="inferred">
          <td><pre><a name="line1">1</a> #! /usr/env/bin ruby</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line2">2</a> #--</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line3">3</a> # Copyright 2004 Austin Ziegler &lt;diff-lcs@halostatue.ca&gt;</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line4">4</a> #   adapted from:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line5">5</a> #     Algorithm::Diff (Perl) by Ned Konz &lt;perl@bike-nomad.com&gt;</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line6">6</a> #     Smalltalk by Mario I. Wolczko &lt;mario@wolczko.com&gt;</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line7">7</a> #   implements McIlroy-Hunt diff algorithm</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line8">8</a> #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line9">9</a> # This program is free software. It may be redistributed and/or modified</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line10">10</a> # under the terms of the GPL version 2 (or later), the Perl Artistic</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line11">11</a> # licence, or the Ruby licence.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line12">12</a> # </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line13">13</a> # $Id: lcs.rb,v 1.9 2004/10/17 20:31:10 austin Exp $</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line14">14</a> #++</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line15">15</a> </pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line16">16</a> module Diff</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line17">17</a>     # = Diff::LCS 1.1.2</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line18">18</a>     # Computes &quot;intelligent&quot; differences between two sequenced Enumerables.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line19">19</a>     # This is an implementation of the McIlroy-Hunt &quot;diff&quot; algorithm for</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line20">20</a>     # Enumerable objects that include Diffable.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line21">21</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line22">22</a>     # Based on Mario I. Wolczko's &lt;mario@wolczko.com&gt; Smalltalk version</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line23">23</a>     # (1.2, 1993) and Ned Konz's &lt;perl@bike-nomad.com&gt; Perl version</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line24">24</a>     # (Algorithm::Diff).</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line25">25</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line26">26</a>     # == Synopsis</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line27">27</a>     #   require 'diff/lcs'</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line28">28</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line29">29</a>     #   seq1 = %w(a b c e h j l m n p)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line30">30</a>     #   seq2 = %w(b c d e f j k l m r s t)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line31">31</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line32">32</a>     #   lcs = Diff::LCS.LCS(seq1, seq2)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line33">33</a>     #   diffs = Diff::LCS.diff(seq1, seq2)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line34">34</a>     #   sdiff = Diff::LCS.sdiff(seq1, seq2)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line35">35</a>     #   seq = Diff::LCS.traverse_sequences(seq1, seq2, callback_obj)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line36">36</a>     #   bal = Diff::LCS.traverse_balanced(seq1, seq2, callback_obj)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line37">37</a>     #   seq2 == Diff::LCS.patch(seq1, diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line38">38</a>     #   seq2 == Diff::LCS.patch!(seq1, diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line39">39</a>     #   seq1 == Diff::LCS.unpatch(seq2, diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line40">40</a>     #   seq1 == Diff::LCS.unpatch!(seq2, diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line41">41</a>     #   seq2 == Diff::LCS.patch(seq1, sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line42">42</a>     #   seq2 == Diff::LCS.patch!(seq1, sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line43">43</a>     #   seq1 == Diff::LCS.unpatch(seq2, sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line44">44</a>     #   seq1 == Diff::LCS.unpatch!(seq2, sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line45">45</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line46">46</a>     # Alternatively, objects can be extended with Diff::LCS:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line47">47</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line48">48</a>     #   seq1.extend(Diff::LCS)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line49">49</a>     #   lcs = seq1.lcs(seq2)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line50">50</a>     #   diffs = seq1.diff(seq2)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line51">51</a>     #   sdiff = seq1.sdiff(seq2)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line52">52</a>     #   seq = seq1.traverse_sequences(seq2, callback_obj)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line53">53</a>     #   bal = seq1.traverse_balanced(seq2, callback_obj)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line54">54</a>     #   seq2 == seq1.patch(diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line55">55</a>     #   seq2 == seq1.patch!(diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line56">56</a>     #   seq1 == seq2.unpatch(diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line57">57</a>     #   seq1 == seq2.unpatch!(diffs)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line58">58</a>     #   seq2 == seq1.patch(sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line59">59</a>     #   seq2 == seq1.patch!(sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line60">60</a>     #   seq1 == seq2.unpatch(sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line61">61</a>     #   seq1 == seq2.unpatch!(sdiff)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line62">62</a>     # </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line63">63</a>     # Default extensions are provided for Array and String objects through</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line64">64</a>     # the use of 'diff/lcs/array' and 'diff/lcs/string'.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line65">65</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line66">66</a>     # == Introduction (by Mark-Jason Dominus)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line67">67</a>     # </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line68">68</a>     # &lt;em&gt;The following text is from the Perl documentation. The only</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line69">69</a>     # changes have been to make the text appear better in Rdoc&lt;/em&gt;.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line70">70</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line71">71</a>     # I once read an article written by the authors of +diff+; they said</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line72">72</a>     # that they hard worked very hard on the algorithm until they found the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line73">73</a>     # right one.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line74">74</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line75">75</a>     # I think what they ended up using (and I hope someone will correct me,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line76">76</a>     # because I am not very confident about this) was the `longest common</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line77">77</a>     # subsequence' method. In the LCS problem, you have two sequences of</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line78">78</a>     # items:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line79">79</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line80">80</a>     #    a b c d f g h j q z</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line81">81</a>     #    a b c d e f g i j k r x y z</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line82">82</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line83">83</a>     # and you want to find the longest sequence of items that is present in</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line84">84</a>     # both original sequences in the same order. That is, you want to find a</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line85">85</a>     # new sequence *S* which can be obtained from the first sequence by</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line86">86</a>     # deleting some items, and from the second sequence by deleting other</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line87">87</a>     # items. You also want *S* to be as long as possible. In this case *S*</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line88">88</a>     # is:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line89">89</a>     # </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line90">90</a>     #    a b c d f g j z</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line91">91</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line92">92</a>     # From there it's only a small step to get diff-like output:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line93">93</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line94">94</a>     #    e   h i   k   q r x y</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line95">95</a>     #    +   - +   +   - + + +</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line96">96</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line97">97</a>     # This module solves the LCS problem. It also includes a canned function</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line98">98</a>     # to generate +diff+-like output.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line99">99</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line100">100</a>     # It might seem from the example above that the LCS of two sequences is</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line101">101</a>     # always pretty obvious, but that's not always the case, especially when</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line102">102</a>     # the two sequences have many repeated elements. For example, consider</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line103">103</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line104">104</a>     #    a x b y c z p d q</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line105">105</a>     #    a b c a x b y c z</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line106">106</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line107">107</a>     # A naive approach might start by matching up the +a+ and +b+ that</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line108">108</a>     # appear at the beginning of each sequence, like this:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line109">109</a>     # </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line110">110</a>     #    a x b y c         z p d q</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line111">111</a>     #    a   b   c a b y c z</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line112">112</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line113">113</a>     # This finds the common subsequence +a b c z+. But actually, the LCS is</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line114">114</a>     # +a x b y c z+:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line115">115</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line116">116</a>     #          a x b y c z p d q</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line117">117</a>     #    a b c a x b y c z</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line118">118</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line119">119</a>     # == Author</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line120">120</a>     # This version is by Austin Ziegler &lt;diff-lcs@halostatue.ca&gt;.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line121">121</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line122">122</a>     # It is based on the Perl Algorithm::Diff by Ned Konz</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line123">123</a>     # &lt;perl@bike-nomad.com&gt;, copyright &amp;copy; 2000 - 2002 and the Smalltalk</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line124">124</a>     # diff version by Mario I. Wolczko &lt;mario@wolczko.com&gt;, copyright &amp;copy;</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line125">125</a>     # 1993. Documentation includes work by Mark-Jason Dominus.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line126">126</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line127">127</a>     # == Licence</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line128">128</a>     # Copyright &amp;copy; 2004 Austin Ziegler</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line129">129</a>     # This program is free software; you can redistribute it and/or modify it</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line130">130</a>     # under the same terms as Ruby, or alternatively under the Perl Artistic</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line131">131</a>     # licence.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line132">132</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line133">133</a>     # == Credits</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line134">134</a>     # Much of the documentation is taken directly from the Perl</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line135">135</a>     # Algorithm::Diff implementation and was written originally by Mark-Jason</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line136">136</a>     # Dominus &lt;mjd-perl-diff@plover.com&gt; and later by Ned Konz. The basic Ruby</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line137">137</a>     # implementation was re-ported from the Smalltalk implementation, available</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line138">138</a>     # at ftp://st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line139">139</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line140">140</a>     # #sdiff and #traverse_balanced were written for the Perl version by Mike</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line141">141</a>     # Schilli &lt;m@perlmeister.com&gt;.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line142">142</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line143">143</a>     # &quot;The algorithm is described in &lt;em&gt;A Fast Algorithm for Computing Longest</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line144">144</a>     # Common Subsequences&lt;/em&gt;, CACM, vol.20, no.5, pp.350-353, May 1977, with</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line145">145</a>     # a few minor improvements to improve the speed.&quot;</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line146">146</a>   module LCS</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line147">147</a>     VERSION = '1.1.2'</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line148">148</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line149">149</a> end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line150">150</a> </pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line151">151</a> require 'diff/lcs/callbacks'</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line152">152</a> </pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line153">153</a> module Diff::LCS</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line154">154</a>     # Returns an Array containing the longest common subsequence(s) between</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line155">155</a>     # +self+ and +other+. See Diff::LCS#LCS.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line156">156</a>     #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line157">157</a>     #   lcs = seq1.lcs(seq2)</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line158">158</a>   def lcs(other, &amp;block) #:yields self[ii] if there are matched subsequences:</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line159">159</a>     Diff::LCS.LCS(self, other, &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line160">160</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line161">161</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line162">162</a>     # Returns the difference set between +self+ and +other+. See</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line163">163</a>     # Diff::LCS#diff.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line164">164</a>   def diff(other, callbacks = nil, &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line165">165</a>     Diff::LCS::diff(self, other, callbacks, &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line166">166</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line167">167</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line168">168</a>     # Returns the balanced (&quot;side-by-side&quot;) difference set between +self+ and</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line169">169</a>     # +other+. See Diff::LCS#sdiff.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line170">170</a>   def sdiff(other, callbacks = nil, &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line171">171</a>     Diff::LCS::sdiff(self, other, callbacks, &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line172">172</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line173">173</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line174">174</a>     # Traverses the discovered longest common subsequences between +self+ and</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line175">175</a>     # +other+. See Diff::LCS#traverse_sequences.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line176">176</a>   def traverse_sequences(other, callbacks = nil, &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line177">177</a>     traverse_sequences(self, other, callbacks || Diff::LCS::YieldingCallbacks,</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line178">178</a>                        &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line179">179</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line180">180</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line181">181</a>     # Traverses the discovered longest common subsequences between +self+ and</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line182">182</a>     # +other+ using the alternate, balanced algorithm. See</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line183">183</a>     # Diff::LCS#traverse_balanced.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line184">184</a>   def traverse_balanced(other, callbacks = nil, &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line185">185</a>     traverse_balanced(self, other, callbacks || Diff::LCS::YieldingCallbacks,</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line186">186</a>                       &amp;block)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line187">187</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line188">188</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line189">189</a>     # Attempts to patch a copy of +self+ with the provided +patchset+. See</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line190">190</a>     # Diff::LCS#patch.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line191">191</a>   def patch(patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line192">192</a>     Diff::LCS::patch(self.dup, patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line193">193</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line194">194</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line195">195</a>     # Attempts to unpatch a copy of +self+ with the provided +patchset+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line196">196</a>     # See Diff::LCS#patch.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line197">197</a>   def unpatch(patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line198">198</a>     Diff::LCS::unpatch(self.dup, patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line199">199</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line200">200</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line201">201</a>     # Attempts to patch +self+ with the provided +patchset+. See</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line202">202</a>     # Diff::LCS#patch!. Does no autodiscovery.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line203">203</a>   def patch!(patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line204">204</a>     Diff::LCS::patch!(self, patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line205">205</a>   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line206">206</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line207">207</a>     # Attempts to unpatch +self+ with the provided +patchset+. See</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line208">208</a>     # Diff::LCS#unpatch. Does no autodiscovery.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line209">209</a>   def unpatch!(patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line210">210</a>     Diff::LCS::unpatch!(self, patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line211">211</a>   end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line212">212</a> end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line213">213</a> </pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line214">214</a> module Diff::LCS</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line215">215</a>   class &lt;&lt; self</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line216">216</a>       # Given two sequenced Enumerables, LCS returns an Array containing their</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line217">217</a>       # longest common subsequences.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line218">218</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line219">219</a>       #   lcs = Diff::LCS.LCS(seq1, seq2)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line220">220</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line221">221</a>       # This array whose contents is such that:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line222">222</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line223">223</a>       #   lcs.each_with_index do |ee, ii|</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line224">224</a>       #     assert(ee.nil? || (seq1[ii] == seq2[ee]))</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line225">225</a>       #   end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line226">226</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line227">227</a>       # If a block is provided, the matching subsequences will be yielded from</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line228">228</a>       # +seq1+ in turn and may be modified before they are placed into the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line229">229</a>       # returned Array of subsequences.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line230">230</a>     def LCS(seq1, seq2, &amp;block) #:yields seq1[ii] for each matched:</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line231">231</a>       matches = Diff::LCS.__lcs(seq1, seq2)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line232">232</a>       ret = []</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line233">233</a>       matches.each_with_index do |ee, ii|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line234">234</a>         unless matches[ii].nil?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line235">235</a>           if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line236">236</a>             ret &lt;&lt; (yield seq1[ii])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line237">237</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line238">238</a>             ret &lt;&lt; seq1[ii]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line239">239</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line240">240</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line241">241</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line242">242</a>       ret</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line243">243</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line244">244</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line245">245</a>       # Diff::LCS.diff computes the smallest set of additions and deletions</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line246">246</a>       # necessary to turn the first sequence into the second, and returns a</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line247">247</a>       # description of these changes.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line248">248</a>       # </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line249">249</a>       # See Diff::LCS::DiffCallbacks for the default behaviour. An alternate</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line250">250</a>       # behaviour may be implemented with Diff::LCS::ContextDiffCallbacks.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line251">251</a>       # If a Class argument is provided for +callbacks+, #diff will attempt</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line252">252</a>       # to initialise it. If the +callbacks+ object (possibly initialised)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line253">253</a>       # responds to #finish, it will be called.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line254">254</a>     def diff(seq1, seq2, callbacks = nil, &amp;block) # :yields diff changes:</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line255">255</a>       callbacks ||= Diff::LCS::DiffCallbacks</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line256">256</a>       if callbacks.kind_of?(Class)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line257">257</a>         cb = callbacks.new rescue callbacks</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line258">258</a>         callbacks = cb</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line259">259</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line260">260</a>       traverse_sequences(seq1, seq2, callbacks)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line261">261</a>       callbacks.finish if callbacks.respond_to?(:finish)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line262">262</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line263">263</a>       if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line264">264</a>         res = callbacks.diffs.map do |hunk|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line265">265</a>           if hunk.kind_of?(Array)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line266">266</a>             hunk = hunk.map { |block| yield block }</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line267">267</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line268">268</a>             yield hunk</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line269">269</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line270">270</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line271">271</a>         res</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line272">272</a>       else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line273">273</a>         callbacks.diffs</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line274">274</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line275">275</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line276">276</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line277">277</a>       # Diff::LCS.sdiff computes all necessary components to show two sequences</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line278">278</a>       # and their minimized differences side by side, just like the Unix</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line279">279</a>       # utility &lt;em&gt;sdiff&lt;/em&gt; does:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line280">280</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line281">281</a>       #     old        &lt;     -</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line282">282</a>       #     same             same</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line283">283</a>       #     before     |     after</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line284">284</a>       #     -          &gt;     new</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line285">285</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line286">286</a>       # See Diff::LCS::SDiffCallbacks for the default behaviour. An alternate</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line287">287</a>       # behaviour may be implemented with Diff::LCS::ContextDiffCallbacks. If</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line288">288</a>       # a Class argument is provided for +callbacks+, #diff will attempt to</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line289">289</a>       # initialise it. If the +callbacks+ object (possibly initialised)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line290">290</a>       # responds to #finish, it will be called.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line291">291</a>     def sdiff(seq1, seq2, callbacks = nil, &amp;block) #:yields diff changes:</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line292">292</a>       callbacks ||= Diff::LCS::SDiffCallbacks</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line293">293</a>       if callbacks.kind_of?(Class)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line294">294</a>         cb = callbacks.new rescue callbacks</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line295">295</a>         callbacks = cb</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line296">296</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line297">297</a>       traverse_balanced(seq1, seq2, callbacks)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line298">298</a>       callbacks.finish if callbacks.respond_to?(:finish)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line299">299</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line300">300</a>       if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line301">301</a>         res = callbacks.diffs.map do |hunk|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line302">302</a>           if hunk.kind_of?(Array)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line303">303</a>             hunk = hunk.map { |block| yield block }</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line304">304</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line305">305</a>             yield hunk</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line306">306</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line307">307</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line308">308</a>         res</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line309">309</a>       else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line310">310</a>         callbacks.diffs</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line311">311</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line312">312</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line313">313</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line314">314</a>       # Diff::LCS.traverse_sequences is the most general facility provided by this</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line315">315</a>       # module; +diff+ and +LCS+ are implemented as calls to it.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line316">316</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line317">317</a>       # The arguments to #traverse_sequences are the two sequences to</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line318">318</a>       # traverse, and a callback object, like this:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line319">319</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line320">320</a>       #   traverse_sequences(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line321">321</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line322">322</a>       # #diff is implemented with #traverse_sequences.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line323">323</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line324">324</a>       # == Callback Methods</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line325">325</a>       # Optional callback methods are &lt;em&gt;emphasized&lt;/em&gt;.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line326">326</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line327">327</a>       # callbacks#match::               Called when +a+ and +b+ are pointing</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line328">328</a>       #                                 to common elements in +A+ and +B+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line329">329</a>       # callbacks#discard_a::           Called when +a+ is pointing to an</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line330">330</a>       #                                 element not in +B+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line331">331</a>       # callbacks#discard_b::           Called when +b+ is pointing to an</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line332">332</a>       #                                 element not in +A+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line333">333</a>       # &lt;em&gt;callbacks#finished_a&lt;/em&gt;:: Called when +a+ has reached the end of</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line334">334</a>       #                                 sequence +A+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line335">335</a>       # &lt;em&gt;callbacks#finished_b&lt;/em&gt;:: Called when +b+ has reached the end of</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line336">336</a>       #                                 sequence +B+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line337">337</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line338">338</a>       # == Algorithm</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line339">339</a>       #       a---+</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line340">340</a>       #           v</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line341">341</a>       #       A = a b c e h j l m n p</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line342">342</a>       #       B = b c d e f j k l m r s t</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line343">343</a>       #           ^</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line344">344</a>       #       b---+</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line345">345</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line346">346</a>       # If there are two arrows (+a+ and +b+) pointing to elements of</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line347">347</a>       # sequences +A+ and +B+, the arrows will initially point to the first</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line348">348</a>       # elements of their respective sequences. #traverse_sequences will</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line349">349</a>       # advance the arrows through the sequences one element at a time,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line350">350</a>       # calling a method on the user-specified callback object before each</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line351">351</a>       # advance. It will advance the arrows in such a way that if there are</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line352">352</a>       # elements &lt;tt&gt;A[ii]&lt;/tt&gt; and &lt;tt&gt;B[jj]&lt;/tt&gt; which are both equal and</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line353">353</a>       # part of the longest common subsequence, there will be some moment</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line354">354</a>       # during the execution of #traverse_sequences when arrow +a+ is pointing</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line355">355</a>       # to &lt;tt&gt;A[ii]&lt;/tt&gt; and arrow +b+ is pointing to &lt;tt&gt;B[jj]&lt;/tt&gt;. When</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line356">356</a>       # this happens, #traverse_sequences will call &lt;tt&gt;callbacks#match&lt;/tt&gt;</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line357">357</a>       # and then it will advance both arrows.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line358">358</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line359">359</a>       # Otherwise, one of the arrows is pointing to an element of its sequence</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line360">360</a>       # that is not part of the longest common subsequence.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line361">361</a>       # #traverse_sequences will advance that arrow and will call</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line362">362</a>       # &lt;tt&gt;callbacks#discard_a&lt;/tt&gt; or &lt;tt&gt;callbacks#discard_b&lt;/tt&gt;, depending</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line363">363</a>       # on which arrow it advanced. If both arrows point to elements that are</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line364">364</a>       # not part of the longest common subsequence, then #traverse_sequences</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line365">365</a>       # will advance one of them and call the appropriate callback, but it is</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line366">366</a>       # not specified which it will call.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line367">367</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line368">368</a>       # The methods for &lt;tt&gt;callbacks#match&lt;/tt&gt;, &lt;tt&gt;callbacks#discard_a&lt;/tt&gt;,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line369">369</a>       # and &lt;tt&gt;callbacks#discard_b&lt;/tt&gt; are invoked with an event comprising</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line370">370</a>       # the action (&quot;=&quot;, &quot;+&quot;, or &quot;-&quot;, respectively), the indicies +ii+ and</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line371">371</a>       # +jj+, and the elements &lt;tt&gt;A[ii]&lt;/tt&gt; and &lt;tt&gt;B[jj]&lt;/tt&gt;. Return</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line372">372</a>       # values are discarded by #traverse_sequences.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line373">373</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line374">374</a>       # === End of Sequences</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line375">375</a>       # If arrow +a+ reaches the end of its sequence before arrow +b+ does,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line376">376</a>       # #traverse_sequence try to call &lt;tt&gt;callbacks#finished_a&lt;/tt&gt; with the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line377">377</a>       # last index and element of +A+ (&lt;tt&gt;A[-1]&lt;/tt&gt;) and the current index</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line378">378</a>       # and element of +B+ (&lt;tt&gt;B[jj]&lt;/tt&gt;). If &lt;tt&gt;callbacks#finished_a&lt;/tt&gt;</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line379">379</a>       # does not exist, then &lt;tt&gt;callbacks#discard_b&lt;/tt&gt; will be called on</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line380">380</a>       # each element of +B+ until the end of the sequence is reached (the call</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line381">381</a>       # will be done with &lt;tt&gt;A[-1]&lt;/tt&gt; and &lt;tt&gt;B[jj]&lt;/tt&gt; for each element).</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line382">382</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line383">383</a>       # If +b+ reaches the end of +B+ before +a+ reaches the end of +A+,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line384">384</a>       # &lt;tt&gt;callbacks#finished_b&lt;/tt&gt; will be called with the current index</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line385">385</a>       # and element of +A+ (&lt;tt&gt;A[ii]&lt;/tt&gt;) and the last index and element of</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line386">386</a>       # +B+ (&lt;tt&gt;A[-1]&lt;/tt&gt;). Again, if &lt;tt&gt;callbacks#finished_b&lt;/tt&gt; does not</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line387">387</a>       # exist on the callback object, then &lt;tt&gt;callbacks#discard_a&lt;/tt&gt; will</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line388">388</a>       # be called on each element of +A+ until the end of the sequence is</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line389">389</a>       # reached (&lt;tt&gt;A[ii]&lt;/tt&gt; and &lt;tt&gt;B[-1]&lt;/tt&gt;).</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line390">390</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line391">391</a>       # There is a chance that one additional &lt;tt&gt;callbacks#discard_a&lt;/tt&gt; or</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line392">392</a>       # &lt;tt&gt;callbacks#discard_b&lt;/tt&gt; will be called after the end of the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line393">393</a>       # sequence is reached, if +a+ has not yet reached the end of +A+ or +b+</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line394">394</a>       # has not yet reached the end of +B+.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line395">395</a>     def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks, &amp;block) #:yields change events:</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line396">396</a>       matches = Diff::LCS.__lcs(seq1, seq2)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line397">397</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line398">398</a>       run_finished_a = run_finished_b = false</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line399">399</a>       string = seq1.kind_of?(String)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line400">400</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line401">401</a>       a_size = seq1.size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line402">402</a>       b_size = seq2.size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line403">403</a>       ai = bj = 0</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line404">404</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line405">405</a>       (0 .. matches.size).each do |ii|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line406">406</a>         b_line = matches[ii]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line407">407</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line408">408</a>         ax = string ? seq1[ii, 1] : seq1[ii]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line409">409</a>         bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line410">410</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line411">411</a>         if b_line.nil?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line412">412</a>           unless ax.nil?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line413">413</a>             event = Diff::LCS::ContextChange.new('-', ii, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line414">414</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line415">415</a>             callbacks.discard_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line416">416</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line417">417</a>         else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line418">418</a>           loop do</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line419">419</a>             break unless bj &lt; b_line</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line420">420</a>             bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line421">421</a>             event = Diff::LCS::ContextChange.new('+', ii, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line422">422</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line423">423</a>             callbacks.discard_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line424">424</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line425">425</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line426">426</a>           bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line427">427</a>           event = Diff::LCS::ContextChange.new('=', ii, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line428">428</a>           event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line429">429</a>           callbacks.match(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line430">430</a>           bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line431">431</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line432">432</a>         ai = ii</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line433">433</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line434">434</a>       ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line435">435</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line436">436</a>         # The last entry (if any) processed was a match. +ai+ and +bj+ point</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line437">437</a>         # just past the last matching lines in their sequences.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line438">438</a>       while (ai &lt; a_size) or (bj &lt; b_size)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line439">439</a>           # last A?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line440">440</a>         if ai == a_size and bj &lt; b_size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line441">441</a>           if callbacks.respond_to?(:finished_a) and not run_finished_a</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line442">442</a>             ax = string ? seq1[-1, 1] : seq1[-1]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line443">443</a>             bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line444">444</a>             event = Diff::LCS::ContextChange.new('&gt;', (a_size - 1), ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line445">445</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line446">446</a>             callbacks.finished_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line447">447</a>             run_finished_a = true</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line448">448</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line449">449</a>             ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line450">450</a>             loop do</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line451">451</a>               bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line452">452</a>               event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line453">453</a>               event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line454">454</a>               callbacks.discard_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line455">455</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line456">456</a>               break unless bj &lt; b_size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line457">457</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line458">458</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line459">459</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line460">460</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line461">461</a>           # last B?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line462">462</a>         if bj == b_size and ai &lt; a_size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line463">463</a>           if callbacks.respond_to?(:finished_b) and not run_finished_b</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line464">464</a>             ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line465">465</a>             bx = string ? seq2[-1, 1] : seq2[-1]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line466">466</a>             event = Diff::LCS::ContextChange.new('&lt;', ai, ax, (b_size - 1), bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line467">467</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line468">468</a>             callbacks.finished_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line469">469</a>             run_finished_b = true</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line470">470</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line471">471</a>             bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line472">472</a>             loop do</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line473">473</a>               ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line474">474</a>               event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line475">475</a>               event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line476">476</a>               callbacks.discard_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line477">477</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line478">478</a>               break unless bj &lt; b_size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line479">479</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line480">480</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line481">481</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line482">482</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line483">483</a>         if ai &lt; a_size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line484">484</a>           ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line485">485</a>           bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line486">486</a>           event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line487">487</a>           event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line488">488</a>           callbacks.discard_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line489">489</a>           ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line490">490</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line491">491</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line492">492</a>         if bj &lt; b_size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line493">493</a>           ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line494">494</a>           bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line495">495</a>           event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line496">496</a>           event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line497">497</a>           callbacks.discard_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line498">498</a>           bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line499">499</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line500">500</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line501">501</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line502">502</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line503">503</a>       # #traverse_balanced is an alternative to #traverse_sequences. It</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line504">504</a>       # uses a different algorithm to iterate through the entries in the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line505">505</a>       # computed longest common subsequence. Instead of viewing the changes as</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line506">506</a>       # insertions or deletions from one of the sequences, #traverse_balanced</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line507">507</a>       # will report &lt;em&gt;changes&lt;/em&gt; between the sequences. To represent a</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line508">508</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line509">509</a>       # The arguments to #traverse_balanced are the two sequences to traverse</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line510">510</a>       # and a callback object, like this:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line511">511</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line512">512</a>       #   traverse_balanced(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line513">513</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line514">514</a>       # #sdiff is implemented with #traverse_balanced.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line515">515</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line516">516</a>       # == Callback Methods</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line517">517</a>       # Optional callback methods are &lt;em&gt;emphasized&lt;/em&gt;.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line518">518</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line519">519</a>       # callbacks#match::               Called when +a+ and +b+ are pointing</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line520">520</a>       #                                 to common elements in +A+ and +B+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line521">521</a>       # callbacks#discard_a::           Called when +a+ is pointing to an</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line522">522</a>       #                                 element not in +B+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line523">523</a>       # callbacks#discard_b::           Called when +b+ is pointing to an</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line524">524</a>       #                                 element not in +A+.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line525">525</a>       # &lt;em&gt;callbacks#change&lt;/em&gt;::     Called when +a+ and +b+ are pointing</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line526">526</a>       #                                 to the same relative position, but</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line527">527</a>       #                                 &lt;tt&gt;A[a]&lt;/tt&gt; and &lt;tt&gt;B[b]&lt;/tt&gt; are</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line528">528</a>       #                                 not the same; a &lt;em&gt;change&lt;/em&gt; has</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line529">529</a>       #                                 occurred.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line530">530</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line531">531</a>       # #traverse_balanced might be a bit slower than #traverse_sequences,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line532">532</a>       # noticable only while processing huge amounts of data.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line533">533</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line534">534</a>       # The +sdiff+ function of this module is implemented as call to</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line535">535</a>       # #traverse_balanced.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line536">536</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line537">537</a>       # == Algorithm</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line538">538</a>       #       a---+</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line539">539</a>       #           v</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line540">540</a>       #       A = a b c e h j l m n p</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line541">541</a>       #       B = b c d e f j k l m r s t</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line542">542</a>       #           ^</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line543">543</a>       #       b---+</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line544">544</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line545">545</a>       # === Matches</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line546">546</a>       # If there are two arrows (+a+ and +b+) pointing to elements of</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line547">547</a>       # sequences +A+ and +B+, the arrows will initially point to the first</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line548">548</a>       # elements of their respective sequences. #traverse_sequences will</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line549">549</a>       # advance the arrows through the sequences one element at a time,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line550">550</a>       # calling a method on the user-specified callback object before each</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line551">551</a>       # advance. It will advance the arrows in such a way that if there are</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line552">552</a>       # elements &lt;tt&gt;A[ii]&lt;/tt&gt; and &lt;tt&gt;B[jj]&lt;/tt&gt; which are both equal and</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line553">553</a>       # part of the longest common subsequence, there will be some moment</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line554">554</a>       # during the execution of #traverse_sequences when arrow +a+ is pointing</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line555">555</a>       # to &lt;tt&gt;A[ii]&lt;/tt&gt; and arrow +b+ is pointing to &lt;tt&gt;B[jj]&lt;/tt&gt;. When</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line556">556</a>       # this happens, #traverse_sequences will call &lt;tt&gt;callbacks#match&lt;/tt&gt;</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line557">557</a>       # and then it will advance both arrows.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line558">558</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line559">559</a>       # === Discards</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line560">560</a>       # Otherwise, one of the arrows is pointing to an element of its sequence</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line561">561</a>       # that is not part of the longest common subsequence.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line562">562</a>       # #traverse_sequences will advance that arrow and will call</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line563">563</a>       # &lt;tt&gt;callbacks#discard_a&lt;/tt&gt; or &lt;tt&gt;callbacks#discard_b&lt;/tt&gt;,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line564">564</a>       # depending on which arrow it advanced.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line565">565</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line566">566</a>       # === Changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line567">567</a>       # If both +a+ and +b+ point to elements that are not part of the longest</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line568">568</a>       # common subsequence, then #traverse_sequences will try to call</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line569">569</a>       # &lt;tt&gt;callbacks#change&lt;/tt&gt; and advance both arrows. If</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line570">570</a>       # &lt;tt&gt;callbacks#change&lt;/tt&gt; is not implemented, then</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line571">571</a>       # &lt;tt&gt;callbacks#discard_a&lt;/tt&gt; and &lt;tt&gt;callbacks#discard_b&lt;/tt&gt; will be</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line572">572</a>       # called in turn.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line573">573</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line574">574</a>       # The methods for &lt;tt&gt;callbacks#match&lt;/tt&gt;, &lt;tt&gt;callbacks#discard_a&lt;/tt&gt;,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line575">575</a>       # &lt;tt&gt;callbacks#discard_b&lt;/tt&gt;, and &lt;tt&gt;callbacks#change&lt;/tt&gt; are</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line576">576</a>       # invoked with an event comprising the action (&quot;=&quot;, &quot;+&quot;, &quot;-&quot;, or &quot;!&quot;,</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line577">577</a>       # respectively), the indicies +ii+ and +jj+, and the elements</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line578">578</a>       # &lt;tt&gt;A[ii]&lt;/tt&gt; and &lt;tt&gt;B[jj]&lt;/tt&gt;. Return values are discarded by</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line579">579</a>       # #traverse_balanced.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line580">580</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line581">581</a>       # === Context</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line582">582</a>       # Note that +ii+ and +jj+ may not be the same index position, even if</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line583">583</a>       # +a+ and +b+ are considered to be pointing to matching or changed</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line584">584</a>       # elements.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line585">585</a>     def traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line586">586</a>       matches = Diff::LCS.__lcs(seq1, seq2)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line587">587</a>       a_size = seq1.size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line588">588</a>       b_size = seq2.size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line589">589</a>       ai = bj = mb = 0</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line590">590</a>       ma = -1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line591">591</a>       string = seq1.kind_of?(String)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line592">592</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line593">593</a>         # Process all the lines in the match vector.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line594">594</a>       loop do</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line595">595</a>           # Find next match indices +ma+ and +mb+</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line596">596</a>         loop do</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line597">597</a>           ma += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line598">598</a>           break unless ma &lt; matches.size and matches[ma].nil?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line599">599</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line600">600</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line601">601</a>         break if ma &gt;= matches.size # end of matches?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line602">602</a>         mb = matches[ma]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line603">603</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line604">604</a>           # Change(seq2)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line605">605</a>         while (ai &lt; ma) or (bj &lt; mb)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line606">606</a>           ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line607">607</a>           bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line608">608</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line609">609</a>           case [(ai &lt; ma), (bj &lt; mb)]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line610">610</a>           when [true, true]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line611">611</a>             if callbacks.respond_to?(:change)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line612">612</a>               event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line613">613</a>               event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line614">614</a>               callbacks.change(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line615">615</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line616">616</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line617">617</a>             else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line618">618</a>               event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line619">619</a>               event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line620">620</a>               callbacks.discard_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line621">621</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line622">622</a>               ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line623">623</a>               event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line624">624</a>               event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line625">625</a>               callbacks.discard_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line626">626</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line627">627</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line628">628</a>           when [true, false]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line629">629</a>             event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line630">630</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line631">631</a>             callbacks.discard_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line632">632</a>             ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line633">633</a>           when [false, true]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line634">634</a>             event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line635">635</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line636">636</a>             callbacks.discard_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line637">637</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line638">638</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line639">639</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line640">640</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line641">641</a>           # Match</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line642">642</a>         ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line643">643</a>         bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line644">644</a>         event = Diff::LCS::ContextChange.new('=', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line645">645</a>         event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line646">646</a>         callbacks.match(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line647">647</a>         ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line648">648</a>         bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line649">649</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line650">650</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line651">651</a>       while (ai &lt; a_size) or (bj &lt; b_size)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line652">652</a>         ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line653">653</a>         bx = string ? seq2[bj, 1] : seq2[bj]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line654">654</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line655">655</a>         case [(ai &lt; a_size), (bj &lt; b_size)]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line656">656</a>         when [true, true]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line657">657</a>           if callbacks.respond_to?(:change)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line658">658</a>             event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line659">659</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line660">660</a>             callbacks.change(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line661">661</a>             ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line662">662</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line663">663</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line664">664</a>             event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line665">665</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line666">666</a>             callbacks.discard_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line667">667</a>             ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line668">668</a>             ax = string ? seq1[ai, 1] : seq1[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line669">669</a>             event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line670">670</a>             event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line671">671</a>             callbacks.discard_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line672">672</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line673">673</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line674">674</a>         when [true, false]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line675">675</a>           event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line676">676</a>           event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line677">677</a>           callbacks.discard_a(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line678">678</a>           ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line679">679</a>         when [false, true]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line680">680</a>           event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line681">681</a>           event = yield event if block_given?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line682">682</a>           callbacks.discard_b(event)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line683">683</a>           bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line684">684</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line685">685</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line686">686</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line687">687</a> </pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line688">688</a>     PATCH_MAP = { #:nodoc:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line689">689</a>       :patch =&gt; { '+' =&gt; '+', '-' =&gt; '-', '!' =&gt; '!', '=' =&gt; '=' },</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line690">690</a>       :unpatch =&gt; { '+' =&gt; '-', '-' =&gt; '+', '!' =&gt; '!', '=' =&gt; '=' }</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line691">691</a>     }</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line692">692</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line693">693</a>       # Given a patchset, convert the current version to the new</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line694">694</a>       # version. If +direction+ is not specified (must be</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line695">695</a>       # &lt;tt&gt;:patch&lt;/tt&gt; or &lt;tt&gt;:unpatch&lt;/tt&gt;), then discovery of the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line696">696</a>       # direction of the patch will be attempted.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line697">697</a>     def patch(src, patchset, direction = nil)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line698">698</a>       string = src.kind_of?(String)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line699">699</a>         # Start with a new empty type of the source's class</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line700">700</a>       res = src.class.new</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line701">701</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line702">702</a>         # Normalize the patchset.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line703">703</a>       patchset = __normalize_patchset(patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line704">704</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line705">705</a>       direction ||= Diff::LCS.__diff_direction(src, patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line706">706</a>       direction ||= :patch</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line707">707</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line708">708</a>       ai = bj = 0</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line709">709</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line710">710</a>       patchset.each do |change|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line711">711</a>           # Both Change and ContextChange support #action</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line712">712</a>         action = PATCH_MAP[direction][change.action]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line713">713</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line714">714</a>         case change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line715">715</a>         when Diff::LCS::ContextChange</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line716">716</a>           case direction</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line717">717</a>           when :patch</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line718">718</a>             el = change.new_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line719">719</a>             op = change.old_position</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line720">720</a>             np = change.new_position</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line721">721</a>           when :unpatch</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line722">722</a>             el = change.old_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line723">723</a>             op = change.new_position</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line724">724</a>             np = change.old_position</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line725">725</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line726">726</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line727">727</a>           case action</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line728">728</a>           when '-' # Remove details from the old string</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line729">729</a>             while ai &lt; op</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line730">730</a>               res &lt;&lt; (string ? src[ai, 1] : src[ai])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line731">731</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line732">732</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line733">733</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line734">734</a>             ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line735">735</a>           when '+'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line736">736</a>             while bj &lt; np</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line737">737</a>               res &lt;&lt; (string ? src[ai, 1] : src[ai])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line738">738</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line739">739</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line740">740</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line741">741</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line742">742</a>             res &lt;&lt; el</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line743">743</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line744">744</a>           when '='</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line745">745</a>               # This only appears in sdiff output with the SDiff callback.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line746">746</a>               # Therefore, we only need to worry about dealing with a single</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line747">747</a>               # element.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line748">748</a>             res &lt;&lt; el</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line749">749</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line750">750</a>             ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line751">751</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line752">752</a>           when '!'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line753">753</a>             while ai &lt; op</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line754">754</a>               res &lt;&lt; (string ? src[ai, 1] : src[ai])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line755">755</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line756">756</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line757">757</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line758">758</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line759">759</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line760">760</a>             ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line761">761</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line762">762</a>             res &lt;&lt; el</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line763">763</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line764">764</a>         when Diff::LCS::Change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line765">765</a>           case action</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line766">766</a>           when '-'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line767">767</a>             while ai &lt; change.position</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line768">768</a>               res &lt;&lt; (string ? src[ai, 1] : src[ai])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line769">769</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line770">770</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line771">771</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line772">772</a>             ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line773">773</a>           when '+'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line774">774</a>             while bj &lt; change.position</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line775">775</a>               res &lt;&lt; (string ? src[ai, 1] : src[ai])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line776">776</a>               ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line777">777</a>               bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line778">778</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line779">779</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line780">780</a>             bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line781">781</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line782">782</a>             res &lt;&lt; change.element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line783">783</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line784">784</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line785">785</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line786">786</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line787">787</a>       while ai &lt; src.size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line788">788</a>         res &lt;&lt; (string ? src[ai, 1] : src[ai])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line789">789</a>         ai += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line790">790</a>         bj += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line791">791</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line792">792</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line793">793</a>       res</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line794">794</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line795">795</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line796">796</a>       # Given a set of patchset, convert the current version to the prior</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line797">797</a>       # version. Does no auto-discovery.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line798">798</a>     def unpatch!(src, patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line799">799</a>       Diff::LCS.patch(src, patchset, :unpatch)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line800">800</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line801">801</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line802">802</a>       # Given a set of patchset, convert the current version to the next</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line803">803</a>       # version. Does no auto-discovery.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line804">804</a>     def patch!(src, patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line805">805</a>       Diff::LCS.patch(src, patchset, :patch)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line806">806</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line807">807</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line808">808</a> # private</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line809">809</a>       # Compute the longest common subsequence between the sequenced Enumerables</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line810">810</a>       # +a+ and +b+. The result is an array whose contents is such that</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line811">811</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line812">812</a>       #     result = Diff::LCS.__lcs(a, b)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line813">813</a>       #     result.each_with_index do |e, ii|</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line814">814</a>       #       assert_equal(a[ii], b[e]) unless e.nil?</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line815">815</a>       #     end</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line816">816</a>     def __lcs(a, b)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line817">817</a>       a_start = b_start = 0</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line818">818</a>       a_finish = a.size - 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line819">819</a>       b_finish = b.size - 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line820">820</a>       vector = []</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line821">821</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line822">822</a>         # Prune off any common elements at the beginning...</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line823">823</a>       while (a_start &lt;= a_finish) and</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line824">824</a>             (b_start &lt;= b_finish) and</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line825">825</a>             (a[a_start] == b[b_start])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line826">826</a>         vector[a_start] = b_start</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line827">827</a>         a_start += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line828">828</a>         b_start += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line829">829</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line830">830</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line831">831</a>         # Now the end...</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line832">832</a>       while (a_start &lt;= a_finish) and</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line833">833</a>             (b_start &lt;= b_finish) and</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line834">834</a>             (a[a_finish] == b[b_finish])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line835">835</a>         vector[a_finish] = b_finish</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line836">836</a>         a_finish -= 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line837">837</a>         b_finish -= 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line838">838</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line839">839</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line840">840</a>         # Now, compute the equivalence classes of positions of elements.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line841">841</a>       b_matches = Diff::LCS.__position_hash(b, b_start .. b_finish)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line842">842</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line843">843</a>       thresh = []</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line844">844</a>       links = []</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line845">845</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line846">846</a>       (a_start .. a_finish).each do |ii|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line847">847</a>         ai = a.kind_of?(String) ? a[ii, 1] : a[ii]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line848">848</a>         bm = b_matches[ai]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line849">849</a>         kk = nil</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line850">850</a>         bm.reverse_each do |jj|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line851">851</a>           if kk and (thresh[kk] &gt; jj) and (thresh[kk - 1] &lt; jj)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line852">852</a>             thresh[kk] = jj</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line853">853</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line854">854</a>             kk = Diff::LCS.__replace_next_larger(thresh, jj, kk)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line855">855</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line856">856</a>           links[kk] = [ (kk &gt; 0) ? links[kk - 1] : nil, ii, jj ] unless kk.nil?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line857">857</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line858">858</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line859">859</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line860">860</a>       unless thresh.empty?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line861">861</a>         link = links[thresh.size - 1]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line862">862</a>         while not link.nil?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line863">863</a>           vector[link[1]] = link[2]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line864">864</a>           link = link[0]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line865">865</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line866">866</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line867">867</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line868">868</a>       vector</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line869">869</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line870">870</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line871">871</a>       # Find the place at which +value+ would normally be inserted into the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line872">872</a>       # Enumerable. If that place is already occupied by +value+, do nothing</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line873">873</a>       # and return +nil+. If the place does not exist (i.e., it is off the end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line874">874</a>       # of the Enumerable), add it to the end. Otherwise, replace the element</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line875">875</a>       # at that point with +value+. It is assumed that the Enumerable's values</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line876">876</a>       # are numeric.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line877">877</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line878">878</a>       # This operation preserves the sort order.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line879">879</a>     def __replace_next_larger(enum, value, last_index = nil)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line880">880</a>         # Off the end?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line881">881</a>       if enum.empty? or (value &gt; enum[-1])</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line882">882</a>         enum &lt;&lt; value</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line883">883</a>         return enum.size - 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line884">884</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line885">885</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line886">886</a>         # Binary search for the insertion point</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line887">887</a>       last_index ||= enum.size</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line888">888</a>       first_index = 0</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line889">889</a>       while (first_index &lt;= last_index)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line890">890</a>         ii = (first_index + last_index) &gt;&gt; 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line891">891</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line892">892</a>         found = enum[ii]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line893">893</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line894">894</a>         if value == found</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line895">895</a>           return nil</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line896">896</a>         elsif value &gt; found</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line897">897</a>           first_index = ii + 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line898">898</a>         else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line899">899</a>           last_index = ii - 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line900">900</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line901">901</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line902">902</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line903">903</a>         # The insertion point is in first_index; overwrite the next larger</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line904">904</a>         # value.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line905">905</a>       enum[first_index] = value</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line906">906</a>       return first_index</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line907">907</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line908">908</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line909">909</a>       # If +vector+ maps the matching elements of another collection onto this</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line910">910</a>       # Enumerable, compute the inverse +vector+ that maps this Enumerable</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line911">911</a>       # onto the collection. (Currently unused.)</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line912">912</a>     def __inverse_vector(a, vector)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line913">913</a>       inverse = a.dup</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line914">914</a>       (0 ... vector.size).each do |ii|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line915">915</a>         inverse[vector[ii]] = ii unless vector[ii].nil?</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line916">916</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line917">917</a>       inverse</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line918">918</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line919">919</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line920">920</a>       # Returns a hash mapping each element of an Enumerable to the set of</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line921">921</a>       # positions it occupies in the Enumerable, optionally restricted to the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line922">922</a>       # elements specified in the range of indexes specified by +interval+.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line923">923</a>     def __position_hash(enum, interval = 0 .. -1)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line924">924</a>       hash = Hash.new { |hh, kk| hh[kk] = [] }</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line925">925</a>       interval.each do |ii|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line926">926</a>         kk = enum.kind_of?(String) ? enum[ii, 1] : enum[ii]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line927">927</a>         hash[kk] &lt;&lt; ii</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line928">928</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line929">929</a>       hash</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line930">930</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line931">931</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line932">932</a>       # Examine the patchset and the source to see in which direction the</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line933">933</a>       # patch should be applied.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line934">934</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line935">935</a>       # WARNING: By default, this examines the whole patch, so this could take</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line936">936</a>       # some time. This also works better with Diff::LCS::ContextChange or</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line937">937</a>       # Diff::LCS::Change as its source, as an array will cause the creation</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line938">938</a>       # of one of the above.</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line939">939</a>     def __diff_direction(src, patchset, limit = nil)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line940">940</a>       count = left = left_miss = right = right_miss = 0</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line941">941</a>       string = src.kind_of?(String)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line942">942</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line943">943</a>       patchset.each do |change|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line944">944</a>         count += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line945">945</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line946">946</a>         case change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line947">947</a>         when Diff::LCS::Change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line948">948</a>             # With a simplistic change, we can't tell the difference between</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line949">949</a>             # the left and right on '!' actions, so we ignore those. On '='</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line950">950</a>             # actions, if there's a miss, we miss both left and right.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line951">951</a>           element = string ? src[change.position, 1] : src[change.position]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line952">952</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line953">953</a>           case change.action</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line954">954</a>           when '-'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line955">955</a>             if element == change.element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line956">956</a>               left += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line957">957</a>             else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line958">958</a>               left_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line959">959</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line960">960</a>           when '+'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line961">961</a>             if element == change.element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line962">962</a>               right += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line963">963</a>             else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line964">964</a>               right_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line965">965</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line966">966</a>           when '='</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line967">967</a>             if element != change.element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line968">968</a>               left_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line969">969</a>               right_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line970">970</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line971">971</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line972">972</a>         when Diff::LCS::ContextChange</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line973">973</a>           case change.action</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line974">974</a>           when '-' # Remove details from the old string</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line975">975</a>             element = string ? src[change.old_position, 1] : src[change.old_position]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line976">976</a>             if element == change.old_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line977">977</a>               left += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line978">978</a>             else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line979">979</a>               left_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line980">980</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line981">981</a>           when '+'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line982">982</a>             element = string ? src[change.new_position, 1] : src[change.new_position]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line983">983</a>             if element == change.new_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line984">984</a>               right += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line985">985</a>             else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line986">986</a>               right_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line987">987</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line988">988</a>           when '='</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line989">989</a>             le = string ? src[change.old_position, 1] : src[change.old_position]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line990">990</a>             re = string ? src[change.new_position, 1] : src[change.new_position]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line991">991</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line992">992</a>             left_miss += 1 if le != change.old_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line993">993</a>             right_miss += 1 if re != change.new_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line994">994</a>           when '!'</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line995">995</a>             element = string ? src[change.old_position, 1] : src[change.old_position]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line996">996</a>             if element == change.old_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line997">997</a>               left += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line998">998</a>             else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line999">999</a>               element = string ? src[change.new_position, 1] : src[change.new_position]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1000">1000</a>               if element == change.new_element</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1001">1001</a>                 right += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1002">1002</a>               else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1003">1003</a>                 left_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1004">1004</a>                 right_miss += 1</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1005">1005</a>               end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1006">1006</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1007">1007</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1008">1008</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1009">1009</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1010">1010</a>         break if not limit.nil? and count &gt; limit</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1011">1011</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1012">1012</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1013">1013</a>       no_left = (left == 0) and (left_miss &gt;= 0)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1014">1014</a>       no_right = (right == 0) and (right_miss &gt;= 0)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1015">1015</a> </pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1016">1016</a>       case [no_left, no_right]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1017">1017</a>       when [false, true]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1018">1018</a>         return :patch</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1019">1019</a>       when [true, false]</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1020">1020</a>         return :unpatch</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1021">1021</a>       else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1022">1022</a>         raise &quot;The provided patchset does not appear to apply to the provided value as either source or destination value.&quot;</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1023">1023</a>       end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1024">1024</a>     end</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1025">1025</a> </pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1026">1026</a>       # Normalize the patchset. A patchset is always a sequence of changes, but</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1027">1027</a>       # how those changes are represented may vary, depending on how they were</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1028">1028</a>       # generated. In all cases we support, we also support the array</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1029">1029</a>       # representation of the changes. The formats are:</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1030">1030</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1031">1031</a>       #   [ # patchset &lt;- Diff::LCS.diff(a, b)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1032">1032</a>       #     [ # one or more hunks</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1033">1033</a>       #       Diff::LCS::Change # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1034">1034</a>       #     ] ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1035">1035</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1036">1036</a>       #   [ # patchset, equivalent to the above</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1037">1037</a>       #     [ # one or more hunks</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1038">1038</a>       #       [ action, line, value ] # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1039">1039</a>       #     ] ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1040">1040</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1041">1041</a>       #   [ # patchset &lt;- Diff::LCS.diff(a, b, Diff::LCS::ContextDiffCallbacks)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1042">1042</a>       #     #       OR &lt;- Diff::LCS.sdiff(a, b, Diff::LCS::ContextDiffCallbacks)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1043">1043</a>       #     [ # one or more hunks</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1044">1044</a>       #       Diff::LCS::ContextChange # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1045">1045</a>       #     ] ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1046">1046</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1047">1047</a>       #   [ # patchset, equivalent to the above</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1048">1048</a>       #     [ # one or more hunks</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1049">1049</a>       #       [ action, [ old line, old value ], [ new line, new value ] ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1050">1050</a>       #         # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1051">1051</a>       #     ] ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1052">1052</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1053">1053</a>       #   [ # patchset &lt;- Diff::LCS.sdiff(a, b)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1054">1054</a>       #     #       OR &lt;- Diff::LCS.diff(a, b, Diff::LCS::SDiffCallbacks)</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1055">1055</a>       #     Diff::LCS::ContextChange # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1056">1056</a>       #   ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1057">1057</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1058">1058</a>       #   [ # patchset, equivalent to the above</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1059">1059</a>       #     [ action, [ old line, old value ], [ new line, new value ] ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1060">1060</a>       #       # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1061">1061</a>       #   ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1062">1062</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1063">1063</a>       # The result of this will be either of the following.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1064">1064</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1065">1065</a>       #   [ # patchset</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1066">1066</a>       #     Diff::LCS::ContextChange # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1067">1067</a>       #   ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1068">1068</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1069">1069</a>       #   [ # patchset</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1070">1070</a>       #     Diff::LCS::Change # one or more changes</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1071">1071</a>       #   ]</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1072">1072</a>       #</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1073">1073</a>       # If either of the above is provided, it will be returned as such.</pre></td>
        </tr>

        <tr class="inferred">
          <td><pre><a name="line1074">1074</a>       #</pre></td>
        </tr>

        <tr class="marked">
          <td><pre><a name="line1075">1075</a>     def __normalize_patchset(patchset)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1076">1076</a>       patchset.map do |hunk|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1077">1077</a>         case hunk</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1078">1078</a>         when Diff::LCS::ContextChange, Diff::LCS::Change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1079">1079</a>           hunk</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1080">1080</a>         when Array</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1081">1081</a>           if (not hunk[0].kind_of?(Array)) and hunk[1].kind_of?(Array) and hunk[2].kind_of?(Array)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1082">1082</a>             Diff::LCS::ContextChange.from_a(hunk)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1083">1083</a>           else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1084">1084</a>             hunk.map do |change|</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1085">1085</a>               case change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1086">1086</a>               when Diff::LCS::ContextChange, Diff::LCS::Change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1087">1087</a>                 change</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1088">1088</a>               when Array</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1089">1089</a>                   # change[1] will ONLY be an array in a ContextChange#to_a call.</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1090">1090</a>                   # In Change#to_a, it represents the line (singular).</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1091">1091</a>                 if change[1].kind_of?(Array)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1092">1092</a>                   Diff::LCS::ContextChange.from_a(change)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1093">1093</a>                 else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1094">1094</a>                   Diff::LCS::Change.from_a(change)</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1095">1095</a>                 end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1096">1096</a>               end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1097">1097</a>             end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1098">1098</a>           end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1099">1099</a>         else</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1100">1100</a>           raise ArgumentError, &quot;Cannot normalise a hunk of class #{hunk.class}.&quot;</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1101">1101</a>         end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1102">1102</a>       end.flatten</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1103">1103</a>     end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1104">1104</a>   end</pre></td>
        </tr>

        <tr class="uncovered">
          <td><pre><a name="line1105">1105</a> end</pre></td>
        </tr>

    </tbody>
  </table>

  <p>Generated on Fri Apr 22 17:22:41 -0700 2011 with <a href="http://github.com/relevance/rcov">rcov 0.9.8</a></p>

</body>

</html>