- Fix an algorithmic bug in `quilt graph --lines': Edges were

  sometimes lost.
- A few minor cleanups.

6 files changed, 63 insertions, 86 deletions

diff --git a/doc/.cvsignore b/doc/.cvsignore
index ed89d0e..b5c3d34 100644
--- a/doc/.cvsignore
+++ b/doc/.cvsignore
@@ -1 +1 @@
-quilt.1 quilt.dvi quilt.ps README
+quilt.1 quilt.dvi quilt.ps README main.aux main.log
diff --git a/quilt.changes b/quilt.changes
index 88202f6..fac13d3 100644
--- a/quilt.changes
+++ b/quilt.changes
@@ -1,4 +1,11 @@
 -------------------------------------------------------------------
+Sat Mar 20 18:04:01 CET 2004 - agruen@suse.de
+
+- Fix an algorithmic bug in `quilt graph --lines': Edges were
+  sometimes lost.
+- A few minor cleanups.
+
+-------------------------------------------------------------------
 Mon Mar 15 00:01:56 CET 2004 - agruen@suse.de
 
 - Extend `quilt graph' to also support checking for overlapping
diff --git a/quilt/diff.in b/quilt/diff.in
index 9973ed5..465c010 100644
--- a/quilt/diff.in
+++ b/quilt/diff.in
@@ -19,12 +19,7 @@ fi
 
 usage()
 {
-	local redirect
-	if [ x$1 != x-h ]
-	then
-		redirect='>&2'
-	fi
-	echo $"Usage: quilt diff [-p n] [-c patch|-z] [-R] [-P patch] [--snapshot] [--diff=utility] [file ...]" $redirect
+	echo $"Usage: quilt diff [-p n] [-c patch|-z] [-R] [-P patch] [--snapshot] [--diff=utility] [file ...]"
 	
 	if [ x$1 = x-h ]
 	then
diff --git a/quilt/graph.in b/quilt/graph.in
index f38f0ea..b9a5316 100644
--- a/quilt/graph.in
+++ b/quilt/graph.in
@@ -19,12 +19,7 @@ fi
 
 usage()
 {
-	local redirect
-	if [ x$1 != x-h ]
-	then
-		redirect='>&2'
-	fi
-	echo $"Usage: quilt graph [--all] [--reduce] [--lines[=num]] [--edge-labels=files] [patch]" $redirect
+	echo $"Usage: quilt graph [--all] [--reduce] [--lines[=num]] [--edge-labels=files] [patch]"
 
 	if [ x$1 = x-h ]
 	then
diff --git a/quilt/refresh.in b/quilt/refresh.in
index 170cc30..8162715 100644
--- a/quilt/refresh.in
+++ b/quilt/refresh.in
@@ -19,12 +19,7 @@ fi
 
 usage()
 {
-	local redirect
-	if [ x$1 != x-h ]
-	then
-		redirect='>&2'
-	fi
-	echo $"Usage: quilt refresh [-p n] [-f] [patch]" $redirect
+	echo $"Usage: quilt refresh [-p n] [-f] [patch]"
 	
 	if [ x$1 = x-h ]
 	then
diff --git a/scripts/dependency-graph.in b/scripts/dependency-graph.in
index f3ffed8..a51f541 100644
--- a/scripts/dependency-graph.in
+++ b/scripts/dependency-graph.in
@@ -164,54 +164,29 @@ sub compute_ranges($$) {
     return $ranges;
 }
 
-# Binary search
-sub binsearch($$) {
-    my ($key, $array) = @_;
-    my ($low, $high) = (-1, scalar @$array - 1);
-    #print STDERR "$low:$high\n";
-    my $i;
-    while ($low + 1 < $high) {
-	$i = ($low + $high) >> 1;
-	if ($key < $array->[$i]) {
-	    $high = $i;
-	} else {
-	    $low = $i;
-	}
-	#print STDERR "$low:$high\n";
-    }
-    my $res;
-    if ($low == -1) {
-	$res = $low;
-    } else {
-	$res = ($key < $array->[$high]) ? $low : $high;
-    }
-    #print STDERR "$key -> [", join(" ", @$array), "] = $res\n";
-    return $res
-}
-
 sub is_a_conflict($$$) {
     my ($from, $to, $filename) = @_;
 
-    $nodes[$from]{$filename} = compute_ranges($from, $filename)
-	unless $nodes[$from]{$filename};
-    $nodes[$to]{$filename} = compute_ranges($to, $filename)
-	unless $nodes[$to]{$filename};
-
-    my ($ra, $rb) = ($nodes[$from]{$filename}[1], $nodes[$to]{$filename}[0]);
-    my $d = 0;
-    foreach my $l (@$ra) {
-	unless (binsearch($l - $d, $rb) % 2) {
-	    return 1;
-	}
-	# Alternate to convert from [in, out) regions to [in, in] regions
-	$d = 1 - $d;
-    }
-    foreach my $l (@$rb) {
-	unless (binsearch($l - $d, $ra) % 2) {
-	    return 1;
+    $nodes[$from]{files}{$filename} = compute_ranges($from, $filename)
+	unless @{$nodes[$from]{files}{$filename}};
+    $nodes[$to]{files}{$filename} = compute_ranges($to, $filename)
+	unless @{$nodes[$to]{files}{$filename}};
+
+    my @a = @{$nodes[$from]{files}{$filename}[1]};
+    my @b = @{$nodes[$to  ]{files}{$filename}[0]};
+
+    while (@a && @b) {
+	if ($a[0] < $b[0]) {
+	    return 1 if @b % 2;
+	    shift @a;
+	} elsif ($a[0] > $b[0]) {
+	    return 1 if @a % 2;
+	    shift @b;
+	} else {
+	    return 1 if (@a % 2) == (@b % 2);
+	    shift @a;
+	    shift @b;
 	}
-	# Alternate to convert from [in, out) regions to [in, in] regions
-	$d = 1 - $d;
     }
     return 0;
 }
@@ -219,29 +194,29 @@ sub is_a_conflict($$$) {
 # Fetch the list of patches (all of them must be applied)
 my @patches;
 if (@ARGV) {
-    if (@ARGV == 1 && $ARGV[0] eq "-") {
-	@patches = map { chomp ; $_ } <STDIN>;
-    } else {
-	@patches = @ARGV;
-    }
+	if (@ARGV == 1 && $ARGV[0] eq "-") {
+		@patches = map { chomp ; $_ } <STDIN>;
+	} else {
+		@patches = @ARGV;
+	}
 } else {
-    my $fh = new FileHandle("< $ENV{QUILT_PC}/applied-patches")
-	or die ".$ENV{QUILT_PC}/applied-patches: $!\n";
-    @patches = map { chomp; $_ } <$fh>;
-    $fh->close();
+	my $fh = new FileHandle("< $ENV{QUILT_PC}/applied-patches")
+		or die ".$ENV{QUILT_PC}/applied-patches: $!\n";
+	@patches = map { chomp; $_ } <$fh>;
+	$fh->close();
 }
 
 # Fetch the list of files
 my $n = 0;
 foreach my $patch (@patches) {
-    if (! -d "$ENV{QUILT_PC}/$patch") {
-	print STDERR "$ENV{QUILT_PC}/$patch does not exist; skipping\n";
-	next;
-    }
-    my @files = split(/\n/, `cd $ENV{QUILT_PC}/$patch ; find -type f ! -name .timestamp`);
-    @files = map { s:\./::; $_ } @files;
-    push @nodes, {number=>$n++, name=>$patch, file=>$patch,
-		  files=>{ map {$_ => []} @files } };
+	if (! -d "$ENV{QUILT_PC}/$patch") {
+		print STDERR "$ENV{QUILT_PC}/$patch does not exist; skipping\n";
+		next;
+	}
+	my @files = split(/\n/, `cd $ENV{QUILT_PC}/$patch ; find -type f ! -name .timestamp`);
+	@files = map { s:\./::; $_ } @files;
+	push @nodes, {number=>$n++, name=>$patch, file=>$patch,
+		files=>{ map {$_ => []} @files } };
 }
 
 my %used_nodes;		# nodes to which at least one edge is attached
@@ -322,16 +297,26 @@ foreach my $node (@nodes) {
     my $number = $node->{number};
     foreach my $file (keys %{$node->{files}}) {
 	if (exists $files_seen{$file}) {
+	    my $patches = $files_seen{$file};
+	    my $patch;
 	    # Optionally look at the line ranges the patches touch
 	    if (defined $lines) {
-		next unless is_a_conflict($number, $files_seen{$file}, $file);
+		for (my $n = $#$patches; $n >= 0; $n--) {
+		    if (is_a_conflict($number, $patches->[$n], $file)) {
+			$patch = $patches->[$n];
+			last;
+		    }
+		}
+	    } else {
+		$patch = $patches->[$#$patches];
+	    }
+	    if (defined $patch) {
+		push @{$edges{"$number:$patch"}{names}}, $file;
+		$used_nodes{$number} = 1;
+		$used_nodes{$patch} = 1;
 	    }
-
-	    push @{$edges{"$number:$files_seen{$file}"}{names}}, $file;
-	    $used_nodes{$number} = 1;
-	    $used_nodes{$files_seen{$file}} = 1;
 	}
-	$files_seen{$file} = $number;
+	push @{$files_seen{$file}}, $number;
     }
 }