1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#!/usr/bin/env ruby -w
# encoding: UTF-8
#
# = IntervalList.rb -- The TaskJuggler III Project Management Software
#
# Copyright (c) 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014
# by Chris Schlaeger <cs@taskjuggler.org>
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of version 2 of the GNU General Public License as
# published by the Free Software Foundation.
#
require 'taskjuggler/Interval'
class TaskJuggler
# A list of Intervals. The intervals in the list must not overlap and must
# be in ascending order.
class IntervalList < Array
alias append <<
def &(list)
res = IntervalList.new
si = li = 0
while si < length && li < list.length do
if self[si].start < list[li].start
# The current Interval of self starts earlier than the current
# Interval of list.
if self[si].end <= list[li].start
# self[si] does not overlap with list[li]. Ignore it.
si += 1
elsif self[si].end < list[li].end
# self[si] does overlap with list[li] but list[li] goes further
res << self[si].class.new(list[li].start, self[si].end)
si += 1
else
# self[si] does overlap with list[li] but self[si] goes further
res << self[si].class.new(list[li].start, list[li].end)
li += 1
end
elsif list[li].start < self[si].start
# The current Interval of list starts earlier than the current
# Interval of self.
if list[li].end <= self[si].start
# list[li] does not overlap with self[si]. Ignore it.
li += 1
elsif list[li].end < self[si].end
# list[li] does overlap with self[si] but self[si] goes further
res << self[si].class.new(self[si].start, list[li].end)
li += 1
else
# list[li] does overlap with self[si] but list[li] goes further
res << self[si].class.new(self[si].start, self[si].end)
si += 1
end
else
# self[si].start and list[li].start are identical
if self[si].end == list[li].end
# self[si] and list[li] are identical. Add the Interval and
# increase both pointers.
res << self[si]
li += 1
si += 1
elsif self[si].end < list[li].end
# self[si] ends earlier.
res << self[si]
si += 1
else
# list[li] ends earlier.
res << list[li]
li += 1
end
end
end
res
end
# Append the Interval _iv_. If the start of _iv_ matches the end of the
# list list item, _iv_ is merged with the last item.
def <<(iv)
if last
if last.end > iv.start
raise "Intervals may not overlap and must be added in " +
"ascending order."
elsif last.end == iv.start
self[-1] = last.class.new(last.start, iv.end)
return self
end
end
append(iv)
end
end
end
|
