00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef RAUL_TABLE_HPP
00019 #define RAUL_TABLE_HPP
00020
00021 #include <algorithm>
00022 #include <utility>
00023 #include <vector>
00024
00025 #include <boost/utility.hpp>
00026
00027 #include "raul/SharedPtr.hpp"
00028
00029
00030
00031 namespace Raul {
00032
00033
00041 template <typename K, typename T>
00042 class Table : public boost::noncopyable {
00043 public:
00044 Table<K, T>() : _entries() {}
00045 Table<K, T>(size_t capacity) : _entries(capacity) {}
00046
00047 void clear() { _entries.clear(); }
00048 bool empty() const { return _entries.empty(); }
00049 void reserve(size_t n) { _entries.reserve(n); }
00050
00051 struct const_iterator {
00052 const_iterator(const Table<K,T>& t, size_t i) : _table(&t), _index(i) {}
00053 inline const std::pair<const K, T> operator*() const { return _table->_entries[_index]; }
00054 inline const std::pair<const K, T>* operator->() const { return (std::pair<const K, T>*)&_table->_entries[_index]; }
00055 inline const_iterator& operator++() { ++_index; return *this; }
00056 inline const_iterator& operator--() { --_index; return *this; }
00057 inline bool operator==(const const_iterator& i) const { return _index == i._index; }
00058 inline bool operator!=(const const_iterator& i) const { return _index != i._index; }
00059 void operator=(const const_iterator& i) { _table = i._table; _index = i._index; }
00060 private:
00061 friend class Table<K,T>;
00062 const Table<K,T>* _table;
00063 size_t _index;
00064 };
00065
00066 struct iterator {
00067 iterator(Table<K,T>& t, size_t i) : _table(&t), _index(i) {}
00068 inline std::pair<K, T>& operator*() const { return (std::pair<K, T>&)_table->_entries[_index]; }
00069 inline std::pair<K, T>* operator->() const { return (std::pair<K, T>*)&_table->_entries[_index]; }
00070 inline iterator& operator++() { ++_index; return *this; }
00071 inline iterator& operator--() { --_index; return *this; }
00072 inline bool operator==(const iterator& i) const { return _index == i._index; }
00073 inline bool operator!=(const iterator& i) const { return _index != i._index; }
00074 operator const_iterator() { return *(const_iterator*)this; }
00075 iterator& operator=(const iterator& i) { _table = i._table; _index = i._index; return *this; }
00076 private:
00077 friend class Table<K,T>;
00078 Table<K,T>* _table;
00079 size_t _index;
00080 };
00081
00082 inline size_t size() const { return _entries.size(); }
00083
00084 std::pair<iterator,bool> insert(const std::pair<K, T>& entry);
00085
00086 void erase(const K& key);
00087 void erase(iterator i);
00088 void erase(iterator start, iterator end);
00089 void erase_by_index(size_t start, size_t end);
00090
00091 SharedPtr< Table<K, T> > yank(iterator start, iterator end);
00092
00093 std::pair<iterator, bool> cram(const Table<K, T>& range);
00094
00095 const_iterator find(const_iterator start, const_iterator end, const K& key) const;
00096 const_iterator find(const K& key) const;
00097
00098 iterator find(const_iterator start, const_iterator end, const K& key);
00099 iterator find(const K& key);
00100
00101 const_iterator find_range_end(const_iterator left, bool (*comp)(const K&,const K&)) const;
00102 iterator find_range_end(iterator left, bool (*comp)(const K&,const K&));
00103
00104 T& operator[](const K& key);
00105
00106 const_iterator begin() const { return const_iterator(*this, 0); }
00107 const_iterator end() const { return const_iterator(*this, size()); }
00108 iterator begin() { return iterator(*this, 0); }
00109 iterator end() { return iterator(*this, size()); }
00110
00111 private:
00112 #ifdef TABLE_SORT_DEBUG
00113 bool is_sorted() const;
00114 #endif
00115
00116 friend class iterator;
00117
00118 typedef std::pair<K, T> Entry;
00119
00120 std::vector<Entry> _entries;
00121 };
00122
00123
00124 }
00125
00126 #endif // RAUL_TABLE_HPP