Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/test/core/vector/table.xml163
-rw-r--r--core/vector/filter.xml144
-rw-r--r--core/vector/table.xml23
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 (&lt;)" />
+ <item name="CMP_OP_LTE" value="3" desc="Less than or equal to (&lt;=)" />
+ <item name="CMP_OP_GT" value="4" desc="Greater than (&gt;)" />
+ <item name="CMP_OP_GTE" value="5" desc="Greater than or equal to (&gt;=)" />
+ </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>