Repository: agiresearch/AIOS (language: python)

Issue:
docs: Corrected gramatical error
I found some slight grammatical mistakes in the documentation and I fixed them.


Discussion / hints:

Fix patch:
diff --git a/CONTRIBUTE.md b/CONTRIBUTE.md
index 3486a593..daee6081 100644
--- a/CONTRIBUTE.md
+++ b/CONTRIBUTE.md
@@ -28,7 +28,7 @@ git checkout -b your-feature
 
 ### Make changes and testing
 
-You can develop new features and then you need to make sure everything works as expected. Run our provided tests and make sure the existing ones go well. You new tests are encouraged.
+You can develop new features and then you need to make sure everything works as expected. Run our provided tests and make sure the existing ones go well. Your new tests are encouraged.
 
 ### Run tests
 
@@ -63,8 +63,8 @@ git commit -m <type>: <subject>
 ### Create a Pull Request
 
 1. Visit your forked AIOS repository on GitHub and click the "Compare & pull request" button to initiate the process of submitting your changes to the original repository for review and potential merging.
-2. Choose the base branch and the compare branch (your feature branch).💡 Note that when you add new features, it is recommended to choose the (`dev`) branch and if you change does not affect original functions, you may consider choosing the (`main`) branch.
+2. Choose the base branch and the compare branch (your feature branch).💡 Note that when you add new features, it is recommended to choose the (`dev`) branch and if your change does not affect original functions, you may consider choosing the (`main`) branch.
 3. Write a title and describe your changes in the description. And it is recommended to select the label of the change to make it more clear.
 
 ## 4. Review and Approval
-Our maintainers, will have a review of that and might give some suggestions or ask for more details. After they approve, your commitment can be incorporated into AIOS!
+Our maintainers will have a review of that and might give some suggestions or ask for more details. After they approve, your commitment can be incorporated into AIOS!
diff --git a/README.md b/README.md
index c7287c0d..ff15f917 100644
--- a/README.md
+++ b/README.md
@@ -3,7 +3,7 @@
 <a href='https://arxiv.org/abs/2403.16971'><img src='https://img.shields.io/badge/Paper-PDF-red'></a>
 <a href='https://arxiv.org/abs/2312.03815'><img src='https://img.shields.io/badge/Paper-PDF-blue'></a>
 [![Code License](https://img.shields.io/badge/Code%20License-MIT-green.svg)](https://github.com/agiresearch/AIOS/blob/main/LICENSE)
-<a href='https://discord.gg/m9Nw9fPR'><img src='https://img.shields.io/badge/Community-Discord-8A2BE2'></a>
+<a href='https://discord.gg/B2HFxEgTJX'><img src='https://img.shields.io/badge/Community-Discord-8A2BE2'></a>
 
 AIOS, a Large Language Model (LLM) Agent operating system, embeds large language model into Operating Systems (OS) as the brain of the OS, enabling an operating system "with soul" -- an important step towards AGI. AIOS is designed to optimize resource allocation, facilitate context switch across agents, enable concurrent execution of agents, provide tool service for agents, maintain access control for agents, and provide a rich set of toolkits for LLM Agent developers.
 
@@ -17,7 +17,7 @@ AIOS, a Large Language Model (LLM) Agent operating system, embeds large language
 ## 📰 News
 - **[2024-04-14]** 🚀 AIOS currently supports generation interrupt (for open-sourced llms) and customized console loggers. Feel free to try!
 - **[2024-04-05]** 🛠️ AIOS codebase has been updated to add shell simulator, rapid API calls, and pre-commit test cases. Please see [CONTRIBUTE](https://github.com/agiresearch/AIOS/blob/main/CONTRIBUTE.md) for how to test your contributions and create pull requests.
-- **[2024-04-02]** 🌟 AIOS [Discord Community](https://discord.gg/m9Nw9fPR) is up. Welcome to join the community for discussions, brainstorming, development, or just random chats!
+- **[2024-04-02]** 🌟 AIOS [Discord Community](https://discord.gg/B2HFxEgTJX) is up. Welcome to join the community for discussions, brainstorming, development, or just random chats!
 - **[2024-03-25]** ✈️ Our paper [AIOS: LLM Agent Operating System](https://arxiv.org/abs/2403.16971) is released and AIOS repository is officially launched!
 - **[2023-12-06]** 📋 After several months of working, our perspective paper [LLM as OS, Agents as Apps: Envisioning AIOS, Agents and the AIOS-Agent Ecosystem](https://arxiv.org/abs/2312.03815) is officially released.
 
@@ -106,11 +106,11 @@ AIOS is dedicated to facilitating LLM agents' development and deployment in a sy
 For detailed information on how to contribute, see [CONTRIBUTE](https://github.com/agiresearch/AIOS/blob/main/CONTRIBUTE.md). If you would like to contribute to the codebase, [issues](https://github.com/agiresearch/AIOS/issues) or [pull requests](https://github.com/agiresearch/AIOS/pulls) are always welcome!
 
 ## 🌟 Discord Channel
-If you would like to join the community, ask questions, chat with fellows, learn about or propose new features, and participate in future developments, join our [Discord Community](https://discord.gg/m9Nw9fPR)!
+If you would like to join the community, ask questions, chat with fellows, learn about or propose new features, and participate in future developments, join our [Discord Community](https://discord.gg/B2HFxEgTJX)!
 
 ## 📪 Contact
 
-For issues related to AIOS development, we encourage submitting [issues](https://github.com/agiresearch/AIOS/issues), [pull requests](https://github.com/agiresearch/AIOS/pulls), or initiating discussions in the AIOS [Discord Channel](https://discord.gg/m9Nw9fPR). For other issues please feel free to contact Kai Mei (marknju2018@gmail.com) and Yongfeng Zhang (yongfeng@email.com).
+For issues related to AIOS development, we encourage submitting [issues](https://github.com/agiresearch/AIOS/issues), [pull requests](https://github.com/agiresearch/AIOS/pulls), or initiating discussions in the AIOS [Discord Channel](https://discord.gg/B2HFxEgTJX). For other issues please feel free to contact Kai Mei (marknju2018@gmail.com) and Yongfeng Zhang (yongfeng@email.com).
 
 ## 🌍 AIOS Contributors
 [![AIOS contributors](https://contrib.rocks/image?repo=agiresearch/AIOS&max=300)](https://github.com/agiresearch/AIOS/graphs/contributors)
diff --git a/src/memory/lru_k_replacer.py b/src/memory/lru_k_replacer.py
new file mode 100644
index 00000000..eea0544e
--- /dev/null
+++ b/src/memory/lru_k_replacer.py
@@ -0,0 +1,94 @@
+from collections import OrderedDict
+from typing import Optional, Dict
+
+
+class Block_Entry:
+    def __init__(self):
+        self.hit_count = 0
+        self.evictable = True
+
+
+class LRU_K_Replacer:
+    def __init__(self, capacity, k):
+        self.replacer_size = capacity
+        self.k = k
+        self.curr_size = 0
+        self.entries: Dict[int, Block_Entry] = {}
+        self.hit_list = OrderedDict()
+        self.cache_list = OrderedDict()
+
+    def evict(self) ->Optional[int]:
+        if self.curr_size == 0:
+            return None
+
+        for block_id in reversed(self.hit_list):
+            if self.entries[block_id].evictable:
+                self.hit_list.pop(block_id)
+                self.entries.pop(block_id)
+                self.curr_size -= 1
+                return block_id
+
+        for block_id in reversed(self.cache_list):
+            if self.entries[block_id].evictable:
+                self.cache_list.pop(block_id)
+                self.entries.pop(block_id)
+                self.curr_size -= 1
+                return block_id
+        return None
+
+    def update_access_history(self, block_id):
+        if block_id > self.replacer_size:
+            raise ValueError(f"Invalid block_id {block_id}")
+
+        if block_id not in self.entries:
+            self.entries[block_id] = Block_Entry()
+            self.curr_size += 1
+
+        self.entries[block_id].hit_count += 1
+        new_count = self.entries[block_id].hit_count
+
+        if new_count == 1:
+            self.hit_list[block_id] = None
+            self.hit_list.move_to_end(block_id, last=False)
+        else:
+            if new_count == self.k:
+                self.hit_list.pop(block_id)
+                self.cache_list[block_id] = None
+                self.cache_list.move_to_end(block_id, last=False)
+            elif new_count > self.k:
+                self.cache_list.move_to_end(block_id, last=False)
+
+    def set_evictable(self, block_id: int, set_evictable: bool) -> None:
+        if block_id > self.replacer_size:
+            raise ValueError(f"Invalid frame {block_id}")
+
+        if block_id not in self.entries:
+            return
+
+        if set_evictable and not self.entries[block_id].evictable:
+            self.curr_size += 1
+        elif self.entries[block_id].evictable and not set_evictable:
+            self.curr_size -= 1
+
+        self.entries[block_id].evictable = set_evictable
+
+    def remove(self, block_id: int) -> None:
+        if block_id not in self.entries:
+            return
+
+        if not self.entries[block_id].evictable:
+            raise ValueError(f"Invalid frame {block_id}")
+
+        if self.entries[block_id].hit_count < self.k:
+            self.hit_list.pop(block_id)
+        else:
+            self.cache_list.pop(block_id)
+
+        self.curr_size -= 1
+        self.entries.pop(block_id)
+
+    def size(self) -> int:
+        return self.curr_size
+
+
+


Test patch:
diff --git a/tests/test_lru_k_replacer.py b/tests/test_lru_k_replacer.py
new file mode 100644
index 00000000..6156ed24
--- /dev/null
+++ b/tests/test_lru_k_replacer.py
@@ -0,0 +1,66 @@
+from src.memory.lru_k_replacer import LRU_K_Replacer
+import pytest
+
+@pytest.fixture
+def replacer():
+    return LRU_K_Replacer(capacity=5, k=2)
+
+def test_update_access_history(replacer):
+    replacer.update_access_history(1)
+    assert replacer.size() == 1
+    assert replacer.entries[1].hit_count == 1
+
+    replacer.update_access_history(1)
+    assert replacer.size() == 1
+    assert replacer.entries[1].hit_count == 2
+
+    replacer.update_access_history(2)
+    assert replacer.size() == 2
+    assert replacer.entries[2].hit_count == 1
+
+def test_evict(replacer):
+    replacer.update_access_history(1)
+    replacer.update_access_history(2)
+    replacer.update_access_history(3)
+    replacer.update_access_history(1)
+    replacer.update_access_history(4)
+    replacer.update_access_history(5)
+
+    assert replacer.evict() == 2
+    assert replacer.size() == 4
+
+    assert replacer.evict() == 3
+    assert replacer.size() == 3
+
+def test_set_evictable(replacer):
+    replacer.update_access_history(1)
+    replacer.update_access_history(2)
+
+    replacer.set_evictable(1, False)
+    assert not replacer.entries[1].evictable
+    assert replacer.size() == 1
+
+    replacer.set_evictable(1, True)
+    assert replacer.entries[1].evictable
+    assert replacer.size() == 2
+
+def test_remove(replacer):
+    replacer.update_access_history(1)
+    replacer.update_access_history(2)
+    replacer.update_access_history(1)
+
+    replacer.remove(1)
+    assert 1 not in replacer.entries
+    assert replacer.size() == 1
+
+    with pytest.raises(ValueError):
+        replacer.remove(2)
+        replacer.set_evictable(2, False)
+        replacer.remove(2)
+
+def test_invalid_block_id(replacer):
+    with pytest.raises(ValueError):
+        replacer.update_access_history(6)
+
+    with pytest.raises(ValueError):
+        replacer.set_evictable(6, True)
\ No newline at end of file