Repository: keon/algorithms
Pull request #222 (2018-04-12 23:52:12)

Separate test case for sort
PR for separating test case for sort


Patch:
diff --git a/README.md b/README.md
index 96fded2..8097c4d 100644
--- a/README.md
+++ b/README.md
@@ -1,6 +1,7 @@
 English | [简体中文](https://github.com/yunshuipiao/algorithms/blob/master/README_CN.md)
 
 [![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
+[![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
 
 Pythonic Data Structures and Algorithms
 =========================================
diff --git a/maths/extended_gcd.py b/maths/extended_gcd.py
index 69ecfa3..96c31ac 100644
--- a/maths/extended_gcd.py
+++ b/maths/extended_gcd.py
@@ -17,4 +17,4 @@ def extended_gcd(a,b):
         old_s, s = s, old_s - quotient * s
         old_t, t = t, old_t - quotient * t
     
-    return old_s, old_t, old_r
\ No newline at end of file
+    return old_s, old_t, old_r
diff --git a/maths/gcd.py b/maths/gcd.py
index 9792d8f..1f80fc9 100644
--- a/maths/gcd.py
+++ b/maths/gcd.py
@@ -2,10 +2,9 @@ def gcd(a, b):
     """Computes the greatest common divisor of integers a and b using
     Euclid's Algorithm.
     """
-    while True:
-        if b == 0:
-            return a
+    while b != 0:
         a, b = b, a % b
+    return a
 
 
 def lcm(a, b):
diff --git a/maths/generate_strobogrammtic.py b/maths/generate_strobogrammtic.py
index f5589ac..2311dcf 100644
--- a/maths/generate_strobogrammtic.py
+++ b/maths/generate_strobogrammtic.py
@@ -14,8 +14,7 @@ def gen_strobogrammatic(n):
     :type n: int
     :rtype: List[str]
     """
-    result = helper(n, n)
-    return result
+    return helper(n, n)
 
 
 def helper(n, length):
@@ -43,19 +42,21 @@ def strobogrammaticInRange(low, high):
     """
     res = []
     count = 0
-    for i in range(len(low), len(high)+1):
+    low_len = len(low)
+    high_len = len(high)
+    for i in range(low_len, high_len + 1):
         res.extend(helper2(i, i))
     for perm in res:
-        if len(perm) == len(low) and int(perm) < int(low):
+        if len(perm) == low_len and int(perm) < int(low):
             continue
-        elif len(perm) == len(high) and int(perm) > int(high):
+        elif len(perm) == high_len and int(perm) > int(high):
             continue
         else:
             count += 1
     return count
 
 
-def helper2(self, n, length):
+def helper2(n, length):
     if n == 0:
         return [""]
     if n == 1:
diff --git a/maths/next_perfect_square.py b/maths/next_perfect_square.py
index dc52ddc..7e6e6b9 100644
--- a/maths/next_perfect_square.py
+++ b/maths/next_perfect_square.py
@@ -13,6 +13,7 @@ def find_next_square(sq):
     
 # Another way:
 
-def find_next_square(sq):
+def find_next_square2(sq):
     x = sq**0.5    
     return -1 if x % 1 else (x+1)**2
+
diff --git a/maths/primes_sieve_of_eratosthenes.py b/maths/primes_sieve_of_eratosthenes.py
index 34289da..1677b25 100644
--- a/maths/primes_sieve_of_eratosthenes.py
+++ b/maths/primes_sieve_of_eratosthenes.py
@@ -31,7 +31,7 @@ def primes(x):
     primes = []                              # List of Primes
     if x >= 2:
         primes.append(2)                     # Add 2 by default
-    for i in range(0, sieve_size):
+    for i in range(sieve_size):
         if sieve[i] == 1:
             value_at_i = i*2 + 3
             primes.append(value_at_i)
diff --git a/maths/pythagoras.py b/maths/pythagoras.py
index 8effe13..d896260 100644
--- a/maths/pythagoras.py
+++ b/maths/pythagoras.py
@@ -13,4 +13,4 @@ def pythagoras(opposite,adjacent,hypotenuse):
         else:
             return "You already know the answer!"
     except:
-        print ("Error, check your input. You must know 2 of the 3 variables.")
+        raise ValueError("invalid argument were given.")
diff --git a/maths/rabin_miller.py b/maths/rabin_miller.py
index b06db5c..c8e2921 100644
--- a/maths/rabin_miller.py
+++ b/maths/rabin_miller.py
@@ -8,6 +8,12 @@ def pow2_factor(n):
         power += 1
     return power, n
 
+def pow_3(a, b, c):
+    """ 
+        helper function for a, b and c integers. 
+    """
+    return a**b % c
+
 """
 Rabin-Miller primality test
 returning False implies that n is guarenteed composite
@@ -15,6 +21,9 @@ returning True means that n is probably prime
 with a 4 ** -k chance of being wrong
 """
 def is_prime(n, k):
+    #precondition
+    assert n >= 5, "the to tested number must been >= 5"
+
     r, d = pow2_factor(n - 1)
     
     """
@@ -23,13 +32,13 @@ def is_prime(n, k):
     an invalid witness guarentees n is composite
     """
     def valid_witness(a):
-        x = pow(a, d, n)
+        x = pow(int(a), int(d), int(n))
         
         if x == 1 or x == n - 1:
             return False
         
         for _ in range(r - 1):
-            x = pow(x, 2, n)
+            x = pow(int(x), int(2), int(n))
             
             if x == 1:
                 return True
diff --git a/maths/rsa.py b/maths/rsa.py
index f3b0f68..5ec1ccc 100644
--- a/maths/rsa.py
+++ b/maths/rsa.py
@@ -30,18 +30,22 @@ from extended_gcd import * # extended_gcd
 generate a prime with k bits
 """
 def genprime(k):
+    random.seed()
     while True:
-        n = random.randrange(2 ** (k - 1),2 ** k)
+        n = random.randrange(int(2 ** (k - 1)),int(2 ** k))
         if is_prime(n,128):
             return n
 
+
 """
 calculate the inverse of a mod m
 that is, find b such that (a * b) % m == 1
 """
 def modinv(a, m):
-        x, y, g = extended_gcd(a,m)
-        return x % m
+        b = 1
+        while ((a*b) % m != 1):
+            b += 1
+        return b
 
 """
 the RSA key generating algorithm
@@ -68,13 +72,20 @@ def generate_key(k):
     l = (p - 1) * (q - 1) # calculate totient function
     d = modinv(e,l)
     
-    return n, e, d
+    return int(n), int(e), int(d)
+
+def encrypt(data, e, n):
+    return pow(int(data), int(e), int(n))
+
+def decrypt(data, d, n):
+    return pow(int(data), int(d), int(n))
+
+
+
+#sample usage:
+# n,e,d = generate_key(16)
+# data = 20
+# encrypted = pow(data,e,n)
+# decrypted = pow(encrypted,d,n)
+# assert decrypted == data
 
-"""
-sample usage:
-n,e,d = generate_key(1024)
-data = 1337
-encrypted = pow(data,e,n)
-decrypted = pow(encrypted,d,n)
-assert decrypted == data
-"""
diff --git a/sort/bubble_sort.py b/sort/bubble_sort.py
index 176217a..da9cebd 100644
--- a/sort/bubble_sort.py
+++ b/sort/bubble_sort.py
@@ -5,8 +5,6 @@ https://en.wikipedia.org/wiki/Bubble_sort
 Worst-case performance: O(N^2)
 
 """
-import unittest
-
 def bubble_sort(arr):
 
     def swap(i, j):
@@ -21,13 +19,3 @@ def bubble_sort(arr):
                 swap(i - 1, i)
                 swapped = True
     return arr
-
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_bubble_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         bubble_sort([1, 5, 65, 23, 57, 1232]))
-if __name__ == "__main__":
-    unittest.main()
diff --git a/sort/comb_sort.py b/sort/comb_sort.py
index 0b066ce..338771d 100644
--- a/sort/comb_sort.py
+++ b/sort/comb_sort.py
@@ -5,7 +5,6 @@ https://en.wikipedia.org/wiki/Comb_sort
 Worst-case performance: O(N^2)
 
 """
-import unittest
 from math import floor
 
 
@@ -33,13 +32,3 @@ def comb_sort(arr):
                 sorted = False
             i = i + 1
     return arr
-
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_comb_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         comb_sort([1, 5, 65, 23, 57, 1232]))
-if __name__ == "__main__":
-    unittest.main()
diff --git a/sort/counting_sort.py b/sort/counting_sort.py
index 6228e6f..9b11af3 100644
--- a/sort/counting_sort.py
+++ b/sort/counting_sort.py
@@ -1,4 +1,3 @@
-import unittest
 def counting_sort(arr):
 	"""
     Counting_sort
@@ -35,15 +34,3 @@ def counting_sort(arr):
 		temp_arr[arr[i]] = temp_arr[arr[i]]-1
 
 	return result_arr
-
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_counting_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         counting_sort([1, 5, 65, 23, 57, 1232]))
-        self.assertEqual([-1232, -65, -57, -23, -5, -1],
-                         counting_sort([-1, -5, -65, -23, -57, -1232]))
-if __name__ == "__main__":
-    unittest.main()
diff --git a/sort/heap_sort.py b/sort/heap_sort.py
index a069511..5cdc786 100644
--- a/sort/heap_sort.py
+++ b/sort/heap_sort.py
@@ -1,4 +1,3 @@
-import unittest
 def max_heap_sort(arr):
     """ Heap Sort that uses a max heap to sort an array in ascending order
         Complexity: O(n log(n))
@@ -76,16 +75,3 @@ def min_heapify(arr, start):
             # If no swap occured, no need to keep iterating
             else:
                 break
-
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_max_heap_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         max_heap_sort([1, 5, 65, 23, 57, 1232]))
-    def test_min_heap_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         min_heap_sort([1, 5, 65, 23, 57, 1232]))
-if __name__ == "__main__":
-    unittest.main()
diff --git a/sort/insertion_sort.py b/sort/insertion_sort.py
index 6f2430a..07a0a52 100644
--- a/sort/insertion_sort.py
+++ b/sort/insertion_sort.py
@@ -1,4 +1,3 @@
-import unittest
 def insertion_sort(arr):
     """ Insertion Sort
         Complexity: O(n^2)
@@ -12,16 +11,5 @@ def insertion_sort(arr):
             pos = pos-1
         # Break and do the final swap
         arr[pos] = cursor
-     
-    return arr
 
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_insertion_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         insertion_sort([1, 5, 65, 23, 57, 1232]))
-
-if __name__ == "__main__":
-    unittest.main()
+    return arr
diff --git a/sort/merge_sort.py b/sort/merge_sort.py
index 69c095c..e1b62b3 100644
--- a/sort/merge_sort.py
+++ b/sort/merge_sort.py
@@ -1,4 +1,3 @@
-import unittest
 def merge_sort(arr):
     """ Merge Sort
         Complexity: O(n log(n))
@@ -35,13 +34,3 @@ def merge(left, right):
 
    # Return result
     return arr
-
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_merge_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         merge_sort([1, 5, 65, 23, 57, 1232]))
-if __name__ == "__main__":
-    unittest.main()
diff --git a/sort/quick_sort.py b/sort/quick_sort.py
index 9d48b2f..bec8132 100644
--- a/sort/quick_sort.py
+++ b/sort/quick_sort.py
@@ -1,4 +1,3 @@
-import unittest
 def quick_sort(arr, first, last):
     """ Quicksort
         Complexity: best O(n) avg O(n log(n)), worst O(N^2)
@@ -17,14 +16,3 @@ def partition(arr, first, last):
             wall += 1
     arr[wall], arr[last] = arr[last], arr[wall]
     return wall
-
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_quick_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         quick_sort([1, 5, 65, 23, 57, 1232], 0, 5))
-
-if __name__ == "__main__":
-    unittest.main()
diff --git a/sort/selection_sort.py b/sort/selection_sort.py
index 18e1aa7..fed1c34 100644
--- a/sort/selection_sort.py
+++ b/sort/selection_sort.py
@@ -1,6 +1,3 @@
-import unittest
-
-
 def selection_sort(arr):
     """ Selection Sort
         Complexity: O(n^2)
@@ -14,16 +11,3 @@ def selection_sort(arr):
 
         arr[minimum], arr[i] = arr[i], arr[minimum]
     return arr
-
-
-class TestSuite(unittest.TestCase):
-    """
-        test suite for the function (above)
-    """
-    def test_selection_sort(self):
-        self.assertEqual([1, 5, 23, 57, 65, 1232],
-                         selection_sort([1, 5, 65, 23, 57, 1232]))
-
-        
-if __name__ == "__main__":
-    unittest.main()


Test patch:
diff --git a/maths/prime_test.py b/maths/prime_test.py
index 05a069f..ba67071 100644
--- a/maths/prime_test.py
+++ b/maths/prime_test.py
@@ -1,7 +1,6 @@
 """
 prime_test(n) returns a True if n is a prime number else it returns False
 """
-import unittest
 
 def prime_test(n):
     if n <= 1:
@@ -34,30 +33,4 @@ def prime_test2(n):
     # if input number is less than
     # or equal to 1, it is not prime
     else:
-        return False
-
-
-class TestSuite (unittest.TestCase):
-    def test_prime_test(self):
-        """
-            checks all prime numbers between 2 up to 100.
-            Between 2 up to 100 exists 25 prime numbers!
-        """
-        counter = 0
-        for i in range(2,101):
-            if prime_test(i):
-                counter += 1
-        self.assertEqual(25,counter)
-    def test_prime_test2(self):
-        """
-            checks all prime numbers between 2 up to 100.
-            Between 2 up to 100 exists 25 prime numbers!
-        """
-        counter = 0
-        for i in range(2,101):
-            if prime_test(i):
-                counter += 1
-        self.assertEqual(25,counter)
-        
-if __name__ == "__main__":
-    unittest.main()
\ No newline at end of file
+        return False
\ No newline at end of file
diff --git a/maths/test_maths.py b/maths/test_maths.py
new file mode 100644
index 0000000..ff6cda0
--- /dev/null
+++ b/maths/test_maths.py
@@ -0,0 +1,193 @@
+from base_conversion import int2base,base2int
+from extended_gcd import extended_gcd
+from gcd import gcd,lcm
+from generate_strobogrammtic import gen_strobogrammatic,strobogrammaticInRange
+from is_strobogrammatic import is_strobogrammatic,is_strobogrammatic2
+from next_perfect_square import find_next_square,find_next_square2
+from primes_sieve_of_eratosthenes import primes
+from prime_test import prime_test, prime_test2
+from pythagoras import pythagoras
+from rabin_miller import is_prime 
+from rsa import encrypt, decrypt, generate_key
+
+import unittest
+
+
+class TestBaseConversion(unittest.TestCase):
+    """
+    Test for the file base_conversion.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_int2base(self):
+        self.assertEqual("101",int2base(5,2))
+        self.assertEqual("0",int2base(0,2))
+        self.assertEqual("FF",int2base(255,16))
+    def test_base2int(self):
+        self.assertEqual(5,base2int("101",2))
+        self.assertEqual(0,base2int("0",2))
+        self.assertEqual(255,base2int("FF",16))
+
+
+class TestExtendedGcd(unittest.TestCase):
+    """[summary]
+    Test for the file extended_gcd.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_extended_gcd(self):
+        self.assertEqual((0,1,2),extended_gcd(8,2))
+        self.assertEqual((0,1,17),extended_gcd(13,17))
+
+
+class TestGcd(unittest.TestCase):
+    """[summary]
+    Test for the file gcd.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_gcd(self):
+        self.assertEqual(4,gcd(8,12))
+        self.assertEqual(1,gcd(13,17))
+    def test_lcm(self):
+        self.assertEqual(24,lcm(8,12))
+
+
+class TestGenerateStroboGrammatic(unittest.TestCase):
+    """[summary]
+    Test for the file generate_strobogrammatic.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_gen_strobomatic(self):
+        self.assertEqual(['88', '11', '96', '69'],gen_strobogrammatic(2))
+    def test_strobogrammaticInRange(self):
+        self.assertEqual(4,strobogrammaticInRange("10","100"))
+
+
+class TestIsStrobogrammatic(unittest.TestCase):
+    """[summary]
+    Test for the file is_strobogrammatic.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_is_strobogrammatic(self):
+        self.assertTrue(is_strobogrammatic("69"))
+        self.assertFalse(is_strobogrammatic("14"))
+    def test_is_strobogrammatic2(self):
+        self.assertTrue(is_strobogrammatic2("69"))
+        self.assertFalse(is_strobogrammatic2("14"))
+
+
+class TestNextPerfectSquare(unittest.TestCase):
+    """[summary]
+    Test for the file next_perfect_square.py
+    
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_find_next_square(self):
+        self.assertEqual(36,find_next_square(25))
+        self.assertEqual(1,find_next_square(0))
+    def test_find_next_square2(self):
+        self.assertEqual(36,find_next_square2(25))
+        self.assertEqual(1,find_next_square2(0))
+
+
+class TestPrimesSieveOfEratosthenes(unittest.TestCase):
+    """[summary]
+    Test for the file primes_sieve_of_eratosthenes.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_primes(self):
+        self.assertEqual([2, 3, 5, 7],primes(7))
+
+
+class TestPrimeTest (unittest.TestCase):
+    """[summary]
+    Test for the file prime_test.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_prime_test(self):
+        """
+            checks all prime numbers between 2 up to 100.
+            Between 2 up to 100 exists 25 prime numbers!
+        """
+        counter = 0
+        for i in range(2,101):
+            if prime_test(i):
+                counter += 1
+        self.assertEqual(25,counter)
+    def test_prime_test2(self):
+        """
+            checks all prime numbers between 2 up to 100.
+            Between 2 up to 100 exists 25 prime numbers!
+        """
+        counter = 0
+        for i in range(2,101):
+            if prime_test(i):
+                counter += 1
+        self.assertEqual(25,counter)
+        
+
+class TestPythagoras(unittest.TestCase):
+    """[summary]
+    Test for the file pythagoras.py 
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_pythagoras(self):
+        self.assertEqual("Hypotenuse = 3.605551275463989",pythagoras(3, 2, "?"))
+
+
+class TestRabinMiller(unittest.TestCase):
+    """[summary]
+    Test for the file rabin_miller.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_is_prime(self):
+        self.assertTrue(is_prime(7,2))
+        self.assertTrue(is_prime(13,11))
+        self.assertFalse(is_prime(6,2))
+
+
+class TestRSA(unittest.TestCase):
+    """[summary]
+    Test for the file rsa.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_encrypt_decrypt(self):
+        self.assertEqual(7,decrypt(encrypt(7, 23, 143), 47, 143))
+    def test_key_generator(self):
+        n, e, d = generate_key(8)
+        data = 2
+        en = encrypt(data, e, n)
+        dec = decrypt(en, d, n)
+        self.assertEqual(data,dec)
+
+if __name__ == "__main__":
+    unittest.main()
\ No newline at end of file
diff --git a/sort/test_sort.py b/sort/test_sort.py
new file mode 100644
index 0000000..085a12f
--- /dev/null
+++ b/sort/test_sort.py
@@ -0,0 +1,50 @@
+from bubble_sort import bubble_sort
+from comb_sort import comb_sort
+from counting_sort import counting_sort
+from heap_sort import max_heap_sort, min_heap_sort
+from insertion_sort import insertion_sort
+from merge_sort import merge_sort
+from quick_sort import quick_sort
+from selection_sort import selection_sort
+
+import unittest
+
+class TestSuite(unittest.TestCase):
+        def test_bubble_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             bubble_sort([1, 5, 65, 23, 57, 1232]))
+
+        def test_comb_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             comb_sort([1, 5, 65, 23, 57, 1232]))
+
+        def test_counting_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             counting_sort([1, 5, 65, 23, 57, 1232]))
+            self.assertEqual([-1232, -65, -57, -23, -5, -1],
+                             counting_sort([-1, -5, -65, -23, -57, -1232]))
+
+        def test_heap_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             max_heap_sort([1, 5, 65, 23, 57, 1232]))
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             min_heap_sort([1, 5, 65, 23, 57, 1232]))
+
+        def test_insertion_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             insertion_sort([1, 5, 65, 23, 57, 1232]))
+
+        def test_merge_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             merge_sort([1, 5, 65, 23, 57, 1232]))
+
+        def test_quick_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             quick_sort([1, 5, 65, 23, 57, 1232], 0, 5))
+
+        def test_selection_sort(self):
+            self.assertEqual([1, 5, 23, 57, 65, 1232],
+                             selection_sort([1, 5, 65, 23, 57, 1232]))
+
+if __name__ == "__main__":
+    unittest.main()