Looking for something similar to Python's bisect_right

Zeke lcarsos at lcarsos.com
Tue Oct 29 23:04:25 PDT 2013


Hello, I'm on day 2 of learning D. I've learned C, C++, Java, 
Python, Ruby in University, but I wanted to broaden my palette by 
picking up D.

This project is a basic implementation of Project Euler problem 
10. I build an array of primes, and for each new test number I 
check if the test is divisible by any prime from 2 to sqrt(test) 
(which cuts down on number of iterations). Trouble is, I can't 
find a method that's in the libraries to calculate the index of 
where sqrt(test) would exist or would be inserted into a sorted 
array.

I tried casting the primes array to a SortedRange using 
assumeSorted() but it didn't work for me. countUntil() returns -1 
if the value doesn't exist. and I didn't find anything in the 
std.algorithm, std.array, or std.container.

Here's my current working implementation of is_prime and the 
functions it uses:

pure nothrow @safe bool is_prime(in ulong[] primes, ulong num) {
     // Need to find a more elegant way to find the index of where 
a number's
     // square root would be in a sorted array.
     auto upper = insind(primes, cast(ulong)sqrt(cast(double)num)) 
+ 1;
     // Check each prime in the array up to the square root of our 
current test
     // number to see if it is prime.
     foreach(ulong prime; primes[0..upper]) {
         if (num % prime == 0) {
             return false;
         }
     }
     return true;
}

/**
  * Friendly overload so I don't have to give the bounds of the 
array for the
  * recursive step.
  */
pure nothrow @safe ulong
insind(in ulong[] arr, ulong key)
{
     return insind(arr, key, 0, arr.length);
}

/**
  * Using tail-recursion (so we don't build up a huge call stack), 
binary search
  * the array for the index where the key would be found if it 
existed or were
  * to be inserted into the array.
  */
pure nothrow @safe ulong
insind(in ulong[] arr, ulong key, ulong lower, ulong upper)
{
     if (lower >= upper) {
         return lower;
     } else {
         ulong mid = (lower + upper) / 2;
         if (arr[mid] > key) {
             return insind(arr, key, lower, mid - 1);
         } else if (arr[mid] < key) {
             return insind(arr, key, mid + 1, upper);
         } else {
             return mid;
         }
     }
}

I would also appreciate tips to help my "D-ness" coding style 
develop.


More information about the Digitalmars-d-learn mailing list