1use std::fmt;
2use std::hash::{Hash, Hasher};
3use std::mem::{MaybeUninit, size_of};
4use std::ptr::{read, drop_in_place};
5use std::ops::{Deref, DerefMut};
6use std::slice::{self, from_raw_parts, from_raw_parts_mut};
7use std::iter::FromIterator;
8use crate::vector::Vector;
9use crate::array::{Array, ArrayIndex};
10use crate::util::PointerExt;
11
12pub struct ArrayVec<T: Array> {
13 array: MaybeUninit<T>,
14 len: T::Index,
15}
16
17impl<T: Array> fmt::Debug for ArrayVec<T> where T::Item: fmt::Debug {
18 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
19 fmt::Debug::fmt(&self[..], fmt)
20 }
21}
22
23impl<T: Array> Hash for ArrayVec<T> where T::Item: Hash {
24 fn hash<H: Hasher>(&self, h: &mut H) {
25 self[..].hash(h)
26 }
27}
28
29impl<T: Array> ArrayVec<T> {
30 pub fn into_inner(mut self) -> Result<T, Self> {
31 if self.len() == self.capacity() {
32 self.len = Default::default();
33 Ok(unsafe { read(self.array.as_ptr()) })
34 } else {
35 Err(self)
36 }
37 }
38}
39
40unsafe impl<T: Array> Vector for ArrayVec<T> {
41 type Item = T::Item;
42
43 #[inline]
44 fn with_capacity(cap: usize) -> Self {
45 assert!(cap <= T::len());
46
47 ArrayVec {
48 array: MaybeUninit::uninit(),
49 len: Default::default(),
50 }
51 }
52
53 #[inline]
54 fn capacity(&self) -> usize { T::len() }
55 #[inline]
56 fn reserve(&mut self, additional: usize) { self.reserve_exact(additional); }
57 #[inline]
58 fn reserve_exact(&mut self, additional: usize) { assert!(T::len() - self.len() >= additional) }
59 #[inline]
60 fn shrink_to_fit(&mut self) { }
61
62 fn into_boxed_slice(self) -> Box<[T::Item]> { unimplemented!() }
63
64 #[inline]
65 unsafe fn set_len(&mut self, len: usize) { self.len = ArrayIndex::from_usize(len); }
66
67 #[inline]
68 fn len(&self) -> usize { ArrayIndex::to_usize(self.len) }
69
70 #[inline]
71 fn as_ptr(&self) -> *const T::Item {
72 Array::as_uninit(&self.array).as_ptr() as *const _
73 }
74
75 #[inline]
76 fn as_mut_ptr(&mut self) -> *mut T::Item {
77 Array::as_uninit_mut(&mut self.array).as_mut_ptr() as *mut _
78 }
79}
80
81impl<T: Array> Drop for ArrayVec<T> {
82 fn drop(&mut self) {
83 let len = ArrayIndex::to_usize(self.len);
84 if len > 0 {
85 let ptr = Array::as_uninit_mut(&mut self.array).as_mut_ptr() as *mut T::Item;
86
87 unsafe {
88 self.set_len(0);
89 for i in 0..len {
90 drop_in_place(ptr.uoffset(i));
91 }
92 }
93 }
94 }
95}
96
97impl<T: Array> From<T> for ArrayVec<T> {
98 fn from(array: T) -> Self {
99 ArrayVec {
100 array: MaybeUninit::new(array),
101 len: ArrayIndex::from_usize(T::len()),
102 }
103 }
104}
105
106pub struct ArrayVecIntoIter<T: Array> {
107 inner: ArrayVec<T>,
108 start: T::Index,
109 end: T::Index,
110}
111
112impl<T: Array> ArrayVecIntoIter<T> {
113 fn new(mut inner: ArrayVec<T>) -> Self {
114 let (start, end) = unsafe {
115 let len = inner.len();
116 inner.set_len(0);
117 (ArrayIndex::from_usize(0), ArrayIndex::from_usize(len))
118 };
119
120 ArrayVecIntoIter {
121 inner,
122 start,
123 end,
124 }
125 }
126
127 fn ptr_size() -> usize {
128 let size = size_of::<<Self as Iterator>::Item>();
129 if size == 0 {
130 1
131 } else {
132 size
133 }
134 }
135
136 fn ptr(&mut self, index: T::Index) -> *mut <Self as Iterator>::Item {
137 (self.inner.as_mut_ptr() as usize + ArrayIndex::to_usize(index) * Self::ptr_size()) as *mut _
138 }
139}
140
141impl<T: Array> Iterator for ArrayVecIntoIter<T> {
142 type Item = <ArrayVec<T> as Vector>::Item;
143
144 fn next(&mut self) -> Option<Self::Item> {
145 if self.start < self.end {
146 unsafe {
147 let start = self.start;
148 self.start = ArrayIndex::from_usize(ArrayIndex::to_usize(start) + 1);
149 Some(read(self.ptr(start)))
150 }
151 } else {
152 None
153 }
154 }
155
156 #[inline]
157 fn size_hint(&self) -> (usize, Option<usize>) {
158 let len = ArrayIndex::to_usize(self.end) - ArrayIndex::to_usize(self.start);
159 (len, Some(len))
160 }
161
162 #[inline]
163 fn count(self) -> usize {
164 self.size_hint().0
165 }
166}
167
168impl<T: Array> DoubleEndedIterator for ArrayVecIntoIter<T> {
169 fn next_back(&mut self) -> Option<Self::Item> {
170 if self.start < self.end {
171 unsafe {
172 self.end = ArrayIndex::from_usize(ArrayIndex::to_usize(self.end) - 1);
173 let end = self.end;
174 Some(read(self.ptr(end)))
175 }
176 } else {
177 None
178 }
179 }
180}
181
182impl<T: Array> ExactSizeIterator for ArrayVecIntoIter<T> { }
183
184impl<T: Array> IntoIterator for ArrayVec<T> {
185 type Item = T::Item;
186 type IntoIter = ArrayVecIntoIter<T>;
187
188 #[inline]
189 fn into_iter(self) -> Self::IntoIter {
190 ArrayVecIntoIter::new(self)
191 }
192}
193
194impl<T: Array, R, RHS: Deref<Target=[R]>> PartialEq<RHS> for ArrayVec<T> where T::Item: PartialEq<R>
195{
196 fn eq(&self, other: &RHS) -> bool {
197 **self == *other.deref()
198 }
199}
200
201impl<T: Array> Eq for ArrayVec<T> where T::Item: Eq { }
202
203impl<T: Array> Drop for ArrayVecIntoIter<T> {
204 fn drop(&mut self) {
205 for _ in self { }
206 }
207}
208
209impl<T: Array> Clone for ArrayVec<T> where T::Item: Clone {
210 fn clone(&self) -> Self {
211 self.iter().cloned().collect()
212 }
213}
214
215impl<T: Array> Default for ArrayVec<T> {
216 fn default() -> Self {
217 Self::new()
218 }
219}
220
221impl<T: Array> Extend<T::Item> for ArrayVec<T> {
222 fn extend<I: IntoIterator<Item=T::Item>>(&mut self, iter: I) {
223 let iter = iter.into_iter();
224 self.reserve(iter.size_hint().0);
225 for v in iter {
226 self.push(v);
227 }
228 }
229}
230
231impl<T: Array> FromIterator<T::Item> for ArrayVec<T> {
232 fn from_iter<I: IntoIterator<Item=T::Item>>(iter: I) -> Self {
233 let mut s = Self::new();
234 s.extend(iter);
235 s
236 }
237}
238
239impl<'a, T: Array> IntoIterator for &'a ArrayVec<T> {
240 type Item = &'a T::Item;
241 type IntoIter = slice::Iter<'a, T::Item>;
242
243 #[inline]
244 fn into_iter(self) -> Self::IntoIter {
245 self.iter()
246 }
247}
248
249impl<'a, T: Array> IntoIterator for &'a mut ArrayVec<T> {
250 type Item = &'a mut T::Item;
251 type IntoIter = slice::IterMut<'a, T::Item>;
252
253 #[inline]
254 fn into_iter(self) -> Self::IntoIter {
255 self.iter_mut()
256 }
257}
258
259impl<T: Array> Deref for ArrayVec<T> {
260 type Target = [T::Item];
261
262 fn deref(&self) -> &Self::Target {
263 unsafe { from_raw_parts(Array::as_uninit(&self.array).as_ptr() as *const _, ArrayIndex::to_usize(self.len)) }
264 }
265}
266
267impl<T: Array> DerefMut for ArrayVec<T> {
268 fn deref_mut(&mut self) -> &mut Self::Target {
269 unsafe { from_raw_parts_mut(Array::as_uninit_mut(&mut self.array).as_mut_ptr() as *mut _, ArrayIndex::to_usize(self.len)) }
270 }
271}