[Java] Hash Table과 AVL Tree를 이용한 Pattern Matching 1/2

자료구조 / 2002년 2학기 / 문병로 교수님

[설명]
Matching.java
 class HashTable : 해쉬테이블을 구현한 클래스. 직접 구현. 테이블의 각 엔트리는 하나의 AVLTree.
 class AVLTree : AVL트리 구현. 공개되어 있는 소스에서 가져와서 약간씩 수정하였습니다.
               URL : http://www.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java
               트리의 각 노드는 key가 되는 스트링과, LinkedList 형의 data를 갖습니다.
 class LinkedList : (int, int) 형의 data를 갖는 링크드리스트. 직접 구현.
 class Matching : 파일을 읽어 data를 저장하고, 콘솔로부터 입력을 받아 검색하는 작업을 합니다.

[Matching.java 1/2]

import java.io.*;

class HashTable
{
       private static int hashSize = 100;                        // 해쉬테이블의 사이즈입니다. 100으로 설정.
       private AVLTree[] array;                                        // 해쉬테이블의 각 slot은 하나의 AVLTree 입니다.

       public HashTable()
       {
               array = new AVLTree[hashSize];                        // 100개의 AVLTree의 레퍼런스를 만듭니다.
       }

       private int hashing(String s)
       {
               int hashValue = 0;
               for (int i=0; i<s.length(); i++)
                       hashValue += s.charAt(i);
               return hashValue%hashSize;                                // 각 character의 아스키코드 값의 합 mod 100
       }

       public void insert(int strNum, String s)        // 입력의 한 Line을 각각의 substring으로 쪼개서 자료구조에 넣는 작업
       {
               if (s.length() < 6)                                                // 한 Line이 6보다 짧으면 에러
               {
                       System.out.println("Illegal String Length on input file.");
                       System.exit(0);
               }
               String sub;
               int hash;
               for (int i=0; i<s.length() - Matching.k + 1; i++)
               {
                       sub = s.substring(i, i + Matching.k);                        // i번째 index에서 시작하는 길이 6(=Matching.k)인 substring
                       hash = hashing(sub);                                                        // hash function의 값 얻기
                       if (array[hash] == null)                                                // 해당하는 Entry가 비어 있으면
                       {
                               array[hash] = new AVLTree();                                // 새 Tree를 하나 생성하고
                               array[hash].insert(strNum, i+1, sub);                // 그 tree에 (몇번째 줄, 몇번째 칸, substring)을 넘겨주면서 insert
                       }
                       else
                               array[hash].insert(strNum, i+1, sub);                // 비어있지 않으면 바로 그 tree에 insert
               }
       }

       public LinkedList findSub(String key)                                        // 길이가 6인 어떤 string이 존재하는가 검사
       {
               int hash = hashing(key);
               if (array[hash] == null)                                                        // 해당 엔트리가 비었으면 존재하지 않는것!
                       return null;
               else
                       return array[hash].find(key);                                        // 비어있지 않다면 AVLTree에서 찾음.
       }
}

class AVLTree
{
       private TreeNode root;

       public AVLTree ()
       {
               root = null;
       }

       public void insert(int strNum, int index, String s)
       {
               root = insert(root, strNum, index, s);
       }

       private TreeNode insert(TreeNode t, int strNum, int index, String s)                        // Tree에 insert하는 recursive 메쏘드
       {
               if (t == null)                                                                                                // 넣으려는 node가 비었으면
               {
                       LinkedList list = new LinkedList();                                                // 새로운 링크드리스트를 만들고
                       list.insert(strNum, index);                                                                // 현재 data를 리스트에 insert하고
                       t = new TreeNode(s, list);                                                                // 그 list를 현재 node에 삽입
               }
               else if (s.compareTo(t.keyStr) < 0)                                                        // 스트링을 비교해 현재 node보다 사전순서로 앞서 있으면
               {
                       t.left = insert(t.left, strNum, index, s);                                // 왼쪽에 삽입
                       if (height(t.left) - height(t.right) == 2)                                // Tree의 Balancing을 조절하는 루틴
                               if (s.compareTo(t.left.keyStr) < 0)
                                       t = rotateLeft(t);
                               else
                                       t = doubleRotateLeft(t);
               }
               else if (s.compareTo(t.keyStr) > 0)                                                        // symmetric
               {
                       t.right = insert(t.right, strNum, index, s);
                       if (height(t.right) - height(t.left) == 2)
                               if (s.compareTo(t.right.keyStr) > 0)
                                       t = rotateRight(t);
                               else
                                       t = doubleRotateRight(t);
               }
               else                                                                                                                // 이미 같은 string이 저장되어 있으면
                       t.list.insert(strNum, index);                                                        // 그 list의 뒤에 붙임
               t.heightReset();                                                                                        // 현재 node의 height를 리세팅 함.
               return t;
       }

       private int height(TreeNode t)
       {
               return t == null ? -1 : t.height;                                                        // 현재 node의 height를 return
       }

       private TreeNode rotateLeft(TreeNode t)                                                        // 밸런싱을 맞출때 왼쪽으로 로테이트
       {
               TreeNode newNode = t.left;
               t.left = newNode.right;
               newNode.right = t;

               t.heightReset();
               newNode.heightReset();                                                                                // 바뀐 두 노드의 height을 리세팅

               return newNode;
       }

       private TreeNode doubleRotateLeft(TreeNode t)                                        // 더블 로테이트
       {
               t.left = rotateRight(t.left);
               return rotateLeft(t);
       }

       private TreeNode rotateRight(TreeNode t)                                                // symmetric
       {
               TreeNode newNode = t.right;
               t.right = newNode.left;
               newNode.left = t;

               t.heightReset();
               newNode.heightReset();

               return newNode;
       }

       private TreeNode doubleRotateRight(TreeNode t)
       {
               t.right = rotateLeft(t.right);
               return rotateRight(t);
       }

       public LinkedList find(String key)                                                                // 현재 tree내에 해당 string(길이 6)이 있는지 조사
       {
               TreeNode t = root;
               while (t != null)
               {
                       if (key.compareTo(t.keyStr) < 0)
                               t = t.left;
                       else if (key.compareTo(t.keyStr) > 0)
                               t = t.right;
                       else
                               return t.list;                                                                                // 같은것이 발견되면 그 리스트를 리턴
               }
               return null;                                                                                                // 없으면 null을 리턴
       }

       private class TreeNode
       {
               public TreeNode(String s, LinkedList l)
               {
                       keyStr = s;
                       list = l;
                       left = right = null;
                       height = 0;
               }

               private void heightReset()
               {
                       height = max(height(left), height(right)) + 1;                                        // height를 reset함. 양쪽의 height중 높은값 + 1.
               }

               private int max(int x, int y)
               {
                       return x > y ? x : y;
               }

               private String keyStr;                                                                                                // 스트링
               private LinkedList list;                                                                                        // 자료를 저장할 링크드리스트(각 노드마다 존재)
               private TreeNode left, right;                                                                                // 이 노드의 height (아래로 몇 층의 노드가 있는지)
               private int height;
       }
}

class LinkedList
{
       private ListNode head;
       private ListNode current;

       public LinkedList()
       {
               head = new ListNode();
               current = null;
       }

       public void insert(int x, int y)                                                                // 현재 리스트의 맨끝에 노드를 추가함.
       {
               ListNode position = head;
               while (position.link != null)
                       position = position.link;
               position.link = new ListNode(x, y, null);
       }

       public void resetIteration()
       {
               current = head.link;
       }

       public boolean moreToIterate()
       {
               return (current != null);
       }

       public void goToNext()
       {
               if (current != null)
               {
                       current = current.link;
               }
               else
               {
                       System.out.println("Interation Error!");
                       System.exit(0);
               }
       }        

       public boolean isExist(int x, int y)                                                                // 자료중에 (x,y)쌍의 자료가 있는지 확인
       {
               ListNode position = head;
               while (position.link != null)
               {
                       position = position.link;
                       if (position.data1 == x && position.data2 == y)
                               return true;
               }
               return false;
       }

       public int getCurrentData1()
       {
               return current.data1;
       }

       public int getCurrentData2()
       {
               return current.data2;
       }

       private class ListNode                                                                                        // 각 노드는 int 데이타 2개와 링크를 가짐
       {
               private int data1;
               private int data2;
               private ListNode link;

               public ListNode()
               {
                       link = null;
               }

               public ListNode(int x, int y, ListNode linkValue)
               {
                       data1 = x;
                       data2 = y;
                       link = linkValue;
               }
       }
}