range.h

C++模板

// StdLibEn.h : main header file for the REGEXP application
//

#if !defined(AFX_RANGE_H__1813340A_0313_4417_8ADB_91370654F595__INCLUDED_)
#define AFX_RANGE_H__1813340A_0313_4417_8ADB_91370654F595__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

// class range template
// class range encapsulate a sequence range: a...b
// open range do not include ehe ends
// [ ] -- close range, include the ends
// ( ) -- open range, not include the ends

#define RANGE_CLOSE_NONE        0
#define RANGE_CLOSE_LEFT        0x01
#define RANGE_CLOSE_RIGHT       0x02
#define RANGE_CLOSE_BOTH        0x03

template<class T>
class range
{
public:
    range(char t = RANGE_CLOSE_NONE)
    {
        m_type = t;
        m_left = m_right;
    }

    range(T b, T e, char t)
    {
        m_type = t;
        set_range(b, e);
    }

    virtual ~range(){}

    void clear()
    {
        m_left = m_right;
        m_type = RANGE_CLOSE_NONE;
    }

    void close_left(bool bclose = true)
    {
        if (bclose)
            m_type |= RANGE_CLOSE_LEFT;
        else
            m_type &= ~RANGE_CLOSE_LEFT;
    }

    void close_right(bool bclose = true)
    {
        if (bclose)
            m_type |= RANGE_CLOSE_RIGHT;
        else
            m_type &= ~RANGE_CLOSE_RIGHT;
    }

    void set_range(T b, T e)
    {
        m_left = b; m_right = e;
        normalize();
    }

    T begin() const
    {
        return m_left;
    }

    T end() const
    {
        return m_right;
    }

    char type() const
    {
        return m_type;
    }

    bool include(T a) const
    {
        return test(a) == 0;
    }

    int test(T a) const
    {
        if (a < m_left
         || a == m_left && !(m_type & RANGE_CLOSE_LEFT)) return -1;
        if (a > m_right
         || a == m_right && !(m_type & RANGE_CLOSE_RIGHT)) return 1;
        return 0;
    }
    
    void normalize()
    {
        if (m_left > m_right)
        {
            T temp = m_left;
            m_left = m_right;
            m_right = temp;
            m_type = ((m_type & RANGE_CLOSE_LEFT) << 1) | ((m_type & RANGE_CLOSE_RIGHT) >> 1);
        }
    }

    bool empty() const
    {
        return (m_left == m_right || adjacent(m_left, m_right)) && RANGE_CLOSE_NONE == m_type;
    }

    const range operator =(const range& r)
    { 
        m_type = r.m_type;
        m_left = r.m_left;
        m_right = r.m_right;
        return *this;
    }

    bool intersected(range& r) const
    {
        range dest;
        return intersect(r, dest);
    }

    bool intersect(range& another, range& result) const
    {
        result.m_type = RANGE_CLOSE_NONE;
        // get the max left
        if (m_left > another.m_left)
        {
            result.m_left = m_left;
            result.m_type |= m_type & RANGE_CLOSE_LEFT;
        }
        else if (m_left == another.m_left)
        {
            result.m_left = m_left;
            result.m_type |= m_type & RANGE_CLOSE_LEFT & another.m_type; // both close
        }
        else
        {
            result.m_left = another.m_left;
            result.m_type |= another.m_type & RANGE_CLOSE_LEFT;
        }

        // get the min right
        if (m_right < another.m_right)
        {
            result.m_right = m_right;
            result.m_type |= m_type & RANGE_CLOSE_RIGHT;
        }
        else if (m_right == another.m_right)
        {
            result.m_right = m_right;
            result.m_type |= m_type & RANGE_CLOSE_RIGHT & another.m_type;
        }
        else
        {
            result.m_right = another.m_right;
            result.m_type |= another.m_type & RANGE_CLOSE_RIGHT;
        }

        if (result.m_left > result.m_right) result.clear();
        else if (result.m_left == result.m_right)
        {
            if (!include(result.m_left) || !another.include(result.m_left)) result.clear();
        }

        return !result.empty();
    }

    // normally, there are two ranges
    // for exmaple exlucde [2, 5] form [1, 9]
    // the result is [1, 2) (stored in the orgine range)  and (5, 9] (stored in rpart)
    // return   true -- exist interscetion
    //          false - not
    bool exclude(range& ex, range& lpart, range& rpart) const
    {
        // get the intersected part
        range inpart;
        if (!intersect(ex, inpart))
        {
            // not intersected, no exclusion
            lpart.clear();
            rpart.clear();
            return false;
        }

        // calculate left part
        lpart = *this;
        lpart.m_right = inpart.m_left;
        lpart.close_left(include(lpart.m_left) && !inpart.include(lpart.m_left));
        lpart.close_right(include(lpart.m_right) && !inpart.include(lpart.m_right));

        // calculate right part
        rpart = *this;
        rpart.m_left = inpart.m_right;
        rpart.close_left(include(rpart.m_left) && !inpart.include(rpart.m_left));
        rpart.close_right(include(rpart.m_right) && !inpart.include(rpart.m_right));
        return true;
    }

    // return true if can cat and succeed to cat
    bool cat(range& another)
    {
        if (!can_cat(another)) return false;

        if (another.empty()) return true;
        if (empty())
        {
            *this = another;
            return true;
        }
        
        // both are not empty
        // get the min left
        if (m_left > another.m_left)
        {
            m_left = another.m_left;
            close_left(another.m_type & RANGE_CLOSE_LEFT);
        }
        else if (m_left == another.m_left)
        {
            m_type |= another.m_type & RANGE_CLOSE_LEFT;
        }

        // get the max right
        if (m_right < another.m_right)
        {
            m_right = another.m_right;
            close_right((another.m_type & RANGE_CLOSE_RIGHT) != 0);
        }
        else if (m_right == another.m_right)
        {
            m_type |= another.m_type & RANGE_CLOSE_RIGHT;
        }

        return true;
    }

    bool can_cat(range& another) const
    {
        if (another.empty() || empty()) return true;

        if (another.m_right < m_left)
        {
            if (adjacent(another.m_right, m_left)
             && (another.m_type & RANGE_CLOSE_RIGHT)
             && (m_type & RANGE_CLOSE_LEFT))
             return true;
        }
        else if (another.m_right == m_left)
        {
            if ((m_type & RANGE_CLOSE_LEFT) 
             || (another.m_type & RANGE_CLOSE_RIGHT)) return true;

            if (another.m_left == another.m_right
             || m_left == m_right) return true;
        }
        else if (another.m_right > m_left && another.m_right <= m_right)
        {
            return true;
        }
        else    //  (another.m_right > m_right)
        {
            if (another.m_left < m_right)
            {
                return true;
            }
            else if (another.m_left == m_right)
            {
                if ((another.m_type & RANGE_CLOSE_LEFT) 
                 || (m_type & RANGE_CLOSE_RIGHT)) return true;

                if (m_left == m_right) return true;
            }
            else    // (another.m_left < m_right)
            {
                if (adjacent(another.m_left, m_right)
                 && (another.m_type & RANGE_CLOSE_LEFT)
                 && (m_type & RANGE_CLOSE_RIGHT))
                return true;
            }
        }

        return false;
    }

public:
private:
    T      m_left, m_right;
    char   m_type;
};

// check the two elements is adjacent or not
// for discrete type such as integer, override it, maybe return true
template<class T>
inline bool adjacent(T t1, T t2)
{ return false; }

template<class T>
inline bool operator <(range<T>& r1, range<T>& r2)
{ return r1.begin() < r2.begin(); }

template<class T>
inline bool operator >(range<T>& r1, range<T>& r2)
{ return r1.m_left > r2.m_left; }

template<class T>
inline bool operator ==(range<T>& r1, range<T>& r2)
{ return r1.m_left == r2.m_left; }

// TCharRange
// override the adjacent function
template<> 
inline bool adjacent<DWORD>(DWORD ch1, DWORD ch2)
{
    return ch2 - ch1 == 1 || ch1 - ch2 == 1;
}

//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_RANGE_H__1813340A_0313_4417_8ADB_91370654F595__INCLUDED_)