dse_classes.hpp

Gramham法求解凸包。从最基本数据结构定义开始实现

#ifndef __DSE_CLASSES_H__
#define __DSE_CLASSES_H__


namespace dse
{
    //##ModelId=443378C800A6
    typedef unsigned int size_t;

    //VC6不支持类内静态常量的初始化附值，
    //这里折中采用了宏定义的方法
    //如果是VC7或者VC8就可以做到一个类里面去了。
    #define DOUBLE_EPS  1.0e-9
    #define PI  3.141592653
    #define NPOS 0xffffffff
    #define IS_ZERO(v) (-DOUBLE_EPS<=(v) && (v)<= DOUBLE_EPS)

    //输出调试信息
    template<typename T> void DPRINTF(T fmt, ...)
    {        
        char tmp[1024];
            va_list ap;
        va_start(ap, fmt);
        _vsnprintf(tmp, sizeof(tmp), fmt, ap);
        va_end(ap);
            OutputDebugStringA(tmp);
    }

    //可变数组
    //##ModelId=443378C800B7
    template<typename T>class array
    {
    private:
        //##ModelId=443378C800C2
        T *items_;      //元素
        //##ModelId=443378C800C3
        size_t size_;   //大小
    public:
        //##ModelId=443378C800CB
        array()
        {
            items_ = NULL;
            size_ = 0;
        }

        //初始化一个大小为n的数组
        //##ModelId=443378C800CC
        array(size_t n)
        {
            if(n != 0)
            {
                items_ = new T[n];
                size_ = n;
            }
            else
            {
                items_ = NULL;
                size_ = 0;
            }
        }

        //##ModelId=443378C800CE
        ~array()
        {
            if(items_)
                delete []items_;
        }

        //返回当前数组大小
        //##ModelId=443378C800CF
        inline size_t size()
        {
            return size_;
        }

        //取得数组第i个元素
        //##ModelId=443378C800D0
        T &operator [](size_t i)
        {
            return items_[i];
        }
    
        //调整数组大小到n
        //如果 n 大于当前大小，则后面的内存不做初始化。
        //如果 n 小于当前大小，则截断超出的元素
        //##ModelId=443378C800D6
        void resize(size_t new_size)
        {
            T *new_items = new T[new_size];
            size_t i = 0;
            while(i < size_ && i < new_size)
            {
                new_items[i] = items_[i];
                i++;
            }

            if(items_)
                delete []items_;

            items_ = new_items;
            size_ = new_size;
        }
    };


    //向量，支持按下标随机访问元素、从尾部添加元素、从尾部删除元素、删除第i个元素
    //##ModelId=443378C800DF
    template<typename T> class vector : public array<T>
    {
        //##ModelId=443378C801E5
        size_t size_;

    public:
        //##ModelId=443378C80201
        typedef T value_type;

        //##ModelId=443378C801E6
        vector()
            : array<T>(1)
        {
            size_ = 0;
        }

        //当前向量的大小
        //##ModelId=443378C801ED
        size_t size()
        {
            return size_;
        }

        //从尾部删除元素
        //##ModelId=443378C801EE
        void pop_back()
        {
            size_ --;
        }

        //清空
        //##ModelId=443378C801EF
        void clear()
        {
            size_ = 0;
        }

        //删除第i个元素
        //##ModelId=443378C801F0
        void erase(size_t i)
        {
            for(size_t j = i + 1; j < size_; j++)
            {
                (*this)[j - 1] = (*this)[j];
            }
            size_ --;
        }

        //从pos位置开始搜索等于t的元素
        //##ModelId=443378C801F8
        void find(T t, size_t pos = 0)
        {
            for(size_t i = pos; i < size_ ; i++)
                if((*this)[i] == t)
                    return i;
            return NPOS;
        }

        //从尾部追加元素
        //##ModelId=443378C801FB
        void push_back(T t)
        {
            if(array<T>::size() == size_)
            {
                //内存递增算法
                //如果当前 size_ 比较小，则翻倍
                //如果当前 size_ 比较大，则线性增长
                //TODO: 试验一个合理的分解点和合理的线性增长量
                if(size_ < 4096)
                    array<T>::resize(size_ * 2);
                else
                    array<T>::resize(size_ + 4096);
            }
            (*this)[size_] = t;
            size_++;
        }
    };

    //通用的数据比较仿函数，比较 a < b 是否成立
    //##ModelId=443378C80203
    template <typename T>class gernic_less
    {
    public:
        //##ModelId=443378C8020C
        bool operator()(const T &a, const T &b)
        {
            return a < b;
        }
    };

    //交换两个变量
    template <typename T> void swap(T &a, T &b)
    {
        T c(a);
        a = b;
        b = c;
    };

    //快速排序算法, a是待排序的数组，low, high为开始，结束元素位置，less为比较仿函数
    //TODO: 对这个原始的快速排序算法改进，提高效率，减少递归栈深度
    template<typename T, typename L> void quick_sort(T &a, int low, int high, L &less)
    { 
        if (low >= high) return; 

        int i = low, j = high;
        T::value_type pv(a[(low + high) / 2]); 

        do
        {
            while (less(a[i], pv)/*(a[i] < pv)*/ && (i < high)) i++;
            while (less(pv, a[j])/*(a[j] > pv)*/ && (j > low)) j--;

            if (i <= j)
                swap(a[i++], a[j--]);

        } while (i <= j);

        if(low < j) quick_sort (a, low, j, less);
        if(high > i) quick_sort (a, i, high, less);
    };

    //二元组, first的类型为T1, second的类型为T2
    //##ModelId=443378C80215
    template<typename T1, typename T2> class pair
    {
    public:
        //##ModelId=443378C80221
        T1 first;
        //##ModelId=443378C80222
        T2 second;

        //##ModelId=443378C80229
        pair()
            : first(), second()
        {

        }
        //##ModelId=443378C8022A
        pair(pair<T1, T2> & other)
            : first(other.first), second(other.second)
        {
        }
        //##ModelId=443378C8022C
        pair(T1 a, T2 b)
            : first(a), second(b)
        {
        }
        //##ModelId=443378C8022F
        pair<T1, T2> & operator = (pair<T1, T2> &other)
        {
            first = other.first;
            second = other.second;
            return *this;
        }
    };

    //构造一个二元组
    template<typename T1, typename T2> pair<T1, T2> make_pair(T1 a, T2 b)
    {
        return pair<T1, T2>(a, b);
    }
};
#endif//__DSE_CLASSES_H__