Add support for EncodeTypeHint.CHARACTER_SET for compacted QR-Codes (#1450)

* Added experimental version of QR-Code compaction which can be activated via EncodeHintType.QR_COMPACT

* - Changed algorithm from recursive divide and conquer to iterative Dijkstra
- Performed the requested modifications.

* Added better debug output and better documententation of the algorithm

* - Added missing error handling in case of a failing assert
- Fixed typo in the documentation

* Fixed bug that the minimal encoder would fail with an internal error if the string to encode contained only characters from ISO-8859-1 and on or more character that is not defined in any of the ISO-8859 characters sets.

* Added unit tests

* - indented class and method comments
- fixed code indententation
- added vertical spacing in statement lists to separate locical blocks
- added comments to document some numeric constants
- commented out debug logging
- made class ResultNode final and all but the methods called by the
class Encoder private.

* - Fixed indentation and line length
- Improved comments

* Fixed line length

* Improved comments

* - Whitespace and comment style changes
- Replaced string concatentation with StringBuilder.append()
- Replaced Vector with ArrayList
- Made members that are ony modified in the constructor final
- Made other minor changes

* - Made more members final
- replaced assert by throwing an IllegalStateException

* Changed internal data representation to be based on java.util.LinkedList

* Removed uneccessary spaces and comments

* Improved the debug output (now produces a compacted graph)

* - Added code to exclude not supported ECIs
- Fixed regression that bits were incorrectly computed

* - Fixed regression that bits were wrongly computed
- Improved compaction
- added a commented proposal for unit test that makes use of the decoder to validate the encoded bits

* Removed useless comparisons

* Removed commented code

* Optimization: added code to cache the value of LinkedList.size().

* Added more test cases

* - Added support for EncodeTypeHint.CHARACTER_SET
- Added support to encode in all ISO-8859 character sets available on the platform
- Removed code that handles failing asserts

* - Replaced string switch case with HashMap lookup
- Reintroduced asserts

* - Replaced <code> with {@code}
- Changed indentation in comment
- Simplified code

* Improved documentation

* Added comment about decoding compatibility with zxing.

* - Made MinimalEncoder responsible of ensuring that the bits fit in the returned version.
- Removed asserts that throw NPE in case of falure.

* Restricted encoder to use only encodings defined in CharacterSetECI

* Improved clarity and readability of the algorithm and of the datastrutures used.
- Minimizing algorithm is based on immutable edges
- ResultList now contains exaclty one ResultNode per mode and possibly several as before

* Changed unit tests (forgotten in previous push)

1 files changed, 56 insertions, 52 deletions

diff --git a/core/src/test/java/com/google/zxing/qrcode/encoder/EncoderTestCase.java b/core/src/test/java/com/google/zxing/qrcode/encoder/EncoderTestCase.java
index 754046e99..61847fe7e 100644
--- a/core/src/test/java/com/google/zxing/qrcode/encoder/EncoderTestCase.java
+++ b/core/src/test/java/com/google/zxing/qrcode/encoder/EncoderTestCase.java
@@ -29,6 +29,7 @@ import org.junit.Test;
 
 import java.util.EnumMap;
 import java.util.Map;
+import java.nio.charset.Charset;
 
 /**
  * @author satorux@google.com (Satoru Takabayashi) - creator
@@ -669,222 +670,225 @@ public final class EncoderTestCase extends Assert {
 
   @Test
   public void testMinimalEncoder1() throws Exception {
-    verifyMinimalEncoding("A", "ALPHANUMERIC(A),TERMINATOR()", false);
+    verifyMinimalEncoding("A", "ALPHANUMERIC(A),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder2() throws Exception {
-    verifyMinimalEncoding("AB", "ALPHANUMERIC(AB),TERMINATOR()", false);
+    verifyMinimalEncoding("AB", "ALPHANUMERIC(AB),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder3() throws Exception {
-    verifyMinimalEncoding("ABC", "ALPHANUMERIC(AB,C),TERMINATOR()", false);
+    verifyMinimalEncoding("ABC", "ALPHANUMERIC(ABC),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder4() throws Exception {
-    verifyMinimalEncoding("ABCD", "ALPHANUMERIC(AB,CD),TERMINATOR()", false);
+    verifyMinimalEncoding("ABCD", "ALPHANUMERIC(ABCD),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder5() throws Exception {
-    verifyMinimalEncoding("ABCDE", "ALPHANUMERIC(AB,CD,E),TERMINATOR()", false);
+    verifyMinimalEncoding("ABCDE", "ALPHANUMERIC(ABCDE),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder6() throws Exception {
-    verifyMinimalEncoding("ABCDEF", "ALPHANUMERIC(AB,CD,EF),TERMINATOR()", false);
+    verifyMinimalEncoding("ABCDEF", "ALPHANUMERIC(ABCDEF),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder7() throws Exception {
-    verifyMinimalEncoding("ABCDEFG", "ALPHANUMERIC(AB,CD,EF,G),TERMINATO" +
-        "R()", false);
+    verifyMinimalEncoding("ABCDEFG", "ALPHANUMERIC(ABCDEFG),TERMINATO" +
+        "R()", null, false);
   }
 
   @Test
   public void testMinimalEncoder8() throws Exception {
-    verifyMinimalEncoding("1", "NUMERIC(1),TERMINATOR()", false);
+    verifyMinimalEncoding("1", "NUMERIC(1),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder9() throws Exception {
-    verifyMinimalEncoding("12", "NUMERIC(12),TERMINATOR()", false);
+    verifyMinimalEncoding("12", "NUMERIC(12),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder10() throws Exception {
-    verifyMinimalEncoding("123", "NUMERIC(123),TERMINATOR()", false);
+    verifyMinimalEncoding("123", "NUMERIC(123),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder11() throws Exception {
-    verifyMinimalEncoding("1234", "NUMERIC(123,4),TERMINATOR()", false);
+    verifyMinimalEncoding("1234", "NUMERIC(1234),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder12() throws Exception {
-    verifyMinimalEncoding("12345", "NUMERIC(123,45),TERMINATOR()", false);
+    verifyMinimalEncoding("12345", "NUMERIC(12345),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder13() throws Exception {
-    verifyMinimalEncoding("123456", "NUMERIC(123,456),TERMINATOR()", false);
+    verifyMinimalEncoding("123456", "NUMERIC(123456),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder14() throws Exception {
-    verifyMinimalEncoding("123A", "ALPHANUMERIC(12,3A),TERMINATOR()", false);
+    verifyMinimalEncoding("123A", "ALPHANUMERIC(123A),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder15() throws Exception {
-    verifyMinimalEncoding("A1", "ALPHANUMERIC(A1),TERMINATOR()", false);
+    verifyMinimalEncoding("A1", "ALPHANUMERIC(A1),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder16() throws Exception {
-    verifyMinimalEncoding("A12", "ALPHANUMERIC(A1,2),TERMINATOR()", false);
+    verifyMinimalEncoding("A12", "ALPHANUMERIC(A12),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder17() throws Exception {
-    verifyMinimalEncoding("A123", "ALPHANUMERIC(A1,23),TERMINATOR()", false);
+    verifyMinimalEncoding("A123", "ALPHANUMERIC(A123),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder18() throws Exception {
-    verifyMinimalEncoding("A1234", "ALPHANUMERIC(A1,23,4),TERMINATOR()", false);
+    verifyMinimalEncoding("A1234", "ALPHANUMERIC(A1234),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder19() throws Exception {
-    verifyMinimalEncoding("A12345", "ALPHANUMERIC(A1,23,45),TERMINATOR()", false);
+    verifyMinimalEncoding("A12345", "ALPHANUMERIC(A12345),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder20() throws Exception {
-    verifyMinimalEncoding("A123456", "ALPHANUMERIC(A1,23,45,6),TERMINATOR()", false);
+    verifyMinimalEncoding("A123456", "ALPHANUMERIC(A123456),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder21() throws Exception {
-    verifyMinimalEncoding("A1234567", "ALPHANUMERIC(A1,23,45,67),TERMINATOR()", false);
+    verifyMinimalEncoding("A1234567", "ALPHANUMERIC(A1234567),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder22() throws Exception {
-    verifyMinimalEncoding("A12345678", "BYTE(A),NUMERIC(123,456,78),TERMINATOR()", false);
+    verifyMinimalEncoding("A12345678", "BYTE(A),NUMERIC(12345678),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder23() throws Exception {
-    verifyMinimalEncoding("A123456789", "BYTE(A),NUMERIC(123,456,789),TERMINATOR()", false);
+    verifyMinimalEncoding("A123456789", "BYTE(A),NUMERIC(123456789),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder24() throws Exception {
-    verifyMinimalEncoding("A1234567890", "ALPHANUMERIC(A1),NUMERIC(234,567,890),TERMINATOR()", false);
+    verifyMinimalEncoding("A1234567890", "ALPHANUMERIC(A1),NUMERIC(234567890),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder25() throws Exception {
-    verifyMinimalEncoding("AB1", "ALPHANUMERIC(AB,1),TERMINATOR()", false);
+    verifyMinimalEncoding("AB1", "ALPHANUMERIC(AB1),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder26() throws Exception {
-    verifyMinimalEncoding("AB12", "ALPHANUMERIC(AB,12),TERMINATOR()", false);
+    verifyMinimalEncoding("AB12", "ALPHANUMERIC(AB12),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder27() throws Exception {
-    verifyMinimalEncoding("AB123", "ALPHANUMERIC(AB,12,3),TERMINATOR()", false);
+    verifyMinimalEncoding("AB123", "ALPHANUMERIC(AB123),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder28() throws Exception {
-    verifyMinimalEncoding("AB1234", "ALPHANUMERIC(AB,12,34),TERMINATOR()", false);
+    verifyMinimalEncoding("AB1234", "ALPHANUMERIC(AB1234),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder29() throws Exception {
-    verifyMinimalEncoding("ABC1", "ALPHANUMERIC(AB,C1),TERMINATOR()", false);
+    verifyMinimalEncoding("ABC1", "ALPHANUMERIC(ABC1),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder30() throws Exception {
-    verifyMinimalEncoding("ABC12", "ALPHANUMERIC(AB,C1,2),TERMINATOR()", false);
+    verifyMinimalEncoding("ABC12", "ALPHANUMERIC(ABC12),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder31() throws Exception {
-    verifyMinimalEncoding("ABC1234", "ALPHANUMERIC(AB,C1,23,4),TERMINA" +
-        "TOR()", false);
+    verifyMinimalEncoding("ABC1234", "ALPHANUMERIC(ABC1234),TERMINA" +
+        "TOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder32() throws Exception {
-    verifyMinimalEncoding("http://foo.com", "BYTE(h,t,t,p,:,/,/,f,o,o,.,c,o,m)" +
-        ",TERMINATOR()", false);
+    verifyMinimalEncoding("http://foo.com", "BYTE(http://foo.com)" +
+        ",TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder33() throws Exception {
-    verifyMinimalEncoding("HTTP://FOO.COM", "ALPHANUMERIC(HT,TP,:/,/F,OO,.C,OM" +
-        "),TERMINATOR()", false);
+    verifyMinimalEncoding("HTTP://FOO.COM", "ALPHANUMERIC(HTTP://FOO.COM" +
+        "),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder34() throws Exception {
     verifyMinimalEncoding("1001114670010%01201220%107211220%140045003267781", 
-        "NUMERIC(100,111,467,001,0),ALPHANUMERIC(%0,12,01,22,0%,10,72,11,22,0%),NUMERIC(140,045,003,267,781),TERMINA" +
-        "TOR()", false);
+        "NUMERIC(1001114670010),ALPHANUMERIC(%01201220%107211220%),NUMERIC(140045003267781),TERMINA" +
+        "TOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder35() throws Exception {
-    verifyMinimalEncoding("\u0150", "ECI(ISO-8859-2),BYTE(.),TERMINATOR()", false);
+    verifyMinimalEncoding("\u0150", "ECI(ISO-8859-2),BYTE(.),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder36() throws Exception {
-    verifyMinimalEncoding("\u015C", "ECI(ISO-8859-3),BYTE(.),TERMINATOR()", false);
+    verifyMinimalEncoding("\u015C", "ECI(ISO-8859-3),BYTE(.),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder37() throws Exception {
-    verifyMinimalEncoding("\u0150\u015C", "ECI(UTF-8),BYTE(.,.),TERMINATOR()", false);
+    verifyMinimalEncoding("\u0150\u015C", "ECI(UTF-8),BYTE(..),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder38() throws Exception {
-    verifyMinimalEncoding("\u0150\u0150\u015C\u015C", "ECI(ISO-8859-2),BYTE(.," +
-        ".),ECI(ISO-8859-3),BYTE(.,.),TERMINATOR()", false);
+    verifyMinimalEncoding("\u0150\u0150\u015C\u015C", "ECI(ISO-8859-2),BYTE(." +
+        ".),ECI(ISO-8859-3),BYTE(..),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder39() throws Exception {
-    verifyMinimalEncoding("abcdef\u0150ghij", "ECI(ISO-8859-2),BYTE(a,b,c,d,e," +
-        "f,.,g,h,i,j),TERMINATOR()", false);
+    verifyMinimalEncoding("abcdef\u0150ghij", "ECI(ISO-8859-2),BYTE(abcde" +
+        "f.ghij),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder40() throws Exception {
     verifyMinimalEncoding("2938928329832983\u01502938928329832983\u015C2938928329832983", 
-        "NUMERIC(293,892,832,983,298,3),ECI(ISO-8859-2),BYTE(.),NUMERIC(293,892,832,983,298,3),ECI(ISO-8" +
-        "859-3),BYTE(.),NUMERIC(293,892,832,983,298,3),TERMINATOR()", false);
+        "NUMERIC(2938928329832983),ECI(ISO-8859-2),BYTE(.),NUMERIC(2938928329832983),ECI(ISO-8" +
+        "859-3),BYTE(.),NUMERIC(2938928329832983),TERMINATOR()", null, false);
   }
 
   @Test
   public void testMinimalEncoder41() throws Exception {
-    verifyMinimalEncoding("1001114670010%01201220%107211220%140045003267781", "FNC1_FIRST_POSITION(),NUMERIC(100,111" +
-        ",467,001,0),ALPHANUMERIC(%0,12,01,22,0%,10,72,11,22,0%),NUMERIC(140,045,003,267,781),TERMINATOR()", true);
+    verifyMinimalEncoding("1001114670010%01201220%107211220%140045003267781", "FNC1_FIRST_POSITION(),NUMERIC(100111" +
+        "4670010),ALPHANUMERIC(%01201220%107211220%),NUMERIC(140045003267781),TERMINATOR()", null, 
+        true);
   }
 
-  static void verifyMinimalEncoding(String input, String expectedResult, boolean isGS1) throws Exception {
-    MinimalEncoder.ResultList result = MinimalEncoder.encode(input, null, isGS1);
+  static void verifyMinimalEncoding(String input, String expectedResult, Charset priorityCharset, boolean isGS1) 
+      throws Exception {
+    MinimalEncoder.ResultList result = MinimalEncoder.encode(input, null, priorityCharset, isGS1,
+        ErrorCorrectionLevel.L);
     assertEquals(result.toString(), expectedResult);
   }