`974f2c15c0a2`

3 files changed

modifiedcrates/jrsonnet-stdlib/src/lib.rsdiff before after both

--- a/crates/jrsonnet-stdlib/src/lib.rs
+++ b/crates/jrsonnet-stdlib/src/lib.rs
@@ -40,6 +40,8 @@
 pub use strings::*;
 mod misc;
 pub use misc::*;
+mod sets;
+pub use sets::*;
 
 pub fn stdlib_uncached(settings: Rc<RefCell<Settings>>) -> ObjValue {
 	let mut builder = ObjValueBuilder::new();
@@ -141,6 +143,8 @@
 		("length", builtin_length::INST),
 		("startsWith", builtin_starts_with::INST),
 		("endsWith", builtin_ends_with::INST),
+		// Sets
+		("setMember", builtin_set_member::INST),
 	]
 	.iter()
 	.cloned()

addedcrates/jrsonnet-stdlib/src/sets.rsdiff before after both

--- /dev/null
+++ b/crates/jrsonnet-stdlib/src/sets.rs
@@ -0,0 +1,31 @@
+use std::cmp::Ordering;
+
+use jrsonnet_evaluator::{
+	error::Result,
+	function::{builtin, FuncVal},
+	operator::evaluate_compare_op,
+	val::ArrValue,
+	Val,
+};
+use jrsonnet_parser::BinaryOpType;
+
+#[builtin]
+#[allow(non_snake_case)]
+pub fn builtin_set_member(x: Val, arr: ArrValue, keyF: Option<FuncVal>) -> Result<bool> {
+	let mut low = 0;
+	let mut high = arr.len();
+
+	let keyF = keyF.unwrap_or(FuncVal::Id).into_native::<((Val,), Val)>();
+
+	let x = keyF(x)?;
+
+	while low < high {
+		let middle = (high + low) / 2;
+		match evaluate_compare_op(&arr.get(middle)?.expect("in bounds"), &x, BinaryOpType::Lt)? {
+			Ordering::Less => low = middle + 1,
+			Ordering::Equal => return Ok(true),
+			Ordering::Greater => high = middle,
+		}
+	}
+	Ok(false)
+}

modifiedcrates/jrsonnet-stdlib/src/std.jsonnetdiff before after both

209  set(arr, keyF=id)::209  set(arr, keyF=id)::
210    std.uniq(std.sort(arr, keyF), keyF),210    std.uniq(std.sort(arr, keyF), keyF),
211211
212  setMember(x, arr, keyF=id)::
213    // TODO(dcunnin): Binary chop for O(log n) complexity
214    std.length(std.setInter([x], arr, keyF)) > 0,
215
216  setUnion(a, b, keyF=id)::212  setUnion(a, b, keyF=id)::
217    // NOTE: order matters, values in `a` win213    // NOTE: order matters, values in `a` win
218    local aux(a, b, i, j, acc) =214    local aux(a, b, i, j, acc) =