Mercurial > octave

annotate src/DLD-FUNCTIONS/lookup.cc @ 8814:de16ebeef93d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
improve lookup, provide Array<T>::lookup
author Jaroslav Hajek <highegg@gmail.com>
date Thu, 19 Feb 2009 15:19:59 +0100
parents e01c6355304f
children eb63fbe60fab
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
1 /*
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
2
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
3 Copyright (C) 2008 VZLU Prague a.s., Czech Republic
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
4
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
5 This file is part of Octave.
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
6
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
7 Octave is free software; you can redistribute it and/or modify it
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
8 under the terms of the GNU General Public License as published by
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
9 the Free Software Foundation; either version 3 of the License, or (at
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
10 your option) any later version.
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
11
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
12 Octave is distributed in the hope that it will be useful, but
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
13 WITHOUT ANY WARRANTY; without even the implied warranty of
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
15 General Public License for more details.
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
16
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
17 You should have received a copy of the GNU General Public License
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
18 along with Octave; see the file COPYING. If not, see
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
19 <http://www.gnu.org/licenses/>.
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
20
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
21 */
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
22
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
23 // Author: Jaroslav Hajek <highegg@gmail.com>
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
24
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
25 #include <cctype>
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
26 #include <functional>
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
27 #include <algorithm>
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
28
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
29 #ifdef HAVE_CONFIG_H
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
30 #include <config.h>
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
31 #endif
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
32
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
33 #include "dNDArray.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
34 #include "CNDArray.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
35
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
36 #include "Cell.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
37 #include "defun-dld.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
38 #include "error.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
39 #include "gripes.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
40 #include "oct-obj.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
41 #include "ov.h"
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
42
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
43 static
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
44 bool
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
45 contains_char (const std::string& str, char c)
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
46 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
47 return (str.find (c) != std::string::npos
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
48 || str.find (std::toupper (c)) != std::string::npos);
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
49 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
50
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
51 // case-insensitive character comparison functors
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
52 struct icmp_char_lt : public std::binary_function<char, char, bool>
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
53 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
54 bool operator () (char x, char y) const
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
55 { return std::toupper (x) < std::toupper (y); }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
56 };
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
57
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
58 struct icmp_char_gt : public std::binary_function<char, char, bool>
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
59 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
60 bool operator () (char x, char y) const
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
61 { return std::toupper (x) > std::toupper (y); }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
62 };
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
63
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
64 // FIXME: maybe these should go elsewhere?
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
65 // case-insensitive ascending comparator
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
66 static bool
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
67 stri_comp_lt (const std::string& a, const std::string& b)
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
68 {
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
69 return std::lexicographical_compare (a.begin (), a.end (),
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
70 b.begin (), b.end (),
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
71 icmp_char_lt());
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
72 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
73
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
74 // case-insensitive descending comparator
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
75 static bool
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
76 stri_comp_gt (const std::string& a, const std::string& b)
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
77 {
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
78 return std::lexicographical_compare (a.begin (), a.end (),
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
79 b.begin (), b.end (),
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
80 icmp_char_gt());
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
81 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
82
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
83 template <class T>
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
84 inline sortmode
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
85 get_sort_mode (const Array<T>& array,
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
86 typename octave_sort<T>::compare_fcn_type desc_comp
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
87 = octave_sort<T>::descending_compare)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
88 {
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
89 octave_idx_type n = array.numel ();
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
90 if (n > 1 && desc_comp (array (0), array (n-1)))
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
91 return DESCENDING;
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
92 else
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
93 return ASCENDING;
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
94 }
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
95
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
96 // FIXME: perhaps there should be octave_value::lookup?
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
97 // The question is, how should it behave w.r.t. the second argument's type.
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
98 // We'd need a dispatch on two arguments. Hmmm...
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
99
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
100 #define INT_ARRAY_LOOKUP(TYPE) \
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
101 (table.is_ ## TYPE ## _type () && y.is_ ## TYPE ## _type ()) \
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
102 idx = table.TYPE ## _array_value ().lookup (y.TYPE ## _array_value (), \
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
103 UNSORTED, left_inf, right_inf);
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
104
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
105 DEFUN_DLD (lookup, args, ,
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
106 "-*- texinfo -*-\n\
8617
4b26e9fbbb37 fix lookup's docstring
Jaroslav Hajek <highegg@gmail.com>
parents: 7924
diff changeset
107 @deftypefn {Loadable Function} {@var{idx} =} lookup (@var{table}, @var{y}, @var{opt})\n\
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
108 Lookup values in a sorted table. Usually used as a prelude to\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
109 interpolation.\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
110 \n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
111 If table is strictly increasing and @code{idx = lookup (table, y)}, then\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
112 @code{table(idx(i)) <= y(i) < table(idx(i+1))} for all @code{y(i)}\n\
8617
4b26e9fbbb37 fix lookup's docstring
Jaroslav Hajek <highegg@gmail.com>
parents: 7924
diff changeset
113 within the table. If @code{y(i) < table (1)} then\n\
4b26e9fbbb37 fix lookup's docstring
Jaroslav Hajek <highegg@gmail.com>
parents: 7924
diff changeset
114 @code{idx(i)} is 0. If @code{y(i) >= table(end)} then\n\
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
115 @code{idx(i)} is @code{table(n)}.\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
116 \n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
117 If the table is strictly decreasing, then the tests are reversed.\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
118 There are no guarantees for tables which are non-monotonic or are not\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
119 strictly monotonic.\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
120 \n\
8617
4b26e9fbbb37 fix lookup's docstring
Jaroslav Hajek <highegg@gmail.com>
parents: 7924
diff changeset
121 The algorithm used by lookup is standard binary search, with optimizations\n\
4b26e9fbbb37 fix lookup's docstring
Jaroslav Hajek <highegg@gmail.com>
parents: 7924
diff changeset
122 to speed up the case of partially ordered arrays (dense downsampling).\n\
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
123 In particular, looking up a single entry is of logarithmic complexity\n\
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
124 (unless a conversion occurs due to non-numeric or unequal types).\n\
8617
4b26e9fbbb37 fix lookup's docstring
Jaroslav Hajek <highegg@gmail.com>
parents: 7924
diff changeset
125 \n\
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
126 @var{table} and @var{y} can also be cell arrays of strings\n\
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
127 (or @var{y} can be a single string). In this case, string lookup\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
128 is performed using lexicographical comparison.\n\
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
129 \n\
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
130 If @var{opts} is specified, it shall be a string with letters indicating\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
131 additional options.\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
132 For numeric lookup, 'l' in @var{opts} indicates that\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
133 the leftmost subinterval shall be extended to infinity (i.e. all indices\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
134 at least 1), and 'r' indicates that the rightmost subinterval shall be\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
135 extended to infinity (i.e. all indices at most n-1).\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
136 \n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
137 For string lookup, 'i' indicates case-insensitive comparison.\n\
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
138 @end deftypefn")
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
139 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
140 octave_value_list retval;
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
141
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
142 int nargin = args.length ();
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
143
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
144 if (nargin < 2 || nargin > 3 || (nargin == 3 && ! args(2).is_string ()))
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
145 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
146 print_usage ();
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
147 return retval;
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
148 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
149
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
150 octave_value table = args(0), y = args(1);
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
151 if (table.ndims () > 2 || (table.columns () > 1 && table.rows () > 1))
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
152 warning ("lookup: table is not a vector");
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
153
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
154 bool num_case = table.is_numeric_type () && y.is_numeric_type ();
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
155 bool str_case = table.is_cellstr () && (y.is_string () || y.is_cellstr ());
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
156
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
157 if (num_case)
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
158 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
159 bool left_inf = false;
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
160 bool right_inf = false;
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
161
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
162 if (nargin == 3)
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
163 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
164 std::string opt = args(2).string_value ();
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
165 left_inf = contains_char (opt, 'l');
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
166 right_inf = contains_char (opt, 'r');
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
167 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
168
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
169 // In the case of a complex array, absolute values will be used for compatibility
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
170 // (though it's not too meaningful).
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
171
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
172 if (table.is_complex_type ())
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
173 table = table.abs ();
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
174
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
175 if (y.is_complex_type ())
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
176 y = y.abs ();
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
177
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
178 Array<octave_idx_type> idx;
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
179
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
180 // PS: I learned this from data.cc
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
181 if INT_ARRAY_LOOKUP (int8)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
182 else if INT_ARRAY_LOOKUP (int16)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
183 else if INT_ARRAY_LOOKUP (int32)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
184 else if INT_ARRAY_LOOKUP (int64)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
185 else if INT_ARRAY_LOOKUP (uint8)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
186 else if INT_ARRAY_LOOKUP (uint16)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
187 else if INT_ARRAY_LOOKUP (uint32)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
188 else if INT_ARRAY_LOOKUP (uint64)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
189 else if (table.is_single_type () || y.is_single_type ())
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
190 idx = table.float_array_value ().lookup (y.float_array_value (),
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
191 UNSORTED, left_inf, right_inf);
7789
82be108cc558 First attempt at single precision tyeps
David Bateman <dbateman@free.fr>
parents: 7671
diff changeset
192 else
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
193 idx = table.array_value ().lookup (y.array_value (),
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
194 UNSORTED, left_inf, right_inf);
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
195
7919
9d080df0c843 new NDArray constructor for ArrayN<octave_idx_type>
David Bateman <dbateman@free.fr>
parents: 7789
diff changeset
196 retval(0) = NDArray (idx);
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
197
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
198 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
199 else if (str_case)
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
200 {
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
201 Array<std::string> str_table = table.cellstr_value ();
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
202
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
203 // Here we'll use octave_sort directly to avoid converting the array
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
204 // for case-insensitive comparison.
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
205
7924
4976f66d469b miscellaneous cleanup
John W. Eaton <jwe@octave.org>
parents: 7919
diff changeset
206 bool icase = false;
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
207
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
208 // check for case-insensitive option
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
209 if (nargin == 3)
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
210 {
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
211 std::string opt = args(2).string_value ();
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
212 icase = contains_char (opt, 'i');
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
213 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
214
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
215 sortmode mode = (icase ? get_sort_mode (str_table, stri_comp_gt)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
216 : get_sort_mode (str_table));
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
217
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
218 bool (*str_comp) (const std::string&, const std::string&);
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
219
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
220 // pick the correct comparator
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
221 if (mode == DESCENDING)
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
222 str_comp = icase ? stri_comp_gt : octave_sort<std::string>::descending_compare;
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
223 else
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
224 str_comp = icase ? stri_comp_lt : octave_sort<std::string>::ascending_compare;
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
225
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
226 octave_sort<std::string> lsort (str_comp);
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
227 if (y.is_cellstr ())
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
228 {
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
229 Array<std::string> str_y = y.cellstr_value ();
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
230
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
231 Array<octave_idx_type> idx (str_y.dims ());
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
232
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
233 lsort.lookup (str_table.data (), str_table.nelem (), str_y.data (),
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
234 str_y.nelem (), idx.fortran_vec ());
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
235
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
236 retval(0) = NDArray (idx);
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
237 }
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
238 else if (y.is_string ())
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
239 {
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
240 std::string str_y = y.string_value ();
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
241
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
242 octave_idx_type idx;
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
243
8814
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
244 lsort.lookup (str_table.data (), str_table.nelem (), &str_y,
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
245 1, &idx);
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
246
de16ebeef93d improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents: 8646
diff changeset
247 retval(0) = idx;
7671
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
248 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
249 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
250 else
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
251 print_usage ();
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
252
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
253 return retval;
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
254
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
255 }
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
256
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
257 /*
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
258 %!assert (real(lookup(1:3, 0.5)), 0) # value before table
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
259 %!assert (real(lookup(1:3, 3.5)), 3) # value after table error
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
260 %!assert (real(lookup(1:3, 1.5)), 1) # value within table error
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
261 %!assert (real(lookup(1:3, [3,2,1])), [3,2,1])
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
262 %!assert (real(lookup([1:4]', [1.2, 3.5]')), [1, 3]');
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
263 %!assert (real(lookup([1:4], [1.2, 3.5]')), [1, 3]');
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
264 %!assert (real(lookup([1:4]', [1.2, 3.5])), [1, 3]);
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
265 %!assert (real(lookup([1:4], [1.2, 3.5])), [1, 3]);
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
266 %!assert (real(lookup(1:3, [3, 2, 1])), [3, 2, 1]);
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
267 %!assert (real(lookup([3:-1:1], [3.5, 3, 1.2, 2.5, 2.5])), [0, 1, 2, 1, 1])
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
268 %!assert (isempty(lookup([1:3], [])))
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
269 %!assert (isempty(lookup([1:3]', [])))
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
270 %!assert (real(lookup(1:3, [1, 2; 3, 0.5])), [1, 2; 3, 0]);
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
271 %!
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
272 %!assert (real(lookup({"apple","lemon","orange"}, {"banana","kiwi"; "ananas","mango"})), [1,1;0,2])
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
273 %!assert (real(lookup({"apple","lemon","orange"}, "potato")), 3)
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
274 %!assert (real(lookup({"orange","lemon","apple"}, "potato")), 0)
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
275 */
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
276
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
277 /*
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
278 ;;; Local Variables: ***
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
279 ;;; mode: C++ ***
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
280 ;;; End: ***
4fbaba9abec1 implement compiled binary lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
diff changeset
281 */