Usermode/Libraries/libc++.so_src/include_exp/map

   1 /*
   2  * Acess2 C++ Library
   3  * - By John Hodge (thePowersGang)
   4  *
   5  * map (header)
   6  * - C++'s map type
   7  */
   8 #ifndef _LIBCXX_MAP_
   9 #define _LIBCXX_MAP_
  10
  11 #include "_libcxx_helpers.h"
  12 #include <allocator>
  13 #include <stdexcept>
  14 #include <iterator>
  15 #include <utility>
  16 #include <functional>   // less
  17
  18 namespace std {
  19
  20 namespace _bits {
  21
  22 template <class Val, class Map>
  23 class map_iterator:
  24         public ::std::iterator< ::std::bidirectional_iterator_tag, Val >
  25 {
  26         friend Map;
  27         typedef Val     value_type;
  28         Map     *m_map;
  29         size_t  m_index;
  30 public:
  31         map_iterator():
  32                 m_map(0), m_index(0)
  33         {
  34         }
  35         map_iterator(Map *map, typename Map::size_type ofs):
  36                 m_map(map), m_index(ofs)
  37         {
  38         }
  39         map_iterator(const map_iterator& x) {
  40                 *this = x;
  41         }
  42         map_iterator& operator=(const map_iterator& x) {
  43                 m_map = x.m_map;
  44                 m_index = x.m_index;
  45                 return *this;
  46         }
  47
  48         map_iterator& operator++() {
  49                 m_index ++;
  50         }
  51         map_iterator& operator--() {
  52                 m_index --;
  53         }
  54
  55         bool operator==(const map_iterator& x) const {
  56                 return m_index == x.m_index;
  57         }
  58         bool operator!=(const map_iterator& x) const {
  59                 return !(*this == x);
  60         }
  61         value_type& operator*() {
  62                 return m_map->m_items[m_index];
  63         }
  64         value_type* operator->() {
  65                 return &m_map->m_items[m_index];
  66         }
  67 };
  68
  69 }       // namespace _bits
  70
  71 template <class Key, class T, class Compare=less<Key>, class Alloc=allocator<pair<const Key,T> > >
  72 class map
  73 {
  74         typedef map     this_type;
  75 public:
  76         typedef Key     key_type;
  77         typedef T       mapped_type;
  78         typedef pair<const Key, T>      value_type;
  79         typedef Compare key_compare;
  80         typedef Alloc   allocator_type;
  81         typedef typename allocator_type::reference      reference;
  82         typedef typename allocator_type::const_reference        const_reference;
  83         typedef typename allocator_type::pointer        pointer;
  84         typedef typename allocator_type::const_pointer  const_pointer;
  85         typedef _bits::map_iterator<value_type,this_type>       iterator;
  86         typedef _bits::map_iterator<const value_type,this_type> const_iterator;
  87         typedef size_t  size_type;
  88
  89 private:
  90         friend class ::std::_bits::map_iterator<value_type, this_type>;
  91         friend class ::std::_bits::map_iterator<const value_type, this_type>;
  92
  93         key_compare     m_comp;
  94         allocator_type  m_alloc;
  95         value_type*     m_items;        // sorted array
  96         size_type       m_size;
  97         size_type       m_capacity;
  98
  99 public:
 100         map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()):
 101                 m_comp(comp),
 102                 m_alloc(alloc),
 103                 m_items(0), m_size(0), m_capacity(0)
 104         {
 105         }
 106         template <class InputInterator>
 107         map(InputInterator first, InputInterator last):
 108                 map()
 109         {
 110                 insert(first, last);
 111         }
 112         map(const map& x):
 113                 map(x.m_comp, x.m_alloc)
 114         {
 115                 *this = x;
 116         }
 117         ~map() {
 118                 clear();
 119                 reserve(0);
 120         }
 121         map& operator=(const map& x) {
 122                 clear();
 123                 reserve(x.m_size);
 124                 for( size_type i = 0; i < x.m_size; i ++ ) {
 125                         emplace_hint( end(), x.m_items[i] );
 126                 }
 127                 return *this;
 128         }
 129
 130         // Iterators
 131         iterator begin() {
 132                 return iterator(this, 0);
 133         }
 134         const_iterator begin() const {
 135                 return const_iterator(this, 0);
 136         }
 137         iterator end() {
 138                 return iterator(this, m_size);
 139         }
 140         const_iterator end() const {
 141                 return const_iterator(this, m_size);
 142         }
 143         #if _CXX11_AVAIL
 144         const_iterator cbegin() const {
 145                 return const_iterator(this, 0);
 146         }
 147         const_iterator cend() const {
 148                 return const_iterator(this, m_size);
 149         }
 150         #endif
 151         //reverse_iterator rbegin();
 152         //const_reverse_iterator rbegin() const;
 153         //const_reverse_iterator crbegin() const;
 154         //reverse_iterator rend();
 155         //const reverse_iterator rend() const;
 156         //const reverse_iterator crend() const;
 157
 158         // Capacity
 159         bool empty() const {
 160                 return m_size == 0;
 161         }
 162         size_type size() const {
 163                 return m_size;
 164         }
 165         size_type max_size() const {
 166                 return (size_type)-1 / sizeof(value_type);
 167         }
 168
 169         // Element access
 170         mapped_type& operator[](const key_type& k) {
 171                 iterator it = upper_bound(k);
 172                 if( it == end() || m_comp(k, it->first) ) {     // if k < it->first, no match
 173                         insert_at(it.m_index, value_type(k,mapped_type()) );
 174                         ++ it;
 175                 }
 176                 return it->second;
 177         }
 178         #if _CXX11_AVAIL
 179         mapped_type& at(const key_type& k) {
 180                 iterator it = lower_bound(k);
 181                 if( it == end() || m_comp(it->first, k) )
 182                         throw ::std::out_of_range("::std:map::at");
 183                 return it->second;
 184         }
 185         const mapped_type& at(const key_type& k) const {
 186                 iterator it = lower_bound(k);
 187                 if( it == end() || m_comp(it->first, k) )
 188                         throw ::std::out_of_range("::std:map::at");
 189                 return it->second;
 190         }
 191         #endif
 192
 193         // Modifiers
 194         // - insert
 195         pair<iterator,bool> insert(const value_type& val);
 196         iterator insert(iterator position, const value_type& val);
 197         template <class InputInterator>
 198         void insert(InputInterator first, InputInterator last);
 199         // - erase
 200         void erase(iterator position);
 201         size_type erase(const key_type& k);
 202         void erase(iterator first, iterator last);
 203         // - swap
 204         void swap(map& x);
 205         // - clear
 206         void clear() {
 207                 for( size_type i = 0; i < m_size; i ++ ) {
 208                         m_alloc.destroy( &m_items[i] );
 209                 }
 210                 m_size = 0;
 211         }
 212         // - emplace
 213         #if _CXX11_AVAIL
 214         template <class... Args>
 215         pair<iterator,bool> emplace(Args&&... args) {
 216                 return emplace_hint(begin(), args...);
 217         }
 218         template <class... Args>
 219         pair<iterator,bool> emplace_hint(iterator position, Args&&... args);
 220         #endif
 221
 222         // TODO: Observers
 223
 224         // Operators
 225         iterator find(const key_type& k) {
 226                 iterator it = lower_bound(k);
 227                 if( it == end() || m_comp(it->first, k) )       // if it->first < k
 228                         return end();
 229                 return it;
 230         }
 231         const_iterator find(const key_type& k) const {
 232                 const_iterator it = lower_bound(k);
 233                 if( it == end() || m_comp(it->first, k) )       // if it->first < k
 234                         return end();
 235                 return it;
 236         }
 237         size_type count(const key_type& k) {
 238                 if( find(k) == end() )
 239                         return 0;
 240                 return 1;
 241         }
 242         iterator lower_bound(const key_type& k) {
 243                 size_type idx;
 244                 if( _search(k, idx) ) {
 245                         // found, return direct iterator
 246                         return iterator(this, idx);
 247                 }
 248                 else {
 249                         // not found, return iterator to before
 250                         if( idx == 0 )  return begin();
 251                         return iterator(this, idx-1);
 252                 }
 253         }
 254         const_iterator lower_bound(const key_type& k) const {
 255                 size_type idx;
 256                 if( _search(k, idx) ) {
 257                         // found, return direct iterator
 258                         return iterator(this, idx);
 259                 }
 260                 else {
 261                         // not found, return iterator to before
 262                         if( idx == 0 )  return begin();
 263                         return iterator(this, idx-1);
 264                 }
 265         }
 266         iterator upper_bound(const key_type& k) {
 267                 size_type idx;
 268                 _search(k, idx);
 269                 // idx == item or just after it
 270                 return iterator(this, idx);
 271         }
 272         const_iterator upper_bound(const key_type& k) const {
 273                 size_type idx;
 274                 _search(k, idx);
 275                 return const_iterator(this, idx);
 276         }
 277         pair<iterator,iterator> equal_range(const key_type& k);
 278         pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
 279
 280 private:
 281         // Change reservation to fit 'n' items
 282         // - NOTE: Will also resize down
 283         void reserve(size_type n) {
 284                 n = (n + 31) & ~31;
 285                 if( n > max_size() )
 286                         throw ::std::length_error("::std::map::reserve");
 287                 if( n != m_capacity )
 288                 {
 289                         auto new_area = m_alloc.allocate(n);
 290                         for( size_type i = 0; i < m_size && i < n; i ++ )
 291                                 m_alloc.construct(&new_area[i], m_items[i]);
 292                         for( size_type i = n; i < m_size; i ++ )
 293                                 m_alloc.destroy( &m_items[i] );
 294                         m_alloc.deallocate(m_items, m_capacity);
 295                         m_items = new_area;
 296                         m_capacity = n;
 297                         if(m_size > n)
 298                                 m_size = n;
 299                 }
 300         }
 301         // Returns the index above or equal to 'k'
 302         // - TODO: Reimplement as a binary search
 303         bool _search(const key_type& k, size_type &pos_out) const {
 304                 #if 0
 305                 size_type pos = m_size / 2;
 306                 size_type step = m_size / 4;
 307                 while( step > 0 ) {
 308                         const key_type& item_key = m_items[pos].first;
 309                         if( m_comp(item_key, k) )
 310                                 pos += step;
 311                         else if( m_comp(k, item_key) )
 312                                 pos -= step;
 313                         else {
 314                                 pos_out = pos;
 315                                 return true;
 316                         }
 317                         step /= 2;
 318                 }
 319                 pos_out = pos;
 320                 return false;
 321                 #else
 322                 for( size_type pos = 0; pos < m_size; pos ++ )
 323                 {
 324                         const key_type& item_key = m_items[pos].first;
 325                         if( m_comp(item_key, k) ) {
 326                                 continue;
 327                         }
 328                         else if( m_comp(k, item_key) ) {
 329                                 pos_out = pos;
 330                                 return false;
 331                         }
 332                         else {
 333                                 pos_out = pos;
 334                                 return true;
 335                         }
 336                 }
 337                 pos_out = m_size;
 338                 return false;
 339                 #endif
 340         }
 341         void insert_at(size_type ofs, const value_type& val) {
 342                 //assert( ofs == 0 || m_comp(m_items[ofs-1].first, val.first) );
 343                 //assert( ofs == m_size || m_comp(m_items[ofs].first, val.first) );
 344                 ::_sys::debug("map::insert_at(%i,)", ofs);
 345                 // Resize up
 346                 reserve( m_size + 1 );
 347                 // Move following items up
 348                 shift_items(&m_items[ofs], &m_items[ofs+1], m_size-ofs);
 349                 // Construct new item
 350                 m_alloc.construct(&m_items[ofs], val);
 351                 m_size ++;
 352         }
 353         void shift_items(value_type *start, value_type *end, size_type count) {
 354                 if( start < end ) {
 355                         for( size_type i = count; i --; ) {
 356                                 #if _CXX11_AVAIL && 0
 357                                 m_alloc.construct(&end[i], ::std::move(start[i]));
 358                                 #else
 359                                 m_alloc.construct(&end[i], start[i]);
 360                                 m_alloc.destroy(&start[i]);
 361                                 #endif
 362                         }
 363                 }
 364                 else {
 365                         for( size_type i = 0; i < count; i ++ ) {
 366                         }
 367                 }
 368         }
 369 };
 370
 371 }       // namespace std
 372
 373 #endif
 374
 375 // vim: ft=cpp
 376