<commit_before>// Binary Search Tree
// https://en.wikipedia.org/wiki/Binary_search_tree
//
// The MIT License (MIT)
//
// Copyright (c) 2015 <NAME> <http://github.com/kouky>

import XCPlayground

indirect enum Tree<T: Comparable> {
    case Node(T, Tree<T>, Tree<T>)
    case Empty
    
    func insert(x: T) -> Tree<T> {
        switch self {
        case let .Node(value, left, right) where x <= value:
            return Tree.Node(value, left.insert(x), right)
        case let .Node(value, left, right):
            return Tree.Node(value, left, right.insert(x))
        case .Empty:
            return Tree.Node(x, Tree.Empty, Tree.Empty)
        }
    }
    
    func search(x: T) -> Bool {
        switch self {
        case .Node(x, _, _):
            return true;
        case let .Node(value, left, _) where x < value:
            return left.search(x)
        case let .Node(_, _, right):
            return right.search(x)
        case .Empty:
            return false
        }
    }
    
    func min() -> T? {
        switch self {
        case let .Node(value, Tree.Empty, _):
            return value
        case let .Node(_, left, _):
            return left.min()
        case .Empty:
            return nil
        }
    }
    
    func max() -> T? {
        switch self {
        case let .Node(value, _, Tree.Empty):
            return value
        case let .Node(_, _, right):
            return right.max()
        case .Empty:
            return nil
        }
    }
    
    func delete(x: T) -> Tree<T> {
        switch self {
        case .Node(x, Tree.Empty, Tree.Empty):
           return Tree.Empty
        case .Node(x, let left, Tree.Empty):
           return left.delete(x)
        case .Node(x, Tree.Empty, let right):
           return right.delete(x)
        case .Node(x, let left, let right):
            guard let successor = right.min() else {
                return Tree.Empty
            }
            return Tree.Node(successor, left, right.delete(successor))
        case let .Node(value, left, right) where x <= value:
            return Tree.Node(value, left.delete(x), right)
        case let .Node(value, left, right):
            return Tree.Node(value, left, right.delete(x))
        case .Empty:
            return Tree.Empty
        }
    }
    
    func invert() -> Tree<T> {
        switch self {
        case let .Node(value, left, right):
            return Tree.Node(value, right.invert(), left.invert())
        case .Empty:
            return Tree.Empty
        }
    }
    
    func verify() -> Bool {
        switch self {
        case let .Node(value, left, right):
            return left.verifySmaller(value) && right.verifyLarger(value)
        case .Empty:
            return true
        }
    }
    
    func verifySmaller(parentValue: T) -> Bool {
        switch self {
        case let .Node(value, left, right):
           return value <= parentValue && left.verifySmaller(value) && right.verifyLarger(value)
        case .Empty:
            return true
        }
    }
    
    func verifyLarger(parentValue: T) -> Bool {
        switch self {
        case let .Node(value, left, right):
            return value > parentValue && left.verifySmaller(value) && right.verifyLarger(value)
        case .Empty:
            return true
        }
    }
}

var x = Tree.Empty.insert(10).insert(20).insert(3).insert(15).insert(8)
x.invert()
x.verify()
x.search(5)
x.search(20)
x.delete(10).verify()<commit_msg>BST min and max throw errors<commit_after>// Binary Search Tree
// https://en.wikipedia.org/wiki/Binary_search_tree
//
// The MIT License (MIT)
//
// Copyright (c) 2015 <NAME> <http://github.com/kouky>

import XCPlayground

indirect enum Tree<T: Comparable> {
    case Node(T, Tree<T>, Tree<T>)
    case Empty
    
    func insert(x: T) -> Tree<T> {
        switch self {
        case let .Node(value, left, right) where x <= value:
            return Tree.Node(value, left.insert(x), right)
        case let .Node(value, left, right):
            return Tree.Node(value, left, right.insert(x))
        case .Empty:
            return Tree.Node(x, Tree.Empty, Tree.Empty)
        }
    }
    
    func search(x: T) -> Bool {
        switch self {
        case .Node(x, _, _):
            return true;
        case let .Node(value, left, _) where x < value:
            return left.search(x)
        case let .Node(_, _, right):
            return right.search(x)
        case .Empty:
            return false
        }
    }
    
    func min() throws -> T {
        switch self {
        case let .Node(value, Tree.Empty, _):
            return value
        case let .Node(_, left, _):
            return try! left.min()
        case .Empty:
            throw TreeError.InvalidOperation
        }
    }
    
    func max() throws -> T {
        switch self {
        case let .Node(value, _, Tree.Empty):
            return value
        case let .Node(_, _, right):
            return try! right.max()
        case .Empty:
            throw TreeError.InvalidOperation
        }
    }
    
    func delete(x: T) -> Tree<T> {
        switch self {
        case .Node(x, Tree.Empty, Tree.Empty):
            return Tree.Empty
        case .Node(x, let left, Tree.Empty):
            return left.delete(x)
        case .Node(x, Tree.Empty, let right):
            return right.delete(x)
        case .Node(x, let left, let right):
            let successor = try! right.min()
            return Tree.Node(successor, left, right.delete(successor))
        case let .Node(value, left, right) where x <= value:
            return Tree.Node(value, left.delete(x), right)
        case let .Node(value, left, right):
            return Tree.Node(value, left, right.delete(x))
        case .Empty:
            return Tree.Empty
        }
    }
    
    func invert() -> Tree<T> {
        switch self {
        case let .Node(value, left, right):
            return Tree.Node(value, right.invert(), left.invert())
        case .Empty:
            return Tree.Empty
        }
    }
    
    func verify() -> Bool {
        switch self {
        case let .Node(value, left, right):
            return left.verifySmaller(value) && right.verifyLarger(value)
        case .Empty:
            return true
        }
    }
    
    func verifySmaller(parentValue: T) -> Bool {
        switch self {
        case let .Node(value, left, right):
           return value <= parentValue && left.verifySmaller(value) && right.verifyLarger(value)
        case .Empty:
            return true
        }
    }
    
    func verifyLarger(parentValue: T) -> Bool {
        switch self {
        case let .Node(value, left, right):
            return value > parentValue && left.verifySmaller(value) && right.verifyLarger(value)
        case .Empty:
            return true
        }
    }
}

enum TreeError: ErrorType {
    case InvalidOperation
}

var x = Tree.Empty.insert(10).insert(20).insert(3).insert(15).insert(8)
x.invert()
x.verify()
x.search(5)
x.search(20)
x.delete(10).verify()
{'fraction_non_alphanumeric': 0.12235327554355549, 'fraction_numerical': 0.004831604376865141, 'mean_word_length': 1.6488520888219798, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 39, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3430829', 'n_tokens_mistral': 2130, 'n_tokens_neox': 2086, 'n_words': 572}