From 53512dc7dc2565f2870a70f3fb054880ddd1e318 Mon Sep 17 00:00:00 2001
From: Olyutorskii <olyutorskii@users.osdn.me>
Date: Thu, 22 Mar 2018 13:19:24 +0900
Subject: [PATCH] add B-search unit test

---
 .../jindolf/parser/content/DecodeErrorInfo.java    |  78 ++++++------
 .../parser/content/DecodeErrorInfoTest.java        | 135 +++++++++++++--------
 2 files changed, 124 insertions(+), 89 deletions(-)

diff --git a/src/main/java/jp/osdn/jindolf/parser/content/DecodeErrorInfo.java b/src/main/java/jp/osdn/jindolf/parser/content/DecodeErrorInfo.java
index e4e67b9..d1fb164 100644
--- a/src/main/java/jp/osdn/jindolf/parser/content/DecodeErrorInfo.java
+++ b/src/main/java/jp/osdn/jindolf/parser/content/DecodeErrorInfo.java
@@ -9,6 +9,7 @@ package jp.osdn.jindolf.parser.content;
 
 import java.util.Comparator;
 import java.util.List;
+import java.util.RandomAccess;
 
 /**
  * 文字デコード異常系の発生により
@@ -27,7 +28,7 @@ public class DecodeErrorInfo{
     public static final Comparator<DecodeErrorInfo> POS_COMPARATOR =
             new PosComparator();
 
-    private static final int BSEARCH_THRESHOLD = 16;
+    static final int BSEARCH_THRESHOLD = 16;
 
 
     private final int charPos;
@@ -96,22 +97,18 @@ public class DecodeErrorInfo{
      * デコードエラーのインデックス位置を返す。※リニアサーチ版。
      *
      * @param errList デコードエラーのリスト
-     * @param startPos 文字位置
+     * @param charPos 代替文字位置
      * @return 0から始まるリスト内の位置。
      *     文字位置の一致するデコードエラーがなければ
      *     リストへの挿入ポイントが返る。
      */
     public static int lsearchErrorIndex(List<DecodeErrorInfo> errList,
-                                        int startPos){
-        // assert errList instanceof RandomAccess;
-
-        int listSize = errList.size();
-
-        int idx;
-        for(idx = 0; idx < listSize; idx++){
-            DecodeErrorInfo einfo = errList.get(idx);
-            int errPos = einfo.getCharPosition();
-            if(startPos <= errPos) break;
+                                        int charPos){
+        int idx = 0;
+        for(DecodeErrorInfo einfo : errList){
+            int errCharPos = einfo.getCharPosition();
+            if(charPos <= errCharPos) break;
+            idx++;
         }
 
         return idx;
@@ -122,55 +119,64 @@ public class DecodeErrorInfo{
      * デコードエラーのインデックス位置を返す。※バイナリサーチ版。
      *
      * @param errList デコードエラーのリスト
-     * @param startPos 文字位置
+     * @param charPos 代替文字位置
      * @return 0から始まるリスト内の位置。
      *     文字位置の一致するデコードエラーがなければ
      *     リストへの挿入ポイントが返る。
      */
     public static int bsearchErrorIndex(List<DecodeErrorInfo> errList,
-                                        int startPos){
-        // assert errList instanceof RandomAccess;
-
-        int floor = 0;
-        int roof  = errList.size() - 1;
-
-        while(floor <= roof){
-            int gapHalf = (roof - floor) / 2;  // 切り捨て
-            int midpoint = floor + gapHalf;
-            DecodeErrorInfo einfo = errList.get(midpoint);
-            int errPos = einfo.getCharPosition();
-
-            if     (errPos < startPos) floor = midpoint + 1;
-            else if(errPos > startPos) roof  = midpoint - 1;
-            else return midpoint;
+                                        int charPos){
+        int floorIdx = 0;
+        int roofIdx  = errList.size() - 1;
+
+        while(floorIdx <= roofIdx){
+            int gapHalf = (roofIdx - floorIdx) / 2;  // 切り捨て
+            int midIdx = floorIdx + gapHalf;
+            DecodeErrorInfo einfo = errList.get(midIdx);
+            int errCharPos = einfo.getCharPosition();
+
+            if     (errCharPos < charPos) floorIdx = midIdx + 1;
+            else if(errCharPos > charPos) roofIdx  = midIdx - 1;
+            else return midIdx;
         }
 
-        return floor;
+        return floorIdx;
     }
 
     /**
      * 与えられた文字位置を含むか、またはそれ以降で最も小さな位置情報を持つ
      * デコードエラーのインデックス位置を返す。
      *
-     * <p>要素数の増減に応じてリニアサーチとバイナリサーチを使い分ける。
+     * <p>ランダムアクセスの可否、および要素数の増減に応じて
+     * リニアサーチとバイナリサーチを使い分ける。
      *
      * @param errList デコードエラーのリスト
-     * @param startPos 文字位置
+     * @param charPos 代替文字位置
      * @return 0から始まるリスト内の位置。
      *     文字位置の一致するデコードエラーがなければ
      *     リストへの挿入ポイントが返る。
      */
     public static int searchErrorIndex(List<DecodeErrorInfo> errList,
-                                       int startPos){
+                                       int charPos){
         int result;
 
-        int listSize = errList.size();
-        if(listSize < BSEARCH_THRESHOLD){
+        boolean useLinear;
+        if(errList instanceof RandomAccess){
+            if(errList.size() < BSEARCH_THRESHOLD){
+                useLinear = true;
+            }else{
+                useLinear = false;
+            }
+        }else{
+            useLinear = true;
+        }
+
+        if(useLinear){
             // linear-search
-            result = lsearchErrorIndex(errList, startPos);
+            result = lsearchErrorIndex(errList, charPos);
         }else{
             // binary-search
-            result = bsearchErrorIndex(errList, startPos);
+            result = bsearchErrorIndex(errList, charPos);
         }
 
         return result;
diff --git a/src/test/java/jp/osdn/jindolf/parser/content/DecodeErrorInfoTest.java b/src/test/java/jp/osdn/jindolf/parser/content/DecodeErrorInfoTest.java
index 9ac6754..ab75e29 100644
--- a/src/test/java/jp/osdn/jindolf/parser/content/DecodeErrorInfoTest.java
+++ b/src/test/java/jp/osdn/jindolf/parser/content/DecodeErrorInfoTest.java
@@ -19,6 +19,9 @@ import static org.junit.Assert.*;
  */
 public class DecodeErrorInfoTest {
 
+    private static final byte B0 = (byte)0x00;
+
+
     public DecodeErrorInfoTest() {
     }
 
@@ -247,40 +250,50 @@ public class DecodeErrorInfoTest {
         int result;
 
         errList = new ArrayList<>();
-        result = DecodeErrorInfo.lsearchErrorIndex(errList, 10);
-        assertEquals(0, result);
 
         errList.clear();
-        errList.add(new DecodeErrorInfo(5, (byte)0x00));
-        result = DecodeErrorInfo.lsearchErrorIndex(errList, 10);
-        assertEquals(1, result);
-
-        errList.clear();
-        errList.add(new DecodeErrorInfo(10, (byte)0x00));
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, -1);
+        assertEquals(0, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 0);
+        assertEquals(0, result);
         result = DecodeErrorInfo.lsearchErrorIndex(errList, 10);
         assertEquals(0, result);
 
         errList.clear();
-        errList.add(new DecodeErrorInfo(15, (byte)0x00));
+        errList.add(new DecodeErrorInfo(10, B0));
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 9);
+        assertEquals(0, result);
         result = DecodeErrorInfo.lsearchErrorIndex(errList, 10);
         assertEquals(0, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 11);
+        assertEquals(1, result);
 
         errList.clear();
-        errList.add(new DecodeErrorInfo(4, (byte)0x00));
-        errList.add(new DecodeErrorInfo(5, (byte)0x00));
-        errList.add(new DecodeErrorInfo(14, (byte)0x00));
-        errList.add(new DecodeErrorInfo(15, (byte)0x00));
+        errList.add(new DecodeErrorInfo(10, B0));
+        errList.add(new DecodeErrorInfo(20, B0));
+        errList.add(new DecodeErrorInfo(30, B0));
+        errList.add(new DecodeErrorInfo(40, B0));
+        errList.add(new DecodeErrorInfo(50, B0));
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 9);
+        assertEquals(0, result);
         result = DecodeErrorInfo.lsearchErrorIndex(errList, 10);
+        assertEquals(0, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 11);
+        assertEquals(1, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 29);
         assertEquals(2, result);
-
-        errList.clear();
-        errList.add(new DecodeErrorInfo(4, (byte)0x00));
-        errList.add(new DecodeErrorInfo(5, (byte)0x00));
-        errList.add(new DecodeErrorInfo(10, (byte)0x00));
-        errList.add(new DecodeErrorInfo(14, (byte)0x00));
-        errList.add(new DecodeErrorInfo(15, (byte)0x00));
-        result = DecodeErrorInfo.lsearchErrorIndex(errList, 10);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 30);
         assertEquals(2, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 31);
+        assertEquals(3, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 49);
+        assertEquals(4, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 50);
+        assertEquals(4, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 51);
+        assertEquals(5, result);
+        result = DecodeErrorInfo.lsearchErrorIndex(errList, 1000);
+        assertEquals(5, result);
 
         return;
      }
@@ -296,44 +309,50 @@ public class DecodeErrorInfoTest {
         int result;
 
         errList = new ArrayList<>();
-        result = DecodeErrorInfo.bsearchErrorIndex(errList, 10);
-        assertEquals(0, result);
 
         errList.clear();
-        errList.add(new DecodeErrorInfo(5, (byte)0x00));
-        result = DecodeErrorInfo.bsearchErrorIndex(errList, 10);
-        assertEquals(1, result);
-
-        errList.clear();
-        errList.add(new DecodeErrorInfo(10, (byte)0x00));
-        result = DecodeErrorInfo.bsearchErrorIndex(errList, 10);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, -1);
+        assertEquals(0, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 0);
         assertEquals(0, result);
-
-        errList.clear();
-        errList.add(new DecodeErrorInfo(15, (byte)0x00));
         result = DecodeErrorInfo.bsearchErrorIndex(errList, 10);
         assertEquals(0, result);
 
         errList.clear();
-        errList.add(new DecodeErrorInfo(4, (byte)0x00));
-        errList.add(new DecodeErrorInfo(5, (byte)0x00));
-        errList.add(new DecodeErrorInfo(14, (byte)0x00));
-        errList.add(new DecodeErrorInfo(15, (byte)0x00));
+        errList.add(new DecodeErrorInfo(10, B0));
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 9);
+        assertEquals(0, result);
         result = DecodeErrorInfo.bsearchErrorIndex(errList, 10);
-        assertEquals(2, result);
+        assertEquals(0, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 11);
+        assertEquals(1, result);
 
         errList.clear();
-        errList.add(new DecodeErrorInfo(4, (byte)0x00));
-        errList.add(new DecodeErrorInfo(5, (byte)0x00));
-        errList.add(new DecodeErrorInfo(10, (byte)0x00));
-        errList.add(new DecodeErrorInfo(14, (byte)0x00));
-        errList.add(new DecodeErrorInfo(15, (byte)0x00));
+        errList.add(new DecodeErrorInfo(10, B0));
+        errList.add(new DecodeErrorInfo(20, B0));
+        errList.add(new DecodeErrorInfo(30, B0));
+        errList.add(new DecodeErrorInfo(40, B0));
+        errList.add(new DecodeErrorInfo(50, B0));
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 9);
+        assertEquals(0, result);
         result = DecodeErrorInfo.bsearchErrorIndex(errList, 10);
+        assertEquals(0, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 11);
+        assertEquals(1, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 29);
         assertEquals(2, result);
-        result = DecodeErrorInfo.bsearchErrorIndex(errList, 9);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 30);
         assertEquals(2, result);
-        result = DecodeErrorInfo.bsearchErrorIndex(errList, 11);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 31);
         assertEquals(3, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 49);
+        assertEquals(4, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 50);
+        assertEquals(4, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 51);
+        assertEquals(5, result);
+        result = DecodeErrorInfo.bsearchErrorIndex(errList, 1000);
+        assertEquals(5, result);
 
         return;
     }
@@ -351,18 +370,28 @@ public class DecodeErrorInfoTest {
         errList = new ArrayList<>();
 
         errList.clear();
-        for(int pos = 0; pos <= 1000; pos += 10){
-            errList.add(new DecodeErrorInfo(pos, (byte)0x00));
+        for(int pos = 0; pos < 150; pos += 10){
+            errList.add(new DecodeErrorInfo(pos, B0));
         }
-        result = DecodeErrorInfo.searchErrorIndex(errList, 503);
-        assertEquals(51, result);
+        assertTrue(errList.size() < DecodeErrorInfo.BSEARCH_THRESHOLD);
+        result = DecodeErrorInfo.searchErrorIndex(errList, 89);
+        assertEquals(9, result);
+        result = DecodeErrorInfo.searchErrorIndex(errList, 90);
+        assertEquals(9, result);
+        result = DecodeErrorInfo.searchErrorIndex(errList, 91);
+        assertEquals(10, result);
 
         errList.clear();
-        for(int pos = 0; pos <= 50; pos += 10){
-            errList.add(new DecodeErrorInfo(pos, (byte)0x00));
+        for(int pos = 0; pos < 1500; pos += 10){
+            errList.add(new DecodeErrorInfo(pos, B0));
         }
-        result = DecodeErrorInfo.searchErrorIndex(errList, 23);
-        assertEquals(3, result);
+        assertTrue(errList.size() >= DecodeErrorInfo.BSEARCH_THRESHOLD);
+        result = DecodeErrorInfo.searchErrorIndex(errList, 899);
+        assertEquals(90, result);
+        result = DecodeErrorInfo.searchErrorIndex(errList, 900);
+        assertEquals(90, result);
+        result = DecodeErrorInfo.searchErrorIndex(errList, 901);
+        assertEquals(91, result);
 
         return;
     }
-- 
2.11.0