require 'finite-set'
require 'delegate'
require 'thread'

class AbstractSet
  def self.phi
    Set.phi
  end

  def member?(obj)
    raise NotImplementError.new("need to define `member?'")
  end

  def include?(obj)
    member?(obj)
  end
  alias === include?
  alias has? include?
  alias contains? include?

  def union(other)
    Union.new(Set[self, other])
  end
  alias | union
  alias cup union

  def intersection(other)
    Intersection.new(Set[self, other])
  end
  alias & intersection
  alias cap intersection

  def difference(other)
    Difference.new(self, other)
  end
  alias - difference  

  def complement
    Complement.new(self)
  end

  ##

  def self.strip_adapter(obj)
    while obj.is_a? Adapter
      obj = obj.__getobj__
    end
    obj
  end

  public

  class Composite < AbstractSet
  end

  class Union < Composite
    attr_reader :sets

    class <<self
      alias real_new new

      def new(sets)
        tmp = Set.phi
        sets.each{|s|
          next if s.respond_to? :empty? and s.empty?
          s0 = AbstractSet.strip_adapter(s)
          if s0.is_a? Union
            tmp |= s0.sets
          else
            tmp << s
          end
        }
        sets = tmp

        tmp = sets.separate{|s| s.is_a? Set}
        unless tmp.empty?
          sets = sets - tmp
          sets << tmp.union
        end

        return self.phi if sets.empty?
        return self.pick if sets.singleton?

        result = real_new(sets)

        if p = sets.find{|s| s.respond_to? :pick}
          result = PickableAdapter.new(result, p.pick)
        end
    
        if sets.all?{|s| s.is_a? Enumerable}
          result = EnumerableAdapter::ForUnion.new(result, sets)
        end
    
        result
      end
    end

    def initialize(sets)
      @sets = sets
    end

    def member?(obj)
      @sets.any?{|set| set.member?(obj)}
    end

    #def ==(other)
    #  other.is_a? Union and @sets == other.sets
    #end

    def inspect
      '(' + @sets.collect{|s| s.inspect}.join(' \/ ') + ')'
    end
  end

  class Intersection < Composite
    class <<self
      alias real_new new

      def new(sets)
        if sets.any?{|s| (s.respond_to? :empty? and s.empty?)}
          return AbstractSet.phi
        end

        a = sets.find{|s| s.is_a? Set}
        return a.separate{|item| sets.all?{|s| s.member?(item)}} if a

        return sets.pick if sets.singleton?

        result = real_new(sets)

        a = sets.find{|s|
          s.respond_to? :pick and
            sets.all?{|t| t.member?(s.pick)}
        }
        result = PickableAdapter.new(result, p.pick) if a

        a = sets.find{|s| s.is_a? Enumerable}   
        result = EnumerableAdapter::ForIntersection.new(result, a, sets) if a
    
        result
      end
    end

    def initialize(sets)
      @sets = sets
    end

    def member?(obj)
      @sets.all?{|set| set.member?(obj)}
    end

    def inspect
      '(' + @sets.collect{|s| s.inspect}.join(' /\ ') + ')'
    end
  end

  class Difference < Composite
    class <<self
      alias real_new new

      def new(a,b)
        return a.separate{|item| not b.member?(item)} if a.is_a? Set
        return a if (b.respond_to? :empty? and b.empty?) or
                    (a.respond_to? :empty? and a.empty?)
        return type.phi if a.equal?(b) # XXX

        result = Difference.real_new(a, b)
    
        if a.respond_to? :pick and not b.member?(a.pick)
          result = PickableAdapter.new(result, a.pick)
        end
    
        if a.is_a? Enumerable
          result = EnumerableAdapter::ForDifference.new(result, a, b)
        end
    
        result
      end
    end

    def initialize(a,b)
      @a,@b = a,b
    end

    def member?(obj)
      @a.member?(obj) and not @b.member?(obj)
    end

    def inspect
      format('(%s - %s)', @a.inspect, @b.inspect)
    end
  end

  class Complement < Composite
    class <<self
      alias real_new new

      def new(set)
        if set.is_a? Complement
          set.complement
        else
          real_new(set)
        end
      end
    end

    def initialize(set)
      @base = set
    end

    def complement
      @base
    end

    def member?(obj)
      not @base.member?(obj)
    end
  end

  ##

  Adapter = DelegateClass(AbstractSet)
  class Adapter
    def __getobj__
      @obj
    end
  end

  class EnumerableAdapter < Adapter
    include Enumerable

    def initialize(obj, &each_proc)
      super(obj)
      @each_proc = each_proc
    end

    def each(&y)
      @each_proc.call(y)
    end

    def empty?
      if @obj.respond_to? :empty?
        __getobj__.empty?
      else
        each{return false}
        true
      end
    end

    def pick
      if __getobj__.respond_to? :pick
        __getobj__.pick
      else
        each{|item| return item}
        nil
      end
    end

    class ForUnion < EnumerableAdapter
      def initialize(obj, sets)
        super(obj)
        @sets = sets
      end

      def each
        q = Queue.new
        t = @sets.collect{|set|
          Thread.new{ set.each{|item| q.enq(item); Thread.pass} }
        }
        #t.each{|t0| t0.priority = Thread.current.priority + 1}

        loop{
          while not q.empty?
            yield(q.pop)
          end
          break unless t.any?{|t0| t0.alive?}
          Thread.pass
        }
      end
    end

    class ForIntersection < EnumerableAdapter
      def initialize(obj, base, sets)
        super(obj)
        @base = base
        @sets = sets
      end

      def each
        @base.each{|item|
          yield item if @sets.all?{|s| s.member?(item)}
        }
      end
    end

    class ForDifference < EnumerableAdapter
      def initialize(obj, a, b)
        super(obj)
        @a,@b = a,b
      end

      def each
        @a.each{|item| yield(item) unless @b.member?(item)}
      end
    end
  end


  class PickableAdapter < Adapter
    def initialize(set, picked)
      super(set)
      @picked = picked
    end

    def pick
      @picked
    end
  end
end


class AbstractSet
  class EnumerableWithComplement < AbstractSet
    include Enumerable

    def initialize(enum, complement)
      @s = enum
      @c = complement
    end

    def member?
      require 'generator'
      e = SyncEnumerator.new(self, complement)
      e.each{|a,b|
        return true  if e.end?(1) or obj == a
        return false if e.end?(0) or obj == b
      }
      raise "not found either in self or in complement"
    end
    
    def each(&block)
      @s.each(&block)
    end

    def complement
      EnumerableWithComplement.new(@c, @e)
    end
  end
end


class AbstractSet
  class SortedEnumerable < AbstractSet
    include Enumerable

    def initialize(enum, compare_proc = lambda{|a,b| a<=>b})
      @enum = enum
      @compare_proc = compare_proc
    end

    def member?(obj)
      @enum.each{|item|
        if @compare_proc.call(obj, item) < 0
          break
        elsif item == obj
          return true
        end
      }
      false
    end

    def each(&block)
      @enum.each(&block)
    end
  end
end


if __FILE__ == $0
  class <<Even = AbstractSet.new.extend(Enumerable)
    def member?(obj)
      obj % 2 == 0
    end

    def each
      i = 0
      loop{
        yield i
        i += 2
      }
    end

    def pick
      0
    end

    def empty?
      false
    end
  end

  class <<Odd = AbstractSet.new.extend(Enumerable)
    def member?(obj)
      obj % 2 == 1
    end

    def each
      i = 1
      loop{
        yield i
        i += 2
      }
    end

    def pick
      1
    end

    def empty?
      false
    end
  end

#  p Even & Odd
#  p Even | Odd
#  p Even - Odd

  NaturalNumber = Even | Odd
  p NaturalNumber.member?(1234)
  p ((Even & Set.phi).empty?)
  p ((Even & Set[0,1,1,2,3,5,8,13,21,34]) == Set[0,2,8,34])
  p (AbstractSet::Difference.new(Set[0,1,2,3,5,8,13,21,34], Even) ==
     Set[1,1,3,5,13,21])
  #p (Even | Set[0,1,2] | Set[1,2,3,4])
  p Even.complement.member?(1) == true

  class <<A = Object.new.extend(Enumerable)
    def each
      s = 'a'
      loop{
        yield s
        s.succ!
      }
    end
  end
  a = AbstractSet::SortedEnumerable.new(A, lambda{|a,b| a.size<=>b.size})
  p !a.member?('123')
end