1
20 package org.crosswire.common.diff;
21
22
31 public final class Commonality {
32
35 private Commonality() {
36 }
37
38
47 public static int prefix(final String source, final String target) {
48 int pointermin = 0;
49 int pointermax = Math.min(source.length(), target.length());
50 int pointermid = pointermax;
51 while (pointermin < pointermid) {
52 if (source.regionMatches(0, target, 0, pointermid)) {
53 pointermin = pointermid;
54 } else {
55 pointermax = pointermid;
56 }
57 pointermid = (pointermax - pointermin) / 2 + pointermin;
58 }
59
60 return pointermid;
61 }
62
63
72 public static int suffix(final String source, final String target) {
73 int pointermin = 0;
74 int pointermax = Math.min(source.length(), target.length());
75 int pointermid = pointermax;
76 while (pointermin < pointermid) {
77 if (source.regionMatches(source.length() - pointermid, target, target.length() - pointermid, pointermid)) {
78 pointermin = pointermid;
79 } else {
80 pointermax = pointermid;
81 }
82 pointermid = (pointermax - pointermin) / 2 + pointermin;
83 }
84
85 return pointermid;
86 }
87
88
98 public static CommonMiddle halfMatch(final String source, final String target) {
99 int sourceLength = source.length();
100 int targetLength = target.length();
101 String longText = sourceLength > targetLength ? source : target;
102 String shortText = sourceLength > targetLength ? target : source;
103 int longTextLength = Math.max(sourceLength, targetLength);
104 if (longTextLength < 10 || shortText.length() < 1) {
105 return null; }
107
108 CommonMiddle hm1 = halfMatch(longText, shortText, ceil(longTextLength, 4));
110 CommonMiddle hm2 = halfMatch(longText, shortText, ceil(longTextLength, 2));
112 CommonMiddle hm = null;
113 if (hm1 == null && hm2 == null) {
114 return null;
115 } else if (hm2 == null) {
116 hm = hm1;
117 } else if (hm1 == null) {
118 hm = hm2;
119 } else {
120 hm = hm1.getCommonality().length() > hm2.getCommonality().length() ? hm1 : hm2;
122 }
123
124 if (sourceLength > targetLength) {
126 return hm;
127 }
128
129 if (hm != null) {
131 return new CommonMiddle(hm.getTargetPrefix(), hm.getTargetSuffix(), hm.getSourcePrefix(), hm.getSourceSuffix(), hm.getCommonality());
132 }
133 return null;
134 }
135
136
150 private static CommonMiddle halfMatch(final String longText, final String shortText, final int startIndex) {
151 String seed = longText.substring(startIndex, startIndex + (longText.length() / 4));
153 int j = -1;
154 String common = "";
155 String longTextPrefix = "";
156 String longTextSuffix = "";
157 String shortTextPrefix = "";
158 String shortTextSuffix = "";
159 while ((j = shortText.indexOf(seed, j + 1)) != -1) {
160 int prefixLength = Commonality.prefix(longText.substring(startIndex), shortText.substring(j));
161 int suffixLength = Commonality.suffix(longText.substring(0, startIndex), shortText.substring(0, j));
162 if (common.length() < (prefixLength + suffixLength)) {
163 common = shortText.substring(j - suffixLength, j) + shortText.substring(j, j + prefixLength);
164 longTextPrefix = longText.substring(0, startIndex - suffixLength);
165 longTextSuffix = longText.substring(startIndex + prefixLength);
166 shortTextPrefix = shortText.substring(0, j - suffixLength);
167 shortTextSuffix = shortText.substring(j + prefixLength);
168 }
169 }
170
171 if (common.length() >= longText.length() / 2) {
172 return new CommonMiddle(longTextPrefix, longTextSuffix, shortTextPrefix, shortTextSuffix, common);
173 }
174
175 return null;
176 }
177
178 private static int ceil(int number, int divisor) {
179 assert divisor > 0;
180 int result = number / divisor + ((number % divisor) > 0 ? 1 : 0);
181 return result;
183 }
184
185 }
186