new better algorithm

[chiark-utils.git] / scripts / expire-iso8601

diff --git a/scripts/expire-iso8601 b/scripts/expire-iso8601
index 7cb274e607991354cf88b890b108054c5c9ed9c7..3a9777d25728c9762cd61df37d7a945176038198 100755 (executable)
--- 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