// 面试题50（二）：字符流中第一个只出现一次的字符

// 题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从

// 字符流中只读出前两个字符"go"时，第一个只出现一次的字符是'g'。当从该字

// 符流中读出前六个字符"google"时，第一个只出现一次的字符是'l'。

#include <iostream>

#include <limits>

using namespace std;

class CharStatistics

{

public:

    CharStatistics() : index()//后初始化index=0

    {

        for (int i = ; i < ; ++i)

            occurrence[i] = -;

    }

    void Insert(char ch)

    {

        if (occurrence[ch] == -)//之前没有过，插入index

            occurrence[ch] = index;

        else if (occurrence[ch] >= )//之前出现过，设为-2

            occurrence[ch] = -;

        index++;//用来指示出现过一次的字符的顺序

    }

    char FirstAppearingOnce()

    {

        char ch = '\0';

        int minIndex = numeric_limits<int>::max();//类型int的最大值

        for (int i = ; i < ; ++i)

        {

            if (occurrence[i] >=  && occurrence[i] < minIndex)//对只出现一次的字符进行搜索，找到最先出现的那个值

            {

                ch = (char)i;

                minIndex = occurrence[i];

            }

        }

        return ch;

    }

private:

    // occurrence[i]: A character with ASCII value i;

    // occurrence[i] = -1: The character has not found;

    // occurrence[i] = -2: The character has been found for mutlple times

    // occurrence[i] >= 0: The character has been found only once

    int occurrence[];

    int index;

};

// ====================测试代码====================

void Test(const char* testName, CharStatistics chars, char expected)

{

    if (testName != nullptr)

        printf("%s begins: ", testName);

    if (chars.FirstAppearingOnce() == expected)

        printf("Passed.\n");

    else

        printf("FAILED.\n");

}

int main()

{

    CharStatistics chars;

    Test("Test1", chars, '\0');

    chars.Insert('g');

    Test("Test2", chars, 'g');

    chars.Insert('o');

    Test("Test3", chars, 'g');

    chars.Insert('o');

    Test("Test4", chars, 'g');

    chars.Insert('g');

    Test("Test5", chars, '\0');

    chars.Insert('l');

    Test("Test6", chars, 'l');

    chars.Insert('e');

    Test("Test7", chars, 'l');

    system("pause");

    return ;

}