rearrange source files

* Add a useful `algorithms` package to provide convinient access to the
implemented algorithms.
* This allows to e.g. dynamically list available algorithms, which
greatly simplifies a lot of things.

7 files changed, 69 insertions, 5 deletions

diff --git a/algorithms/impl/__init__.py b/algorithms/impl/__init__.py
new file mode 100644
index 0000000..29cd51c
--- /dev/null
+++ b/algorithms/impl/__init__.py
@@ -0,0 +1,29 @@
+# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com>
+# This file is licensed under the terms of the MIT License.
+# See LICENSE.txt for details.
+
+_ALL_ALGORITHMS = {}
+
+def _refresh_algorithms():
+    _ALGORITHMS_NAME = '_ALGORITHMS'
+    global _ALL_ALGORITHMS
+    _ALL_ALGORITHMS = {}
+
+    from algorithms.algorithm import Algorithm
+
+    from importlib import import_module
+    import os.path
+    from pkgutil import iter_modules
+
+    for _, module_name, is_pkg in iter_modules([os.path.dirname(__file__)]):
+        if is_pkg:
+            continue
+        module = import_module('.' + module_name, __package__)
+        if hasattr(module, _ALGORITHMS_NAME):
+            module_algorithms = getattr(module, _ALGORITHMS_NAME)
+            for algorithm in module_algorithms:
+                assert isinstance(algorithm, Algorithm)
+                assert algorithm.get_codename() not in _ALL_ALGORITHMS
+                _ALL_ALGORITHMS[algorithm.get_codename()] = algorithm
+
+_refresh_algorithms()
diff --git a/bubble_sort.py b/algorithms/impl/bubble_sort.py
index 8309201..2abfc43 100644
--- a/bubble_sort.py
+++ b/algorithms/impl/bubble_sort.py
@@ -31,3 +31,9 @@ if __name__ == '__main__':
     xs = list(map(int, sys.argv[1:]))
     print(bubble_sort(list(xs)))
     print(bubble_sort_optimized(list(xs)))
+else:
+    from algorithms.algorithm import SortingAlgorithm
+    _ALGORITHMS = [
+        SortingAlgorithm('bubble_sort', 'Bubble sort', bubble_sort),
+        SortingAlgorithm('bubble_sort_optimized', 'Bubble sort (optimized)', bubble_sort_optimized),
+    ]
diff --git a/heapsort.py b/algorithms/impl/heapsort.py
index 3f44e51..db3b6bd 100644
--- a/heapsort.py
+++ b/algorithms/impl/heapsort.py
@@ -5,11 +5,11 @@
 # Disclaimer: implemented in the most literate way.
 
 def heapsort(xs):
-    heapify(xs)
+    _heapify(xs)
     first, last = 0, len(xs) - 1
     for end in range(last, first, -1):
         xs[end], xs[first] = xs[first], xs[end]
-        siftdown(xs, first, end - 1)
+        _siftdown(xs, first, end - 1)
     return xs
 
 # In a heap stored in a zero-based array,
@@ -26,13 +26,13 @@ def _get_left_child(node):
 def _get_right_child(node):
     return node * 2 + 2
 
-def heapify(xs):
+def _heapify(xs):
     last = len(xs) - 1
     first_parent, last_parent = 0, _get_parent(last)
     for parent in range(last_parent, first_parent - 1, -1):
-        siftdown(xs, parent, last)
+        _siftdown(xs, parent, last)
 
-def siftdown(xs, start, end):
+def _siftdown(xs, start, end):
     root = start
     while True:
         # We swap if there is at least one child
@@ -52,3 +52,8 @@ def siftdown(xs, start, end):
 if __name__ == '__main__':
     import sys
     print(heapsort(list(map(int, sys.argv[1:]))))
+else:
+    from algorithms.algorithm import SortingAlgorithm
+    _ALGORITHMS = [
+        SortingAlgorithm('heapsort', 'Heapsort', heapsort),
+    ]
diff --git a/insertion_sort.py b/algorithms/impl/insertion_sort.py
index 9e0912d..f671712 100644
--- a/insertion_sort.py
+++ b/algorithms/impl/insertion_sort.py
@@ -13,3 +13,8 @@ def insertion_sort(xs):
 if __name__ == '__main__':
     import sys
     print(insertion_sort(list(map(int, sys.argv[1:]))))
+else:
+    from algorithms.algorithm import SortingAlgorithm
+    _ALGORITHMS = [
+        SortingAlgorithm('insertion_sort', 'Insertion sort', insertion_sort),
+    ]
diff --git a/merge_sort.py b/algorithms/impl/merge_sort.py
index 6d5403d..9fa96ec 100644
--- a/merge_sort.py
+++ b/algorithms/impl/merge_sort.py
@@ -27,3 +27,8 @@ def merge_sort(xs):
 if __name__ == '__main__':
     import sys
     print(merge_sort(list(map(int, sys.argv[1:]))))
+else:
+    from algorithms.algorithm import SortingAlgorithm
+    _ALGORITHMS = [
+        SortingAlgorithm('merge_sort', 'Merge sort', merge_sort),
+    ]
diff --git a/quicksort.py b/algorithms/impl/quicksort.py
index b8ecc18..32100b0 100644
--- a/quicksort.py
+++ b/algorithms/impl/quicksort.py
@@ -63,3 +63,12 @@ if __name__ == '__main__':
     print(quicksort_middle(list(xs)))
     print(quicksort_last(list(xs)))
     print(quicksort_random(list(xs)))
+else:
+    from algorithms.algorithm import SortingAlgorithm
+    _ALGORITHMS = [
+        SortingAlgorithm('quicksort_first', 'Quicksort (first element as pivot)', quicksort_first),
+        SortingAlgorithm('quicksort_second', 'Quicksort (second element as pivot)', quicksort_second),
+        SortingAlgorithm('quicksort_middle', 'Quicksort (middle element as pivot)', quicksort_middle),
+        SortingAlgorithm('quicksort_last', 'Quicksort (last element as pivot)', quicksort_last),
+        SortingAlgorithm('quicksort_random', 'Quicksort (random element as pivot)', quicksort_random),
+    ]
diff --git a/selection_sort.py b/algorithms/impl/selection_sort.py
index c466bea..d48c058 100644
--- a/selection_sort.py
+++ b/algorithms/impl/selection_sort.py
@@ -15,3 +15,8 @@ def selection_sort(xs):
 if __name__ == '__main__':
     import sys
     print(selection_sort(list(map(int, sys.argv[1:]))))
+else:
+    from algorithms.algorithm import SortingAlgorithm
+    _ALGORITHMS = [
+        SortingAlgorithm('selection', 'Selection sort', selection_sort),
+    ]