Knot.__make_ends()   A
last analyzed

Complexity

Conditions 3

Size

Total Lines 6

Duplication

Lines 0
Ratio 0 %

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 3
c 1
b 0
f 0
dl 0
loc 6
rs 9.4285
1
# coding: utf8
2
3
# Copyright 2013-2015 Vincent Jacques <[email protected]>
4
5
import collections
6
import fractions
7
import math
8
9
10
End = collections.namedtuple("End", "theta, altitude")
11
Segment = collections.namedtuple("Segment", "begin, end")
12
Bridge = collections.namedtuple("Bridge", "before, after, tunnel")
13
Tunnel = collections.namedtuple("Tunnel", "k, before, after")
14
String = collections.namedtuple("String", "k, segments, bridges")
15
16
17
class Knot(object):
18
    def __init__(self, p, q):
19
        self.p = p
20
        self.q = q
21
        self.d = fractions.gcd(p, q)
22
        self._ks = range(self.d)
23
        self.p_prime = p // self.d
24
        self.q_prime = q // self.d
25
        self.__max_theta = 2 * self.p * self.q_prime
26
        if self.q == 1:
27
            self.strings = [String(0, [Segment(End(0, 0), End(2 * self.p, 0))], [])]
28
        else:
29
            self.strings = list(self.__make_strings())
30
31
    def __make_strings(self):
32
        intersections = list(self.__find_intersections())
33
        tidied_intersections = self.__tidy_intersections(intersections)
34
        ends = list(self.__make_ends(tidied_intersections))
35
        segments = list(self.__make_segments(ends))
36
        bridges = list(self.__make_bridges(tidied_intersections, segments))
37
        for k in self._ks:
38
            yield String(k, segments[k], bridges[k])
39
40
    def __find_intersections(self):
41
        found = 0
42
        for m in range(self.d):
43
            for n in range(m, self.d):
44
                for theta_1, theta_2 in self.__find_strings_intersections(m, n):
45
                    assert 0 <= theta_1 < self.__max_theta
46
                    assert 0 <= theta_2 < self.__max_theta
47
                    assert m != n or theta_1 < theta_2
48
                    found += 1
49
                    yield m, n, theta_1, theta_2
50
        assert found == self.p * (self.q - 1)
51
52
    def __find_strings_intersections(self, m, n):
53
        if m == n:
54
            min_a = 1
55
        else:
56
            min_a = -self.q_prime + 1
57
        max_a = self.q_prime
58
        for a in range(min_a, max_a):
59
            min_b = int(math.ceil(float(abs(a) * self.p - m - n) / self.q))
60
            max_b = 2 * self.p_prime - int(math.floor(float(abs(a) * self.p + m + n) / self.q))
61
            for b in range(min_b, max_b):
62
                theta_1 = b * self.q - a * self.p + m + n
63
                theta_2 = b * self.q + a * self.p + m + n
64
                yield theta_1, theta_2
65
66
    def __tidy_intersections(self, intersections):
67
        tidied_intersections = [{} for k in self._ks]
68
        for m, n, theta_1, theta_2 in intersections:
69
            tidied_intersections[m][theta_1] = (n, theta_2)
70
            tidied_intersections[n][theta_2] = (m, theta_1)
71
        return tidied_intersections
72
73
    def __make_ends(self, tidied_intersections):
74
        ref_ends = list(self.__make_ref_ends(tidied_intersections))
75
        yield ref_ends
76
        ref_ends = {e.theta: e for e in ref_ends}
77
        for k in range(1, self.d):
78
            yield list(self.__make_string_ends(ref_ends, tidied_intersections, k))
79
80
    def __make_ref_ends(self, tidied_intersections):
81
        for (i, theta) in enumerate(sorted(tidied_intersections[0].iterkeys())):
82
            yield End(theta, (-1)**i)
83
84
    def __make_string_ends(self, ref_ends, tidied_intersections, k):
85
        for theta in tidied_intersections[k].iterkeys():
86
            altitude = ref_ends[(theta - 2 * k) % (self.__max_theta)].altitude
87
            yield End(theta, altitude)
88
89
    def __make_segments(self, ends):
90
        for string_ends in ends:
91
            yield list(self.__make_string_segments(string_ends))
92
93
    def __make_string_segments(self, string_ends):
94
        for begin, end in zip(string_ends, string_ends[1:]):
95
            yield Segment(begin, end)
96
        yield Segment(
97
            string_ends[-1],
98
            End(string_ends[0].theta + self.__max_theta, string_ends[0].altitude)
99
        )
100
101
    def __make_bridges(self, tidied_intersections, segments):
102
        segs_by_begin = [{s.begin.theta: s for s in string_segments} for string_segments in segments]
103
        segs_by_end = [{s.end.theta: s for s in string_segments} for string_segments in segments]
104
        for k, string_segments in enumerate(segments):
105
            yield list(self.__make_string_bridges(tidied_intersections, segs_by_begin, segs_by_end, k, string_segments))
106
107
    def __make_string_bridges(self, tidied_intersections, segs_by_begin, segs_by_end, k, string_segments):
108
        assert len(string_segments) % 2 == 0
109
        it = iter(string_segments)  # Inspired by grouper in https://docs.python.org/2/library/itertools.html#recipes
110
        if string_segments[0].end.altitude != 1:
111
            after = it.next()
112
            before = self.__rotate_segment(string_segments[-1])
113
            yield self.__make_bridge(tidied_intersections, segs_by_begin, segs_by_end, k, before, after)
114
        for before, after in zip(it, it):
115
            yield self.__make_bridge(tidied_intersections, segs_by_begin, segs_by_end, k, before, after)
116
117
    def __rotate_segment(self, segment):
118
        return Segment(
119
            End(segment.begin.theta - self.__max_theta, segment.begin.altitude),
120
            End(segment.end.theta - self.__max_theta, segment.end.altitude),
121
        )
122
123
    def __make_bridge(self, tidied_intersections, segs_by_begin, segs_by_end, k, before, after):
124
        assert before.end.theta == after.begin.theta
125
        assert before.end.altitude == after.begin.altitude == 1
126
        n, theta_2 = tidied_intersections[k][before.end.theta]
127
        tunnel = self.__make_tunnel(segs_by_begin, segs_by_end, n, theta_2)
128
        bridge = Bridge(before, after, tunnel)
129
        if self.p < 3 or self.q < 3:
130
            return self.__shorten_bridge(bridge)
131
        else:
132
            return bridge
133
134
    def __make_tunnel(self, segs_by_begin, segs_by_end, n, theta_2):
135
        if theta_2 in segs_by_end[n]:
136
            bef_tunnel = segs_by_end[n][theta_2]
137
        else:
138
            bef_tunnel = self.__rotate_segment(segs_by_end[n][theta_2 + self.__max_theta])
139
        aft_tunnel = segs_by_begin[n][theta_2]
140
        return Tunnel(n, bef_tunnel, aft_tunnel)
141
142
    def __shorten_bridge(self, bridge):
143
        return Bridge(
144
            Segment(End((bridge.before.begin.theta + bridge.before.end.theta) / 2, 0), bridge.before.end),
145
            Segment(bridge.after.begin, End((bridge.after.begin.theta + bridge.after.end.theta) / 2, 0)),
146
            Tunnel(
147
                bridge.tunnel.k,
148
                Segment(
149
                    End((bridge.tunnel.before.begin.theta + bridge.tunnel.before.end.theta) / 2, 0),
150
                    bridge.tunnel.before.end
151
                ),
152
                Segment(
153
                    bridge.tunnel.after.begin,
154
                    End((bridge.tunnel.after.begin.theta + bridge.tunnel.after.end.theta) / 2, 0)
155
                ),
156
            ),
157
        )
158