## 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 ## -*- texinfo -*- ## @deftypefn {Function File} {} ismember(@var{A}, @var{S}) ## ## Return a matrix the same shape as @var{A} which has 1 if ## @code{A(i,j)} is in @var{S} or 0 if it isn't. ## ## @end deftypefn ## @seealso{unique, union, intersect, setxor, setdiff} function c = ismember(a,S) if nargin != 2 usage("ismember(A,S)"); endif [ra, ca] = size(a); if isempty(a) || isempty(S) c = zeros(ra, ca); else S = unique(S(:)); lt = length(S); if lt == 1 c = ( a == S ); elseif ra*ca == 1 c = any (a == S); else ## Magic : the following code determines for each a, the index i ## such that S(i)<= a < S(i+1). It does this by sorting the a ## into S and remembering the source index where each element came ## from. Since all the a's originally came after all the S's, if ## the source index is less than the length of S, then the element ## came from S. We can then do a cumulative sum on the indices to ## figure out which element of S each a comes after. ## E.g., S=[2 4 6], a=[1 2 3 4 5 6 7] ## unsorted [S a] = [ 2 4 6 1 2 3 4 5 6 7 ] ## sorted [ S a ] = [ 1 2 2 3 4 4 5 6 6 7 ] ## source index p = [ 4 1 5 6 2 7 8 3 9 10 ] ## boolean p<=l(S) = [ 0 1 0 0 1 0 0 1 0 0 ] ## cumsum(p<=l(S)) = [ 0 1 1 1 2 2 2 3 3 3 ] ## Note that this leaves a(1) coming after S(0) which doesn't ## exist. So arbitrarily, we will dump all elements less than ## S(1) into the interval after S(1). We do this by dropping S(1) ## from the sort! E.g., S=[2 4 6], a=[1 2 3 4 5 6 7] ## unsorted [S(2:3) a] =[4 6 1 2 3 4 5 6 7 ] ## sorted [S(2:3) a] = [ 1 2 3 4 4 5 6 6 7 ] ## source index p = [ 3 4 5 1 6 7 2 8 9 ] ## boolean p<=l(S)-1 = [ 0 0 0 1 0 0 1 0 0 ] ## cumsum(p<=l(S)-1) = [ 0 0 0 1 1 1 2 2 2 ] ## Now we can use Octave's lvalue indexing to "invert" the sort, ## and assign all these indices back to the appropriate A and S, ## giving S_idx = [ -- 1 2], a_idx = [ 0 0 0 1 1 2 2 ]. Add 1 to ## a_idx, and we know which interval S(i) contains a. It is ## easy to now check membership by comparing S(a_idx) == a. This ## magic works because S starts out sorted, and because sort ## preserves the relative order of identical elements. [v, p] = sort ( [ S(2:lt) ; a(:) ] ); idx(p) = cumsum (p <= lt-1) + 1; idx = idx (lt : lt+ra*ca-1); c = ( a == reshape (S (idx), size (a)) ); endif endif endfunction

Generated by Doxygen 1.6.0 Back to index