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.

1 files changed, 63 insertions, 121 deletions

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)