Add `bit_array.compare`

3 files changed, 137 insertions, 0 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 55def03..159ac5c 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -11,6 +11,7 @@
 - The `dynamic.optional_field` decoder no longer treats the value as implicitly
   optional. It only deals with the presence or absence of the key itself which
   brings it inline with its documentation.
+- The `bit_array` module gains the `compare` function.
 - Fixed a bug where `string.trim` could remove commas on JavaScript.
 - The `string.pop_grapheme` function has been optimised on Erlang, greatly
   improving its performance.
diff --git a/src/gleam/bit_array.gleam b/src/gleam/bit_array.gleam
index 23b243a..e0cf4f2 100644
--- a/src/gleam/bit_array.gleam
+++ b/src/gleam/bit_array.gleam
@@ -1,6 +1,7 @@
 //// BitArrays are a sequence of binary data of any length.
 
 import gleam/int
+import gleam/order
 import gleam/string
 
 /// Converts a UTF-8 `String` type into a `BitArray`.
@@ -187,3 +188,39 @@ fn do_inspect(input: BitArray, accumulator: String) -> String {
     _ -> accumulator
   }
 }
+
+/// Compare two bit arrays as sequences of bytes.
+///
+/// ## Examples
+///
+/// ```gleam
+/// compare(<<1>>, <<2>>)
+/// // -> Lt
+///
+/// compare(<<"AB":utf8>>, <<"AA":utf8>>)
+/// // -> Gt
+///
+/// compare(<<1, 2:size(2)>>, <<1, 2:size(2)>>)
+/// // -> Eq
+/// ```
+///
+pub fn compare(first: BitArray, second: BitArray) -> order.Order {
+  do_compare(first, second, 0)
+}
+
+fn do_compare(first: BitArray, second: BitArray, index: Int) -> order.Order {
+  case slice(first, index, 1), slice(second, index, 1) {
+    Ok(<<first_byte>>), Ok(<<second_byte>>) ->
+      int.compare(first_byte, second_byte)
+      |> order.lazy_break_tie(fn() {
+        do_compare(first, second, index + 1)
+      })
+
+    // First has more items, example: "AB" > "A":
+    Ok(_), Error(_) -> order.Gt
+    // Second has more items, example: "A" < "AB":
+    Error(_), Ok(_) -> order.Lt
+    // Both have the same length, fallback:
+    _, _ -> order.Eq
+  }
+}
diff --git a/test/gleam/bit_array_test.gleam b/test/gleam/bit_array_test.gleam
index 246fbaa..6cf8464 100644
--- a/test/gleam/bit_array_test.gleam
+++ b/test/gleam/bit_array_test.gleam
@@ -1,4 +1,5 @@
 import gleam/bit_array
+import gleam/order
 import gleam/result
 import gleam/should
 import gleam/string
@@ -331,3 +332,101 @@ pub fn inspect_partial_bytes_test() {
   bit_array.inspect(<<5:3, 11:4, 1:2>>)
   |> should.equal("<<182, 1:size(1)>>")
 }
+
+pub fn bit_array_compare_test() {
+  bit_array.compare(<<1, 2, 3>>, <<1, 2, 3>>)
+  |> should.equal(order.Eq)
+
+  bit_array.compare(<<1, 2>>, <<1, 3>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<1, 3>>, <<1, 2>>)
+  |> should.equal(order.Gt)
+
+  bit_array.compare(<<1, 2>>, <<1, 2, 3>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<1, 2, 3>>, <<1, 2>>)
+  |> should.equal(order.Gt)
+}
+
+pub fn bit_array_compare_utf8_test() {
+  // utf8
+  bit_array.compare(<<"ABC":utf8>>, <<"ABC":utf8>>)
+  |> should.equal(order.Eq)
+
+  bit_array.compare(<<"AB":utf8>>, <<"ABC":utf8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<"ABC":utf8>>, <<"AB":utf8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<"AB":utf8>>, <<"AC":utf8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<"AC":utf8>>, <<"AB":utf8>>)
+  |> should.equal(order.Gt)
+
+  bit_array.compare(<<"":utf8>>, <<"ABC":utf8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<"A":utf8>>, <<"":utf8>>)
+  |> should.equal(order.Gt)
+
+  bit_array.compare(<<"":utf8>>, <<"":utf8>>)
+  |> should.equal(order.Eq)
+}
+
+pub fn bit_array_compare_utf16_test() {
+  bit_array.compare(<<"ABC":utf16>>, <<"ABC":utf16>>)
+  |> should.equal(order.Eq)
+
+  bit_array.compare(<<"ABC":utf16>>, <<"AB":utf16>>)
+  |> should.equal(order.Gt)
+
+  bit_array.compare(<<"A":utf16>>, <<"Z":utf16>>)
+  |> should.equal(order.Lt)
+}
+
+pub fn bit_array_compare_mixed_utfs_test() {
+  bit_array.compare(<<"A":utf16>>, <<"A":utf8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<"A":utf8>>, <<"A":utf16>>)
+  |> should.equal(order.Gt)
+
+  bit_array.compare(<<"":utf8>>, <<"A":utf16>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<"":utf16>>, <<"A":utf8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<"":utf16>>, <<"":utf8>>)
+  |> should.equal(order.Eq)
+
+  bit_array.compare(<<"":utf8>>, <<"":utf16>>)
+  |> should.equal(order.Eq)
+}
+
+pub fn bit_array_compare_different_sizes_test() {
+  bit_array.compare(<<4:5>>, <<4:5>>)
+  |> should.equal(order.Eq)
+
+  bit_array.compare(<<3:5>>, <<4:5>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<5:5>>, <<4:5>>)
+  |> should.equal(order.Gt)
+
+  bit_array.compare(<<4:8>>, <<4:5>>)
+  |> should.equal(order.Gt)
+
+  bit_array.compare(<<4:5>>, <<4:8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<0:5>>, <<0:8>>)
+  |> should.equal(order.Lt)
+
+  bit_array.compare(<<0:2>>, <<0:1>>)
+  |> should.equal(order.Gt)
+}