TdZdd  1.1
A top-down/breadth-first decision diagram manipulation framework
MyVector.hpp
1 /*
2  * TdZdd: a Top-down/Breadth-first Decision Diagram Manipulation Framework
3  * by Hiroaki Iwashita <iwashita@erato.ist.hokudai.ac.jp>
4  * Copyright (c) 2014 ERATO MINATO Project
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a
7  * copy of this software and associated documentation files (the "Software"),
8  * to deal in the Software without restriction, including without limitation
9  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  * and/or sell copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  * DEALINGS IN THE SOFTWARE.
23  */
24 
25 #pragma once
26 
27 #include <cassert>
28 #include <cstring>
29 #include <vector>
30 
31 namespace tdzdd {
32 
33 template<typename T, typename Size = size_t>
34 class MyVector {
35  Size capacity_;
36  Size size_;
37  T* array_;
38 
39  static T* allocate(Size n) {
40  return std::allocator<T>().allocate(n);
41  }
42 
43  static void deallocate(T* p, Size n) {
44  std::allocator<T>().deallocate(p, n);
45  }
46 
47  void ensureCapacity(Size capacity) {
48  if (capacity_ < capacity) {
49 // reserve(std::max(Size(16), capacity * 4));
50  reserve(capacity * 2);
51  }
52  }
53 
54  void moveElement(T& from, T& to) {
55  //new (&to) T(std::move(from));
56  new (&to) T(from);
57  from.~T();
58  }
59 
60 public:
61  MyVector()
62  : capacity_(0), size_(0), array_(0) {
63  }
64 
65  MyVector(Size n)
66  : capacity_(0), size_(0), array_(0) {
67  resize(n);
68  }
69 
70  MyVector(Size n, T const& val)
71  : capacity_(0), size_(0), array_(0) {
72  reserve(n);
73  for (Size i = 0; i < n; ++i) {
74  push_back(val);
75  }
76  }
77 
78 // template<typename ... Args>
79 // MyVector(Size n, Args const&... args)
80 // : capacity_(0), size_(0), array_(0) {
81 // resize(n, args...);
82 // }
83 
84 // MyVector(Size size, T&& val)
85 // : capacity_(0), size_(0), array_(0) {
86 // resize(size, std::move(val));
87 // }
88 
89  MyVector(MyVector const& o)
90  : capacity_(o.size_), size_(o.size_),
91  array_(capacity_ ? allocate(capacity_) : 0) {
92  for (Size i = 0; i < size_; ++i) {
93  new (array_ + i) T(o[i]);
94  }
95  }
96 
97  MyVector& operator=(MyVector const& o) {
98  resize(0);
99  reserve(o.size_);
100  size_ = o.size_;
101  for (Size i = 0; i < size_; ++i) {
102  new (array_ + i) T(o[i]);
103  }
104  return *this;
105  }
106 
107  template<typename U>
108  MyVector(std::vector<U> const& o)
109  : capacity_(o.size()), size_(o.size()), array_(allocate(capacity_)) {
110  for (Size i = 0; i < size_; ++i) {
111  new (array_ + i) T(o[i]);
112  }
113  }
114 
115  template<typename U>
116  MyVector& operator=(std::vector<U> const& o) {
117  resize(0);
118  reserve(o.size());
119  size_ = o.size();
120  for (Size i = 0; i < size_; ++i) {
121  new (array_ + i) T(o[i]);
122  }
123  return *this;
124  }
125 
126 // template<typename U>
127 // MyVector(MyVector<U> const& o)
128 // : capacity_(o.size_), size_(o.size_), array_(allocate(capacity_)) {
129 // for (Size i = 0; i < size_; ++i) {
130 // new (array_ + i) T(o[i]);
131 // }
132 // }
133 //
134 // template<typename U>
135 // MyVector& operator=(MyVector<U> const& o) {
136 // resize(0);
137 // reserve(o.size_);
138 // size_ = o.size_;
139 // for (Size i = 0; i < size_; ++i) {
140 // new (array_ + i) T(o[i]);
141 // }
142 // return *this;
143 // }
144 
145 // MyVector(MyVector&& o) {
146 // *this = std::move(o);
147 // }
148 
149 // MyVector & operator=(MyVector&& o) {
150 // throw std::runtime_error("!!!");
151 // capacity_ = o.capacity_;
152 // size_ = o.size_;
153 // array_ = o.array_;
154 // o.capacity_ = 0;
155 // o.size_ = 0;
156 // o.array_ = 0;
157 // return *this;
158 // }
159 
160  void swap(MyVector& o) {
161  std::swap(capacity_, o.capacity_);
162  std::swap(size_, o.size_);
163  std::swap(array_, o.array_);
164  }
165 
166  ~MyVector() {
167  clear();
168  }
169 
174  Size capacity() const {
175  return capacity_;
176  }
177 
182  Size size() const {
183  return size_;
184  }
185 
190  bool empty() const {
191  return size_ == 0;
192  }
193 
199  void reserve(Size capacity) {
200  if (capacity_ < capacity) {
201  T* tmp = allocate(capacity);
202  if (array_ != 0) {
203  assert(0 <= size_ && size_ <= capacity_);
204  for (Size i = 0; i < size_; ++i) {
205  moveElement(array_[i], tmp[i]);
206  }
207  deallocate(array_, capacity_);
208  }
209  array_ = tmp;
210  capacity_ = capacity;
211  }
212  }
213 
218  void init(Size n) {
219  while (0 < size_) {
220  array_[--size_].~T();
221  }
222  resize(n);
223  }
224 
230  void resize(Size n) {
231  assert(n >= 0);
232  if (n == 0) {
233  clear();
234  }
235  else if (capacity_ * 10 <= n * 11 && n <= capacity_) {
236  while (n < size_) {
237  array_[--size_].~T();
238  }
239 
240  while (size_ < n) {
241  new (array_ + size_++) T();
242  }
243  }
244  else {
245  while (n < size_) {
246  array_[--size_].~T();
247  }
248  assert(size_ <= n);
249 
250  T* tmp = allocate(n);
251  for (Size i = 0; i < size_; ++i) {
252  moveElement(array_[i], tmp[i]);
253  }
254 
255  while (size_ < n) {
256  new (tmp + size_++) T();
257  }
258 
259  deallocate(array_, capacity_);
260  array_ = tmp;
261  capacity_ = n;
262  }
263  }
264 
271  T* erase(T* first, T* last) {
272  assert(array_ <= first && first <= last && last <= array_ + size_);
273  Size newSize = size_ - (last - first);
274 
275  for (Size i = first - array_; i < newSize; ++i) {
276  array_[i] = last[i];
277  }
278 
279  while (newSize < size_) {
280  array_[--size_].~T();
281  }
282 
283  return first;
284  }
285 
290  void clear() {
291  if (array_ != 0) {
292  assert(capacity_ > 0);
293  while (size_ > 0) {
294  array_[--size_].~T();
295  }
296  deallocate(array_, capacity_);
297  array_ = 0;
298  }
299  capacity_ = 0;
300  }
301 
308  void push_back(T const& val) {
309  ensureCapacity(size_ + 1);
310  new (array_ + size_) T(val);
311  ++size_;
312  }
313 
317  void pop_back() {
318  if (size_ > 0) array_[--size_].~T();
319  }
320 
321 // /*
322 // * Adds an element constructed in place to the end of the array.
323 // * The array is automatically extended,
324 // * which may cause data move.
325 // * @param args arguments to element's constructor.
326 // */
327 // template<typename ... Args>
328 // void emplace_back(Args const&... args) {
329 // ensureCapacity(size_ + 1);
330 // new (array_ + size_) T(args...);
331 // ++size_;
332 // }
333 
338  T& back() {
339  assert(size_ >= 1);
340  return array_[size_ - 1];
341  }
342 
347  T const& back() const {
348  assert(size_ >= 1);
349  return array_[size_ - 1];
350  }
351 
357  T& operator[](Size i) {
358  assert(i < size_);
359  return array_[i];
360  }
361 
367  T const& operator[](Size i) const {
368  assert(i < size_);
369  return array_[i];
370  }
371 
376  T* data() const {
377  return array_;
378  }
379 
380  typedef T* iterator;
381  typedef T const* const_iterator;
382 
387  iterator begin() {
388  return array_;
389  }
390 
395  const_iterator begin() const {
396  return array_;
397  }
398 
403  iterator end() {
404  return array_ + size_;
405  }
406 
411  const_iterator end() const {
412  return array_ + size_;
413  }
414 
415  template<typename U>
416  class reverse_iterator_ {
417  U* ptr;
418 
419  public:
420  reverse_iterator_(U* ptr)
421  : ptr(ptr) {
422  }
423 
424  U& operator*() const {
425  return *ptr;
426  }
427 
428  U* operator->() const {
429  return ptr;
430  }
431 
432  reverse_iterator_& operator++() {
433  --ptr;
434  return *this;
435  }
436 
437  bool operator==(reverse_iterator_ const& o) const {
438  return ptr == o.ptr;
439  }
440 
441  bool operator!=(reverse_iterator_ const& o) const {
442  return ptr != o.ptr;
443  }
444  };
445 
446  typedef reverse_iterator_<T> reverse_iterator;
447  typedef reverse_iterator_<T const> const_reverse_iterator;
448 
453  reverse_iterator rbegin() {
454  return reverse_iterator(array_ + size_ - 1);
455  }
456 
461  const_reverse_iterator rbegin() const {
462  return const_reverse_iterator(array_ + size_ - 1);
463  }
464 
469  reverse_iterator rend() {
470  return reverse_iterator(array_ - 1);
471  }
472 
477  const_reverse_iterator rend() const {
478  return const_reverse_iterator(array_ - 1);
479  }
480 
485  iterator erase(iterator pos) {
486  assert(begin() <= pos && pos < end());
487  std::memmove(pos, pos + 1, end() - pos - 1);
488  return pos;
489  }
490 
495  size_t hash() const {
496  size_t h = size_;
497  for (Size i = 0; i < size_; ++i) {
498  h = h * 31 + array_[i].hash();
499  }
500  return h;
501  }
502 
508  bool operator==(MyVector const& o) const {
509  if (size_ != o.size_) return false;
510  for (Size i = 0; i < size_; ++i) {
511  if (!(array_[i] == o.array_[i])) return false;
512  }
513  return true;
514  }
515 
522  friend std::ostream& operator<<(std::ostream& os, MyVector const& o) {
523  bool cont = false;
524  os << "(";
525  for (T const* t = o.begin(); t != o.end(); ++t) {
526  if (cont) os << ",";
527  os << *t;
528  cont = true;
529  }
530  return os << ")";
531  }
532 };
533 
534 //template<typename T, typename Size>
535 //void swap(MyVector<T,Size>& v1, MyVector<T,Size>& v2) {
536 // v1.swap(v2);
537 //}
538 
539 //template<typename T, int dimension>
540 //struct MyMultiVector: public MyVector<MyMultiVector<T,dimension - 1> > {
541 // MyMultiVector() {
542 // }
543 //
544 // MyMultiVector(Size n)
545 // : MyVector<MyMultiVector<T,dimension - 1> >(n) {
546 // }
547 //};
548 //
549 //template<typename T>
550 //struct MyMultiVector<T,1> : public MyVector<T> {
551 // MyMultiVector() {
552 // }
553 //
554 // MyMultiVector(Size n)
555 // : MyVector<T>(n) {
556 // }
557 //};
558 
559 }// namespace tdzdd