3 * - By John Hodge (thePowersGang)
11 #include "_libcxx_helpers.h"
16 #include <functional> // less
22 template <class Val, class Map>
24 public ::std::iterator< ::std::bidirectional_iterator_tag, Val >
27 typedef Val value_type;
35 map_iterator(Map *map, typename Map::size_type ofs):
36 m_map(map), m_index(ofs)
39 map_iterator(const map_iterator& x) {
42 map_iterator& operator=(const map_iterator& x) {
48 map_iterator& operator++() {
51 map_iterator& operator--() {
55 bool operator==(const map_iterator& x) const {
56 return m_index == x.m_index;
58 bool operator!=(const map_iterator& x) const {
61 value_type& operator*() {
62 _libcxx_assert(m_index < m_map->m_size);
63 return m_map->m_items[m_index];
65 value_type* operator->() {
66 _libcxx_assert(m_index < m_map->m_size);
67 return &m_map->m_items[m_index];
73 template <class Key, class T, class Compare=less<Key>, class Alloc=allocator<pair<const Key,T> > >
76 typedef map this_type;
79 typedef T mapped_type;
80 typedef pair<const Key, T> value_type;
81 typedef Compare key_compare;
82 typedef Alloc allocator_type;
83 typedef typename allocator_type::reference reference;
84 typedef typename allocator_type::const_reference const_reference;
85 typedef typename allocator_type::pointer pointer;
86 typedef typename allocator_type::const_pointer const_pointer;
87 typedef _bits::map_iterator<value_type,this_type> iterator;
88 typedef _bits::map_iterator<const value_type,this_type> const_iterator;
89 typedef size_t size_type;
92 friend class ::std::_bits::map_iterator<value_type, this_type>;
93 friend class ::std::_bits::map_iterator<const value_type, this_type>;
96 allocator_type m_alloc;
97 value_type* m_items; // sorted array
102 map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()):
105 m_items(0), m_size(0), m_capacity(0)
108 template <class InputInterator>
109 map(InputInterator first, InputInterator last):
115 map(x.m_comp, x.m_alloc)
123 map& operator=(const map& x) {
126 for( size_type i = 0; i < x.m_size; i ++ ) {
127 emplace_hint( end(), x.m_items[i] );
134 return iterator(this, 0);
136 const_iterator begin() const {
137 return const_iterator(this, 0);
140 return iterator(this, m_size);
142 const_iterator end() const {
143 return const_iterator(this, m_size);
146 const_iterator cbegin() const {
147 return const_iterator(this, 0);
149 const_iterator cend() const {
150 return const_iterator(this, m_size);
153 //reverse_iterator rbegin();
154 //const_reverse_iterator rbegin() const;
155 //const_reverse_iterator crbegin() const;
156 //reverse_iterator rend();
157 //const reverse_iterator rend() const;
158 //const reverse_iterator crend() const;
164 size_type size() const {
167 size_type max_size() const {
168 return (size_type)-1 / sizeof(value_type);
172 mapped_type& operator[](const key_type& k) {
173 iterator it = upper_bound(k);
174 if( it == end() || m_comp(k, it->first) ) { // if k < it->first, no match
175 insert_at(it.m_index, value_type(k,mapped_type()) );
180 mapped_type& at(const key_type& k) {
181 iterator it = lower_bound(k);
182 if( it == end() || m_comp(it->first, k) )
183 throw ::std::out_of_range("::std:map::at");
186 const mapped_type& at(const key_type& k) const {
187 iterator it = lower_bound(k);
188 if( it == end() || m_comp(it->first, k) )
189 throw ::std::out_of_range("::std:map::at");
196 pair<iterator,bool> insert(const value_type& val)
198 const key_type& k = val.first;
199 iterator it = upper_bound(k);
200 if( it == end() || m_comp(k, it->first) ) { // if k < it->first, no match
201 insert_at(it.m_index, val);
202 return pair<iterator,bool>(it, true);
205 return pair<iterator,bool>(it, false);
208 iterator insert(iterator position, const value_type& val);
209 template <class InputInterator>
210 void insert(InputInterator first, InputInterator last);
212 void erase(iterator position)
215 erase(pos, ++position);
217 size_type erase(const key_type& k)
228 void erase(iterator first, iterator last)
230 _libcxx_assert(first.m_index <= last.m_index);
231 unsigned int ofs = first.m_index;
232 unsigned int count = last.m_index - first.m_index;
233 for( unsigned int i = 0; i < count; i ++ )
235 // Construct new item
236 m_alloc.destroy(&m_items[ofs]);
238 // Move following items down
239 shift_items(&m_items[ofs+1], &m_items[ofs], m_size-ofs);
246 for( size_type i = 0; i < m_size; i ++ ) {
247 m_alloc.destroy( &m_items[i] );
253 template <class... Args>
254 pair<iterator,bool> emplace(Args&&... args) {
255 return emplace_hint(begin(), args...);
257 template <class... Args>
258 pair<iterator,bool> emplace_hint(iterator position, Args&&... args);
264 iterator find(const key_type& k) {
265 iterator it = lower_bound(k);
266 if( it == end() || m_comp(it->first, k) ) // if it->first < k
270 const_iterator find(const key_type& k) const {
271 const_iterator it = lower_bound(k);
272 if( it == end() || m_comp(it->first, k) ) // if it->first < k
276 size_type count(const key_type& k) {
277 if( find(k) == end() )
281 iterator lower_bound(const key_type& k) {
283 if( _search(k, idx) ) {
284 // found, return direct iterator
285 return iterator(this, idx);
288 // not found, return iterator to before
289 if( idx == 0 ) return begin();
290 return iterator(this, idx-1);
293 const_iterator lower_bound(const key_type& k) const {
295 if( _search(k, idx) ) {
296 // found, return direct iterator
297 return iterator(this, idx);
300 // not found, return iterator to before
301 if( idx == 0 ) return begin();
302 return iterator(this, idx-1);
305 iterator upper_bound(const key_type& k) {
308 // idx == item or just after it
309 return iterator(this, idx);
311 const_iterator upper_bound(const key_type& k) const {
314 return const_iterator(this, idx);
316 pair<iterator,iterator> equal_range(const key_type& k);
317 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
320 // Change reservation to fit 'n' items
321 // - NOTE: Will also resize down
322 void reserve(size_type n) {
325 throw ::std::length_error("::std::map::reserve");
326 if( n != m_capacity )
328 auto new_area = m_alloc.allocate(n);
329 for( size_type i = 0; i < m_size && i < n; i ++ )
330 m_alloc.construct(&new_area[i], m_items[i]);
331 for( size_type i = n; i < m_size; i ++ )
332 m_alloc.destroy( &m_items[i] );
333 m_alloc.deallocate(m_items, m_capacity);
340 // Returns the index above or equal to 'k'
341 // - TODO: Reimplement as a binary search
342 bool _search(const key_type& k, size_type &pos_out) const {
344 size_type pos = m_size / 2;
345 size_type step = m_size / 4;
347 const key_type& item_key = m_items[pos].first;
348 if( m_comp(item_key, k) )
350 else if( m_comp(k, item_key) )
361 //::_sys::debug("map::_search (m_size=%i)", m_size);
362 for( size_type pos = 0; pos < m_size; pos ++ )
364 const key_type& item_key = m_items[pos].first;
365 if( m_comp(item_key, k) ) {
368 else if( m_comp(k, item_key) ) {
369 //::_sys::debug("map::_search - Passed %i", pos);
374 //::_sys::debug("map::_search - Found %i", pos);
379 //::_sys::debug("map::_search - Off end %i", m_size);
384 void insert_at(size_type ofs, const value_type& val) {
385 //_libcxx_assert( ofs == 0 || m_comp(m_items[ofs-1].first, val.first) );
386 //_libcxx_assert( ofs == m_size || m_comp(m_items[ofs].first, val.first) );
388 reserve( m_size + 1 );
389 // Move following items up
390 shift_items(&m_items[ofs], &m_items[ofs+1], m_size-ofs);
391 // Construct new item
392 m_alloc.construct(&m_items[ofs], val);
395 void shift_items(value_type *start, value_type *end, size_type count) {
397 for( size_type i = count; i --; ) {
398 #if _CXX11_AVAIL && 0
399 m_alloc.construct(&end[i], ::std::move(start[i]));
401 m_alloc.construct(&end[i], start[i]);
402 m_alloc.destroy(&start[i]);
407 for( size_type i = 0; i < count; i ++ ) {