단순 자료구조 (4) - 문자열 (String)

1. 문자열 (String)

String은 문자열을 의미한다. 기본적으로 String 클래스는 내부에 문자배열(char[])로 된 버퍼를 가지고 있고, 이를 조작하는 메소드들을 제공한다. 보통의 자료구조는 이렇다. 내부에 어떤 데이터 버퍼(배열 or 리스트)가 있고, 이 버퍼안에 담긴 데이터를 조작할 수 있는 많은 메소드를 제공한다.

 

2. Simple String

간단하게 구현한 String Class이다. 내부에 mBuffer를 가지고 있고, 배열을 이용하여 구현하였다. buffer는 어레이 리스트로 구현하여 직접 grow() 함수를 구현했고, CharSequence를 implements하여 length(), charAt(int), subSequence(int, int) 등을 추가로 구현하였다.

 

System.out을 이용하기 위해 toString()을 구현했고, 비교를 위한 equals()를 구현하였다. 기타로 추가 add(char) add(char...), add(SimpleString), 삭제 remove(char), removeAt(int), 검색 contains(char), 쪼개기 split(char), 비우기 claer(), 비었는지확인 isEmpty() 등을 구현하였다. 

 

package structures;

import java.util.LinkedList;
import java.util.List;

public class SimpleString implements CharSequence {

    private char[] mBuffer;
    private int capacity;
    private int count = 0;

    public SimpleString(int capacity) {
        this.capacity = capacity;
        this.mBuffer = new char[capacity];
    }

    public SimpleString() {
        this(1);
    }

    public SimpleString(char... chars) {
        this(chars.length);
        add(chars);
    }

    @Override
    public int length() {
        return count;
    }

    @Override
    public char charAt(int index) {
        return mBuffer[index];
    }

    @Override
    public SimpleString subSequence(int start, int end) {
        int size = end - start + 1;
        SimpleString newStrings = new SimpleString(size);
        for (int i = start; i < end + 1; i++) {
            newStrings.add(charAt(i));
        }
        return newStrings;
    }

    @Override
    public String toString() {
        return new String(mBuffer);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj != null) {
            SimpleString otherStrings = ((SimpleString) obj);
            int n = otherStrings.mBuffer.length;
            char chars1[] = mBuffer;
            char chars2[] = otherStrings.mBuffer;
            int i = 0;

            while (n-- != 0) {
                if (chars1[i] != chars2[i])
                    return false;
                i++;
            }
            return true;
        }
        return false;
    }

    private void grow() {
        // array list
        int newSize = mBuffer.length << 1 + 1;
        char[] newBuffer = new char[newSize];

        for (int i = 0; i < mBuffer.length; i++) {
            newBuffer[i] = mBuffer[i];
        }
        this.mBuffer = newBuffer;
        this.capacity = newSize;
    }

    private void add(char ch) {
        if (count == capacity) {
            grow();
        }
        mBuffer[count] = ch;
        count++;
    }

    public void add(char... chars) {
        for (char ch : chars) {
            add(ch);
        }
    }

    public void add(SimpleString strings) {
        add(strings.mBuffer);
    }

    public boolean contains(char ch) {
        for (char buff : mBuffer) {
            if (buff == ch) return true;
            // sequential search
        }
        return false;
    }

    public void removeAt(int index) {
        for (int i = index; i < count; i++) {
            if (i == count - 1) {
                mBuffer[i] = '\0';
            } else {
                mBuffer[i] = mBuffer[i + 1];
            }
        }
        count--;
    }

    public boolean remove(char ch) {
        int index = -1;
        for (int i = 0; i < count; i++) {
            if (mBuffer[i] == ch) {
                index = i;
            }
        }

        if (index != -1) {
            removeAt(index);
            return true;
        }
        return false;
    }

    public void clear() {
        for (int i = 0; i < count; i++) {
            mBuffer[i] = '\0';
        }
        count = 0;
    }

    public boolean isEmpty() {
        return length() == 0;
    }

    public SimpleString[] split(char delimeter) {
        List<Integer> idxs = new LinkedList<>();
        for (int i = 0; i < count; i++) {
            if (delimeter == mBuffer[i]) {
                idxs.add(i);
            }
        }

        int size = idxs.size() + 1;
        SimpleString[] stringArray = new SimpleString[size];

        char[] buffer = new char[count];
        for (int i = 0, j = 0; i < count; i++) {
            if (idxs.contains(i)) {
                stringArray[j] = new SimpleString(buffer);
                buffer = new char[count];
                j++;
            } else if (i == count - 1) {
                stringArray[j] = new SimpleString(buffer);
            } else {
                buffer[i] = mBuffer[i];
            }
        }

        return stringArray;
    }
}