Line data Source code
1 : /* GRAPHITE2 LICENSING
2 :
3 : Copyright 2010, SIL International
4 : All rights reserved.
5 :
6 : This library is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU Lesser General Public License as published
8 : by the Free Software Foundation; either version 2.1 of License, or
9 : (at your option) any later version.
10 :
11 : This program is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : Lesser General Public License for more details.
15 :
16 : You should also have received a copy of the GNU Lesser General Public
17 : License along with this library in the file named "LICENSE".
18 : If not, write to the Free Software Foundation, 51 Franklin Street,
19 : Suite 500, Boston, MA 02110-1335, USA or visit their web page on the
20 : internet at http://www.fsf.org/licenses/lgpl.html.
21 :
22 : Alternatively, the contents of this file may be used under the terms of the
23 : Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
24 : License, as published by the Free Software Foundation, either version 2
25 : of the License or (at your option) any later version.
26 : */
27 :
28 : // designed to have a limited subset of the std::vector api
29 : #pragma once
30 :
31 : #include <cstddef>
32 : #include <cassert>
33 : #include <cstring>
34 : #include <cstdlib>
35 : #include <new>
36 :
37 :
38 : namespace graphite2 {
39 :
40 : template <typename T>
41 : inline
42 0 : ptrdiff_t distance(T* first, T* last) { return last-first; }
43 :
44 :
45 : template <typename T>
46 : class Vector
47 : {
48 : T * m_first, *m_last, *m_end;
49 : public:
50 : typedef T & reference;
51 : typedef const T & const_reference;
52 : typedef T * iterator;
53 : typedef const T * const_iterator;
54 :
55 0 : Vector() : m_first(0), m_last(0), m_end(0) {}
56 0 : Vector(size_t n, const T& value = T()) : m_first(0), m_last(0), m_end(0) { insert(begin(), n, value); }
57 0 : Vector(const Vector<T> &rhs) : m_first(0), m_last(0), m_end(0) { insert(begin(), rhs.begin(), rhs.end()); }
58 : template <typename I>
59 : Vector(I first, const I last) : m_first(0), m_last(0), m_end(0) { insert(begin(), first, last); }
60 0 : ~Vector() { clear(); free(m_first); }
61 :
62 0 : iterator begin() { return m_first; }
63 0 : const_iterator begin() const { return m_first; }
64 :
65 0 : iterator end() { return m_last; }
66 0 : const_iterator end() const { return m_last; }
67 :
68 : bool empty() const { return m_first == m_last; }
69 0 : size_t size() const { return m_last - m_first; }
70 0 : size_t capacity() const{ return m_end - m_first; }
71 :
72 : void reserve(size_t n);
73 : void resize(size_t n, const T & v = T());
74 :
75 0 : reference front() { assert(size() > 0); return *begin(); }
76 : const_reference front() const { assert(size() > 0); return *begin(); }
77 : reference back() { assert(size() > 0); return *(end()-1); }
78 : const_reference back() const { assert(size() > 0); return *(end()-1); }
79 :
80 : Vector<T> & operator = (const Vector<T> & rhs) { assign(rhs.begin(), rhs.end()); return *this; }
81 0 : reference operator [] (size_t n) { assert(size() > n); return m_first[n]; }
82 0 : const_reference operator [] (size_t n) const { assert(size() > n); return m_first[n]; }
83 :
84 : void assign(size_t n, const T& u) { clear(); insert(begin(), n, u); }
85 : void assign(const_iterator first, const_iterator last) { clear(); insert(begin(), first, last); }
86 0 : iterator insert(iterator p, const T & x) { p = _insert_default(p, 1); new (p) T(x); return p; }
87 : void insert(iterator p, size_t n, const T & x);
88 : void insert(iterator p, const_iterator first, const_iterator last);
89 0 : void pop_back() { assert(size() > 0); --m_last; }
90 0 : void push_back(const T &v) { if (m_last == m_end) reserve(size()+1); new (m_last++) T(v); }
91 :
92 0 : void clear() { erase(begin(), end()); }
93 0 : iterator erase(iterator p) { return erase(p, p+1); }
94 : iterator erase(iterator first, iterator last);
95 :
96 : private:
97 : iterator _insert_default(iterator p, size_t n);
98 : };
99 :
100 : template <typename T>
101 : inline
102 0 : void Vector<T>::reserve(size_t n)
103 : {
104 0 : if (n > capacity())
105 : {
106 0 : const ptrdiff_t sz = size();
107 0 : m_first = static_cast<T*>(realloc(m_first, n*sizeof(T)));
108 0 : if (!m_first) std::abort();
109 0 : m_last = m_first + sz;
110 0 : m_end = m_first + n;
111 : }
112 0 : }
113 :
114 : template <typename T>
115 : inline
116 0 : void Vector<T>::resize(size_t n, const T & v) {
117 0 : const ptrdiff_t d = n-size();
118 0 : if (d < 0) erase(end()+d, end());
119 0 : else if (d > 0) insert(end(), d, v);
120 0 : }
121 :
122 : template<typename T>
123 : inline
124 0 : typename Vector<T>::iterator Vector<T>::_insert_default(iterator p, size_t n)
125 : {
126 0 : assert(begin() <= p && p <= end());
127 0 : const ptrdiff_t i = p - begin();
128 0 : reserve(((size() + n + 7) >> 3) << 3);
129 0 : p = begin() + i;
130 : // Move tail if there is one
131 0 : if (p != end()) memmove(p + n, p, distance(p,end())*sizeof(T));
132 0 : m_last += n;
133 0 : return p;
134 : }
135 :
136 : template<typename T>
137 : inline
138 0 : void Vector<T>::insert(iterator p, size_t n, const T & x)
139 : {
140 0 : p = _insert_default(p, n);
141 : // Copy in elements
142 0 : for (; n; --n, ++p) { new (p) T(x); }
143 0 : }
144 :
145 : template<typename T>
146 : inline
147 0 : void Vector<T>::insert(iterator p, const_iterator first, const_iterator last)
148 : {
149 0 : p = _insert_default(p, distance(first, last));
150 : // Copy in elements
151 0 : for (;first != last; ++first, ++p) { new (p) T(*first); }
152 0 : }
153 :
154 : template<typename T>
155 : inline
156 0 : typename Vector<T>::iterator Vector<T>::erase(iterator first, iterator last)
157 : {
158 0 : for (iterator e = first; e != last; ++e) e->~T();
159 0 : const size_t sz = distance(first, last);
160 0 : if (m_last != last) memmove(first, last, distance(last,end())*sizeof(T));
161 0 : m_last -= sz;
162 0 : return first;
163 : }
164 :
165 : } // namespace graphite2
|
