jpountz commented on a change in pull request #91: URL: https://github.com/apache/lucene/pull/91#discussion_r622900018
########## File path: lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java ########## @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.lucene.util; + +/** + * Stable radix sorter for variable-length strings. + * + * @lucene.internal + */ +public abstract class StableMSBRadixSorter extends MSBRadixSorter { + + protected boolean useStableSort; Review comment: unused? ########## File path: lucene/core/src/java/org/apache/lucene/codecs/MutablePointValues.java ########## @@ -41,4 +41,10 @@ protected MutablePointValues() {} /** Swap the i-th and j-th values. */ public abstract void swap(int i, int j); + + /** Assign the from-th value to to-th position in another array which used temporarily. */ + public abstract void assign(int from, int to); + + /** Finalize assign operation, to switch array. */ + public abstract void finalizeAssign(int from, int to); Review comment: `TimSorter` uses `save` and `restore` as names, maybe we should try to reuse this terminology for consistency? By the way, maybe we could even reuse the semantics of these methods where `save` copies a whole range while `restore` restores a single element at a time. This would only require slight modifications to `StableMSBRadixSorter#reorder` to copy the whole range first and then move items from the `temp` array to their expected index in the original array? ########## File path: lucene/core/src/test/org/apache/lucene/util/bkd/TestBKD.java ########## @@ -1698,6 +1698,16 @@ public void getValue(int i, BytesRef packedValue) { public byte getByteAt(int i, int k) { throw new UnsupportedOperationException(); } + + @Override + public void assign(int from, int to) { + // do nothing + } + + @Override + public void finalizeAssign(int from, int to) { + // do nothing + } Review comment: can you throw an UnexpectedOperationException in both these methods instead, like we do for other methods? ########## File path: lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java ########## @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.lucene.util; + +/** + * Stable radix sorter for variable-length strings. + * + * @lucene.internal + */ +public abstract class StableMSBRadixSorter extends MSBRadixSorter { Review comment: Since the name has "stable", can you override `getFallbackSorter` to return an `InPlaceMergeSorter` so that the sort is guaranteed to be stable in all cases? ########## File path: lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java ########## @@ -0,0 +1,60 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.lucene.util; + +/** + * Stable radix sorter for variable-length strings. + * + * @lucene.internal + */ +public abstract class StableMSBRadixSorter extends MSBRadixSorter { + + protected boolean useStableSort; + + public StableMSBRadixSorter(int maxLength) { + super(maxLength); + } + + /** Assign the from-th value to to-th position in another array which used temporarily. */ + protected void assign(int from, int to) { + throw new UnsupportedOperationException(); + } + + /** Finalize assign operation, to switch array. */ + protected void finalizeAssign(int from, int to) { + throw new UnsupportedOperationException(); + } Review comment: Can you make these two methods abstract? Forgetting to implement them would always lead to errors? ########## File path: lucene/core/src/java/org/apache/lucene/util/bkd/MutablePointsReaderUtils.java ########## @@ -35,63 +37,60 @@ MutablePointsReaderUtils() {} - /** Sort the given {@link MutablePointValues} based on its packed value then doc ID. */ + /** + * Sort the given {@link MutablePointValues} based on its packed value, note that doc ID is not + * taken into sorting algorithm, since if they are already in ascending order, stable sort is able + * to maintain the ordering of doc ID. + */ Review comment: Hmm I don't think this is correct when index sorting is configured. Should we add back the check you previously had to know whether doc IDs came in order? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
