opkele/iterator.h header

added a bunch of utility iterators

* output and forward iterator proxies
* filtering iterator
* map key extracting iterator

Signed-off-by: Michael Krelin <hacker@klever.net>

1 files changed, 217 insertions, 0 deletions

diff --git a/include/opkele/iterator.h b/include/opkele/iterator.h
new file mode 100644
index 0000000..812a786
--- a/dev/null
+++ b/include/opkele/iterator.h
@@ -0,0 +1,217 @@
+#ifndef __OPKELE_ITERATOR_H
+#define __OPKELE_ITERATOR_H
+
+#include <cassert>
+#include <iterator>
+
+namespace opkele {
+    namespace util {
+	using std::iterator;
+	using std::forward_iterator_tag;
+	using std::output_iterator_tag;
+
+	template <typename T>
+	class basic_output_iterator_proxy_impl : public iterator<output_iterator_tag,T,void,T*,T&> {
+	    public:
+		virtual ~basic_output_iterator_proxy_impl() { }
+
+		virtual basic_output_iterator_proxy_impl<T>* dup() const = 0;
+		basic_output_iterator_proxy_impl<T>& operator*() { return *this; };
+		virtual basic_output_iterator_proxy_impl<T>& operator=(const T& x) = 0;
+
+	};
+
+	template<typename IT,typename T=typename IT::value_type>
+	class output_iterator_proxy_impl : public basic_output_iterator_proxy_impl<T> {
+	    public:
+		IT i;
+
+		output_iterator_proxy_impl(const IT& i) : i(i) { }
+		basic_output_iterator_proxy_impl<T>* dup() const {
+		    return new output_iterator_proxy_impl<IT,T>(i); }
+		basic_output_iterator_proxy_impl<T>& operator=(const T& x) {
+		    (*i) = x;
+		}
+	};
+
+	template<typename T>
+	class output_iterator_proxy : public iterator<output_iterator_tag,T,void,T*,T&> {
+	    public:
+		basic_output_iterator_proxy_impl<T> *I;
+
+		template<typename IT>
+		    output_iterator_proxy(const IT& i)
+		    : I(new output_iterator_proxy_impl<IT,T>(i)) { }
+		output_iterator_proxy(const output_iterator_proxy<T>& x)
+		    : I(x.I->dup()) { }
+		~output_iterator_proxy() { delete I; }
+
+		output_iterator_proxy& operator=(const output_iterator_proxy<T>& x) {
+		    delete I; I = x.I->dup(); }
+
+		output_iterator_proxy& operator*() { return *this; }
+		output_iterator_proxy& operator=(const T& x) {
+		    (**I) = x; }
+
+		output_iterator_proxy& operator++() { return *this; }
+		output_iterator_proxy& operator++(int) { return *this; }
+	};
+
+	template <typename T,typename TR=T&,typename TP=T*>
+	class basic_forward_iterator_proxy_impl : public iterator<forward_iterator_tag,T,void,TP,TR> {
+	    public:
+		virtual ~basic_forward_iterator_proxy_impl() { }
+
+		virtual basic_forward_iterator_proxy_impl<T,TR,TP>* dup() const = 0;
+
+		virtual bool operator==(const basic_forward_iterator_proxy_impl<T,TR,TP>& x) const = 0;
+		virtual bool operator!=(const basic_forward_iterator_proxy_impl<T,TR,TP>& x) const {
+		    return !((*this)==x); }
+		virtual TR operator*() const = 0;
+		virtual TP operator->() const = 0;
+		virtual void advance() = 0;
+	};
+
+	template <typename IT>
+	class forward_iterator_proxy_impl : public basic_forward_iterator_proxy_impl<typename IT::value_type,typename IT::reference,typename IT::pointer> {
+	    public:
+		IT i;
+
+		forward_iterator_proxy_impl(const IT& i) : i(i) { }
+
+		virtual basic_forward_iterator_proxy_impl<typename IT::value_type,typename IT::reference,typename IT::pointer>* dup() const {
+		    return new forward_iterator_proxy_impl<IT>(i); }
+
+		virtual bool operator==(const basic_forward_iterator_proxy_impl<typename IT::value_type,typename IT::reference,typename IT::pointer>& x) const {
+		    return i==static_cast<const forward_iterator_proxy_impl<IT>*>(&x)->i; }
+		virtual bool operator!=(const basic_forward_iterator_proxy_impl<typename IT::value_type,typename IT::reference,typename IT::pointer>& x) const {
+		    return i!=static_cast<const forward_iterator_proxy_impl<IT>*>(&x)->i; }
+		virtual typename IT::reference operator*() const { return *i; }
+		virtual typename IT::pointer operator->() const { return i.operator->(); }
+		virtual void advance() { ++i; }
+	};
+
+	template<typename T,typename TR=T&,typename TP=T*>
+	class forward_iterator_proxy : public iterator<forward_iterator_tag,T,void,TP,TR> {
+	    public:
+		basic_forward_iterator_proxy_impl<T,TR,TP> *I;
+
+		template<typename IT>
+		    forward_iterator_proxy(const IT& i)
+		    : I(new forward_iterator_proxy_impl<IT>(i)) { }
+		forward_iterator_proxy(const forward_iterator_proxy<T,TR,TP>& x)
+		    : I(x.I->dup()) { }
+		~forward_iterator_proxy() { delete I; }
+
+		forward_iterator_proxy& operator=(const forward_iterator_proxy<T,TR,TP>& x) {
+		    delete I; I = x.I->dup(); }
+
+		bool operator==(const forward_iterator_proxy<T,TR,TP>& x) const {
+		    return (*I)==(*(x.I)); }
+		bool operator!=(const forward_iterator_proxy<T,TR,TP>& x) const {
+		    return (*I)!=(*(x.I)); }
+
+		TR operator*() const {
+		    return **I; }
+		TP operator->() const {
+		    return I->operator->(); }
+
+		forward_iterator_proxy<T,TR,TP>& operator++() {
+		    I->advance(); return *this; }
+		forward_iterator_proxy<T,TR,TP>& operator++(int) {
+		    forward_iterator_proxy<T,TR,TP> rv(*this);
+		    I->advance(); return rv; }
+	};
+
+	template<typename IT>
+	    class basic_filterator : public iterator<
+					  typename IT::iterator_category,
+					  typename IT::value_type,
+					  typename IT::difference_type,
+					  typename IT::pointer,
+					  typename IT::reference> {
+		public:
+		    IT it;
+		    IT ei;
+		    bool empty;
+
+		    basic_filterator() : empty(true) { }
+		    basic_filterator(const IT& bi,const IT& ei)
+			: it(bi), ei(ei) { empty = (bi==ei); }
+		    basic_filterator(const basic_filterator<IT>& x)
+			: it(x.it), ei(x.ei), empty(x.empty) { }
+		    virtual ~basic_filterator() { }
+
+		    bool operator==(const basic_filterator<IT>& x) const {
+			return empty?x.empty:(it==x.it); }
+		    bool operator!=(const basic_filterator<IT>& x) const {
+			return empty!=x.empty || it!=x.it; }
+
+		    typename IT::reference operator*() const {
+			assert(!empty);
+			return *it; }
+		    typename IT::pointer operator->() const {
+			assert(!empty);
+			return it.operator->(); }
+
+		    basic_filterator<IT>& operator++() {
+			bool found = false;
+			for(++it;!(it==ei || (found=is_interesting()));++it);
+			if(!found) empty=true;
+			return *this;
+		    }
+		    basic_filterator<IT> operator++(int) {
+			basic_filterator<IT> rv(*this);
+			++(*this);
+			return rv;
+		    }
+
+		    void prepare() {
+			bool found = false;
+			for(;!(it==ei || (found=is_interesting()));++it);
+			if(!found) empty = true;
+		    }
+		    virtual bool is_interesting() const = 0;
+	    };
+
+	template<typename IT,typename T=typename IT::value_type::first_type,typename TR=T&,typename TP=T*>
+	    class map_keys_iterator : public iterator<
+				      typename IT::iterator_category,
+				      T,void,TP,TR> {
+		public:
+		    typedef map_keys_iterator<IT,T,TR,TP> self_type;
+		    IT it;
+		    IT ei;
+		    bool empty;
+
+		    map_keys_iterator() : empty(true) { }
+		    map_keys_iterator(const IT& bi,
+			    const IT& ei)
+			: it(bi), ei(ei) { empty = (bi==ei); }
+		    map_keys_iterator(const self_type& x)
+			: it(x.it), ei(x.ei), empty(x.empty) { }
+
+		    bool operator==(const self_type& x) const {
+			return empty?x.empty:(it==x.it); }
+		    bool operator!=(const self_type& x) const {
+			return empty!=x.empty || it!=x.it; }
+
+		    TR operator*() const {
+			assert(!empty);
+			return it->first; }
+		    TP operator->() const {
+			assert(!empty);
+			return &(it->first); }
+
+		    self_type& operator++() {
+			assert(!empty);
+			empty=((++it)==ei); return *this; }
+		    self_type operator++(int) {
+			self_type rv(*this);
+			++(*this); return rv; }
+	    };
+
+    }
+}
+
+#endif /* __OPKELE_ITERATOR_H */