1 package org.unicode.cldr.draft; 2 3 import java.util.Random; 4 5 import org.unicode.cldr.util.Timer; 6 7 import com.ibm.icu.dev.test.TestFmwk; 8 import com.ibm.icu.text.DecimalFormat; 9 import com.ibm.icu.text.NumberFormat; 10 11 public class GapStringTest extends TestFmwk { 12 13 private static final int ITERATIONS = 100000; 14 private static final int RANDOM_STRING_LENGTH = 9; 15 main(String[] args)16 public static void main(String[] args) { 17 new GapStringTest().run(args); 18 } 19 TestCorrectness()20 public static void TestCorrectness() { 21 GapString a = new GapString(); 22 StringBuilder b = new StringBuilder(); 23 24 for (int iteration = 0; iteration < ITERATIONS; ++iteration) { 25 int randomPos = random.nextInt(b.length() + 1); 26 String randomString; 27 switch (random.nextInt(4)) { 28 case 0: // delete 29 int randomEnd = randomPos + random.nextInt(b.length() - randomPos + 1); 30 b.delete(randomPos, randomEnd); 31 a.delete(randomPos, randomEnd); 32 assertEqual(a, b); 33 break; 34 case 1: // insert 35 char randomChar = (char) ('a' + random.nextInt(26)); 36 b.insert(randomPos, randomChar); 37 a.insert(randomPos, randomChar); 38 assertEqual(a, b); 39 break; 40 case 2: // insert string 41 randomString = getRandomString(RANDOM_STRING_LENGTH); 42 b.insert(randomPos, randomString); 43 a.insert(randomPos, randomString); 44 assertEqual(a, b); 45 break; 46 case 3: // insert char sequence (different code path) 47 StringBuffer randomStringBuffer = new StringBuffer(getRandomString(RANDOM_STRING_LENGTH)); 48 b.insert(randomPos, randomStringBuffer); 49 a.insert(randomPos, randomStringBuffer); 50 assertEqual(a, b); 51 break; 52 case 4: // append string 53 randomString = getRandomString(RANDOM_STRING_LENGTH); 54 b.append(randomString); 55 a.append(randomString); 56 assertEqual(a, b); 57 break; 58 59 } 60 } 61 } 62 63 static DecimalFormat percent = (DecimalFormat) NumberFormat.getPercentInstance(); 64 private static Random random = new Random(0); 65 static { 66 percent.setMaximumFractionDigits(6); 67 percent.setPositivePrefix("+"); 68 } 69 TestTimeDeleteInsert()70 public static void TestTimeDeleteInsert() { 71 checkTime(TimingStyle.fixed); 72 } 73 TestTimeRandomDeleteInsert()74 public static void TestTimeRandomDeleteInsert() { 75 checkTime(TimingStyle.randomStart); 76 } 77 TestTimeAppend()78 public static void TestTimeAppend() { 79 checkTime(TimingStyle.append); 80 } 81 82 enum TimingStyle { 83 fixed, randomStart, append 84 } 85 checkTime(TimingStyle timingStyle)86 private static void checkTime(TimingStyle timingStyle) { 87 GapString a = new GapString("abcdefghijklmonpqrstuvwxyz"); 88 StringBuilder b = new StringBuilder("abcdefghijklmonpqrstuvwxyz"); 89 double[] randomStarts = new double[256]; 90 double[] randomInserts = new double[256]; 91 if (timingStyle == TimingStyle.randomStart) { 92 for (int i = 0; i < randomStarts.length; ++i) { 93 randomStarts[i] = random.nextDouble(); 94 randomInserts[i] = random.nextDouble(); 95 } 96 } 97 Timer timer = new Timer(); 98 99 timer.start(); 100 for (int i = 0; i < ITERATIONS; ++i) { 101 switch (timingStyle) { 102 case append: 103 a.append("!@#$%X"); 104 break; 105 case randomStart: 106 case fixed: 107 int deletePos = 5; 108 int insertPos = 5; 109 if (timingStyle == TimingStyle.randomStart) { 110 final int length = a.length() - 5; 111 deletePos = (int) (length * randomStarts[i & 0xFF]); 112 insertPos = (int) (length * randomInserts[i & 0xFF]); 113 } 114 a.delete(deletePos, deletePos + 5); 115 a.insert(insertPos, "!@#$%X"); 116 } 117 } 118 timer.stop(); 119 long gapDuration = timer.getDuration(); 120 121 timer.start(); 122 for (int i = 0; i < ITERATIONS; ++i) { 123 switch (timingStyle) { 124 case append: 125 b.append("!@#$%X"); 126 break; 127 case randomStart: 128 case fixed: 129 int deletePos = 5; 130 int insertPos = 5; 131 if (timingStyle == TimingStyle.randomStart) { 132 final int length = b.length() - 5; 133 deletePos = (int) (length * randomStarts[i & 0xFF]); 134 insertPos = (int) (length * randomInserts[i & 0xFF]); 135 } 136 b.delete(deletePos, deletePos + 5); 137 b.insert(insertPos, "!@#$%X"); 138 } 139 } 140 timer.stop(); 141 long builderDuration = timer.getDuration(); 142 assertEqual(a, b); 143 System.out.println("\tGap - Builder% =\t" + percent.format(gapDuration * 1.0 / builderDuration - 1.0)); 144 } 145 getRandomString(int maxLength)146 private static String getRandomString(int maxLength) { 147 StringBuilder result = new StringBuilder(); 148 for (int i = random.nextInt(maxLength); i >= 0; --i) { 149 result.append((char) ('a' + random.nextInt(26))); 150 } 151 return result.toString(); 152 } 153 assertEqual(CharSequence a, CharSequence b)154 private static void assertEqual(CharSequence a, CharSequence b) { 155 if (!a.equals(b)) { 156 a.equals(b); 157 throw new IllegalArgumentException(); 158 } 159 if (!b.toString().equals(a.toString())) { 160 b.equals(a.toString()); 161 throw new IllegalArgumentException(); 162 } 163 } 164 } 165