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.

12 files changed, 227 insertions, 126 deletions

diff --git a/algorithms/__init__.py b/algorithms/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/algorithms/__init__.py
diff --git a/algorithms/algorithm.py b/algorithms/algorithm.py
new file mode 100644
index 0000000..322a51f
--- /dev/null
+++ b/algorithms/algorithm.py
@@ -0,0 +1,25 @@
+# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com>
+# This file is licensed under the terms of the MIT License.
+# See LICENSE.txt for details.
+
+class Algorithm:
+    def __init__(self, codename, display_name, f):
+        self._codename = codename
+        self._display_name = display_name
+        self._f = f
+
+    def get_codename(self):
+        return self._codename
+
+    def get_display_name(self):
+        return self._display_name
+
+    def get_function(self):
+        return self._f
+
+    def __str__(self):
+        return self.get_display_name()
+
+class SortingAlgorithm(Algorithm):
+    def __init__(self, codename, display_name, f):
+        super().__init__(codename, display_name, f)
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),
+    ]
diff --git a/algorithms/registry.py b/algorithms/registry.py
new file mode 100644
index 0000000..8f0469d
--- /dev/null
+++ b/algorithms/registry.py
@@ -0,0 +1,17 @@
+# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com>
+# This file is licensed under the terms of the MIT License.
+# See LICENSE.txt for details.
+
+import algorithms.impl
+
+def refresh_algorithms():
+    algorithms.impl._refresh_algorithms()
+
+def get_codenames():
+    return algorithms.impl._ALL_ALGORITHMS.keys()
+
+def iter_algorithms():
+    return iter(algorithms.impl._ALL_ALGORITHMS.values())
+
+def get(codename):
+    return algorithms.impl._ALL_ALGORITHMS[codename]
diff --git a/plot.py b/plot.py
index 99452c4..2771467 100644
--- a/plot.py
+++ b/plot.py
@@ -12,23 +12,59 @@ class InputKind(Enum):
     def __str__(self):
         return self.value
 
-class SortingAlgorithm(Enum):
-    BUBBLE = 'bubble'
-    BUBBLE_OPTIMIZED = 'bubble_optimized'
-    HEAP = 'heap'
-    INSERTION = 'insertion'
-    MERGE = 'merge'
-    QUICK_FIRST = 'quick_first'
-    QUICK_SECOND = 'quick_second'
-    QUICK_MIDDLE = 'quick_middle'
-    QUICK_LAST = 'quick_last'
-    QUICK_RANDOM = 'quick_random'
-    SELECTION = 'selection'
+def get_timestamp():
+    return clock()
 
-    def __str__(self):
-        return self.value
+def init_clock():
+    get_timestamp()
+
+def gen_input(kind, n):
+    if kind is InputKind.SORTED:
+        return list(range(n))
+    elif kind is InputKind.REVERSED:
+        return sorted(range(n), reverse=True)
+    elif kind is InputKind.RANDOMIZED:
+        from random import sample
+        return sample(range(n), n)
+    else:
+        raise NotImplementedError(
+            'invalid initial input state \'{}\''.format(kind))
+
+def measure_running_time(algorithm, kind, xs_len, repetitions):
+    xs = gen_input(kind, xs_len)
+    xss = [list(xs) for _ in range(repetitions)]
+    algorithm = algorithm.get_function()
+    gc.disable()
+    started_at = get_timestamp()
+    for i in range(repetitions):
+        algorithm(xss[i])
+    finished_at = get_timestamp()
+    gc.enable()
+    return finished_at - started_at
+
+def _decorate_plot(algorithm, repetitions, kind, plt):
+    plt.grid()
+    plt.xlabel('Input length')
+    plt.ylabel('Running time (sec)')
+    plt.title('{}, {} repetition(s), {} input'.format(
+        algorithm.get_display_name(), repetitions, kind))
+
+def plot_algorithm(algorithm, repetitions, kind, min_len, max_len, output_path=None):
+    import matplotlib.pyplot as plt
+    _decorate_plot(algorithm, repetitions, kind, plt)
+    xs_lengths = range(min_len, max_len + 1)
+    running_time = []
+    for xs_len in xs_lengths:
+        running_time.append(measure_running_time(algorithm, kind, xs_len, repetitions))
+    plt.plot(xs_lengths, running_time)
+    if output_path is None:
+        plt.show()
+    else:
+        plt.savefig(output_path)
+
+if __name__ == '__main__':
+    import algorithms.registry
 
-def _get_context():
     def natural_number(s):
         n = int(s)
         if n < 0:
@@ -44,13 +80,12 @@ def _get_context():
             return InputKind(s)
         except ValueError:
             raise argparse.ArgumentError()
-    def sorting_algorithm(s):
-        try:
-            return SortingAlgorithm(s)
-        except ValueError:
-            raise argparse.ArgumentError()
+
     import argparse
     parser = argparse.ArgumentParser()
+    parser.add_argument('--algorithm', '-l', required=True,
+                        choices=algorithms.registry.get_codenames(),
+                        help='specify sorting algorithm to use')
     parser.add_argument('--repetitions', '-r',
                         type=positive_number, default=1,
                         help='set number of sorting repetitions')
@@ -58,113 +93,20 @@ def _get_context():
                         choices=tuple(x for x in InputKind),
                         type=input_kind, default=InputKind.RANDOMIZED,
                         help='choose initial input state')
-    parser.add_argument('--algorithm', '-l', required=True,
-                        choices=tuple(x for x in SortingAlgorithm),
-                        type=sorting_algorithm,
-                        help='select sorting algorithm to use')
     parser.add_argument('--min', '-a', type=natural_number,
-                        required=True, dest='min_input_length',
+                        required=True, dest='min_len',
                         help='set min input length')
     parser.add_argument('--max', '-b', type=natural_number,
-                        required=True, dest='max_input_length',
+                        required=True, dest='max_len',
                         help='set max input length')
-    parser.add_argument('--output', '-o', dest='plot_path',
+    parser.add_argument('--output', '-o', dest='output_path',
                         help='set plot output path')
     args = parser.parse_args()
-    if args.max_input_length < args.min_input_length:
+    if args.max_len < args.min_len:
         parser.error('max input length cannot be less than min input length')
-    return args
-
-def get_timestamp():
-    return clock()
-
-def init_clock():
-    get_timestamp()
 
-def gen_input(args, n):
-    if args.input is InputKind.SORTED:
-        return list(range(n))
-    elif args.input is InputKind.REVERSED:
-        return sorted(range(n), reverse=True)
-    elif args.input is InputKind.RANDOMIZED:
-        from random import sample
-        return sample(range(n), n)
-    else:
-        raise NotImplementedError(
-            'invalid initial input state \'{}\''.format(args.input))
-
-def measure_running_time(ctx, algorithm, input_length):
-    xs = gen_input(ctx, input_length)
-    assert algorithm(list(xs)) == sorted(xs)
-    input_copies = [list(xs) for i in range(ctx.repetitions)]
-    gc.disable()
-    starting_time = get_timestamp()
-    for i in range(ctx.repetitions):
-        algorithm(input_copies[i])
-    running_time = get_timestamp() - starting_time
-    gc.enable()
-    return running_time
-
-def _decorate_plot(ctx, plt):
-    plt.grid()
-    plt.xlabel('Input length')
-    plt.ylabel('Running time (sec)')
-    plt.title('{} sort, {} repetition(s), {} input'.format(
-        ctx.algorithm, ctx.repetitions, ctx.input))
-
-def plot_algorithm(ctx, algorithm):
-    import matplotlib.pyplot as plt
-    _decorate_plot(ctx, plt)
-    input_length = range(ctx.min_input_length,
-                         ctx.max_input_length + 1)
-    running_time = []
-    for n in input_length:
-        running_time.append(measure_running_time(ctx, algorithm, n))
-    plt.plot(input_length, running_time)
-    if ctx.plot_path is not None:
-        plt.savefig(ctx.plot_path)
-    else:
-        plt.show()
-
-def plot(ctx):
-    if ctx.algorithm is SortingAlgorithm.BUBBLE:
-        from bubble_sort import bubble_sort
-        plot_algorithm(ctx, bubble_sort)
-    elif ctx.algorithm is SortingAlgorithm.BUBBLE_OPTIMIZED:
-        from bubble_sort import bubble_sort_optimized
-        plot_algorithm(ctx, bubble_sort_optimized)
-    elif ctx.algorithm is SortingAlgorithm.HEAP:
-        from heapsort import heapsort
-        plot_algorithm(ctx, heapsort)
-    elif ctx.algorithm is SortingAlgorithm.INSERTION:
-        from insertion_sort import insertion_sort
-        plot_algorithm(ctx, insertion_sort)
-    elif ctx.algorithm is SortingAlgorithm.MERGE:
-        from merge_sort import merge_sort
-        plot_algorithm(ctx, merge_sort)
-    elif ctx.algorithm is SortingAlgorithm.QUICK_FIRST:
-        from quicksort import quicksort_first
-        plot_algorithm(ctx, quicksort_first)
-    elif ctx.algorithm is SortingAlgorithm.QUICK_SECOND:
-        from quicksort import quicksort_second
-        plot_algorithm(ctx, quicksort_second)
-    elif ctx.algorithm is SortingAlgorithm.QUICK_MIDDLE:
-        from quicksort import quicksort_middle
-        plot_algorithm(ctx, quicksort_middle)
-    elif ctx.algorithm is SortingAlgorithm.QUICK_LAST:
-        from quicksort import quicksort_last
-        plot_algorithm(ctx, quicksort_last)
-    elif ctx.algorithm is SortingAlgorithm.QUICK_RANDOM:
-        from quicksort import quicksort_random
-        plot_algorithm(ctx, quicksort_random)
-    elif ctx.algorithm is SortingAlgorithm.SELECTION:
-        from selection_sort import selection_sort
-        plot_algorithm(ctx, selection_sort)
-    else:
-        raise NotImplementedError(
-            'invalid sorting algorithm \'{}\''.format(ctx.algorithm))
-
-if __name__ == '__main__':
-    ctx = _get_context()
     init_clock()
-    plot(ctx)
+    plot_algorithm(algorithms.registry.get(args.algorithm),
+                   args.repetitions, args.input,
+                   args.min_len, args.max_len,
+                   args.output_path)
diff --git a/test.py b/test.py
new file mode 100644
index 0000000..b3d9dd3
--- /dev/null
+++ b/test.py
@@ -0,0 +1,53 @@
+# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com>
+# This file is licensed under the terms of the MIT License.
+# See LICENSE.txt for details.
+
+from enum import Enum
+
+class InputKind(Enum):
+    SORTED, RANDOMIZED, REVERSED = 'sorted', 'randomized', 'reversed'
+
+    def __str__(self):
+        return self.value
+
+def gen_input(kind, n):
+    if kind is InputKind.SORTED:
+        return list(range(n))
+    elif kind is InputKind.REVERSED:
+        return sorted(range(n), reverse=True)
+    elif kind is InputKind.RANDOMIZED:
+        from random import sample
+        return sample(range(n), n)
+    else:
+        raise NotImplementedError(
+            'invalid initial input state \'{}\''.format(kind))
+
+if __name__ == '__main__':
+    import algorithms.registry
+
+    def natural_number(s):
+        n = int(s)
+        if n < 0:
+            raise argparse.ArgumentTypeError('cannot be negative')
+        return n
+    def input_kind(s):
+        try:
+            return InputKind(s)
+        except ValueError:
+            raise argparse.ArgumentError()
+
+    import argparse
+    parser = argparse.ArgumentParser()
+    parser.add_argument('--algorithm', '-l', required=True,
+                        choices=algorithms.registry.get_codenames(),
+                        help='specify algorithm codename')
+    parser.add_argument('--input', '-i',
+                        choices=tuple(x for x in InputKind),
+                        type=input_kind, default=InputKind.RANDOMIZED,
+                        help='set initial input state')
+    parser.add_argument('--length', '-n',
+                        type=natural_number, default=100,
+                        help='set input length')
+    args = parser.parse_args()
+    xs = gen_input(args.input, args.length)
+    print(algorithms.registry.get(args.algorithm).get_function()(xs))