| 1 | include "basics/types.ma". |
|---|
| 2 | include "basics/lists/list.ma". |
|---|
| 3 | include "arithmetics/nat.ma". |
|---|
| 4 | include "common/Integers.ma". |
|---|
| 5 | |
|---|
| 6 | include "ASM/Util.ma". |
|---|
| 7 | |
|---|
| 8 | axiom priority_set: Type[0] → Type[0]. |
|---|
| 9 | |
|---|
| 10 | axiom pset_empty: ∀elt_type. priority_set elt_type. |
|---|
| 11 | axiom pset_size: ∀elt_type. priority_set elt_type → nat. |
|---|
| 12 | |
|---|
| 13 | axiom pset_to_list: ∀elt_type. priority_set elt_type → list (elt_type × nat). |
|---|
| 14 | |
|---|
| 15 | axiom pset_insert: ∀elt_type. elt_type → nat → priority_set elt_type → priority_set elt_type. |
|---|
| 16 | axiom pset_remove: ∀elt_type. elt_type → priority_set elt_type → priority_set elt_type. |
|---|
| 17 | axiom pset_lookup: ∀elt_type. elt_type → priority_set elt_type → option nat. |
|---|
| 18 | |
|---|
| 19 | axiom pset_increment: ∀elt_type. elt_type → int → priority_set elt_type → priority_set elt_type. |
|---|
| 20 | axiom pset_incrementifx: ∀elt_type. elt_type → int → priority_set elt_type → priority_set elt_type. |
|---|
| 21 | axiom pset_modify: ∀elt_type. elt_type → int → priority_set elt_type → priority_set elt_type. |
|---|
| 22 | axiom pset_lowest: ∀elt_type. priority_set elt_type → option (elt_type × nat). |
|---|
| 23 | |
|---|
| 24 | axiom pset_equal: ∀elt_type. priority_set elt_type → priority_set elt_type → bool. |
|---|
| 25 | |
|---|
| 26 | axiom pset_map: ∀elt_type. ∀a: Type[0]. (elt_type → a) → priority_set elt_type → priority_set a. |
|---|
| 27 | axiom pset_fold: ∀elt_type. ∀a: Type[0]. (elt_type → int → a → a) → priority_set elt_type → a → a. |
|---|
| 28 | |
|---|
| 29 | definition pset_is_empty ≝ |
|---|
| 30 | λelt_type : Type[0]. |
|---|
| 31 | λpriority_set : priority_set elt_type. |
|---|
| 32 | pset_size … priority_set = 0. |
|---|
| 33 | |
|---|
| 34 | definition pset_singleton ≝ |
|---|
| 35 | λelt_type : Type[0]. |
|---|
| 36 | λelt : elt_type. |
|---|
| 37 | λpriority : nat. |
|---|
| 38 | pset_insert … elt priority (pset_empty elt_type). |
|---|
| 39 | |
|---|
| 40 | definition pset_from_list ≝ |
|---|
| 41 | λelt_type : Type[0]. |
|---|
| 42 | λthe_list : list (elt_type × nat). |
|---|
| 43 | foldr … (λelt_priority. |
|---|
| 44 | let 〈elt, priority〉 ≝ elt_priority in |
|---|
| 45 | pset_insert elt_type elt priority) |
|---|
| 46 | (pset_empty …) the_list. |
|---|
