From 91705745330b10e14ed1022bd954bc760d09ad05 Mon Sep 17 00:00:00 2001
From: ianmdlvl <ianmdlvl>
Date: Mon, 2 Oct 2006 17:10:47 +0000
Subject: [PATCH] new better algorithm

---
 scripts/expire-iso8601 | 55 ++++++++++++++++++++++++++++++------------
 1 file changed, 39 insertions(+), 16 deletions(-)

diff --git a/scripts/expire-iso8601 b/scripts/expire-iso8601
index 7cb274e..3a9777d 100755
--- a/scripts/expire-iso8601
+++ b/scripts/expire-iso8601
@@ -106,7 +106,8 @@ done
 
 # We process each minimum/extent pair, to have it select a bunch of
 # versions to keep.  We annotate entries in $l: if we are keeping
-# an entry we prepend a colon.
+# an entry we prepend a colon; temporarily, if we are keeping an entry
+# because of this particular minimum/extent, we prepend a comma.
 
 # For each minimum/extent pair we look at the list from most recent
 # to least recent,
@@ -123,27 +124,49 @@ END
 )
 
 for ni in "$@"; do
-	min=$(( ${ni#*x} * $unit - $slop ))
 	wantcount=${ni%x*}
 
-	ls=''
+	div=1
+
+	while true; do
+		min=$(( (${ni#*x} * $unit) / $div - $slop ))
+
+		ls=''
+		lnew=''
+		skipped=0
+		for ce in $l; do
+			cn=${ce#*/}; cl=${ce%%/*}
+			cs=${cl#,}; cs=${cs#:}
+			case $cl in ,*)	ls=$cs; continue;; esac
+			if [ $wantcount != 0 ]; then
+				if ! [ "$ls" ] || \
+				   [ $(( $ls - $cs )) -ge $min ]; then
+					echo "keep (for $ni) $cn"
+					ce=,$ce
+					ls=$cs
+					wantcount=$(( $wantcount - 1 ))
+				else
+					skipped=$(( $skipped+1 ))
+				fi
+			fi
+			lnew="$lnew $ce"
+		done
+		l=$lnew
+
+		if [ $wantcount = 0 ]; then break; fi
+		printf "%s" "insufficient (for $ni) by $wantcount"
+		if [ $skipped = 0 ]; then echo; break; fi
+		div=$(( $div * 2 ))
+		echo " shortening interval ${div}x"
+	done
+
+	# s/([,:]+).*/:\1/g
 	lnew=''
 	for ce in $l; do
-		cn=${ce#*/}; cl=${ce%%/*}; cs=${cl#:}
-		if [ $wantcount != 0 ]; then
-			if ! [ "$ls" ] || \
-			   [ $(( $ls - $cs )) -ge $min ]; then
-				echo "keep (for $ni) $cn"
-				ls=$cs
-				ce=:$cs/$cn
-				wantcount=$(( $wantcount - 1 ))
-			fi
-		fi
+		case $ce in ,*) ce=:${ce#,};; esac
+		case $ce in ::*) ce=${ce#:};; esac
 		lnew="$lnew $ce"
 	done
-	if [ $wantcount != 0 ];then
-		echo "insufficient (for $ni) by $wantcount"
-	fi
 	l=$lnew
 done
 
-- 
2.30.2