public int fixedWindowTemplate(int[] arr, int k) {
    int n = arr.length;
    if (n < k) return -1; // edge case: array smaller than window
 
    // Step 1: Initialize the first window
    int windowState = 0;
    for (int i = 0; i < k; i++) {
        windowState += arr[i]; // or whatever operation defines the state
    }
 
    int answer = windowState;
 
    // Step 2: Slide the window from position k to n-1
    for (int right = k; right < n; right++) {
        // Expand: add the incoming element on the right
        windowState += arr[right];
 
        // Contract: remove the outgoing element on the left
        // The outgoing element is at index (right - k)
        windowState -= arr[right - k];
 
        // Update answer
        answer = Math.max(answer, windowState);
    }
 
    return answer;
}

def fixed_window_template(arr: list, k: int) -> int:
    n = len(arr)
    if n < k:
        return -1  # edge case
 
    # Initialize the first window
    window_state = sum(arr[:k])
    answer = window_state
 
    # Slide the window
    for right in range(k, n):
        # Expand: add incoming element
        window_state += arr[right]
 
        # Contract: remove outgoing element
        # The outgoing element is at index (right - k)
        window_state -= arr[right - k]
 
        # Update answer
        answer = max(answer, window_state)
 
    return answer

public int variableWindowMaxLength(int[] arr, int constraint) {
    int left = 0;
    int windowState = 0; // represents the current window's metric
    int answer = 0;
 
    for (int right = 0; right < arr.length; right++) {
        // Expand: incorporate arr[right] into the window state
        windowState = incorporate(windowState, arr[right]);
 
        // Contract: while the window is invalid, shrink from the left
        while (isInvalid(windowState, constraint)) {
            windowState = remove(windowState, arr[left]);
            left++;
        }
 
        // At this point, window [left, right] is valid
        // Update the answer with the current valid window size
        answer = Math.max(answer, right - left + 1);
    }
 
    return answer;
}

public int variableWindowMinLength(int[] arr, int target) {
    int left = 0;
    int windowState = 0;
    int answer = Integer.MAX_VALUE;
 
    for (int right = 0; right < arr.length; right++) {
        // Expand
        windowState = incorporate(windowState, arr[right]);
 
        // Shrink aggressively as long as the window remains valid
        while (isValid(windowState, target)) {
            // Record the current valid window (try to minimize it)
            answer = Math.min(answer, right - left + 1);
 
            // Now shrink to see if we can find an even smaller valid window
            windowState = remove(windowState, arr[left]);
            left++;
        }
    }
 
    return answer == Integer.MAX_VALUE ? 0 : answer;
}

def variable_window_max_length(arr: list, constraint: int) -> int:
    left = 0
    window_state = {}  # or 0, or set() - depends on problem
    answer = 0
 
    for right in range(len(arr)):
        # Expand: add arr[right]
        window_state[arr[right]] = window_state.get(arr[right], 0) + 1
 
        # Contract: while invalid
        while not is_valid(window_state, constraint):
            window_state[arr[left]] -= 1
            if window_state[arr[left]] == 0:
                del window_state[arr[left]]
            left += 1
 
        # Window [left, right] is now valid
        answer = max(answer, right - left + 1)
 
    return answer
 
 
def variable_window_min_length(arr: list, target: int) -> int:
    left = 0
    current_sum = 0
    answer = float('inf')
 
    for right in range(len(arr)):
        current_sum += arr[right]
 
        while current_sum >= target:
            answer = min(answer, right - left + 1)
            current_sum -= arr[left]
            left += 1
 
    return 0 if answer == float('inf') else answer

public class MaxSumSubarrayK {
 
    public static int maxSum(int[] arr, int k) {
        int n = arr.length;
        if (n < k) {
            throw new IllegalArgumentException("Array size smaller than k");
        }
 
        // Build the first window
        int currentSum = 0;
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
 
        int maxSum = currentSum;
 
        // Slide the window across the rest of the array
        for (int right = k; right < n; right++) {
            // The magic: O(1) update instead of recomputing the entire sum
            currentSum += arr[right];       // add new element entering the window
            currentSum -= arr[right - k];   // remove element leaving the window
 
            maxSum = Math.max(maxSum, currentSum);
        }
 
        return maxSum;
    }
 
    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println(maxSum(arr, k)); // Output: 9 (subarray [5,1,3])
    }
}

def max_sum_subarray_k(arr: list[int], k: int) -> int:
    if len(arr) < k:
        raise ValueError("Array size smaller than k")
 
    # Build the first window
    current_sum = sum(arr[:k])
    max_sum = current_sum
 
    # Slide
    for right in range(k, len(arr)):
        current_sum += arr[right]
        current_sum -= arr[right - k]
        max_sum = max(max_sum, current_sum)
 
    return max_sum
 
# Test
arr = [2, 1, 5, 1, 3, 2]
print(max_sum_subarray_k(arr, 3))  # Output: 9

public double findMaxAverage(int[] nums, int k) {
    double windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
 
    double maxSum = windowSum;
 
    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right];
        windowSum -= nums[right - k];
        maxSum = Math.max(maxSum, windowSum);
    }
 
    return maxSum / k;
}

import java.util.*;
 
public class FindAllAnagrams {
 
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;
 
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        int k = p.length();
 
        // Build frequency maps for the pattern and the first window
        for (int i = 0; i < k; i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }
 
        // Count how many characters already match
        int matches = 0;
        for (int i = 0; i < 26; i++) {
            if (pCount[i] <mark class="obsidian-highlight"> sCount[i]) matches++;
        }
 
        if (matches </mark> 26) result.add(0);
 
        for (int right = k; right < s.length(); right++) {
            // Add the new character entering the window
            int incoming = s.charAt(right) - 'a';
            sCount[incoming]++;
            if (sCount[incoming] <mark class="obsidian-highlight"> pCount[incoming]) {
                matches++;
            } else if (sCount[incoming] </mark> pCount[incoming] + 1) {
                // This character just became mismatched (was previously matched)
                matches--;
            }
 
            // Remove the character leaving the window
            int outgoing = s.charAt(right - k) - 'a';
            sCount[outgoing]--;
            if (sCount[outgoing] <mark class="obsidian-highlight"> pCount[outgoing]) {
                matches++;
            } else if (sCount[outgoing] </mark> pCount[outgoing] - 1) {
                matches--;
            }
 
            if (matches == 26) result.add(right - k + 1);
        }
 
        return result;
    }
}

from collections import Counter
 
def find_anagrams(s: str, p: str) -> list[int]:
    if len(s) < len(p):
        return []
 
    k = len(p)
    p_count = Counter(p)
    s_count = Counter(s[:k])
    result = []
 
    if s_count == p_count:
        result.append(0)
 
    for right in range(k, len(s)):
        # Add incoming character
        incoming = s[right]
        s_count[incoming] += 1
 
        # Remove outgoing character
        outgoing = s[right - k]
        s_count[outgoing] -= 1
        if s_count[outgoing] <mark class="obsidian-highlight"> 0:
            del s_count[outgoing]
 
        if s_count </mark> p_count:
            result.append(right - k + 1)
 
    return result

import java.util.*;
 
public class SlidingWindowMaximum {
 
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // Deque stores indices; front = index of current window's max
        Deque<Integer> deque = new ArrayDeque<>();
 
        for (int right = 0; right < n; right++) {
            // Remove indices that are out of the current window
            while (!deque.isEmpty() && deque.peekFirst() < right - k + 1) {
                deque.pollFirst();
            }
 
            // Remove from the back all indices whose values are smaller
            // than the current element - they are useless candidates
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[right]) {
                deque.pollLast();
            }
 
            deque.offerLast(right);
 
            // Start recording results once the first full window is formed
            if (right >= k - 1) {
                result[right - k + 1] = nums[deque.peekFirst()];
            }
        }
 
        return result;
    }
}

from collections import deque
 
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    result = []
    dq = deque()  # stores indices
 
    for right in range(len(nums)):
        # Remove out-of-window indices from front
        while dq and dq[0] < right - k + 1:
            dq.popleft()
 
        # Remove smaller elements from the back
        while dq and nums[dq[-1]] < nums[right]:
            dq.pop()
 
        dq.append(right)
 
        # Record result once first full window is complete
        if right >= k - 1:
            result.append(nums[dq[0]])
 
    return result

import java.util.*;
 
public class LongestSubstringNoRepeat {
 
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;
 
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
 
            // If the character exists in the window, move left past its last occurrence
            // This collapses the while-loop shrink into a single jump
            if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
                left = charIndex.get(c) + 1;
            }
 
            // Record the latest position of this character
            charIndex.put(c, right);
 
            // Update answer
            maxLength = Math.max(maxLength, right - left + 1);
        }
 
        return maxLength;
    }
}

def length_of_longest_substring(s: str) -> int:
    char_index = {}
    left = 0
    max_length = 0
 
    for right, c in enumerate(s):
        if c in char_index and char_index[c] >= left:
            left = char_index[c] + 1
 
        char_index[c] = right
        max_length = max(max_length, right - left + 1)
 
    return max_length

import java.util.*;
 
public class LongestKDistinct {
 
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0) return 0;
 
        Map<Character, Integer> freq = new HashMap<>();
        int left = 0;
        int maxLength = 0;
 
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            freq.put(c, freq.getOrDefault(c, 0) + 1);
 
            // Contract: too many distinct characters
            while (freq.size() > k) {
                char leftChar = s.charAt(left);
                freq.put(leftChar, freq.get(leftChar) - 1);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }
 
            maxLength = Math.max(maxLength, right - left + 1);
        }
 
        return maxLength;
    }
}

from collections import defaultdict
 
def longest_k_distinct(s: str, k: int) -> int:
    if k == 0:
        return 0
 
    freq = defaultdict(int)
    left = 0
    max_length = 0
 
    for right, c in enumerate(s):
        freq[c] += 1
 
        while len(freq) > k:
            left_char = s[left]
            freq[left_char] -= 1
            if freq[left_char] == 0:
                del freq[left_char]
            left += 1
 
        max_length = max(max_length, right - left + 1)
 
    return max_length

import java.util.*;
 
public class MinimumWindowSubstring {
 
    public String minWindow(String s, String t) {
        if (s.isEmpty() || t.isEmpty()) return "";
 
        // Required frequency of each character in t
        Map<Character, Integer> required = new HashMap<>();
        for (char c : t.toCharArray()) {
            required.put(c, required.getOrDefault(c, 0) + 1);
        }
 
        int totalRequired = required.size(); // number of unique chars needed
        int formed = 0; // number of unique chars in window meeting required frequency
 
        Map<Character, Integer> windowCounts = new HashMap<>();
        int left = 0;
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
 
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);
 
            // Check if this character's frequency in the window
            // matches its required frequency
            if (required.containsKey(c) &&
                windowCounts.get(c).intValue() <mark class="obsidian-highlight"> required.get(c).intValue()) {
                formed++;
            }
 
            // Contract: try to shrink the window while it remains valid
            while (formed </mark> totalRequired && left <= right) {
                // Update the answer if this window is smaller
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }
 
                // Remove the leftmost character
                char leftChar = s.charAt(left);
                windowCounts.put(leftChar, windowCounts.get(leftChar) - 1);
                if (required.containsKey(leftChar) &&
                    windowCounts.get(leftChar) < required.get(leftChar)) {
                    formed--;
                }
                left++;
            }
        }
 
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }
}

from collections import Counter, defaultdict
 
def min_window(s: str, t: str) -> str:
    if not s or not t:
        return ""
 
    required = Counter(t)
    total_required = len(required)  # number of unique chars to satisfy
    formed = 0
 
    window_counts = defaultdict(int)
    left = 0
    min_len = float('inf')
    min_left = 0
 
    for right, c in enumerate(s):
        window_counts[c] += 1
 
        if c in required and window_counts[c] == required[c]:
            formed += 1
 
        while formed == total_required:
            # Update answer
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left
 
            # Shrink from left
            left_char = s[left]
            window_counts[left_char] -= 1
            if left_char in required and window_counts[left_char] < required[left_char]:
                formed -= 1
            left += 1
 
    return "" if min_len == float('inf') else s[min_left:min_left + min_len]

public class MinSizeSubarraySum {
 
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int currentSum = 0;
        int minLength = Integer.MAX_VALUE;
 
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
 
            // As long as the window is valid, record and try to shrink
            while (currentSum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }
 
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

def min_subarray_len(target: int, nums: list[int]) -> int:
    left = 0
    current_sum = 0
    min_length = float('inf')
 
    for right, num in enumerate(nums):
        current_sum += num
 
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
 
    return 0 if min_length == float('inf') else min_length

public class LongestRepeatingReplacement {
 
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int left = 0;
        int maxFreq = 0; // max frequency of any single character in the window
        int maxLength = 0;
 
        for (int right = 0; right < s.length(); right++) {
            int c = s.charAt(right) - 'A';
            freq[c]++;
            maxFreq = Math.max(maxFreq, freq[c]);
 
            // Check validity: replacements needed = window_size - maxFreq
            // If replacements needed > k, the window is invalid
            int windowSize = right - left + 1;
            if (windowSize - maxFreq > k) {
                // Shrink by one from the left
                freq[s.charAt(left) - 'A']--;
                left++;
                // Note: maxFreq may be stale but that is intentional and safe.
                // We never need to decrease maxFreq because a smaller window
                // with a lower maxFreq cannot give us a longer answer.
            }
 
            maxLength = Math.max(maxLength, right - left + 1);
        }
 
        return maxLength;
    }
}

def character_replacement(s: str, k: int) -> int:
    freq = [0] * 26
    left = 0
    max_freq = 0
    max_length = 0
 
    for right, c in enumerate(s):
        idx = ord(c) - ord('A')
        freq[idx] += 1
        max_freq = max(max_freq, freq[idx])
 
        window_size = right - left + 1
        if window_size - max_freq > k:
            freq[ord(s[left]) - ord('A')] -= 1
            left += 1
 
        max_length = max(max_length, right - left + 1)
 
    return max_length

public class SubarraysProductLessK {
 
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
 
        int left = 0;
        int product = 1;
        int count = 0;
 
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
 
            while (product >= k) {
                product /= nums[left];
                left++;
            }
 
            // All subarrays [left, right], [left+1, right], ..., [right, right]
            // are valid. That is (right - left + 1) subarrays.
            count += right - left + 1;
        }
 
        return count;
    }
}

import java.util.*;
 
public class ExactlyKDistinct {
 
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMostK(nums, k) - atMostK(nums, k - 1);
    }
 
    private int atMostK(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int left = 0;
        int count = 0;
 
        for (int right = 0; right < nums.length; right++) {
            freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);
 
            while (freq.size() > k) {
                freq.put(nums[left], freq.get(nums[left]) - 1);
                if (freq.get(nums[left]) == 0) {
                    freq.remove(nums[left]);
                }
                left++;
            }
 
            count += right - left + 1;
        }
 
        return count;
    }
}

import heapq
from collections import defaultdict
 
def median_sliding_window(nums: list[int], k: int) -> list[float]:
    # Max-heap (inverted) for the lower half
    # Min-heap for the upper half
    lo = []   # max-heap (negate values)
    hi = []   # min-heap
    lazy_del = defaultdict(int)  # lazy deletion tracker
 
    result = []
 
    def get_median():
        if k % 2 == 1:
            return float(hi[0])
        return (-lo[0] + hi[0]) / 2.0
 
    def balance():
        # Ensure hi has ceil(k/2) elements and lo has floor(k/2)
        while len(hi) > len(lo) + 1:
            heapq.heappush(lo, -heapq.heappop(hi))
        while len(lo) > len(hi):
            heapq.heappush(hi, -heapq.heappop(lo))
 
    def prune(heap, sign):
        # Remove lazily deleted elements from the top
        while heap and lazy_del[sign * heap[0]] > 0:
            lazy_del[sign * heap[0]] -= 1
            heapq.heappop(heap)
 
    # Build the first window
    for i in range(k):
        heapq.heappush(hi, nums[i])
 
    for _ in range(k // 2):
        heapq.heappush(lo, -heapq.heappop(hi))
 
    result.append(get_median())
 
    for right in range(k, len(nums)):
        incoming = nums[right]
        outgoing = nums[right - k]
 
        # Add incoming
        if incoming >= hi[0]:
            heapq.heappush(hi, incoming)
        else:
            heapq.heappush(lo, -incoming)
 
        # Lazily mark outgoing for deletion
        lazy_del[outgoing] += 1
 
        # Prune tops of heaps if they are marked for deletion
        prune(hi, 1)
        prune(lo, -1)
 
        balance()
        prune(hi, 1)
        prune(lo, -1)
 
        result.append(get_median())
 
    return result

HystrixCommandProperties.Setter()
    // THE ROLLING WINDOW
    .withMetricsRollingStatisticalWindowInMilliseconds(10000) // window size = 10 seconds
    .withMetricsRollingStatisticalWindowBuckets(10)           // number of buckets = 10
    // bucket width = 10000 / 10 = 1000ms per bucket
 
    // CIRCUIT BREAKER DECISION
    .withCircuitBreakerRequestVolumeThreshold(20)    // minimum calls in the window
                                                     // before the circuit CAN open
                                                     // (prevents opening on 1 failure out of 1 call)
    .withCircuitBreakerErrorThresholdPercentage(50)  // failure rate % to open the circuit
    .withCircuitBreakerSleepWindowInMilliseconds(5000) // how long to stay OPEN before
                                                       // trying HALF-OPEN probe
 
    // EXECUTION
    .withExecutionTimeoutInMilliseconds(1000)         // a timeout counts as a FAILURE
                                                      // in the rolling window
 
    // PERCENTILE WINDOW (separate from circuit breaker window - for latency metrics)
    .withMetricsRollingPercentileWindowInMilliseconds(60000) // 60 second window for latency
    .withMetricsRollingPercentileWindowBuckets(6)            // 6 buckets = 10 seconds each
    .withMetricsRollingPercentileEnabled(true)               // track p50, p75, p95, p99 latencies

import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
 
/**
 * HystrixStyleCircuitBreaker
 *
 * Reproduces Hystrix's core internal design:
 *   - Rolling window divided into fixed-size time buckets
 *   - Each bucket aggregates call counts (success, failure, timeout)
 *   - Window slides by dropping the oldest bucket every bucketWidthMs
 *   - Circuit opens when: window is full AND failureRate >= threshold
 *   - Circuit re-probes after sleepWindowMs (HALF-OPEN)
 *
 * Default configuration mirrors Hystrix defaults:
 *   windowSizeMs    = 10000  (10 seconds)
 *   numBuckets      = 10     (1 second per bucket)
 *   minRequests     = 20     (requestVolumeThreshold)
 *   errorThreshold  = 50%    (circuitBreakerErrorThresholdPercentage)
 *   sleepWindowMs   = 5000   (circuitBreakerSleepWindowInMilliseconds)
 */
public class HystrixStyleCircuitBreaker {
 
    // -------------------------------------------------------------------------
    // A single time bucket - aggregates all calls within one time slice
    // Uses AtomicLong so multiple threads can write concurrently without locks
    // -------------------------------------------------------------------------
    static class Bucket {
        final long bucketStartMs;           // wall-clock start of this bucket
        final AtomicLong successCount  = new AtomicLong(0);
        final AtomicLong failureCount  = new AtomicLong(0);
        final AtomicLong timeoutCount  = new AtomicLong(0);
        // Total calls = success + failure + timeout
        // Failure rate = (failure + timeout) / total
 
        Bucket(long startMs) {
            this.bucketStartMs = startMs;
        }
 
        long total()    { return successCount.get() + failureCount.get() + timeoutCount.get(); }
        long failures() { return failureCount.get() + timeoutCount.get(); }
    }
 
    // -------------------------------------------------------------------------
    // The rolling window - a circular array of Bucket objects
    // -------------------------------------------------------------------------
    static class RollingWindow {
        private final Bucket[] buckets;      // circular array
        private final int      numBuckets;
        private final long     bucketWidthMs;
        private final long     windowSizeMs;
 
        // AtomicReference allows lock-free swap of the "current bucket" pointer
        private final AtomicReference<Bucket> currentBucketRef;
 
        RollingWindow(int numBuckets, long windowSizeMs) {
            this.numBuckets    = numBuckets;
            this.windowSizeMs  = windowSizeMs;
            this.bucketWidthMs = windowSizeMs / numBuckets;
            this.buckets       = new Bucket[numBuckets];
 
            long now = System.currentTimeMillis();
            // Pre-fill all slots with empty buckets so reads are never null
            for (int i = 0; i < numBuckets; i++) {
                buckets[i] = new Bucket(now - (numBuckets - i) * bucketWidthMs);
            }
            currentBucketRef = new AtomicReference<>(buckets[numBuckets - 1]);
        }
 
        /**
         * Returns the bucket that should receive the current call.
         * Creates a new bucket if the current second has rolled over.
         * This is the "slide" operation: old bucket is overwritten by new one.
         */
        Bucket getCurrentBucket() {
            long now      = System.currentTimeMillis();
            Bucket current = currentBucketRef.get();
 
            // Still within the same bucket's time slice - no slide needed
            if (now < current.bucketStartMs + bucketWidthMs) {
                return current;
            }
 
            // Time has moved past the current bucket - need to create new bucket(s)
            // and slide the window forward
            synchronized (this) {
                // Re-check inside the lock (another thread may have already slid)
                current = currentBucketRef.get();
                if (now < current.bucketStartMs + bucketWidthMs) {
                    return current;
                }
 
                // Calculate how many buckets we need to advance
                // (could be more than 1 if the system was idle for multiple seconds)
                long newBucketStartMs = current.bucketStartMs + bucketWidthMs;
                int  bucketsMissed    = (int) ((now - newBucketStartMs) / bucketWidthMs);
 
                // Fill any missed buckets with empty ones (no calls happened in that time)
                // This ensures stale data from a busy period does not persist
                for (int i = 0; i <= bucketsMissed; i++) {
                    long slotStart = newBucketStartMs + (i * bucketWidthMs);
                    int  slot      = computeSlot(slotStart);
 
                    // Overwrite the slot - this evicts the oldest data (the "slide")
                    buckets[slot] = new Bucket(slotStart);
                }
 
                // Point the current bucket reference at the newest slot
                long  newestStart  = newBucketStartMs + (bucketsMissed * bucketWidthMs);
                Bucket newCurrent  = buckets[computeSlot(newestStart)];
                currentBucketRef.set(newCurrent);
                return newCurrent;
            }
        }
 
        /**
         * Maps a bucket's start timestamp to its slot in the circular array.
         * Two buckets that are `windowSizeMs` apart map to the same slot,
         * which is why writing a new bucket naturally evicts the old one.
         */
        private int computeSlot(long bucketStartMs) {
            long bucketNumber = bucketStartMs / bucketWidthMs;
            return (int) (bucketNumber % numBuckets);
        }
 
        /**
         * Reads all buckets that fall within the current rolling window.
         * Buckets older than windowSizeMs are ignored.
         */
        WindowSnapshot snapshot() {
            long now         = System.currentTimeMillis();
            long windowStart = now - windowSizeMs;
 
            long totalCalls   = 0;
            long totalFails   = 0;
 
            for (Bucket b : buckets) {
                // Only count buckets that are within the rolling window
                if (b.bucketStartMs >= windowStart) {
                    totalCalls += b.total();
                    totalFails += b.failures();
                }
            }
            return new WindowSnapshot(totalCalls, totalFails);
        }
    }
 
    // Immutable snapshot of the window totals at a point in time
    record WindowSnapshot(long totalCalls, long totalFailures) {
        double failureRate() {
            return totalCalls == 0 ? 0.0 : (double) totalFailures / totalCalls * 100.0;
        }
    }
 
    // -------------------------------------------------------------------------
    // Circuit states
    // -------------------------------------------------------------------------
    enum State { CLOSED, OPEN, HALF_OPEN }
 
    // -------------------------------------------------------------------------
    // Circuit Breaker Configuration (mirrors Hystrix property names)
    // -------------------------------------------------------------------------
    record Config(
        int    numBuckets,              // metricsRollingStatisticalWindowBuckets      default: 10
        long   windowSizeMs,            // metricsRollingStatisticalWindowInMilliseconds default: 10000
        int    requestVolumeThreshold,  // circuitBreakerRequestVolumeThreshold         default: 20
        double errorThresholdPercent,   // circuitBreakerErrorThresholdPercentage       default: 50.0
        long   sleepWindowMs            // circuitBreakerSleepWindowInMilliseconds       default: 5000
    ) {
        static Config defaults() {
            return new Config(10, 10_000, 20, 50.0, 5_000);
        }
    }
 
    // -------------------------------------------------------------------------
    // Circuit Breaker State Machine
    // -------------------------------------------------------------------------
    private final Config        config;
    private final RollingWindow window;
 
    private volatile State  state      = State.CLOSED;
    private volatile long   openedAtMs = 0;
 
    public HystrixStyleCircuitBreaker(Config config) {
        this.config = config;
        this.window = new RollingWindow(config.numBuckets(), config.windowSizeMs());
    }
 
    /**
     * Call this BEFORE making the actual remote call.
     * Returns true if the request should be allowed through.
     * Returns false if the circuit is OPEN (fail-fast).
     */
    public boolean allowRequest() {
        if (state <mark class="obsidian-highlight"> State.CLOSED) {
            return true;
        }
 
        if (state </mark> State.OPEN) {
            long elapsed = System.currentTimeMillis() - openedAtMs;
            if (elapsed >= config.sleepWindowMs()) {
                // Sleep window has expired - allow one probe request (HALF-OPEN)
                state = State.HALF_OPEN;
                System.out.println("[CIRCUIT] State -> HALF_OPEN (probing recovery)");
                return true;
            }
            // Still within sleep window - reject immediately
            window.getCurrentBucket().failureCount.incrementAndGet(); // count as short-circuit
            return false;
        }
 
        // HALF_OPEN: allow the probe through
        return true;
    }
 
    /**
     * Call this AFTER the remote call succeeds.
     */
    public void recordSuccess() {
        window.getCurrentBucket().successCount.incrementAndGet();
 
        if (state <mark class="obsidian-highlight"> State.HALF_OPEN) {
            // Probe succeeded - the downstream service has recovered
            reset();
        }
    }
 
    /**
     * Call this AFTER the remote call fails (exception, non-2xx response, etc.)
     */
    public void recordFailure() {
        window.getCurrentBucket().failureCount.incrementAndGet();
        evaluateThreshold();
    }
 
    /**
     * Call this when the remote call times out.
     * Hystrix distinguishes timeouts from failures for metrics, but both trip the circuit.
     */
    public void recordTimeout() {
        window.getCurrentBucket().timeoutCount.incrementAndGet();
        evaluateThreshold();
    }
 
    /**
     * After every failure or timeout, check if the circuit should open.
     * Mirrors Hystrix's isOpen() logic exactly.
     */
    private void evaluateThreshold() {
        if (state </mark> State.HALF_OPEN) {
            // Probe failed - re-open the circuit
            tripBreaker();
            return;
        }
 
        if (state == State.OPEN) {
            return; // already open, nothing to evaluate
        }
 
        // CLOSED state: evaluate the rolling window
        WindowSnapshot snap = window.snapshot();
 
        // Gate 1: requestVolumeThreshold - do not open on tiny sample sizes
        if (snap.totalCalls() < config.requestVolumeThreshold()) {
            System.out.printf("[CIRCUIT] Calls in window: %d (below minimum %d) - staying CLOSED%n",
                snap.totalCalls(), config.requestVolumeThreshold());
            return;
        }
 
        // Gate 2: errorThresholdPercentage
        if (snap.failureRate() >= config.errorThresholdPercent()) {
            System.out.printf("[CIRCUIT] Failure rate: %.1f%% >= threshold %.1f%% - OPENING%n",
                snap.failureRate(), config.errorThresholdPercent());
            tripBreaker();
        }
    }
 
    private void tripBreaker() {
        state      = State.OPEN;
        openedAtMs = System.currentTimeMillis();
        System.out.println("[CIRCUIT] State -> OPEN");
    }
 
    private void reset() {
        state = State.CLOSED;
        // Hystrix does NOT clear the rolling window on reset.
        // The old failure data ages out naturally as time buckets expire.
        // This is intentional: if the service recovers but then fails again,
        // the circuit re-opens quickly because the failure history is still in the window.
        System.out.println("[CIRCUIT] State -> CLOSED (recovered)");
    }
 
    public State getState() { return state; }
 
    public WindowSnapshot getMetrics() { return window.snapshot(); }
 
    // -------------------------------------------------------------------------
    // Convenience: wrap a remote call with full circuit breaker protection
    // -------------------------------------------------------------------------
    @FunctionalInterface
    public interface RemoteCall<T> {
        T execute() throws Exception;
    }
 
    public <T> T execute(RemoteCall<T> call, T fallback) {
        if (!allowRequest()) {
            System.out.println("[CIRCUIT] Short-circuited - returning fallback");
            return fallback;
        }
 
        long startMs = System.currentTimeMillis();
        try {
            T result = call.execute();
            recordSuccess();
            return result;
        } catch (Exception e) {
            long elapsed = System.currentTimeMillis() - startMs;
            if (elapsed >= 1000) { // treat calls taking > 1s as timeouts
                recordTimeout();
            } else {
                recordFailure();
            }
            System.out.println("[CIRCUIT] Call failed: " + e.getMessage());
            return fallback;
        }
    }
 
    // -------------------------------------------------------------------------
    // Demo: simulate a service going down and recovering
    // -------------------------------------------------------------------------
    public static void main(String[] args) throws InterruptedException {
        HystrixStyleCircuitBreaker cb = new HystrixStyleCircuitBreaker(
            new Config(
                10,     // 10 buckets
                10_000, // 10-second window
                5,      // min 5 requests (lowered for demo)
                50.0,   // 50% failure threshold
                3_000   // 3-second sleep window (lowered for demo)
            )
        );
 
        System.out.println("=<mark class="obsidian-highlight"> Phase 1: Healthy service (should stay CLOSED) </mark>=");
        for (int i = 0; i < 6; i++) {
            cb.execute(() -> "OK", "FALLBACK");
        }
        System.out.println("State: " + cb.getState());
 
        System.out.println("\n=<mark class="obsidian-highlight"> Phase 2: Service degrades - 70% failures </mark>=");
        for (int i = 0; i < 10; i++) {
            if (i < 7) {
                // Simulate failure
                cb.execute(() -> { throw new RuntimeException("Connection refused"); }, "FALLBACK");
            } else {
                cb.execute(() -> "OK", "FALLBACK");
            }
        }
        System.out.println("State: " + cb.getState());
        WindowSnapshot snap = cb.getMetrics();
        System.out.printf("Window: %d total calls, %.1f%% failure rate%n",
            snap.totalCalls(), snap.failureRate());
 
        System.out.println("\n=<mark class="obsidian-highlight"> Phase 3: Circuit is OPEN - all calls short-circuited </mark>=");
        for (int i = 0; i < 5; i++) {
            String result = cb.execute(() -> "OK", "FALLBACK");
            System.out.println("Result: " + result);
        }
 
        System.out.println("\n=<mark class="obsidian-highlight"> Phase 4: Wait for sleep window, then probe (HALF-OPEN) </mark>=");
        System.out.println("Waiting 3 seconds for sleep window...");
        Thread.sleep(3_100);
 
        System.out.println("Service has recovered - probe should succeed:");
        String result = cb.execute(() -> "RECOVERED", "FALLBACK");
        System.out.println("Probe result: " + result);
        System.out.println("State after recovery: " + cb.getState());
    }
}

"""
hystrix_circuit_breaker.py
===========================
A faithful reproduction of Hystrix's internal bucket-based rolling window
circuit breaker in Python. Every design decision mirrors the Java original:
 
  - Time bucketed rolling window (not per-call)
  - Atomic-style thread-safe bucket writes (via threading.Lock per bucket)
  - requestVolumeThreshold gate before evaluating error rate
  - Three-state machine: CLOSED -> OPEN -> HALF_OPEN -> CLOSED
  - Stale buckets are NOT cleared on reset (ages out naturally)
"""
 
import time
import threading
from dataclasses import dataclass, field
from enum import Enum
from typing import Callable, TypeVar, Optional
 
T = TypeVar('T')
 
 
# ===========================================================================<mark class="obsidian-highlight">
# Configuration - property names mirror Hystrix exactly
# </mark>===========================================================================
 
@dataclass(frozen=True)
class HystrixConfig:
    """
    All times in seconds for readability (Hystrix uses milliseconds internally).
    """
    metrics_rolling_statistical_window_seconds: float = 10.0
    metrics_rolling_statistical_window_buckets: int   = 10
    circuit_breaker_request_volume_threshold: int     = 20
    circuit_breaker_error_threshold_percentage: float = 50.0
    circuit_breaker_sleep_window_seconds: float       = 5.0
 
    @property
    def bucket_width_seconds(self) -> float:
        return (self.metrics_rolling_statistical_window_seconds /
                self.metrics_rolling_statistical_window_buckets)
 
 
# ===========================================================================<mark class="obsidian-highlight">
# Time Bucket - one time slice in the rolling window
# </mark>===========================================================================
 
class Bucket:
    """
    Aggregates all call outcomes for a fixed time slice.
    Thread-safe: uses a reentrant lock for counter updates.
    In production this would use atomics; Python's GIL gives some safety
    but explicit locking makes the intent clear.
    """
 
    def __init__(self, start_time: float):
        self.start_time: float = start_time
        self._lock = threading.Lock()
        self.success_count: int = 0
        self.failure_count: int = 0
        self.timeout_count: int = 0
 
    def record_success(self):
        with self._lock:
            self.success_count += 1
 
    def record_failure(self):
        with self._lock:
            self.failure_count += 1
 
    def record_timeout(self):
        with self._lock:
            self.timeout_count += 1
 
    @property
    def total(self) -> int:
        return self.success_count + self.failure_count + self.timeout_count
 
    @property
    def failures(self) -> int:
        # Hystrix counts both failures AND timeouts against the error rate
        return self.failure_count + self.timeout_count
 
    def __repr__(self) -> str:
        return (f"Bucket(t={self.start_time:.1f}, "
                f"S={self.success_count}, F={self.failure_count}, "
                f"T={self.timeout_count})")
 
 
# ===========================================================================<mark class="obsidian-highlight">
# Rolling Window - circular array of Buckets
# </mark>=========================================================================<mark class="obsidian-highlight">
 
@dataclass
class WindowSnapshot:
    total_calls: int
    total_failures: int
 
    @property
    def failure_rate(self) -> float:
        if self.total_calls </mark> 0:
            return 0.0
        return (self.total_failures / self.total_calls) * 100.0
 
 
class RollingWindow:
    """
    Hystrix-style rolling window implemented as a circular array of Buckets.
 
    Key properties:
      - numBuckets slots in a circular array.
      - Each slot represents one time slice of width `bucket_width_seconds`.
      - The "current" slot is determined by wall-clock time.
      - When time advances past the current bucket, new empty buckets are
        written into the circular array, naturally evicting old data.
        This is the "slide" operation.
    """
 
    def __init__(self, config: HystrixConfig):
        self._config  = config
        self._n       = config.metrics_rolling_statistical_window_buckets
        self._width   = config.bucket_width_seconds
        self._window  = config.metrics_rolling_statistical_window_seconds
        self._lock    = threading.Lock()
 
        # Pre-populate circular array with empty buckets
        now = time.time()
        self._buckets: list[Bucket] = [
            Bucket(now - (self._n - i) * self._width)
            for i in range(self._n)
        ]
        self._current_bucket: Bucket = self._buckets[-1]
 
    def _slot_for(self, bucket_start: float) -> int:
        """
        Maps a bucket's start time to its position in the circular array.
        Two bucket starts that are `window_seconds` apart map to the same slot,
        meaning a new bucket naturally evicts the old one at that position.
        """
        bucket_number = int(bucket_start / self._width)
        return bucket_number % self._n
 
    def get_current_bucket(self) -> Bucket:
        """
        Returns the bucket for the current moment in time.
        If the clock has moved past the current bucket, creates new buckets
        (overwriting stale ones in the circular array) and slides the window.
        """
        now = time.time()
 
        # Fast path: still within the current bucket's time slice
        if now < self._current_bucket.start_time + self._width:
            return self._current_bucket
 
        # Slow path: time has advanced, need to slide the window
        with self._lock:
            # Re-check after acquiring lock (another thread may have slid already)
            if now < self._current_bucket.start_time + self._width:
                return self._current_bucket
 
            new_start      = self._current_bucket.start_time + self._width
            buckets_missed = int((now - new_start) / self._width)
 
            # Fill in any missed buckets with empty ones
            # (handles the case where the system was idle for several seconds)
            for i in range(buckets_missed + 1):
                slot_start = new_start + i * self._width
                slot       = self._slot_for(slot_start)
                # SLIDE: overwriting this slot evicts the bucket that was here
                # (which is exactly `window_seconds` in the past)
                self._buckets[slot] = Bucket(slot_start)
 
            # Point current bucket at the newest slot
            newest_start          = new_start + buckets_missed * self._width
            newest_slot           = self._slot_for(newest_start)
            self._current_bucket  = self._buckets[newest_slot]
            return self._current_bucket
 
    def snapshot(self) -> WindowSnapshot:
        """
        Reads all buckets within the rolling window and returns aggregate totals.
        Buckets older than `window_seconds` are excluded.
        """
        window_start  = time.time() - self._window
        total_calls   = 0
        total_failures = 0
 
        for bucket in self._buckets:
            if bucket.start_time >= window_start:
                total_calls    += bucket.total
                total_failures += bucket.failures
 
        return WindowSnapshot(total_calls, total_failures)
 
 
# ===========================================================================<mark class="obsidian-highlight">
# Circuit Breaker State Machine
# </mark>===========================================================================
 
class CircuitState(Enum):
    CLOSED    = "CLOSED"
    OPEN      = "OPEN"
    HALF_OPEN = "HALF_OPEN"
 
 
class HystrixCircuitBreaker:
    """
    Hystrix-style circuit breaker with rolling bucket window.
 
    Usage:
        cb = HystrixCircuitBreaker(HystrixConfig(
            metrics_rolling_statistical_window_seconds=10,
            metrics_rolling_statistical_window_buckets=10,
            circuit_breaker_request_volume_threshold=20,
            circuit_breaker_error_threshold_percentage=50.0,
            circuit_breaker_sleep_window_seconds=5.0
        ))
 
        if cb.allow_request():
            try:
                result = call_remote_service()
                cb.record_success()
            except Exception as e:
                cb.record_failure()
        else:
            result = fallback_value
    """
 
    def __init__(self, config: HystrixConfig = HystrixConfig()):
        self._config     = config
        self._window     = RollingWindow(config)
        self._state      = CircuitState.CLOSED
        self._opened_at: Optional[float] = None
        self._state_lock = threading.Lock()
 
    @property
    def state(self) -> CircuitState:
        return self._state
 
    def allow_request(self) -> bool:
        """
        Gate: should this request be allowed through?
        Called BEFORE making the remote call.
        """
        if self._state <mark class="obsidian-highlight"> CircuitState.CLOSED:
            return True
 
        if self._state </mark> CircuitState.OPEN:
            elapsed = time.time() - self._opened_at
            if elapsed >= self._config.circuit_breaker_sleep_window_seconds:
                with self._state_lock:
                    # Double-check pattern (another thread may have transitioned already)
                    if self._state == CircuitState.OPEN:
                        self._state = CircuitState.HALF_OPEN
                        print("[CIRCUIT] State -> HALF_OPEN (probing recovery)")
                return True
            # Still within sleep window: short-circuit the request
            return False
 
        # HALF_OPEN: allow the single probe through
        return True
 
    def record_success(self):
        """Call this after a successful remote call."""
        self._window.get_current_bucket().record_success()
 
        if self._state <mark class="obsidian-highlight"> CircuitState.HALF_OPEN:
            self._reset()
 
    def record_failure(self):
        """Call this after a failed remote call (exception or error response)."""
        self._window.get_current_bucket().record_failure()
        self._evaluate()
 
    def record_timeout(self):
        """
        Call this when the remote call exceeds the configured timeout.
        Hystrix tracks timeouts separately from failures in metrics,
        but both contribute equally to the error rate.
        """
        self._window.get_current_bucket().record_timeout()
        self._evaluate()
 
    def get_metrics(self) -> WindowSnapshot:
        """Returns a snapshot of current rolling window statistics."""
        return self._window.snapshot()
 
    def _evaluate(self):
        """
        Mirrors Hystrix's isOpen() calculation.
        Only trips the circuit from CLOSED state.
        From HALF_OPEN, any failure immediately re-opens.
        """
        if self._state </mark> CircuitState.HALF_OPEN:
            print("[CIRCUIT] Probe failed - re-opening circuit")
            self._trip()
            return
 
        if self._state == CircuitState.OPEN:
            return  # already open, nothing to do
 
        # Evaluate from CLOSED state
        snap = self._window.snapshot()
 
        # Gate 1: requestVolumeThreshold
        # Do not open on a tiny or unrepresentative sample
        if snap.total_calls < self._config.circuit_breaker_request_volume_threshold:
            print(f"[CIRCUIT] {snap.total_calls} calls in window "
                  f"(below minimum {self._config.circuit_breaker_request_volume_threshold})"
                  f" - staying CLOSED")
            return
 
        # Gate 2: errorThresholdPercentage
        if snap.failure_rate >= self._config.circuit_breaker_error_threshold_percentage:
            print(f"[CIRCUIT] Failure rate {snap.failure_rate:.1f}% "
                  f">= threshold {self._config.circuit_breaker_error_threshold_percentage}% "
                  f"- OPENING")
            self._trip()
 
    def _trip(self):
        with self._state_lock:
            self._state     = CircuitState.OPEN
            self._opened_at = time.time()
        print("[CIRCUIT] State -> OPEN")
 
    def _reset(self):
        with self._state_lock:
            self._state = CircuitState.CLOSED
            # INTENTIONAL: do NOT clear the rolling window here.
            # Old failure data ages out naturally as buckets expire.
            # Keeping it means the circuit re-opens quickly if recovery is partial.
        print("[CIRCUIT] State -> CLOSED (recovered)")
 
    def execute(self, call: Callable[[], T], fallback: T,
                timeout_seconds: float = 1.0) -> T:
        """
        Convenience wrapper: checks circuit, calls the function,
        records the outcome, and returns either the real result or the fallback.
        """
        if not self.allow_request():
            print("[CIRCUIT] Short-circuited - returning fallback")
            return fallback
 
        start = time.time()
        try:
            result = call()
            self.record_success()
            return result
        except Exception as e:
            elapsed = time.time() - start
            if elapsed >= timeout_seconds:
                self.record_timeout()
                print(f"[CIRCUIT] Timeout after {elapsed:.1f}s: {e}")
            else:
                self.record_failure()
                print(f"[CIRCUIT] Failure: {e}")
            return fallback
 
 
# ===========================================================================<mark class="obsidian-highlight">
# Demo: simulate a service going down and recovering
# </mark>===========================================================================
 
def demo():
    config = HystrixConfig(
        metrics_rolling_statistical_window_seconds=10,
        metrics_rolling_statistical_window_buckets=10,
        circuit_breaker_request_volume_threshold=5,   # lowered for demo
        circuit_breaker_error_threshold_percentage=50.0,
        circuit_breaker_sleep_window_seconds=3.0,     # lowered for demo
    )
    cb = HystrixCircuitBreaker(config)
 
    print("=" * 60)
    print("Phase 1: Healthy service (should stay CLOSED)")
    print("=" * 60)
    for _ in range(6):
        cb.execute(lambda: "OK", fallback="FALLBACK")
    snap = cb.get_metrics()
    print(f"State: {cb.state.value}  |  "
          f"Calls: {snap.total_calls}  |  "
          f"Failure rate: {snap.failure_rate:.1f}%\n")
 
    print("=" * 60)
    print("Phase 2: Service degrades (7 failures, 3 successes)")
    print("=" * 60)
    for i in range(10):
        if i < 7:
            cb.execute(lambda: (_ for _ in ()).throw(ConnectionError("refused")),
                       fallback="FALLBACK")
        else:
            cb.execute(lambda: "OK", fallback="FALLBACK")
    snap = cb.get_metrics()
    print(f"State: {cb.state.value}  |  "
          f"Calls: {snap.total_calls}  |  "
          f"Failure rate: {snap.failure_rate:.1f}%\n")
 
    print("=" * 60)
    print("Phase 3: Circuit OPEN - all calls short-circuited")
    print("=" * 60)
    for _ in range(5):
        result = cb.execute(lambda: "OK", fallback="FALLBACK")
        print(f"  Result: {result}")
    print()
 
    print("=" * 60)
    print("Phase 4: Sleep window expires - probe with HALF_OPEN")
    print("=" * 60)
    print("Sleeping 3.1 seconds for sleep window to expire...")
    time.sleep(3.1)
 
    print("Service has recovered - sending probe:")
    result = cb.execute(lambda: "RECOVERED", fallback="FALLBACK")
    print(f"Probe result: {result}")
    print(f"Final state: {cb.state.value}")
 
 
if __name__ == "__main__":
    demo()

// WRONG: not atomic
if (state != State.OPEN) {
    state = State.OPEN;
    openedAt = System.currentTimeMillis();
}
 
// CORRECT: CAS - only the first thread to swap wins
private final AtomicReference<State> stateRef = new AtomicReference<>(State.CLOSED);
 
// Only one thread will successfully compare-and-swap from CLOSED to OPEN
if (stateRef.compareAndSet(State.CLOSED, State.OPEN)) {
    openedAt = System.currentTimeMillis();
    // Only the winning thread reaches here
}