+
+UBAHN, TRAM, BUS, NIGHTLINE, OTHER = range(5)
+LINE_TYPE_NAMES = ['U-Bahn', 'Strassenbahn', 'Bus', 'Nightline', 'Andere']
+
+def get_line_sort_key(name):
+ """Return a sort key for a line name
+
+ >>> get_line_sort_key('U6')
+ ('U', 6)
+
+ >>> get_line_sort_key('D')
+ ('D', 0)
+
+ >>> get_line_sort_key('59A')
+ ('A', 59)
+ """
+ txt = ''.join(x for x in name if not x.isdigit())
+ num = ''.join(x for x in name if x.isdigit()) or '0'
+
+ return (txt, int(num))
+
+def get_line_type(name):
+ """Get the type of line for the given name
+
+ >>> get_line_type('U1')
+ UBAHN
+ >>> get_line_type('59A')
+ BUS
+ """
+ if name.isdigit():
+ return TRAM
+ elif name.endswith('A') or name.endswith('B') and name[1].isdigit():
+ return BUS
+ elif name.startswith('U'):
+ return UBAHN
+ elif name.startswith('N'):
+ return NIGHTLINE
+ elif name in ('D', 'O', 'VRT', 'WLB'):
+ return TRAM
+
+ return OTHER
+
+def categorize_lines(lines):
+ """Return a categorized version of a list of line names
+
+ >>> categorize_lines(['U4', 'U3', '59A'])
+ [('U-Bahn', ['U3', 'U4']), ('Bus', ['59A'])]
+ """
+ categorized_lines = collections.defaultdict(list)
+
+ for line in sorted(lines):
+ line_type = get_line_type(line)
+ categorized_lines[line_type].append(line)
+
+ for lines in categorized_lines.values():
+ lines.sort(key=get_line_sort_key)
+
+ return [(LINE_TYPE_NAMES[key], categorized_lines[key])
+ for key in sorted(categorized_lines)]
+