Diff of /lookup.m [000000] .. [67a5bd]  Maximize  Restore

  Switch to side-by-side view

--- a
+++ b/lookup.m
@@ -0,0 +1,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 <kai.habel@gmx.de> 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]);

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks