summaryrefslogtreecommitdiff
path: root/Runtime/Utilities/vector_set.h
diff options
context:
space:
mode:
Diffstat (limited to 'Runtime/Utilities/vector_set.h')
-rw-r--r--Runtime/Utilities/vector_set.h229
1 files changed, 229 insertions, 0 deletions
diff --git a/Runtime/Utilities/vector_set.h b/Runtime/Utilities/vector_set.h
new file mode 100644
index 0000000..9d06e19
--- /dev/null
+++ b/Runtime/Utilities/vector_set.h
@@ -0,0 +1,229 @@
+#ifndef VECTOR_SET_H
+#define VECTOR_SET_H
+
+#include "sorted_vector.h"
+#include <functional>
+
+// vector_set offers the same functionality as std::set
+// but it is implemented using sorted vectors.
+// sorted_vectors are smaller in used memory and can be faster due to cache coherence
+// However inserting or erasing elements is O (N) instead of O (logN)
+// - Usually you will want to use vector_set when you have a set which you use
+// much more often to find values than inserting them or if the set you use is very small
+// vector_set also offers the vector function reserve.
+// - also note that if you store an iterator to an element you are NOT guaranteed that this iterator
+// remains valid after you insert/erase other elements
+
+template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> >
+class vector_set
+{
+ public:
+
+ typedef sorted_vector<Key, Compare, Allocator> container;
+ typedef typename container::container vector_container;
+ typedef typename container::iterator iterator;
+ typedef typename container::const_iterator const_iterator;
+ typedef typename container::reverse_iterator reverse_iterator;
+ typedef typename container::const_reverse_iterator const_reverse_iterator;
+ typedef typename container::value_type value_type;
+ typedef typename container::value_type key_type;
+ typedef Compare key_compare;
+ typedef Compare value_compare;
+ typedef typename container::size_type size_type;
+ typedef typename container::difference_type difference_type;
+ typedef Allocator allocator_type;
+
+
+ vector_set (const Compare& comp = Compare (), const Allocator& a = Allocator())
+ : c (comp, a) { }
+
+ template <class InputIterator>
+ vector_set (InputIterator first, InputIterator last, const Compare& comp = Compare (), const Allocator& a = Allocator())
+ : c (comp, a)
+ {
+ assign(first, last);
+ }
+
+ // Assigns a range that is known to be sorted
+ template<class InputIterator>
+ void assign_sorted (InputIterator first, InputIterator last){ c.c.assign (first, last); c.verify_duplicates_and_sorted (); }
+
+ // Assigns a range
+ // Asserts if there are any duplicates in the input
+ template<class InputIterator>
+ void assign (InputIterator first, InputIterator last)
+ {
+ c.c.assign (first, last);
+
+ sort();
+ }
+
+ // Assigns a range
+ // clears any duplicate objects
+ template<class InputIterator>
+ void assign_clear_duplicates (InputIterator first, InputIterator last)
+ {
+ c.c.assign (first, last);
+ std::stable_sort(c.begin(), c.end(), c.value_comp());
+
+ // Check that there are no duplicates in the set
+ if (!empty())
+ {
+ Key* previous = &*c.begin();
+ iterator i = c.begin(); i++;
+ for (; i != c.end();)
+ {
+ if (*i < *previous || *previous < *i)
+ {
+ previous = &*i;
+ i++;
+ }
+ else
+ {
+ iterator e;
+ for (e=i;e!=c.end() && !(*e < *previous || *previous < *e);e++)
+ ;
+ c.erase(i, e);
+ }
+ }
+ }
+
+ c.verify_duplicates_and_sorted ();
+ }
+
+ bool empty () const { return c.empty (); }
+
+ iterator begin() { return c.begin (); }
+ const_iterator begin() const { return c.begin (); }
+ iterator end() { return c.end (); }
+ const_iterator end() const { return c.end (); }
+ reverse_iterator rbegin() { return c.rbegin (); }
+ const_reverse_iterator rbegin() const { return c.rbegin (); }
+ reverse_iterator rend() { return c.rend (); }
+ const_reverse_iterator rend() const { return c.rend (); }
+
+ size_type size() const { return c.size (); }
+ size_type max_size() const { return c.max_size (); }
+
+ std::pair<iterator,bool>insert(const value_type& x) { return c.insert_one (x); }
+
+ void erase(iterator position) { c.erase (position); }
+ size_type erase(const key_type& x) { return c.erase_one (x); }
+ void erase(iterator first, iterator last){ c.erase (first, last); }
+ void clear() { c.clear (); }
+
+ void swap(vector_set& x) { c.swap (x.c); }
+
+ // set operations:
+ iterator find(const key_type& x) { return c.find (x); }
+ const_iterator find(const key_type& x) const { return c.find (x); }
+ size_type count(const key_type& x) const { return c.count_one (x); }
+
+ iterator lower_bound(const key_type& x) { return c.lower_bound (x); }
+ const_iterator lower_bound(const key_type& x) const{ return c.lower_bound (x); }
+
+ iterator upper_bound(const key_type& x) { return c.upper_bound (x); }
+ const_iterator upper_bound(const key_type& x) const{ return c.upper_bound (x); }
+
+ std::pair<iterator,iterator> equal_range(const key_type& x) { return c.equal_range (x); }
+ std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const { return c.equal_range (x); }
+
+ // vector specific operations
+ void reserve (size_type n) { c.reserve (n); }
+
+ value_type& operator [] (int n) { return c[n]; }
+ const value_type& operator [] (int n) const { return c[n]; }
+
+ vector_container& get_vector () { return c.c; }
+
+ void push_unsorted (const value_type& x)
+ {
+ get_vector().push_back(x);
+ }
+
+ void sort ()
+ {
+ std::sort(c.c.begin(), c.c.end(), c.value_comp ());
+ c.verify_duplicates_and_sorted ();
+ }
+
+ void verify_duplicates_and_sorted () const
+ {
+ c.verify_duplicates_and_sorted ();
+ }
+
+
+ public:
+
+ container c;
+};
+
+template <class Key, class Compare = std::equal_to<Key>, class Allocator = std::allocator<Key> >
+class us_vector_set
+{
+ public:
+
+ typedef unsorted_vector<Key, Compare, Allocator> container;
+ typedef typename container::container vector_container;
+ typedef typename container::iterator iterator;
+ typedef typename container::const_iterator const_iterator;
+ typedef typename container::reverse_iterator reverse_iterator;
+ typedef typename container::const_reverse_iterator const_reverse_iterator;
+ typedef typename container::value_type value_type;
+ typedef typename container::value_type key_type;
+ typedef Compare key_compare;
+ typedef Compare value_compare;
+ typedef typename container::size_type size_type;
+ typedef typename container::difference_type difference_type;
+ typedef Allocator allocator_type;
+
+
+ us_vector_set (const Compare& comp = Compare (), const Allocator& a = Allocator())
+ : c (comp, a) { }
+
+ template <class InputIterator>
+ us_vector_set (InputIterator first, InputIterator last, const Compare& comp = Compare (), const Allocator& a = Allocator())
+ : c (comp, a) { insert_one (first, last); }
+
+ bool empty () const { return c.empty (); }
+
+ iterator begin() { return c.begin (); }
+ const_iterator begin() const { return c.begin (); }
+ iterator end() { return c.end (); }
+ const_iterator end() const { return c.end (); }
+ reverse_iterator rbegin() { return c.rbegin (); }
+ const_reverse_iterator rbegin() const { return c.rbegin (); }
+ reverse_iterator rend() { return c.rend (); }
+ const_reverse_iterator rend() const { return c.rend (); }
+
+ size_type size() const { return c.size (); }
+ size_type max_size() const { return c.max_size (); }
+
+ std::pair<iterator,bool> insert(const value_type& x) { return c.insert_one (x); }
+
+ void erase(iterator position) { c.erase (position); }
+ size_type erase(const key_type& x) { return c.erase_one (x); }
+ void erase(iterator first, iterator last){ c.erase (first, last); }
+ void clear() { c.clear (); }
+
+ void swap(us_vector_set& x) { c.swap (x.c); }
+
+ // set operations:
+ iterator find(const key_type& x) { return c.find (x); }
+ const_iterator find(const key_type& x) const { return c.find (x); }
+ size_type count(const key_type& x) const { return c.count_one (x); }
+
+ // vector specific operations
+ void reserve (size_type n) { c.reserve (n); }
+
+ value_type& operator [] (int n) { return c[n]; }
+ const value_type& operator [] (int n) const { return c[n]; }
+
+ vector_container& get_vector () { return c.c; }
+
+ public:
+
+ container c;
+};
+
+#endif
generated by cgit v1.1-26-g67d0 at 2025-05-18 19:24:26 +0000