FAILURE MAP
← Case archive

FA-47306 / Bounded deques / Open access

Sorted deque insertion places new ties before existing ties · case 01

Sorted deque insertion places new ties before existing ties.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Sorted deque insertion places new ties before existing ties.

VERIFIED REPAIR

Restore the documented stable upper bound invariant in sorted-stable-insert.

Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.

Case contract

Insert a keyed entry into an ascending bounded deque after all existing equal keys. Full capacity rejects atomically. Return insertion position and number of suffix entries shifted.

Why this case matters

Controlled bounded deque implementation model with explicit storage and lifecycle observations.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    a,entry,cap=x
    if len(a)==cap:return [a,False,None,0]
    position=next((i for i,z in enumerate(a) if z[0]>=entry[0]),len(a))
    result=a[:position]+[entry]+a[position:]
    shifted=len(a)-position
    return [result,True,position,shifted]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[[1,N],[2,N+1],[2,N+2],[4,N+3]],[2,N+4],6]), {1: [[[1, 1], [2, 2], [2, 3], [2, 5], [4, 4]], True, 3, 1], 2: [[[1, 2], [2, 3], [2, 4], [2, 6], [4, 5]], True, 3, 1], 3: [[[1, 3], [2, 4], [2, 5], [2, 7], [4, 6]], True, 3, 1], 4: [[[1, 4], [2, 5], [2, 6], [2, 8], [4, 7]], True, 3, 1], 5: [[[1, 5], [2, 6], [2, 7], [2, 9], [4, 8]], True, 3, 1]}[N])
check('1', solve([[[2,N],[3,N+1]],[1,N+2],3]), {1: [[[1, 3], [2, 1], [3, 2]], True, 0, 2], 2: [[[1, 4], [2, 2], [3, 3]], True, 0, 2], 3: [[[1, 5], [2, 3], [3, 4]], True, 0, 2], 4: [[[1, 6], [2, 4], [3, 5]], True, 0, 2], 5: [[[1, 7], [2, 5], [3, 6]], True, 0, 2]}[N])
check('2', solve([[[1,N],[2,N+1]],[3,N+2],4]), {1: [[[1, 1], [2, 2], [3, 3]], True, 2, 0], 2: [[[1, 2], [2, 3], [3, 4]], True, 2, 0], 3: [[[1, 3], [2, 4], [3, 5]], True, 2, 0], 4: [[[1, 4], [2, 5], [3, 6]], True, 2, 0], 5: [[[1, 5], [2, 6], [3, 7]], True, 2, 0]}[N])
check('3', solve([[],[1,N],1]), {1: [[[1, 1]], True, 0, 0], 2: [[[1, 2]], True, 0, 0], 3: [[[1, 3]], True, 0, 0], 4: [[[1, 4]], True, 0, 0], 5: [[[1, 5]], True, 0, 0]}[N])
check('4', solve([[[1,N],[2,N+1]],[1,N+2],2]), {1: [[[1, 1], [2, 2]], False, None, 0], 2: [[[1, 2], [2, 3]], False, None, 0], 3: [[[1, 3], [2, 4]], False, None, 0], 4: [[[1, 4], [2, 5]], False, None, 0], 5: [[[1, 5], [2, 6]], False, None, 0]}[N])
check('5', solve([[[1,N],[3,N+1],[5,N+2]],[4,N+3],4]), {1: [[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1], 2: [[[1, 2], [3, 3], [4, 5], [5, 4]], True, 2, 1], 3: [[[1, 3], [3, 4], [4, 6], [5, 5]], True, 2, 1], 4: [[[1, 4], [3, 5], [4, 7], [5, 6]], True, 2, 1], 5: [[[1, 5], [3, 6], [4, 8], [5, 7]], True, 2, 1]}[N])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
0[[[1, 1], [2, 5], [2, 2], [2, 3], [4, 4]], True, 1, 3][[[1, 1], [2, 2], [2, 3], [2, 5], [4, 4]], True, 3, 1]Failed
1[[[1, 3], [2, 1], [3, 2]], True, 0, 2][[[1, 3], [2, 1], [3, 2]], True, 0, 2]Passed
2[[[1, 1], [2, 2], [3, 3]], True, 2, 0][[[1, 1], [2, 2], [3, 3]], True, 2, 0]Passed
3[[[1, 1]], True, 0, 0][[[1, 1]], True, 0, 0]Passed
4[[[1, 1], [2, 2]], False, None, 0][[[1, 1], [2, 2]], False, None, 0]Passed
5[[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1][[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1]Passed

SHA-256 / cef28f418f3080763c902a183a2479c48d123f9ee5dac2ddd69fc257020e9500

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    a,entry,cap=x
    if len(a)==cap:return [a,False,None,0]
    position=next((i for i,z in enumerate(a) if (z[0]>=entry[0] if i>0 else z[0]>entry[0])),len(a))
    result=a[:position]+[entry]+a[position:]
    shifted=len(a)-position
    return [result,True,position,shifted]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[[1,N],[2,N+1],[2,N+2],[4,N+3]],[2,N+4],6]), {1: [[[1, 1], [2, 2], [2, 3], [2, 5], [4, 4]], True, 3, 1], 2: [[[1, 2], [2, 3], [2, 4], [2, 6], [4, 5]], True, 3, 1], 3: [[[1, 3], [2, 4], [2, 5], [2, 7], [4, 6]], True, 3, 1], 4: [[[1, 4], [2, 5], [2, 6], [2, 8], [4, 7]], True, 3, 1], 5: [[[1, 5], [2, 6], [2, 7], [2, 9], [4, 8]], True, 3, 1]}[N])
check('1', solve([[[2,N],[3,N+1]],[1,N+2],3]), {1: [[[1, 3], [2, 1], [3, 2]], True, 0, 2], 2: [[[1, 4], [2, 2], [3, 3]], True, 0, 2], 3: [[[1, 5], [2, 3], [3, 4]], True, 0, 2], 4: [[[1, 6], [2, 4], [3, 5]], True, 0, 2], 5: [[[1, 7], [2, 5], [3, 6]], True, 0, 2]}[N])
check('2', solve([[[1,N],[2,N+1]],[3,N+2],4]), {1: [[[1, 1], [2, 2], [3, 3]], True, 2, 0], 2: [[[1, 2], [2, 3], [3, 4]], True, 2, 0], 3: [[[1, 3], [2, 4], [3, 5]], True, 2, 0], 4: [[[1, 4], [2, 5], [3, 6]], True, 2, 0], 5: [[[1, 5], [2, 6], [3, 7]], True, 2, 0]}[N])
check('3', solve([[],[1,N],1]), {1: [[[1, 1]], True, 0, 0], 2: [[[1, 2]], True, 0, 0], 3: [[[1, 3]], True, 0, 0], 4: [[[1, 4]], True, 0, 0], 5: [[[1, 5]], True, 0, 0]}[N])
check('4', solve([[[1,N],[2,N+1]],[1,N+2],2]), {1: [[[1, 1], [2, 2]], False, None, 0], 2: [[[1, 2], [2, 3]], False, None, 0], 3: [[[1, 3], [2, 4]], False, None, 0], 4: [[[1, 4], [2, 5]], False, None, 0], 5: [[[1, 5], [2, 6]], False, None, 0]}[N])
check('5', solve([[[1,N],[3,N+1],[5,N+2]],[4,N+3],4]), {1: [[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1], 2: [[[1, 2], [3, 3], [4, 5], [5, 4]], True, 2, 1], 3: [[[1, 3], [3, 4], [4, 6], [5, 5]], True, 2, 1], 4: [[[1, 4], [3, 5], [4, 7], [5, 6]], True, 2, 1], 5: [[[1, 5], [3, 6], [4, 8], [5, 7]], True, 2, 1]}[N])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
0[[[1, 1], [2, 5], [2, 2], [2, 3], [4, 4]], True, 1, 3][[[1, 1], [2, 2], [2, 3], [2, 5], [4, 4]], True, 3, 1]Failed
1[[[1, 3], [2, 1], [3, 2]], True, 0, 2][[[1, 3], [2, 1], [3, 2]], True, 0, 2]Passed
2[[[1, 1], [2, 2], [3, 3]], True, 2, 0][[[1, 1], [2, 2], [3, 3]], True, 2, 0]Passed
3[[[1, 1]], True, 0, 0][[[1, 1]], True, 0, 0]Passed
4[[[1, 1], [2, 2]], False, None, 0][[[1, 1], [2, 2]], False, None, 0]Passed
5[[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1][[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1]Passed

SHA-256 / 27a4b4422aa2564e6c817625751e6283004ba63772285e6f9b311fb31f54dc1f

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    a,entry,cap=x
    if len(a)==cap:return [a,False,None,0]
    position=next((i for i,z in enumerate(a) if z[0]>entry[0]),len(a))
    result=a[:position]+[entry]+a[position:]
    shifted=len(a)-position
    return [result,True,position,shifted]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[[1,N],[2,N+1],[2,N+2],[4,N+3]],[2,N+4],6]), {1: [[[1, 1], [2, 2], [2, 3], [2, 5], [4, 4]], True, 3, 1], 2: [[[1, 2], [2, 3], [2, 4], [2, 6], [4, 5]], True, 3, 1], 3: [[[1, 3], [2, 4], [2, 5], [2, 7], [4, 6]], True, 3, 1], 4: [[[1, 4], [2, 5], [2, 6], [2, 8], [4, 7]], True, 3, 1], 5: [[[1, 5], [2, 6], [2, 7], [2, 9], [4, 8]], True, 3, 1]}[N])
check('1', solve([[[2,N],[3,N+1]],[1,N+2],3]), {1: [[[1, 3], [2, 1], [3, 2]], True, 0, 2], 2: [[[1, 4], [2, 2], [3, 3]], True, 0, 2], 3: [[[1, 5], [2, 3], [3, 4]], True, 0, 2], 4: [[[1, 6], [2, 4], [3, 5]], True, 0, 2], 5: [[[1, 7], [2, 5], [3, 6]], True, 0, 2]}[N])
check('2', solve([[[1,N],[2,N+1]],[3,N+2],4]), {1: [[[1, 1], [2, 2], [3, 3]], True, 2, 0], 2: [[[1, 2], [2, 3], [3, 4]], True, 2, 0], 3: [[[1, 3], [2, 4], [3, 5]], True, 2, 0], 4: [[[1, 4], [2, 5], [3, 6]], True, 2, 0], 5: [[[1, 5], [2, 6], [3, 7]], True, 2, 0]}[N])
check('3', solve([[],[1,N],1]), {1: [[[1, 1]], True, 0, 0], 2: [[[1, 2]], True, 0, 0], 3: [[[1, 3]], True, 0, 0], 4: [[[1, 4]], True, 0, 0], 5: [[[1, 5]], True, 0, 0]}[N])
check('4', solve([[[1,N],[2,N+1]],[1,N+2],2]), {1: [[[1, 1], [2, 2]], False, None, 0], 2: [[[1, 2], [2, 3]], False, None, 0], 3: [[[1, 3], [2, 4]], False, None, 0], 4: [[[1, 4], [2, 5]], False, None, 0], 5: [[[1, 5], [2, 6]], False, None, 0]}[N])
check('5', solve([[[1,N],[3,N+1],[5,N+2]],[4,N+3],4]), {1: [[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1], 2: [[[1, 2], [3, 3], [4, 5], [5, 4]], True, 2, 1], 3: [[[1, 3], [3, 4], [4, 6], [5, 5]], True, 2, 1], 4: [[[1, 4], [3, 5], [4, 7], [5, 6]], True, 2, 1], 5: [[[1, 5], [3, 6], [4, 8], [5, 7]], True, 2, 1]}[N])
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
0[[[1, 1], [2, 2], [2, 3], [2, 5], [4, 4]], True, 3, 1][[[1, 1], [2, 2], [2, 3], [2, 5], [4, 4]], True, 3, 1]Passed
1[[[1, 3], [2, 1], [3, 2]], True, 0, 2][[[1, 3], [2, 1], [3, 2]], True, 0, 2]Passed
2[[[1, 1], [2, 2], [3, 3]], True, 2, 0][[[1, 1], [2, 2], [3, 3]], True, 2, 0]Passed
3[[[1, 1]], True, 0, 0][[[1, 1]], True, 0, 0]Passed
4[[[1, 1], [2, 2]], False, None, 0][[[1, 1], [2, 2]], False, None, 0]Passed
5[[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1][[[1, 1], [3, 2], [4, 4], [5, 3]], True, 2, 1]Passed

SHA-256 / 55318437d1f6b54cfadcd8502e7911aef34a1bde5249a963c2d6be346732469c

Verification & scope

Offline finite deterministic model; no claim of production implementation or concurrent memory-model conformance. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:44:40.216116+00:00.

Case digest / e4acbbb227ae9d063a2a9cba8787122f60b0f9c5f4c2a5bc8658553e7edb9a9c