## [67a5bd]: lookup.m  Maximize  Restore  History

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82``` ```## Copyright (C) 2000 Paul Kienzle ## ## This program is free software; you can redistribute it and/or modify ## it under the terms of the GNU General Public License as published by ## the Free Software Foundation; either version 2 of the License, or ## (at your option) any later version. ## ## This program is distributed in the hope that it will be useful, ## but WITHOUT ANY WARRANTY; without even the implied warranty of ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ## GNU General Public License for more details. ## ## You should have received a copy of the GNU General Public License ## along with this program; if not, write to the Free Software ## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA ## usage: idx = lookup(table, y) ## ## If table is strictly increasing and idx=lookup(table, y), then ## table(idx(i)) <= y(i) < table(idx(i+1)) ## for all y(i) within the table. If y(i) is before the table, then ## idx(i) is 0. If y(i) is after the table then idx(i) is table(n). ## If the table is strictly decreasing, then the tests are reversed. ## No guarantees for tables which are non-monotonic or are not strictly ## monotonic. ## ## To get an index value which lies within an interval of the table ## use: ## idx = lookup(table(2:length(table)-1), y) - 1 ## This puts values before the table into the first interval, and values ## after the table into the last interval. ## Changed from binary search to sort. ## Thanks to Kai Habel for the suggestion. ## TODO: sort-based lookup is significantly slower given a large table ## TODO: and small lookup vector. This shouldn't be a problem since ## TODO: interpolation (the reason for the table lookup in the first ## TODO: place) usually involves subsampling of an existing table. The ## TODO: other use of interpolation, looking up values one at a time, is ## TODO: unfortunately significantly slower for large tables. ## TODO: sort is order O((lt+lx)*log(lt+lx)) ## TODO: search is order O(lx*log(lt)) ## TODO: Clearly, search is asymptotically better than sort, but sort ## TODO: is compiled and search is not. Could support both, or recode ## TODO: search in C++, or assume things are good enough as they stand. function idx=lookup(table,xi) if isempty (table) idx = zeros(size(xi)); elseif is_vector(table) [nr, nc] = size(xi); lt=length(table); if ( table(1) > table(lt) ) ## decreasing table [v, p] = sort ([xi(:) ; table(:)]); idx (p) = cumsum (p > nr*nc); idx = lt - idx (1 : nr*nc); else ## increasing table [v, p] = sort ([table(:) ; xi(:) ]); idx (p) = cumsum (p <= lt); idx = idx (lt+1 : lt+nr*nc); endif idx = reshape (idx, nr, nc); else error ("lookup: table must be a vector"); endif endfunction %!assert (lookup(1:3, 0.5), 0) # value before table %!assert (lookup(1:3, 3.5), 3) # value after table error %!assert (lookup(1:3, 1.5), 1) # value within table error %!assert (lookup(1:3, [3,2,1]), [3,2,1]) %!assert (lookup([1:4]', [1.2, 3.5]'), [1, 3]'); %!assert (lookup([1:4], [1.2, 3.5]'), [1, 3]'); %!assert (lookup([1:4]', [1.2, 3.5]), [1, 3]); %!assert (lookup([1:4], [1.2, 3.5]), [1, 3]); %!assert (lookup(1:3, [3, 2, 1]), [3, 2, 1]); %!assert (lookup([3:-1:1], [3.5, 3, 1.2, 2.5, 2.5]), [0, 1, 2, 1, 1]) %!assert (isempty(lookup([1:3], []))) %!assert (isempty(lookup([1:3]', []))) %!assert (lookup(1:3, [1, 2; 3, 0.5]), [1, 2; 3, 0]); ```