1542 int mid = (low + high) >>> 1;
1543 mergeSort(dest, src, low, mid, -off, c);
1544 mergeSort(dest, src, mid, high, -off, c);
1545
1546 // If list is already sorted, just copy from src to dest. This is an
1547 // optimization that results in faster sorts for nearly ordered lists.
1548 if (c.compare(src[mid-1], src[mid]) <= 0) {
1549 System.arraycopy(src, low, dest, destLow, length);
1550 return;
1551 }
1552
1553 // Merge sorted halves (now in src) into dest
1554 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1555 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1556 dest[i] = src[p++];
1557 else
1558 dest[i] = src[q++];
1559 }
1560 }
1561
1562 // Searching
1563
1564 /**
1565 * Searches the specified array of longs for the specified value using the
1566 * binary search algorithm. The array must be sorted (as
1567 * by the {@link #sort(long[])} method) prior to making this call. If it
1568 * is not sorted, the results are undefined. If the array contains
1569 * multiple elements with the specified value, there is no guarantee which
1570 * one will be found.
1571 *
1572 * @param a the array to be searched
1573 * @param key the value to be searched for
1574 * @return index of the search key, if it is contained in the array;
1575 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1576 * <i>insertion point</i> is defined as the point at which the
1577 * key would be inserted into the array: the index of the first
1578 * element greater than the key, or <tt>a.length</tt> if all
1579 * elements in the array are less than the specified key. Note
1580 * that this guarantees that the return value will be >= 0 if
1581 * and only if the key is found.
|
1542 int mid = (low + high) >>> 1;
1543 mergeSort(dest, src, low, mid, -off, c);
1544 mergeSort(dest, src, mid, high, -off, c);
1545
1546 // If list is already sorted, just copy from src to dest. This is an
1547 // optimization that results in faster sorts for nearly ordered lists.
1548 if (c.compare(src[mid-1], src[mid]) <= 0) {
1549 System.arraycopy(src, low, dest, destLow, length);
1550 return;
1551 }
1552
1553 // Merge sorted halves (now in src) into dest
1554 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1555 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1556 dest[i] = src[p++];
1557 else
1558 dest[i] = src[q++];
1559 }
1560 }
1561
1562 // Parallel prefix
1563
1564 /**
1565 * Cumulates in parallel each element of the given array in place,
1566 * using the supplied function. For example if the array initially
1567 * holds {@code [2, 1, 0, 3]} and the operation performs addition,
1568 * then upon return the array holds {@code [2, 3, 3, 6]}.
1569 * Parallel prefix computation is usually more efficient than
1570 * sequential loops for large arrays.
1571 *
1572 * @param array the array, which is modified in-place by this method
1573 * @param op a side-effect-free, associative function to perform the
1574 * cumulation
1575 * @throws NullPointerException if the specified array or function is null
1576 * @since 1.8
1577 */
1578 public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) {
1579 if (array.length > 0)
1580 new ArrayPrefixHelpers.CumulateTask<>
1581 (null, op, array, 0, array.length).invoke();
1582 }
1583
1584 /**
1585 * Performs {@link #parallelPrefix(Object[], BinaryOperator)}
1586 * for the given subrange of the array.
1587 *
1588 * @param array the array
1589 * @param fromIndex the index of the first element, inclusive
1590 * @param toIndex the index of the last element, exclusive
1591 * @param op a side-effect-free, associative function to perform the
1592 * cumulation
1593 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1594 * @throws ArrayIndexOutOfBoundsException
1595 * if {@code fromIndex < 0} or {@code toIndex > array.length}
1596 * @throws NullPointerException if the specified array or function is null
1597 * @since 1.8
1598 */
1599 public static <T> void parallelPrefix(T[] array, int fromIndex,
1600 int toIndex, BinaryOperator<T> op) {
1601 rangeCheck(array.length, fromIndex, toIndex);
1602 if (fromIndex < toIndex)
1603 new ArrayPrefixHelpers.CumulateTask<>
1604 (null, op, array, fromIndex, toIndex).invoke();
1605 }
1606
1607 /**
1608 * Cumulates in parallel each element of the given array in place,
1609 * using the supplied function. For example if the array initially
1610 * holds {@code [2, 1, 0, 3]} and the operation performs addition,
1611 * then upon return the array holds {@code [2, 3, 3, 6]}.
1612 * Parallel prefix computation is usually more efficient than
1613 * sequential loops for large arrays.
1614 *
1615 * @param array the array, which is modified in-place by this method
1616 * @param op a side-effect-free, associative function to perform the
1617 * cumulation
1618 * @throws NullPointerException if the specified array or function is null
1619 * @since 1.8
1620 */
1621 public static void parallelPrefix(long[] array, LongBinaryOperator op) {
1622 if (array.length > 0)
1623 new ArrayPrefixHelpers.LongCumulateTask
1624 (null, op, array, 0, array.length).invoke();
1625 }
1626
1627 /**
1628 * Performs {@link #parallelPrefix(long[], LongBinaryOperator)}
1629 * for the given subrange of the array.
1630 *
1631 * @param array the array
1632 * @param fromIndex the index of the first element, inclusive
1633 * @param toIndex the index of the last element, exclusive
1634 * @param op a side-effect-free, associative function to perform the
1635 * cumulation
1636 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1637 * @throws ArrayIndexOutOfBoundsException
1638 * if {@code fromIndex < 0} or {@code toIndex > array.length}
1639 * @throws NullPointerException if the specified array or function is null
1640 * @since 1.8
1641 */
1642 public static void parallelPrefix(long[] array, int fromIndex,
1643 int toIndex, LongBinaryOperator op) {
1644 rangeCheck(array.length, fromIndex, toIndex);
1645 if (fromIndex < toIndex)
1646 new ArrayPrefixHelpers.LongCumulateTask
1647 (null, op, array, fromIndex, toIndex).invoke();
1648 }
1649
1650 /**
1651 * Cumulates in parallel each element of the given array in place,
1652 * using the supplied function. For example if the array initially
1653 * holds {@code [2, 1, 0, 3]} and the operation performs addition,
1654 * then upon return the array holds {@code [2, 3, 3, 6]}.
1655 * Parallel prefix computation is usually more efficient than
1656 * sequential loops for large arrays.
1657 *
1658 * @param array the array, which is modified in-place by this method
1659 * @param op a side-effect-free, associative function to perform the
1660 * cumulation
1661 * @throws NullPointerException if the specified array or function is null
1662 * @since 1.8
1663 */
1664 public static void parallelPrefix(double[] array, DoubleBinaryOperator op) {
1665 if (array.length > 0)
1666 new ArrayPrefixHelpers.DoubleCumulateTask
1667 (null, op, array, 0, array.length).invoke();
1668 }
1669
1670 /**
1671 * Performs {@link #parallelPrefix(double[], DoubleBinaryOperator)}
1672 * for the given subrange of the array.
1673 *
1674 * @param array the array
1675 * @param fromIndex the index of the first element, inclusive
1676 * @param toIndex the index of the last element, exclusive
1677 * @param op a side-effect-free, associative function to perform the
1678 * cumulation
1679 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1680 * @throws ArrayIndexOutOfBoundsException
1681 * if {@code fromIndex < 0} or {@code toIndex > array.length}
1682 * @throws NullPointerException if the specified array or function is null
1683 * @since 1.8
1684 */
1685 public static void parallelPrefix(double[] array, int fromIndex,
1686 int toIndex, DoubleBinaryOperator op) {
1687 rangeCheck(array.length, fromIndex, toIndex);
1688 if (fromIndex < toIndex)
1689 new ArrayPrefixHelpers.DoubleCumulateTask
1690 (null, op, array, fromIndex, toIndex).invoke();
1691 }
1692
1693 /**
1694 * Cumulates in parallel each element of the given array in place,
1695 * using the supplied function. For example if the array initially
1696 * holds {@code [2, 1, 0, 3]} and the operation performs addition,
1697 * then upon return the array holds {@code [2, 3, 3, 6]}.
1698 * Parallel prefix computation is usually more efficient than
1699 * sequential loops for large arrays.
1700 *
1701 * @param array the array, which is modified in-place by this method
1702 * @param op a side-effect-free, associative function to perform the
1703 * cumulation
1704 * @throws NullPointerException if the specified array or function is null
1705 * @since 1.8
1706 */
1707 public static void parallelPrefix(int[] array, IntBinaryOperator op) {
1708 if (array.length > 0)
1709 new ArrayPrefixHelpers.IntCumulateTask
1710 (null, op, array, 0, array.length).invoke();
1711 }
1712
1713 /**
1714 * Performs {@link #parallelPrefix(int[], IntBinaryOperator)}
1715 * for the given subrange of the array.
1716 *
1717 * @param array the array
1718 * @param fromIndex the index of the first element, inclusive
1719 * @param toIndex the index of the last element, exclusive
1720 * @param op a side-effect-free, associative function to perform the
1721 * cumulation
1722 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1723 * @throws ArrayIndexOutOfBoundsException
1724 * if {@code fromIndex < 0} or {@code toIndex > array.length}
1725 * @throws NullPointerException if the specified array or function is null
1726 * @since 1.8
1727 */
1728 public static void parallelPrefix(int[] array, int fromIndex,
1729 int toIndex, IntBinaryOperator op) {
1730 rangeCheck(array.length, fromIndex, toIndex);
1731 if (fromIndex < toIndex)
1732 new ArrayPrefixHelpers.IntCumulateTask
1733 (null, op, array, fromIndex, toIndex).invoke();
1734 }
1735
1736 // Searching
1737
1738 /**
1739 * Searches the specified array of longs for the specified value using the
1740 * binary search algorithm. The array must be sorted (as
1741 * by the {@link #sort(long[])} method) prior to making this call. If it
1742 * is not sorted, the results are undefined. If the array contains
1743 * multiple elements with the specified value, there is no guarantee which
1744 * one will be found.
1745 *
1746 * @param a the array to be searched
1747 * @param key the value to be searched for
1748 * @return index of the search key, if it is contained in the array;
1749 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1750 * <i>insertion point</i> is defined as the point at which the
1751 * key would be inserted into the array: the index of the first
1752 * element greater than the key, or <tt>a.length</tt> if all
1753 * elements in the array are less than the specified key. Note
1754 * that this guarantees that the return value will be >= 0 if
1755 * and only if the key is found.
|