// 📂 LinkedList.js (JavaScript)
// 자바스크립트 클래스를 활용한 단순 연결 리스트 구현

class Node {
    constructor(data) {
        this.data = data;
        this.next = null; // 다음 노드를 가리키는 포인터
    }
}

class LinkedList {
    constructor() {
        this.head = null; // 리스트의 시작점
    }

    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    printList() {
        let current = this.head;
        const result = [];
        while (current) {
            result.push(current.data);
            current = current.next;
        }
        console.log(result.join(" -> "));
    }
}

// 📂 main.js (사용 예시)
// 1. 배열(Array) 사용
const arr = [10, 20, 30];
arr.push(40);
console.log("Array:", arr);

// 2. 연결 리스트(LinkedList) 사용
const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.append(40);
process.stdout.write("LinkedList: ");
list.printList();

// 📂 DataStructures.js (JavaScript)
// 자바스크립트는 배열(Array) 자체에 스택과 큐를 위한 내장 메서드가 모두 존재합니다.

// 1. Stack (LIFO)
class Stack {
    constructor() {
        this.items = [];
    }
    push(element) {
        this.items.push(element); // 배열의 맨 끝에 추가 (O(1))
    }
    pop() {
        return this.items.pop(); // 배열의 맨 끝에서 제거 (O(1))
    }
    peek() {
        return this.items[this.items.length - 1];
    }
}

// 2. Queue (FIFO)
class Queue {
    constructor() {
        this.items = [];
    }
    enqueue(element) {
        this.items.push(element); // 배열의 맨 끝에 추가 (O(1))
    }
    dequeue() {
        // shift()는 O(N)의 시간이 걸리므로 실제로는 연결리스트 기반 큐가 더 효율적입니다.
        return this.items.shift(); // 배열의 맨 앞(0번 인덱스)에서 제거
    }
}

// 실행 예시
const stack = new Stack();
stack.push("A");
stack.push("B");
console.log("Stack Pop:", stack.pop()); // B 출력

const queue = new Queue();
queue.enqueue("1번 손님");
queue.enqueue("2번 손님");
console.log("Queue Dequeue:", queue.dequeue()); // 1번 손님 출력

// 📂 HashTable.js (JavaScript)
// 자바스크립트의 객체(Object)와 Map은 내부적으로 해시 테이블을 사용합니다.
// 여기서는 원리를 이해하기 위해 배열을 이용해 직접 해시 테이블을 구현해 봅니다.

class HashTable {
    constructor(size = 50) {
        this.buckets = new Array(size);
        this.size = size;
    }

    // 간단한 문자열 해시 함수
    _hash(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % this.size;
    }

    // 체이닝(Chaining) 기법을 사용한 데이터 삽입
    set(key, value) {
        const index = this._hash(key);
        if (!this.buckets[index]) {
            this.buckets[index] = [];
        }
        this.buckets[index].push([key, value]);
    }

    // Key를 통해 O(1)에 가까운 속도로 Value 탐색
    get(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        if (bucket) {
            for (let i = 0; i < bucket.length; i++) {
                if (bucket[i][0] === key) {
                    return bucket[i][1];
                }
            }
        }
        return undefined;
    }
}

// 실행 예시
const myHash = new HashTable();
myHash.set("name", "Minstudio");
myHash.set("age", 25);
console.log("Name:", myHash.get("name")); // Minstudio 출력

// 💡 실무에서는 자바스크립트 내장 Map을 쓰는 것이 가장 성능이 좋습니다.
const map = new Map();
map.set("name", "Minstudio");
console.log("Map Output:", map.get("name"));

// 📂 BST.js (JavaScript)
// 클래스를 활용하여 노드(Node)와 이진 탐색 트리(BST)를 구현합니다.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    // 데이터 삽입
    insert(value) {
        const newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return this;
        }
        let current = this.root;
        while (true) {
            if (value === current.value) return undefined; // 중복 허용 안함
            if (value < current.value) { // 작으면 왼쪽으로
                if (current.left === null) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else { // 크면 오른쪽으로
                if (current.right === null) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }

    // 데이터 탐색 (O(log N))
    find(value) {
        if (this.root === null) return false;
        let current = this.root;
        let found = false;
        while (current && !found) {
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            } else {
                found = true; // 찾음!
            }
        }
        return found ? current : false;
    }
}

// 실행 예시
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);

console.log("트리에서 15 탐색:", tree.find(15)); // Node { value: 15, left: null, right: null }
console.log("트리에서 99 탐색:", tree.find(99)); // false

// 📂 MaxHeap.js (JavaScript)
// 자바스크립트는 기본적으로 힙이나 우선순위 큐 내장 객체가 없으므로, 배열을 이용해 직접 구현합니다.

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    // 부모, 왼쪽 자식, 오른쪽 자식 인덱스 계산 공식
    parent(i) { return Math.floor((i - 1) / 2); }
    leftChild(i) { return 2 * i + 1; }
    rightChild(i) { return 2 * i + 2; }

    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

    // 🌟 데이터 삽입 (O(log N))
    push(value) {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }

    // 삽입 후 부모와 비교하며 위로 끌어올림 (Max Heap 성질 복구)
    heapifyUp(i) {
        while (i > 0 && this.heap[this.parent(i)] < this.heap[i]) {
            this.swap(this.parent(i), i);
            i = this.parent(i);
        }
    }

    // 🌟 최댓값 추출 (O(log N))
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const max = this.heap[0]; // 루트 노드(최댓값) 저장
        this.heap[0] = this.heap.pop(); // 맨 끝 노드를 루트로 올림
        this.heapifyDown(0); // 다시 아래로 내리며 정렬
        return max;
    }

    // 루트에서부터 자식과 비교하며 아래로 내려감
    heapifyDown(i) {
        let maxIndex = i;
        const left = this.leftChild(i);
        const right = this.rightChild(i);

        if (left < this.heap.length && this.heap[left] > this.heap[maxIndex]) {
            maxIndex = left;
        }
        if (right < this.heap.length && this.heap[right] > this.heap[maxIndex]) {
            maxIndex = right;
        }

        if (maxIndex !== i) {
            this.swap(i, maxIndex);
            this.heapifyDown(maxIndex);
        }
    }
}

// 실행 예시
const maxHeap = new MaxHeap();
maxHeap.push(15);
maxHeap.push(40);
maxHeap.push(10);
maxHeap.push(50);

console.log("최댓값 추출:", maxHeap.pop()); // 50 출력 (가장 큰 값이 먼저 나옴)
console.log("다음 최댓값 추출:", maxHeap.pop()); // 40 출력

// 📂 Graph.js (JavaScript)
// 그래프는 보통 인접 리스트(Adjacency List) 방식으로 구현합니다. (메모리 절약)

class Graph {
    constructor() {
        this.adjacencyList = {};
    }

    // 정점(Vertex) 추가
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }

    // 간선(Edge) 추가 (무방향 그래프 기준)
    addEdge(v1, v2) {
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1); // 양방향 연결
    }

    // 간선(Edge) 제거
    removeEdge(v1, v2) {
        this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2);
        this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1);
    }

    // 정점(Vertex) 제거
    removeVertex(vertex) {
        while (this.adjacencyList[vertex].length) {
            const adjacentVertex = this.adjacencyList[vertex].pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex];
    }
}

// 🌐 소셜 네트워크(SNS) 친구 관계 그래프 생성
const sns = new Graph();
sns.addVertex("Alice");
sns.addVertex("Bob");
sns.addVertex("Charlie");

sns.addEdge("Alice", "Bob"); // 앨리스와 밥은 친구!
sns.addEdge("Bob", "Charlie"); // 밥과 찰리는 친구!

console.log(sns.adjacencyList);
/*
출력 결과:
{
  Alice: [ 'Bob' ],
  Bob: [ 'Alice', 'Charlie' ],
  Charlie: [ 'Bob' ]
}
*/

// 📂 Trie.js (JavaScript)
// 트라이 노드 클래스: 자식 노드들을 담는 객체와 단어의 끝임을 알리는 플래그를 가집니다.

class TrieNode {
    constructor() {
        this.children = {}; // 알파벳을 키로 하는 자식 노드들
        this.isEndOfWord = false; // 단어의 끝(단어 완성) 여부
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // 🌟 단어 삽입 (Insert)
    insert(word) {
        let current = this.root;
        for (let i = 0; i < word.length; i++) {
            let char = word[i];
            if (!current.children[char]) {
                current.children[char] = new TrieNode(); // 없으면 새로운 노드 생성
            }
            current = current.children[char]; // 다음 노드로 이동
        }
        current.isEndOfWord = true; // 마지막 글자 노드에 단어 끝 표시
    }

    // 🌟 단어 완전 일치 검색 (Search)
    search(word) {
        let current = this.root;
        for (let i = 0; i < word.length; i++) {
            let char = word[i];
            if (!current.children[char]) return false; // 도중에 길이 끊기면 없음
            current = current.children[char];
        }
        return current.isEndOfWord; // 마지막 글자까지 도달했고, 단어의 끝이라면 true
    }

    // 🌟 접두사(Prefix) 검색 (자동완성에 주로 사용됨)
    startsWith(prefix) {
        let current = this.root;
        for (let i = 0; i < prefix.length; i++) {
            let char = prefix[i];
            if (!current.children[char]) return false;
            current = current.children[char];
        }
        return true; // 접두사까지만 무사히 도달하면 true
    }
}

// 🌐 테스트 실행
const trie = new Trie();
trie.insert("apple");
trie.insert("app");

console.log("apple 검색:", trie.search("apple"));   // true
console.log("app 검색:", trie.search("app"));       // true
console.log("appl 검색:", trie.search("appl"));     // false (appl이라는 단어는 등록 안 됨)
console.log("app로 시작하는가?:", trie.startsWith("app")); // true

// 📂 BTreeNode.js (JavaScript)
// B-Tree 노드의 핵심: 여러 개의 키(Keys)와 여러 개의 자식(Children)을 갖습니다.

class BTreeNode {
    constructor(leaf = false) {
        this.keys = [];      // 노드가 가지는 데이터들 (항상 정렬된 상태 유지)
        this.children = [];  // 자식 노드를 가리키는 포인터들
        this.leaf = leaf;    // 단말 노드(맨 아래 노드)인지 여부
    }
}

class BTree {
    constructor(t) {
        this.root = new BTreeNode(true);
        this.t = t; // 최소 차수 (t가 2면 한 노드에 최대 3개의 키가 들어감)
    }

    // 데이터 검색 (이진 탐색 트리와 매우 유사하지만 여러 갈래로 나뉨)
    search(node, key) {
        let i = 0;
        // 1. 현재 노드에서 나보다 크거나 같은 키를 찾을 때까지 오른쪽으로 이동
        while (i < node.keys.length && key > node.keys[i]) {
            i++;
        }

        // 2. 일치하는 키를 찾았다면 바로 해당 노드 반환!
        if (i < node.keys.length && key === node.keys[i]) {
            return { node, index: i };
        }

        // 3. 리프 노드인데도 못 찾았다면 데이터가 없는 것
        if (node.leaf) {
            return null;
        }

        // 4. 자식 노드로 내려가서 다시 재귀적으로 탐색
        return this.search(node.children[i], key);
    }
}

console.log("실제 RDBMS(MySQL 등)의 인덱스 검색은 이와 같은 방식으로 동작합니다.");

// 📂 RBTree.js (JavaScript)
// 레드-블랙 트리의 노드는 항상 '색상(Color)' 정보를 가집니다.

const RED = true;
const BLACK = false;

class Node {
    constructor(key, color = RED) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.parent = null; // 부모를 가리키는 포인터가 회전(Rotation) 시 필수적입니다.
        this.color = color; // 새로 추가되는 노드는 무조건 RED로 시작합니다.
    }
}

class RedBlackTree {
    constructor() {
        this.root = null;
    }

    // 🌟 핵심 원리: 좌회전 (Left Rotate)
    // 오른쪽 자식이 무거워졌을 때, 중심축을 왼쪽으로 기울여 밸런스를 맞춥니다.
    leftRotate(x) {
        let y = x.right;
        x.right = y.left;
        
        if (y.left !== null) y.left.parent = x;
        y.parent = x.parent;
        
        if (x.parent === null) this.root = y;
        else if (x === x.parent.left) x.parent.left = y;
        else x.parent.right = y;
        
        y.left = x;
        x.parent = y;
        console.log(`노드 ${x.key}를 기준으로 좌회전(Left-Rotate) 수행!`);
    }

    // 삽입 로직 (이진 트리 삽입 후 색상 규칙 위반 시 회전 및 색 변환 수행)
    insert(key) {
        // ... (이진 탐색 트리 삽입 코드) ...
        // ... (삽입 후 fixViolation(newNode) 호출하여 RED-RED 충돌 해결) ...
        console.log(`${key} 삽입 후 밸런스를 스스로 맞춥니다.`);
    }
}

const rbt = new RedBlackTree();
rbt.insert(10);
rbt.insert(20);
rbt.insert(30); // 10-20-30 일직선 시 Left-Rotate 발생!

// 📂 BloomFilter.js (JavaScript)
// 해시 함수를 여러 개 사용하여 비트 배열(Bit Array)에 마킹합니다.

class BloomFilter {
    constructor(size = 100) {
        this.size = size;
        this.bitArray = new Array(size).fill(0); // 0으로 초기화된 비트 배열
    }

    // 간단한 해시 함수 3개 (실무에서는 MurmurHash 등 빠르고 고른 해시 사용)
    hash1(item) {
        let hash = 0;
        for (let i = 0; i < item.length; i++) hash += item.charCodeAt(i);
        return hash % this.size;
    }

    hash2(item) {
        let hash = 0;
        for (let i = 0; i < item.length; i++) hash += (item.charCodeAt(i) * 7);
        return hash % this.size;
    }

    hash3(item) {
        let hash = 0;
        for (let i = 0; i < item.length; i++) hash += (item.charCodeAt(i) * 13);
        return hash % this.size;
    }

    // 🌟 데이터 삽입 (비트를 1로 마킹)
    add(item) {
        this.bitArray[this.hash1(item)] = 1;
        this.bitArray[this.hash2(item)] = 1;
        this.bitArray[this.hash3(item)] = 1;
    }

    // 🌟 데이터 존재 여부 확인
    mightContain(item) {
        // 세 개의 해시 결과 위치가 모두 1인지 확인합니다.
        // 단 하나라도 0이라면 "절대 없음(100%)"을 확신할 수 있습니다.
        return this.bitArray[this.hash1(item)] === 1 &&
               this.bitArray[this.hash2(item)] === 1 &&
               this.bitArray[this.hash3(item)] === 1;
    }
}

// 🌐 테스트 실행
const filter = new BloomFilter(100);
filter.add("minstudio");
filter.add("youtube");

console.log("minstudio가 있나요?", filter.mightContain("minstudio")); // true
console.log("netflix가 있나요?", filter.mightContain("netflix"));     // false (없음 확실!)

// 📂 UnionFind.js (JavaScript)
// 1차원 배열(parent) 하나로 모든 집합 관계를 완벽하게 표현합니다.

class UnionFind {
    constructor(size) {
        // 처음에는 자기 자신을 부모로 가리킵니다. (각자 독립된 집합)
        this.parent = Array.from({ length: size }, (_, i) => i);
    }

    // 🌟 Find: 자신이 속한 집합의 대장(Root)을 찾습니다.
    find(x) {
        if (this.parent[x] === x) {
            return x; // 자신이 대장이면 그대로 반환
        }
        // 💡 경로 압축(Path Compression)
        // 대장을 찾는 길에 만나는 모든 노드들이 직접 대장을 가리키게 만듭니다. (속도 극대화)
        this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }

    // 🌟 Union: 두 집합을 하나로 합칩니다.
    union(a, b) {
        let rootA = this.find(a);
        let rootB = this.find(b);

        if (rootA !== rootB) {
            this.parent[rootB] = rootA; // B의 대장을 A의 대장 밑으로 편입시킵니다.
        }
    }

    // 두 노드가 같은 집합에 있는지 확인
    isConnected(a, b) {
        return this.find(a) === this.find(b);
    }
}

// 🌐 테스트 실행
const uf = new UnionFind(10);
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);

console.log("1과 3은 같은 네트워크인가요?", uf.isConnected(1, 3)); // true (1-2-3 연결됨)
console.log("1과 5는 같은 네트워크인가요?", uf.isConnected(1, 5)); // false