|| [[TableOfContents]] ||
== Python version ==
 * 개발자 : 나휘동
 * 개발방식 : TestDrivenDevelopment
{{{~cpp 
import copy
import string

class CrossReference:
##    def __init__(self, aRoot):
##        self.root = aRoot
##    def find(self, aRoot, aWord):
##        if aRoot.getWord() == aWord:
##            return True
##        elif string.lower(aRoot.getWord()) > aWord and aRoot.left != None:
##            return self.find(aRoot.left, aWord)
##        elif string.lower(aRoot.getWord()) < aWord and aRoot.right != None:
##            return self.find(aRoot.right, aWord)
##        return False

    def getNode(self, aRoot, aWord):
        if  aRoot.getWord() == '' or aRoot.getWord() == aWord:
            return aRoot
        
        if aRoot.left == None:
            aRoot.left = Node('')
            return aRoot.left
        elif string.lower(aRoot.getWord()) > aWord:
            return self.getNode(aRoot.left, aWord)
        
        if aRoot.right == None:
            aRoot.right = Node('')
            return aRoot.right
        elif string.lower(aRoot.getWord()) < aWord:
            return self.getNode(aRoot.right, aWord)
        
    def setNode(self, aRoot, aWord, aLine = '1'):
        node = self.getNode(aRoot, aWord)
        if node == None:
            node = Node(aWord)
        else:
            node.setWord(aWord)
        node.increaseCount()
        node.addLines(aLine)


    def run(self):
        sentence =\
        '''Twas brilling and the slithy toves did gtre and gimble in the wabe'''
        wordList = sentence.split(' ')
        root = Node('')
        for l in wordList:
            self.setNode(root, l)

        print 'Word\t\tCount\t\tLines'
        self.inorder(root)

    def inorder(self, aRoot):
##        print 'start'
        if aRoot.left != None:
##            print 'left'
            self.inorder(aRoot.left)
        if aRoot.word != '':
##            print 'root'
            aRoot.show()
        if aRoot.right != None:
##            print 'right'
            self.inorder(aRoot.right)
        
class Node:
    def __init__(self, aWord = ''):
        self.setWord(aWord)
        self.left = None
        self.right = None

        self.count = 0
        self.lines = ''
    def setWord(self, aWord):
        self.word = aWord
    def increaseCount(self):
        self.count += 1
    def addLines(self, aLine):
        self.lines += aLine + ' '
    def setLeftChild(self, aWord):
        self.left = Node(aWord)
    def setRightChild(self, aWord):
        self.right = Node(aWord)
    def getWord(self):
        return self.word
    def show(self):
        print self.getWord() + '\t\t' + str(self.count) + '\t\t' + self.lines
#########################################################################
            
import unittest

class CrossReferenceTestCase(unittest.TestCase):
##    def testFind(self):
##        t = Node('')
##        t.setWord('Twas')
##        t.setLeftChild('brilling')
##        t.setRightChild('wabe')
##
##        c = CrossReference()
##        self.assertEqual(c.find(t, 'Twas'), True)
##        self.assertEqual(c.find(t, 'brilling'), True)
##        self.assertEqual(c.find(t, 'wabe'), True)
##        self.assertEqual(c.find(t, 'and'), False)
##
##        t.left.setLeftChild('and')
##        self.assertEqual(c.find(t, 'and'), True)

    def testGetNode(self):
        t = Node()
        t.setWord('Twas')
        t.setLeftChild('brilling')
        t.setRightChild('wabe')

        c = CrossReference()

        self.assertEqual(c.getNode(t, 'Twas').getWord(), 'Twas')
        self.assertEqual(c.getNode(t, 'brilling').getWord(), 'brilling')
        self.assertEqual(c.getNode(t, 'wabe').getWord(), 'wabe')
        self.assertEqual(c.getNode(t, 'and').getWord(), '')

        t.left.setLeftChild('and')
        self.assertEqual(c.getNode(t, 'and').getWord(), 'and')

    def testSetNode(self):
        t = Node()
        c = CrossReference()
        c.setNode(t, 'Twas')
        self.assertEqual(c.getNode(t, 'Twas').getWord(), 'Twas')
        c.setNode(t, 'brilling')
        self.assertEqual(c.getNode(t, 'brilling').getWord(), 'brilling')
        c.setNode(t, 'wabe')
        self.assertEqual(c.getNode(t, 'wabe').getWord(), 'wabe')

        c.setNode(t, 'and')

        self.assertEqual(c.getNode(t, 'and').getWord(), 'and')
        self.assertEqual(c.getNode(t, 'and').count, 1)
        self.assertEqual(c.getNode(t, 'and').lines, '1 ')        

if __name__ == '__main__': 
    unittest.main()   
    c = CrossReference()
    c.run()

##    t = Node()
##    c = CrossReference()
##    c.setNode(t, 'Twas')
##    c.setNode(t, 'brilling')
##    c.setNode(t, 'wabe')
##    c.setNode(t, 'and')
##
##    c.inorder(t)

}}}

== C++ version ==
=== [황재선] ===
 * 불필요한 부분 리펙토링 하는 중
 * 배열 변수 제거. string과 동적 할당 이용.
{{{~cpp 
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

struct Line
{
	int row;
	Line * next;
};

struct Node
{
	Node * left;
	string word;
	int wordCount;
	Line * line;
	Node * right;
};

void makeRootNode(Node * aRoot, string aWord);
void initNode(Node * aNewNode);
Node * setNode(Node * ptr, string aWord, int aLineCount);
void insertToNode(Node * ptr, string aWord, int aLineCount);
void duplicatedWord(Node * ptr, string aWord, int aLineCount);
void inorder(Node * aRoot);
void printResult(Node * aRoot);
void freeMem(Node * aRoot);

int count = 0;

int main()
{
	Node * root = new Node;

	ifstream fin("lincoln.txt");
	char word[150];
	
	char split[] = " ,.;-";
	char * p;
	int lineCount = 1;
	int start = true;
	while(!fin.eof())
	{
		fin.getline(word, 150, '\n');
		if(!strcmp(word, ""))
			continue;
		strlwr(word);
		p = strtok(word, split);
		strcpy(word, p);					
		if (start)
		{
			makeRootNode(root, word);
			start = false;
		}
		else
			insertToNode(root, word, lineCount);

		while(p != NULL)
		{
			p = strtok(NULL, split);
			if (p)
			{
				strcpy(word, p);
				insertToNode(root, word, lineCount);
			}
		}
		lineCount++;
	}

	cout << "WORD\t\tCOUNT\t\tLINES" << endl;
	inorder(root);
	cout << "TOTAL\t\t" << count << endl;

	freeMem(root);

	fin.close();

	return 0;
}

void insertToNode(Node * ptr, string aWord, int aLineCount)
{
	bool isDuplicated = false;
	
	while(true)
	{
		if (ptr->word == aWord)
		{
			duplicatedWord(ptr, aWord, aLineCount);
			isDuplicated = true;
			break;
		}
		else if (ptr->word > aWord)
		{
			if (ptr->left != NULL)
				ptr = ptr->left;			
			else
				break;
		}
		else if (ptr->word < aWord)
		{
			if (ptr->right != NULL)
				ptr = ptr->right;
			else
				break;
		}	
	}
				
	if (!isDuplicated)
	{
		if (aWord < ptr->word)
			ptr->left = setNode(ptr, aWord, aLineCount);
		else if (aWord > ptr->word)
			ptr->right = setNode(ptr, aWord, aLineCount);
	}	
}

void initNode(Node * aNewNode)
{
	aNewNode->left = NULL;
	aNewNode->word = "";
	aNewNode->wordCount = 0;

	Line * lp = new Line();
	lp->row = 0;
	lp->next = NULL;

	aNewNode->line = lp;

	aNewNode->right = NULL;
}


void makeRootNode(Node * aRoot, string aWord)
{
	initNode(aRoot);
	
	aRoot->word = aWord;
	aRoot->wordCount++;
	aRoot->line->row = 1;
}

Node * setNode(Node * ptr, string aWord, int aLineCount)
{
	Node * newNode = new Node;
	initNode(newNode);

	newNode->word = aWord;
	newNode->wordCount++;

	newNode->line->row = aLineCount;

	return newNode;
}

void duplicatedWord(Node * ptr, string aWord, int aLineCount)
{
	ptr->wordCount++;
	Line * temp = ptr->line;

	while (temp->next != NULL)
		temp = temp->next;
	Line * lp = new Line();
	lp->row = aLineCount;
	lp->next = NULL;
	temp->next = lp;
}

void inorder(Node * aRoot)
{	
	if(aRoot)
	{
		inorder(aRoot->left);
		printResult(aRoot);
		inorder(aRoot->right);
	}
}

void printResult(Node * aRoot)
{
	count++;
	cout.setf(ios_base::left, ios_base::adjustfield);
	cout.width(18);
	cout << aRoot->word;
	cout << aRoot->wordCount << "\t\t";
	cout.width(3);

	while (aRoot->line->next != NULL)
	{
		cout.width(3);
		cout << aRoot->line->row;
		aRoot->line = aRoot->line->next;
	}
	cout.width(3);
	cout << aRoot->line->row;
	
	cout << "\n";
}

void freeMem(Node * aRoot)
{

	if (aRoot)
	{
		freeMem(aRoot->left);
		freeMem(aRoot->right);
		Line * temp = aRoot->line;
		while (temp->next != NULL)
		{
			temp = aRoot->line->next;
			delete aRoot->line;
			aRoot->line = temp;
		}
		delete aRoot->line;
		delete aRoot;
	}
}
}}}
=== 나휘동 ===
 * 파이선 코드를 바탕으로 짜려고 했으나, 완전히 다르게 되어버려 시간이 더 오래걸렸다.
{{{~cpp 

#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
using namespace std;

// Binary Tree를 구성하는 노드
#define Node_ptr struct Node *

struct Node{
string word;// 노드에 들어있는 값
int count;
string lines;

Node_ptr  left;// Left Child
Node_ptr right;// Right Child
};
/////////////////////////////////////////////////////

// Cross Reference를 작성하기 위한 함수
string toString(int aNum);

Node_ptr * getNode( Node_ptr * aRoot, char aWord[]);
void setNode( Node_ptr * aRoot, char aWord[], int aLine = 1);

void show(ostream & aOs, Node_ptr aNode);
void inorderTravel(ostream & aOs, Node_ptr aRoot);
void showAll(ostream & aOs, Node_ptr aRoot);

void deleteAllNode( Node_ptr aRoot );
/////////////////////////////////////////////////////

int num_of_node = 0;

void main()
{
int line = 1;
const int MAX_LEN = 20;
char word[MAX_LEN];
Node_ptr root = NULL;

ifstream fin("lincoln.txt");
char ch = fin.get();

while(!fin.eof()){

while ( ch == '\n' ){
line++;
do
ch = fin.get();
while ( ch == '\n' );
}

if ( isalpha(ch) ){
for ( int i = 0 ; isalpha(ch) ; i++){
word[i] = (char)tolower(ch);
ch = fin.get();
}
word[i] = '\0';

setNode(&root, word, line);
}
else if ( isspace(ch) || ispunct(ch) == 16)  // 공백이거나 
ch = fin.get();// 알파벳이 아닌 문자일 경우

}
fin.close();

//ofstream fout("result.txt", ios::app); // result.txt 라는 파일에 출력하는 경우
//showAll(fout, root);
//fout.close();

showAll(cout, root);
deleteAllNode(root);
}

Node_ptr * getNode( Node_ptr * aRoot, char aWord[])
{
    if ((*aRoot) == NULL ||  (*aRoot)->word == aWord )
        return aRoot;

// 루트에 있는 단어보다 새로 들어온 단어가 작으면
// 왼쪽 서브트리와 다시 비교한다.
    else if ( (*aRoot)->word > aWord)
        return getNode(&(*aRoot)->left, aWord);

// 루트에 있는 단어보다 새로 들어온 단어가 크면
// 오른쪽 서브트리와 다시 비교한다.
    else if ( (*aRoot)->word < aWord )
return getNode(&(*aRoot)->right, aWord);
    return aRoot;
}

void setNode( Node_ptr * aRoot, char aWord[], int aLine )
{
// 단어를 집어넣을 노드를 가져온다.
Node_ptr * node = getNode(aRoot, aWord);

if ((*node) == NULL){// 빈 노드일 경우
(*node) = new Node;// 노드를 새로 만들고
(*node)->left = NULL;// child 노드를 NULL로 초기화한다.
(*node)->right = NULL;

(*node)->word = aWord;// 노드에 값을 넣는다.
(*node)->count = 1;
(*node)->lines = toString(aLine);
}
else{
(*node)->count++;
(*node)->lines += " ";
(*node)->lines += toString(aLine);
}
}

void inorderTravel(ostream & aOs, Node_ptr aRoot)
{
    if ( aRoot->left != NULL )
inorderTravel(aOs, aRoot->left);

    if ( aRoot->count != 0 ){
show(aOs, aRoot);
num_of_node++;
}

    if ( aRoot->right != NULL )
        inorderTravel(aOs, aRoot->right);
}

void show(ostream & aOs, Node_ptr aNode)
{
aOs << aNode->word << "\t\t";
if ( aNode->word.size() < 8)// 결과를 보기 좋게 탭 개수 조절
aOs << "\t";
if ( aNode->word.size() < 4)
aOs << "\t";
aOs << aNode->count << "\t\t"
<< aNode->lines << endl;
}

void deleteAllNode( Node_ptr aRoot )
{
if ( aRoot->left != NULL )
deleteAllNode( aRoot->left );

if ( aRoot->right != NULL )
deleteAllNode( aRoot->right );

delete aRoot;
}

string toString(int aNum) // 줄수를 string 객체로 바꾸는 함수
{
char * temp;
if ( aNum / 1000 != 0 ){
temp = new char[5];
temp[0] = aNum / 1000 + 48;
temp[1] = aNum % 1000 / 100 + 48;
temp[2] = aNum % 100 / 10 + 48;
temp[3] = aNum % 10 + 48;
temp[4] = '\0';
}

else if ( aNum / 100 != 0 ){
temp = new char[4];
temp[0] = aNum / 100 + 48;
temp[1] = aNum % 100 / 10 + 48;
temp[2] = aNum % 10 + 48;
temp[3] = '\0';
}
else if ( aNum / 10 != 0 ){
temp = new char[3];
temp[0] = aNum / 10 + 48;
temp[1] = aNum % 10 + 48;
temp[2] = '\0';
}

else if ( aNum > 0 ){
temp = new char[2];
temp[0] = aNum + 48;
temp[1] = '\0';
}
string number(temp);
delete temp;
return number;
}


void showAll(ostream & aOs, Node_ptr aRoot)
{
aOs << "WORD" << "\t\t\t" << "COUNT" << "\t\t" << "LINES" << endl
<< "--------------------------------------" << endl;
inorderTravel(aOs, aRoot);
aOs << "--------------------------------------" << endl
<< "TOTAL" << "\t\t" << num_of_node++ << endl;
}
}}}
----
[몸짱프로젝트]