Coverage Report

Coverage Report - org.crosswire.common.diff.Commonality

Classes in this File

0/66

0/42

 /**
  * Distribution License:
  * JSword is free software; you can redistribute it and/or modify it under
  * the terms of the GNU Lesser General Public License, version 2.1 or later
  * as published by the Free Software Foundation. This program is distributed
  * in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
  * the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * See the GNU Lesser General Public License for more details.
  *
  * The License is available on the internet at:
  *      http://www.gnu.org/copyleft/lgpl.html
  * or by writing to:
  *      Free Software Foundation, Inc.
  *      59 Temple Place - Suite 330
  *      Boston, MA 02111-1307, USA
  *
  * © CrossWire Bible Society, 2007 - 2016
  *
  */
 package org.crosswire.common.diff;
 
 /**
  * A Commonality is shared text at the beginning, middle or end of two strings.
  * 
  * Based on the LGPL Diff_Match_Patch v1.5 javascript of Neil Fraser, Copyright (C) 2006<br>
  * <a href="http://neil.fraser.name/software/diff_match_patch/">http://neil.fraser.name/software/diff_match_patch/</a>
  * 
  * @see gnu.lgpl.License The GNU Lesser General Public License for details.
  * @author DM Smith
  */
 public final class Commonality {
     /**
      * This is a utility class, therefore the constructor is private.
      */
     private Commonality() {
     }
 
     /**
      * Find the length of a common prefix.
      * 
      * @param source
      *            First string
      * @param target
      *            Second string
      * @return The number of characters common to the start of each string.
      */
     public static int prefix(final String source, final String target) {
         int pointermin = 0;
         int pointermax = Math.min(source.length(), target.length());
         int pointermid = pointermax;
         while (pointermin < pointermid) {
             if (source.regionMatches(0, target, 0, pointermid)) {
                 pointermin = pointermid;
             } else {
                 pointermax = pointermid;
             }
             pointermid = (pointermax - pointermin) / 2 + pointermin;
         }
 
         return pointermid;
     }
 
     /**
      * Find the length of a common suffix.
      * 
      * @param source
      *            First string
      * @param target
      *            Second string
      * @return The number of characters common to the end of each string.
      */
     public static int suffix(final String source, final String target) {
         int pointermin = 0;
         int pointermax = Math.min(source.length(), target.length());
         int pointermid = pointermax;
         while (pointermin < pointermid) {
             if (source.regionMatches(source.length() - pointermid, target, target.length() - pointermid, pointermid)) {
                 pointermin = pointermid;
             } else {
                 pointermax = pointermid;
             }
             pointermid = (pointermax - pointermin) / 2 + pointermin;
         }
 
         return pointermid;
     }
 
     /**
      * Do the two texts share a substring which is at least half the length of
      * the longer text?
      * 
      * @param source
      *            Baseline string
      * @param target
      *            Changed string
      * @return a CommonMiddle Or null if there was no match.
      */
     public static CommonMiddle halfMatch(final String source, final String target) {
         int sourceLength = source.length();
         int targetLength = target.length();
         String longText = sourceLength > targetLength ? source : target;
         String shortText = sourceLength > targetLength ? target : source;
         int longTextLength = Math.max(sourceLength, targetLength);
         if (longTextLength < 10 || shortText.length() < 1) {
             return null; // Pointless.
         }
 
         // First check if the second quarter is the seed for a half-match.
         CommonMiddle hm1 = halfMatch(longText, shortText, ceil(longTextLength, 4));
         // Check again based on the third quarter.
         CommonMiddle hm2 = halfMatch(longText, shortText, ceil(longTextLength, 2));
         CommonMiddle hm = null;
         if (hm1 == null && hm2 == null) {
             return null;
         } else if (hm2 == null) {
             hm = hm1;
         } else if (hm1 == null) {
             hm = hm2;
         } else {
             // Both matched. Select the longest.
             hm = hm1.getCommonality().length() > hm2.getCommonality().length() ? hm1 : hm2;
         }
 
         // A half-match was found, sort out the return data.
         if (sourceLength > targetLength) {
             return hm;
         }
 
         // While hm cannot be null our QA checker can't figure that out.
         if (hm != null) {
             return new CommonMiddle(hm.getTargetPrefix(), hm.getTargetSuffix(), hm.getSourcePrefix(), hm.getSourceSuffix(), hm.getCommonality());
         }
         return null;
     }
 
     /**
      * Does a substring of shortText exist within longText such that the
      * substring is at least half the length of longText?
      * 
      * @param longText
      *            Longer string
      * @param shortText
      *            Shorter string
      * @param startIndex
      *            Start index of quarter length substring within longText
      * @return Five element String array, containing the prefix of longText, the
      *         suffix of longText, the prefix of shortText, the suffix of
      *         shortText and the common middle. Or null if there was no match.
      */
     private static CommonMiddle halfMatch(final String longText, final String shortText, final int startIndex) {
         // Start with a 1/4 length substring at position i as a seed.
         String seed = longText.substring(startIndex, startIndex + (longText.length() / 4));
         int j = -1;
         String common = "";
         String longTextPrefix = "";
         String longTextSuffix = "";
         String shortTextPrefix = "";
         String shortTextSuffix = "";
         while ((j = shortText.indexOf(seed, j + 1)) != -1) {
             int prefixLength = Commonality.prefix(longText.substring(startIndex), shortText.substring(j));
             int suffixLength = Commonality.suffix(longText.substring(0, startIndex), shortText.substring(0, j));
             if (common.length() < (prefixLength + suffixLength)) {
                 common = shortText.substring(j - suffixLength, j) + shortText.substring(j, j + prefixLength);
                 longTextPrefix = longText.substring(0, startIndex - suffixLength);
                 longTextSuffix = longText.substring(startIndex + prefixLength);
                 shortTextPrefix = shortText.substring(0, j - suffixLength);
                 shortTextSuffix = shortText.substring(j + prefixLength);
             }
         }
 
         if (common.length() >= longText.length() / 2) {
             return new CommonMiddle(longTextPrefix, longTextSuffix, shortTextPrefix, shortTextSuffix, common);
         }
 
         return null;
     }
 
     private static int ceil(int number, int divisor) {
         assert divisor > 0;
         int result = number / divisor + ((number % divisor) > 0 ? 1 : 0);
         // assert result == (int) Math.ceil(((double) number) / ((double) divisor));
         return result;
     }
 
 }

1		/**
2		* Distribution License:
3		* JSword is free software; you can redistribute it and/or modify it under
4		* the terms of the GNU Lesser General Public License, version 2.1 or later
5		* as published by the Free Software Foundation. This program is distributed
6		* in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
7		* the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
8		* See the GNU Lesser General Public License for more details.
9		*
10		* The License is available on the internet at:
11		* http://www.gnu.org/copyleft/lgpl.html
12		* or by writing to:
13		* Free Software Foundation, Inc.
14		* 59 Temple Place - Suite 330
15		* Boston, MA 02111-1307, USA
16		*
17		* © CrossWire Bible Society, 2007 - 2016
18		*
19		*/
20		package org.crosswire.common.diff;
21
22		/**
23		* A Commonality is shared text at the beginning, middle or end of two strings.
24		*
25		* Based on the LGPL Diff_Match_Patch v1.5 javascript of Neil Fraser, Copyright (C) 2006<br>
26		* <a href="http://neil.fraser.name/software/diff_match_patch/">http://neil.fraser.name/software/diff_match_patch/</a>
27		*
28		* @see gnu.lgpl.License The GNU Lesser General Public License for details.
29		* @author DM Smith
30		*/
31	0	public final class Commonality {
32		/**
33		* This is a utility class, therefore the constructor is private.
34		*/
35	0	private Commonality() {
36	0	}
37
38		/**
39		* Find the length of a common prefix.
40		*
41		* @param source
42		* First string
43		* @param target
44		* Second string
45		* @return The number of characters common to the start of each string.
46		*/
47		public static int prefix(final String source, final String target) {
48	0	int pointermin = 0;
49	0	int pointermax = Math.min(source.length(), target.length());
50	0	int pointermid = pointermax;
51	0	while (pointermin < pointermid) {
52	0	if (source.regionMatches(0, target, 0, pointermid)) {
53	0	pointermin = pointermid;
54		} else {
55	0	pointermax = pointermid;
56		}
57	0	pointermid = (pointermax - pointermin) / 2 + pointermin;
58		}
59
60	0	return pointermid;
61		}
62
63		/**
64		* Find the length of a common suffix.
65		*
66		* @param source
67		* First string
68		* @param target
69		* Second string
70		* @return The number of characters common to the end of each string.
71		*/
72		public static int suffix(final String source, final String target) {
73	0	int pointermin = 0;
74	0	int pointermax = Math.min(source.length(), target.length());
75	0	int pointermid = pointermax;
76	0	while (pointermin < pointermid) {
77	0	if (source.regionMatches(source.length() - pointermid, target, target.length() - pointermid, pointermid)) {
78	0	pointermin = pointermid;
79		} else {
80	0	pointermax = pointermid;
81		}
82	0	pointermid = (pointermax - pointermin) / 2 + pointermin;
83		}
84
85	0	return pointermid;
86		}
87
88		/**
89		* Do the two texts share a substring which is at least half the length of
90		* the longer text?
91		*
92		* @param source
93		* Baseline string
94		* @param target
95		* Changed string
96		* @return a CommonMiddle Or null if there was no match.
97		*/
98		public static CommonMiddle halfMatch(final String source, final String target) {
99	0	int sourceLength = source.length();
100	0	int targetLength = target.length();
101	0	String longText = sourceLength > targetLength ? source : target;
102	0	String shortText = sourceLength > targetLength ? target : source;
103	0	int longTextLength = Math.max(sourceLength, targetLength);
104	0	if (longTextLength < 10 \|\| shortText.length() < 1) {
105	0	return null; // Pointless.
106		}
107
108		// First check if the second quarter is the seed for a half-match.
109	0	CommonMiddle hm1 = halfMatch(longText, shortText, ceil(longTextLength, 4));
110		// Check again based on the third quarter.
111	0	CommonMiddle hm2 = halfMatch(longText, shortText, ceil(longTextLength, 2));
112	0	CommonMiddle hm = null;
113	0	if (hm1 == null && hm2 == null) {
114	0	return null;
115	0	} else if (hm2 == null) {
116	0	hm = hm1;
117	0	} else if (hm1 == null) {
118	0	hm = hm2;
119		} else {
120		// Both matched. Select the longest.
121	0	hm = hm1.getCommonality().length() > hm2.getCommonality().length() ? hm1 : hm2;
122		}
123
124		// A half-match was found, sort out the return data.
125	0	if (sourceLength > targetLength) {
126	0	return hm;
127		}
128
129		// While hm cannot be null our QA checker can't figure that out.
130	0	if (hm != null) {
131	0	return new CommonMiddle(hm.getTargetPrefix(), hm.getTargetSuffix(), hm.getSourcePrefix(), hm.getSourceSuffix(), hm.getCommonality());
132		}
133	0	return null;
134		}
135
136		/**
137		* Does a substring of shortText exist within longText such that the
138		* substring is at least half the length of longText?
139		*
140		* @param longText
141		* Longer string
142		* @param shortText
143		* Shorter string
144		* @param startIndex
145		* Start index of quarter length substring within longText
146		* @return Five element String array, containing the prefix of longText, the
147		* suffix of longText, the prefix of shortText, the suffix of
148		* shortText and the common middle. Or null if there was no match.
149		*/
150		private static CommonMiddle halfMatch(final String longText, final String shortText, final int startIndex) {
151		// Start with a 1/4 length substring at position i as a seed.
152	0	String seed = longText.substring(startIndex, startIndex + (longText.length() / 4));
153	0	int j = -1;
154	0	String common = "";
155	0	String longTextPrefix = "";
156	0	String longTextSuffix = "";
157	0	String shortTextPrefix = "";
158	0	String shortTextSuffix = "";
159	0	while ((j = shortText.indexOf(seed, j + 1)) != -1) {
160	0	int prefixLength = Commonality.prefix(longText.substring(startIndex), shortText.substring(j));
161	0	int suffixLength = Commonality.suffix(longText.substring(0, startIndex), shortText.substring(0, j));
162	0	if (common.length() < (prefixLength + suffixLength)) {
163	0	common = shortText.substring(j - suffixLength, j) + shortText.substring(j, j + prefixLength);
164	0	longTextPrefix = longText.substring(0, startIndex - suffixLength);
165	0	longTextSuffix = longText.substring(startIndex + prefixLength);
166	0	shortTextPrefix = shortText.substring(0, j - suffixLength);
167	0	shortTextSuffix = shortText.substring(j + prefixLength);
168		}
169	0	}
170
171	0	if (common.length() >= longText.length() / 2) {
172	0	return new CommonMiddle(longTextPrefix, longTextSuffix, shortTextPrefix, shortTextSuffix, common);
173		}
174
175	0	return null;
176		}
177
178		private static int ceil(int number, int divisor) {
179	0	assert divisor > 0;
180	0	int result = number / divisor + ((number % divisor) > 0 ? 1 : 0);
181		// assert result == (int) Math.ceil(((double) number) / ((double) divisor));
182	0	return result;
183		}
184
185		}