diff options
Diffstat (limited to 'core')
| -rw-r--r-- | core/test/core/vector/table.xml | 163 | ||||
| -rw-r--r-- | core/vector/filter.xml | 144 | ||||
| -rw-r--r-- | core/vector/table.xml | 23 |
3 files changed, 294 insertions, 36 deletions
diff --git a/core/test/core/vector/table.xml b/core/test/core/vector/table.xml index 5e189d6..df2b5e3 100644 --- a/core/test/core/vector/table.xml +++ b/core/test/core/vector/table.xml @@ -61,6 +61,63 @@ </t:create-table> + <t:create-table name="test-table-seq" + desc="Dummy sequential table for query testing"> + <t:table-column name="a" + index="0" + desc="Column A" /> + <t:table-column name="b" + index="1" + desc="Column B" /> + + <t:table-rows> + <t:table-row> + <t:table-value const="1" /> + <t:table-value const="1" /> + </t:table-row> + + <t:table-row> + <t:table-value const="2" /> + <t:table-value const="1" /> + </t:table-row> + <t:table-row> + <t:table-value const="2" /> + <t:table-value const="2" /> + </t:table-row> + + <t:table-row> + <t:table-value const="5" /> + <t:table-value const="1" /> + </t:table-row> + <t:table-row> + <t:table-value const="5" /> + <t:table-value const="2" /> + </t:table-row> + <t:table-row> + <t:table-value const="5" /> + <t:table-value const="3" /> + </t:table-row> + + <t:table-row> + <t:table-value const="7" /> + <t:table-value const="1" /> + </t:table-row> + <t:table-row> + <t:table-value const="7" /> + <t:table-value const="2" /> + </t:table-row> + <t:table-row> + <t:table-value const="7" /> + <t:table-value const="3" /> + </t:table-row> + <t:table-row> + <t:table-value const="7" /> + <t:table-value const="4" /> + </t:table-row> + </t:table-rows> + </t:create-table> + + <t:describe name="_query-first-field_"> <t:it desc="returns first row of multi-row result"> <t:given> @@ -150,6 +207,112 @@ </t:expect> </t:it> </t:describe> + + + <!-- TODO: tried using inline-template here but id generation was not + working as expected --> + <t:describe name="with CMP_OP_LT"> + <t:it desc="matches less than a given value"> + <t:given> + <c:let> + <c:values> + <c:value name="results" type="integer" set="vector"> + <t:query-field table="test-table-seq" field="a"> + <t:when field="a" op="CMP_OP_LT"> + <c:value-of name="#5" /> + </t:when> + </t:query-field> + </c:value> + </c:values> + + <c:sum of="results" /> + </c:let> + </t:given> + + <t:expect> + <!-- 1 + 2 + 2 --> + <t:match-result eq="5" /> + </t:expect> + </t:it> + </t:describe> + + + <t:describe name="with CMP_OP_LTE"> + <t:it desc="matches less than or equal to a given value"> + <t:given> + <c:let> + <c:values> + <c:value name="results" type="integer" set="vector"> + <t:query-field table="test-table-seq" field="a"> + <t:when field="a" op="CMP_OP_LTE"> + <c:value-of name="#5" /> + </t:when> + </t:query-field> + </c:value> + </c:values> + + <c:sum of="results" /> + </c:let> + </t:given> + + <t:expect> + <!-- 1 + 2 + 2 + 5 + 5 + 5 --> + <t:match-result eq="20" /> + </t:expect> + </t:it> + </t:describe> + + + <t:describe name="with CMP_OP_GT"> + <t:it desc="matches greater than a given value"> + <t:given> + <c:let> + <c:values> + <c:value name="results" type="integer" set="vector"> + <t:query-field table="test-table-seq" field="a"> + <t:when field="a" op="CMP_OP_GT"> + <c:value-of name="#5" /> + </t:when> + </t:query-field> + </c:value> + </c:values> + + <c:sum of="results" /> + </c:let> + </t:given> + + <t:expect> + <!-- 7 + 7 + 7 + 7 --> + <t:match-result eq="28" /> + </t:expect> + </t:it> + </t:describe> + + + <t:describe name="with CMP_OP_GTE"> + <t:it desc="matches greater than or equal to a given value"> + <t:given> + <c:let> + <c:values> + <c:value name="results" type="integer" set="vector"> + <t:query-field table="test-table-seq" field="a"> + <t:when field="a" op="CMP_OP_GTE"> + <c:value-of name="#5" /> + </t:when> + </t:query-field> + </c:value> + </c:values> + + <c:sum of="results" /> + </c:let> + </t:given> + + <t:expect> + <!-- 5 + 5 + 5 + 7 + 7 + 7 + 7 --> + <t:match-result eq="43" /> + </t:expect> + </t:it> + </t:describe> </t:describe> diff --git a/core/vector/filter.xml b/core/vector/filter.xml index 30cee02..b7a0754 100644 --- a/core/vector/filter.xml +++ b/core/vector/filter.xml @@ -28,6 +28,19 @@ <import package="list" /> + <typedef name="CmpOp" + desc="Comparison operator"> + <enum type="integer"> + <!-- DO NOT REORDER; see mrange 'over' check --> + <item name="CMP_OP_EQ" value="1" desc="Equal (=)" /> + <item name="CMP_OP_LT" value="2" desc="Less than (<)" /> + <item name="CMP_OP_LTE" value="3" desc="Less than or equal to (<=)" /> + <item name="CMP_OP_GT" value="4" desc="Greater than (>)" /> + <item name="CMP_OP_GTE" value="5" desc="Greater than or equal to (>=)" /> + </enum> + </typedef> + + <section title="Vector Filtering"> <function name="vfilter_lookup" desc="Filter predicate by value and use corresponding index in @@ -46,10 +59,11 @@ <section title="Matrix Filtering"> \ref{mfilter} handles complex filtering of matrices. - If the requested column~\tt{@col@} is marked as sequential with~\tt{@seq@}, - a~$O(lg n)$ bisect algorithm will be used; - otherwise, - it will undergo a~$O(n)$ linear scan. + If the requested column~\tt{@col@} is marked as sequential with~\tt{@seq@} + \emph{and} the comparison operator is~\ref{CMP_OP_EQ}, + then an~$O(lg n)$ bisect algorithm will be used; + otherwise, + it will undergo a~$O(n)$ linear scan. <function name="mfilter" desc="Filter matrix rows by column value"> @@ -57,6 +71,7 @@ <param name="col" type="integer" desc="Column index to filter on" /> <param name="vals" type="float" desc="Column value to filter on" /> <param name="seq" type="boolean" desc="Is data sequential?" /> + <param name="op" type="integer" desc="Comparison operator" /> <!-- merge the result of each condition in vals into a single set, which has the effect of supporting multiple conditions on a single column of @@ -64,13 +79,15 @@ the lookups separately for each, we preserve the bisect-ability of the condition. --> <t:merge-until-empty set="vals" car="val" glance="TABLE_WHEN_MASK_VALUE"> - <c:apply name="mrange" matrix="matrix" col="col" val="val" seq="seq"> + <c:apply name="mrange" matrix="matrix" col="col" val="val" seq="seq" op="op"> <c:arg name="start"> <c:cases> <!-- if we know that the data is sequential, then we may not need to perform a linear search (if the dataset is large enough and the column value is relatively distinct) --> + <!-- TODO: bisect is currently only performed for CMP_OP_EQ --> <c:case> + <t:when-eq name="op" value="CMP_OP_EQ" /> <t:when-eq name="seq" value="TRUE" /> <c:apply name="bisect" matrix="matrix" col="col" val="val"> @@ -117,6 +134,7 @@ <param name="start" type="integer" desc="Starting index (inclusive)" /> <param name="end" type="integer" desc="Ending index (inclusive)" /> <param name="seq" type="boolean" desc="Is data sequential?" /> + <param name="op" type="integer" desc="Comparison operator" /> <c:let> <c:values> @@ -157,8 +175,10 @@ </c:case> <!-- if the data is sequential and the next element is over the - requested value, then we're done --> + requested value, then we're done (can only be used for + equality and LT{,E}; need a GT{,E} version --> <c:case> + <t:when-lte name="op" value="CMP_OP_LTE" /> <t:when-eq name="over" value="TRUE" /> <c:vector /> @@ -166,8 +186,8 @@ <c:otherwise> - <c:apply name="_mfilter" matrix="matrix" col="col" val="val" - start="start" end="end" seq="seq"> + <c:apply name="_mrange_cmp" matrix="matrix" col="col" val="val" + start="start" end="end" seq="seq" op="op"> <c:arg name="cur"> <c:value-of name="matrix"> <!-- current row --> @@ -189,29 +209,95 @@ </function> - <function name="_mfilter" desc="mfilter helper"> + <!-- mutually recursive with _mrange --> + <function name="_mrange_cmp" desc="mrange helper for value comparison"> <param name="matrix" type="float" set="matrix" desc="Matrix to filter" /> <param name="col" type="integer" desc="Column index to filter on" /> <param name="val" type="float" desc="Column value to filter on" /> <param name="start" type="integer" desc="Starting index (aka current index)" /> <param name="end" type="integer" desc="Ending index" /> <param name="seq" type="integer" desc="Is data sequential?" /> - + <param name="op" type="integer" desc="Comparison operator" /> <param name="cur" type="float" desc="Current value" /> - <c:cases> - <c:case> - <t:when-eq name="cur" value="val" /> - <c:cons> - <c:value-of name="matrix"> - <c:index> - <c:value-of name="start" /> - </c:index> - </c:value-of> + <c:let> + <c:values> + <c:value name="found" type="boolean" + desc="Whether comparison matches"> + <c:cases> + <c:case label="Equal"> + <t:when-eq name="op" value="CMP_OP_EQ" /> + + <c:value-of name="TRUE"> + <t:when-eq name="cur" value="val" /> + </c:value-of> + </c:case> + + <c:case label="Less than"> + <t:when-eq name="op" value="CMP_OP_LT" /> + + <c:value-of name="TRUE"> + <t:when-lt name="cur" value="val" /> + </c:value-of> + </c:case> + + <c:case label="Less than or equal to"> + <t:when-eq name="op" value="CMP_OP_LTE" /> + + <c:value-of name="TRUE"> + <t:when-lte name="cur" value="val" /> + </c:value-of> + </c:case> + + <c:case label="Greater than"> + <t:when-eq name="op" value="CMP_OP_GT" /> + + <c:value-of name="TRUE"> + <t:when-gt name="cur" value="val" /> + </c:value-of> + </c:case> + + <c:case label="Greater than or equal to"> + <t:when-eq name="op" value="CMP_OP_GTE" /> + + <c:value-of name="TRUE"> + <t:when-gte name="cur" value="val" /> + </c:value-of> + </c:case> + </c:cases> + </c:value> + </c:values> + <c:cases> + <!-- if values matches, cons it --> + <c:case> + <t:when-eq name="found" value="TRUE" /> + + <c:cons> + <c:value-of name="matrix"> + <c:index> + <c:value-of name="start" /> + </c:index> + </c:value-of> + + <c:apply name="mrange" matrix="matrix" col="col" val="val" + end="end" seq="seq" op="op"> + <c:arg name="start"> + <c:sum> + <c:value-of name="start" /> + <c:const value="1" desc="Check next element" /> + </c:sum> + </c:arg> + </c:apply> + </c:cons> + </c:case> + + + <!-- no match, continue (mutual) recursion --> + <c:otherwise> <c:apply name="mrange" matrix="matrix" col="col" val="val" - end="end" seq="seq"> + end="end" seq="seq" op="op"> <c:arg name="start"> <c:sum> <c:value-of name="start" /> @@ -219,21 +305,9 @@ </c:sum> </c:arg> </c:apply> - </c:cons> - </c:case> - - <c:otherwise> - <c:apply name="mrange" matrix="matrix" col="col" val="val" - end="end" seq="seq"> - <c:arg name="start"> - <c:sum> - <c:value-of name="start" /> - <c:const value="1" desc="Check next element" /> - </c:sum> - </c:arg> - </c:apply> - </c:otherwise> - </c:cases> + </c:otherwise> + </c:cases> + </c:let> </function> diff --git a/core/vector/table.xml b/core/vector/table.xml index 268dce6..53c13a7 100644 --- a/core/vector/table.xml +++ b/core/vector/table.xml @@ -371,6 +371,12 @@ <text>_IS_SEQ</text> </param> + <param name="@op@" + desc="Comparison operator (default CMP_OP_EQ; see CmpOp typedef)"> + <text>CMP_OP_EQ</text> + </param> + + <c:vector label="Conditional for {@field@}"> <!-- the first element will represent the column (field) index --> <unless name="@name@"> @@ -385,7 +391,7 @@ <param-copy name="@values@" /> </c:vector> - <!-- the final element will represent whether or not this field is sequential --> + <!-- the third element will represent whether or not this field is sequential --> <if name="@sequential@"> <c:const value="@sequential@" type="boolean" desc="Whether data is sequential" /> </if> @@ -400,6 +406,9 @@ <c:value-of name="FALSE" /> </unless> </unless> + + <!-- the fourth and final element is the comparison operator --> + <c:value-of name="@op@" /> </c:vector> </template> @@ -479,6 +488,18 @@ </c:index> </c:value-of> </c:arg> + + <!-- comparison operator --> + <c:arg name="op"> + <c:value-of name="criteria"> + <c:index> + <c:value-of name="i" /> + </c:index> + <c:index> + <c:const value="3" type="integer" desc="Comparison operator" /> + </c:index> + </c:value-of> + </c:arg> </c:apply> </c:otherwise> </c:cases> |