Trees

import collections

// Create with default comparison (for numbers, strings)
var tree = collections.new_bst()

// Create with custom comparison function
var custom_tree = collections.new_bst(|a, b| {
    if a < b { return -1 }
    if a > b { return 1 }
    return 0
})

var tree = collections.new_bst()

// Insert numbers
tree.insert(50)
tree.insert(30)
tree.insert(70)
tree.insert(20)
tree.insert(40)
tree.insert(60)
tree.insert(80)

fmt.Println("Tree size:", tree.size())  // 7

// Check if element exists
if tree.contains(40) {
    fmt.Println("Tree contains 40")
}

if !tree.contains(90) {
    fmt.Println("Tree does not contain 90")
}

// Find minimum and maximum values
var min_val = tree.min()
var max_val = tree.max()
fmt.Println("Min:", min_val, "Max:", max_val)  // Min: 20 Max: 80

// Remove specific element
var removed = tree.remove(30)
fmt.Println("Removed 30:", removed)  // true

// Try to remove non-existent element
var not_found = tree.remove(100)
fmt.Println("Removed 100:", not_found)  // false

fmt.Println("Size after removal:", tree.size())

fmt.Println("Tree size:", tree.size())
fmt.Println("Is empty:", tree.is_empty())
fmt.Println("Height:", tree.height())

// Clear all elements
tree.clear()
fmt.Println("After clear:", tree.is_empty())  // true

var tree = collections.new_bst()
var values = [50, 30, 70, 20, 40, 60, 80]
for val in values {
    tree.insert(val)
}

// In-order traversal gives sorted sequence
fmt.Println("In-order traversal:")
var in_order = tree.in_order_traversal()
for val in in_order {
    fmt.Println("  ", val)  // 20, 30, 40, 50, 60, 70, 80
}

// Pre-order: root, left subtree, right subtree
fmt.Println("Pre-order traversal:")
var pre_order = tree.pre_order_traversal()
for val in pre_order {
    fmt.Println("  ", val)  // 50, 30, 20, 40, 70, 60, 80
}

// Post-order: left subtree, right subtree, root
fmt.Println("Post-order traversal:")
var post_order = tree.post_order_traversal()
for val in post_order {
    fmt.Println("  ", val)  // 20, 40, 30, 60, 80, 70, 50
}

// Level-order: visit nodes level by level
fmt.Println("Level-order traversal:")
var level_order = tree.level_order_traversal()
for val in level_order {
    fmt.Println("  ", val)  // 50, 30, 70, 20, 40, 60, 80
}

// Using iterators for memory-efficient traversal
var iter = tree.in_order_iterator()
fmt.Println("Iterator traversal:")
for iter.has_next() {
    var val = iter.next()
    fmt.Println("  ", val)

    // Can break early if needed
    if val > 50 {
        break
    }
}

var tree = collections.new_bst()
for i in range(1, 101) {  // Insert 1 to 100
    tree.insert(i)
}

// Find all values in range [25, 75]
var range_values = tree.range_query(25, 75)
fmt.Println("Values between 25 and 75:", range_values.size())

// Find values less than 50
var less_than_50 = tree.values_less_than(50)
fmt.Println("Values < 50:", less_than_50.size())

// Find values greater than 75
var greater_than_75 = tree.values_greater_than(75)
fmt.Println("Values > 75:", greater_than_75.size())

// Find next larger element
var successor = tree.successor(40)
fmt.Println("Successor of 40:", successor)  // Next larger value

// Find next smaller element
var predecessor = tree.predecessor(40)
fmt.Println("Predecessor of 40:", predecessor)  // Next smaller value

// Get various tree statistics
fmt.Println("Tree height:", tree.height())
fmt.Println("Is balanced:", tree.is_balanced())
fmt.Println("Node count:", tree.size())

// Get depth of specific value
var depth = tree.depth(40)
fmt.Println("Depth of 40:", depth)

// Convert to sorted array
var sorted_array = tree.to_array()
fmt.Println("As sorted array:", sorted_array)

// Create tree from array
var values = [64, 32, 96, 16, 48, 80, 112]
var new_tree = collections.bst_from_array(values)

// Case-insensitive string tree
var string_tree = collections.new_bst(|a, b| {
    var lower_a = a.to_lower()
    var lower_b = b.to_lower()
    if lower_a < lower_b { return -1 }
    if lower_a > lower_b { return 1 }
    return 0
})

string_tree.insert("apple")
string_tree.insert("Banana")
string_tree.insert("cherry")
string_tree.insert("Apple")  // Treated as duplicate due to case-insensitive comparison

var sorted_strings = string_tree.in_order_traversal()
fmt.Println("Sorted strings:", sorted_strings)

struct Person {
    name: string
    age: int
}

// Tree sorted by age
var person_tree = collections.new_bst(|a, b| {
    if a.age < b.age { return -1 }
    if a.age > b.age { return 1 }
    return 0
})

person_tree.insert(Person{name: "Alice", age: 30})
person_tree.insert(Person{name: "Bob", age: 25})
person_tree.insert(Person{name: "Charlie", age: 35})

// Traverse in age order
var people_by_age = person_tree.in_order_traversal()
for person in people_by_age {
    fmt.Println(person.name, "age", person.age)
}

struct Dictionary {
    words: BinarySearchTree
}

function new_dictionary() {
    return Dictionary{
        words: collections.new_bst()
    }
}

function (d *Dictionary) add_word(word) {
    d.words.insert(word.to_lower())
}

function (d *Dictionary) is_valid_word(word) {
    return d.words.contains(word.to_lower())
}

function (d *Dictionary) get_suggestions(prefix) {
    var suggestions = []
    var all_words = d.words.in_order_traversal()

    for word in all_words {
        if word.starts_with(prefix.to_lower()) {
            suggestions.append(word)
        }
    }

    return suggestions
}

function (d *Dictionary) words_in_range(start, end) {
    return d.words.range_query(start.to_lower(), end.to_lower())
}

// Usage
var dict = new_dictionary()
dict.add_word("apple")
dict.add_word("application")
dict.add_word("apply")
dict.add_word("banana")
dict.add_word("band")

fmt.Println("Is 'apple' valid:", dict.is_valid_word("apple"))  // true
fmt.Println("Suggestions for 'app':", dict.get_suggestions("app"))  // [apple, application, apply]
fmt.Println("Words from 'a' to 'b':", dict.words_in_range("a", "b"))

struct Event {
    name: string
    start_time: int  // Unix timestamp
    duration: int    // minutes
}

struct EventScheduler {
    events: BinarySearchTree
}

function new_event_scheduler() {
    return EventScheduler{
        events: collections.new_bst(|a, b| {
            if a.start_time < b.start_time { return -1 }
            if a.start_time > b.start_time { return 1 }
            return 0
        })
    }
}

function (es *EventScheduler) schedule_event(event) {
    // Check for conflicts
    if es.has_conflict(event) {
        return false
    }

    es.events.insert(event)
    return true
}

function (es *EventScheduler) has_conflict(new_event) {
    var new_start = new_event.start_time
    var new_end = new_event.start_time + new_event.duration * 60

    var all_events = es.events.in_order_traversal()
    for event in all_events {
        var event_start = event.start_time
        var event_end = event.start_time + event.duration * 60

        // Check for overlap
        if (new_start < event_end && new_end > event_start) {
            return true
        }
    }

    return false
}

function (es *EventScheduler) get_events_in_range(start_time, end_time) {
    var events_in_range = []
    var all_events = es.events.in_order_traversal()

    for event in all_events {
        if event.start_time >= start_time && event.start_time <= end_time {
            events_in_range.append(event)
        }
    }

    return events_in_range
}

function (es *EventScheduler) get_next_event(current_time) {
    var all_events = es.events.in_order_traversal()
    for event in all_events {
        if event.start_time > current_time {
            return event
        }
    }
    return null
}

// Usage
var scheduler = new_event_scheduler()
var meeting1 = Event{name: "Team Meeting", start_time: 1640995200, duration: 60}
var meeting2 = Event{name: "Client Call", start_time: 1640998800, duration: 30}

fmt.Println("Scheduled meeting1:", scheduler.schedule_event(meeting1))  // true
fmt.Println("Scheduled meeting2:", scheduler.schedule_event(meeting2))  // true

var conflicting = Event{name: "Conflict", start_time: 1640996000, duration: 60}
fmt.Println("Scheduled conflicting:", scheduler.schedule_event(conflicting))  // false

struct Record {
    id: int
    name: string
    data: any
}

struct DatabaseIndex {
    primary_index: BinarySearchTree    // Index by ID
    name_index: BinarySearchTree       // Index by name
    records: Map                       // Actual record storage
}

function new_database_index() {
    return DatabaseIndex{
        primary_index: collections.new_bst(|a, b| {
            if a.id < b.id { return -1 }
            if a.id > b.id { return 1 }
            return 0
        }),
        name_index: collections.new_bst(|a, b| {
            if a.name < b.name { return -1 }
            if a.name > b.name { return 1 }
            return 0
        }),
        records: collections.new_map()
    }
}

function (db *DatabaseIndex) insert_record(record) {
    // Check if ID already exists
    if db.primary_index.contains(record) {
        return false  // Duplicate ID
    }

    // Insert into indexes
    db.primary_index.insert(record)
    db.name_index.insert(record)

    // Store actual record
    db.records.set(record.id, record)

    return true
}

function (db *DatabaseIndex) find_by_id(id) {
    var dummy = Record{id: id, name: "", data: null}
    if db.primary_index.contains(dummy) {
        return db.records.get(id)
    }
    return null
}

function (db *DatabaseIndex) find_by_name(name) {
    var dummy = Record{id: 0, name: name, data: null}
    if db.name_index.contains(dummy) {
        // Linear search through name index to find actual record
        var name_records = db.name_index.in_order_traversal()
        for record in name_records {
            if record.name == name {
                return db.records.get(record.id)
            }
        }
    }
    return null
}

function (db *DatabaseIndex) find_records_in_id_range(min_id, max_id) {
    var min_record = Record{id: min_id, name: "", data: null}
    var max_record = Record{id: max_id, name: "", data: null}

    var range_records = db.primary_index.range_query(min_record, max_record)
    var results = []

    for record in range_records {
        results.append(db.records.get(record.id))
    }

    return results
}

function (db *DatabaseIndex) delete_record(id) {
    var record = db.find_by_id(id)
    if record != null {
        db.primary_index.remove(record)
        db.name_index.remove(record)
        db.records.remove(id)
        return true
    }
    return false
}

// Usage
var db = new_database_index()
db.insert_record(Record{id: 1, name: "Alice", data: {"age": 30}})
db.insert_record(Record{id: 3, name: "Charlie", data: {"age": 25}})
db.insert_record(Record{id: 2, name: "Bob", data: {"age": 35}})

var alice = db.find_by_name("Alice")
fmt.Println("Found Alice:", alice.id, alice.data)

var records_1_to_2 = db.find_records_in_id_range(1, 2)
fmt.Println("Records 1-2:", records_1_to_2.size())

struct ExpressionNode {
    value: string
    left: ExpressionNode
    right: ExpressionNode
    is_operator: bool
}

function new_expression_node(value, is_operator) {
    return ExpressionNode{
        value: value,
        left: null,
        right: null,
        is_operator: is_operator
    }
}

struct ExpressionTree {
    root: ExpressionNode
}

function build_expression_tree(postfix_tokens) {
    var stack = collections.new_stack()

    for token in postfix_tokens {
        if is_operator(token) {
            var node = new_expression_node(token, true)
            node.right = stack.pop()
            node.left = stack.pop()
            stack.push(node)
        } else {
            var node = new_expression_node(token, false)
            stack.push(node)
        }
    }

    return ExpressionTree{root: stack.pop()}
}

function (et *ExpressionTree) evaluate() {
    return evaluate_node(et.root)
}

function evaluate_node(node) {
    if node == null {
        return 0
    }

    if !node.is_operator {
        return node.value.to_int()
    }

    var left_val = evaluate_node(node.left)
    var right_val = evaluate_node(node.right)

    switch node.value {
        case "+": return left_val + right_val
        case "-": return left_val - right_val
        case "*": return left_val * right_val
        case "/": return left_val / right_val
        default: return 0
    }
}

function (et *ExpressionTree) to_infix() {
    return infix_traversal(et.root)
}

function infix_traversal(node) {
    if node == null {
        return ""
    }

    if !node.is_operator {
        return node.value
    }

    return "(" + infix_traversal(node.left) + " " + node.value + " " + infix_traversal(node.right) + ")"
}

// Usage
var postfix = ["3", "4", "+", "2", "*"]  // (3 + 4) * 2
var expr_tree = build_expression_tree(postfix)
fmt.Println("Result:", expr_tree.evaluate())      // 14
fmt.Println("Infix:", expr_tree.to_infix())       // ((3 + 4) * 2)

// Worst case: inserting sorted data creates a linear tree
var bad_tree = collections.new_bst()
for i in range(1, 1001) {
    bad_tree.insert(i)  // Creates right-skewed tree, O(n) operations
}

// Better: insert in random order or use self-balancing tree
var values = range(1, 1001).shuffle()
var good_tree = collections.new_bst()
for val in values {
    good_tree.insert(val)  // More balanced, closer to O(log n)
}

// Check balance
fmt.Println("Bad tree height:", bad_tree.height())    // ~1000
fmt.Println("Good tree height:", good_tree.height())  // ~10

var tree = collections.new_bst()

// Operations on empty tree
var min_result = tree.min()
if min_result == null {
    fmt.Println("Tree is empty")
}

// Remove non-existent element
var removed = tree.remove(100)
fmt.Println("Removed 100:", removed)  // false

// Invalid comparison function
var invalid_tree = collections.new_bst(|a, b| {
    // Inconsistent comparison can break BST property
    return random_int(-1, 1)  // Don't do this!
})

// Good: comparable data types
var number_tree = collections.new_bst()  // Numbers
var string_tree = collections.new_bst()  // Strings

// Provide comparison for custom types
var custom_tree = collections.new_bst(comparison_function)

// Avoid sorted input for better balance
var values = [1, 2, 3, 4, 5, 6, 7]  // Bad: creates skewed tree
values.shuffle()  // Better: random order

var tree = collections.new_bst()
for val in values {
    tree.insert(val)
}

// Use in-order for sorted output
var sorted = tree.in_order_traversal()

// Use level-order for breadth-first processing
var level_order = tree.level_order_traversal()

// Use iterators for memory efficiency
var iter = tree.in_order_iterator()

// Check balance periodically
if tree.height() > 2 * log2(tree.size()) {
    fmt.Println("Tree may be unbalanced")
    // Consider rebuilding or using self-balancing tree
}

// For concurrent access, use appropriate synchronization
var shared_tree = collections.new_concurrent_bst()
// Or implement proper locking around tree operations