class Hamster::Set

def add(item)
  return self if include?(item)
  self.class.new(@trie.put(item, nil))
end

def all?
  return all? { |item| item } unless block_given?
  each { |item| return false unless yield(item) }
  true
end

def any?
  return any? { |item| item } unless block_given?
  each { |item| return true if yield(item) }
  false
end

def clear
  EmptySet
end

def compact
  remove(&:nil?)
end

def count(&block)
  filter(&block).size
end

def delete(item)
  trie = @trie.delete(item)
  if trie.equal?(@trie)
    self
  else
    self.class.new(trie)
  end
end

def dup
  self
end

def each
  return self unless block_given?
  @trie.each { |entry| yield(entry.key) }
end

def empty?
  @trie.empty?
end

def eql?(other)
  other.is_a?(self.class) && @trie.eql?(other.instance_eval{@trie})
end

def filter
  return self unless block_given?
  trie = @trie.filter { |entry| yield(entry.key) }
  if trie.equal?(@trie)
    self
  elsif trie.empty?
    EmptySet
  else
    self.class.new(trie)
  end
end

def find
  return nil unless block_given?
  each { |item| return item if yield(item) }
  nil
end

def grep(pattern, &block)
  filter { |item| pattern === item }.map(&block)
end

def group_by(&block)
  return group_by { |item| item } unless block_given?
  reduce(Hamster::Hash.new) do |hash, item|
    key = yield(item)
    hash.put(key, (hash.get(key) || EmptySet).add(item))
  end
end

def head
  find { true }
end

def include?(item)
  @trie.has_key?(item)
end

def initialize(trie = Trie.new)
  @trie = trie
end

def inspect
  "{#{to_a.inspect[1..-2]}}"
end

def join(sep = nil)
  to_a.join(sep)
end

def map
  return self unless block_given?
  return self if empty?
  self.class.new(@trie.reduce(Trie.new) { |trie, entry| trie.put(yield(entry.key), nil) })
end

def none?
  return none? { |item| item } unless block_given?
  each { |item| return false if yield(item) }
  true
end

def one?
  return one? { |item| item } unless block_given?
end

def partition(&block)
  return self unless block_given?
  Tuple.new(filter(&block), reject(&block))
end

def product
  reduce(1, &:*)
end

def reduce(memo)
  return memo unless block_given?
  @trie.reduce(memo) { |memo, entry| yield(memo, entry.key) }
end

def remove
  return self unless block_given?
  filter { |item| !yield(item) }
end

def size
  @trie.size
end

def sort(&block)
  Stream.new { Sorter.new(self).sort(&block).to_list }
end

def sort_by(&block)
  return sort unless block_given?
  Stream.new { Sorter.new(self).sort_by(&block).to_list }
end

def sum
  reduce(0, &:+)
end

def to_a
  reduce([]) { |a, item| a << item }
end

def to_list
  reduce(EmptyList) { |list, item| list.cons(item) }
end