KYLIN-2794 MultipleDictionaryValueEnumerator should output values in sorted order
Project: http://git-wip-us.apache.org/repos/asf/kylin/repo Commit: http://git-wip-us.apache.org/repos/asf/kylin/commit/622bafe2 Tree: http://git-wip-us.apache.org/repos/asf/kylin/tree/622bafe2 Diff: http://git-wip-us.apache.org/repos/asf/kylin/diff/622bafe2 Branch: refs/heads/2.2.x Commit: 622bafe278ec1ca3039e2e2c23764c80a7aed631 Parents: 5fbd952 Author: Li Yang <[email protected]> Authored: Mon Oct 9 06:25:31 2017 +0800 Committer: Li Yang <[email protected]> Committed: Mon Oct 9 06:30:06 2017 +0800 ---------------------------------------------------------------------- .../dict/MultipleDictionaryValueEnumerator.java | 50 ++++++++++-------- .../MultipleDictionaryValueEnumeratorTest.java | 54 ++++++++++++-------- 2 files changed, 62 insertions(+), 42 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/kylin/blob/622bafe2/core-dictionary/src/main/java/org/apache/kylin/dict/MultipleDictionaryValueEnumerator.java ---------------------------------------------------------------------- diff --git a/core-dictionary/src/main/java/org/apache/kylin/dict/MultipleDictionaryValueEnumerator.java b/core-dictionary/src/main/java/org/apache/kylin/dict/MultipleDictionaryValueEnumerator.java index c1bc5d5..f0d4e34 100644 --- a/core-dictionary/src/main/java/org/apache/kylin/dict/MultipleDictionaryValueEnumerator.java +++ b/core-dictionary/src/main/java/org/apache/kylin/dict/MultipleDictionaryValueEnumerator.java @@ -30,20 +30,16 @@ import com.google.common.collect.Lists; */ @SuppressWarnings("rawtypes") public class MultipleDictionaryValueEnumerator implements IDictionaryValueEnumerator { - private int curDictIndex = 0; - private Dictionary<String> curDict; - private int curKey; + private List<Integer> curKeys = Lists.newArrayList(); private String curValue = null; private List<Dictionary<String>> dictionaryList; public MultipleDictionaryValueEnumerator(List<DictionaryInfo> dictionaryInfoList) { dictionaryList = Lists.newArrayListWithCapacity(dictionaryInfoList.size()); for (DictionaryInfo dictInfo : dictionaryInfoList) { + Dictionary<String> dictionary = (Dictionary<String>) dictInfo.getDictionaryObject(); dictionaryList.add((Dictionary<String>) dictInfo.getDictionaryObject()); - } - if (!dictionaryList.isEmpty()) { - curDict = dictionaryList.get(0); - curKey = curDict.getMinId(); + curKeys.add(dictionary.getMinId()); } } @@ -54,22 +50,34 @@ public class MultipleDictionaryValueEnumerator implements IDictionaryValueEnumer @Override public boolean moveNext() throws IOException { - while (curDictIndex < dictionaryList.size()) { - if (curKey <= curDict.getMaxId()) { - curValue = curDict.getValueFromId(curKey); - curKey ++; - - return true; - } - - // move to next dict if exists - if (++curDictIndex < dictionaryList.size()) { - curDict = dictionaryList.get(curDictIndex); - curKey = curDict.getMinId(); + String minValue = null; + int curDictIndex = 0; + + // multi-merge dictionary forest + for (int i = 0; i < dictionaryList.size(); i++) { + Dictionary<String> dict = dictionaryList.get(i); + if (dict == null) + continue; + + int curKey = curKeys.get(i); + if (curKey > dict.getMaxId()) + continue; + + String curValue = dict.getValueFromId(curKey); + if (minValue == null || minValue.compareTo(curValue) > 0) { + minValue = curValue; + curDictIndex = i; } } - curValue = null; - return false; + + if (minValue == null) { + curValue = null; + return false; + } + + curValue = minValue; + curKeys.set(curDictIndex, curKeys.get(curDictIndex) + 1); + return true; } @Override http://git-wip-us.apache.org/repos/asf/kylin/blob/622bafe2/core-dictionary/src/test/java/org/apache/kylin/dict/MultipleDictionaryValueEnumeratorTest.java ---------------------------------------------------------------------- diff --git a/core-dictionary/src/test/java/org/apache/kylin/dict/MultipleDictionaryValueEnumeratorTest.java b/core-dictionary/src/test/java/org/apache/kylin/dict/MultipleDictionaryValueEnumeratorTest.java index 2e90bcf..3496c00 100644 --- a/core-dictionary/src/test/java/org/apache/kylin/dict/MultipleDictionaryValueEnumeratorTest.java +++ b/core-dictionary/src/test/java/org/apache/kylin/dict/MultipleDictionaryValueEnumeratorTest.java @@ -56,52 +56,63 @@ public class MultipleDictionaryValueEnumeratorTest { @Test public void testNormalDicts() throws IOException { List<DictionaryInfo> dictionaryInfoList = new ArrayList<>(2); - dictionaryInfoList.add(createDictInfo(new int[]{0, 1, 2})); - dictionaryInfoList.add(createDictInfo(new int[]{4, 5, 6})); + dictionaryInfoList.add(createDictInfo(new int[] { 0, 1, 2 })); + dictionaryInfoList.add(createDictInfo(new int[] { 4, 5, 6 })); Integer[] values = enumerateDictInfoList(dictionaryInfoList); assertEquals(6, values.length); - assertArrayEquals(new Integer[]{0, 1, 2, 4, 5, 6}, values); + assertArrayEquals(new Integer[] { 0, 1, 2, 4, 5, 6 }, values); } @Test public void testFirstEmptyDicts() throws IOException { List<DictionaryInfo> dictionaryInfoList = new ArrayList<>(2); - dictionaryInfoList.add(createDictInfo(new int[]{})); - dictionaryInfoList.add(createDictInfo(new int[]{4, 5, 6})); + dictionaryInfoList.add(createDictInfo(new int[] {})); + dictionaryInfoList.add(createDictInfo(new int[] { 4, 5, 6 })); Integer[] values = enumerateDictInfoList(dictionaryInfoList); assertEquals(3, values.length); - assertArrayEquals(new Integer[]{4, 5, 6}, values); + assertArrayEquals(new Integer[] { 4, 5, 6 }, values); } @Test public void testMiddleEmptyDicts() throws IOException { List<DictionaryInfo> dictionaryInfoList = new ArrayList<>(3); - dictionaryInfoList.add(createDictInfo(new int[]{0, 1, 2})); - dictionaryInfoList.add(createDictInfo(new int[]{})); - dictionaryInfoList.add(createDictInfo(new int[]{7, 8, 9})); + dictionaryInfoList.add(createDictInfo(new int[] { 0, 1, 2 })); + dictionaryInfoList.add(createDictInfo(new int[] {})); + dictionaryInfoList.add(createDictInfo(new int[] { 7, 8, 9 })); Integer[] values = enumerateDictInfoList(dictionaryInfoList); assertEquals(6, values.length); - assertArrayEquals(new Integer[]{0, 1, 2, 7, 8, 9}, values); + assertArrayEquals(new Integer[] { 0, 1, 2, 7, 8, 9 }, values); } @Test public void testLastEmptyDicts() throws IOException { List<DictionaryInfo> dictionaryInfoList = new ArrayList<>(3); - dictionaryInfoList.add(createDictInfo(new int[]{0, 1, 2})); - dictionaryInfoList.add(createDictInfo(new int[]{6, 7, 8})); - dictionaryInfoList.add(createDictInfo(new int[]{})); + dictionaryInfoList.add(createDictInfo(new int[] { 0, 1, 2 })); + dictionaryInfoList.add(createDictInfo(new int[] { 6, 7, 8 })); + dictionaryInfoList.add(createDictInfo(new int[] {})); Integer[] values = enumerateDictInfoList(dictionaryInfoList); assertEquals(6, values.length); - assertArrayEquals(new Integer[]{0, 1, 2, 6, 7, 8}, values); + assertArrayEquals(new Integer[] { 0, 1, 2, 6, 7, 8 }, values); + } + + @Test + public void testUnorderedDicts() throws IOException { + List<DictionaryInfo> dictionaryInfoList = new ArrayList<>(3); + dictionaryInfoList.add(createDictInfo(new int[] { 0, 1, 6 })); + dictionaryInfoList.add(createDictInfo(new int[] { 3, 7, 8 })); + dictionaryInfoList.add(createDictInfo(new int[] { 2, 7, 9 })); + Integer[] values = enumerateDictInfoList(dictionaryInfoList); + assertEquals(9, values.length); + assertArrayEquals(new Integer[] { 0, 1, 2, 3, 6, 7, 7, 8, 9 }, values); } public static class MockDictionary extends Dictionary<String> { private static final long serialVersionUID = 1L; - + public int[] values; @Override @@ -111,7 +122,7 @@ public class MultipleDictionaryValueEnumeratorTest { @Override public int getMaxId() { - return values.length-1; + return values.length - 1; } @Override @@ -134,16 +145,17 @@ public class MultipleDictionaryValueEnumeratorTest { return "" + values[id]; } - @Override - public void dump(PrintStream out) {} + public void dump(PrintStream out) { + } @Override - public void write(DataOutput out) throws IOException {} + public void write(DataOutput out) throws IOException { + } @Override - public void readFields(DataInput in) throws IOException {} - + public void readFields(DataInput in) throws IOException { + } @Override public boolean contains(Dictionary another) {
