/*
从一个简单的实例开始：对考试结果进行统计分析（及格率）

int main(int argc, char *argv[])
{
    float scores[STUDENT_COUNT];
    int passed = 0;
    //initialize scores here...
    for (int i = 0; i != STUDENT_COUNT; i++)
    {
        if (scores[i] >= 60)
        {
            passed++;
        }
    }
    cout << "passed rate=" << (float)passed/STUDENT_COUNT << endl;
    return EXIT_SUCCESS;
}

责任分解：把分析单独作为一个功能
void analyze(float *scores, int student_count)
{
    int passed = 0;
    for (int i = 0; i != student_count; i++)
    {
        if （scores[i] >= 60）
            passed++;
    }

    cout << "passing rate = " << (float)passed / student_count << endl;
}

备注：以上传进去的参数是指针，是否可以使用链表代替数组?
如果成绩用单项非循环链表呢？
struct Student
{
    float score;
    Student* next;
};
//..
Student *head;

//如果成绩用单项非循环链表存储？
void analyze(Student *scores)
{
    int passed = 0, count = 0;
    for (Student *p = scores; p ！= NULL; p = p->next)
    {
        if (p->score >= 60)
            passed++;
        count++;
    }

    cout << "passing rate=" << (float)passed/count << endl;
}
//遍历：变与不变
//需要遍历所有学生的成绩（不变），不希望绑定在某种存储方式下（变）
//分离变与不变（存储）与不变（访问）
//把“访问”设计为一个接口,针对不同的存储完成这个接口的不同的实现
for (int i = 0; i != STUDENT_COUNT; i++)
{
//access item by p
}

for (Student *p = scores; p != NULL; p = p->next)
{
//access item by p
}

迭代器：把访问设计成为一个接口
class Iterator
{
public:
    virtual ~Iterator() {}
    virtual bool operator!=(const Iterator &other) const = 0;
    virtual const Iterator& operator++() = 0;
    virtual const Iterator& operator++(int) = 0;
    virtual float& operator*() const = 0;
    virtual float* operator->() const = 0;
    bool operator==(const Iterator &other) const
    {
        return !(*this != other);
    }

};

使用迭代器作为参数传递
void analyze(Iterator *begin, Iterator* end)
{
    int passed = 0, count = 0;
    for    (Iterator* p = begin; *p != *end; (*p)++)
    {
        if (**p >=60)
            passed++;
        count++;
    }
    cout << "passing rate" << (float)passed/count << endl;
}
//需要给存储对象一个约束：能够返回代表头部和尾部的迭代器
//使用“左边闭右开区间，即[begin,end)
class Collection
{
public:
    virtual ~Collection() {}
    virtual Iterator* begin() const = 0;
    virtual Iterator* end() const = 0;
    virtual int size() = 0;
};

int main(int argc, char *argv[])
{
    Collection *collection;
    //initialize collection here...
    analyze(collection->begin(), collection->end());
}

//实现基于数组的集合Collection
class ArrayCollection:public Collection
{
    friend class ArrayIterator;
    float *_data;
    int _size;
public:
    ArrayCollection():_size(10){_data = http://www.mamicode.com/new float0[_size];}"passing rate=" << (float)passed/count << endl;
}

int main(int argc, char **argv[])
{
    float scores[] = {90,20,40,40,20,60,70,30,90,100};
    Collection *collection = new ArrayCollection(10,scores);

    analyze(collection->begin(), collection->end());
    system("PAUSE");
    return EXIT_SUCCESS;
}

//总结：迭代器模式
//提供一种方法顺序访问一个聚合对象中各个元素，而又不需要暴露该对象的内部表示，与对象的内部表示无关（数组还是链表）
//
for （Iterator p = begin; p ！= end; p++）
{
//do something with object *p;
}


//另一种常见的迭代器模式
Iterator it = collection.iterator();
while(it.hasNext())
{
    Object object = it.next();
    //do something with object;
}

变与不变
不变
产生迭代器的方法不变
迭代器遍历集合的接口不变
变：
集合的存储方式可变
迭代器遍历集合的具体实现可变
实现了遍历与存储方法的隔离；
更进一步：把analyze看做一个算法，我们实现了算法和数据存储的隔离
算法--迭代器--数据表示
算法的通用化
设计一系列通用算法
max,min,sort,count,count_if,find...
模板：在编写代码时候留出一些可变的部分（类型），这些部分在使用前必须作出指明，这样，我们就可以使用通用的
算法和数据结构，然后再在使用时予以实例化；
使用模板技术实现泛型；

通用算法：
template <class _iterator>
void analyze(_iterator begin,_iterator end)
{
    int passed = 0, count = 0;
    for    (_iterator p = begin; p != end; p++)
    {
        if (*p >= 60)
            passed++；
        //...
    }
}

数组容器与迭代器
template <class T>
class ArrayCollection
{
    T* _data;
    int _size;
public:
    ArrayCollection():_size(10){_data = http://www.mamicode.com/new T[_size];}"PAUSE");
    return EXIT_SUCCESS;

}
新的类型
考试三科都要高于60分，怎么办？
struct Score
{
    float value[3];
    Score(){}
    Score(float f1,float f2,float f3)
    {
        value[0] = f1;
        value[1] = f2;
        value[2] = f3;
    }
    Score& operator=(const Score& s)
    {
        value[0] = s.value[0];
        value[1] = s.value[1];
        value[2] = s.value[2];
        return *this;
    }
    bool operator>=(float pass)
    {
        return (value[0] >= pass && value[1] >= pass && value[2] >= pass);
    }
};

ostream& operator<<(ostream& out, const Score& s)
{
    out << "{" << s.value[0] << "," << s.value[1] << "," << s.value[2] << "}";
    return out;
}

适应新的类型
int main(int argc, char *argv[])
{
    Score sarray[3];
    sarray[0] = Score(60,60,60);
    sarray[1] = Score(70,70,70);
    sarray[2] = Score(90,80,80);

    ArrayCollection<Score> collection3(3,sarray);
    LinkCollection<Score> collection4(3,sarray);

    analyze(collection3.begin(),collection3.end());
    analyze(collection4.begin(),collection4.end());

    system("PAUSE");
    return EXIT_SUCCESS;
}
算法实际上与“可用的操作相关”，与具体的数据类型无关；

抽象结构和类模板
除了抽象算法外，还有抽象结构：Stack,Linked list,Vector...
这些抽象结构与存储什么数据没有关系，只与数据的存储方式和访问方式相关；
可以借助类模板实现：

template <class T>
struct LinkNode
{
    T _data;
    LinkNode *_next;
    LinkNode():_next(NULL){}
    LinkNode(T data):_data(data),_next(NULL){}
    LinkNode(T data,T* next):_data(data),_next(next){}
};

template <class T>
class LinkedListCollection
{    
    LinkedListNode<T>* _head;
public:
    LinkedListCollection():_head(NULL){}
    ~LinkedListCollection(){clear();}
    bool empty(){return (_head == NULL);}
    void addFirst(const T& data) {_head = new LinkedListNode<T>(data,_head);}
    bool removeFirst() {
    if (_head != NULL)
        {
            LinkedListNode<T>* p = _head;
            _head = _head->_next;
            delete p;
            return true;
        }
    else
        return false;        
    }
}

T* getFirst() { return (_head != NULL) ? &(_head->_data) : NULL;}

LinkedListNode<T>* lastNode()
{
    LinkedListNode<T>* p;
    for    (p = _head; p->_next != NULL; p = p->_next);
    return p;
}

void addLast(const T& data)
{
    if (_head != NULL)
        lastNode()->_next = new LinkedListNode<T>(data);
    else
        _head = new LinkedListNode<T>(data);
}

T* getLast() { return (_head != NULL) ? &(_lastNode()->_data : NULL);}

bool removeLast()
{    
    if (_head != NULL)
    {
        if (_head->_next != NULL)
        {
            LinkedListNode<T>* p;
            for    (p = _head; p->_next->_next != NULL; p = p->_next);
            delete p->_next;
            p->_next = NULL;
            return true;
        }
        else
        {
            delete _head;
            _head = NULL;
            return true;
        }
    }
    else
    {
        return false;
    }
}

void clear()
{
    while(removeFirst());
}

LinkedListIterator<T> begin() {return LinkedListIterator<T>(_head);}
LinkedListIterator<T> end() {return LinkedListIterator<T>(NULL);}

内联函数：
inline int min(int a, int b) { return (a>b) ？ a:b;}
作用：函数内联展开，避免函数调用开销用空间换时间；
在类定义体内定义(实现)的函数缺省为内联函数；

通过模板实例化使用Linked List(抽象结构)
int main(int argc, char *argv[])
{
    LinkedListCollection<Score> collection4;
    for    (int i = 0; i < 3; i++)
        collection4.addFirst(sarray[i]);

    analyze(collection4.begin(),collection4.end());
    //....
    return EXIT_SUCCESS;
}


备注：
不变：算法和抽象结构的接口与实现不变，数据的访问接口不变（迭代器），数据的可用操作不变（操作符重载）；
数据的组织形式可变，数据的类型可变；

实现“算法/抽象结构”与数据表示之间的分离；
泛型编程：先实现算法，再充实数据表示（类型）；


假设算法继续变化
某些科目的及格线不是60分
template<class _iterator> void analyze(_iterator begin,_iterator end)
{
    int passed = 0, count = 0;

    for (_iterator p = begin; p != end; p++)
    {
        if(*p >= 60)
            passed++;
        count++;
    }
    cout << "passing rate= " << (float)passed / count << endl;
}

使用函数指针把判断及格的这个函数传递进去
template <class _iterator>
void analyze(_iterator begin, _iterator end, bool (*isPass)(const _iterator&))
{
    int passed = 0, count = 0;

    for    (_iterator p = begin; p != end; p++)
    {
        if(isPass(p))
        {
            passed++;
        }
        count++;
    }
}

使用函数指针判断及格函数
template <class _Iterator> bool isPass(const _Iterator& p)
{
    return (p->value[0] >= 70 && p->value[1] >= 60 && p->value[2] >= 60);
}//注意这个函数的实现是有缺陷的，只适用于Score类型

int main(int argc, char *argv[])
{
    //...
    analyze(sarray,sarray + 3,isPass<Score *>);//???
    analyze(collection3.begin,collection3.end(),isPass<Score *>);//???
    analyze(collection4.begin,collection4.end(),isPass<LinkedListIterator<Score> >);//????
    //...
}

继续解耦
这两个函数有什么不同吗?
template <class _Iterator> bool isPass(const _Iterator& p)
{
    return (p->value[0] >= 60
    && p->value[1] >= 60 && p->value[2] >= 60);
}

template <class _Iterator> bool isPass(const _Iterator& p)
{
return (p->value[0] >= 70
&& p->value[1] >= 60 && p->value[2] >= 60);
}

如果及格线能够被记住呢？
Score pass(70,60,60);
template <class _Iterator> bool isPass(const _Iterator& p)
{
    return (p->value[0] >= pass.value[0] && 
            p->value[1] >= pass.value[1] &&
            p->value[2] >= pass.value[2]);
}

文件也可以作为函数“记住”数据的另外一种手段
Score pass(70,60,60);
template <class _Iterator>
bool isPass(const _Iterator& p)
{
    float pass1, pass2, pass3;
    ifstream is("passScore.txt");
    is >> pass1 >> pass2 >> pass3;
    return (p->value[0] >= pass1 && p->value[1] >= pass2 && p->value[2] >= pass3);
}
这样的话通过修改passScore.text文件可以轻松地修改及格的分数线；
单一实例的问题依然存在； 
问题在于函数是死的：数据 + 函数 = 对象  函数 + 数据  = 对象

函数调用==（）操作符，还原（）操作符的本意，操作符重载；
函数对象：
通过对函数运算符的重载，我们可以赋予一个对象“函数”的特性，能被调用

template <class _iterator,class T>
class IsPass{
    T _pass;
public:
    IsPass(const T& pass):_pass(pass){}
    bool operator() (const _iterator& p)
    {
        return (*p >= _pass);
    }
};

IsPass就是一个函数对象类模板
算法的定义：

template <class _iterator , class T>
void analyze(_iterator begin, _iterator end, IsPass<_iterator,T> isPass)
{
    int passed = 0, count = 0;
    
    for    (_iterator p = begin; p != end; p++)
        if (isPass(p))
            passed++;
        count++;
}

使用函数对象
int main(int argc, char *argv[])
{
    //...
    sarray[0] = Score(60,60,70);
    sarray[1] = Score(60,60,70);
    sarray[2] = Score(60,60,70);

    ArrayCollection<Score> collection3(3,sarray);
    LinkedListCollection<Score> collection4;
    //....
    analyze(sarray,sarray + 3 ,IsPass<Score*, Score> (Score(70,60,60)));
    analyze(collection3.begin(),collection3.end(),IsPass<Score*,Score>(Score(50,60,60)));
    analyze(collection4.begin(),collection4.end(),IsPass<LinkedListIterator<Score>, Score>(Score(60,60,60)));

}
*/