Repository: codezonediitj/pydatastructs (language: python)

Issue:
Add `multiset` to `pydatastructs.miscellaneous_data_structures`
#### Description of the problem

https://github.com/codezonediitj/pydatastructs/issues/390#issuecomment-986180523

> We do have SelfBalancingBinaryTree we just need to put pop method (which is basically show top and delete). Apply pop enough time and we have tree sort. My point being that we don't need to reinvent anything.

#### References



Discussion / hints:
I would like to work kn this issue kindly assign it to  me .I am gssoc'21 participant
Can we create a `multiset` using this? I would prefer having the implementation which is available in CPP where Insert, deletion, and count works in O(logN)?
@Smit-create Can I do it in Python?
Please assign this issue to me under Gssoc'21.
> Can we create a `multiset` using this? I would prefer having the implementation which is available in CPP where Insert, deletion, and count works in O(logN)?

We do have `SelfBalancingBinaryTree` we just need to put pop method (which is basically show top and delete). Apply pop enough time and we have tree sort. My point being that we don't need to reinvent anything.
We already have plenty of sorting algorithms. Having one more makes sense? Though I like the idea of `multiset`, it is a data structure worth adding.
Kindly assign this issue to me under Gssoc'22


@Smriti123Shukla You can go ahead with adding `multiset`. We don't assign issues. Please read, https://github.com/codezonediitj/pydatastructs/wiki/Issue-Policy

Fix patch:
diff --git a/pydatastructs/miscellaneous_data_structures/__init__.py b/pydatastructs/miscellaneous_data_structures/__init__.py
index 16e23e366..60754c413 100644
--- a/pydatastructs/miscellaneous_data_structures/__init__.py
+++ b/pydatastructs/miscellaneous_data_structures/__init__.py
@@ -45,3 +45,8 @@
     RangeQueryDynamic
 )
 __all__.extend(algorithms.__all__)
+
+from .multiset import (
+    Multiset
+)
+__all__.extend(multiset.__all__)
diff --git a/pydatastructs/miscellaneous_data_structures/multiset.py b/pydatastructs/miscellaneous_data_structures/multiset.py
new file mode 100644
index 000000000..397978224
--- /dev/null
+++ b/pydatastructs/miscellaneous_data_structures/multiset.py
@@ -0,0 +1,42 @@
+__all__ = [
+    'Multiset'
+]
+
+
+class Multiset:
+    def __init__(self, *args):
+        # TODO: Implement dict in pydatastructs
+        self.counter = dict()
+        from pydatastructs.trees import RedBlackTree
+        self.tree = RedBlackTree()
+        self._n = 0
+        for arg in args:
+            self.add(arg)
+
+    def add(self, element):
+        self.counter[element]  = self.counter.get(element, 0) + 1
+        self._n += 1
+        if self.counter[element] == 1:
+            self.tree.insert(element)
+
+    def remove(self, element):
+        if self.counter[element] == 1:
+            self.tree.delete(element)
+        if self.counter.get(element, 0) > 0:
+            self._n -= 1
+            self.counter[element] -= 1
+
+    def lower_bound(self, element):
+        return self.tree.lower_bound(element)
+
+    def upper_bound(self, element):
+        return self.tree.upper_bound(element)
+
+    def __contains__(self, element):
+        return self.counter.get(element, 0) > 0
+
+    def __len__(self):
+        return self._n
+
+    def count(self, element):
+        return self.counter.get(element, 0)


Test patch:
diff --git a/pydatastructs/miscellaneous_data_structures/tests/test_multiset.py b/pydatastructs/miscellaneous_data_structures/tests/test_multiset.py
new file mode 100644
index 000000000..fb412704a
--- /dev/null
+++ b/pydatastructs/miscellaneous_data_structures/tests/test_multiset.py
@@ -0,0 +1,39 @@
+from pydatastructs.miscellaneous_data_structures import Multiset
+
+def test_Multiset():
+
+    ms = Multiset()
+    ms.add(5)
+    ms.add(5)
+    ms.add(3)
+    ms.add(7)
+    assert len(ms) == 4
+    assert 5 in ms
+    assert ms.count(5) == 2
+    assert ms.count(3) == 1
+    assert ms.count(-3) == 0
+    assert not 4 in ms
+    ms.remove(5)
+    assert 5 in ms
+    assert ms.lower_bound(5) == 5
+    assert ms.upper_bound(5) == 7
+
+    ms = Multiset(5, 3, 7, 2)
+
+    assert len(ms) == 4
+    assert 5 in ms
+    assert ms.count(7) == 1
+    assert not 4 in ms
+    assert ms.lower_bound(3) == 3
+    assert ms.upper_bound(3) == 5
+    assert ms.upper_bound(7) is None
+
+    ms.remove(5)
+
+    assert len(ms) == 3
+    assert not 5 in ms
+
+    ms.add(4)
+
+    assert 4 in ms
+    assert len(ms) == 4