diff options
author | Jason Gross <jagro@google.com> | 2018-06-29 15:17:17 -0400 |
---|---|---|
committer | Jason Gross <jagro@google.com> | 2018-06-29 15:17:17 -0400 |
commit | 4976f80d2e630a41d8d278a103d4c64b9f841ee5 (patch) | |
tree | 0331c9b9966ab3f5c4adba7583807c7f496dbf78 /src/Util/ZUtil/Sorting.v | |
parent | 0d0a1ebe0bc221d99e3d9bcf3c72eee933320ab9 (diff) |
Add ZUtil.Sorting
Diffstat (limited to 'src/Util/ZUtil/Sorting.v')
-rw-r--r-- | src/Util/ZUtil/Sorting.v | 21 |
1 files changed, 21 insertions, 0 deletions
diff --git a/src/Util/ZUtil/Sorting.v b/src/Util/ZUtil/Sorting.v new file mode 100644 index 000000000..1f25ff80b --- /dev/null +++ b/src/Util/ZUtil/Sorting.v @@ -0,0 +1,21 @@ +Require Import Coq.ZArith.ZArith Coq.micromega.Lia. +Require Import Coq.Sorting.Mergesort Coq.Structures.Orders. + +Module Z. + Module Order <: TotalLeBool. + Definition t := Z. + Definition leb := Z.leb. + Infix "<=?" := leb. + Local Coercion is_true : bool >-> Sortclass. + Theorem leb_total : forall a1 a2, a1 <=? a2 \/ a2 <=? a1. + Proof. intros x y; destruct (Z.le_ge_cases x y); [ left | right ]; unfold is_true, leb; rewrite Z.leb_le; omega. Qed. + End Order. + + Module Sort := Mergesort.Sort Order. + + Notation sort := Sort.sort. + Notation Sorted_sort := Sort.Sorted_sort. + Notation LocallySorted_sort := Sort.LocallySorted_sort. + Notation StronglySorted_sort := Sort.StronglySorted_sort. + Notation Permuted_sort := Sort.Permuted_sort. +End Z. |