gsKnotIterator.h

Go to the documentation of this file.

#pragma once

namespace gismo {

namespace internal {

    template<typename T> class gsKnotIterator;

template <typename T>
class gsUKnotIterator
{
public:
    friend class gsKnotVector<T>;
    friend class gsKnotIterator<T>;

    typedef typename gsKnotVector<T>::mult_t mult_t;    //index_t, gsKnotVector.h:85
    typedef std::random_access_iterator_tag iterator_category;
    typedef const gsKnotVector<T> knotVector;
    typedef T value_type;
    typedef std::ptrdiff_t difference_type;
    typedef const T&       reference;
    typedef const T*       pointer;
    typedef const mult_t*  mltpointer;

private:
    mltpointer m_mlt ; 
    pointer    m_raw ; 
    mult_t     m_upos; 
    mult_t     m_sh  ; 

//#if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
    mult_t m_dbg;// iteration limit: extra member for iterator debugging mode
//#endif

protected:

    // Change the value of the knot - access restricted to friend classes
    // Warning: call GISMO_ASSERT(check()) after using.
    void setValue(const T val)
    {
        std::fill(const_cast<T*>(m_raw) + firstAppearance(),
                  const_cast<T*>(m_raw) + multSum(), val);
    }

public:

    gsUKnotIterator()
    : m_mlt(NULL), m_raw(NULL), m_upos(0), m_sh(0), m_dbg(0)
    { }

    explicit gsUKnotIterator(knotVector & KV, const mult_t upos = 0, const index_t s = 0)
    : m_mlt ( KV.multSumData() ), m_raw ( KV.data() ),
      m_upos( upos             ), m_sh  (s          )
    {
        m_dbg = KV.uSize()+1;
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        //m_dbg = KV.uSize()+1;
        GISMO_ENSURE(upos < m_dbg, "Invalid iterator position "<< upos
                     <<" for knot vector with "<<KV.uSize()<<" unique knots");
#       endif
    }

    static inline gsUKnotIterator End(knotVector & KV)
    {   // the past-the-end position occurs for upos=KV.uSize()
        return gsUKnotIterator(KV, KV.uSize(),KV.numLeftGhosts());
    }

public:

    reference operator*  () const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_upos >= 0 && m_upos + 1 < m_dbg, "Access to invalid knot position.");
#       endif
        return m_raw[m_mlt[m_upos]-1];
    }

    pointer   operator-> () const {return m_raw+m_mlt[m_upos]-1 ;}

    gsUKnotIterator& operator++()
    {
        ++m_upos;
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_upos < m_dbg, "Invalid knot-iterator increment: "
                     << m_upos <<" is past the end position ("<<m_dbg-1<<").");
#       endif
        return *this;
    }

    gsUKnotIterator& operator--()
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_upos > 0 && m_upos < m_dbg, "Invalid knot-iterator decrement");
#       endif
        --m_upos;
        return *this;
    }

    gsUKnotIterator operator++(int) { gsUKnotIterator tmp(*this); ++(*this); return tmp; }
    gsUKnotIterator operator--(int) { gsUKnotIterator tmp(*this); --(*this); return tmp; }

    bool operator == (const gsUKnotIterator& other) const
    { return m_upos == other.m_upos;}// && m_raw == other.m_raw;}

    bool operator != (const gsUKnotIterator& other) const {return m_upos != other.m_upos;}
    bool operator <  (const gsUKnotIterator& other) const {return m_upos <  other.m_upos;}
    bool operator >  (const gsUKnotIterator& other) const {return m_upos >  other.m_upos;}
    bool operator <= (const gsUKnotIterator& other) const {return m_upos <= other.m_upos;}
    bool operator >= (const gsUKnotIterator& other) const {return m_upos >= other.m_upos;}

    reference operator[] (ptrdiff_t a) const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_upos+a>=0 && m_upos+a+1 < m_dbg, "Invalid access to non-existent knot.");
#       endif
        return m_raw[m_mlt[m_upos+a]-1];
    }

    gsUKnotIterator& operator+=(const difference_type & a)
    {
        m_upos += a;
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        // Note: we allow invalid position for iterators on empty knot-vectors
        GISMO_ENSURE(m_dbg<2 || (m_upos >= 0 && m_upos < m_dbg),
                     "Iterator jumped to invalid knot position.");
#       endif
        return *this;
    }

    gsUKnotIterator operator+(const difference_type & a) const
    {
        gsUKnotIterator tmp(*this);
        return tmp+=a;
    }

    gsUKnotIterator& operator-=(const difference_type & a)
    {
        return operator+=(-a);
    }

    gsUKnotIterator operator-(const difference_type & a) const
    {
        gsUKnotIterator tmp(*this);
        return tmp-=a;
    }

    friend difference_type operator-(const gsUKnotIterator & l, const gsUKnotIterator & r)
    {return l.m_upos - r.m_upos; }

    reference value() const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_upos >= 0 && m_upos + 1< m_dbg, "Access to invalid knot position.");
#       endif
        return this->operator*();
    }

    mult_t multiplicity() const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_upos >= 0 && m_upos + 1< m_dbg, "Access to invalid knot position.");
#       endif
        if ( 0 == m_upos )//is it the first unique knot?
            return *m_mlt;
        else
        {
            mltpointer mp = m_mlt + m_upos;
            return *mp - *(mp-1);
        }
    }

    mult_t uIndex() const {return m_upos-m_sh;}

    mult_t uCardinalIndex() const {return m_upos;}

     mult_t firstAppearance() const
    {
        return 0 == m_upos ? 0 : m_mlt[m_upos-1];
    }

    mult_t lastAppearance() const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_upos >= 0 && m_upos + 1< m_dbg, "Access to invalid knot position.");
#       endif
        return m_mlt[m_upos] - 1;
    }

    mult_t multSum() const
    { return m_mlt[m_upos];}

private:

    /*
       \brief Sets the iterator to the first (without repetitions)
       knot in the knot sequence

    // needed ?
    void reset()
    {
        m_upos = 0;
    }
     */
};

template <typename T>
class gsKnotIterator
{
public:
    friend class gsKnotVector<T>;

    typedef typename gsKnotVector<T>::mult_t mult_t;
    typedef std::random_access_iterator_tag iterator_category;
    typedef const gsKnotVector<T> knotVector;
    typedef T value_type;
    typedef std::ptrdiff_t difference_type;
    typedef const T&       reference;
    typedef const T*       pointer;
    typedef const mult_t*  mltpointer;

private:
    gsUKnotIterator<T> m_uit; 
    mult_t             m_pos; 

#if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
    mult_t m_dbg;// iteration limit: extra member for iterator debugging mode
#endif

public:

    gsKnotIterator()
    : m_uit(), m_pos(0)
    { }

    explicit gsKnotIterator(knotVector & KV, const mult_t upos = 0, const index_t s = 0)
    : m_uit(KV,upos,s), m_pos(firstAppearance())
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        m_dbg = KV.size()+1;
        GISMO_ENSURE(static_cast<size_t>(upos) <= KV.uSize(),
                     "Invalid iterator position "<< upos
                     <<" for knot vector with "<<KV.uSize()<<" unique knots");
#       endif
    }

    static inline gsKnotIterator End(const gsKnotVector<T> & KV)
    {   // the past-the-end position occurs for upos=KV.uSize()
        return gsKnotIterator(KV, KV.uSize(),KV.numLeftGhosts());
    }

public:

    reference operator*  () const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_pos >= 0 && m_pos + 1< m_dbg,
                     "Access to invalid knot position.");
#       endif
        return  m_uit.m_raw[m_pos];
    }

    pointer   get()         const {return  m_uit.m_raw+m_pos;}
    pointer   operator-> () const {return  get();}

    gsKnotIterator& operator++()
    {
        if (++m_pos == m_uit.multSum())//crossing interval?
            ++m_uit;
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_pos < m_dbg, "Invalid knot-iterator increment: "
                     << m_pos <<" is past the end position ("<<m_dbg-1<<").");
#       endif
        return *this;
    }

    gsKnotIterator& operator--()
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_pos > 0 && m_pos < m_dbg, "Invalid knot-iterator decrement");
#       endif
        if ( m_pos-- == firstAppearance() )//crossing interval?
            --m_uit;
        return *this;
    }

    gsKnotIterator operator++(int) { gsKnotIterator tmp(*this); ++(*this); return tmp; }
    gsKnotIterator operator--(int) { gsKnotIterator tmp(*this); --(*this); return tmp; }

    bool operator == (const gsKnotIterator& other) const
    { return m_pos == other.m_pos;}// && m_raw == other.m_raw;}

    bool operator != (const gsKnotIterator& other) const {return m_pos != other.m_pos;}
    bool operator <  (const gsKnotIterator& other) const {return m_pos <  other.m_pos;}
    bool operator >  (const gsKnotIterator& other) const {return m_pos >  other.m_pos;}
    bool operator <= (const gsKnotIterator& other) const {return m_pos <= other.m_pos;}
    bool operator >= (const gsKnotIterator& other) const {return m_pos >= other.m_pos;}

    reference operator[] (ptrdiff_t a) const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_pos+a>=0 && m_pos+a+1 < m_dbg, "Invalid access to non-existent knot.");
#       endif
        return m_uit.m_raw[m_pos+a];
    }

    reference operator() (ptrdiff_t a) const
    {
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE(m_pos+a>=0 && m_pos+a+1 < m_dbg, "Invalid access to non-existent knot.");
#       endif
        return m_uit[a];
    }

    const gsUKnotIterator<T> & uIterator() const
    { return m_uit; }

    void uNext()
    {
        ++m_uit;
        m_pos = firstAppearance();
        //m_pos = (m_uit++).multSum();//advance unique position and update m_pos
    }

    void uPrev()
    {
        --m_uit;
        m_pos = firstAppearance();
    }

    void uAdd(const difference_type & a)
    {
        m_uit += a;
        m_pos = firstAppearance();
    }

    gsKnotIterator& operator+=(const difference_type & a)
    {
        m_pos += a;
#       if defined(_GLIBCXX_DEBUG) || _SECURE_SCL != 0
        GISMO_ENSURE((m_pos >= 0 && m_pos < m_dbg),
                     "Iterator jumped to invalid knot position.");
#       endif

        if (a<0) //substracting ?
        {
            mltpointer end = m_uit.m_mlt + m_uit.m_upos;
            mltpointer beg = end + a;
            if (beg < m_uit.m_mlt) beg = m_uit.m_mlt;
            //note: [beg, end) is a valid sorted range, complexity:  O(log a)
            m_uit.m_upos = std::upper_bound(beg, end, m_pos) - m_uit.m_mlt;
        }
        else    //incrementing
        {
            mltpointer beg = m_uit.m_mlt + m_uit.m_upos;
            // O(log a) efficient version
            mltpointer end = std::min(m_uit.m_mlt + m_uit.m_dbg-1, beg + a);
            m_uit.m_upos = std::upper_bound(beg, end, m_pos) - m_uit.m_mlt;

            // unsafe version withoud m_dbg
            //mltpointer end = beg + a; // note: could be over the end of m_mlt
            // while (beg!=end && (*beg)<=m_pos) { ++beg; }
            // m_uit.m_upos = beg - m_uit.m_mlt;
        }

        return *this;
    }

    gsKnotIterator operator+(const difference_type & a) const
    {
        gsKnotIterator tmp(*this);
        return tmp+=a;
    }


    gsKnotIterator& operator-=(const difference_type & a)
    {
        return operator+=(-a);
    }

    gsKnotIterator operator-(const difference_type & a) const
    {
        gsKnotIterator tmp(*this);
        return tmp-=a;
    }

    friend difference_type operator-(const gsKnotIterator & l, const gsKnotIterator & r)
    {return l.m_pos - r.m_pos; }

    reference value() const {return this->operator*();}

    mult_t multiplicity() const
    {
        return m_uit.multiplicity();
    }

    mult_t index() const {return m_pos;}

    mult_t uIndex() const {return m_uit.uIndex();}

    mult_t uCardinalIndex() const {return m_uit.uCardinalIndex();}

     mult_t firstAppearance() const
    { return m_uit.firstAppearance();}

    mult_t lastAppearance() const
    { return m_uit.lastAppearance();}

    mult_t multSum() const
    { return m_uit.multSum();}

    void backToFirstAppearance()
    { m_pos = m_uit.firstAppearance();}

    /*
       \brief Sets the iterator to the first knot in the knot sequence
    // needed ?
    void reset()
    {
        m_pos  = 0;
        m_upos = 0;
    }
     */

};


} // namespace internal



}// namespace gismo