Mercurial > octave-nkf

comparison liboctave/Array.cc @ 9921:7c8392a034e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix & improve lookup API
author Jaroslav Hajek <highegg@gmail.com>
date Sat, 05 Dec 2009 06:10:41 +0100
parents 56fbe170d354
children bb30843c4929
comparison
equal deleted inserted replaced
9920:56fbe170d354 9921:7c8392a034e6
2240 Array<octave_idx_type> 2240 Array<octave_idx_type>
2241 Array<T>::sort_rows_idx (sortmode mode) const 2241 Array<T>::sort_rows_idx (sortmode mode) const
2242 { 2242 {
2243 Array<octave_idx_type> idx; 2243 Array<octave_idx_type> idx;
2244 2244
2245 octave_sort<T> lsort; 2245 octave_sort<T> lsort (safe_comparator (mode, *this, true));
2246
2247 lsort.set_compare (safe_comparator (mode, *this, true));
2248 2246
2249 octave_idx_type r = rows (), c = cols (); 2247 octave_idx_type r = rows (), c = cols ();
2250 2248
2251 idx = Array<octave_idx_type> (r); 2249 idx = Array<octave_idx_type> (r);
2252 2250
2334 lsort.set_compare (mode); 2332 lsort.set_compare (mode);
2335 2333
2336 return lsort.lookup (data (), n, value); 2334 return lsort.lookup (data (), n, value);
2337 } 2335 }
2338 2336
2339 // Ditto, but for an array of values, specializing on long runs.
2340 // Adds optional offset to all indices.
2341 template <class T> 2337 template <class T>
2342 Array<octave_idx_type> 2338 Array<octave_idx_type>
2343 Array<T>::lookup (const Array<T>& values, sortmode mode, 2339 Array<T>::lookup (const Array<T>& values, sortmode mode) const
2344 bool linf, bool rinf) const 2340 {
2345 { 2341 octave_idx_type n = numel (), nval = values.numel ();
2346 octave_idx_type n = numel ();
2347 octave_sort<T> lsort; 2342 octave_sort<T> lsort;
2348 Array<octave_idx_type> idx (values.dims ()); 2343 Array<octave_idx_type> idx (values.dims ());
2349 2344
2350 if (mode == UNSORTED) 2345 if (mode == UNSORTED)
2351 { 2346 {
2356 mode = ASCENDING; 2351 mode = ASCENDING;
2357 } 2352 }
2358 2353
2359 lsort.set_compare (mode); 2354 lsort.set_compare (mode);
2360 2355
2361 // set offset and shift size. 2356 // This determines the split ratio between the O(M*log2(N)) and O(M+N) algorithms.
2362 octave_idx_type offset = 0; 2357 static const double ratio = 1.0;
2363 2358 sortmode vmode = UNSORTED;
2364 if (linf && n > 0) 2359
2365 { 2360 // Attempt the O(M+N) algorithm if M is large enough.
2366 offset++; 2361 if (nval > ratio * n / xlog2 (n + 1.0))
2367 n--; 2362 {
2368 } 2363 vmode = values.is_sorted ();
2369 if (rinf && n > 0) 2364 // The table must not contain a NaN.
2370 n--; 2365 if ((vmode == ASCENDING && sort_isnan<T> (values(nval-1)))
2371 2366 || (vmode == DESCENDING && sort_isnan<T> (values(0))))
2372 lsort.lookup (data () + offset, n, values.data (), values.numel (), 2367 vmode = UNSORTED;
2373 idx.fortran_vec (), offset); 2368 }
2369
2370 if (vmode != UNSORTED)
2371 lsort.lookup_sorted (data (), n, values.data (), nval,
2372 idx.fortran_vec (), vmode != mode);
2373 else
2374 lsort.lookup (data (), n, values.data (), nval, idx.fortran_vec ());
2374 2375
2375 return idx; 2376 return idx;
2376 }
2377
2378 template <class T>
2379 Array<octave_idx_type>
2380 Array<T>::lookupm (const Array<T>& values, sortmode mode) const
2381 {
2382 octave_idx_type n = numel ();
2383 octave_sort<T> lsort;
2384 Array<octave_idx_type> idx (values.dims ());
2385
2386 if (mode == UNSORTED)
2387 {
2388 // auto-detect mode
2389 if (n > 1 && lsort.descending_compare (elem (0), elem (n-1)))
2390 mode = DESCENDING;
2391 else
2392 mode = ASCENDING;
2393 }
2394
2395 lsort.set_compare (mode);
2396
2397 lsort.lookupm (data (), n, values.data (), values.numel (),
2398 idx.fortran_vec ());
2399
2400 return idx;
2401 }
2402
2403 template <class T>
2404 Array<bool>
2405 Array<T>::lookupb (const Array<T>& values, sortmode mode) const
2406 {
2407 octave_idx_type n = numel ();
2408 octave_sort<T> lsort;
2409 Array<bool> match (values.dims ());
2410
2411 if (mode == UNSORTED)
2412 {
2413 // auto-detect mode
2414 if (n > 1 && lsort.descending_compare (elem (0), elem (n-1)))
2415 mode = DESCENDING;
2416 else
2417 mode = ASCENDING;
2418 }
2419
2420 lsort.set_compare (mode);
2421
2422 lsort.lookupb (data (), n, values.data (), values.numel (),
2423 match.fortran_vec ());
2424
2425 return match;
2426 } 2377 }
2427 2378
2428 template <class T> 2379 template <class T>
2429 octave_idx_type 2380 octave_idx_type
2430 Array<T>::nnz (void) const 2381 Array<T>::nnz (void) const
2698 \ 2649 \
2699 template <> octave_idx_type \ 2650 template <> octave_idx_type \
2700 Array<T>::lookup (T const &, sortmode) const \ 2651 Array<T>::lookup (T const &, sortmode) const \
2701 { return 0; } \ 2652 { return 0; } \
2702 template <> Array<octave_idx_type> \ 2653 template <> Array<octave_idx_type> \
2703 Array<T>::lookup (const Array<T>&, sortmode, bool, bool) const \ 2654 Array<T>::lookup (const Array<T>&, sortmode) const \
2704 { return Array<octave_idx_type> (); } \ 2655 { return Array<octave_idx_type> (); } \
2705 template <> Array<octave_idx_type> \
2706 Array<T>::lookupm (const Array<T>&, sortmode) const \
2707 { return Array<octave_idx_type> (); } \
2708 template <> Array<bool> \
2709 Array<T>::lookupb (const Array<T>&, sortmode) const \
2710 { return Array<bool> (); } \
2711 \ 2656 \
2712 template <> octave_idx_type \ 2657 template <> octave_idx_type \
2713 Array<T>::nnz (void) const\ 2658 Array<T>::nnz (void) const\
2714 { return 0; } \ 2659 { return 0; } \
2715 template <> Array<octave_idx_type> \ 2660 template <> Array<octave_idx_type> \