xset.h

// xset.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2008

@import "SelectBPlusTree.h"
#include <set>

namespace ceda
{

///////////////////////////////////////////////////////////////////////////////////////////////////
// xset

/*
xset<K> is basically an alias for  cref< BTree<K> > with the following additional
changes

    *   ==, !=, < modified to work on the B+Tree rather than the cref
    
    *   copy ctor, assignment ???
    
Note that serialisation of the model attribute serialises the cref as we require.
*/

template <typename K>
class _xset : public bplustreeset<K>
{
public:
    using typename bplustreeset<K>::key_type;
    using typename bplustreeset<K>::const_iterator;

    bool Insert(const key_type& key)
    {
        return this->insert(key).second;
    }
    bool Delete(const key_type& key)
    {
        return this->erase(key) == 1;
    }
    
    ///////////////////////////////////////////////////////////////////////////
    // Implementation of IXSet

    void Construct()
    {
        new(this) _xset();
    }

    void Insert(InputArchive& ar)
    {
        key_type key;
        ar >> key;
        this->insert(key);
    }
    void Delete(InputArchive& ar)
    {
        key_type key;
        ar >> key;
        this->erase(key);
    }
    void Find(InputArchive& ar, bool& found) const
    {
        key_type key;
        ar >> key;
        found = this->find(key) != this->end();
    }

    template<typename Archive>
    void Serialise(Archive& ar) const
    {
        SerialiseVariableLengthUint(ar,this->size());
        for (const_iterator i = this->begin() ; i != this->end() ; ++i)
        {
            ar << *i;
        }
    }
    
    template<typename Archive>
    void Deserialise(Archive& ar)
    {
        ssize_t n;
        DeserialiseVariableLengthUint(ar,n);
        this->clear();
        for (ssize_t i=0 ; i < n ; ++i)
        {
            key_type key;
            ar >> key;    
            this->insert(key);
        }
    }
    ptr<IObject> GetRootNode()  // todo: bad name - not the same as the root node of the B+Tree
    {
        return &this->GetUnderlyingBPlusTree();
    }

    ptr<IBiDirIterator> GetIterator() const
    {
        return new BTreeIterator<const_iterator>(this->begin());
    }

    static void ScanOver(InputArchive& ar)
    {
        ssize_t n;
        DeserialiseVariableLengthUint(ar,n);
        for (ssize_t i=0 ; i < n ; ++i)
        {
            key_type key;
            ar >> key;    
        }
    }

    static ptr<IKeyType> GetKeyType()
    {
        static KeyType<key_type> s;
        return &s;
    }
};

template <typename K>
class xset : public _xset<K>
{
};

// todo: What about specialisation for pref<T>?
template<typename T>
class xset<cref<T> > : public _xset<cref<T> >
{
public:
    using typename _xset<cref<T> >::const_iterator;
    /*
    struct const_iterator : public _xset<cref<T> >::const_iterator
    {
        typedef typename _xset<cref<T> >::const_iterator _Base;
        
        const_iterator& operator++() { return (const_iterator&) _Base::operator++(); }
        const const_iterator operator++(int) { return (const_iterator) _Base::operator++(int); }
        const_iterator& operator--() { return (const_iterator&) _Base::operator--(); }
        const const_iterator operator--(int) { return (const_iterator) _Base::operator--(int); }

        const cref<T>& operator*() const { return (const cref<T>&) _Base::operator*(); }
    };
    

    const_iterator begin() const { return (const const_iterator&) _xset<cref<T> >::begin(); }
    const_iterator end() const { return (const const_iterator&) _xset<cref<T> >::end(); }
    */

    // todo: Hideously inefficient
    bool operator<(const xset& rhs) const
    {
        std::multiset<T> s1;
        InitMultiSet(s1);
        
        std::multiset<T> s2;
        rhs.InitMultiSet(s2);
        
        return s1 < s2;
    }
    bool operator==(const xset& rhs) const
    {
        std::multiset<T> s1;
        InitMultiSet(s1);
        
        std::multiset<T> s2;
        rhs.InitMultiSet(s2);
        
        return s1 == s2;
    }
    bool operator!=(const xset& _rhs) const { return !operator==(_rhs); }
    bool operator<=(const xset& _rhs) const { return !_rhs.operator<(*this); }
    bool operator>(const xset& _rhs) const { return _rhs.operator<(*this); }
    bool operator>=(const xset& _rhs) const { return !operator<(_rhs); }
    
private:
    void InitMultiSet(std::multiset<T>& s) const
    {
        for (const_iterator i = this->begin() ; i != this->end() ; ++i)
        {
            const cref<T>& c = (const cref<T>&) *i;
            s.insert(*c);
        }
    }
};

} // namespace ceda