Created
July 7, 2009 02:03
-
-
Save vilterp/141839 to your computer and use it in GitHub Desktop.
very unoptimized diff implementation & test harness based on http://is.gd/1ppey
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <html> | |
| <head> | |
| <title>Diff</title> | |
| <style type="text/css" media="screen"> | |
| ins { | |
| background-color: lightgreen; | |
| text-decoration: none; | |
| } | |
| del { | |
| background-color: pink; | |
| text-decoration: none; | |
| } | |
| </style> | |
| <script src="./jquery.js" type="text/javascript" charset="utf-8"></script> | |
| <script src="./diff.js" type="text/javascript" charset="utf-8"></script> | |
| <script type="text/javascript" charset="utf-8"> | |
| function recompute_diff() { | |
| var left = $('#area1').val() | |
| var right = $('#area2').val() | |
| $('#output').html(new Diff(left,right).to_html()) | |
| } | |
| $(document).ready(function(){ | |
| recompute_diff() // if something's there cuz of autocomplete | |
| $('#area1').keyup(recompute_diff) | |
| $('#area2').keyup(recompute_diff) | |
| }) | |
| </script> | |
| </head> | |
| <body> | |
| <p> | |
| <textarea id="area1" rows="8" cols="40"></textarea> | |
| </p> | |
| <p> | |
| <textarea id="area2" rows="8" cols="40"></textarea> | |
| </p> | |
| <p> | |
| <pre id="output"></pre> | |
| </p> | |
| </body> | |
| </html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| var LEAVE = 1 | |
| var INSERT = 2 | |
| var DELETE = 3 | |
| function Edit(type, value) { | |
| this.type = type | |
| this.value = value | |
| } | |
| function Diff(left, right) { | |
| this.left = left | |
| this.right = right | |
| this.edits = this.compute(0,0).toArray() | |
| this.cleanup() | |
| } | |
| Diff.prototype.compute = function(left_start, right_start) { | |
| if(left_start == this.left.length) { | |
| if(right_start == this.right.length) { | |
| return new LinkedList() | |
| } else { | |
| var ins_right = new LinkedList() | |
| for(var i=right_start; i < this.right.length; i++) { | |
| ins_right.append(new Edit(INSERT,this.right[i])) | |
| } | |
| return ins_right | |
| } | |
| } else if(right_start == this.right.length) { | |
| var del_left = new LinkedList() | |
| for(var i=left_start; i < this.left.length; i++) { | |
| del_left.append(new Edit(DELETE,this.left[i])) | |
| } | |
| return del_left | |
| } else { | |
| if(this.left[left_start] == this.right[right_start]) { | |
| var path = new LinkedList() | |
| path.append(new Edit(LEAVE,this.left[left_start])) | |
| path.concat(this.compute(left_start+1,right_start+1)) | |
| return path | |
| } else { | |
| var path1 = new LinkedList() | |
| path1.append(new Edit(INSERT,this.right[right_start])) | |
| path1.concat(this.compute(left_start,right_start+1)) | |
| var path2 = new LinkedList() | |
| path2.append(new Edit(DELETE,this.left[left_start])) | |
| path2.concat(this.compute(left_start+1,right_start)) | |
| if(path1.length > path2.length) { | |
| return path2 | |
| } else { | |
| return path1 | |
| } | |
| } | |
| } | |
| } | |
| Diff.prototype.cleanup = function() { | |
| var cleaned_up = [] | |
| for(var i=0; i < this.edits.length; i++) { | |
| if(cleaned_up.length == 0) { | |
| cleaned_up.push(this.edits[i]) | |
| } else { | |
| var c = this.edits[i] | |
| var p = cleaned_up[cleaned_up.length-1] | |
| if(c.type == p.type) { | |
| cleaned_up[cleaned_up.length-1] = new Edit(c.type,p.value + c.value) | |
| } else { | |
| cleaned_up.push(c) | |
| } | |
| } | |
| } | |
| return cleaned_up | |
| } | |
| Diff.prototype.to_html = function(diff_result) { | |
| var ans = '' | |
| for(var i=0; i < this.edits.length; i++) { | |
| var edit = this.edits[i] | |
| if(edit.type == LEAVE) { | |
| ans += edit.value | |
| } else if(edit.type == INSERT) { | |
| ans += '<ins>' + edit.value + '</ins>' | |
| } else { | |
| ans += '<del>' + edit.value + '</del>' | |
| } | |
| } | |
| return ans | |
| } | |
| function LinkedListItem(value, next) { | |
| this.value = value | |
| this.next = next | |
| } | |
| function LinkedList(initvalues) { | |
| this.header = null | |
| this.tail = null | |
| this.length = 0 | |
| } | |
| LinkedList.prototype.append = function(value) { | |
| if(this.header == null) { | |
| this.header = new LinkedListItem(value,null) | |
| this.tail = this.header | |
| } else { | |
| this.tail.next = new LinkedListItem(value,null) | |
| this.tail = this.tail.next | |
| } | |
| this.length ++ | |
| return this | |
| } | |
| LinkedList.prototype.concat = function(other) { | |
| this.tail.next = other.header | |
| this.tail = other.tail | |
| this.length += other.length | |
| } | |
| LinkedList.prototype.toArray = function() { | |
| var ans = [] | |
| var cur = this.header | |
| while(cur != null) { | |
| ans.push(cur.value) | |
| cur = cur.next | |
| } | |
| return ans | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment