128
boolean isLessThan(path, index)
if this.path == path then
return (this.index < index)
endif /* rest is "else" after return above */
/* trim any common prefix, up to, but not including
the final insertion ID of either change */
my_path = this.path.trim(path)
path = path.trim(this.path)
if my_path.length > 1 then
/* I can be ordered by a move/copy destination */
my_label = my_path.head().getDestination().getComparisonLabel()
else
/* I am ordered by an insertion position */
my_label =
findSegment(my_path.head(), this.index).getComparisonLabel()
endif
if path.length > 1 then
/* other is ordered by her destination */
label = path.head().getDestination().getComparisonLabel()
else
/* other is ordered by an insertion segment */
label = findSegment(path,
index).getAddress().getcomparisonLabel()
endif
return my_label < label
F F F F iii ig g g gu u u ur r r re e e e 6666....5555:::: AAAAllllggggoooorrrriiiitttthhhhmmmm ffffoooorrrr ccccoooommmmppppaaaarrrriiiinnnngggg aaaa nnnnoooonnnn----iiiinnnnddddeeeexxxxeeeedddd aaaaddddddddrrrreeeessssssss
It suffices, to find the starting address of the segment containing a given index for a par-
ticular insertion. This is the findSegmentfunction. It is almost certainly most practical
simply to search the segments of an insertion (which can be easily kept linked to each
other) to find an insertion offset. It would certainly be possible to keep a sorted list of indi-
ces for each insertion to guarantee a logarithmic worst-case search time if very large split-
ting factors were present in some editing scenario.
It is worth making comparison for destination addresses fast because of the need for
comparison based search structures for move and deletion ranges. In interactive editing,
however, a simpler strategy is available so that search and comparison time is not an issue.
boolean isLessThan(path, index)
if this.path == path then
return (this.index < index)
endif /* rest is "else" after return above */
/* trim any common prefix, up to, but not including
the final insertion ID of either change */
my_path = this.path.trim(path)
path = path.trim(this.path)
if my_path.length > 1 then
/* I can be ordered by a move/copy destination */
my_label = my_path.head().getDestination().getComparisonLabel()
else
/* I am ordered by an insertion position */
my_label =
findSegment(my_path.head(), this.index).getComparisonLabel()
endif
if path.length > 1 then
/* other is ordered by her destination */
label = path.head().getDestination().getComparisonLabel()
else
/* other is ordered by an insertion segment */
label = findSegment(path,
index).getAddress().getcomparisonLabel()
endif
return my_label < label
F F F F iii ig g g gu u u ur r r re e e e 6666....5555:::: AAAAllllggggoooorrrriiiitttthhhhmmmm ffffoooorrrr ccccoooommmmppppaaaarrrriiiinnnngggg aaaa nnnnoooonnnn----iiiinnnnddddeeeexxxxeeeedddd aaaaddddddddrrrreeeessssssss
It suffices, to find the starting address of the segment containing a given index for a par-
ticular insertion. This is the findSegmentfunction. It is almost certainly most practical
simply to search the segments of an insertion (which can be easily kept linked to each
other) to find an insertion offset. It would certainly be possible to keep a sorted list of indi-
ces for each insertion to guarantee a logarithmic worst-case search time if very large split-
ting factors were present in some editing scenario.
It is worth making comparison for destination addresses fast because of the need for
comparison based search structures for move and deletion ranges. In interactive editing,
however, a simpler strategy is available so that search and comparison time is not an issue.
