From: Matt S Trout <mst@shadowcat.co.uk>
Date: Wed, 18 Apr 2018 21:54:39 +0000 (+0000)
Subject: compact_deps function
X-Git-Url: http://git.shadowcat.co.uk/gitweb/gitweb.cgi?p=scpubgit%2FDX.git;a=commitdiff_plain;h=e04bdc77b7135167545846a4e9dbc77a2e99293c

compact_deps function
---

diff --git a/lib/DX/Utils.pm b/lib/DX/Utils.pm
index 2bef078..fe1990c 100644
--- a/lib/DX/Utils.pm
+++ b/lib/DX/Utils.pm
@@ -1,17 +1,18 @@
 package DX::Utils;
 
 use strictures 2;
+use List::UtilsBy qw(sort_by);
 use Exporter 'import';
 
 my @const = (
-  my @dep_types = qw(EXISTENCE_OF TYPE_OF INDICES_OF CONTENTS_OF),
+  my @dep_types = qw(CONTENTS_OF INDICES_OF TYPE_OF EXISTENCE_OF),
   my @ev_types = qw(VALUE_SET VALUE_EXISTS),
 );
 
 our @EXPORT_OK = (
   @const,
   (my @builders = qw(rspace rstrat res string number dict proposition)),
-  'deparse', '*trace', 'expand_deps', 'format_deps',
+  'deparse', '*trace', 'expand_deps', 'format_deps', 'compact_deps',
 );
 
 our %EXPORT_TAGS = (
@@ -29,7 +30,7 @@ constant->import(+{
   map {; no strict 'refs'; $_ => \*$_ } @const
 });
 
-# $EXISTENCE_OF = 1, ...
+# $CONTENTS_OF = 1, ... # stronger dependency has lower number
 
 do { no strict 'refs'; ${$dep_types[$_-1]} = $_ } for 1..@dep_types;
 
@@ -65,6 +66,35 @@ sub format_deps {
   ] ]
 }
 
+sub compact_deps {
+  my ($deps) = @_;
+  my @sorted = sort_by { join "\0", @{$_->[0]} }
+                 map { [ [ join("\0", @{$_}[1..$#$_]), $${$_->[0]} ], $_ ] } @$deps;
+  my @compacted;
+  while (my $s = shift @sorted) {
+    my ($path, $type) = @{$s->[0]};
+    shift @sorted while @sorted and $sorted[0][0][0] eq $path;
+    if ($type == 1) { # CONTENTS_OF dep, prune children
+      my $len = length($path);
+      shift @sorted while @sorted and substr($sorted[0][0][0], 0, $len) eq $path;
+    }
+    if ($type == 2) { # INDICES_OF dep, drop immediately below EXISTENCE_OF
+      my $len = length($path);
+      my $parts = @{$s->[1]} + 1;
+      my @keep;
+      while (@sorted and substr($sorted[0][0][0], 0, $len) eq $path) {
+        my $check = shift @sorted;
+        unless ($check->[0][1] == 4 and @{$check->[1]} == $parts) {
+          push @keep, $check;
+        }
+      }
+      unshift @sorted, @keep;
+    }
+    push @compacted, $s->[1];
+  }
+  return \@compacted;
+}
+
 sub rspace {
   require DX::ResolutionSpace;
   DX::ResolutionSpace->new(@_);