0000129: The locate() method in AbstractInterpolation leads to java.lang.ArrayIndexOutOfBoundsException.

(0000123)
Ueli Hofstetter (developer)
2009-02-05 21:00

use new upper_bound method in Std.java
************code

call return Std.upper_bound(vx, 0, vx.length-1,x) /*- not used xBegin_*/ -1; (the same for y in the 2d implementation)

add to Std.java
/**
     * Java implementation of std::upper_bound
     * @param list
     * @param fromIndex
     * @param toIndex
     * @param key
     * @return see upper_bound doc
     */

    public static int upper_bound(double[] list, int fromIndex, int toIndex, double key) {
        return Math.abs(custom_binarySearch(list, fromIndex, toIndex, key));
    }

    /**
     * Custom binary search. Does not decrement the standard result, if it is not found in the list, increment the index of a found value.
     * @param list an ordered list
     * @param fromIndex startIndex
     * @param toIndex endIndex
     * @param key key
     * @return binary_Search - 1
     */
    private static int custom_binarySearch(double[] list, int fromIndex, int toIndex, double key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            double midVal = list[mid];

            if (midVal < key){
                low = mid + 1;
            }
            else if (midVal > key){
                high = mid - 1;
            }
            else{
                return mid + 1;
            }
        }
        return -(low) ;
    }

(0000124)
Richard Gomes (manager)
2009-02-06 02:18

Ueli,

Please review your implementation against
http://acm.cs.uct.ac.za/docs/libstdc++-3.4/stl__algo_8h-source.html#l02712 [^]

... then make sure you have added the adequate copyright note to the method or class you have implemented and commit to SVN, please.

(0000128)
Ueli Hofstetter (developer)
2009-02-06 10:53

richard,

i rewrote upper_bound according to the c++ implementation you pointed to and tested it. should be ok.
however, there are two issues:
1. the use of iterators is imho to nasty in java. what do you mean?
(i add my implementation combined with the c++ implementation so that you can see the issue)
2. may we should add a copyright notice to Std.java, which points to the c++ gnu implementation (i guess the other stuff is from there too)

cheers

ueli

****code
/**
     * Java implementation of std::upper_bound
     * @param list
     * @param fromIndex
     * @param toIndex
     * @param val
     * @return see upper_bound doc
     */
    public static /*_ForwardIterator*/ int upper_bound(final double[] list, /*_ForwardIterator _first*/ int first, /*_ForwardIterator _last*/int last , final double val){
        //_DistanceType __len = std::distance(__first, __last);
        int len = last - first;
        //_DistanceType __half;
        int half;
        //_ForwardIterator __middle;
        int middle;

        while(len > 0){
            //__half = __len >> 1;
            half = len >>> 1;
            //__middle = __first;
            //std::advance(__middle, __half);
            middle = first;
            middle = middle + half;

            //if(val < *__middle)
            if (val < list[middle]){
                //__len = __half;
                len = half;
            }
            else{
                //__first = __middle;
                first = middle;
                //++__first;
                first++;
                //__len = __len - __half - 1;
                len = len - half -1;
            }
        }
        //return __first;
        return first;
    }

(0000130)
Richard Gomes (manager)
2009-02-06 11:25

Hi Ueli,

I'm sorry if I was not very clear.
I meant that it's a good idea to verify our implementation against the [original] STL mainly because we are providing an equivalent thing which 'ideally' must have the same behaviour. For this reason, I pointed out the original source code. I was not meaning that you should rewrite it and/or use the exact the same object model, but only review to see if something important was missing.

I'm sorry for this failure of communication.
Communication is always an issue much bigger than we expect. :(

As we are providing something equivalent to STL, we potentially should mimic STL as close as possible but I'm afraid that some C/C++ constructs are not desirable in Java.

A point to consider is that JQuantLib has internal translations for STL but JQuantLib is not willing to become a reference implementation of STL in Java. We are translating only what we need and for our internal purposes only. So, it's needed to balance the correctness and beauty we need against the time we are willing to spend on it.

Thanks a lot! :)

(0000131)
Richard Gomes (manager)
2009-02-06 11:27

You can change status to feedback and press the button.
A new form appears and you can choose the person to be assigned and add a note like this. :)

(0000133)
Ueli Hofstetter (developer)
2009-02-06 13:31

hi there,

that's completely io. pointing me to the implementation. the other one was a nasty hack ;-).

i let the c++ comments in the code, in the case the algo. turns out to be buggy. but feel free to remove them.

(0000360)
Richard Gomes (manager)
2009-06-26 20:19

done

Issue History
Date Modified	Username	Field	Change
2009-01-11 15:18	Daniel Kong	New Issue
2009-01-14 01:24	Richard Gomes	Relationship added	related to 0000004
2009-01-14 01:24	Richard Gomes	Issue Monitored: Dominik Holenstein
2009-01-14 01:24	Richard Gomes	Issue Monitored: Gary Kennedy
2009-01-25 22:43	Richard Gomes	Target Version	=> 0.1.2
2009-01-25 23:42	Richard Gomes	Relationship added	child of 0000141
2009-02-04 01:17	Ueli Hofstetter	Status	new => assigned
2009-02-04 01:17	Ueli Hofstetter	Assigned To	=> Ueli Hofstetter
2009-02-05 21:00	Ueli Hofstetter	Note Added: 0000123
2009-02-05 21:01	Ueli Hofstetter	Assigned To	Ueli Hofstetter => Richard Gomes
2009-02-06 02:18	Richard Gomes	Note Added: 0000124
2009-02-06 02:18	Richard Gomes	Assigned To	Richard Gomes => Ueli Hofstetter
2009-02-06 10:53	Ueli Hofstetter	Note Added: 0000128
2009-02-06 10:54	Ueli Hofstetter	Assigned To	Ueli Hofstetter => Richard Gomes
2009-02-06 11:25	Richard Gomes	Note Added: 0000130
2009-02-06 11:27	Richard Gomes	Note Added: 0000131
2009-02-06 11:27	Richard Gomes	Assigned To	Richard Gomes => Ueli Hofstetter
2009-02-06 11:27	Richard Gomes	Status	assigned => feedback
2009-02-06 13:31	Ueli Hofstetter	Note Added: 0000133
2009-02-08 05:53	Richard Gomes	Status	feedback => resolved
2009-02-08 05:53	Richard Gomes	Resolution	open => fixed
2009-06-26 20:01	Richard Gomes	Relationship added	child of 0000067
2009-06-26 20:19	Richard Gomes	Note Added: 0000360
2009-06-26 20:19	Richard Gomes	Status	resolved => closed
2009-06-26 20:19	Richard Gomes	Fixed in Version	=> 0.1.3

Notes
(0000123) Ueli Hofstetter (developer) 2009-02-05 21:00	use new upper_bound method in Std.java ***********code call return Std.upper_bound(vx, 0, vx.length-1,x) /- not used xBegin_/ -1; (the same for y in the 2d implementation) add to Std.java /* * Java implementation of std::upper_bound * @param list * @param fromIndex * @param toIndex * @param key * @return see upper_bound doc / public static int upper_bound(double[] list, int fromIndex, int toIndex, double key) { return Math.abs(custom_binarySearch(list, fromIndex, toIndex, key)); } /* * Custom binary search. Does not decrement the standard result, if it is not found in the list, increment the index of a found value. * @param list an ordered list * @param fromIndex startIndex * @param toIndex endIndex * @param key key * @return binary_Search - 1 */ private static int custom_binarySearch(double[] list, int fromIndex, int toIndex, double key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; double midVal = list[mid]; if (midVal < key){ low = mid + 1; } else if (midVal > key){ high = mid - 1; } else{ return mid + 1; } } return -(low) ; }

(0000124) Richard Gomes (manager) 2009-02-06 02:18	Ueli, Please review your implementation against http://acm.cs.uct.ac.za/docs/libstdc++-3.4/stl__algo_8h-source.html#l02712 [^] ... then make sure you have added the adequate copyright note to the method or class you have implemented and commit to SVN, please.

(0000128) Ueli Hofstetter (developer) 2009-02-06 10:53	richard, i rewrote upper_bound according to the c++ implementation you pointed to and tested it. should be ok. however, there are two issues: 1. the use of iterators is imho to nasty in java. what do you mean? (i add my implementation combined with the c++ implementation so that you can see the issue) 2. may we should add a copyright notice to Std.java, which points to the c++ gnu implementation (i guess the other stuff is from there too) cheers ueli **code / * Java implementation of std::upper_bound * @param list * @param fromIndex * @param toIndex * @param val * @return see upper_bound doc / public static /_ForwardIterator/ int upper_bound(final double[] list, /_ForwardIterator _first/ int first, /_ForwardIterator _last/int last , final double val){ //_DistanceType __len = std::distance(__first, __last); int len = last - first; //_DistanceType __half; int half; //_ForwardIterator __middle; int middle; while(len > 0){ //__half = __len >> 1; half = len >>> 1; //__middle = __first; //std::advance(__middle, __half); middle = first; middle = middle + half; //if(val < __middle) if (val < list[middle]){ //__len = __half; len = half; } else{ //__first = __middle; first = middle; //++__first; first++; //__len = __len - __half - 1; len = len - half -1; } } //return __first; return first; }

(0000130) Richard Gomes (manager) 2009-02-06 11:25	Hi Ueli, I'm sorry if I was not very clear. I meant that it's a good idea to verify our implementation against the [original] STL mainly because we are providing an equivalent thing which 'ideally' must have the same behaviour. For this reason, I pointed out the original source code. I was not meaning that you should rewrite it and/or use the exact the same object model, but only review to see if something important was missing. I'm sorry for this failure of communication. Communication is always an issue much bigger than we expect. :( As we are providing something equivalent to STL, we potentially should mimic STL as close as possible but I'm afraid that some C/C++ constructs are not desirable in Java. A point to consider is that JQuantLib has internal translations for STL but JQuantLib is not willing to become a reference implementation of STL in Java. We are translating only what we need and for our internal purposes only. So, it's needed to balance the correctness and beauty we need against the time we are willing to spend on it. Thanks a lot! :)

(0000131) Richard Gomes (manager) 2009-02-06 11:27	You can change status to feedback and press the button. A new form appears and you can choose the person to be assigned and add a note like this. :)

(0000133) Ueli Hofstetter (developer) 2009-02-06 13:31	hi there, that's completely io. pointing me to the implementation. the other one was a nasty hack ;-). i let the c++ comments in the code, in the case the algo. turns out to be buggy. but feel free to remove them.

(0000360) Richard Gomes (manager) 2009-06-26 20:19	done