1 files changed, 512 insertions, 0 deletions
diff --git a/quickcheck/flat_segment_tree.cpp b/quickcheck/flat_segment_tree.cpp
new file mode 100644
index 0000000..a7d3168
--- /dev/null
+++ b/quickcheck/flat_segment_tree.cpp
@@ -0,0 +1,512 @@
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <memory>
+#include <ostream>
+#include <set>
+#include <string>
+#include <sstream>
+
+#include <mdds/flat_segment_tree.hpp>
+
+#include <quickcheck/quickcheck.hh>
+
+namespace
+{
+
+using quickcheck::Property;
+
+using std::ostream;
+using std::pair;
+using std::string;
+
+typedef mdds::flat_segment_tree<unsigned, unsigned> fst_type;
+typedef fst_type::key_type key_type;
+typedef fst_type::value_type value_type;
+
+class fst_wrapper
+{
+public:
+    fst_type* get() const
+    {
+        return m_pimpl.get();
+    }
+    fst_type& operator*() const
+    {
+        assert(initialized());
+        return *get();
+    }
+    fst_type* operator->() const
+    {
+        assert(initialized());
+        return get();
+    }
+
+    bool initialized() const
+    {
+        return m_pimpl.get();
+    }
+
+    void initialize(key_type low_, key_type high_, value_type value_)
+    {
+        assert(!initialized());
+        m_pimpl.reset(new fst_type(low_, high_, value_));
+    }
+
+private:
+    std::shared_ptr<fst_type> m_pimpl;
+};
+
+template<typename Key, typename Value>
+ostream&
+operator<<(ostream& out_, mdds::flat_segment_tree<Key, Value> const& fst_)
+{
+    out_ << "[";
+    bool first(true);
+    typedef typename mdds::flat_segment_tree<Key, Value>::const_iterator
+        iterator_type;
+    iterator_type cur(fst_.begin());
+    for (iterator_type end(fst_.end()); cur != end; ++cur) 
+    {
+        if (first)
+            first = false;
+        else
+            out_ << ", ";
+        out_ << cur->first << ": " << cur->second;
+    }
+    out_ << ", " << cur->first << "), default = " << fst_.default_value();
+    return out_;
+}
+
+ostream& operator<<(ostream& out_, fst_wrapper const& fst_)
+{
+    return fst_.initialized() ? out_ << *fst_ : out_;
+}
+
+template<typename T>
+struct generator
+{
+    generator(size_t n_)
+        : m_n(n_)
+    {
+    }
+
+    T operator()() const
+    {
+        using quickcheck::generate;
+        T val;
+        generate(m_n, val);
+        return val;
+    }
+
+private:
+    size_t m_n;
+};
+
+void generate(size_t n_, fst_wrapper& fst_)
+{
+    using quickcheck::generate;
+    value_type default_value;
+    generate(n_, default_value);
+
+    // generate a number of segments
+    size_t segments(0);
+    generate(n_, segments);
+    segments = std::max<size_t>(segments, 1);
+
+    using std::set;
+    set<key_type> points;
+    {
+        size_t count(segments + 1);
+        while (count > 0)
+        {
+            generator<key_type> gen(n_);
+            if (points.insert(gen()).second)
+                --count;
+        }
+    }
+
+    using std::vector;
+    vector<value_type> values;
+    values.reserve(segments);
+    std::generate_n(
+            std::back_inserter(values), segments, generator<value_type>(n_));
+
+    fst_.initialize(*points.begin(), *points.rbegin(), default_value);
+
+    // insert segments
+    if (segments >= 2)
+    {
+        assert(points.size() == values.size() + 1);
+
+        typedef set<key_type>::const_iterator points_iterator;
+        points_iterator last(points.begin());
+        points_iterator cur(points.begin());
+        points_iterator end(points.end());
+        typedef vector<value_type>::const_iterator values_iterator;
+        values_iterator cur_val(values.begin());
+        values_iterator end_val(values.end());
+        ++cur;
+        while (cur != end && cur_val != end_val)
+        {
+            fst_->insert_back(*last, *cur, *cur_val);
+            last = cur;
+            ++cur;
+            ++cur_val;
+        }
+    }
+}
+
+bool is_valid_key(fst_type const& fst_, key_type const& key_)
+{
+    return key_ >= fst_.begin()->first && key_ < fst_.rbegin()->first;
+}
+
+bool is_valid_range(fst_type const& fst_, key_type const& low_, key_type const& high_)
+{
+    return low_ < high_ && is_valid_key(fst_, low_) && is_valid_key(fst_, high_);
+}
+
+bool is_empty_tree(fst_type const& fst_)
+{
+    return fst_.rbegin()->first - fst_.begin()->first == 1;
+}
+
+bool is_single_segment(fst_type const& fst_)
+{
+    fst_type::const_iterator begin(fst_.begin());
+    ++begin;
+    return begin == fst_.end();
+}
+
+class FlatSegmentTreeInsertProperty
+    : public Property<fst_wrapper, key_type, key_type, key_type>
+{
+public:
+    typedef fst_type::const_iterator const_iterator;
+
+    virtual bool
+    accepts(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const&)
+    {
+        return is_valid_range(*fst_, low_, high_);
+    }
+};
+
+class FlatSegmentTreeChangeProperty
+    : public FlatSegmentTreeInsertProperty
+{
+public:
+    virtual bool
+    isTrivialFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const&)
+    {
+        return is_empty_tree(*fst_);
+    }
+};
+
+class PInsertFrontIsSameAsInsertBack : public FlatSegmentTreeChangeProperty
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const& value_)
+    {
+        fst_type insert_front(*fst_);
+        fst_type insert_back(*fst_);
+        insert_front.insert_front(low_, high_, value_);
+        insert_back.insert_back(low_, high_, value_);
+        return insert_front == insert_back;
+    }
+};
+
+class PInsertIsSameAsInsertBack : public FlatSegmentTreeChangeProperty
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const& value_)
+    {
+        fst_type insert(*fst_);
+        fst_type insert_back(*fst_);
+        insert.insert(insert.begin(), low_, high_, value_);
+        insert_back.insert_back(low_, high_, value_);
+        return insert == insert_back;
+    }
+};
+
+class PRepeatedInsertDoesNothing : public FlatSegmentTreeChangeProperty
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const& value_)
+    {
+        fst_type fst(*fst_);
+        const_iterator const pos(fst.insert_front(low_, high_, value_).first);
+        fst_type orig(fst);
+        fst.build_tree();
+        pair<const_iterator, bool> result(fst.insert(pos, low_, high_, value_));
+        return !result.second && result.first == pos && fst == orig;
+    }
+};
+
+class PKeyInLimitsIsFound : public FlatSegmentTreeInsertProperty
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const& value_)
+    {
+        fst_type fst(*fst_);
+        value_type dummy;
+        pair<const_iterator, bool> result(fst.search(low_, dummy));
+
+        return result.second && result.first != fst.end() &&
+            result.first->first <= low_;
+    }
+};
+
+class PKeyInInsertedSegmentIsFound : public FlatSegmentTreeChangeProperty
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const& value_)
+    {
+        fst_type fst(*fst_);
+        pair<const_iterator, bool>
+            insert(fst.insert_front(low_, high_, value_));
+        value_type value;
+        pair<const_iterator, bool> search(fst.search(insert.first, low_, value));
+        return search.second && search.first == insert.first && value == value_;
+    }
+};
+
+class PSearchTreeIsSameAsSearch : public Property<fst_wrapper, key_type>
+{
+    virtual bool holdsFor(fst_wrapper const& fst_, key_type const& key_)
+    {
+        fst_type fst(*fst_);
+        value_type value;
+        key_type low;
+        key_type high;
+        pair<fst_type::const_iterator, bool> search(fst.search(key_, value, &low, &high));
+
+        if (!fst.is_tree_valid())
+            fst.build_tree();
+        value_type value_tree;
+        key_type low_tree;
+        key_type high_tree;
+        bool const search_tree(fst.search_tree(key_, value_tree, &low_tree, &high_tree));
+        return search.second == search_tree && low == low_tree
+            && high == high_tree && value == value_tree;
+    }
+
+    virtual bool accepts(fst_wrapper const& fst_, key_type const& key_)
+    {
+        return is_valid_key(*fst_, key_);
+    }
+};
+
+class PSearchDoesNotChangeTree : public Property<fst_wrapper, key_type>
+{
+    virtual bool holdsFor(fst_wrapper const& fst_, key_type const& key_)
+    {
+        fst_type& orig(*fst_);
+        fst_type fst(orig);
+        value_type dummy;
+        fst.search(key_, dummy);
+        return fst == orig;
+    }
+
+    virtual bool accepts(fst_wrapper const& fst_, key_type const& key_)
+    {
+        return is_valid_key(*fst_, key_);
+    }
+};
+
+class PBuildTreeDoesNotChangeTree : public Property<fst_wrapper>
+{
+    virtual bool holdsFor(fst_wrapper const& fst_)
+    {
+        fst_type& orig(*fst_);
+        fst_type& fst(orig);
+        fst.build_tree();
+        return fst == orig;
+    }
+
+    virtual bool isTrivialFor(fst_wrapper const& fst_)
+    {
+        return fst_->is_tree_valid();
+    }
+};
+
+class PShiftLeftRemovesSomething : public Property<fst_wrapper, key_type, key_type>
+{
+    virtual bool
+    holdsFor(fst_wrapper const& fst_, key_type const& low_, key_type const& high_)
+    {
+        fst_type& orig(*fst_);
+        fst_type fst(orig);
+        fst.shift_left(low_, high_);
+        return fst != orig;
+    }
+
+    virtual bool
+    accepts(fst_wrapper const& fst_, key_type const& low_, key_type const& high_)
+    {
+        return is_valid_range(*fst_, low_, high_) && !is_single_segment(*fst_);
+    }
+};
+
+class PShiftRightWorks : public Property<fst_wrapper, key_type, key_type, bool>
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& key_, key_type const& size_,
+            bool const& skip_start_)
+    {
+        fst_type& orig(*fst_);
+        fst_type fst(orig);
+        fst.shift_right(key_, size_, skip_start_);
+        return isTrivialFor(fst_, key_, size_, skip_start_) ? fst == orig : fst != orig;
+    }
+
+    virtual bool
+    accepts(
+            fst_wrapper const& fst_, key_type const& key_, key_type const& size_,
+            bool const&)
+    {
+        return is_valid_key(*fst_, key_);
+    }
+
+    virtual bool
+    isTrivialFor(
+            fst_wrapper const& fst_, key_type const& key_, key_type const& size_,
+            bool const& skip_start_)
+    {
+        return
+            (is_single_segment(*fst_) && fst_->begin()->second == fst_->default_value())
+            || size_ == 0
+            || (skip_start_ && key_ == fst_->max_key() - 1);
+    }
+};
+
+bool keys_ordered(fst_type const& fst_)
+{
+    fst_type::const_iterator cur(fst_.begin());
+    fst_type::const_iterator end(fst_.end());
+    fst_type::const_iterator last(cur);
+    ++cur;
+    while (cur != end)
+    {
+        if (last->first >= cur->first)
+            return false;
+        ++cur;
+    }
+    return last->first < cur->first;
+}
+
+class PKeysOrderedAfterInsert : public FlatSegmentTreeInsertProperty
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const& value_)
+    {
+        fst_type fst(*fst_);
+        fst.insert_front(low_, high_, value_);
+        return keys_ordered(fst);
+    }
+
+    virtual bool
+    isTrivialFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            value_type const& value_)
+    {
+        fst_type fst(*fst_);
+        return !fst.insert_front(low_, high_, value_).second;
+    }
+};
+
+class PKeysOrderedAfterShiftLeft : public Property<fst_wrapper, key_type, key_type>
+{
+    virtual bool
+    holdsFor(fst_wrapper const& fst_, key_type const& low_, key_type const& high_)
+    {
+        fst_type fst(*fst_);
+        fst.shift_left(low_, high_);
+        return keys_ordered(fst);
+    }
+
+    virtual bool
+    accepts(fst_wrapper const& fst_, key_type const& low_, key_type const& high_)
+    {
+        return is_valid_range(*fst_, low_, high_);
+    }
+
+    virtual bool
+    isTrivialFor(fst_wrapper const& fst_, key_type const& low_, key_type const& high_)
+    {
+        fst_type& fst(*fst_);
+        return is_single_segment(fst) && fst.begin()->second == fst.default_value();
+    }
+};
+
+class PKeysOrderedAfterShiftRight : public Property<fst_wrapper, key_type, key_type, bool>
+{
+    virtual bool
+    holdsFor(
+            fst_wrapper const& fst_, key_type const& key_, key_type const& size_,
+            bool const& skip_start_)
+    {
+        fst_type fst(*fst_);
+        fst.shift_right(key_, size_, skip_start_);
+        return keys_ordered(fst);
+    }
+
+    virtual bool
+    accepts(
+            fst_wrapper const& fst_, key_type const& key_, key_type const& size_,
+            bool const&)
+    {
+        return is_valid_key(*fst_, key_);
+    }
+
+    virtual bool
+    isTrivialFor(
+            fst_wrapper const& fst_, key_type const& low_, key_type const& high_,
+            bool const&)
+    {
+        fst_type& fst(*fst_);
+        return is_single_segment(fst) && fst.begin()->second == fst.default_value();
+    }
+};
+
+}
+
+int main()
+{
+    size_t const tests(200);
+    using quickcheck::check;
+    check<PInsertFrontIsSameAsInsertBack>(
+            "insert_front is the same as insert_back", tests);
+    check<PInsertIsSameAsInsertBack>("insert is same as insert_back", tests);
+    check<PRepeatedInsertDoesNothing>("repeated insert does nothing", tests);
+    check<PKeyInLimitsIsFound>("key in tree limits is found", tests);
+    check<PKeyInInsertedSegmentIsFound>(
+            "key in just inserted segment is found at the right pos", tests);
+    check<PSearchTreeIsSameAsSearch>("search_tree is the same as search", tests);
+    check<PSearchDoesNotChangeTree>("search does not change tree", tests);
+    check<PBuildTreeDoesNotChangeTree>("build_tree does not change tree", tests);
+    check<PShiftLeftRemovesSomething>("shift_left removes something", tests);
+    // check<PShiftRightWorks>("shift_right works", tests);
+    check<PKeysOrderedAfterInsert>("keys remain ordered after insert", tests);
+    check<PKeysOrderedAfterShiftLeft>("keys remain ordered after shift_left", tests);
+    check<PKeysOrderedAfterShiftRight>("keys remain ordered after shift_right", tests);
+}
+
+// vim: set ts=4 sw=4 et: