// 알고리즘 헬퍼의 인터페이스(추상클래스)를 구현하세요. (상속 직후의 초기 상태입니다.)
public class AvlTree extends BinarySearchTree<Integer, String> {
    @Override
    protected Node<Integer, String> getRoot() {
        return null;
    }

    @Override
    protected void setRoot(Node<Integer, String> node) {
    }

    @Override
    protected void doSave(@NonNull Node<Integer, String> node) {
    }

    @Override
    public Optional<Node<Integer, String>> findNode(@NonNull Integer key) {
        return Optional.empty();
    }

    @Override
    protected void doDelete(@NonNull Integer key) {
    }

    @Override
    public void inOrder(Consumer<Node<Integer, String>> consumer) {
    }
}

// 구현하실 추상메서드의 바깥에서는 입력, 상태, 구현 등을 검증합니다.
public abstract class BinarySearchTree<K extends Comparable<K>, V> {
    // 템플릿메서드
    public void save(@NonNull K key, @NonNull V value) {
        ValidateUtil.validateKey(getRoot(), key); // 키 중복 검증
        doSave(new Node<>(key, value)); // 추상메서드
        ValidateUtil.validateBst(getRoot()); // 정렬 검증
    }

    // 추상메서드
    protected abstract void doSave(@NonNull Node<K, V> node);
}

// 데이터생성기, 프로파일러, 미리 구현된 출력 메서드와 함께 테스트를 꼭 작성하세요.
class AvlTreeTest {
    @Test
    void find() {
        // n에 따라 항상 동일하게 섞인 정수 리스트 생성
        Integers integers = IntegersFactory.stablyShuffled(1000, true);
        // 원하는 타입의 리스트로 변환
        List<Node<Integer, String>> nodes = integers.toTypeList(i -> new Node<>(i, Integer.toHexString(i)));

        // 프로파일러를 프록시로 사용
        BinarySearchTree<Integer, String> bst = new BinarySearchTreeProfiler<>(new AvlTree());
        // 테스트 전 데이터 입력 및 진행 상황 로깅
        BinarySearchTreeUtil.saveDataLoggingProgress(bst, nodes, 100);

        // 테스트 데이터 리스트의 중앙 값
        Integer key = integers.getMid();
        // When
        Object value = bst.findValue(key).orElse(null);
        // Then
        assertEquals(Integer.toHexString(key), value);

        // 트리 형태로 노드의 toString() 출력
        bst.print(Node::toString);
        // 루트부터 리프까지의 모든 경로 출력
        bst.printPaths();
    }
}
        /*  개략적인 로그
            > Integers created in 1 ms.
            > [8, 14, 7, 13, 6, 12, 5, 11, 4, 10, 2, 3, 9, 1]
            
            data 0 saved.
            data 5 saved.
            data 10 saved.
            > BST Initialized in 8 ms.
            
            > Node 11 found in 0 ms.
              Path: 8 - 11
            
            > Print Tree
                                 ( 8:8)                     
                     ( 4:4)                  (11:b)         
               ( 2:2)      ( 6:6)      (10:a)      (13:d)   
            ( 1:1)( 3:3)( 5:5)( 7:7)( 9:9)(    )(12:c)(14:e)
            
            > Print paths
               8 -  4 -  2 -  1
               8 -  4 -  2 -  3
               8 -  4 -  6 -  5
               8 -  4 -  6 -  7
               8 - 11 - 10
               8 - 11 - 10 -  9
               8 - 11 - 13 - 12
               8 - 11 - 13 - 14
         */

<dependency>
    <groupId>com.github.suloginscene</groupId>
    <artifactId>algorithm-helper</artifactId>
    <version>1.0.5</version>
</dependency>

public class SortImpl extends Sort {
    @Override
    protected void doExecute(int[] array) {
    }
}

public class BinarySearchTreeImpl<K extends Comparable<K>, V> extends BinarySearchTree<K, V> {
    @Override
    protected Node<K, V> getRoot() {
        return null;
    }

    @Override
    protected void setRoot(Node<K, V> node) {
    }

    @Override
    protected void doSave(@NonNull Node<K, V> node) {
    }

    @Override
    public Optional<Node<K, V>> findNode(@NonNull K key) {
        return Optional.empty();
    }

    @Override
    protected void doDelete(@NonNull K key) {
    }

    @Override
    public void inOrder(Consumer<Node<K, V>> consumer) {
    }
}

public class GraphImpl<V> extends Graph<V> {
    @Override
    protected Map<V, Set<V>> getVertexMap() {
        return null;
    }

    @Override
    protected Map<Edge<V>, Edge<V>> getEdgeMap() {
        return null;
    }

    @Override
    public void bfs(@NonNull V start, Consumer<V> consumer) {
    }

    @Override
    public void dfs(@NonNull V start, Consumer<V> consumer) {
    }

    @Override
    protected void doTopologicalSort(Consumer<V> consumer) {
    }

    @Override
    protected Map<V, Course<V>> doShortestCourses(@NonNull V start) {
        return null;
    }

    @Override
    protected Graph<V> doMinimumSpanningTree() {
        return null;
    }
}

public class EncoderImpl extends Encoder {
    @Override
    protected List<String> tokenize(String text) {
        return null;
    }

    @Override
    protected Map<String, String> mapTokenCode(List<String> tokens) {
        return null;
    }
}