1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 (* This file was automatically generated: do not edit *********************)
19 (*#***********************************************************************)
21 (* v * The Coq Proof Assistant / The Coq Development Team *)
23 (* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
25 (* \VV/ **************************************************************)
27 (* // * This file is distributed under the terms of the *)
29 (* * GNU Lesser General Public License Version 2.1 *)
31 (*#***********************************************************************)
33 (*i $Id: Heap.v,v 1.3.2.1 2004/07/16 19:31:19 herbelin Exp $ i*)
35 (*#* A development of Treesort on Heap trees *)
37 (* G. Huet 1-9-95 uses Multiset *)
39 include "Lists/List.ma".
41 include "Sets/Multiset.ma".
43 include "Sorting/Permutation.ma".
45 include "Relations/Relations.ma".
47 include "Sorting/Sorting.ma".
54 cic:/Coq/Sorting/Heap/defs/A.var
58 cic:/Coq/Sorting/Heap/defs/leA.var
62 cic:/Coq/Sorting/Heap/defs/eqA.var
65 (* UNAVAILABLE OBJECT: cic:/Coq/Sorting/Heap/defs/gtA.con *****************)
67 inline procedural "cic:/Coq/Sorting/Heap/defs/gtA.con" "defs__" as definition.
70 cic:/Coq/Sorting/Heap/defs/leA_dec.var
74 cic:/Coq/Sorting/Heap/defs/eqA_dec.var
78 cic:/Coq/Sorting/Heap/defs/leA_refl.var
82 cic:/Coq/Sorting/Heap/defs/leA_trans.var
86 cic:/Coq/Sorting/Heap/defs/leA_antisym.var
90 Hint Resolve leA_refl.
94 Hint Immediate eqA_dec leA_dec leA_antisym.
97 (* UNAVAILABLE OBJECT: cic:/Coq/Sorting/Heap/defs/emptyBag.con ************)
99 inline procedural "cic:/Coq/Sorting/Heap/defs/emptyBag.con" "defs__" as definition.
101 (* UNAVAILABLE OBJECT: cic:/Coq/Sorting/Heap/defs/singletonBag.con ********)
103 inline procedural "cic:/Coq/Sorting/Heap/defs/singletonBag.con" "defs__" as definition.
105 inline procedural "cic:/Coq/Sorting/Heap/Tree.ind".
107 (*#* [a] is lower than a Tree [T] if [T] is a Leaf
108 or [T] is a Node holding [b>a] *)
110 inline procedural "cic:/Coq/Sorting/Heap/leA_Tree.con" as definition.
112 inline procedural "cic:/Coq/Sorting/Heap/leA_Tree_Leaf.con" as lemma.
114 inline procedural "cic:/Coq/Sorting/Heap/leA_Tree_Node.con" as lemma.
117 Hint Resolve leA_Tree_Leaf leA_Tree_Node.
120 (*#* The heap property *)
122 inline procedural "cic:/Coq/Sorting/Heap/is_heap.ind".
125 Hint Constructors is_heap.
128 inline procedural "cic:/Coq/Sorting/Heap/invert_heap.con" as lemma.
130 (* This lemma ought to be generated automatically by the Inversion tools *)
132 inline procedural "cic:/Coq/Sorting/Heap/is_heap_rec.con" as lemma.
134 inline procedural "cic:/Coq/Sorting/Heap/low_trans.con" as lemma.
136 (*#* contents of a tree as a multiset *)
138 (*#* Nota Bene : In what follows the definition of SingletonBag
139 in not used. Actually, we could just take as postulate:
140 [Parameter SingletonBag : A->multiset]. *)
142 inline procedural "cic:/Coq/Sorting/Heap/contents.con" as definition.
144 (*#* equivalence of two trees is equality of corresponding multisets *)
146 inline procedural "cic:/Coq/Sorting/Heap/equiv_Tree.con" as definition.
148 (*#* specification of heap insertion *)
150 inline procedural "cic:/Coq/Sorting/Heap/insert_spec.ind".
152 inline procedural "cic:/Coq/Sorting/Heap/insert.con" as lemma.
154 (*#* building a heap from a list *)
156 inline procedural "cic:/Coq/Sorting/Heap/build_heap.ind".
158 inline procedural "cic:/Coq/Sorting/Heap/list_to_heap.con" as lemma.
160 (*#* building the sorted list *)
162 inline procedural "cic:/Coq/Sorting/Heap/flat_spec.ind".
164 inline procedural "cic:/Coq/Sorting/Heap/heap_to_list.con" as lemma.
166 (*#* specification of treesort *)
168 inline procedural "cic:/Coq/Sorting/Heap/treesort.con" as theorem.