지침
원형 버퍼, 순환 버퍼, 링 버퍼는 하나의 고정 크기 버퍼를 마치 끝과 끝이 연결된 것처럼 사용하는 자료 구조예요.
원형 버퍼는 처음에는 비어 있고, 미리 정해진 길이를 가져요.
예를 들어 다음은 요소 7개짜리 버퍼예요:
[ ][ ][ ][ ][ ][ ][ ]
버퍼 가운데에 1을 쓴다고 해봐요. (원형 버퍼에서는 정확히 어디에서 시작하는지는 중요하지 않아요.)
[ ][ ][ ][1][ ][ ][ ]
그다음 요소 두 개, 2와 3을 1 뒤에 이어 붙인다고 해봐요:
[ ][ ][ ][1][2][3][ ]
이때 버퍼에서 요소 두 개를 꺼내면, 버퍼 안에서 가장 오래된 값이 꺼내져요.
이 경우 꺼내지는 두 요소는 1과 2이고, 버퍼에는 3만 남아요:
[ ][ ][ ][ ][ ][3][ ]
버퍼에 요소가 7개 있으면 버퍼는 완전히 가득 찬 상태예요:
[5][6][7][8][9][3][4]
버퍼가 가득 차면 오류가 발생해서, 빈 자리가 생길 때까지 더 이상 쓸 수 없다는 것을 클라이언트에 알려줘요.
버퍼가 가득 찼을 때 클라이언트는 강제 쓰기로 가장 오래된 데이터를 덮어쓸 수도 있어요.
이 경우 요소 두 개, A와 B를 추가하면 3과 4를 덮어써요:
[5][6][7][8][9][A][B]
3과 4가 A와 B로 바뀌었으니 이제 버퍼에서 가장 오래된 데이터는 5예요.
마지막으로 요소 두 개를 꺼내면 5와 6이 반환되면서 버퍼는 이렇게 돼요:
[ ][ ][7][8][9][A][B]
빈 공간이 있기 때문에 클라이언트가 다시 덮어쓰기로 C와 D를 저장하면, 7과 8이 있는 자리가 아니라 이전에 5와 6이 저장되어 있던 자리가 사용돼요.
7은 여전히 가장 오래된 요소이고, 버퍼는 다시 가득 찼어요.
[C][D][7][8][9][A][B]
과제
타입 T의 요소를 담는 매개변수화된 복합 타입 CircularBuffer{T}를 정의하고, 다음과 같은 생성자를 작성해요.
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
이 생성자는 최대 capacity개의 요소를 저장할 수 있는 인스턴스를 만들어요.
Base의 다음 함수들을 CircularBuffer에서 동작하도록 확장해요:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): cb의 끝에 요소 item을 삽입한 뒤 cb를 반환해요. cb가 이미 가득 차 있고 overwrite가 false(기본값)라면 BoundsError를 발생시켜요. 그렇지 않고 overwrite가 true라면 item을 위한 자리를 만들기 위해 첫 번째 요소를 제거해요.
-
Base.popfirst!(cb::CircularBuffer): cb의 첫 번째 요소를 제거하고 반환해요.
-
Base.empty!(cb::CircularBuffer): cb에서 모든 요소를 제거한 뒤 비어 있는 cb를 반환해요.
보너스 과제
이 연습 문제는 분량이 꽤 많고 복잡할 수 있어서, 멘토링하기가 더 어렵고 시간도 더 많이 걸려요. 멘토를 돕기 위해, 멘토가 연습 문제의 첫 부분에 대한 풀이를 검토할 때까지는 보너스 과제의 코드를 제출하지 말아 주세요.
CircularBuffer를 확장해서 DataStructures.jl 패키지의 CircularBuffer에 대한 테스트를 통과하도록 해봐요. 이 테스트들은 이 Exercism 연습 문제에 제공된 테스트에 포함되어 있지만 비활성화되어 있어요. 이 테스트를 활성화하려면 파일이나 노트북 맨 위에 enable_bonus_tests = true 한 줄을 추가해요.
이 테스트를 통과하려면 CircularBuffer를 AbstractVector의 하위 타입으로 선언하고, 두 함수를 정의해야 해요:
-
capacity(cb::CircularBuffer): cb의 용량을 반환해요.
-
isfull(cb::CircularBuffer): cb가 가득 찼으면 true를 반환해요.
그다음 Base의 다음 함수들이 CircularBuffer와 함께 올바르게 동작하도록 해야 해요: append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length, size.
힌트: 이 함수들을 전부 확장할 필요도 없고, 확장해서도 안 돼요! CircularBuffer를 AbstractVector의 하위 타입으로 정의하면, AbstractVector용으로 정의된 제네릭 함수들이 이제 CircularBuffer를 입력으로 받아들여요. Julia 매뉴얼의 인터페이스 섹션을 참고해요:
Julia의 강력함과 확장성 중 상당 부분은 비공식 인터페이스 모음에서 나와요. 사용자 정의 타입에서 동작하도록 몇 가지 특정 메서드를 확장하면, 그 타입의 객체는 그 기능들을 받을 뿐만 아니라, 그 동작 위에 일반적으로 쌓아 올리도록 작성된 다른 메서드에서도 사용할 수 있어요.
Julia의 Base 모듈 소스 코드를 살펴보면서 함수 정의를 확인하고, 어떤 것을 확장해야 하는지 알아내야 해요. 함수 호출과 관련된 코드를 찾으려면 @which 매크로를 사용해서 함수 호출이 디스패치되는 특정 메서드를 확인할 수 있어요. 이 매크로는 그 메서드가 정의된 파일과 줄 번호도 보여줘요 (IJulia를 통한 Jupyter Notebook에서는 GitHub의 관련 코드로 가는 링크까지 보여줘요).
REPL에서 작업한다면, 기본 텍스트 편집기에서 관련 파일과 줄을 열어 주는 @edit 매크로를 사용하는 편이 좋아요.
