# Documentation: https://github.com/monzita/algorithmix/wiki/BinaryHeap

module Algorithmix
  module DataStructure
    module Heap

      class BinaryHeap

        # Creates a new binary heap.
        #
        # @param obj [#to_a] can be any object, which responds to #to_a method. By default is set to nil.
        # @kwarg copy [true, false] if is set to true, content of the object will be copied into content of the new heap. 
        #                           By default is set to false.
        # @kwarg min [true, false] defines the type of the new heap, be default min is set to false
        # @raise ArgumentError, if given object doesn't respond to #to_a method.
        # @return [BinaryHeap] a newly created binary heap
        def initialize(obj = nil, copy: false, min: false)
          @container = []
          @max = min ? false : true
          obj.nil? ? nil : from_obj(obj, copy)
        end

        # Assigns content of an object, to content of the heap.
        #
        # @param obj [#to_a] can be any object, which responds to #to_a method. By default is set to nil.
        # @kwarg copy [true, false] if is set to true, content of the object will be copied into content of the new heap. 
        #                           By default is set to false.
        # @raise ArgumentError, if given object doesn't respond to #to_a method.
        # @return [BinaryHeap] self object
        def assign(obj, copy: false)
          from_obj(obj, copy)
        end

        # Inserts a value in the heap.
        #
        # @param value
        # @return [BinaryHeap] self object
        def insert(value)
          @container << value
          sift_up(@container.size - 1)
          self
        end

        # (see #insert)
        def <<(value)
          insert(value)
        end

        # Removes top element of the heap.
        #
        # @raise Algorithmix::EmptyContainerError, if the heap is empty.
        # @return top element of the heap.
        def extract
          raise EmptyContainerError, "The Binary heap is empty." if @container.empty?
          @container[0], @container[@container.length - 1] = @container[@container.length - 1], @container[0]
          value = @container.pop
          heapify(0)
          value
        end

        # Returns top element of the heap, without removing it.
        #
        # @return top element.
        def top
          @container.first
        end

        # Returns number of elements in the heap.
        def size
          @container.size
        end

        # (see #size)
        def length
          @container.size
        end

        # Returns information for current ...
        def empty?
          @container.empty?
        end

        # Increases a value in the heap, if current heap is set to be max heap.
        #
        # @kwarg idx [Integer] any integer, which can represent index at an array.
        # @krarg old_value 
        # @kwarg new_value
        # @raise TypeError, if current heap has type min heap
        # @raise ArgumentError, if idx or old_value are not provided
        # @raise ArgumentError, if new_value is not provided
        # @return [BinaryHeap] self object
        def increase_key(idx: nil, old_value: nil, new_value: nil)
          raise TypeError, "Undefined method BinaryHeap#increase_key for MinBinaryHeap" if !@max
          raise ArgumentError, "At least one of both options must be provided." if idx.nil? && old_value.nil?
          raise ArgumentError, ":new_value cannot be nil." if new_value.nil?

          idx = idx.nil? && !old_value.nil? ? @container.index(old_value) : idx
          raise ArgumentError, "Element at position #{idx} doesn't exist." if idx.nil? || @container[idx].nil?
          change_key(idx, new_value, increase: true)
          
          self
        end


        # Decreases a value in the heap, if current heap is set to be min heap.
        #
        # @kwarg idx [Integer] any integer, which can represent index at an array.
        # @krarg old_value 
        # @kwarg new_value
        # @raise TypeError, if current heap has type max heap
        # @raise ArgumentError, if idx or old_value are not provided
        # @raise ArgumentError, if new_value is not provided
        # @return [BinaryHeap] self object
        def decrease_key(idx: nil, old_value: nil, new_value: nil)
          raise TypeError, "Undefined method BinaryHeap#decrease_key for MaxBinaryHeap" if @max
          raise ArgumentError, "At least one of both options must be provided." if idx.nil? && old_value.nil?
          raise ArgumentError, ":new_value cannot be nil." if new_value.nil?

          idx = idx.nil? && !old_value.nil? ? @container.index(old_value) : idx
          raise ArgumentError, "Element at position #{idx} doesn't exist." if idx.nil? || @container[idx].nil?
          change_key(idx, new_value)

          self
        end

        # Compares contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap.
        # @return [true, false] true if heaps are equal, false otherwise
        def ==(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#== for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          @container == binary_heap.to_a
        end

        # (see #==)
        def eql?(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#eql? for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self == binary_heap
        end

        # Compares contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap.
        # @return [true, false] false if heaps are equal, true otherwise
        def !=(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#!= for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          @container != binary_heap.to_a
        end

        # (see #!=)
        def diff?(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#diff? for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self != binary_heap
        end

        # Compares contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap.
        # @return 
        # => 1 if content of the heap is greater than content of the given heap
        # => 0 if contents are equal
        # => -1 if content of the given heap is greater than content of the heap
        def <=>(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#<=> for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          @container <=> binary_heap.to_a
        end

        # Concatenates contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] a new binary heap
        def +(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#+ for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
        
          BinaryHeap.new(@container + binary_heap.to_a, min: !@max)
        end

        # (see #+)
        def concat(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#concat for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self + binary_heap
        end

        # (see #+)
        def merge(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#merge for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self + binary_heap
        end

        # Concatenates contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] self object
        def concat!(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#concat! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          from_obj(@container + binary_heap.to_a, false)
        end

        # Concatenates contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] self object
        def merge!(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#merge! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          from_obj(@container + binary_heap.to_a, false)
        end

        # Unites contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] a new binary heap
        def |(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#| for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          BinaryHeap.new(@container | binary_heap.to_a, min: !@max)
        end

        # (see #|)
        def union(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#union for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self | binary_heap
        end

        # Unites contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] self object
        def union!(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#union! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          from_obj(@container | binary_heap.to_a, false)
        end

        # Finds the intersection of contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] a new binary heap
        def &(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#& for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          BinaryHeap.new(@container & binary_heap.to_a, min: !@max)
        end

        # (see #&)
        def intersect(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#intersect for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self & binary_heap.to_a
        end

        # Finds the intersection of contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] self object
        def intersect!(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#intersect! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          from_obj(@container & binary_heap.to_a, false)
        end

        # Finds the difference of contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] a new binary heap
        def -(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#- for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          BinaryHeap.new(@container - binary_heap.to_a, min: !@max)
        end

        # (see #-)
        def difference(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#difference for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self - binary_heap
        end

        # Finds the difference of contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] self object
        def difference!(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#difference! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          from_obj(@container - binary_heap.to_a, false)
        end

        # Finds the symmetric difference of contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] a new binary heap
        def ^(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#^ for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          result = (@container | binary_heap.to_a) - (@container & binary_heap.to_a)
          BinaryHeap.new(result, min: !@max)
        end

        # (see #^)
        def symmetric_difference(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#symmetric_difference for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          self ^ binary_heap
        end

        # Finds the symmetric difference of contents of the heap, and a heap given as argument.
        #
        # @param binary_heap [BinaryHeap]
        # @raise ArgumentError, if given object is not a heap
        # @return [BinaryHeap] self object
        def symmetric_difference!(binary_heap)
          raise ArgumentError, "Undefined method BinaryHeap#symmetric_difference! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
          result = (@container | binary_heap.to_a) - (@container & binary_heap.to_a)
          from_obj(result, false)
        end

        # Converts content of the heap to an array.
        def to_a
          @container
        end

        # Clears content of the heap.
        def clear
          @container = []
          self
        end

        # Filters elements of the heap by given condition.
        #
        # @param block
        # @return [BinaryHeap] a new binary heap
        def select(&block)
          BinaryHeap.new(@container.select { |e| block.call(e)}, min: !@max)
        end

        # Filters elements of the heap by given condition.
        #
        # @param block
        # @return [BinaryHeap] self object
        def select!(&block)
          from_obj(@container.select { |e| block.call(e)}, false)
        end

        # (see #select)
        def filter(&block)
          select(&block)
        end

        # (see #select!)
        def filter!(&block)
          select!(&block)
        end

        # (see #select)
        def find_all(&block)
          select(&block)
        end

        # (see #select!)
        def find_all!(&block)
          select!(&block)
        end

        # Applies a function to each element of the heap.
        #
        # @param block
        # @return [BinaryHeap] a new binary heap
        def map(&block)
          BinaryHeap.new(@container.map { |e| block.call(e)}, min: !@max)
        end

        # Applies a function to each element of the heap.
        #
        # @param block
        # @return [BinaryHeap] self object
        def map!(&block)
          from_obj(@container.map { |e| block.call(e)}, false)
        end

        # (see #map)
        def apply(&block)
          map(&block)
        end

        # (see #map!)
        def apply!(&block)
          map!(&block)
        end

        private

        def from_obj(obj, copy)
          raise ArgumentError, "Object doesn't respond to #to_a method" unless obj.respond_to?(:to_a)
          @container = copy ? obj.send(:to_a).dup : obj.send(:to_a)

          build_heap
          self
        end

        def heapify(idx)
          return if idx.nil?
          lhs = idx * 2 + 1
          rhs = idx * 2 + 2
          current = idx

          if !@container[lhs].nil? &&
            ((@max && @container[lhs] > @container[current]) ||
            (!@max && @container[lhs] < @container[current]))

            current = lhs
          end

          if !@container[rhs].nil? &&
            ((@max && @container[rhs] > @container[current]) ||
            (!@max && @container[rhs] < @container[current]))

            current = rhs
          end

          if current != idx
            @container[idx], @container[current] = @container[current], @container[idx]
            heapify(current)
          end
        end

        def build_heap
          (@container.length / 2).downto(0) do |idx|
            heapify(idx)
          end
        end

        def sift_up(idx)
          return if idx.zero?
          parent = idx.even? ? idx / 2 - 1 : idx / 2

          if (@max && @container[parent] < @container[idx]) || (!@max && @container[parent] > @container[idx])
            @container[parent], @container[idx] = @container[idx], @container[parent]

            sift_up(parent)
          end
        end

        def change_key(idx, value, increase: false)
          idx = idx < 0 ? idx + @container.size : idx
          @container[idx] = increase ? (@container[idx] < value ? value : @container[idx]) :
                                       (@container[idx] > value ? value : @container[idx])

          sift_up(idx)
        end
        
      end
    end
  end
end