diff options
Diffstat (limited to 'aoc2023/build/packages/gap')
24 files changed, 2630 insertions, 0 deletions
diff --git a/aoc2023/build/packages/gap/LICENSE b/aoc2023/build/packages/gap/LICENSE new file mode 100644 index 0000000..d1cec9b --- /dev/null +++ b/aoc2023/build/packages/gap/LICENSE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright 2023 John Björk + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License.
\ No newline at end of file diff --git a/aoc2023/build/packages/gap/README.md b/aoc2023/build/packages/gap/README.md new file mode 100644 index 0000000..3e02686 --- /dev/null +++ b/aoc2023/build/packages/gap/README.md @@ -0,0 +1,202 @@ +# gap + +[](https://hex.pm/packages/gap) +[](https://hexdocs.pm/gap/) + +A Gleam library for comparing strings/lists and producing a textual (styled) representation of the differences. + +A typical styled output from the comparison can look like this: + +<img src="https://github.com/JohnBjrk/gap/blob/main/static/example_diff_lucy.png?raw=true" alt="Image of two strings with highlighted differences" width="400vw"> + +## Installation + +If available on Hex this package can be added to your Gleam project: + +```sh +gleam add gap +``` + +Documentation can be found at <https://hexdocs.pm/gap>. + +## Usage + +# Introduction + +Gap implements string/list comparison by finding the longest common subsequence. The result of the comparison are two sequences +(one for each of the compared strings/lists) consisting of subsequences that are annotated as matching or non-matching. + +For example comparing the strings in the example above will look as follows: + +```gleam +let comparison = +compare_strings( + "lucy in the sky with diamonds", + "lucy is the shy with diagrams", +) +|> io.debug() +// StringComparison( +// [ +// Match(["l", "u", "c", "y", " ", "i"]), +// NoMatch(["n"]), +// Match([" ", "t", "h", "e", " ", "s"]), +// NoMatch(["k"]), +// Match(["y", " ", "w", "i", "t", "h", " ", "d", "i", "a", "m"]), +// NoMatch(["o", "n", "d"]), +// Match(["s"]), +// ], +// [ +// Match(["l", "u", "c", "y", " ", "i"]), +// NoMatch(["s", " "]), +// Match([" ", "t", "h", "e", " ", "s"]), +// NoMatch(["h"]), +// Match(["y", " ", "w", "i", "t", "h", " ", "d", "i"]), +// NoMatch(["a", "g", "r"]), +// Match(["a", "m", "s"]), +// ], +// ) +``` + +## Styling + +This is useful information but a bit overwhelming to look at (specially for longer string) so the library +has some built in functions to display the differences using colors instead. + +Using the same example again we can style the result and print it to the console + +```gleam +let comparison = +compare_strings( + "lucy in the sky with diamonds", + "lucy is the shy with diagrams", +) +|> to_styled() +io.println(comparison.first) +io.println(comparison.second) +``` + +This will give us something similar to the output above. + +## Comparing list + +It is also possible to compare lists with elements of arbitrary types. + +```gleam +pub type Warning { + Please + Mind + The(what: String) +} + +compare_lists([Mind, The("Gap")], [Please, Mind, The("What")]) +|> io.debug() +// ListComparison( +// [Match([Mind]), NoMatch([The("Gap")])], +// [NoMatch([Please]), Match([Mind]), NoMatch([The("What")])], +// ) +``` + +## Customize styling + +The visual representation of the comparison can be customized. To do this use a `Styling` created from +the comparison that should be styled. This example uses [gleam_community/ansi](https://hexdocs.pm/gleam_community_ansi/index.html) +to highlight the non-matches in different colors. + +```gleam +let comparison = +compare_strings( + "Strings are made of smaller things", + "Things are maybe smaller string", +) +|> from_comparison() +|> highlight( + fn(first) { ansi.cyan(first) }, + fn(second) { ansi.magenta(second) }, + fn(matching) { matching }, +) +|> to_styled_comparison() +io.println(comparison.first) +io.println(comparison.second) +``` + +This will output something similar to this + +<img src="https://github.com/JohnBjrk/gap/blob/main/static/example_diff_things.png?raw=true" alt="Image of two strings with highlighted differences" width="400vw"> + +### Serialization + +Furthermore it is also possible to customize the styling by changing the way that the comparison is serialized. An easy way to do +this is to use the utility function `mk_generic_serializer` which creates a serializer which some specific separator and a hook +for surrounding the result with some content. Here is a somewhat contrived example + +```gleam +let comparison = +compare_lists(["one", "two", "three"], ["two", "two", "tree"]) +|> from_comparison() +|> highlight( + fn(first) { first <> " was not found in other" }, + fn(second) { second <> " was not found in other" }, +) +|> serialize(mk_generic_serializer( + ", and ", + fn(result) { "Comparing the lists gave the following result: " <> result }, +)) +|> to_styled_comparison() +io.println(comparison.first) +io.println(comparison.second) +// Comparing the lists gave the following result: "one" was not found in other, and "two" was found in other, and "three" was not found in other +// Comparing the lists gave the following result: "two" was not found in other, and "two" was found in other, and "tree" was not found in other +``` + +### Custom serialization + +Serializers can of course have a custom implementation. The following example utilizes this together with custom highlighters, +creating a patch-like output (this is not exactly the same as patch-format since that shows the changes in relation to the original - to do +that both lists of matching/non-matching lines would need to be processed together) + +```gleam +let comparison = +compare_lists( + [ + "pub type Gap = List(EmptyString)", "", "pub type Traveler {", + " OnTrain", " OverGap(gap: Gap)", " OnPlatform", "}", + ], + [ + "pub type Traveler {", " OnTrain", " OverGap(gap: String)", + " OnPlatform", "}", + ], +) +|> from_comparison() +|> highlight( + fn(first) { "+" <> first }, + fn(second) { "-" <> second }, + fn(matching) { " " <> matching }, +) +|> serialize(fn(part) { + case part { + Part(acc, lines, highlight) -> + acc <> { + lines + |> list.map(fn(line) { highlight(line) }) + |> string.join("\n") + } <> "\n" + All(result) -> result + } +}) +|> to_styled_comparison() +io.println(comparison.first) +io.println(comparison.second) +// +pub type Gap = List(EmptyString) +// + +// pub type Traveler { +// OnTrain +// + OverGap(gap: Gap) +// OnPlatform +// } +// +// pub type Traveler { +// OnTrain +// - OverGap(gap: String) +// OnPlatform +// } +``` diff --git a/aoc2023/build/packages/gap/gleam.toml b/aoc2023/build/packages/gap/gleam.toml new file mode 100644 index 0000000..ec35329 --- /dev/null +++ b/aoc2023/build/packages/gap/gleam.toml @@ -0,0 +1,18 @@ +name = "gap" +gleam = ">= 0.32.2" +version = "1.0.1" +description = "A Gleam library for comparing strings/lists and producing a textual (styled) representation of the differences." + +# Fill out these fields if you intend to generate HTML documentation or publish +# your project to the Hex package manager. +# +licences = ["Apache-2.0"] +repository = { type = "github", user = "JohnBjrk", repo = "gap" } +# links = [{ title = "Website", href = "https://gleam.run" }] + +[dependencies] +gleam_stdlib = "~> 0.32" +gleam_community_ansi = "~> 1.2" + +[dev-dependencies] +gleeunit = "~> 1.0" diff --git a/aoc2023/build/packages/gap/include/gap@comparison_ListComparison.hrl b/aoc2023/build/packages/gap/include/gap@comparison_ListComparison.hrl new file mode 100644 index 0000000..5e4b20d --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@comparison_ListComparison.hrl @@ -0,0 +1,4 @@ +-record(list_comparison, { + first :: list(gap@comparison:match(list(any()))), + second :: list(gap@comparison:match(list(any()))) +}). diff --git a/aoc2023/build/packages/gap/include/gap@comparison_Match.hrl b/aoc2023/build/packages/gap/include/gap@comparison_Match.hrl new file mode 100644 index 0000000..f1225dd --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@comparison_Match.hrl @@ -0,0 +1 @@ +-record(match, {item :: any()}). diff --git a/aoc2023/build/packages/gap/include/gap@comparison_NoMatch.hrl b/aoc2023/build/packages/gap/include/gap@comparison_NoMatch.hrl new file mode 100644 index 0000000..742783b --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@comparison_NoMatch.hrl @@ -0,0 +1 @@ +-record(no_match, {item :: any()}). diff --git a/aoc2023/build/packages/gap/include/gap@comparison_StringComparison.hrl b/aoc2023/build/packages/gap/include/gap@comparison_StringComparison.hrl new file mode 100644 index 0000000..c0b1a75 --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@comparison_StringComparison.hrl @@ -0,0 +1,4 @@ +-record(string_comparison, { + first :: list(gap@comparison:match(list(binary()))), + second :: list(gap@comparison:match(list(binary()))) +}). diff --git a/aoc2023/build/packages/gap/include/gap@styled_comparison_StyledComparison.hrl b/aoc2023/build/packages/gap/include/gap@styled_comparison_StyledComparison.hrl new file mode 100644 index 0000000..0e7c64a --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@styled_comparison_StyledComparison.hrl @@ -0,0 +1 @@ +-record(styled_comparison, {first :: binary(), second :: binary()}). diff --git a/aoc2023/build/packages/gap/include/gap@styling_All.hrl b/aoc2023/build/packages/gap/include/gap@styling_All.hrl new file mode 100644 index 0000000..c11a9a6 --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@styling_All.hrl @@ -0,0 +1 @@ +-record(all, {all :: binary()}). diff --git a/aoc2023/build/packages/gap/include/gap@styling_Highlighters.hrl b/aoc2023/build/packages/gap/include/gap@styling_Highlighters.hrl new file mode 100644 index 0000000..6e073b3 --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@styling_Highlighters.hrl @@ -0,0 +1,5 @@ +-record(highlighters, { + first :: fun((binary()) -> binary()), + second :: fun((binary()) -> binary()), + matching :: fun((binary()) -> binary()) +}). diff --git a/aoc2023/build/packages/gap/include/gap@styling_Part.hrl b/aoc2023/build/packages/gap/include/gap@styling_Part.hrl new file mode 100644 index 0000000..db45796 --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@styling_Part.hrl @@ -0,0 +1,5 @@ +-record(part, { + acc :: binary(), + part :: list(any()), + highlight :: fun((binary()) -> binary()) +}). diff --git a/aoc2023/build/packages/gap/include/gap@styling_Styling.hrl b/aoc2023/build/packages/gap/include/gap@styling_Styling.hrl new file mode 100644 index 0000000..a7341c6 --- /dev/null +++ b/aoc2023/build/packages/gap/include/gap@styling_Styling.hrl @@ -0,0 +1,5 @@ +-record(styling, { + comparison :: gap@comparison:comparison(any()), + serializer :: gleam@option:option(fun((gap@styling:part(any())) -> binary())), + highlight :: gleam@option:option(gap@styling:highlighters()) +}). diff --git a/aoc2023/build/packages/gap/src/gap.app.src b/aoc2023/build/packages/gap/src/gap.app.src new file mode 100644 index 0000000..1abc7df --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap.app.src @@ -0,0 +1,13 @@ +{application, gap, [ + {vsn, "1.0.1"}, + {applications, [gleam_community_ansi, + gleam_stdlib, + gleeunit]}, + {description, "A Gleam library for comparing strings/lists and producing a textual (styled) representation of the differences."}, + {modules, [gap, + gap@comparison, + gap@myers, + gap@styled_comparison, + gap@styling]}, + {registered, []} +]}. diff --git a/aoc2023/build/packages/gap/src/gap.erl b/aoc2023/build/packages/gap/src/gap.erl new file mode 100644 index 0000000..827e5ce --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap.erl @@ -0,0 +1,538 @@ +-module(gap). +-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]). + +-export([to_styled/1, compare_strings_with_algorithm/3, compare_lists_with_algorithm/3, myers/2, compare_lists/2, compare_strings/2, lcs/2]). +-export_type([score/1]). + +-type score(GAM) :: {score, integer(), gleam@option:option(GAM)}. + +-spec to_styled(gap@comparison:comparison(any())) -> gap@styled_comparison:styled_comparison(). +to_styled(Comparison) -> + _pipe = Comparison, + _pipe@1 = gap@styling:from_comparison(_pipe), + _pipe@2 = gap@styling:highlight( + _pipe@1, + fun gap@styling:first_highlight_default/1, + fun gap@styling:second_highlight_default/1, + fun gap@styling:no_highlight/1 + ), + gap@styling:to_styled_comparison(_pipe@2). + +-spec compare_strings_with_algorithm( + binary(), + binary(), + fun((list(binary()), list(binary())) -> gap@comparison:comparison(binary())) +) -> gap@comparison:comparison(binary()). +compare_strings_with_algorithm(First, Second, Algorithm) -> + Comparison = Algorithm( + gleam@string:to_graphemes(First), + gleam@string:to_graphemes(Second) + ), + case Comparison of + {list_comparison, First@1, Second@1} -> + {string_comparison, First@1, Second@1}; + + {string_comparison, First@2, Second@2} -> + {string_comparison, First@2, Second@2} + end. + +-spec compare_lists_with_algorithm( + list(GBB), + list(GBB), + fun((list(GBB), list(GBB)) -> gap@comparison:comparison(GBB)) +) -> gap@comparison:comparison(GBB). +compare_lists_with_algorithm(First_sequence, Second_sequence, Algorithm) -> + Algorithm(First_sequence, Second_sequence). + +-spec myers(list(GBG), list(GBG)) -> gap@comparison:comparison(GBG). +myers(First_sequence, Second_sequence) -> + Edits = gap@myers:difference(First_sequence, Second_sequence), + _pipe = Edits, + _pipe@1 = gleam@list:reverse(_pipe), + gleam@list:fold( + _pipe@1, + {list_comparison, [], []}, + fun(Comparison, Edit) -> case Comparison of + {list_comparison, First, Second} -> + case Edit of + {eq, Segment} -> + {list_comparison, + [{match, Segment} | First], + [{match, Segment} | Second]}; + + {ins, Segment@1} -> + {list_comparison, + First, + [{no_match, Segment@1} | Second]}; + + {del, Segment@2} -> + {list_comparison, + [{no_match, Segment@2} | First], + Second} + end; + + {string_comparison, _, _} -> + Comparison + end end + ). + +-spec compare_lists(list(GAX), list(GAX)) -> gap@comparison:comparison(GAX). +compare_lists(First_sequence, Second_sequence) -> + myers(First_sequence, Second_sequence). + +-spec compare_strings(binary(), binary()) -> gap@comparison:comparison(binary()). +compare_strings(First, Second) -> + Comparison = compare_lists( + gleam@string:to_graphemes(First), + gleam@string:to_graphemes(Second) + ), + case Comparison of + {list_comparison, First@1, Second@1} -> + {string_comparison, First@1, Second@1}; + + {string_comparison, First@2, Second@2} -> + {string_comparison, First@2, Second@2} + end. + +-spec prepend_and_merge( + list(gap@comparison:match(list(GBO))), + gap@comparison:match(list(GBO)) +) -> list(gap@comparison:match(list(GBO))). +prepend_and_merge(Matches, Match) -> + case {Matches, Match} of + {[], _} -> + [Match]; + + {[{match, First_match} | Rest], {match, _}} -> + [{match, + begin + _pipe = erlang:element(2, Match), + gleam@list:append(_pipe, First_match) + end} | + Rest]; + + {[{no_match, First_match@1} | Rest@1], {no_match, _}} -> + [{no_match, + begin + _pipe@1 = erlang:element(2, Match), + gleam@list:append(_pipe@1, First_match@1) + end} | + Rest@1]; + + {Matches@1, Match@1} -> + [Match@1 | Matches@1] + end. + +-spec append_and_merge( + list(gap@comparison:match(list(GBX))), + gap@comparison:match(list(GBX)) +) -> list(gap@comparison:match(list(GBX))). +append_and_merge(Matches, Match) -> + _pipe@3 = case {begin + _pipe = Matches, + gleam@list:reverse(_pipe) + end, + Match} of + {[], _} -> + [Match]; + + {[{match, First_match} | Rest], {match, _}} -> + [{match, + begin + _pipe@1 = First_match, + gleam@list:append(_pipe@1, erlang:element(2, Match)) + end} | + Rest]; + + {[{no_match, First_match@1} | Rest@1], {no_match, _}} -> + [{no_match, + begin + _pipe@2 = First_match@1, + gleam@list:append(_pipe@2, erlang:element(2, Match)) + end} | + Rest@1]; + + {Matches@1, Match@1} -> + [Match@1 | Matches@1] + end, + gleam@list:reverse(_pipe@3). + +-spec collect_matches( + gleam@map:map_(GFY, any()), + list(GCH), + fun((GFY) -> integer()) +) -> list(gap@comparison:match(list(GCH))). +collect_matches(Tracking, Str, Extract_fun) -> + Matching_indexes = begin + _pipe = gleam@map:keys(Tracking), + _pipe@1 = gleam@list:map(_pipe, Extract_fun), + gleam@set:from_list(_pipe@1) + end, + Matches = begin + _pipe@2 = Str, + gleam@list:index_map( + _pipe@2, + fun(Index, Item) -> + case gleam@set:contains(Matching_indexes, Index) of + true -> + {match, Item}; + + false -> + {no_match, Item} + end + end + ) + end, + _pipe@3 = Matches, + _pipe@4 = gleam@list:chunk(_pipe@3, fun(Match) -> case Match of + {match, _} -> + true; + + {no_match, _} -> + false + end end), + gleam@list:map(_pipe@4, fun(Match_list) -> case Match_list of + [{match, _} | _] -> + {match, + gleam@list:filter_map( + Match_list, + fun(Match@1) -> case Match@1 of + {match, Item@1} -> + {ok, Item@1}; + + {no_match, _} -> + {error, nil} + end end + )}; + + [{no_match, _} | _] -> + {no_match, + gleam@list:filter_map( + Match_list, + fun(Match@2) -> case Match@2 of + {no_match, Item@2} -> + {ok, Item@2}; + + {match, _} -> + {error, nil} + end end + )} + end end). + +-spec back_track( + gleam@map:map_({integer(), integer()}, score(GCL)), + integer(), + integer(), + list({{integer(), integer()}, GCL}) +) -> list({{integer(), integer()}, GCL}). +back_track(Diff_map, First_index, Second_index, Stack) -> + case (First_index =:= 0) orelse (Second_index =:= 0) of + true -> + This_score = begin + _pipe = gleam@map:get(Diff_map, {First_index, Second_index}), + gleam@result:unwrap(_pipe, {score, 0, none}) + end, + case This_score of + {score, _, {some, Item}} -> + [{{First_index, Second_index}, Item} | Stack]; + + _ -> + case {First_index, Second_index} of + {0, A} when A > 0 -> + back_track( + Diff_map, + First_index, + Second_index - 1, + Stack + ); + + {A@1, 0} when A@1 > 0 -> + back_track( + Diff_map, + First_index - 1, + Second_index, + Stack + ); + + {0, 0} -> + Stack; + + {_, _} -> + back_track( + Diff_map, + First_index - 1, + Second_index, + Stack + ) + end + end; + + false -> + This_score@1 = begin + _pipe@1 = gleam@map:get(Diff_map, {First_index, Second_index}), + gleam@result:unwrap(_pipe@1, {score, 0, none}) + end, + case This_score@1 of + {score, _, {some, Item@1}} -> + back_track( + Diff_map, + First_index - 1, + Second_index - 1, + [{{First_index, Second_index}, Item@1} | Stack] + ); + + {score, _, none} -> + Up = begin + _pipe@2 = gleam@map:get( + Diff_map, + {First_index, Second_index - 1} + ), + gleam@result:unwrap(_pipe@2, {score, 0, none}) + end, + Back = begin + _pipe@3 = gleam@map:get( + Diff_map, + {First_index - 1, Second_index} + ), + gleam@result:unwrap(_pipe@3, {score, 0, none}) + end, + case gleam@int:compare( + erlang:element(2, Up), + erlang:element(2, Back) + ) of + gt -> + back_track( + Diff_map, + First_index, + Second_index - 1, + Stack + ); + + lt -> + back_track( + Diff_map, + First_index - 1, + Second_index, + Stack + ); + + eq -> + case {First_index, Second_index} of + {0, A@2} when A@2 > 0 -> + back_track( + Diff_map, + First_index, + Second_index - 1, + Stack + ); + + {A@3, 0} when A@3 > 0 -> + back_track( + Diff_map, + First_index - 1, + Second_index, + Stack + ); + + {0, 0} -> + Stack; + + {_, _} -> + back_track( + Diff_map, + First_index - 1, + Second_index, + Stack + ) + end + end + end + end. + +-spec build_diff_map( + GCR, + integer(), + GCR, + integer(), + gleam@map:map_({integer(), integer()}, score(GCR)) +) -> gleam@map:map_({integer(), integer()}, score(GCR)). +build_diff_map(First_item, First_index, Second_item, Second_index, Diff_map) -> + Prev_score = begin + _pipe = gleam@map:get(Diff_map, {First_index - 1, Second_index - 1}), + gleam@result:unwrap(_pipe, {score, 0, none}) + end, + Derived_score_up = begin + _pipe@1 = Diff_map, + _pipe@2 = gleam@map:get(_pipe@1, {First_index, Second_index - 1}), + gleam@result:unwrap(_pipe@2, {score, 0, none}) + end, + Derived_score_back = begin + _pipe@3 = Diff_map, + _pipe@4 = gleam@map:get(_pipe@3, {First_index - 1, Second_index}), + gleam@result:unwrap(_pipe@4, {score, 0, none}) + end, + Derived_score = gleam@int:max( + erlang:element(2, Derived_score_up), + erlang:element(2, Derived_score_back) + ), + This_score = case First_item =:= Second_item of + true -> + {score, erlang:element(2, Prev_score) + 1, {some, First_item}}; + + false -> + {score, Derived_score, none} + end, + _pipe@5 = Diff_map, + gleam@map:insert(_pipe@5, {First_index, Second_index}, This_score). + +-spec lcs(list(GBK), list(GBK)) -> gap@comparison:comparison(GBK). +lcs(First_sequence, Second_sequence) -> + Leading_matches = begin + _pipe = gleam@list:zip(First_sequence, Second_sequence), + _pipe@1 = gleam@list:take_while( + _pipe, + fun(Pair) -> erlang:element(1, Pair) =:= erlang:element(2, Pair) end + ), + gleam@list:map(_pipe@1, fun gleam@pair:first/1) + end, + Num_leading_matches = gleam@list:length(Leading_matches), + Trailing_matches = begin + _pipe@2 = gleam@list:zip( + gleam@list:reverse(First_sequence), + gleam@list:reverse(Second_sequence) + ), + _pipe@3 = gleam@list:take_while( + _pipe@2, + fun(Pair@1) -> + erlang:element(1, Pair@1) =:= erlang:element(2, Pair@1) + end + ), + _pipe@4 = gleam@list:map(_pipe@3, fun gleam@pair:first/1), + gleam@list:reverse(_pipe@4) + end, + Num_trailing_matches = gleam@list:length(Trailing_matches), + First_sequence_to_diff = begin + _pipe@5 = First_sequence, + _pipe@6 = gleam@list:drop(_pipe@5, Num_leading_matches), + gleam@list:take( + _pipe@6, + (gleam@list:length(First_sequence) - Num_leading_matches) - Num_trailing_matches + ) + end, + Second_sequence_to_diff = begin + _pipe@7 = Second_sequence, + _pipe@8 = gleam@list:drop(_pipe@7, Num_leading_matches), + gleam@list:take( + _pipe@8, + (gleam@list:length(Second_sequence) - Num_leading_matches) - Num_trailing_matches + ) + end, + Diff_map@2 = begin + _pipe@9 = Second_sequence_to_diff, + gleam@list:index_fold( + _pipe@9, + gleam@map:new(), + fun(Diff_map, Item_second, Index_second) -> + _pipe@10 = First_sequence_to_diff, + gleam@list:index_fold( + _pipe@10, + Diff_map, + fun(Diff_map@1, Item_first, Index_first) -> + build_diff_map( + Item_first, + Index_first, + Item_second, + Index_second, + Diff_map@1 + ) + end + ) + end + ) + end, + {First_segments@1, Second_segments@1} = case {First_sequence_to_diff, + Second_sequence_to_diff} of + {[], []} -> + {[], []}; + + {First_matching, []} -> + {[{no_match, First_matching}], []}; + + {[], Second_matching} -> + {[], [{no_match, Second_matching}]}; + + {First_sequence_to_diff@1, Second_sequence_to_diff@1} -> + Tracking = begin + _pipe@11 = back_track( + Diff_map@2, + gleam@list:length(First_sequence_to_diff@1) - 1, + gleam@list:length(Second_sequence_to_diff@1) - 1, + [] + ), + gleam@map:from_list(_pipe@11) + end, + First_segments = collect_matches( + Tracking, + First_sequence_to_diff@1, + fun(Key) -> + {First, _} = Key, + First + end + ), + Second_segments = collect_matches( + Tracking, + Second_sequence_to_diff@1, + fun(Key@1) -> + {_, Second} = Key@1, + Second + end + ), + {First_segments, Second_segments} + end, + {First_segments_with_leading_trailing, + Second_segments_with_leading_trailing} = case {Leading_matches, + Trailing_matches} of + {[], []} -> + {First_segments@1, Second_segments@1}; + + {[], Trailing_matches@1} -> + {begin + _pipe@12 = First_segments@1, + append_and_merge(_pipe@12, {match, Trailing_matches@1}) + end, + begin + _pipe@13 = Second_segments@1, + append_and_merge(_pipe@13, {match, Trailing_matches@1}) + end}; + + {Leading_matches@1, []} -> + {begin + _pipe@14 = First_segments@1, + prepend_and_merge(_pipe@14, {match, Leading_matches@1}) + end, + begin + _pipe@15 = Second_segments@1, + prepend_and_merge(_pipe@15, {match, Leading_matches@1}) + end}; + + {Leading_matches@2, Trailing_matches@2} -> + {begin + _pipe@16 = First_segments@1, + _pipe@17 = prepend_and_merge( + _pipe@16, + {match, Leading_matches@2} + ), + append_and_merge(_pipe@17, {match, Trailing_matches@2}) + end, + begin + _pipe@18 = Second_segments@1, + _pipe@19 = prepend_and_merge( + _pipe@18, + {match, Leading_matches@2} + ), + append_and_merge(_pipe@19, {match, Trailing_matches@2}) + end} + end, + {list_comparison, + First_segments_with_leading_trailing, + Second_segments_with_leading_trailing}. diff --git a/aoc2023/build/packages/gap/src/gap.gleam b/aoc2023/build/packages/gap/src/gap.gleam new file mode 100644 index 0000000..7eb0e7f --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap.gleam @@ -0,0 +1,438 @@ +import gleam/string +import gleam/list +import gleam/pair +import gleam/map.{type Map} +import gleam/result +import gleam/option.{type Option, None, Some} +import gleam/int +import gleam/order.{Eq, Gt, Lt} +import gleam/set +import gap/comparison.{ + type Comparison, type Match, type Segments, ListComparison, Match, NoMatch, + StringComparison, +} +import gap/styled_comparison.{type StyledComparison} +import gap/styling.{ + first_highlight_default, from_comparison, highlight, no_highlight, + second_highlight_default, to_styled_comparison, +} +import gap/myers.{type Edit, Del, Eq as MyerEq, Ins} + +type MatchedItem(a) = + #(#(Int, Int), a) + +type Score(a) { + Score(value: Int, item: Option(a)) +} + +type DiffMap(a) = + Map(#(Int, Int), Score(a)) + +/// Creates a `StyledComparison` from `Comparison` using default values for +/// highting and serialization. +/// +/// ## Example +/// +/// ```gleam +/// > compare_strings("abc", "abe") |> to_styled() +/// ``` +/// This will return a `StyledComparison(first, second)` where "c" in `first` is green +/// and "e" in `second` is red. +pub fn to_styled(comparison: Comparison(a)) -> StyledComparison { + comparison + |> from_comparison() + |> highlight(first_highlight_default, second_highlight_default, no_highlight) + |> to_styled_comparison() +} + +/// Compare two string and return a `StringComparison` which will be styled as string +/// when passed to `to_styled` +/// +/// Will use the default `myers` algorithm +pub fn compare_strings(first: String, second: String) -> Comparison(String) { + let comparison = + compare_lists(string.to_graphemes(first), string.to_graphemes(second)) + case comparison { + ListComparison(first, second) -> StringComparison(first, second) + StringComparison(first, second) -> StringComparison(first, second) + } +} + +/// Compare two string and return a `StringComparison` which will be styled as string +/// when passed to `to_styled` +/// +/// Algorithm can be used to select either `myers` or the legacy `lcs` algorithm +pub fn compare_strings_with_algorithm( + first: String, + second: String, + algorithm, +) -> Comparison(String) { + let comparison = + algorithm(string.to_graphemes(first), string.to_graphemes(second)) + case comparison { + ListComparison(first, second) -> StringComparison(first, second) + StringComparison(first, second) -> StringComparison(first, second) + } +} + +/// Compare two lists and return a `ListComparison` which will be styled as list +/// when passed to `to_styled` +/// +/// Will use the default `myers` algorithm +pub fn compare_lists( + first_sequence: List(a), + second_sequence: List(a), +) -> Comparison(a) { + myers(first_sequence, second_sequence) +} + +/// Compare two lists and return a `ListComparison` which will be styled as list +/// when passed to `to_styled` +/// +/// Algorithm can be used to select either `myers` or the legacy `lcs` algorithm +pub fn compare_lists_with_algorithm( + first_sequence: List(a), + second_sequence: List(a), + algorithm, +) -> Comparison(a) { + algorithm(first_sequence, second_sequence) +} + +/// An adapter for the the `myers` algorithm. +/// Intended to be use as an argument to `compare_strings_with_algorithm` or +/// `compare_lists_with_algorithm` +pub fn myers(first_sequence: List(a), second_sequence: List(a)) -> Comparison(a) { + let edits = myers.difference(first_sequence, second_sequence) + edits + |> list.reverse() + |> list.fold( + ListComparison([], []), + fn(comparison: Comparison(a), edit: Edit(a)) { + case comparison { + ListComparison(first, second) -> { + case edit { + MyerEq(segment) -> + ListComparison( + [Match(segment), ..first], + [Match(segment), ..second], + ) + Ins(segment) -> ListComparison(first, [NoMatch(segment), ..second]) + Del(segment) -> ListComparison([NoMatch(segment), ..first], second) + } + } + StringComparison(..) -> comparison + } + }, + ) +} + +/// An adapter for the the `lcs` (longest common subsequence) algorithm. +/// Intended to be use as an argument to `compare_strings_with_algorithm` or +/// `compare_lists_with_algorithm` +pub fn lcs(first_sequence: List(a), second_sequence: List(a)) -> Comparison(a) { + let leading_matches = + list.zip(first_sequence, second_sequence) + |> list.take_while(fn(pair) { pair.0 == pair.1 }) + |> list.map(pair.first) + let num_leading_matches = list.length(leading_matches) + let trailing_matches = + list.zip(list.reverse(first_sequence), list.reverse(second_sequence)) + |> list.take_while(fn(pair) { pair.0 == pair.1 }) + |> list.map(pair.first) + |> list.reverse() + let num_trailing_matches = list.length(trailing_matches) + let first_sequence_to_diff = + first_sequence + |> list.drop(num_leading_matches) + |> list.take( + list.length(first_sequence) - num_leading_matches - num_trailing_matches, + ) + let second_sequence_to_diff = + second_sequence + |> list.drop(num_leading_matches) + |> list.take( + list.length(second_sequence) - num_leading_matches - num_trailing_matches, + ) + + let diff_map = + second_sequence_to_diff + |> list.index_fold( + map.new(), + fn(diff_map, item_second, index_second) { + first_sequence_to_diff + |> list.index_fold( + diff_map, + fn(diff_map, item_first, index_first) { + build_diff_map( + item_first, + index_first, + item_second, + index_second, + diff_map, + ) + }, + ) + }, + ) + let #(first_segments, second_segments) = case + first_sequence_to_diff, + second_sequence_to_diff + { + [], [] -> #([], []) + first_matching, [] -> #([NoMatch(first_matching)], []) + [], second_matching -> #([], [NoMatch(second_matching)]) + first_sequence_to_diff, second_sequence_to_diff -> { + let tracking = + back_track( + diff_map, + list.length(first_sequence_to_diff) - 1, + list.length(second_sequence_to_diff) - 1, + [], + ) + |> map.from_list() + + let first_segments = + collect_matches( + tracking, + first_sequence_to_diff, + fn(key) { + let #(first, _) = key + first + }, + ) + let second_segments = + collect_matches( + tracking, + second_sequence_to_diff, + fn(key) { + let #(_, second) = key + second + }, + ) + #(first_segments, second_segments) + } + } + + let #( + first_segments_with_leading_trailing, + second_segments_with_leading_trailing, + ) = case leading_matches, trailing_matches { + [], [] -> #(first_segments, second_segments) + [], trailing_matches -> #( + first_segments + |> append_and_merge(Match(trailing_matches)), + second_segments + |> append_and_merge(Match(trailing_matches)), + ) + leading_matches, [] -> #( + first_segments + |> prepend_and_merge(Match(leading_matches)), + second_segments + |> prepend_and_merge(Match(leading_matches)), + ) + leading_matches, trailing_matches -> #( + first_segments + |> prepend_and_merge(Match(leading_matches)) + |> append_and_merge(Match(trailing_matches)), + second_segments + |> prepend_and_merge(Match(leading_matches)) + |> append_and_merge(Match(trailing_matches)), + ) + } + + ListComparison( + first_segments_with_leading_trailing, + second_segments_with_leading_trailing, + ) +} + +fn prepend_and_merge( + matches: List(Match(List(a))), + match: Match(List(a)), +) -> List(Match(List(a))) { + case matches, match { + [], _ -> [match] + [Match(first_match), ..rest], Match(_) -> [ + Match( + match.item + |> list.append(first_match), + ), + ..rest + ] + [NoMatch(first_match), ..rest], NoMatch(_) -> [ + NoMatch( + match.item + |> list.append(first_match), + ), + ..rest + ] + matches, match -> [match, ..matches] + } +} + +fn append_and_merge( + matches: List(Match(List(a))), + match: Match(List(a)), +) -> List(Match(List(a))) { + case + matches + |> list.reverse(), + match + { + [], _ -> [match] + [Match(first_match), ..rest], Match(_) -> [ + Match( + first_match + |> list.append(match.item), + ), + ..rest + ] + [NoMatch(first_match), ..rest], NoMatch(_) -> [ + NoMatch( + first_match + |> list.append(match.item), + ), + ..rest + ] + matches, match -> [match, ..matches] + } + |> list.reverse() +} + +fn collect_matches(tracking, str: List(a), extract_fun) -> Segments(a) { + let matching_indexes = + map.keys(tracking) + |> list.map(extract_fun) + |> set.from_list() + + let matches = + str + |> list.index_map(fn(index, item) { + case set.contains(matching_indexes, index) { + True -> Match(item) + False -> NoMatch(item) + } + }) + + matches + |> list.chunk(fn(match) { + case match { + Match(_) -> True + NoMatch(_) -> False + } + }) + |> list.map(fn(match_list) { + case match_list { + [Match(_), ..] -> + Match(list.filter_map( + match_list, + fn(match) { + case match { + Match(item) -> Ok(item) + NoMatch(_) -> Error(Nil) + } + }, + )) + [NoMatch(_), ..] -> + NoMatch(list.filter_map( + match_list, + fn(match) { + case match { + NoMatch(item) -> Ok(item) + Match(_) -> Error(Nil) + } + }, + )) + } + }) +} + +fn back_track( + diff_map: DiffMap(a), + first_index: Int, + second_index: Int, + stack: List(MatchedItem(a)), +) -> List(MatchedItem(a)) { + case first_index == 0 || second_index == 0 { + True -> { + let this_score = + map.get(diff_map, #(first_index, second_index)) + |> result.unwrap(Score(0, None)) + case this_score { + Score(_, Some(item)) -> [#(#(first_index, second_index), item), ..stack] + _ -> + case first_index, second_index { + 0, a if a > 0 -> + back_track(diff_map, first_index, second_index - 1, stack) + a, 0 if a > 0 -> + back_track(diff_map, first_index - 1, second_index, stack) + 0, 0 -> stack + _, _ -> back_track(diff_map, first_index - 1, second_index, stack) + } + } + } + False -> { + let this_score = + map.get(diff_map, #(first_index, second_index)) + |> result.unwrap(Score(0, None)) + case this_score { + Score(_, Some(item)) -> + back_track( + diff_map, + first_index - 1, + second_index - 1, + [#(#(first_index, second_index), item), ..stack], + ) + Score(_, None) -> { + let up = + map.get(diff_map, #(first_index, second_index - 1)) + |> result.unwrap(Score(0, None)) + let back = + map.get(diff_map, #(first_index - 1, second_index)) + |> result.unwrap(Score(0, None)) + case int.compare(up.value, back.value) { + Gt -> back_track(diff_map, first_index, second_index - 1, stack) + Lt -> back_track(diff_map, first_index - 1, second_index, stack) + Eq -> + case first_index, second_index { + 0, a if a > 0 -> + back_track(diff_map, first_index, second_index - 1, stack) + a, 0 if a > 0 -> + back_track(diff_map, first_index - 1, second_index, stack) + 0, 0 -> stack + _, _ -> + back_track(diff_map, first_index - 1, second_index, stack) + } + } + } + } + } + } +} + +fn build_diff_map( + first_item: a, + first_index: Int, + second_item: a, + second_index: Int, + diff_map: DiffMap(a), +) -> DiffMap(a) { + let prev_score = + map.get(diff_map, #(first_index - 1, second_index - 1)) + |> result.unwrap(Score(0, None)) + let derived_score_up = + diff_map + |> map.get(#(first_index, second_index - 1)) + |> result.unwrap(Score(0, None)) + let derived_score_back = + diff_map + |> map.get(#(first_index - 1, second_index)) + |> result.unwrap(Score(0, None)) + let derived_score = int.max(derived_score_up.value, derived_score_back.value) + let this_score = case first_item == second_item { + True -> Score(prev_score.value + 1, Some(first_item)) + False -> Score(derived_score, None) + } + diff_map + |> map.insert(#(first_index, second_index), this_score) +} diff --git a/aoc2023/build/packages/gap/src/gap/comparison.gleam b/aoc2023/build/packages/gap/src/gap/comparison.gleam new file mode 100644 index 0000000..da30c29 --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap/comparison.gleam @@ -0,0 +1,22 @@ +/// Comparison of two strings or lists +/// +/// The comparison consists of two lists of matched segments. The segments represent +/// a sequence of succeeding matches or non-matches (up until the next match/non-match) +/// +/// For lists the elements in the segment will be same as the elements in the list, and +/// for strings the elements will be the graphemes of the string +pub type Comparison(a) { + ListComparison(first: Segments(a), second: Segments(a)) + StringComparison(first: Segments(String), second: Segments(String)) +} + +/// Indicating that the item has a matching (`Match`) or no matching (`NoMatch`) item in the +/// other string/list +pub type Match(a) { + Match(item: a) + NoMatch(item: a) +} + +/// List of segments of succeeding matches / non-matches +pub type Segments(a) = + List(Match(List(a))) diff --git a/aoc2023/build/packages/gap/src/gap/myers.gleam b/aoc2023/build/packages/gap/src/gap/myers.gleam new file mode 100644 index 0000000..f0b8ddc --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap/myers.gleam @@ -0,0 +1,122 @@ +import gleam/list + +pub type Edit(a) { + Eq(List(a)) + Del(List(a)) + Ins(List(a)) +} + +type Path(a) { + Path(x: Int, y: Int, list1: List(a), list2: List(a), edits: List(Edit(a))) +} + +type Status(a) { + Done(edits: List(Edit(a))) + Next(paths: List(Path(a))) + Cont(path: Path(a)) +} + +/// The algorithm is outlined in the +/// "An O(ND) Difference Algorithm and Its Variations" paper by E. Myers. +/// +/// Adapted from the implementation of "myers_difference" in Elixirs List module +pub fn difference(list1: List(a), list2: List(a)) -> List(Edit(a)) { + let path = Path(0, 0, list1, list2, []) + find_script(0, list.length(list1) + list.length(list2), [path]) +} + +fn find_script(envelope: Int, max: Int, paths: List(Path(a))) { + case envelope > max { + True -> [] + False -> { + case each_diagonal(-envelope, envelope, paths, []) { + Done(edits) -> compact_reverse(edits, []) + Next(paths) -> find_script(envelope + 1, max, paths) + _ -> panic as "Didn't expect a Cont here" + } + } + } +} + +fn compact_reverse(edits: List(Edit(a)), acc: List(Edit(a))) -> List(Edit(a)) { + case edits, acc { + [], acc -> acc + [Eq(elem), ..rest], [Eq(result), ..acc_rest] -> + compact_reverse(rest, [Eq(list.flatten([elem, result])), ..acc_rest]) + [Del(elem), ..rest], [Del(result), ..acc_rest] -> + compact_reverse(rest, [Del(list.flatten([elem, result])), ..acc_rest]) + [Ins(elem), ..rest], [Ins(result), ..acc_rest] -> + compact_reverse(rest, [Ins(list.flatten([elem, result])), ..acc_rest]) + [Eq(elem), ..rest], acc -> compact_reverse(rest, [Eq(elem), ..acc]) + [Del(elem), ..rest], acc -> compact_reverse(rest, [Del(elem), ..acc]) + [Ins(elem), ..rest], acc -> compact_reverse(rest, [Ins(elem), ..acc]) + } +} + +fn each_diagonal( + diag: Int, + limit: Int, + paths: List(Path(a)), + next_paths: List(Path(a)), +) -> Status(a) { + case diag > limit { + True -> Next(list.reverse(next_paths)) + False -> { + let #(path, rest) = proceed_path(diag, limit, paths) + case follow_snake(path) { + Cont(path) -> each_diagonal(diag + 2, limit, rest, [path, ..next_paths]) + other -> other + } + } + } +} + +fn proceed_path( + diag: Int, + limit: Int, + paths: List(Path(a)), +) -> #(Path(a), List(Path(a))) { + let neg_limit = -limit + case diag, limit, paths { + 0, 0, [path] -> #(path, []) + diag, _limit, [path, ..] as paths if diag == neg_limit -> #( + move_down(path), + paths, + ) + diag, limit, [path, ..] as paths if diag == limit -> #( + move_right(path), + paths, + ) + _diag, _limit, [path1, path2, ..rest] -> { + case path1.y > path2.y { + True -> #(move_right(path1), [path2, ..rest]) + False -> #(move_down(path2), [path2, ..rest]) + } + } + } +} + +fn move_right(path: Path(a)) -> Path(a) { + case path { + Path(x, y, list1, [elem, ..rest], edits) -> + Path(x + 1, y, list1, rest, [Ins([elem]), ..edits]) + Path(x, y, list1, [], edits) -> Path(x + 1, y, list1, [], edits) + } +} + +fn move_down(path: Path(a)) -> Path(a) { + case path { + Path(x, y, [elem, ..rest], list2, edits) -> + Path(x, y + 1, rest, list2, [Del([elem]), ..edits]) + Path(x, y, [], list2, edits) -> Path(x, y + 1, [], list2, edits) + } +} + +fn follow_snake(path: Path(a)) -> Status(a) { + case path { + Path(x, y, [elem1, ..rest1], [elem2, ..rest2], edits) if elem1 == elem2 -> + follow_snake(Path(x + 1, y + 1, rest1, rest2, [Eq([elem1]), ..edits])) + Path(_x, _y, [], [], edits) -> Done(edits) + _ -> Cont(path) + } +} diff --git a/aoc2023/build/packages/gap/src/gap/styled_comparison.gleam b/aoc2023/build/packages/gap/src/gap/styled_comparison.gleam new file mode 100644 index 0000000..7103c2e --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap/styled_comparison.gleam @@ -0,0 +1,4 @@ +/// A comparison where the parts have been styled (serialized and highlighted) +pub type StyledComparison { + StyledComparison(first: String, second: String) +} diff --git a/aoc2023/build/packages/gap/src/gap/styling.gleam b/aoc2023/build/packages/gap/src/gap/styling.gleam new file mode 100644 index 0000000..623ae8a --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap/styling.gleam @@ -0,0 +1,233 @@ +import gleam/option.{type Option, None, Some} +import gleam/list +import gleam/string +import gleam_community/ansi +import gap/comparison.{ + type Comparison, type Segments, ListComparison, Match, NoMatch, + StringComparison, +} +import gap/styled_comparison.{type StyledComparison, StyledComparison} + +/// The `Highlighter`takes a string representation of the item that was not matching +/// and should return a string representation that can be used to visually indicate that +/// it is a non-matching item. +/// +/// The default implementation of the highlighters uses the +/// [gleam_community/ansi](https://hexdocs.pm/gleam_community_ansi/index.html) library +/// to set a different color for the item, but any type if indication can be used as long +/// as it returns a valid string +pub type Highlighter = + fn(String) -> String + +/// `Part` is used to indicate to a custom serializer if it should produce a serialization +/// based on a segment with items or the final string that contains already serialized segments +pub type Part(a) { + /// `acc` the already serialized part of the result, `part` is the current segment that should be serialized and appended and `highlighter` is the `Highlighter` that can be used to indicate non-matching items + Part(acc: String, part: List(a), highlight: Highlighter) + /// `all` is a string representing all serialized segments. This can be useful if some string should be prepended/appended to the final result + All(all: String) +} + +/// A `Serializer`can be used to create string representation of the comparison results +/// +/// See [serialize](#serialize) for adding custom serializers and [mk_generic_serializer](#mk_generic_serializer) +pub type Serializer(a) = + fn(Part(a)) -> String + +/// Highlighters to use for indicating matches / non-matches +/// +/// `first` is used to highlight non-matches in the first string/list +/// `second` is used to highlight non-matches in the second string/list +/// `matching` is used to highlight matches in the both strings/lists +pub type Highlighters { + Highlighters(first: Highlighter, second: Highlighter, matching: Highlighter) +} + +/// Styling of a `Comparison` +/// +/// See [from_comparison](#from_comparison) +pub opaque type Styling(a) { + Styling( + comparison: Comparison(a), + serializer: Option(Serializer(a)), + highlight: Option(Highlighters), + ) +} + +/// Create a new `Styling` from a `Comparison` +/// +/// The `Styling` can be customized by adding highlighters and a serializer +/// See [highlight](#highlight) and [serialize](#serialize) +pub fn from_comparison(comparison: Comparison(a)) -> Styling(a) { + Styling(comparison, None, None) +} + +/// Add highlighters to the `Styling` +/// +/// The highlighters are used to mark the matching/non-matching items in the +/// first/second list/string +pub fn highlight( + styling: Styling(a), + first: Highlighter, + second: Highlighter, + matching: Highlighter, +) -> Styling(a) { + Styling(..styling, highlight: Some(Highlighters(first, second, matching))) +} + +/// Add a serializer to the `Styling` +/// +/// The serializer is used to create string representation of the items in the segments of the `Comparison` +/// See [Part](#part) for details +/// +/// > **NOTE:** `StringComparison` will always use the default string serializer (concatenating the graphemes). +/// > If there is a need for custom serialization of `StringComparison` convert the string to a list of +/// > graphemes and treat it as a `ListComparison` +pub fn serialize(styling: Styling(a), serializer: Serializer(a)) -> Styling(a) { + Styling(..styling, serializer: Some(serializer)) +} + +/// Creates a styled comparison using either custom highlighters/serializer if they where added or default +/// highlighters and/or serializer +pub fn to_styled_comparison(styling: Styling(a)) -> StyledComparison { + let highlight = + styling.highlight + |> option.unwrap(Highlighters( + first_highlight_default, + second_highlight_default, + no_highlight, + )) + case styling.comparison { + StringComparison(first, second) -> + to_strings( + first, + second, + // NOTE: Using string serializer here because otherwise we need to have a specific string serializer on the styling + string_serializer, + highlight.first, + highlight.second, + highlight.matching, + ) + ListComparison(first, second) -> + to_strings( + first, + second, + option.unwrap(styling.serializer, generic_serializer), + highlight.first, + highlight.second, + highlight.matching, + ) + } +} + +/// Default highlighter for the first string/list in the comparison +pub fn first_highlight_default(string: String) -> String { + case string { + " " -> + string + |> ansi.underline() + |> ansi.bold() + |> ansi.green() + + _ -> + string + |> ansi.green() + |> ansi.bold() + } +} + +/// Default highlighter for the second string/list in the comparison +pub fn second_highlight_default(string: String) -> String { + case string { + " " -> + string + |> ansi.underline() + |> ansi.bold() + |> ansi.red() + + _ -> + string + |> ansi.red() + |> ansi.bold() + } +} + +/// Default highlighter used for matching items +pub fn no_highlight(string: String) -> String { + string +} + +fn string_serializer(part: Part(String)) -> String { + case part { + Part(acc, sequence, highlight) -> + acc <> { + sequence + |> list.map(highlight) + |> string.join("") + } + All(string) -> string + } +} + +fn generic_serializer(part: Part(a)) -> String { + mk_generic_serializer(", ", fn(all) { "[" <> all <> "]" })(part) +} + +/// Creates a generic serializer that uses `separator` between all items and calls +/// `around` for possibility to prepend/append strings to the final result +pub fn mk_generic_serializer(separator: String, around: fn(String) -> String) { + fn(part) { + case part { + Part(acc, sequence, highlight) -> { + let segment_separator = case acc { + "" -> "" + _ -> separator + } + acc <> segment_separator <> { + sequence + |> list.map(string.inspect) + |> list.map(highlight) + |> string.join(separator) + } + } + All(string) -> around(string) + } + } +} + +fn to_strings( + first: Segments(a), + second: Segments(a), + serializer: Serializer(a), + first_highlight: Highlighter, + second_highlight: Highlighter, + no_highlight: Highlighter, +) -> StyledComparison { + let first_styled = + first + |> list.fold( + "", + fn(str, match) { + case match { + Match(item) -> serializer(Part(str, item, no_highlight)) + NoMatch(item) -> serializer(Part(str, item, first_highlight)) + } + }, + ) + let second_styled = + second + |> list.fold( + "", + fn(str, match) { + case match { + Match(item) -> serializer(Part(str, item, no_highlight)) + NoMatch(item) -> serializer(Part(str, item, second_highlight)) + } + }, + ) + + StyledComparison( + serializer(All(first_styled)), + serializer(All(second_styled)), + ) +} diff --git a/aoc2023/build/packages/gap/src/gap@comparison.erl b/aoc2023/build/packages/gap/src/gap@comparison.erl new file mode 100644 index 0000000..36bd1c3 --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap@comparison.erl @@ -0,0 +1,15 @@ +-module(gap@comparison). +-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]). + +-export_type([comparison/1, match/1]). + +-type comparison(FQT) :: {list_comparison, + list(match(list(FQT))), + list(match(list(FQT)))} | + {string_comparison, + list(match(list(binary()))), + list(match(list(binary())))}. + +-type match(FQU) :: {match, FQU} | {no_match, FQU}. + + diff --git a/aoc2023/build/packages/gap/src/gap@myers.erl b/aoc2023/build/packages/gap/src/gap@myers.erl new file mode 100644 index 0000000..6a8ad35 --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap@myers.erl @@ -0,0 +1,156 @@ +-module(gap@myers). +-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]). + +-export([difference/2]). +-export_type([edit/1, path/1, status/1]). + +-type edit(FUV) :: {eq, list(FUV)} | {del, list(FUV)} | {ins, list(FUV)}. + +-type path(FUW) :: {path, + integer(), + integer(), + list(FUW), + list(FUW), + list(edit(FUW))}. + +-type status(FUX) :: {done, list(edit(FUX))} | + {next, list(path(FUX))} | + {cont, path(FUX)}. + +-spec compact_reverse(list(edit(FVH)), list(edit(FVH))) -> list(edit(FVH)). +compact_reverse(Edits, Acc) -> + case {Edits, Acc} of + {[], Acc@1} -> + Acc@1; + + {[{eq, Elem} | Rest], [{eq, Result} | Acc_rest]} -> + compact_reverse( + Rest, + [{eq, gleam@list:flatten([Elem, Result])} | Acc_rest] + ); + + {[{del, Elem@1} | Rest@1], [{del, Result@1} | Acc_rest@1]} -> + compact_reverse( + Rest@1, + [{del, gleam@list:flatten([Elem@1, Result@1])} | Acc_rest@1] + ); + + {[{ins, Elem@2} | Rest@2], [{ins, Result@2} | Acc_rest@2]} -> + compact_reverse( + Rest@2, + [{ins, gleam@list:flatten([Elem@2, Result@2])} | Acc_rest@2] + ); + + {[{eq, Elem@3} | Rest@3], Acc@2} -> + compact_reverse(Rest@3, [{eq, Elem@3} | Acc@2]); + + {[{del, Elem@4} | Rest@4], Acc@3} -> + compact_reverse(Rest@4, [{del, Elem@4} | Acc@3]); + + {[{ins, Elem@5} | Rest@5], Acc@4} -> + compact_reverse(Rest@5, [{ins, Elem@5} | Acc@4]) + end. + +-spec move_right(path(FWA)) -> path(FWA). +move_right(Path) -> + case Path of + {path, X, Y, List1, [Elem | Rest], Edits} -> + {path, X + 1, Y, List1, Rest, [{ins, [Elem]} | Edits]}; + + {path, X@1, Y@1, List1@1, [], Edits@1} -> + {path, X@1 + 1, Y@1, List1@1, [], Edits@1} + end. + +-spec move_down(path(FWD)) -> path(FWD). +move_down(Path) -> + case Path of + {path, X, Y, [Elem | Rest], List2, Edits} -> + {path, X, Y + 1, Rest, List2, [{del, [Elem]} | Edits]}; + + {path, X@1, Y@1, [], List2@1, Edits@1} -> + {path, X@1, Y@1 + 1, [], List2@1, Edits@1} + end. + +-spec proceed_path(integer(), integer(), list(path(FVU))) -> {path(FVU), + list(path(FVU))}. +proceed_path(Diag, Limit, Paths) -> + Neg_limit = - Limit, + case {Diag, Limit, Paths} of + {0, 0, [Path]} -> + {Path, []}; + + {Diag@1, _, [Path@1 | _] = Paths@1} when Diag@1 =:= Neg_limit -> + {move_down(Path@1), Paths@1}; + + {Diag@2, Limit@1, [Path@2 | _] = Paths@2} when Diag@2 =:= Limit@1 -> + {move_right(Path@2), Paths@2}; + + {_, _, [Path1, Path2 | Rest]} -> + case erlang:element(3, Path1) > erlang:element(3, Path2) of + true -> + {move_right(Path1), [Path2 | Rest]}; + + false -> + {move_down(Path2), [Path2 | Rest]} + end + end. + +-spec follow_snake(path(FWG)) -> status(FWG). +follow_snake(Path) -> + case Path of + {path, X, Y, [Elem1 | Rest1], [Elem2 | Rest2], Edits} when Elem1 =:= Elem2 -> + follow_snake( + {path, X + 1, Y + 1, Rest1, Rest2, [{eq, [Elem1]} | Edits]} + ); + + {path, _, _, [], [], Edits@1} -> + {done, Edits@1}; + + _ -> + {cont, Path} + end. + +-spec each_diagonal(integer(), integer(), list(path(FVO)), list(path(FVO))) -> status(FVO). +each_diagonal(Diag, Limit, Paths, Next_paths) -> + case Diag > Limit of + true -> + {next, gleam@list:reverse(Next_paths)}; + + false -> + {Path, Rest} = proceed_path(Diag, Limit, Paths), + case follow_snake(Path) of + {cont, Path@1} -> + each_diagonal(Diag + 2, Limit, Rest, [Path@1 | Next_paths]); + + Other -> + Other + end + end. + +-spec find_script(integer(), integer(), list(path(FVD))) -> list(edit(FVD)). +find_script(Envelope, Max, Paths) -> + case Envelope > Max of + true -> + []; + + false -> + case each_diagonal(- Envelope, Envelope, Paths, []) of + {done, Edits} -> + compact_reverse(Edits, []); + + {next, Paths@1} -> + find_script(Envelope + 1, Max, Paths@1); + + _ -> + erlang:error(#{gleam_error => panic, + message => <<"Didn't expect a Cont here"/utf8>>, + module => <<"gap/myers"/utf8>>, + function => <<"find_script"/utf8>>, + line => 35}) + end + end. + +-spec difference(list(FUY), list(FUY)) -> list(edit(FUY)). +difference(List1, List2) -> + Path = {path, 0, 0, List1, List2, []}, + find_script(0, gleam@list:length(List1) + gleam@list:length(List2), [Path]). diff --git a/aoc2023/build/packages/gap/src/gap@styled_comparison.erl b/aoc2023/build/packages/gap/src/gap@styled_comparison.erl new file mode 100644 index 0000000..14cc390 --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap@styled_comparison.erl @@ -0,0 +1,8 @@ +-module(gap@styled_comparison). +-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]). + +-export_type([styled_comparison/0]). + +-type styled_comparison() :: {styled_comparison, binary(), binary()}. + + diff --git a/aoc2023/build/packages/gap/src/gap@styling.erl b/aoc2023/build/packages/gap/src/gap@styling.erl new file mode 100644 index 0000000..ba226c3 --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap@styling.erl @@ -0,0 +1,202 @@ +-module(gap@styling). +-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]). + +-export([from_comparison/1, highlight/4, serialize/2, first_highlight_default/1, second_highlight_default/1, no_highlight/1, mk_generic_serializer/2, to_styled_comparison/1]). +-export_type([part/1, highlighters/0, styling/1]). + +-type part(FRE) :: {part, binary(), list(FRE), fun((binary()) -> binary())} | + {all, binary()}. + +-type highlighters() :: {highlighters, + fun((binary()) -> binary()), + fun((binary()) -> binary()), + fun((binary()) -> binary())}. + +-opaque styling(FRF) :: {styling, + gap@comparison:comparison(FRF), + gleam@option:option(fun((part(FRF)) -> binary())), + gleam@option:option(highlighters())}. + +-spec from_comparison(gap@comparison:comparison(FRI)) -> styling(FRI). +from_comparison(Comparison) -> + {styling, Comparison, none, none}. + +-spec highlight( + styling(FRL), + fun((binary()) -> binary()), + fun((binary()) -> binary()), + fun((binary()) -> binary()) +) -> styling(FRL). +highlight(Styling, First, Second, Matching) -> + erlang:setelement( + 4, + Styling, + {some, {highlighters, First, Second, Matching}} + ). + +-spec serialize(styling(FRO), fun((part(FRO)) -> binary())) -> styling(FRO). +serialize(Styling, Serializer) -> + erlang:setelement(3, Styling, {some, Serializer}). + +-spec first_highlight_default(binary()) -> binary(). +first_highlight_default(String) -> + case String of + <<" "/utf8>> -> + _pipe = String, + _pipe@1 = gleam_community@ansi:underline(_pipe), + _pipe@2 = gleam_community@ansi:bold(_pipe@1), + gleam_community@ansi:green(_pipe@2); + + _ -> + _pipe@3 = String, + _pipe@4 = gleam_community@ansi:green(_pipe@3), + gleam_community@ansi:bold(_pipe@4) + end. + +-spec second_highlight_default(binary()) -> binary(). +second_highlight_default(String) -> + case String of + <<" "/utf8>> -> + _pipe = String, + _pipe@1 = gleam_community@ansi:underline(_pipe), + _pipe@2 = gleam_community@ansi:bold(_pipe@1), + gleam_community@ansi:red(_pipe@2); + + _ -> + _pipe@3 = String, + _pipe@4 = gleam_community@ansi:red(_pipe@3), + gleam_community@ansi:bold(_pipe@4) + end. + +-spec no_highlight(binary()) -> binary(). +no_highlight(String) -> + String. + +-spec string_serializer(part(binary())) -> binary(). +string_serializer(Part) -> + case Part of + {part, Acc, Sequence, Highlight} -> + <<Acc/binary, + (begin + _pipe = Sequence, + _pipe@1 = gleam@list:map(_pipe, Highlight), + gleam@string:join(_pipe@1, <<""/utf8>>) + end)/binary>>; + + {all, String} -> + String + end. + +-spec mk_generic_serializer(binary(), fun((binary()) -> binary())) -> fun((part(any())) -> binary()). +mk_generic_serializer(Separator, Around) -> + fun(Part) -> case Part of + {part, Acc, Sequence, Highlight} -> + Segment_separator = case Acc of + <<""/utf8>> -> + <<""/utf8>>; + + _ -> + Separator + end, + <<<<Acc/binary, Segment_separator/binary>>/binary, + (begin + _pipe = Sequence, + _pipe@1 = gleam@list:map( + _pipe, + fun gleam@string:inspect/1 + ), + _pipe@2 = gleam@list:map(_pipe@1, Highlight), + gleam@string:join(_pipe@2, Separator) + end)/binary>>; + + {all, String} -> + Around(String) + end end. + +-spec generic_serializer(part(any())) -> binary(). +generic_serializer(Part) -> + (mk_generic_serializer( + <<", "/utf8>>, + fun(All) -> <<<<"["/utf8, All/binary>>/binary, "]"/utf8>> end + ))(Part). + +-spec to_strings( + list(gap@comparison:match(list(FRY))), + list(gap@comparison:match(list(FRY))), + fun((part(FRY)) -> binary()), + fun((binary()) -> binary()), + fun((binary()) -> binary()), + fun((binary()) -> binary()) +) -> gap@styled_comparison:styled_comparison(). +to_strings( + First, + Second, + Serializer, + First_highlight, + Second_highlight, + No_highlight +) -> + First_styled = begin + _pipe = First, + gleam@list:fold(_pipe, <<""/utf8>>, fun(Str, Match) -> case Match of + {match, Item} -> + Serializer({part, Str, Item, No_highlight}); + + {no_match, Item@1} -> + Serializer({part, Str, Item@1, First_highlight}) + end end) + end, + Second_styled = begin + _pipe@1 = Second, + gleam@list:fold( + _pipe@1, + <<""/utf8>>, + fun(Str@1, Match@1) -> case Match@1 of + {match, Item@2} -> + Serializer({part, Str@1, Item@2, No_highlight}); + + {no_match, Item@3} -> + Serializer({part, Str@1, Item@3, Second_highlight}) + end end + ) + end, + {styled_comparison, + Serializer({all, First_styled}), + Serializer({all, Second_styled})}. + +-spec to_styled_comparison(styling(any())) -> gap@styled_comparison:styled_comparison(). +to_styled_comparison(Styling) -> + Highlight = begin + _pipe = erlang:element(4, Styling), + gleam@option:unwrap( + _pipe, + {highlighters, + fun first_highlight_default/1, + fun second_highlight_default/1, + fun no_highlight/1} + ) + end, + case erlang:element(2, Styling) of + {string_comparison, First, Second} -> + to_strings( + First, + Second, + fun string_serializer/1, + erlang:element(2, Highlight), + erlang:element(3, Highlight), + erlang:element(4, Highlight) + ); + + {list_comparison, First@1, Second@1} -> + to_strings( + First@1, + Second@1, + gleam@option:unwrap( + erlang:element(3, Styling), + fun generic_serializer/1 + ), + erlang:element(2, Highlight), + erlang:element(3, Highlight), + erlang:element(4, Highlight) + ) + end. diff --git a/aoc2023/build/packages/gap/src/gap_ffi.mjs b/aoc2023/build/packages/gap/src/gap_ffi.mjs new file mode 100644 index 0000000..235c80b --- /dev/null +++ b/aoc2023/build/packages/gap/src/gap_ffi.mjs @@ -0,0 +1,431 @@ +import { + Error, + List, + Ok, + inspect, + toList, + makeError, + isEqual, +} from "./gleam.mjs"; +import * as $option from "../gleam_stdlib/gleam/option.mjs"; + +const HASHCODE_CACHE = new WeakMap(); +const Nil = undefined; + +class MutableMap { + static #hashcode_cache = new WeakMap(); + + static hash(value) { + let existing = this.#hashcode_cache.get(value); + if (existing) { + return existing; + } else if (value instanceof Object) { + let hashcode = inspect(value); + HASHCODE_CACHE.set(value, hashcode); + return hashcode; + } else { + return value.toString(); + } + } + + constructor() { + this.entries = new globalThis.Map(); + } + + get size() { + return this.entries.size; + } + + inspect() { + let entries = [...this.entries.values()] + .map((pair) => inspect(pair)) + .join(", "); + return `map.from_list([${entries}])`; + } + + toList() { + return List.fromArray([...this.entries.values()]); + } + + insert(k, v) { + this.entries.set(MutableMap.hash(k), [k, v]); + return this; + } + + delete(k) { + this.entries.delete(MutableMap.hash(k)); + return this; + } + + get(key) { + let code = MutableMap.hash(key); + if (this.entries.has(code)) { + return new Ok(this.entries.get(code)[1]); + } else { + return new Error(Nil); + } + } +} + +export function new_mutable_map() { + return new MutableMap(); +} + +export function mutable_map_size(map) { + return map.size; +} + +export function mutable_map_to_list(map) { + return map.toList(); +} + +export function mutable_map_remove(k, map) { + return map.delete(k); +} + +export function mutable_map_get(map, key) { + return map.get(key); +} + +export function mutable_map_insert(key, value, map) { + return map.insert(key, value); +} + +// From map.mjs + +export function size(map) { + return mutable_map_size(map); +} + +export function to_list(map) { + return mutable_map_to_list(map); +} + +export function new$() { + return new_mutable_map(); +} + +export function get(from, get) { + return mutable_map_get(from, get); +} + +function do_has_key(key, map) { + return !isEqual(get(map, key), new Error(undefined)); +} + +export function has_key(map, key) { + return do_has_key(key, map); +} + +export function insert(map, key, value) { + return mutable_map_insert(key, value, map); +} + +function insert_pair(map, pair) { + return insert(map, pair[0], pair[1]); +} + +export function update(map, key, fun) { + let _pipe = map; + let _pipe$1 = get(_pipe, key); + let _pipe$2 = $option.from_result(_pipe$1); + let _pipe$3 = fun(_pipe$2); + return ((_capture) => { + return insert(map, key, _capture); + })(_pipe$3); +} + +export function delete$(map, key) { + return mutable_map_remove(key, map); +} + +function fold_list_of_pair(loop$list, loop$initial) { + while (true) { + let list = loop$list; + let initial = loop$initial; + if (list.hasLength(0)) { + return initial; + } else if (list.atLeastLength(1)) { + let x = list.head; + let rest = list.tail; + loop$list = rest; + loop$initial = insert(initial, x[0], x[1]); + } else { + throw makeError( + "case_no_match", + "gleam/map", + 98, + "fold_list_of_pair", + "No case clause matched", + { values: [list] } + ); + } + } +} + +function do_from_list(list) { + return fold_list_of_pair(list, new$()); +} + +export function from_list(list) { + return do_from_list(list); +} + +function do_fold(loop$list, loop$initial, loop$fun) { + while (true) { + let list = loop$list; + let initial = loop$initial; + let fun = loop$fun; + if (list.hasLength(0)) { + return initial; + } else if (list.atLeastLength(1)) { + let k = list.head[0]; + let v = list.head[1]; + let tail = list.tail; + loop$list = tail; + loop$initial = fun(initial, k, v); + loop$fun = fun; + } else { + throw makeError( + "case_no_match", + "gleam/map", + 558, + "do_fold", + "No case clause matched", + { values: [list] } + ); + } + } +} + +export function fold(map, initial, fun) { + let _pipe = map; + let _pipe$1 = to_list(_pipe); + return do_fold(_pipe$1, initial, fun); +} + +function do_map_values(f, map) { + let f$1 = (map, k, v) => { + return insert(map, k, f(k, v)); + }; + let _pipe = map; + return fold(_pipe, new$(), f$1); +} + +export function map_values(map, fun) { + return do_map_values(fun, map); +} + +function do_filter(f, map) { + let insert$1 = (map, k, v) => { + let $ = f(k, v); + if ($) { + return insert(map, k, v); + } else { + return map; + } + }; + let _pipe = map; + return fold(_pipe, new$(), insert$1); +} + +export function filter(map, property) { + return do_filter(property, map); +} + +function do_keys_acc(loop$list, loop$acc) { + while (true) { + let list = loop$list; + let acc = loop$acc; + if (list.hasLength(0)) { + return reverse_and_concat(acc, toList([])); + } else if (list.atLeastLength(1)) { + let x = list.head; + let xs = list.tail; + loop$list = xs; + loop$acc = toList([x[0]], acc); + } else { + throw makeError( + "case_no_match", + "gleam/map", + 276, + "do_keys_acc", + "No case clause matched", + { values: [list] } + ); + } + } +} + +function do_keys(map) { + let list_of_pairs = (() => { + let _pipe = map; + return to_list(_pipe); + })(); + return do_keys_acc(list_of_pairs, toList([])); +} + +export function keys(map) { + return do_keys(map); +} + +function reverse_and_concat(loop$remaining, loop$accumulator) { + while (true) { + let remaining = loop$remaining; + let accumulator = loop$accumulator; + if (remaining.hasLength(0)) { + return accumulator; + } else if (remaining.atLeastLength(1)) { + let item = remaining.head; + let rest = remaining.tail; + loop$remaining = rest; + loop$accumulator = toList([item], accumulator); + } else { + throw makeError( + "case_no_match", + "gleam/map", + 269, + "reverse_and_concat", + "No case clause matched", + { values: [remaining] } + ); + } + } +} + +function do_values_acc(loop$list, loop$acc) { + while (true) { + let list = loop$list; + let acc = loop$acc; + if (list.hasLength(0)) { + return reverse_and_concat(acc, toList([])); + } else if (list.atLeastLength(1)) { + let x = list.head; + let xs = list.tail; + loop$list = xs; + loop$acc = toList([x[1]], acc); + } else { + throw makeError( + "case_no_match", + "gleam/map", + 314, + "do_values_acc", + "No case clause matched", + { values: [list] } + ); + } + } +} + +function do_values(map) { + let list_of_pairs = (() => { + let _pipe = map; + return to_list(_pipe); + })(); + return do_values_acc(list_of_pairs, toList([])); +} + +export function values(map) { + return do_values(map); +} + +function insert_taken(loop$map, loop$desired_keys, loop$acc) { + while (true) { + let map = loop$map; + let desired_keys = loop$desired_keys; + let acc = loop$acc; + let insert$1 = (taken, key) => { + let $ = get(map, key); + if ($.isOk()) { + let value = $[0]; + return insert(taken, key, value); + } else { + return taken; + } + }; + if (desired_keys.hasLength(0)) { + return acc; + } else if (desired_keys.atLeastLength(1)) { + let x = desired_keys.head; + let xs = desired_keys.tail; + loop$map = map; + loop$desired_keys = xs; + loop$acc = insert$1(acc, x); + } else { + throw makeError( + "case_no_match", + "gleam/map", + 411, + "insert_taken", + "No case clause matched", + { values: [desired_keys] } + ); + } + } +} + +function do_take(desired_keys, map) { + return insert_taken(map, desired_keys, new$()); +} + +export function take(map, desired_keys) { + return do_take(desired_keys, map); +} + +function fold_inserts(loop$new_entries, loop$map) { + while (true) { + let new_entries = loop$new_entries; + let map = loop$map; + if (new_entries.hasLength(0)) { + return map; + } else if (new_entries.atLeastLength(1)) { + let x = new_entries.head; + let xs = new_entries.tail; + loop$new_entries = xs; + loop$map = insert_pair(map, x); + } else { + throw makeError( + "case_no_match", + "gleam/map", + 451, + "fold_inserts", + "No case clause matched", + { values: [new_entries] } + ); + } + } +} + +function do_merge(map, new_entries) { + let _pipe = new_entries; + let _pipe$1 = to_list(_pipe); + return fold_inserts(_pipe$1, map); +} + +export function merge(map, new_entries) { + return do_merge(map, new_entries); +} + +export function drop(loop$map, loop$disallowed_keys) { + while (true) { + let map = loop$map; + let disallowed_keys = loop$disallowed_keys; + if (disallowed_keys.hasLength(0)) { + return map; + } else if (disallowed_keys.atLeastLength(1)) { + let x = disallowed_keys.head; + let xs = disallowed_keys.tail; + loop$map = delete$(map, x); + loop$disallowed_keys = xs; + } else { + throw makeError( + "case_no_match", + "gleam/map", + 514, + "drop", + "No case clause matched", + { values: [disallowed_keys] } + ); + } + } +} |