Repository: TheAlgorithms/Java
Pull request #5840 (2024-10-15 07:17:54)

feat: Add TokenBucket new algorithm with Junit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5840?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 66.03%. Comparing base [(`30504c1`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/30504c179ebc42d15c7b738435a87a3d8bc4053b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`fa418bf`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/fa418bf2c61f22787247f9909584813a76c617ba?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5840      +/-   ##
============================================
+ Coverage     65.99%   66.03%   +0.03%     
- Complexity     4395     4399       +4     
============================================
  Files           603      604       +1     
  Lines         16799    16815      +16     
  Branches       3226     3227       +1     
============================================
+ Hits          11086    11103      +17     
  Misses         5266     5266              
+ Partials        447      446       -1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5840?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 061cf93a..fa9c2653 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -201,6 +201,7 @@
               * [PriorityQueues](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/PriorityQueues.java)
               * [Queue](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/Queue.java)
               * [QueueByTwoStacks](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/QueueByTwoStacks.java)
+              * [TokenBucket](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/queues/TokenBucket.java)
             * stacks
               * [NodeStack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/stacks/NodeStack.java)
               * [ReverseStack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/stacks/ReverseStack.java)
@@ -865,6 +866,7 @@
               * [PriorityQueuesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/PriorityQueuesTest.java)
               * [QueueByTwoStacksTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/QueueByTwoStacksTest.java)
               * [QueueTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/QueueTest.java)
+              * [TokenBucketTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/queues/TokenBucketTest.java)
             * stacks
               * [NodeStackTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/stacks/NodeStackTest.java)
               * [StackArrayListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/stacks/StackArrayListTest.java)
diff --git a/src/main/java/com/thealgorithms/datastructures/queues/TokenBucket.java b/src/main/java/com/thealgorithms/datastructures/queues/TokenBucket.java
new file mode 100644
index 00000000..999c963f
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/queues/TokenBucket.java
@@ -0,0 +1,61 @@
+package com.thealgorithms.datastructures.queues;
+
+import java.util.concurrent.TimeUnit;
+
+/**
+ * TokenBucket implements a token bucket rate limiter algorithm.
+ * This class is used to control the rate of requests in a distributed system.
+ * It allows a certain number of requests (tokens) to be processed in a time frame,
+ * based on the defined refill rate.
+ *
+ * Applications: Computer networks, API rate limiting, distributed systems, etc.
+ *
+ * @author Hardvan
+ */
+public final class TokenBucket {
+    private final int maxTokens;
+    private final int refillRate; // tokens per second
+    private int tokens;
+    private long lastRefill; // Timestamp in nanoseconds
+
+    /**
+     * Constructs a TokenBucket instance.
+     *
+     * @param maxTokens  Maximum number of tokens the bucket can hold.
+     * @param refillRate The rate at which tokens are refilled (tokens per second).
+     */
+    public TokenBucket(int maxTokens, int refillRate) {
+        this.maxTokens = maxTokens;
+        this.refillRate = refillRate;
+        this.tokens = maxTokens;
+        this.lastRefill = System.nanoTime();
+    }
+
+    /**
+     * Attempts to allow a request based on the available tokens.
+     * If a token is available, it decrements the token count and allows the request.
+     * Otherwise, the request is denied.
+     *
+     * @return true if the request is allowed, false if the request is denied.
+     */
+    public synchronized boolean allowRequest() {
+        refillTokens();
+        if (tokens > 0) {
+            tokens--;
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * Refills the tokens based on the time elapsed since the last refill.
+     * The number of tokens to be added is calculated based on the elapsed time
+     * and the refill rate, ensuring the total does not exceed maxTokens.
+     */
+    private void refillTokens() {
+        long now = System.nanoTime();
+        long tokensToAdd = (now - lastRefill) / TimeUnit.SECONDS.toNanos(1) * refillRate;
+        tokens = Math.min(maxTokens, tokens + (int) tokensToAdd);
+        lastRefill = now;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/queues/TokenBucketTest.java b/src/test/java/com/thealgorithms/datastructures/queues/TokenBucketTest.java
new file mode 100644
index 00000000..959ea872
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/queues/TokenBucketTest.java
@@ -0,0 +1,90 @@
+package com.thealgorithms.datastructures.queues;
+
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import org.junit.jupiter.api.Test;
+
+public class TokenBucketTest {
+
+    @Test
+    public void testRateLimiter() throws InterruptedException {
+        TokenBucket bucket = new TokenBucket(5, 1);
+        for (int i = 0; i < 5; i++) {
+            assertTrue(bucket.allowRequest());
+        }
+        assertFalse(bucket.allowRequest());
+        Thread.sleep(1000);
+        assertTrue(bucket.allowRequest());
+    }
+
+    @Test
+    public void testRateLimiterWithExceedingRequests() throws InterruptedException {
+        TokenBucket bucket = new TokenBucket(3, 1);
+
+        for (int i = 0; i < 3; i++) {
+            assertTrue(bucket.allowRequest());
+        }
+        assertFalse(bucket.allowRequest());
+
+        Thread.sleep(1000);
+        assertTrue(bucket.allowRequest());
+        assertFalse(bucket.allowRequest());
+    }
+
+    @Test
+    public void testRateLimiterMultipleRefills() throws InterruptedException {
+        TokenBucket bucket = new TokenBucket(2, 1);
+
+        assertTrue(bucket.allowRequest());
+        assertTrue(bucket.allowRequest());
+        assertFalse(bucket.allowRequest());
+
+        Thread.sleep(1000);
+        assertTrue(bucket.allowRequest());
+
+        Thread.sleep(1000);
+        assertTrue(bucket.allowRequest());
+        assertFalse(bucket.allowRequest());
+    }
+
+    @Test
+    public void testRateLimiterEmptyBucket() {
+        TokenBucket bucket = new TokenBucket(0, 1);
+
+        assertFalse(bucket.allowRequest());
+    }
+
+    @Test
+    public void testRateLimiterWithHighRefillRate() throws InterruptedException {
+        TokenBucket bucket = new TokenBucket(5, 10);
+
+        for (int i = 0; i < 5; i++) {
+            assertTrue(bucket.allowRequest());
+        }
+
+        assertFalse(bucket.allowRequest());
+
+        Thread.sleep(1000);
+
+        for (int i = 0; i < 5; i++) {
+            assertTrue(bucket.allowRequest());
+        }
+    }
+
+    @Test
+    public void testRateLimiterWithSlowRequests() throws InterruptedException {
+        TokenBucket bucket = new TokenBucket(5, 1);
+
+        for (int i = 0; i < 5; i++) {
+            assertTrue(bucket.allowRequest());
+        }
+
+        Thread.sleep(1000);
+        assertTrue(bucket.allowRequest());
+
+        Thread.sleep(2000);
+        assertTrue(bucket.allowRequest());
+        assertTrue(bucket.allowRequest());
+    }
+}