-
Notifications
You must be signed in to change notification settings - Fork 84
/
Basic.lean
207 lines (179 loc) · 6.64 KB
/
Basic.lean
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
/-
Copyright (c) 2021 Floris van Doorn. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Arthur Paulino, Floris van Doorn, Jannis Limperg
-/
import Batteries.Data.List.Init.Attach
import Batteries.Data.Array.Init.Lemmas
/-!
## Definitions on Arrays
This file contains various definitions on `Array`. It does not contain
proofs about these definitions, those are contained in other files in `Batteries.Data.Array`.
-/
namespace Array
/-- Drop `none`s from a Array, and replace each remaining `some a` with `a`. -/
def reduceOption (l : Array (Option α)) : Array α :=
l.filterMap id
/--
Check whether `xs` and `ys` are equal as sets, i.e. they contain the same
elements when disregarding order and duplicates. `O(n*m)`! If your element type
has an `Ord` instance, it is asymptotically more efficient to sort the two
arrays, remove duplicates and then compare them elementwise.
-/
def equalSet [BEq α] (xs ys : Array α) : Bool :=
xs.all (ys.contains ·) && ys.all (xs.contains ·)
set_option linter.unusedVariables.funArgs false in
/--
Sort an array using `compare` to compare elements.
-/
def qsortOrd [ord : Ord α] (xs : Array α) : Array α :=
xs.qsort fun x y => compare x y |>.isLT
set_option linter.unusedVariables.funArgs false in
/--
Returns the first minimal element among `d` and elements of the array.
If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered (in addition to `d`).
-/
@[inline]
protected def minWith [ord : Ord α]
(xs : Array α) (d : α) (start := 0) (stop := xs.size) : α :=
xs.foldl (init := d) (start := start) (stop := stop) fun min x =>
if compare x min |>.isLT then x else min
set_option linter.unusedVariables.funArgs false in
/--
Find the first minimal element of an array. If the array is empty, `d` is
returned. If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered.
-/
@[inline]
protected def minD [ord : Ord α]
(xs : Array α) (d : α) (start := 0) (stop := xs.size) : α :=
if h: start < xs.size ∧ start < stop then
xs.minWith (xs.get ⟨start, h.left⟩) (start + 1) stop
else
d
set_option linter.unusedVariables.funArgs false in
/--
Find the first minimal element of an array. If the array is empty, `none` is
returned. If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered.
-/
@[inline]
protected def min? [ord : Ord α]
(xs : Array α) (start := 0) (stop := xs.size) : Option α :=
if h : start < xs.size ∧ start < stop then
some $ xs.minD (xs.get ⟨start, h.left⟩) start stop
else
none
set_option linter.unusedVariables.funArgs false in
/--
Find the first minimal element of an array. If the array is empty, `default` is
returned. If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered.
-/
@[inline]
protected def minI [ord : Ord α] [Inhabited α]
(xs : Array α) (start := 0) (stop := xs.size) : α :=
xs.minD default start stop
set_option linter.unusedVariables.funArgs false in
/--
Returns the first maximal element among `d` and elements of the array.
If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered (in addition to `d`).
-/
@[inline]
protected def maxWith [ord : Ord α]
(xs : Array α) (d : α) (start := 0) (stop := xs.size) : α :=
xs.minWith (ord := ord.opposite) d start stop
set_option linter.unusedVariables.funArgs false in
/--
Find the first maximal element of an array. If the array is empty, `d` is
returned. If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered.
-/
@[inline]
protected def maxD [ord : Ord α]
(xs : Array α) (d : α) (start := 0) (stop := xs.size) : α :=
xs.minD (ord := ord.opposite) d start stop
set_option linter.unusedVariables.funArgs false in
/--
Find the first maximal element of an array. If the array is empty, `none` is
returned. If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered.
-/
@[inline]
protected def max? [ord : Ord α]
(xs : Array α) (start := 0) (stop := xs.size) : Option α :=
xs.min? (ord := ord.opposite) start stop
set_option linter.unusedVariables.funArgs false in
/--
Find the first maximal element of an array. If the array is empty, `default` is
returned. If `start` and `stop` are given, only the subarray `xs[start:stop]` is
considered.
-/
@[inline]
protected def maxI [ord : Ord α] [Inhabited α]
(xs : Array α) (start := 0) (stop := xs.size) : α :=
xs.minI (ord := ord.opposite) start stop
/--
Unsafe implementation of `attachWith`, taking advantage of the fact that the representation of
`Array {x // P x}` is the same as the input `Array α`.
-/
@[inline] private unsafe def attachWithImpl
(xs : Array α) (P : α → Prop) (_ : ∀ x ∈ xs, P x) : Array {x // P x} := unsafeCast xs
/-- `O(1)`. "Attach" a proof `P x` that holds for all the elements of `xs` to produce a new array
with the same elements but in the type `{x // P x}`. -/
@[implemented_by attachWithImpl] def attachWith
(xs : Array α) (P : α → Prop) (H : ∀ x ∈ xs, P x) : Array {x // P x} :=
⟨xs.data.attachWith P fun x h => H x (Array.Mem.mk h)⟩
/-- `O(1)`. "Attach" the proof that the elements of `xs` are in `xs` to produce a new array
with the same elements but in the type `{x // x ∈ xs}`. -/
@[inline] def attach (xs : Array α) : Array {x // x ∈ xs} := xs.attachWith _ fun _ => id
/--
`O(|join L|)`. `join L` concatenates all the arrays in `L` into one array.
* `join #[#[a], #[], #[b, c], #[d, e, f]] = #[a, b, c, d, e, f]`
-/
@[inline] def join (l : Array (Array α)) : Array α := l.foldl (· ++ ·) #[]
end Array
namespace Subarray
/--
The empty subarray.
-/
protected def empty : Subarray α where
array := #[]
start := 0
stop := 0
start_le_stop := Nat.le_refl 0
stop_le_array_size := Nat.le_refl 0
instance : EmptyCollection (Subarray α) :=
⟨Subarray.empty⟩
instance : Inhabited (Subarray α) :=
⟨{}⟩
/--
Check whether a subarray is empty.
-/
@[inline]
def isEmpty (as : Subarray α) : Bool :=
as.start == as.stop
/--
Check whether a subarray contains an element.
-/
@[inline]
def contains [BEq α] (as : Subarray α) (a : α) : Bool :=
as.any (· == a)
/--
Remove the first element of a subarray. Returns the element and the remaining
subarray, or `none` if the subarray is empty.
-/
def popHead? (as : Subarray α) : Option (α × Subarray α) :=
if h : as.start < as.stop
then
let head := as.array.get ⟨as.start, Nat.lt_of_lt_of_le h as.stop_le_array_size⟩
let tail :=
{ as with
start := as.start + 1
start_le_stop := Nat.le_of_lt_succ $ Nat.succ_lt_succ h }
some (head, tail)
else
none
end Subarray