# frozen_string_literal: true
gem "minitest", "6.0.6"
require "minitest/autorun"

module SearchPatterns
  module_function
  # Precondition: values are sorted ascending and comparable to target.
  def lower_bound(values, target)
    left, right = 0, values.length
    while left < right
      middle = left + (right - left) / 2
      if values[middle] < target
        left = middle + 1
      else
        right = middle
      end
    end
    left
  end

  # Length is measured in Ruby characters, not grapheme clusters.
  def longest_unique_length(text)
    last_seen = {}
    left = 0
    best = 0
    text.each_char.with_index do |char, right|
      previous = last_seen[char]
      left = [left, previous + 1].max if previous
      last_seen[char] = right
      best = [best, right - left + 1].max
    end
    best
  end

  def append_default(value, items = [])
    items << value
  end

  class MinHeap
    def initialize
      @items = []
    end
    def push(value)
      raise ArgumentError, "Integer required" unless value.is_a?(Integer)
      @items << value
      index = @items.length - 1
      while index.positive?
        parent = (index - 1) / 2
        break if @items[parent] <= @items[index]
        @items[parent], @items[index] = @items[index], @items[parent]
        index = parent
      end
      self
    end
    def pop
      return nil if @items.empty?
      minimum = @items.first
      tail = @items.pop
      return minimum if @items.empty?
      @items[0] = tail
      index = 0
      while (left = 2 * index + 1) < @items.length
        right = left + 1
        child = right < @items.length && @items[right] < @items[left] ? right : left
        break if @items[index] <= @items[child]
        @items[index], @items[child] = @items[child], @items[index]
        index = child
      end
      minimum
    end
  end
end

class SearchPatternsTest < Minitest::Test
  def test_lower_bound_boundaries_and_duplicates
    assert_equal 0, SearchPatterns.lower_bound([], 3)
    assert_equal 0, SearchPatterns.lower_bound([1, 1, 4], 1)
    assert_equal 2, SearchPatterns.lower_bound([1, 1, 4], 3)
    assert_equal 3, SearchPatterns.lower_bound([1, 1, 4], 5)
  end
  def test_lower_bound_matches_linear_oracle
    random = Random.new(42)
    100.times do
      values = Array.new(random.rand(0..30)) { random.rand(-10..10) }.sort
      target = random.rand(-12..12)
      expected = values.index { |n| n >= target } || values.length
      assert_equal expected, SearchPatterns.lower_bound(values, target)
    end
  end
  def test_window_does_not_move_left_backwards
    {"abba" => 2, "abcabcbb" => 3, "" => 0, "aaaa" => 1, "éaé" => 2}.each do |text, length|
      assert_equal length, SearchPatterns.longest_unique_length(text)
    end
  end
  def test_window_matches_brute_force_oracle
    random = Random.new(99)
    100.times do
      chars = Array.new(random.rand(0..10)) { %w[a b c][random.rand(3)] }
      expected = 0
      chars.length.times do |start|
        (1..chars.length-start).each do |length|
          part = chars.slice(start, length)
          expected = [expected, length].max if part.uniq.length == part.length
        end
      end
      assert_equal expected, SearchPatterns.longest_unique_length(chars.join)
    end
  end
  def test_heap_empty_singleton_duplicates_and_negatives
    heap = SearchPatterns::MinHeap.new
    assert_nil heap.pop
    [3, -2, 3, 0].each { |n| heap.push(n) }
    assert_equal [-2, 0, 3, 3], 4.times.map { heap.pop }
    assert_nil heap.pop
    assert_raises(ArgumentError) { heap.push(nil) }
  end
  def test_heap_mixed_operations_match_sorted_array
    random = Random.new(17)
    heap = SearchPatterns::MinHeap.new
    oracle = []
    200.times do
      if oracle.empty? || random.rand(2).zero?
        value = random.rand(-20..20)
        heap.push(value); oracle << value; oracle.sort!
      else
        assert_equal oracle.shift, heap.pop
      end
    end
    assert_equal oracle, oracle.length.times.map { heap.pop }
    assert_nil heap.pop
  end
  def test_ruby_default_array_is_new_for_each_omitted_argument
    assert_equal [1], SearchPatterns.append_default(1)
    assert_equal [2], SearchPatterns.append_default(2)
    explicit = []
    SearchPatterns.append_default(1, explicit)
    SearchPatterns.append_default(2, explicit)
    assert_equal [1, 2], explicit
  end
end