module NSWTopo::Labels

def add(layer)
  label_params = layer.params.fetch("labels", {})
  label_params.except(*LABEL_PARAMS).select do |key, value|
    Hash === value
  end.transform_keys do |categories|
    Array(categories).map do |category|
      [layer.name, category].join(?\s)
    end
  end.then do |params|
    { layer.name => label_params }.merge(params)
  end.transform_values do |params|
    params.slice(*LABEL_PARAMS)
  end.transform_values do |params|
    # handle legacy format for separation, separation-all, separation-along
    params.each.with_object("separation" => Hash[]) do |(key, value), hash|
      case [key, value]
      in ["separation",    Hash] then hash["separation"].merge! value
      in ["separation",       *] then hash["separation"].merge! "self"  => value
      in ["separation-all",   *] then hash["separation"].merge! "other" => value
      in ["separation-along", *] then hash["separation"].merge! "along" => value
      else hash[key] = value
      end
    end
  end.then do |category_params|
    @params.merge! category_params
  end
  feature_count = feature_total = 0
  layer.labeling_features.tap do |features|
    feature_total = features.length
  end.map(&:multi).group_by do |feature|
    Set[layer.name, *feature["category"]]
  end.each do |categories, features|
    transforms = params_for(categories).slice(*LABEL_TRANSFORMS)
    attributes, point_attributes, line_attributes = [nil, "point", "line"].map do |extra_category|
      categories | Set[*extra_category]
    end.map do |categories|
      params_for(categories).slice(*LABEL_ATTRIBUTES).merge(categories: categories)
    end
    features.map do |feature|
      log_update "collecting labels: %s: feature %i of %i" % [layer.name, feature_count += 1, feature_total]
      text = feature["label"]
      text = case
      when REXML::Element === text then text
      when attributes["format"] then attributes["format"] % text
      else Array(text).map(&:to_s).map(&:strip).join(?\s)
      end
      dual = feature["dual"]
      text.upcase! if String === text && attributes["upcase"]
      dual.upcase! if String === dual && attributes["upcase"]
      feature_attributes = { text: text, dual: dual, layer_name: layer.name }
      transforms.inject([feature]) do |features, (transform, (arg, *args))|
        next features unless arg
        opts, args = args.partition do |arg|
          Hash === arg
        end
        opts = opts.inject({}, &:merge).transform_keys(&:to_sym)
        features.flat_map do |feature|
          case transform
          when "reduce"
            case arg
            when "skeleton"
              feature.respond_to?(arg) ? feature.send(arg) : feature
            when "centrelines"
              feature.respond_to?(arg) ? feature.send(arg, **opts) : feature
            when "centrepoints"
              interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
              feature.respond_to?(arg) ? feature.send(arg, interval: interval, **opts) : feature
            when "centres"
              interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
              feature.respond_to?(arg) ? feature.send(arg, interval: interval, **opts) : feature
            when "centroids"
              feature.respond_to?(arg) ? feature.send(arg) : feature
            when "samples"
              interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
              feature.respond_to?(arg) ? feature.send(arg, interval) : feature
            else
              raise "unrecognised label transform: reduce: %s" % arg
            end
          when "fallback"
            case arg
            when "samples"
              next feature unless feature.respond_to? arg
              interval = Float(opts.delete(:interval) || DEFAULT_SAMPLE)
              [feature, *feature.send(arg, interval)]
            else
              raise "unrecognised label transform: fallback: %s" % arg
            end
          when "offset", "buffer"
            next feature unless feature.respond_to? transform
            margins = [arg, *args].map { |value| Float(value) }
            feature.send transform, *margins, **opts
          when "smooth"
            next feature unless feature.respond_to? transform
            margin = Float(arg)
            max_turn = attributes["max-turn"] * Math::PI / 180
            feature.send transform, margin, cutoff_angle: max_turn, **opts
          when "minimum-area"
            area = Float(arg)
            case feature
            when GeoJSON::MultiLineString
              feature.reject_linestrings do |linestring|
                linestring.closed? && linestring.signed_area.abs < area
              end
            when GeoJSON::MultiPolygon
              feature.reject_polygons do |polygon|
                polygon.area < area
              end
            else
              feature
            end
          when "minimum-length"
            next feature unless GeoJSON::MultiLineString === feature
            distance = Float(arg)
            feature.reject_linestrings do |linestring|
              linestring.path_length < distance
            end
          when "minimum-hole", "remove-holes"
            next feature unless GeoJSON::MultiPolygon === feature
            area = Float(arg).abs unless true == arg
            feature.remove_holes do |ring|
              area ? (-area...0) === ring.signed_area : true
            end
          when "remove"
            remove = [arg, *args].any? do |value|
              case value
              when true    then true
              when String  then text == value
              when Regexp  then text =~ value
              when Numeric then text == value.to_s
              end
            end
            remove ? [] : feature
          when "keep-largest"
            case feature
            when GeoJSON::MultiLineString
              feature.max_by(&:path_length).multi
            when GeoJSON::MultiPolygon
              feature.max_by(&:area).multi
            else
              feature
            end
          when "trim"
            next feature unless GeoJSON::MultiLineString === feature
            distance = Float(arg)
            feature.trim distance
          end
        end
      rescue ArgumentError
        raise "invalid label transform: %s: %s" % [transform, [arg, *args].join(?,)]
      end.reject(&:empty?).map do |feature|
        case feature
        when GeoJSON::MultiPoint      then feature.with_properties(**feature_attributes, **point_attributes)
        when GeoJSON::MultiLineString then feature.with_properties(**feature_attributes, **line_attributes)
        when GeoJSON::MultiPolygon    then feature.with_properties(**feature_attributes, **line_attributes)
        end
      end.flat_map(&:explode)
    end.then do |features|
      next features unless label_params["collate"]
      features.flatten.group_by do |feature|
        feature[:text]
      end.values
    end.each do |features|
      label_features << features
    end
  end
end

def barriers
  @barriers ||= Barriers.new
end

def conflicts
  @conflicts ||= Hash.new do |conflicts, label|
    conflicts[label] = Set[]
  end
end

def drawing_features
  debug_features = []
  candidates = label_candidates do |feature, category|
    debug_features << [feature, Set["debug", category]]
  end
  ordered, unlabeled = AVLTree.new, Hash.new(true)
  remaining = candidates.to_set.classify(&:label_index)
  Enumerator.produce do |label|
    if label
      removals = Set[label] | conflicts[label]
      if first = unlabeled[label.label_index]
        removals.merge remaining[label.label_index].select(&:barriers?)
        unlabeled[label.label_index] = false
      end
      removals.each do |candidate|
        remaining[candidate.label_index].delete candidate
        ordered.delete candidate
      end
      conflicts.values_at(*removals).inject(Set[], &:|).subtract(removals).each do |candidate|
        conflicts[candidate].subtract removals
      end.tap do |changed|
        changed.merge remaining[label.label_index] if first
      end
    else
      candidates
    end.each do |candidate|
      conflict_count = conflicts[candidate].each.with_object Set[] do |other, indices|
        indices << other.label_index
      end.delete(candidate.label_index).size
      conflict_count += candidate.barrier_count
      unsafe = conflicts[candidate].classify(&:label_index).any? do |label_index, conflicts|
        next false unless unlabeled[label_index]
        others = remaining[label_index].reject(&:optional?)
        others.any? && others.all?(conflicts)
      end
      ordinal = [
        candidate.fixed                  ? 0 : 1, # fixed grid-line labels
        candidate.optional?              ? 1 : 0, # non-optional candidates
        unsafe                           ? 1 : 0, # candidates which don't prevent another feature being labeled altogether
        unlabeled[candidate.label_index] ? 0 : 1, # candidates for unlabeled features
        conflict_count,                           # candidates with fewer conflicts
        candidate.priority                        # better quality candidates
      ]
      unless candidate.ordinal == ordinal
        ordered.delete candidate
        candidate.ordinal.replace ordinal
        ordered.insert candidate
      end
    end
    ordered.first or raise StopIteration
  end.to_set.tap do |labels|
    grouped = candidates.group_by(&:indices)
    5.times do
      labels.select(&:point?).each do |label|
        labels.delete label
        labels << grouped[label.indices].min_by do |candidate|
          [(labels & conflicts[candidate] - Set[label]).count, candidate.priority]
        end
      end
    end
  end.flat_map do |label|
    label.elements.map.with_object(label.categories).entries
  end.tap do |result|
    next unless debug_features.any?
    @params = DEBUG_PARAMS.deep_merge @params
    result.concat debug_features
  end
end

def label_candidates(&debug)
  label_features.flat_map.with_index do |features, label_index|
    log_update "compositing %s: feature %i of %i" % [@name, label_index + 1, label_features.length]
    features.map do |feature|
      font_size = feature["font-size"]
      properties = feature.slice(*FONT_SCALED_ATTRIBUTES).transform_values do |value|
        /^\d+%$/ === value ? value.to_i * font_size * 0.01 : value
      end.then do |scaled_properties|
        feature.except(*FONT_SCALED_ATTRIBUTES).merge(scaled_properties)
      end
      feature.with_properties(**properties)
    end.flat_map do |feature|
      case feature
      when GeoJSON::Point, GeoJSON::LineString
        feature
      when GeoJSON::Polygon
        feature.rings.explode
      end
    end.tap do |features|
      features.each.with_object("feature", &debug) if Config["debug"]
    end.map.with_index do |feature, feature_index|
      feature.add_properties label_index: label_index, feature_index: feature_index
    end.flat_map do |feature|
      case feature
      when GeoJSON::Point
        point_candidates(feature)
      when GeoJSON::LineString
        line_string_candidates(feature)
      end
    end.tap do |candidates|
      candidates.reject!(&:point?) unless candidates.all?(&:point?)
    end.sort.each.with_index do |candidate, index|
      candidate.priority.replace [index]
    end
  end.tap do |candidates|
    log_update "compositing %s: choosing label positions" % @name
    if Config["debug"]
      candidates.flat_map(&:explode).map do |ring|
        GeoJSON::LineString.new [*ring, ring.first]
      end.each.with_object("candidate", &debug)
      candidates.clear
    end
    Enumerator.new do |yielder|
      # separation/self: minimum distance between a label and another label for the same feature
      candidates.group_by do |label|
        label.label_index
      end.values.each do |group|
        Label.overlaps(group) do |label|
          label.separation["self"]
        end.each(&yielder)
      end
      # separation/same: minimum distance between a label and another label with the same text
      candidates.group_by do |label|
        [label.layer_name, label.text]
      end.values.each do |group|
        Label.overlaps(group) do |label|
          label.separation["same"]
        end.each(&yielder)
      end
      candidates.group_by do |candidate|
        candidate.layer_name
      end.each do |layer_name, group|
        # separation/other: minimum distance between a label and another label from the same layer
        Label.overlaps(group) do |label|
          label.separation["other"]
        end.each(&yielder)
        # separation/<layer>: minimum distance between a label and any label from <layer>
        Label.overlaps(group, candidates) do |label|
          label.separation[layer_name]
        end.each(&yielder)
      end
      # separation/dual: minimum distance between any two dual labels
      candidates.select(&:dual).group_by do |label|
        [label.layer_name, Set[label.text, label.dual]]
      end.values.each do |group|
        Label.overlaps(group) do |label|
          label.separation["dual"]
        end.each(&yielder)
      end
      # separation/all: minimum distance between a label and *any* other label
      Label.overlaps(candidates) do |label|
        # default of zero prevents any two labels overlapping
        label.separation["all"] || 0
      end.reject do |label1, label2|
        label1.coexists_with?(label2) ||
        label2.coexists_with?(label1)
      end.each(&yielder)
    end.each do |label1, label2|
      conflicts[label1] << label2
      conflicts[label2] << label1
    end
  end
end

def label_features
  @label_features ||= []
end

def line_string_candidates(feature)
  orientation = feature["orientation"]
  max_turn    = feature["max-turn"] * Math::PI / 180
  min_radius  = feature["min-radius"]
  max_angle   = feature["max-angle"] * Math::PI / 180
  curved      = feature["curved"]
  sample      = feature["sample"]
  font_size   = feature["font-size"]
  text        = feature[:text]
  closed = feature.closed?
  text_length = case text
  when REXML::Element then feature.path_length
  when String then Font.glyph_length text, feature.properties
  end
  points, deltas, angles, avoid = feature.coordinates.each_cons(2).flat_map do |p0, p1|
    next [p0] if REXML::Element === text
    distance = (p1 - p0).norm
    next [p0] if curved && distance >= text_length
    (0...1).step(sample/distance).map do |fraction|
      p0 * (1 - fraction) + p1 * fraction
    end
  end.then do |points|
    if closed
      p0, p2 = points.last, points.first
      points.unshift(p0).push(p2)
    else
      points.push(feature.coordinates.last).unshift(nil).push(nil)
    end
  end.each_cons(3).map do |p0, p1, p2|
    next p1, 0, 0, false unless p0
    next p1, (p1 - p0).norm, 0, false unless p2
    o01, o12, o20 = p1 - p0, p2 - p1, p0 - p2
    l01, l12, l20 = o01.norm, o12.norm, o20.norm
    h01, h12 = o01 / l01, o12 / l12
    angle = Math::atan2 h01.cross(h12), h01.dot(h12)
    semiperimeter = (l01 + l12 + l20) / 2
    area_squared = [0, semiperimeter * (semiperimeter - l01) * (semiperimeter - l12) * (semiperimeter - l20)].max
    curvature = 4 * Math::sqrt(area_squared) / (l01 * l12 * l20)
    avoid = angle.abs > max_angle || min_radius * (curvature || 0) > 1
    next p1, l01, angle, avoid
  end.transpose
  total, distances = deltas.inject([0, []]) do |(total, distances), delta|
    next total += delta, distances << total
  end
  start = points.length.times
  stop = closed ? points.length.times.cycle : points.length.times
  indices = [stop.next]
  Enumerator.produce do
    while indices.length > 1 && deltas.values_at(*indices).drop(1).sum >= text_length do
      start.next
      indices.shift
    end
    until indices.length > 1 && deltas.values_at(*indices).drop(1).sum >= text_length do
      indices.push stop.next
    end
    interior = indices.values_at(1...-1)
    angle_sum, angle_sum_min, angle_sum_max, angle_square_sum = interior.inject [0, 0, 0, 0] do |(sum, min, max, square_sum), index|
      next sum += angles[index], [min, sum].min, [max, sum].max, square_sum + angles[index]**2
    end
    redo if angle_sum_max - angle_sum_min > max_turn
    redo if curved && indices.length < 3
    redo if avoid.values_at(*interior).any?
    baseline = GeoJSON::LineString.new(points.values_at *indices).crop(text_length).then do |baseline|
      case orientation
      when "uphill", "anticlockwise" then true
      when "downhill", "clockwise" then false
      else baseline.coordinates.values_at(0, -1).map(&:x).inject(&:<=)
      end ? baseline : baseline.reverse
    end
    along = distances.values_at(indices.first, indices.last).then do |d0, d1|
      (d0 + ((d1 - d0) % total) / 2) % total
    end
    priority = [angle_square_sum, (total - 2 * along).abs / total]
    path_id = [@name, "path", *feature.values_at(:layer_name, :label_index, :feature_index), indices.first, indices.last].join ?.
    path_element = REXML::Element.new("path")
    path_element.add_attributes "id" => path_id, "d" => baseline.svg_path_data, "pathLength" => VALUE % text_length
    text_element = REXML::Element.new("text")
    case text
    when REXML::Element
      fixed = true
      text_element.add_element text, "href" => "#%s" % path_id
    when String
      text_path = text_element.add_element "textPath", "href" => "#%s" % path_id, "textLength" => VALUE % text_length, "spacing" => "auto"
      text_path.add_element("tspan", "dy" => VALUE % (CENTRELINE_FRACTION * font_size)).add_text(text)
    end
    Label.new baseline, feature, priority, [text_element, path_element], along: along, fixed: fixed, &barriers
  end.reject do |candidate|
    candidate.optional? && candidate.barriers?
  end.select do |candidate|
    map_contains? candidate
  end.then do |candidates|
    neighbours = Hash.new do |hash, candidate|
      hash[candidate] = Set[]
    end
    candidates.each.with_index do |candidate1, index1|
      index2 = index1
      loop do
        index2 = (index2 + 1) % candidates.length
        break if index2 == (closed ? index1 : 0)
        candidate2 = candidates[index2]
        offset = candidate2.along - candidate1.along
        break unless offset % total < sample || (closed && -offset % total < sample)
        neighbours[candidate2] << candidate1
        neighbours[candidate1] << candidate2
      end
    end
    removed = Set[]
    candidates.sort.each.with_object Array[] do |candidate, sampled|
      next if removed === candidate
      removed.merge neighbours[candidate]
      sampled << candidate
    end.tap do |candidates|
      next unless separation = feature.dig("separation", "along")
      separation += text_length
      sorted = candidates.sort_by(&:along)
      sorted.each.with_index do |candidate1, index1|
        index2 = index1
        loop do
          index2 = (index2 + 1) % candidates.length
          break if index2 == (closed ? index1 : 0)
          candidate2 = sorted[index2]
          offset = candidate2.along - candidate1.along
          break unless offset % total < separation || (closed && -offset % total < separation)
          conflicts[candidate2] << candidate1
          conflicts[candidate1] << candidate2
        end
      end
    end
  end
end

def map_contains?(label)
  @labelling_neatline ||= @map.neatline(mm: -INSET).first
  @labelling_neatline.contains? label.hull
end

def point_candidates(feature)
  margin      = feature["margin"]
  line_height = feature["line-height"]
  font_size   = feature["font-size"]
  text        = feature[:text]
  point = feature.coordinates
  lines = Font.in_two text, feature.properties
  lines = [[text, Font.glyph_length(text, feature.properties)]] if lines.map(&:first).map(&:length).min == 1
  height = lines.map { font_size }.inject { |total| total + line_height }
  # if feature["shield"]
  #   width += SHIELD_X * font_size
  #   height += SHIELD_Y * font_size
  # end
  [*feature["position"] || "over"].map do |position|
    dx = position =~ /right$/ ? 1 : position =~ /left$/  ? -1 : 0
    dy = position =~ /^below/ ? 1 : position =~ /^above/ ? -1 : 0
    next dx, dy, dx * dy == 0 ? 1 : 0.6
  end.uniq.map.with_index do |(dx, dy, f), position_index|
    text_elements, baselines = lines.map.with_index do |(line, text_length), index|
      offset_x = dx * (f * margin + 0.5 * text_length)
      offset_y = dy * (f * margin + 0.5 * height)
      offset_y += (index - 0.5) * 0.5 * height unless lines.one?
      anchor = point + Vector[offset_x, offset_y]
      text_element = REXML::Element.new("text")
      text_element.add_attribute "transform", "translate(%s)" % POINT % anchor
      text_element.add_attribute "text-anchor", "middle"
      text_element.add_attribute "textLength", VALUE % text_length
      text_element.add_attribute "y", VALUE % (CENTRELINE_FRACTION * font_size)
      text_element.add_text line
      offset = Vector[0.5 * text_length, 0]
      baseline = GeoJSON::LineString.new [anchor - offset, anchor + offset]
      next text_element, baseline
    end.transpose
    priority = [position_index, feature[:feature_index]]
    Label.new baselines.inject(&:+), feature, priority, text_elements, &barriers
  end.reject do |candidate|
    candidate.optional? && candidate.barriers?
  end.select do |candidate|
    map_contains? candidate
  end.tap do |candidates|
    candidates.combination(2).each do |candidate1, candidate2|
      conflicts[candidate1] << candidate2
      conflicts[candidate2] << candidate1
    end
  end
end