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