# frozen_string_literal: true

module Linked
  # List
  #
  # This class implements a linked list. Most importantly, the methods #head,
  # #tail, #grow, #shrink and #create_item are implemented to comply with the
  # requirements defined by Listable.

  class List
    include Enumerable

    # Initializes the list. It is important that this method be called during
    # the initialization of the including class, and that the instance variables
    # @_item_count and @_eol never be accessed directly.

    def initialize
      @_eol = EOL.new self
      @_item_count = 0

      super
    end

    # When copying a list its entire item chain needs to be copied as well.
    # Therefore #dup will be called on each of the original lists items, making
    # this operation quite expensive.

    def initialize_dup(source)
      @_eol = EOL.new self
      @_item_count = 0

      source.each_item { |item| push item.dup  }

      super
    end

    # Identity method that simply return the list. This method mirrors Item#list
    # and allows other methods that work on List objects to easily and
    # interchangebly accept both lists and items as arguments.
    #
    # Returns the list itself.

    def list
      self
    end

    # Access the first item in the list. If the list is empty a NoMethodError
    # will be raised. This mirrors the behaviour of Item#item and allows other
    # methods that work on List objects to easily and interchangeably accept
    # both lists and items as arguments.
    #
    # Returns the first item in the list.

    def item
      raise NoMethodError if empty?
      head.next
    end

    # Two lists are considered equal if the n:th item from each list are equal.
    #
    # other - any object.
    #
    # Returns true if the given object is a list and the items are equal.

    def ==(other)
      return false unless other.is_a? self.class
      return false unless other.count == @_item_count

      other_items = other.each_item
      each_item.all? { |item| item == other_items.next }
    end

    alias eql? ==

    # Access the first n item(s) in the list. If a block is given each item will
    # be yielded to it. The first item, starting from the first in the list, for
    # which the block returns true and the n - 1 items directly following it
    # will be returned.
    #
    # n - the number of items to return.
    #
    # Returns, for different values of n:
    # n == 0) nil
    # n == 1) an item if the list contains one, or nil
    #  n > 1) an array of between 0 and n items, depending on how many are in
    #         the list

    def first(n = 1)
      raise ArgumentError, 'n cannot be negative' if n < 0

      return first_item_after head, n, count unless block_given?

      item = head
      items_left = count

      items_left.times do
        break if yield next_item = item.next
        item = next_item
        items_left -= 1
      end

      first_item_after item, n, items_left
    end

    # Access the last n item(s) in the list. The items will retain thier order.
    # If a block is given each item, starting with the last in the list, will be
    # yielded to it. The first item for which the block returns true and the
    # n - 1 items directly preceding it will be returned.
    #
    # n - the number of items to return.
    #
    # Returns, for different values of n:
    # n == 0) nil
    # n == 1) an item if the list contains one, or nil
    #  n > 1) an array of between 0 and n items, depending on how many are in
    #         the list

    def last(n = 1)
      raise ArgumentError, 'n cannot be negative' if n < 0

      return last_item_before tail, n, count unless block_given?

      item = tail
      items_left = count

      items_left.times do
        break if yield prev_item = item.prev
        item = prev_item
        items_left -= 1
      end

      last_item_before item, n, items_left
    end

    # Overrides the Enumerable#count method when given no argument to provide a
    # fast item count. Instead of iterating over each item, the internal item
    # count is returned.
    #
    # args - see Enumerable#count
    #
    # Returns the number of items counted.

    def count(*args)
      if args.empty? && !block_given?
        @_item_count
      else
        super
      end
    end

    # Returns true if the list does not contain any items.

    def empty?
      @_item_count == 0
    end

    # Insert an item at the end of the list. If the given object is not an
    # object responding to #item it will be treated as a value. The value will
    # be wraped in a new Item create by #create_item.
    #
    # See Item#append for more details.
    #
    # object - the item to insert, or an arbitrary object.
    #
    # Returns self.

    def push(object)
      tail.append object
      self
    end

    alias << push

    # Pop the last item off the list.
    #
    # Returns the last item in the list, or nil if the list is empty.

    def pop
      return nil if empty?
      last.delete
    end

    # Insert an item at the beginning of the list. If the given object is not an
    # object responding to #item it will be treated as a value. The value will
    # be wraped in a new Item create by #create_item.
    #
    # See Item#prepend for more details.
    #
    # object - the item to insert, or an arbitrary object.
    #
    # Returns self.

    def unshift(object)
      head.prepend object
      self
    end

    # Shift the first item off the list.
    #
    # Returns the first item in the list, or nil if the list is empty.

    def shift
      return nil if empty?
      first.delete
    end

    # Check if an item is in the list.
    #
    # item - Item, or any object that may be in the list.
    #
    # Returns true if the given item is in the list, otherwise false.

    def include?(item)
      item.in? self
    rescue NoMethodError
      false
    end

    # Iterates over each item in the list If a block is not given an enumerator
    # is returned.

    def each_item
      return to_enum(__method__) { count } unless block_given?
      return if empty?

      item = head
      loop { yield item = item.next }
    end

    alias each each_item

    # Iterates over each item in the list in reverse order. If a block is not
    # given an enumerator is returned.

    def reverse_each_item
      return to_enum(__method__) { count } unless block_given?
      return if empty?

      item = tail
      loop { yield item = item.prev }
    end

    alias reverse_each reverse_each_item

    # Calls #freeze on all items in the list, as well as the head and the tail
    # (eol).

    def freeze
      @_eol.freeze
      each_item(&:freeze)
      super
    end

    # Overrides the default inspect method to provide a more useful view of the
    # list.
    #
    # Importantly this implementation supports nested lists and will return a
    # tree like structure.

    def inspect(&block)
      # Get the parents inspect output
      res = [super]

      each_item do |item|
        lines = item.inspect(&block).split "\n"

        res.push (item.last? ? '└─╴' : '├─╴') + lines.shift
        padding = item.last? ? '   ' : '│  '
        lines.each { |line| res.push padding + line }
      end

      res.join("\n")
    end

    # Protected factory method for creating items compatible with the list. This
    # method is called whenever an arbitrary object is pushed or unshifted onto
    # the list and need to be wraped inside an Item.
    #
    # This method can be overridden to support different Item types.
    #
    # args - any arguments will be passed on to Item.new.
    #
    # Returns a new Item.

    protected def create_item(*args)
      Item.new(*args)
    end

    # Returns an object that responds to #next= and #prepend.

    protected def head
      @_eol
    end

    # Returns an object that responds to #prev= and #append.

    alias tail head

    # Internal method to grow the list with n elements. Never call this method
    # without also inserting the n elements.
    #
    # n - the number of items that has been/will be added to the list.
    #
    # Returns updated the item count.

    private def grow(n = 1)
      @_item_count += n
    end

    # Internal method to shrink the list with n elements. Never call this method
    # without also deleting the n elements.
    #
    # n - the number of items that has been/will be removed from the list.
    #
    # Returns updated the item count.

    private def shrink(n = 1)
      @_item_count -= n
    end

    # Private method to clear the list. Never call this method without also
    # modifying the items in the list, as this operation leavs them in an
    # inconsistant state. If the list items are kept, make sure to
    # a) clear the `prev` pointer of the first item and
    # b) clear the `next` pointer of the last item.

    private def clear
      @_eol.send :reset
      @_item_count = 0
    end

    # Private helper method that returns the first n items, starting just
    # after item, given that there are items_left items left. Knowing the exact
    # number of items left is not cruicial but does impact speed. The number
    # should not be lower than the actual ammount. The following must
    # hold for the output to be valid:
    # a) n > 0
    # b) there are at least items_left items left
    #
    # item - the Item just before the item to start from.
    # n - the number of items to return.
    # items_left - the number of items left.
    #
    # Returns, for different values of n:
    # n == 0) nil
    # n == 1) an item if items_left > 0 or nil
    #  n > 1) an array of items if items_left > 0 or an empty array

    private def first_item_after(item, n, items_left = @_item_count)
      # Optimize for these cases
      return nil if n == 0
      return n > 1 ? [] : nil if item.last?
      return item.next if n == 1

      n = items_left if n > items_left

      arr = Array.new n
      n.times { |i| arr[i] = item = item.next }
      arr
    rescue StopIteration
      arr.compact! || arr
    end

    # Private helper method that returns the last n items, ending just before
    # item,  given that there are items_left items left. Knowing the exact
    # number of items left is not cruicial but does impact speed. The number
    # should not be lower than the actual ammount. The following must hold for
    # the output to be valid:
    # a) n > 0
    # b) there are at least items_left items left
    #
    # item - the Item just after the item to start from.
    # n - the number of items to return.
    # items_left - the number of items left.
    #
    # Returns, for different values of n:
    # n == 0) nil
    # n == 1) an item if items_left > 0 or nil
    #  n > 1) an array of items if items_left > 0 or an empty array

    private def last_item_before(item, n, items_left = @_item_count)
      # Optimize for these cases
      return nil if n == 0
      return n > 1 ? [] : nil if item.first?
      return item.prev if n == 1

      n = items_left if n > items_left

      arr = Array.new n
      (n - 1).downto(0) { |i| arr[i] = item = item.prev }
      arr
    rescue StopIteration
      arr.compact! || arr
    end
  end
end