You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "kvr000 (via GitHub)" <gi...@apache.org> on 2024/08/31 19:54:44 UTC
[PR] binarySearch on sorted arrays and sorted lists [commons-lang]
kvr000 opened a new pull request, #1270:
URL: https://github.com/apache/commons-lang/pull/1270
There is `Collections.binarySearch()` in Java core. However, it searches for exact element which is often not usable, as the elements are typically sorted by particular field.
These methods introduce `binarySearch()` on arrays and (sorted) List, with ability to provide sorting key extraction function and key comparator.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1758067906
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
@garydgregory : I already did. I dropped `binarySearch` as the randomness of choosing any of equal element effectively disqualifies it from such use cases. Predictable behavior of `binarySearchFirst` and `binarySearchLast` is huge benefit and comes at almost no cost (is slower only in cases when the lookup is quickly "lucky").
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1755521703
##########
src/test/java/org/apache/commons/lang3/ArrayUtilsBinarySearchTest.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * 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.commons.lang3;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.stream.IntStream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * Unit tests {@link ArrayUtils} binarySearch functions.
+ */
+public class ArrayUtilsBinarySearchTest extends AbstractLangTest {
+
+ @Test
+ public void binarySearch_whenEmpty_returnM1() {
Review Comment:
Since all tests in the class call `binarySearch()` and the class is already called "binary search", you do not need to repeat that name in each test method name, that'll de-clutter names a bit.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#issuecomment-2345149560
> Hello @kvr000
>
> * See my scattered comments.
> * Add a method called `createSortedList(int...)` that guarantees sorted results and use it.
> * Add tests for non-sorted input, make sure the results are predictable, we do not want a DOS for an infinite loop for example.
The `createdSortedList()` won't have any value. In the test, I have to see what is returned index - that's impossible with unsorted array. Additionally, now it's used also for intentionally unsorted array.
Good point for non-sorted input, I added a test. The code always does `l = m+1` or `h = m-1` , so it's safe.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1759171390
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
@sebbASF @garydgregory :
> In the case of the 'Arrays' method, the entire entry is matched, so to some extent it does not matter which index is returned. That is not the case where a partial key is used, so I think in the user will often want to know all the matches.
In my particular case, I have list of GPS locations sorted by time and track distance, with distance unchanged if there was no move (causing duplicates). One use case is to find point for particular distance and if there are duplicates, I want the result to be predictable (here last but can be first in different use cases). If the result is unpredictable, it will lead to different results based on initial conditions for the search. I don't care about whole range, though I can imagine someone would appreciate such function with added complexity.
> Sudden thought: surely key extraction can take place in the Comparator, so why is this method needed at all?
No, unless we're able to construct the full object which is not always possible - note that `Comparator` takes two arguments of the same type. It is technically achievable with hacking and casting one argument to `T` and the other one to `K`, relying on internal implementation passing the arguments in expected order but that would be super ugly and fragile.
@garydgregory :
> Please revert the First/Last APIs.
For the reasons above, I want to keep those as they better match intended use case. I think we actually don't need original unpredictable `binarySearch()` .
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "sebbASF (via GitHub)" <gi...@apache.org>.
sebbASF commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1756297624
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
The above para needs rework: there is no specified range here, and no toIndex
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch0(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Searches element in array sorted by key, within range fromIndex - toIndex (inclusive - exclusive).
+ *
Review Comment:
It would be clearer as
fromIndex (inclusive) - toIndex (exclusive)
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch0(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Searches element in array sorted by key, within range fromIndex - toIndex (inclusive - exclusive).
+ *
+ * @param array
+ * array sorted by key field
+ * @param fromIndex
+ * start index
+ * @param toIndex
+ * end index (exclusive)
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @throws ArrayIndexOutOfBoundsException
+ * when fromIndex or toIndex is out of array range
+ * @throws IllegalArgumentException
+ * when fromIndex is greater than toIndex
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <T, K> int binarySearch(
+ T[] array,
+ int fromIndex, int toIndex,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException(
+ "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+ }
+ if (fromIndex < 0) {
+ throw new ArrayIndexOutOfBoundsException(fromIndex);
+ }
+ if (toIndex > array.length) {
+ throw new ArrayIndexOutOfBoundsException(toIndex);
+ }
+
+ return binarySearch0(array, fromIndex, toIndex, key, keyExtractor, comparator);
+ }
+
+ // common implementation for binarySearch methods, with same semantics:
+ private static <T, K> int binarySearch0(
+ T[] array,
+ int fromIndex, int toIndex,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ int l = fromIndex;
+ int h = toIndex - 1;
+
+ while (l <= h) {
+ final int m = (l + h) >>> 1; // unsigned shift to avoid overflow
+ final K value = keyExtractor.apply(array[m]);
+ final int c = comparator.compare(value, key);
+ if (c < 0) {
+ l = m + 1;
+ } else if (c > 0) {
+ h = m - 1;
+ } else {
+ // 0, found
+ return m;
+ }
+ }
+
Review Comment:
What if there are no higher matches?
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch0(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Searches element in array sorted by key, within range fromIndex - toIndex (inclusive - exclusive).
+ *
+ * @param array
+ * array sorted by key field
+ * @param fromIndex
+ * start index
Review Comment:
add '(inclusive)' here
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1758717601
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
The use caee, I thought, was a version of the 'Arrays' method plus key extraction. I would not necessarily want an API that always allocates an array to return a value. Maybe do this later, as a second API only if needed.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1742870948
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
Review Comment:
Added.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1755500193
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,89 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Finds element in sorted array.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Finds element in sorted array, within range fromIndex - toIndex (inclusive - exclusive).
Review Comment:
"FInds" -> "Searches" since the API is called "search".
For compatibility with `java.util.Arrays.binarySearch(T[], [int, int,] T, Comparator<? super T>)`, you'll want to add range checks. From a call site's POV, I think the functionality should be the same as
- `java.util.Arrays.binarySearch(T[], int, int, T, Comparator<? super T>)` and
- `java.util.Arrays.binarySearch(T[], T, Comparator<? super T>)`
but with the addition of the key extractor feature.
Like `Arrays`, you might want to refactor into a `binarySearch0`.
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,89 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Finds element in sorted array.
Review Comment:
"FInds" -> "Searches" since the API is called "search".
##########
src/test/java/org/apache/commons/lang3/ArrayUtilsBinarySearchTest.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * 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.commons.lang3;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.stream.IntStream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * Unit tests {@link ArrayUtils} binarySearch functions.
+ */
+public class ArrayUtilsBinarySearchTest extends AbstractLangTest {
+
+ @Test
+ public void binarySearch_whenEmpty_returnM1() {
+ Data[] list = createList();
+ int found = ArrayUtils.binarySearch(list, 0, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenExists_returnIndex() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 9, Data::getValue, Integer::compare);
+ assertEquals(5, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExists_returnMinusInsertion() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 8, Data::getValue, Integer::compare);
+ assertEquals(-6, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsBeginning_returnMinus1() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, -3, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsEnd_returnMinusLength() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 29, Data::getValue, Integer::compare);
+ assertEquals(-(list.length + 1), found);
+ }
+
+ private Data[] createList(int... values) {
+ return IntStream.of(values).mapToObj(Data::new)
+ .toArray(Data[]::new);
+ }
+
+ public class Data
Review Comment:
The test fixture should be static and package-private.
##########
src/test/java/org/apache/commons/lang3/ArrayUtilsBinarySearchTest.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * 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.commons.lang3;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.stream.IntStream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * Unit tests {@link ArrayUtils} binarySearch functions.
+ */
+public class ArrayUtilsBinarySearchTest extends AbstractLangTest {
+
+ @Test
+ public void binarySearch_whenEmpty_returnM1() {
+ Data[] list = createList();
+ int found = ArrayUtils.binarySearch(list, 0, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenExists_returnIndex() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 9, Data::getValue, Integer::compare);
+ assertEquals(5, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExists_returnMinusInsertion() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 8, Data::getValue, Integer::compare);
+ assertEquals(-6, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsBeginning_returnMinus1() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, -3, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsEnd_returnMinusLength() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
Review Comment:
Use `final` where you can.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1757257699
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
The result should be documented as undefined if all array elements are equals; like `Arrays` version.
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
The result should be documented as undefined if all array elements are equals; like the `Arrays` version.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1756006366
##########
src/test/java/org/apache/commons/lang3/ArrayUtilsBinarySearchTest.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * 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.commons.lang3;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.stream.IntStream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * Unit tests {@link ArrayUtils} binarySearch functions.
+ */
+public class ArrayUtilsBinarySearchTest extends AbstractLangTest {
+
+ @Test
+ public void binarySearch_whenEmpty_returnM1() {
+ Data[] list = createList();
+ int found = ArrayUtils.binarySearch(list, 0, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenExists_returnIndex() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 9, Data::getValue, Integer::compare);
+ assertEquals(5, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExists_returnMinusInsertion() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 8, Data::getValue, Integer::compare);
+ assertEquals(-6, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsBeginning_returnMinus1() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, -3, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsEnd_returnMinusLength() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 29, Data::getValue, Integer::compare);
+ assertEquals(-(list.length + 1), found);
+ }
+
+ private Data[] createList(int... values) {
+ return IntStream.of(values).mapToObj(Data::new)
+ .toArray(Data[]::new);
+ }
+
+ public class Data
Review Comment:
Done
##########
src/test/java/org/apache/commons/lang3/ArrayUtilsBinarySearchTest.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * 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.commons.lang3;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.stream.IntStream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * Unit tests {@link ArrayUtils} binarySearch functions.
+ */
+public class ArrayUtilsBinarySearchTest extends AbstractLangTest {
+
+ @Test
+ public void binarySearch_whenEmpty_returnM1() {
+ Data[] list = createList();
+ int found = ArrayUtils.binarySearch(list, 0, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenExists_returnIndex() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 9, Data::getValue, Integer::compare);
+ assertEquals(5, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExists_returnMinusInsertion() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, 8, Data::getValue, Integer::compare);
+ assertEquals(-6, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsBeginning_returnMinus1() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
+ int found = ArrayUtils.binarySearch(list, -3, Data::getValue, Integer::compare);
+ assertEquals(-1, found);
+ }
+
+ @Test
+ public void binarySearch_whenNotExistsEnd_returnMinusLength() {
+ Data[] list = createList(0, 1, 2, 4, 7, 9, 12, 15, 17, 19, 25);
Review Comment:
Done
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1742870869
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted arrays.
+ *
+ * @author Zbynek Vyskovsky
Review Comment:
Done. I noticed it somewhere else but it seems legacy.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1741984262
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted arrays.
+ *
+ * @author Zbynek Vyskovsky
Review Comment:
We do not use `@author` tags, please remove it. Contributors are usually credited in `changes.xml` after a PR is merged.
##########
src/main/java/org/apache/commons/lang3/SortedListUtils.java:
##########
@@ -0,0 +1,89 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted {@link List}.
+ *
+ * @author Zbynek Vyskovsky
+ */
+public class SortedListUtils {
+ /**
+ * Finds element in sorted list.
+ *
+ * @param a
+ * list sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param c
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion
+ * point) - 1). The insertion point is defined as the point at which the key would be inserted into the array:
+ * the index of the first element in the range greater than the key, or toIndex if all elements in the range
+ * are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if
+ * the key is found.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(List<T> a, K key,
+ Function<T, K> keyExtractor, Comparator<? super K> c) {
+ return binarySearch(a, 0, a.size(), key, keyExtractor, c);
+ }
+
+ /**
+ * Finds element in sorted list, within range fromIndex - toIndex (inclusive - exclusive).
+ *
+ * @param a
+ * list sorted by key field
+ * @param fromIndex
+ * start index
+ * @param toIndex
+ * end index (exclusive)
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param c
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion
+ * point) - 1). The insertion point is defined as the point at which the key would be inserted into the array:
+ * the index of the first element in the range greater than the key, or toIndex if all elements in the range
+ * are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if
+ * the key is found.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <T, K> int binarySearch(List<T> a, int fromIndex, int toIndex, K key,
Review Comment:
This code looks like a copy-paste with small edits based on Java's `Arrays.binarySearch0()` method, this might violate Oracle's license. IOW, you can't copy the JDK's code. If we are serious about adding something like this, it has to be different or we'll need to check with our legal mailing list. Let's see what others think.
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
Review Comment:
All new files MUST carry the Apache license header:
```
/*
* 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.
*/
```
##########
src/main/java/org/apache/commons/lang3/SortedListUtils.java:
##########
@@ -0,0 +1,89 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted {@link List}.
+ *
+ * @author Zbynek Vyskovsky
+ */
+public class SortedListUtils {
Review Comment:
Collection utilities do not belong in Commons Lang IMO. This would be for Commons Collections unless this functionality is already there.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1757850118
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch0(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Searches element in array sorted by key, within range fromIndex - toIndex (inclusive - exclusive).
+ *
+ * @param array
+ * array sorted by key field
+ * @param fromIndex
+ * start index
+ * @param toIndex
+ * end index (exclusive)
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @throws ArrayIndexOutOfBoundsException
+ * when fromIndex or toIndex is out of array range
+ * @throws IllegalArgumentException
+ * when fromIndex is greater than toIndex
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <T, K> int binarySearch(
+ T[] array,
+ int fromIndex, int toIndex,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException(
+ "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+ }
+ if (fromIndex < 0) {
+ throw new ArrayIndexOutOfBoundsException(fromIndex);
+ }
+ if (toIndex > array.length) {
+ throw new ArrayIndexOutOfBoundsException(toIndex);
+ }
+
+ return binarySearch0(array, fromIndex, toIndex, key, keyExtractor, comparator);
+ }
+
+ // common implementation for binarySearch methods, with same semantics:
+ private static <T, K> int binarySearch0(
+ T[] array,
+ int fromIndex, int toIndex,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ int l = fromIndex;
+ int h = toIndex - 1;
+
+ while (l <= h) {
+ final int m = (l + h) >>> 1; // unsigned shift to avoid overflow
+ final K value = keyExtractor.apply(array[m]);
+ final int c = comparator.compare(value, key);
+ if (c < 0) {
+ l = m + 1;
+ } else if (c > 0) {
+ h = m - 1;
+ } else {
+ // 0, found
+ return m;
+ }
+ }
+
Review Comment:
Then `l` reaches `h+1` and exits the loop, returning `-toIndex - 1` as documented.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1756008217
##########
src/test/java/org/apache/commons/lang3/ArrayUtilsBinarySearchTest.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * 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.commons.lang3;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.stream.IntStream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * Unit tests {@link ArrayUtils} binarySearch functions.
+ */
+public class ArrayUtilsBinarySearchTest extends AbstractLangTest {
+
+ @Test
+ public void binarySearch_whenEmpty_returnM1() {
Review Comment:
I don't agree with this comment. The methods names are intentionally descriptive with pattern `name-condition-expected`. This improves readability. While there are truly only `binarySearch` now, it doesn't have to be forever and vice versa - this class may be possibly merged into more generic ones which would work with sorted arrays (which was the very original name).
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1756006548
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,89 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Finds element in sorted array.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Finds element in sorted array, within range fromIndex - toIndex (inclusive - exclusive).
Review Comment:
Done
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,89 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Finds element in sorted array.
Review Comment:
Done
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "sebbASF (via GitHub)" <gi...@apache.org>.
sebbASF commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1758299410
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
If there are multiple matches, would it not be better to return both indexes, so all the entries can be accessed?
Rather than return a single index, why not return first and last?
If they are the same, there is a unique match.
I'm not sure what the use case is for choosing either First or Last rather than both.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1759141591
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
> Sudden thought: surely key extraction can take place in the Comparator, so why is this method needed at all?
>
> Or maybe I am missing something?
Good point @sebbASF !
We might not need this at all...
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#issuecomment-2343707642
> > Hello @kvr000,
> > This code should be in `ArrayUtils`. TY!
>
> @garydgregory : Yeah, got it, was busy to finish that. Fixed now, thank you.
@kvr000
Run `mvn` (by itself) before you push to catch build errors.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1757257699
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
The result should be undefined if all array elements are equals; like `Arrays` version.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "sebbASF (via GitHub)" <gi...@apache.org>.
sebbASF commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1758995470
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
Sudden thought: surely key extraction can take place in the Comparator, so why is this method needed at all?
Or maybe I am missing something?
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1757936189
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
WRT binarySearchFirst and Last, let's not add those.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1759171390
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
@sebbASF @garydgregory :
> In the case of the 'Arrays' method, the entire entry is matched, so to some extent it does not matter which index is returned. That is not the case where a partial key is used, so I think in the user will often want to know all the matches.
In my particular case, I have list of GPS locations sorted by time and track distance, with distance unchanged if there was no move (causing duplicates). One use case is to find point for particular distance and if there are duplicates, I want the result to be predictable (here last but can be first in different use cases). If the result is unpredictable, it will lead to different results based on initial conditions for the search. I don't care about whole range, though I can imagine someone would appreciate such function with added complexity.
> Sudden thought: surely key extraction can take place in the Comparator, so why is this method needed at all?
No, unless we're able to construct the full object which is not always possible - note that `Comparator` takes two arguments of the same type. It is technically achievable with hacking and casting one argument to `T` and the other one to `K`, relying on internal implementation passing the arguments in expected order.
@garydgregory :
> Please revert the First/Last APIs.
For the reasons above, I want to keep those as they better match intended use case. I think we actually don't need original unpredictable `binarySearch()` .
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#issuecomment-2357420293
> @kvr000 Please revert the First/Last APIs.
@garydgregory : As explained in https://github.com/apache/commons-lang/pull/1270/#discussion_r1759171390 , I want to keep First/Last as I find them more useful due to their predictability. I don't think we really need original unpredictable simple binarySearch.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1749417221
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted arrays.
+ *
+ * @author Zbynek Vyskovsky
Review Comment:
Hello @kvr000
This only makes sense in the 'ArrayUtils' class IMO.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "sebbASF (via GitHub)" <gi...@apache.org>.
sebbASF commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1758991035
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
In the case of the 'Arrays' method, the entire entry is matched, so to some extent it does not matter which index is returned. That is not the case where a partial key is used, so I think in the user will often want to know all the matches.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1759171390
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
@sebbASF @garydgregory :
> In the case of the 'Arrays' method, the entire entry is matched, so to some extent it does not matter which index is returned. That is not the case where a partial key is used, so I think in the user will often want to know all the matches.
In my particular case, I have list of GPS locations sorted by time and track distance, with distance unchanged if there was no move (causing duplicates). One use case is to find point for particular distance and if there are duplicates, I want the result to be predictable (here last but can be first in different use cases). If the result is unpredictable, it will lead to different results based on initial conditions for the search. I don't care about whole range, though I can imagine someone would appreciate such function with added complexity.
> Sudden thought: surely key extraction can take place in the Comparator, so why is this method needed at all?
No, unless we're able to construct the full object which is not always possible - note that `Comparator` takes two arguments of the same type. It is technically achievable with hacking and casting one argument to `T` and the other one to `K`, relying on internal implementation passing the arguments in expected order but that would be super ugly and fragile to implementation changes.
@garydgregory :
> Please revert the First/Last APIs.
For the reasons above, I want to keep those as they better match intended use case. I think we actually don't need original unpredictable `binarySearch()` .
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1757845422
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch0(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Searches element in array sorted by key, within range fromIndex - toIndex (inclusive - exclusive).
+ *
+ * @param array
+ * array sorted by key field
+ * @param fromIndex
+ * start index
Review Comment:
Updated.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1742875196
##########
src/main/java/org/apache/commons/lang3/SortedListUtils.java:
##########
@@ -0,0 +1,89 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted {@link List}.
+ *
+ * @author Zbynek Vyskovsky
+ */
+public class SortedListUtils {
+ /**
+ * Finds element in sorted list.
+ *
+ * @param a
+ * list sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param c
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion
+ * point) - 1). The insertion point is defined as the point at which the key would be inserted into the array:
+ * the index of the first element in the range greater than the key, or toIndex if all elements in the range
+ * are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if
+ * the key is found.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(List<T> a, K key,
+ Function<T, K> keyExtractor, Comparator<? super K> c) {
+ return binarySearch(a, 0, a.size(), key, keyExtractor, c);
+ }
+
+ /**
+ * Finds element in sorted list, within range fromIndex - toIndex (inclusive - exclusive).
+ *
+ * @param a
+ * list sorted by key field
+ * @param fromIndex
+ * start index
+ * @param toIndex
+ * end index (exclusive)
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param c
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion
+ * point) - 1). The insertion point is defined as the point at which the key would be inserted into the array:
+ * the index of the first element in the range greater than the key, or toIndex if all elements in the range
+ * are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if
+ * the key is found.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <T, K> int binarySearch(List<T> a, int fromIndex, int toIndex, K key,
Review Comment:
Well, the `binarySearch()` is so common that everybody writes it the same way as we learnt in school 😁. I do understand your comment though.
I wrote the code with different names of variables, added explaining comments and different calculation of not-found result. There is little to do about the algorithm itself but the same algorithms appear everywhere, including Wiki, so Oracle definitely cannot claim license on this.
Hope this helps.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1757842403
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
Review Comment:
Updated to match non-index version.
@garydgregory : That is great point. In fact, one of my use cases is array (list) with duplicities. So this can be done better. I introduce `binarySearchFirst` and `binarySearchLast` methods which return consistently first and last matching element respectively.
##########
src/main/java/org/apache/commons/lang3/ArrayUtils.java:
##########
@@ -1432,6 +1432,115 @@ public static <T> T arraycopy(final T source, final int sourcePos, final T dest,
return dest;
}
+ /**
+ * Searches element in array sorted by key.
+ *
+ * @param array
+ * array sorted by key field
+ * @param key
+ * key to search for
+ * @param keyExtractor
+ * function to extract key from element
+ * @param comparator
+ * comparator for keys
+ *
+ * @return
+ * index of the search key, if it is contained in the array within specified range; otherwise,
+ * (-first_greater - 1). The first_greater is the index of lowest greater element in the list - if all elements
+ * are lower, the first_greater is defined as toIndex.
+ *
+ * @param <T>
+ * type of array element
+ * @param <K>
+ * type of key
+ */
+ public static <K, T> int binarySearch(
+ T[] array,
+ K key,
+ Function<T, K> keyExtractor, Comparator<? super K> comparator
+ ) {
+ return binarySearch0(array, 0, array.length, key, keyExtractor, comparator);
+ }
+
+ /**
+ * Searches element in array sorted by key, within range fromIndex - toIndex (inclusive - exclusive).
+ *
Review Comment:
Updated.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Add ArrayUtils.binarySearch() with a key extractor [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#issuecomment-2349116982
@kvr000
Please revert the First/Last APIs.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "garydgregory (via GitHub)" <gi...@apache.org>.
garydgregory commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1744665238
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted arrays.
+ *
+ * @author Zbynek Vyskovsky
Review Comment:
It just dawned on me that this new method would belong in the existing 'ArrayUtils' class.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1742870869
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted arrays.
+ *
+ * @author Zbynek Vyskovsky
Review Comment:
Done. I noticed it somewhere else seems legacy.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1742880453
##########
src/main/java/org/apache/commons/lang3/SortedListUtils.java:
##########
@@ -0,0 +1,89 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted {@link List}.
+ *
+ * @author Zbynek Vyskovsky
+ */
+public class SortedListUtils {
Review Comment:
I removed it. Unsure whether this was the best choice, as this is about the algorithm, not about implementing collections.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on code in PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#discussion_r1749303613
##########
src/main/java/org/apache/commons/lang3/SortedArrayUtils.java:
##########
@@ -0,0 +1,90 @@
+package org.apache.commons.lang3;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.function.Function;
+
+
+/**
+ * Operations on sorted arrays.
+ *
+ * @author Zbynek Vyskovsky
Review Comment:
@garydgregory : I thought about it originally but:
- `ArrayUtils` already contains quite a lot of functions and may become too messy. I agree it may not be a valid argument though.
- These functions require special semantics from the arrays (be sorted), so I thought it would be better to explicitly name the wrapping class.
I'm open to move them to `ArrayUtils` though, if you don't agree.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] binarySearch on sorted arrays and sorted lists [commons-lang]
Posted by "kvr000 (via GitHub)" <gi...@apache.org>.
kvr000 commented on PR #1270:
URL: https://github.com/apache/commons-lang/pull/1270#issuecomment-2342610208
> Hello @kvr000,
>
> This code should be in `ArrayUtils`. TY!
Yeah, got it, was busy to finish that. Fixed now, thank you.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org