学步园

#ifndef EXCEPTIONS_H
#define EXCEPTIONS_H

#include <exception>
#include <iostream>

/**
 * @brief The OutOfBoundary class 越界异常
 */
class OutOfBoundary : public std::exception
{
    friend std::ostream& operator << (std::ostream& os, const std::exception &obj) {
        os << obj.what();
        return os;
    }

public:
    OutOfBoundary() throw(): exception(){}
    ~OutOfBoundary() throw(){}

    const char* what() const throw(){
        return "out of boundary!";
    }

};
/**
 * @brief The BadValue class 坏值异常
 */
class BadValue : public std::exception
{
    friend std::ostream& operator << (std::ostream& os, const BadValue &obj) {
        os << obj.what();
        return os;
    }
public:
    BadValue() throw(): exception(){}
    ~BadValue() throw(){}
    const char* what() const throw(){
        return "bad value!";
    }

};



#endif

#ifndef LIST_H
#define LIST_H

#include <iostream>

template <typename T>
/**
 * @brief The List class 线性表基类
 */
class List
{
public:
    virtual ~List(){}
    virtual void clear() = 0;
    virtual void insert(int i, const T& t) = 0;
    virtual void remove(int i) = 0;
    virtual void traverse(std::ostream &os = std::cout) const = 0;
    virtual int length() const = 0;
    virtual int search(const T& t) const = 0;
    virtual T visit(int i) const = 0;
};

#endif
#ifndef SEQLIST_H
#define SEQLIST_H

#include "list.hpp"
#include "exceptions.hpp"

template <typename T>
/**
 * @brief The SeqList class 顺序实现的线性表
 */
class SeqList : public List<T>
{
public:
    /**
     * @brief The Iterator class 迭代器
     */
    class Iterator
    {
        friend std::ostream& operator << (std::ostream &os, const Iterator &obj) {
            os << *obj.p;
            return os;
        }

    public:
        Iterator(T *_p):p(_p) {}
        Iterator(const Iterator& obj):p(obj.p) {}
        Iterator& operator = (const Iterator& obj) {
            p = obj.p;
            return *this;
        }

        Iterator& operator ++() {
            this->p++;
            return *this;
        }
        Iterator operator ++(int) {
            return  Iterator(this->p++);
        }
        T operator * () {
            return *p;
        }
        T* operator -> () {
            return p;
        }

        bool operator == (const Iterator &ite) {
            return this->p == ite.p;
        }

        bool operator != (const Iterator &ite) {
            return this->p != ite.p;
        }

    private:
        T *p;
    };
    SeqList(int _size = defaultSize);
    ~SeqList();
    void clear();
    int length() const;
    void insert(int i, const T &t);
    int search(const T &t) const;
    T visit(int i) const;
    void traverse(std::ostream &os = std::cout) const;
    void remove(int i);

    int capacity() const {
        return size;
    }

    Iterator begin() const {
        return Iterator(p_d);
    }


    Iterator end() const {
        return Iterator(p_d+index+1);
    }
private:
    enum {defaultSize = 10};
    /**
     * @brief index 当前的下标
     */
    int index;
    /**
     * @brief size 数组的大小
     */
    int size;
    T *p_d;

    void doubleExpand();
};

template <typename T>
SeqList<T>::SeqList(int _size):
    index(-1),
    size(_size)
{
    p_d = new T[size];
}

template <typename T>
SeqList<T>::~SeqList()
{
    delete[] p_d;
}

template <typename T>
void SeqList<T>::clear()
{
    index = -1;
}

template <typename T>
int SeqList<T>::length() const
{
    return (index + 1);
}

template <typename T>
void SeqList<T>::insert(int i, const T &t)//值可以是0~index+1
{
    if (i < 0 || i > index+1) throw BadValue();

    if ((index+2) > size) {
        doubleExpand();
    }
    int j = index;
    while (i <= j) {
        p_d[j+1] = p_d[j];
        --j;
    }
    p_d[i] = t;
    ++index;
}

template <typename T>
void SeqList<T>::doubleExpand()
{
    if (size == 0) {
        size = 1;
    }
    T * t = p_d;
    p_d = new T[size * 2];
    for (int i = 0;i < size;++i) {
        //p_d++ = t++;
        p_d[i] = t[i];
    }
    delete[] t;
    size *= 2;

}

template <typename T>
int SeqList<T>::search(const T &t) const
{
    int re = -1;
    for (int i = 0;i <= index;++i) {
        if (p_d[i] == t) {
            re = i;
        }
    }
    return re;
}
template <typename T>
T SeqList<T>::visit(int i) const
{
    if (i < 0|| i > index) throw OutOfBoundary();
    return p_d[i];
}

template <typename T>
void SeqList<T>::traverse(std::ostream &os) const
{
    for (int i = 0;i <= index;++i) {
        os << p_d[i] << std::endl;
    }
}

template <typename T>
void SeqList<T>::remove(int i)
{
    if (i < 0 || i> index) throw OutOfBoundary();
    while (++i <= index) {
        p_d[i-1] = p_d[i];
    }
    --index;
}


#endif

#include "seqList.hpp"

struct obj {
    int a;
    int b;
    int c;
    obj(int _a = 0, int _b = 0, int _c = 0):
        a(_a),
        b(_b),
        c(_c) {
    }
    friend std::ostream& operator << (std::ostream& os, const obj& o) {
        os << "a->" <<o.a << "b->" << o.b << "c->" << o.c;
        return os;
    }
    bool operator == (const obj& o) {
        return a == o.a && b == o.b && c == o.c;
    }

    obj& operator = (const obj& o) {
        a = o.a;
        b = o.b;
        c = o.c;
        return *this;
    }
};

int main()
{
    //    SeqList<int> seqlist;

    //    seqlist.insert(0,2);
    //    seqlist.insert(1,3);
    SeqList<obj> seqlist;

    obj _1;
    obj _2;
    obj _3;
    std::cout << seqlist.capacity() << std::endl;
    seqlist.insert(0,_1);
    std::cout << seqlist.capacity() << std::endl;
    seqlist.insert(1,_2);
    std::cout << seqlist.capacity() << std::endl;
    seqlist.insert(0,_3);
    std::cout << seqlist.capacity() << std::endl;

    //    std::cout << seqlist.length() << std::endl;

    //    seqlist.traverse();

    //    seqlist.remove(0);

    //    std::cout << seqlist.capacity() <<std::endl;

    //    seqlist.traverse();

    //    std::cout << seqlist.length() << std::endl;
    /*SeqList<int>::Iterator*/ SeqList<obj>::Iterator ite = seqlist.begin();
    for (;ite != seqlist.end();++ite) {
        std::cout << *ite << std::endl;
    }

    // seqlist.traverse();

    return 0;
}