public Fragment(Differences.FragmentType ThisType, string Part, int Location)
 {
     sb = new StringBuilder();
     Type = ThisType;
     Position = Location;
     sb.Append(Part);
 }

 private ExecutionBlock ScriptDifferences(Differences differences)
 {
     var work = new Work();
     work.BuildFromDifferences(differences, Options.Default, true);
     ExecutionBlock block = work.ExecutionBlock;
     return block;
 }

        /// <summary>
        /// Build a code that can be used to transform one version of a file into another.
        /// </summary>
        public static string BuildDiffCode(Differences differences)
        {
            var sb = new StringBuilder();
            int pos = 0;
            int del = 0;
            string ins = "";

            foreach (Fragment frag in differences) {

                if (frag.Type == Differences.FragmentType.Unchanged) {
                    pos += del;
                    pos -= ins.Length;
                    if (del > 0 || ins.Length > 0) {
                        WriteDiffCode(sb, pos-del, del, ins);
                    }
                    pos += frag.Length;
                    del = 0;
                    ins = "";
                } else if (frag.Type == Differences.FragmentType.Deleted) {
                    del += frag.Length;
                } else if (frag.Type == Differences.FragmentType.Inserted) {
                    pos += frag.Length;
                    ins += frag.SplitPart;
                } else {
                    throw new Exception("broken frag type");
                }
            }

            // Don't forget the last one!
            if (del > 0 || ins.Length > 0) {
                WriteDiffCode(sb, pos - del, del, ins);
            }

            return sb.ToString();
        }

 public virtual AttributeNode GetClosestMatch(AttributeNode/*!*/ nd1, AttributeList/*!*/ list1, AttributeList list2, int list1pos, ref int list2start,
   TrivialHashtable/*!*/ matchedNodes, out Differences closestDifferences, out int list2pos) {
   closestDifferences = null; list2pos = -1;
   if (list2 == null) return null;
   if (nd1 == null || list1 == null || matchedNodes == null ||  list1pos < 0 || list1pos >= list1.Count || list2start < 0 || list2start >= list2.Count) {
     Debug.Assert(false); return null;
   }
   AttributeNode closest = null;
   Differences winnerSoFar = null;
   for (int j = list2start, m = list2.Count; j < m; j++){
     AttributeNode nd2 = list2[j];
     if (list2start == j) list2start++;
     if (nd2 == null) continue;
     if (matchedNodes[nd2.UniqueKey] != null) continue;
     Differences diff = this.GetDifferences(nd1, nd2);
     if (diff == null){Debug.Assert(false); continue;}
     if (diff.Similarity <= 0.5){
       //Not a good enough match
       if (list2start == j+1) list2start--; //The next call to GetClosestMatch will start looking at list2start, so this node will be considered then
       continue; //ignore it for the rest of this call
     }
     if (winnerSoFar != null && winnerSoFar.Similarity >= diff.Similarity) continue;
     winnerSoFar = closestDifferences = diff;
     closest = nd2;
     list2pos = j;
     if (diff.NumberOfDifferences == 0) return closest; //Perfect match, no need to look for other matches
   }
   if (closest != null){
     //^ assert winnerSoFar != null;
     //closest is closer to nd1 than any other node in list2, but this is no good if some other node in list1 has a better claim on closest
     for (int i = list1pos+1, n = list1.Count; i < n; i++){
       AttributeNode nd1alt = list1[i];
       if (nd1alt == null) continue;
       if (matchedNodes[nd1alt.UniqueKey] != null) continue;
       Differences diff = this.GetDifferences(nd1alt, closest);
       if (diff == null){Debug.Assert(false); continue;}
       if (diff.Similarity <= winnerSoFar.Similarity) continue;
       //nd1alt has a better claim on closest. See if it wants closest.
       Differences diff2;
       int j, k = list2start;
       AttributeNode nd2alt = this.GetClosestMatch(nd1alt, list1, list2, i, ref k,  matchedNodes, out diff2, out j);
       if (nd2alt != closest){
         Debug.Assert(nd2alt != null && diff2 != null && diff2.Similarity >= diff.Similarity);
         continue; //nd1alt prefers nd2alt to closest, so closest is still available
       }
       //nd1alt wants closest, take it out of the running
       matchedNodes[closest.UniqueKey] = nd1alt;
       //Now that closest is out of the running, try again
       k = list2start;
       AttributeNode newClosest = this.GetClosestMatch(nd1, list1, list2, i, ref k, matchedNodes, out winnerSoFar, out list2pos);
       //put closest back in the running so that the next call to this routine will pick it up
       matchedNodes[closest.UniqueKey] = closest;
       closest = newClosest;
       break;
     }
   }
   closestDifferences = winnerSoFar;
   return closest;
 }

        protected void Page_Load(object sender, EventArgs e)
        {
            string left = File.ReadAllText(Server.MapPath("~/Examples/DeOfficiis.txt"));
            //string left = File.ReadAllText(Server.MapPath("~/Examples/DeOfficiis_Recombined.txt"));

            string right = File.ReadAllText(Server.MapPath("~/Examples/DeOfficiis_Altered.txt"));
            //string right = File.ReadAllText(Server.MapPath("~/Examples/DeOfficiis_Minor_Altered.txt"));
            //string right = File.ReadAllText(Server.MapPath("~/Examples/TotallyDifferent.txt"));

            GC.Collect(3, GCCollectionMode.Forced); // give the algorithm a fair shot...
            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            var differences = new Differences(left, right, Differences.PerWord);

            sw.Stop();

            Repeater1.DataSource = from d in differences
                                   select new Fragment(d.Type,
                                       HttpContext.Current.Server.HtmlEncode(d.SplitPart).Replace("\n", "<br/>"), d.Position);
            Repeater1.DataBind();

            Response.Write("DocDiff took " + sw.Elapsed.TotalSeconds + " seconds<br/>");

            // This gives a code to convert LEFT into RIGHT
            // Is a revision repository, the older file would be RIGHT, and the newer be LEFT.
            sw.Reset();
            sw.Start();
            byte[] final_out = DiffCode.StorageDiffCode(differences);
            sw.Stop();
            Response.Write("DocDiff-code took " + sw.Elapsed.TotalSeconds + " seconds<br/>");

            double sizePc = ((double)final_out.Length / right.Length) * 100.0;
            Response.Write("<br/>DocDiff code size: " + (final_out.Length / 1024) + "KiB which is " + sizePc.ToString("0.0") + "% of the resulting file");
            Response.Write("<br/>diff code contains " + differences.Count() + " alterations.");

            sw.Reset();
            sw.Start();
            File.WriteAllText(Server.MapPath("~/Examples/DeOfficiis_Recombined.txt"),
                DiffCode.BuildRevision(left, DiffCode.BuildDiffCode(differences)));
            sw.Stop();
            Response.Write("<br/>Rebuild and write took " + sw.Elapsed.TotalSeconds + " seconds<br/>");
        }

        private void LogChanges(string zipFilePath, Differences differences)
        {
            Console.WriteLine("In {0}...", zipFilePath);
            Logger.Info("In {0}...", zipFilePath);

            var added = differences.Added;
            var changed = differences.Changed;
            var removed = differences.Removed;

            int numberOfDifferences = added.Count + changed.Count + removed.Count;

            if (numberOfDifferences > 0)
            {
                Console.WriteLine("Number of differences = {0}.", numberOfDifferences);
                Logger.Info("Number of differences = {0}.", numberOfDifferences);
            }

            if (added.Any())
            {
                Console.WriteLine("Added...");
                Logger.Info("Added...");
                added.Keys.ToList().ForEach(k => { Console.WriteLine(k); Logger.Info(k); });
            }

            if (changed.Any())
            {
                Console.WriteLine("Changed...");
                Logger.Info("Changed...");
                changed.Keys.ToList().ForEach(k => { Console.WriteLine(k); Logger.Info(k); });
            }

            if (removed.Any())
            {
                Console.WriteLine("Removed...");
                Logger.Info("Removed...");
                removed.Keys.ToList().ForEach(k => { Console.WriteLine(k); Logger.Info(k); });
            }
        }

 public virtual Differences GetMemberDifferences(Member member1, Member member2) {
   if (member1 == null || member2 == null) return new Differences(member1, member2);
   if (this.memberDifferencesMapFor == null) this.memberDifferencesMapFor = new TrivialHashtable();
   TrivialHashtable map = this.memberDifferencesMapFor[member1.UniqueKey] as TrivialHashtable;
   if (map == null) this.memberDifferencesMapFor[member1.UniqueKey] = map = new TrivialHashtable();
   Differences differences = map[member2.UniqueKey] as Differences;
   if (differences == null){
     map[member2.UniqueKey] = differences = new Differences(member1, member2);
     if (member1 == member2) differences.NumberOfSimilarities++;
   }
   return differences;
 }

    public virtual Differences VisitQueryUpdate(QueryUpdate update1, QueryUpdate update2){
      Differences differences = new Differences(update1, update2);
      if (update1 == null || update2 == null){
        if (update1 != update2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryUpdate changes = (QueryUpdate)update2.Clone();
      QueryUpdate deletions = (QueryUpdate)update2.Clone();
      QueryUpdate insertions = (QueryUpdate)update2.Clone();

      //      update1.Context;
      //      update1.Source;
      //      update1.UpdateList;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }    

    public virtual Differences VisitQueryTypeFilter(QueryTypeFilter filter1, QueryTypeFilter filter2){
      Differences differences = new Differences(filter1, filter2);
      if (filter1 == null || filter2 == null){
        if (filter1 != filter2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryTypeFilter changes = (QueryTypeFilter)filter2.Clone();
      QueryTypeFilter deletions = (QueryTypeFilter)filter2.Clone();
      QueryTypeFilter insertions = (QueryTypeFilter)filter2.Clone();

      //      filter1.Constraint;
      //      filter1.Source;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQuerySingleton(QuerySingleton singleton1, QuerySingleton singleton2){
      Differences differences = new Differences(singleton1, singleton2);
      if (singleton1 == null || singleton2 == null){
        if (singleton1 != singleton2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QuerySingleton changes = (QuerySingleton)singleton2.Clone();
      QuerySingleton deletions = (QuerySingleton)singleton2.Clone();
      QuerySingleton insertions = (QuerySingleton)singleton2.Clone();

      //singleton1.Source;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryQuantifiedExpression(QueryQuantifiedExpression qqe1, QueryQuantifiedExpression qqe2){
      Differences differences = new Differences(qqe1, qqe2);
      if (qqe1 == null || qqe2 == null){
        if (qqe1 != qqe2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryQuantifiedExpression changes = (QueryQuantifiedExpression)qqe2.Clone();
      QueryQuantifiedExpression deletions = (QueryQuantifiedExpression)qqe2.Clone();
      QueryQuantifiedExpression insertions = (QueryQuantifiedExpression)qqe2.Clone();

      //      qqe1.Expression;
      //      qqe1.Left;
      //      qqe1.Right;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

 public virtual Differences VisitQueryRollback(QueryRollback qr1, QueryRollback qr2){
   Differences differences = new Differences(qr1, qr2);
   if (qr1 == null || qr2 == null){
     if (qr1 != qr2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
   }else
     differences.Changes = null;
   return differences;
 }

    public virtual Differences VisitQueryGroupBy(QueryGroupBy groupby1, QueryGroupBy groupby2){
      Differences differences = new Differences(groupby1, groupby2);
      if (groupby1 == null || groupby2 == null){
        if (groupby1 != groupby2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryGroupBy changes = (QueryGroupBy)groupby2.Clone();
      QueryGroupBy deletions = (QueryGroupBy)groupby2.Clone();
      QueryGroupBy insertions = (QueryGroupBy)groupby2.Clone();

      //      groupby1.AggregateList;
      //      groupby1.GroupContext;
      //      groupby1.GroupList;
      //      groupby1.Having;
      //      groupby1.HavingContext;
      //      groupby1.Source;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryExists(QueryExists exists1, QueryExists exists2){
      Differences differences = new Differences(exists1, exists2);
      if (exists1 == null || exists2 == null){
        if (exists1 != exists2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryExists changes = (QueryExists)exists2.Clone();
      QueryExists deletions = (QueryExists)exists2.Clone();
      QueryExists insertions = (QueryExists)exists2.Clone();

      //      exists1.Source;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryDistinct(QueryDistinct distinct1, QueryDistinct distinct2){
      Differences differences = new Differences(distinct1, distinct2);
      if (distinct1 == null || distinct2 == null){
        if (distinct1 != distinct2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryDistinct changes = (QueryDistinct)distinct2.Clone();
      QueryDistinct deletions = (QueryDistinct)distinct2.Clone();
      QueryDistinct insertions = (QueryDistinct)distinct2.Clone();

      //      distinct1.Context;
      //      distinct1.Group;
      //      distinct1.GroupTarget;
      //      distinct1.Source;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryPosition(QueryPosition position1, QueryPosition position2){
      Differences differences = new Differences(position1, position2);
      if (position1 == null || position2 == null){
        if (position1 != position2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryPosition changes = (QueryPosition)position2.Clone();
      QueryPosition deletions = (QueryPosition)position2.Clone();
      QueryPosition insertions = (QueryPosition)position2.Clone();

      //position1.Context;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryProject(QueryProject project1, QueryProject project2){
      Differences differences = new Differences(project1, project2);
      if (project1 == null || project2 == null){
        if (project1 != project2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryProject changes = (QueryProject)project2.Clone();
      QueryProject deletions = (QueryProject)project2.Clone();
      QueryProject insertions = (QueryProject)project2.Clone();

      //      project1.Context;
      //      project1.Members;
      //      project1.ProjectedType;
      //      project1.ProjectionList;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryGeneratedType(QueryGeneratedType qgt1, QueryGeneratedType qgt2){
      Differences differences = new Differences(qgt1, qgt2);
      if (qgt1 == null || qgt2 == null){
        if (qgt1 != qgt2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryGeneratedType changes = (QueryGeneratedType)qgt2.Clone();
      QueryGeneratedType deletions = (QueryGeneratedType)qgt2.Clone();
      QueryGeneratedType insertions = (QueryGeneratedType)qgt2.Clone();

      //qgt1.Type;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryQuantifier(QueryQuantifier qq1, QueryQuantifier qq2){
      Differences differences = new Differences(qq1, qq2);
      if (qq1 == null || qq2 == null){
        if (qq1 != qq2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryQuantifier changes = (QueryQuantifier)qq2.Clone();
      QueryQuantifier deletions = (QueryQuantifier)qq2.Clone();
      QueryQuantifier insertions = (QueryQuantifier)qq2.Clone();

      //      qq1.Expression;
      //      qq1.Target;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }

    public virtual Differences VisitQueryInsert(QueryInsert insert1, QueryInsert insert2){
      Differences differences = new Differences(insert1, insert2);
      if (insert1 == null || insert2 == null){
        if (insert1 != insert2) differences.NumberOfDifferences++; else differences.NumberOfSimilarities++;
        return differences;
      }
      QueryInsert changes = (QueryInsert)insert2.Clone();
      QueryInsert deletions = (QueryInsert)insert2.Clone();
      QueryInsert insertions = (QueryInsert)insert2.Clone();

      //      insert1.HintList;
      //      insert1.InsertList;
      //      insert1.IsBracket;
      //      insert1.Location;
      //      insert1.Position;

      if (differences.NumberOfDifferences == 0){
        differences.Changes = null;
        differences.Deletions = null;
        differences.Insertions = null;
      }else{
        differences.Changes = changes;
        differences.Deletions = deletions;
        differences.Insertions = insertions;
      }
      return differences;
    }