Mercurial > repos > prog > lcmsmatching

annotate search.R @ 0:3afe41d3e9e7 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
author prog
date Mon, 11 Jul 2016 09:12:03 -0400
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
1 if ( ! exists('binary.search')) { # Do not load again if already loaded
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
2
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
3 # Run a binary search on a sorted array.
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
4 # val The value to search.
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
5 # tab The array of values, sorted in ascending order.
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
6 # lower If set to NA, then search for the first value found by the binary search. If set to TRUE, find the value with the lowest index in the array. If set to FALSE, find the value with the highest index in the array.
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
7 # first The index of the array from which to start (1 by default).
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
8 # last The index of the array where to stop searching (end of the array by default).
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
9 # Returns the index of the found value, or NA.
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
10 binary.search <- function(val, tab, lower = NA, first = 1L, last = length(tab))
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
11 {
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
12 # Check array & value
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
13 if (is.null(tab))
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
14 stop('Argument "tab" is NULL.')
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
15 if (is.null(val))
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
16 stop('Argument "val" is NULL.')
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
17
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
18 # Wrong arguments
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
19 if (is.na(val) || last < first || length(tab) == 0)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
20 return(NA_integer_)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
21
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
22 # Find value
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
23 l <- first
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
24 h <- last
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
25 while (h >= l) {
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
26
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
27 # Take middle point
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
28 m <- (h + l) %/% 2
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
29 # Found value
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
30 if (tab[m] == val) {
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
31 if (is.na(lower))
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
32 return(m)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
33 if (lower && m > first) {
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
34 for (i in (m-1):first)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
35 if (tab[i] != val)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
36 return(i+1)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
37 }
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
38 else if ( ! lower && m < last)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
39 for (i in (m+1):last)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
40 if (tab[i] != val)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
41 return(i-1)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
42 return(m)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
43 }
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
44
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
45 # Decrease higher bound
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
46 else if (tab[m] > val) h <- m - 1
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
47
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
48 # Increase lower bound
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
49 else l <- m + 1
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
50 }
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
51
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
52 # Value not found
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
53 if ( ! is.na(lower)) {
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
54 # Look for lower or higher bound
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
55 if (lower)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
56 return(if (h < first) NA_integer_ else h)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
57 else
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
58 return(if (l > last) NA_integer_ else l)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
59 }
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
60
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
61 return(NA_integer_)
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
62 }
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
63
3afe41d3e9e7 planemo upload for repository https://github.com/workflow4metabolomics/lcmsmatching.git commit bb4d3e23d99828bfee16d31d794c49a17313ec2f
prog
parents:
diff changeset
64 } # end of load safe guard