重构 寻求优雅的代码, 计算两个日程是否有冲突?

lance_zyb · 2015年07月08日 · 最后由 yangxing_star 回复于 2015年07月10日 · 8423 次阅读

前提:用户建立日程 schedule

  1. 日程有开始时间 start_datetime ,结束时间 end_datetime
  2. 日程是可以重复的(用 repeat 标记),重复的日程的 start_datetimeend_datetime 必须在同一天
  3. 重复的日程有个截止日期 finish_date (只记录到哪天,不关心具体到几点)
  4. 如果 finish_datenil 表示它一直重复下去,不终止
  5. repeat : 0 不重复none_day,1 每天every_day,2 每个工作日every_wday,3 每周every_week,4 每月every_month

结果:schedule1 与 schedule2,两个日程的时间是否有冲突

我用 conflict? 作为方法名,英语能力差,有好的方法名希望能提出来

  1. 日程【2015-07-08 16:00:00,2015-07-08 17:00:00,不重复】与日程【2015-07-06 16:00:00,2015-07-06 16:30:00,每天重复,没有截止日期】冲突
  2. 日程【2015-07-08 16:00:00,2015-07-08 17:00:00,每工作日重复,没有截止日期】与日程【2015-07-11 16:00:00,2015-07-11 17:00:00,每周重复,没有截止日期】 不冲突
  3. 日程【2015-05-31 16:00:00,2015-05-31 17:00:00,每月重复,截止 2015-07-15】与日程【2015-06-10 16:00:00,2015-06-10 17:00:00,每天重复,没有截止日期】不冲突。(补充:每月重复会比较特殊,有些月份可能没有 29、30 和 31,那么这个月份会跳过,如 2015-05-31 16:00:00,下个重复时间是 2015-07-31 16:00:00)

我的思路

分两步解决

  1. 由于 none_day 是可以跨过 1 天的(如:2015-07-15 15:00:00 ~ 2015-07-19 15:00:00),而其他的却不可以,我先判断 none_day 分别与其他(none_day,every_day,every_wday,every_week,every_month)的情况
  2. 再解决 every_day,every_wday,every_week,every_month

先判断 none_day

  1. none_day 的特点:时间是连续。两个 none_day 的日程有冲突:not (s1.start_datetime > s2.end_datetime or s1.end_datetime < s2.start_datetime)
  2. none_day 与 every_??? 作比较,缩短比较范围:【max(start_datetime) ~ min(end_datetime)】,穷举在这个范围内 every_??? 日程,与 none_day 的日程作对比

every_???

  1. start_datetime ~ end_datetime 的 日期是一样的,如果两个 every_???的日程,start_datetime ~ end_datetime 的 time 没有交集,那么这个两个日程没有冲突
  2. 以下的判断都是基于两个日程 time 上有交集。(如:【2015-07-11 15:00:00~2015-07-11 16:00:00】与【2015-07-12 15:30:00~2015-07-12 :16:30:00】,两个日程 time 是有交集的)
  3. every_days,每天重复,若没有截止时间,将涵盖所有星期(工作日和周末),所有天(几号,每月重复需要考虑的)
  4. every_wday,主要的判断条件是:另一个日程是否都在存在一天在工作日上
  5. every_week,日程只包含一个星期,周期是 7 天
  6. every_month,每月的问题。先考虑两个日程都没有截止日期的情况,每月与每天——冲突了,每月与每工作日——冲突了,每月与每周——冲突了,每月与每月——判断日期是否一样;有截止日期的,若截止日期与 every_month 的 start_datetime 的日期相差 20 年,那也只有 20 x 12 = 120 个的判断,在考虑到项目的操作上,穷举是可取的

我的代码,已经不晓得哪些能再改的了

各位有啥想改的,哪怕是一行,别憋着

有啥想批评的也尽量来,有批评才有进步

require 'active_support/all'

# repeat:
# 0 -> 不重复
# 1 -> 每天
# 2 -> 每个工作日
# 3 -> 每周
# 4 -> 每月

# [OPTIMIZE]
module ScheduleCheck
  SCHEDULEREPEAT = [:none_day, :every_day, :every_wday, :every_week, :every_month]
  SCHEDULEREPEATMAP = { none_day: 0, every_day: 1, every_wday: 2, every_week: 3, every_month: 4 }

  class << self
    def find_conflicted ar_schedule, ar_maybe_conf_schedules
      schedule = Schedule.new(ar_schedule)
      ar_maybe_conf_schedules
        .map { |ar_maybe_conf_schedule| Schedule.new(ar_maybe_conf_schedule) }
        .select { |maybe_conf_schedule| conflict? schedule, maybe_conf_schedule }
        .map(&:model)
    end

    def conflict? s1, s2
      s1, s2 = sort(s1, s2)
      s1.conflict?(s2)
    end

    def sort s1, s2
      s1.repeat_value <= s2.repeat_value ? [s1, s2] : [s2, s1]
    end

    def max date1, date2
      date1 >= date2 ? date1 : date2
    end

    def min date1, date2
      return date1 if date2.blank?
      return date2 if date1.blank?

      date1 <= date2 ? date1 : date2
    end

    def time_compare_lt_and_eq date1, date2
      date1 <= date2.change(year: date1.year, month: date1.month, day: date1.day)
    end

    def time_compare_gt_and_eq date1, date2
      date1 >= date2.change(year: date1.year, month: date1.month, day: date1.day)
    end
  end

  class Repeat
    attr_reader :type, :start_datetime, :end_datetime, :finish_date

    def initialize params
      @type = params[:repeat_type]
      @start_datetime = params[:start_datetime]
      @end_datetime = params[:end_datetime]
      @finish_date = params[:finish_date]

      validate
      tidy
    end

    def tidy; end

    def next_repeat
      return if finish_date <= start_datetime.to_date
      Schedule.new(*to_repeat, SCHEDULEREPEATMAP[type], finish_date)
    end

    def repeat_value
      SCHEDULEREPEATMAP[type]
    end

    def finish_datetime
      return end_datetime if finish_date <= end_datetime.to_date
      end_datetime.change(year: finish_date.year, month: finish_date.month, day: finish_date.day)
    end

    def to_repeat
      raise "you need to rewrite this method!"
    end

    def weekend?
      return false if none_day?
      start_datetime.day.in?(5..6)
    end

    %w( none_day every_day every_wday every_week every_month ).each do |repeat_type|
      define_method "#{repeat_type}?" do
        type.to_s == repeat_type
      end
    end

    # 冲突
    def conflict? other
      return false if impossibility_conflict other
      oh_my_god? other
    end

    def infinite_time?
      finish_date == 999.years.since(Date.new(2015))
    end

    protected
    def validate
      raise EndDateError if end_datetime < start_datetime
      raise EndDateError if !none_day? && end_datetime.to_date != start_datetime.to_date
    end

    def impossibility_conflict other
      return false if none_day?
      time_start_after_other_end(other) ||
        time_end_before_other_start(other) ||
        finish_before_other_start(other) ||
        start_after_other_finish(other)
    end

    def time_start_after_other_end other
      ScheduleCheck.time_compare_gt_and_eq(start_datetime, other.end_datetime)
    end

    def time_end_before_other_start other
      ScheduleCheck.time_compare_lt_and_eq(end_datetime, other.start_datetime)
    end

    def finish_before_other_start other
      finish_date < other.start_datetime.to_date
    end

    def start_after_other_finish other
      other.finish_date < start_datetime.to_date
    end

    def end_before_other_start other
      end_datetime < other.start_datetime
    end

    def start_after_other_end other
      start_datetime > other.end_datetime
    end
  end

  class RepeatNoneDay < Repeat
    def to_repeat
      raise RepeatError
    end

    def oh_my_god? other
      if other.none_day?
        compare_with_other_none_day(other)
      elsif end_before_other_start(other) || start_after_other_finish(other)
        false
      else
        compare_with_repeat_day(other)
      end
    end

    protected
    def compare_with_other_none_day other
      !(start_after_other_end(other) || end_before_other_start(other))
    end

    def compare_with_repeat_day other
      s = Schedule.new(
        ScheduleCheck.max(@start_datetime, other.start_datetime).change(hour: other.start_datetime.hour, min: other.start_datetime.min),
        ScheduleCheck.max(@start_datetime, other.start_datetime).change(hour: other.end_datetime.hour, min: other.end_datetime.min),
        other.repeat_value,
        ScheduleCheck.min(@end_datetime.to_date, other.finish_date)
      )
      rescure(s, s.finish_date)
    end

    def rescure other, f_date
      return false if other.blank? || other.end_datetime.to_date > f_date
      return true unless other.start_datetime > end_datetime || other.end_datetime < start_datetime
      return false if other.every_day?
      rescure(other.next_repeat, f_date)
    end
  end

  class RepeatEveryDay < Repeat
    def to_repeat
      [1.day.since(start_datetime), 1.day.since(end_datetime)]
    end

    def oh_my_god? other
      return true
    end
  end

  class RepeatEveryWday < Repeat
    def tidy
      return if infinite_time?
      if finish_date.days_to_week_start.in?(5..6)
        @finish_date = (finish_date.days_to_week_start - 4).days.ago(finish_date)
      end
      if start_datetime.days_to_week_start.in?(5..6)
        @start_datetime = (7 - start_datetime.days_to_week_start).days.since(start_datetime)
        @end_datetime = (7 - end_datetime.days_to_week_start).days.since(end_datetime)
      end
    end

    def to_repeat
      if start_datetime.days_to_week_start == 4
        [3.day.since(start_datetime), 3.day.since(end_datetime)]
      else
        [ 1.day.since(start_datetime), 1.day.since(end_datetime)]
      end
    end

    def one_period_days
      rs = [self.start_datetime]
      (1..5).inject(next_repeat) do |next_r, _|
        break if next_r.blank?
        rs << next_r.start_datetime
        next_r.next_repeat
      end
      rs
    end

    def oh_my_god? other
      return true if other.every_wday?
      return false if other.weekend?

      if other.every_week?
        one_period_days
          .map(&:days_to_week_start)
          .include?(other.start_datetime.days_to_week_start)
      elsif other.every_month?
        return true if infinite_time? && other.infinite_time?
        max_start_datetime = ScheduleCheck.max(start_datetime, other.start_datetime)
        !(other
          .days_until(finish_date)
          .delete_if { |s| s < max_start_datetime }
          .map(&:days_to_week_start) & (0..4).to_a).blank?
      end
    end
  end

  class RepeatEveryWeek < Repeat
    def tidy
      return if infinite_time?
      if finish_date.days_to_week_start != start_datetime.days_to_week_start
        days = finish_date.days_to_week_start - start_datetime.days_to_week_start
        new_finish_date = days > 0 ? days.days.ago(finish_date) : (7 + days).days.ago(finish_date)
        @finish_date = new_finish_date > start_datetime.to_date ? new_finish_date : start_datetime.to_date
      end
    end

    def to_repeat
      [1.week.since(start_datetime), 1.week.since(end_datetime)]
    end

    def oh_my_god? other
      if other.every_week?
        start_datetime.days_to_week_start == other.start_datetime.days_to_week_start
      elsif other.every_month?
        return true if infinite_time? && other.infinite_time?
        other
          .days_until(finish_date)
          .delete_if { |d| d < ScheduleCheck.max(start_datetime, other.start_datetime) }
          .inject(false) { |conf, date| conf || include?(date) }
      end
    end

    protected
    def include? date
      days_dis = (date.at_beginning_of_day.to_i / 86400) - (start_datetime.at_beginning_of_day.to_i / 86400)
      return days_dis % 7 == 0
    end
  end

  class RepeatEveryMonth < Repeat
    def tidy
      return if infinite_time?
      if start_datetime.day != finish_date.day
        if start_datetime.day > finish_date.day
          # 下个月的最大天数是否包含重复的那天(eg:重复的是31号,4月是没有31号的)
          # 两个月内,一定会有重复的那天
          if 1.month.ago(finish_date).at_end_of_month.day < start_datetime.day
            new_finish_date = 2.months.ago(finish_date).change(day: start_datetime.day)
          else
            new_finish_date = 1.months.ago(finish_date).change(day: start_datetime.day)
          end
          @finish_date = new_finish_date > start_datetime.to_date ? new_finish_date : start_datetime.to_date
        else
          @finish_date = finish_date.change(day: start_datetime.day)
        end
      end
    end

    def to_repeat
      if 1.month.since(start_datetime).day == start_datetime.day
        [1.month.since(start_datetime), 1.month.since(end_datetime)]
      else
        [2.month.since(start_datetime), 2.month.since(end_datetime)]
      end
    end

    def oh_my_god? other
      if other.every_month?
        start_datetime.day == other.start_datetime.day
      end
    end

    def days_until e_date, count = nil
      e_date = ScheduleCheck.min(e_date, finish_date)
      s = self
      days = []
      while(e_date >= s.start_datetime.to_date)
        days << s.start_datetime
        s = s.next_repeat
        break if s.blank?
      end
      days
    end
  end

  class Schedule
    attr_reader :repeat, :model

    def initialize *args
      options = args.extract_options!
      params = if args.first.is_a?(ActiveRecord::Base) && args.first.class.name == "Schedule"
                 # activerecord
                 @model = args.first
                 {
                   start_datetime: @model.plan_start_time,
                   end_datetime: @model.plan_finish_time,
                   repeat_type: @model.period,
                   finish_date: @model.feal_deadline
                 }
               elsif options.present?
                 # hash
                 raise "need start_datetime and end_datetime" if (options.keys.map(&:to_sym) & [:start_datetime, :end_datetime]).blank?
                 options
                   .tap { |o| o[:finish_date] ||= infinite_long_date }
                   .reverse_merge({ repeat_type: :none_day})
               else
                 # array
                 raise "wrong number of arguments #{args.length} to 4" if args.length != 4
                 {
                   start_datetime: args[0],
                   end_datetime: args[1],
                   repeat_type: args[2],
                   finish_date: args[3] || infinite_long_date
                 }
               end
      @repeat_type = params[:repeat_type] = params[:repeat_type].is_a?(Fixnum) ? SCHEDULEREPEAT[params[:repeat_type]] : params[:repeat_type]
      @repeat = ("ScheduleCheck::Repeat#{@repeat_type.to_s.camelize}").constantize.new params
    end

    def method_missing(name, *args, &block)
      if repeat.respond_to?(name)
        repeat.public_send(name, *args, &block)
      else
        super
      end
    end

    protected
    def infinite_long_date
      999.years.since Date.new(2015)
    end
  end

  class EndDateError < StandardError; end
  class RepeatError < StandardError; end
  class RepeatTypeError < StandardError; end
end

一看到做 schedule,之前用过这个 gem ice_cube 他里面的conflicts_with? 不知道可否借鉴一下。

斌哥,容我没把代码仔细看完...

斌哥,容我没把代码仔细看完...

很多年前写过一个类似这样的东西不过还好没有选择每周这样的功能。我只想说这东西考虑到跨时区以及夏令时了么

你可以把两个日程想象成两个等差数列,然后对等差数列做 merge sort。 写一个伪代码。

def conflicts? s1, s2
  # if both schedule exists?
  while !s1.nil? && !s2.nil?
    # check if they conflicts
    return true if s1.date conflicts? s2.date
    # find the next date to compare
    if s1.date < s2.date
      s1 = s1.next_schedule
    else
      s2 = s2.next_schedule
    end
  end
  false
end

class Schedule
  # return: nil if no next, else a schedule start from next date
  def next_schedule
    return nil if repeat == 0
    next_s = this.dup
    case repeat
    when DAY then next_s.date.add-1-day
    when WDAY then next_s.date.travel-to-next-wday
    when WEEK then next_s.date.add-7-days
    when MONTH then next_s.date.travel-to-next-month
    end
    return nil if next_s.date > finish_date
    return nil if next_s.date.too_late?
    next_s
  end
end

应该不算太复杂吧。 具体实现方法(具体使用的对象/是否使用迭代器技术等等)请根据你自己的实际要求来写。 不过核心方法也就这么二三十行了。 而且也不需要开始结束日期在同一天。 而且也可以扩展到无数个日程互相检查冲突的情况。(用个小顶堆来实现应该就好)

#3 楼 @ywjno 时区和夏令时应该并不重要吧。反正 Rails 已经接管了时区问题。

https://gist.github.com/msg7086/1822abdc063aee116f19

$ rspec main_spec.rb

Schedule
  generates future events by month
  generates future events by week
  generates future events by workday
  generates future events by day

ScheduleService
  日程【2015-07-08 16:00:00,2015-07-08 17:00:00,不重复】与日程【2015-07-06 16:00:00,2015-07-06 16:30:00,每天重复,没有截止日期】冲突
  日程【2015-07-08 16:00:00,2015-07-08 17:00:00,每工作日重复,没有截止日期】与日程【2015-07-11 16:00:00,2015-07-11 17:00:00,每周重复,没有截止日期】 不冲突
  日程【2015-05-31 16:00:00,2015-05-31 17:00:00,每月重复,截止2015-07-15】与日程【2015-06-10 16:00:00,2015-06-10 17:00:00,每天重复,没有截止日期】不冲突

Finished in 0.131 seconds (files took 0.3343 seconds to load)
7 examples, 0 failures

现在是计算到 10 年后,我觉得差不多应该够了……

斌哥,容我没把代码仔细看完...

@msg7086 先赞一个 用等差数列来解决这个问题,太高大尚了。那么多的 if 就这样飘走了!

@justin 赞!刚好冲着这个机会,去看看 ice_cube 的源码,看看别人是怎么整理的!!

有现成轮子可以用啊

require 'ice_cube'
s1 = IceCube::Schedule.new(Time.parse('2015-07-08 16:00:00'), duration: 3600)
s2 = IceCube::Schedule.new(Time.parse('2015-07-06 16:00:00'), duration: 1800) do |s|
  s.add_recurrence_rule(IceCube::Rule.daily)
end
s1.conflicts_with?(s2)
#=> true

#8 楼 @lance_zyb 算法题就要当成算法题来做,然后就发现不难了 wwww 代码如果觉得有用的话就拿走好了,当 public domain 授权了。 当然有轮子用的话直接用轮子也可以。

@msg7086 已经很不客气的拿走了

斌哥,容我没把代码仔细看完...

需要 登录 后方可回复, 如果你还没有账号请 注册新账号