diff options
| author | Jedidiah Barber <contact@jedbarber.id.au> | 2026-02-09 11:54:31 +1300 |
|---|---|---|
| committer | Jedidiah Barber <contact@jedbarber.id.au> | 2026-02-09 11:54:31 +1300 |
| commit | ab78413a044900e421d2e0144f3c170bdc3f0b18 (patch) | |
| tree | 13e65770246b82b1ca030cf5ec173669700d53a1 /src | |
| parent | 32eea08483afb754c7da5663f33cd022d4a2723c (diff) | |
More complete IDDFS that resets counter when backtracking
Diffstat (limited to 'src')
| -rw-r--r-- | src/kompsos-collector.adb | 30 |
1 files changed, 24 insertions, 6 deletions
diff --git a/src/kompsos-collector.adb b/src/kompsos-collector.adb index b64d284..6e3d75d 100644 --- a/src/kompsos-collector.adb +++ b/src/kompsos-collector.adb @@ -32,9 +32,12 @@ package body Kompsos.Collector is Local_Cursor : Upwards_Maps.Cursor; Next_Pick : Positive; - Conjunct_Count : Natural := 0; - Conjunct_Limit : Positive := Initial_Depth_Limit; - Already_Done : Choice_Vector_Vectors.Vector; + Conjunct_Need_More : Boolean := False; + Conjunct_Count_Active : Boolean := False; + Conjunct_Trail_Start : Natural := 0; + Conjunct_Count : Natural := 0; + Conjunct_Limit : Positive := Initial_Depth_Limit; + Already_Done : Choice_Vector_Vectors.Vector; Result : State := Within; State_Valid : Boolean := False; @@ -304,6 +307,9 @@ package body Kompsos.Collector is procedure Reset_Position is begin + Conjunct_Need_More := False; + Conjunct_Count_Active := False; + Conjunct_Trail_Start := 0; Conjunct_Count := 0; Conjunct_Limit := Conjunct_Limit * 2; Walk_Trail.Clear; @@ -333,6 +339,12 @@ package body Kompsos.Collector is Truncate (Result, Crumb.State_Size); Walk_Trail.Set_Length (Ada.Containers.Count_Type (Marker - 1)); Walk_Choices.Set_Length (Ada.Containers.Count_Type (Marker - 1)); + if Conjunct_Count_Active and then Marker - 1 < Conjunct_Trail_Start then + Conjunct_Count_Active := False; + Conjunct_Trail_Start := 0; + Conjunct_Count := 0; + Conjunct_Limit := Conjunct_Limit * 2; + end if; return True; -- Backtracking success else Marker := Marker - 1; @@ -359,7 +371,7 @@ package body Kompsos.Collector is State_Valid := True; return; elsif not Choose_Another_Way then - if Conjunct_Count >= Conjunct_Limit then + if Conjunct_Need_More then Reset_Position; else State_Valid := False; @@ -373,9 +385,15 @@ package body Kompsos.Collector is loop Ptr := Up_Vector (Upwards_Maps.Element (Local_Cursor)).Parents (Next_Pick).Node; exit when Ptr.Kind /= Conjunct_Node; + if not Conjunct_Count_Active then + Conjunct_Count_Active := True; + Conjunct_Trail_Start := Walk_Trail.Last_Index; + end if; if Conjunct_Count >= Conjunct_Limit then if not Choose_Another_Way then Reset_Position; + else + Conjunct_Need_More := True; end if; else Expand_Conjunct (Ptr); @@ -399,7 +417,7 @@ package body Kompsos.Collector is -- If unification fails then backtrack if possible, -- or otherwise reset if the Graph isn't exhausted if not Choose_Another_Way then - if Conjunct_Count > 0 then + if Conjunct_Need_More then Reset_Position; else State_Valid := False; @@ -416,7 +434,7 @@ package body Kompsos.Collector is begin if Choose_Another_Way then Walk_Graph; - elsif Conjunct_Count >= Conjunct_Limit then + elsif Conjunct_Need_More then Reset_Position; Walk_Graph; else |