500 lines
15 KiB
Python
500 lines
15 KiB
Python
import unittest
|
|
import math
|
|
|
|
LEFT = 0
|
|
RIGHT = 1
|
|
|
|
class Numbers:
|
|
def __init__(self, content:list):
|
|
self._content = content
|
|
|
|
def __repr__(self):
|
|
return str(self._content)
|
|
|
|
def isEmpty(self):
|
|
return len(self._content) == 0
|
|
|
|
def getNumTuples(self):
|
|
if self.isEmpty():
|
|
return 0
|
|
lastItem = self._content[-1]
|
|
numTuples = 1
|
|
for e in reversed(self._content):
|
|
if e < lastItem:
|
|
numTuples += 1
|
|
lastItem = e
|
|
return numTuples
|
|
|
|
def getTuples(self, toGet:int)-> list:
|
|
res = list()
|
|
if self.isEmpty():
|
|
return res
|
|
lastItem = self._content[-1]
|
|
numTuples = 1
|
|
for e in reversed(self._content):
|
|
if e < lastItem:
|
|
numTuples += 1
|
|
lastItem = e
|
|
if numTuples <= toGet:
|
|
res.insert(0, e)
|
|
else:
|
|
break
|
|
return res
|
|
|
|
class Roundabout:
|
|
def __init__(self, rotation = LEFT):
|
|
self.coatHangers = list()
|
|
self.rotation = rotation
|
|
|
|
def addList(self, items):
|
|
for item in items:
|
|
self.add(item)
|
|
|
|
def add(self, item):
|
|
if self.rotation == LEFT: #linksdrehend
|
|
self.coatHangers.insert(0, item)
|
|
else:
|
|
self.coatHangers.append(item)
|
|
|
|
def remove(self):
|
|
if self.rotation == LEFT: #linksdrehend
|
|
return self.coatHangers.pop()
|
|
else:
|
|
return self.coatHangers.pop(0)
|
|
|
|
def content(self):
|
|
return self.coatHangers
|
|
|
|
def hasItems(self):
|
|
if len(self.coatHangers) == 0:
|
|
return False
|
|
return True
|
|
|
|
def itemOnSeparator(self):
|
|
if len(self.coatHangers) == 0:
|
|
return None
|
|
if self.rotation == LEFT: #linksdrehend
|
|
return self.coatHangers[-1]
|
|
else:
|
|
return self.coatHangers[0]
|
|
|
|
def getSmallestItem(self):
|
|
return min(self.coatHangers)
|
|
|
|
def isEmpty(self):
|
|
return len(self.coatHangers) == 0
|
|
|
|
def clear(self):
|
|
self.coatHangers.clear()
|
|
|
|
def clear(self):
|
|
self.coatHangers.clear()
|
|
|
|
def getNumTuples(self) -> int:
|
|
content = list(self.content())
|
|
if self.rotation == RIGHT: #rechtssdrehend
|
|
content.reverse()
|
|
n = Numbers(content)
|
|
return n.getNumTuples()
|
|
|
|
def getTuples(self, numToGet:int) -> list:
|
|
content = list(self.content())
|
|
if self.rotation == RIGHT: #rechtsdrehend
|
|
content.reverse()
|
|
n = Numbers(content)
|
|
return n.getTuples(numToGet)
|
|
|
|
class Switch:
|
|
def __init__(self, left_roundabout: Roundabout, right_roundabout: Roundabout):
|
|
self.lR = left_roundabout
|
|
self.rR = right_roundabout
|
|
self.set_to_left()
|
|
|
|
def switch(self):
|
|
if self.is_left():
|
|
self.set_to_right()
|
|
else:
|
|
self.set_to_left()
|
|
|
|
def set_to_left(self):
|
|
self.status = LEFT
|
|
return self.status
|
|
|
|
def set_to_right(self):
|
|
self.status = RIGHT
|
|
return self.status
|
|
|
|
def is_left(self):
|
|
if self.status == LEFT:
|
|
return True
|
|
return False
|
|
|
|
def is_right(self):
|
|
if self.status == RIGHT:
|
|
return True
|
|
return False
|
|
|
|
def assign(self, item):
|
|
if self.is_left():
|
|
self.lR.add(item)
|
|
else:
|
|
self.rR.add(item)
|
|
|
|
class RoundaboutPair:
|
|
def __init__(self, left_roundabout: Roundabout, right_roundabout: Roundabout, switch: Switch):
|
|
self.lR = left_roundabout
|
|
self.rR = right_roundabout
|
|
self.sw = switch
|
|
|
|
def sortStepPickSort(self):
|
|
"""Picksort Verfahren. Hole immer das kleinste aus dem Roundabout raus
|
|
"""
|
|
if self.lR.getSmallestItem() == self.lR.itemOnSeparator():
|
|
item = self.lR.remove()
|
|
self.sw.set_to_right() # weiche auf ausschleusen
|
|
self.sw.assign(item) # item auf die Weiche setzen
|
|
self.sw.set_to_left() # weiche wieder zurück setzen
|
|
else:
|
|
item = self.lR.remove()
|
|
self.sw.assign(item)
|
|
|
|
def initTupleSort(self):
|
|
if self.lR.isEmpty():
|
|
return False
|
|
|
|
nleft = Numbers(self.lR.content()).getNumTuples()
|
|
nright = Numbers(self.rR.content()).getNumTuples()
|
|
nTarget = math.ceil((nleft + nright)/2)
|
|
|
|
if (nleft+nright) % 2 == 0: # even number
|
|
addOn = 0
|
|
else:
|
|
addOn = 1
|
|
# bei ungerader Anzahl von Bügelträgern sollte der linke immer die Mehrheit besitzen
|
|
# also z.B. 5 - 4
|
|
# bei einem geradzahligen Tupel, sollten nach der Initialisierung auf beiden Seiten diesselbe Anzahl von Tupel stehen
|
|
|
|
|
|
while (nleft != nright+addOn):
|
|
|
|
if nleft > nright:
|
|
before = self.doPassageLeftItem()
|
|
else:
|
|
before = self.doPassageRightItem()
|
|
nleft = Numbers(self.lR.content()).getNumTuples()
|
|
nright = Numbers(self.rR.content()).getNumTuples()
|
|
|
|
return True
|
|
|
|
|
|
def sortStepTupleSort(self):
|
|
before = 0
|
|
while True:
|
|
rightItem = self.rR.itemOnSeparator()
|
|
leftItem = self.lR.itemOnSeparator()
|
|
|
|
# wenn beide leer sind macht der Methode keinen Sinn
|
|
if rightItem == None and leftItem == None:
|
|
return
|
|
# wenn der linke Kreisel leer ist, sind wir fertig
|
|
if leftItem == None:
|
|
break
|
|
if rightItem is None:
|
|
rightItem = 0
|
|
# raus zum nächsten Schritt. Ende dieses Tupels erreicht.
|
|
if max(leftItem, rightItem) < before:
|
|
break
|
|
|
|
if leftItem < rightItem:
|
|
if leftItem > before:
|
|
before = self.doPassageLeftItem()
|
|
if rightItem > before:
|
|
before = self.doPassageRightItem()
|
|
else:
|
|
if rightItem > before:
|
|
before = self.doPassageRightItem()
|
|
if leftItem > before:
|
|
before = self.doPassageLeftItem()
|
|
|
|
# Weiche auf die andere Seite stellen
|
|
self.sw.switch()
|
|
return
|
|
|
|
def doPassageLeftItem(self):
|
|
"""greift sich das Element vom linken Roundabout und fährt durch die Weiche
|
|
"""
|
|
leftItem = self.lR.itemOnSeparator()
|
|
if leftItem == None:
|
|
return
|
|
|
|
leftItem = self.lR.remove()
|
|
self.sw.assign(leftItem)
|
|
return leftItem
|
|
|
|
def doPassageRightItem(self):
|
|
"""greift sich das Element vom rechten Roundabout und fährt durch die Weiche
|
|
"""
|
|
rightItem = self.rR.itemOnSeparator()
|
|
if rightItem == None:
|
|
return
|
|
|
|
rightItem = self.rR.remove()
|
|
self.sw.assign(rightItem)
|
|
return rightItem
|
|
|
|
def runPickSort(self):
|
|
# number = 0
|
|
while not self.lR.isEmpty():
|
|
self.sortStepPickSort()
|
|
# number += 1
|
|
# if number > 300:
|
|
# break
|
|
|
|
def runTupleSort(self):
|
|
number = 0
|
|
self.sw.set_to_right()
|
|
runSorting = True
|
|
while runSorting:
|
|
self.sortStepTupleSort()
|
|
if self.lR.isEmpty():
|
|
break
|
|
|
|
def show(self):
|
|
return (self.lR.content(), self.rR.content())
|
|
|
|
class TestObjectMethods(unittest.TestCase):
|
|
|
|
def test_order(self):
|
|
# tupel werden von rechts nach links bestimmt.
|
|
# Jede Zahl, die kleiner als ihr Vorgänger ist, ist ein neuer Start eines Tupels
|
|
n1 = Numbers([1, 2, 3, 4, 5, 6])
|
|
self.assertEqual(repr(n1), "[1, 2, 3, 4, 5, 6]")
|
|
self.assertEqual(n1.getNumTuples(), 6)
|
|
self.assertEqual(n1.getTuples(1), [6])
|
|
self.assertEqual(n1.getTuples(2), [5, 6])
|
|
self.assertEqual(n1.getTuples(3), [4, 5, 6])
|
|
|
|
# das ist ein Tupel
|
|
n2 = Numbers([3, 3, 3])
|
|
self.assertEqual(n2.getNumTuples(), 1)
|
|
self.assertEqual(n2.getTuples(1), [3, 3, 3])
|
|
|
|
n3 = Numbers([3, 2, 1]) # nur ein Tupel drin
|
|
self.assertEqual(n3.getNumTuples(), 1)
|
|
self.assertEqual(n3.getTuples(1), [3, 2, 1])
|
|
|
|
n4 = Numbers([1, 10, 1, 10])
|
|
self.assertEqual(n4.getNumTuples(), 2)
|
|
self.assertEqual(n4.getTuples(1), [10])
|
|
self.assertEqual(n4.getTuples(2), [1, 10, 1, 10])
|
|
|
|
n5 = Numbers([30, 2, 1, 10, 5, 4, 16])
|
|
self.assertEqual(n5.getNumTuples(), 3)
|
|
self.assertEqual(n5.getTuples(1), [16])
|
|
self.assertEqual(n5.getTuples(2), [10, 5, 4, 16])
|
|
self.assertEqual(n5.getTuples(3), [30, 2, 1, 10, 5, 4, 16])
|
|
|
|
def test_roundabout(self):
|
|
k1 = Roundabout()
|
|
k1.addList([1, 2, 3])
|
|
self.assertEqual(k1.content(), [3, 2, 1])
|
|
self.assertEqual(k1.remove(), 1)
|
|
self.assertEqual(k1.content(), [3, 2])
|
|
|
|
k2 = Roundabout(LEFT) # links drehend - default
|
|
k2.add(1)
|
|
k2.add(2)
|
|
k2.add(3)
|
|
k2.add(4)
|
|
self.assertEqual(k2.content(), [4, 3, 2, 1])
|
|
|
|
k3 = Roundabout(RIGHT) # rechts drehend
|
|
k3.add(5)
|
|
k3.add(6)
|
|
k3.add(7)
|
|
k3.add(8)
|
|
self.assertEqual(k3.content(), [5, 6, 7, 8])
|
|
|
|
self.assertEqual(k2.itemOnSeparator(), 1)
|
|
self.assertEqual(k3.itemOnSeparator(), 5)
|
|
|
|
self.assertEqual(k3.remove(), 5)
|
|
self.assertEqual(k2.remove(), 1)
|
|
|
|
k5 = Roundabout()
|
|
self.assertEqual(k5.isEmpty(), True)
|
|
k5.addList([1, 2, 3])
|
|
self.assertEqual(k5.isEmpty(), False)
|
|
self.assertEqual(k5.getSmallestItem(), 1)
|
|
|
|
def test_roundabout_tuples(self):
|
|
|
|
k1 = Roundabout(LEFT)
|
|
self.assertEqual(k1.isEmpty(), True)
|
|
k1.addList([1, 2, 3, 4])
|
|
# in a left rotationg roundabout: one tuple is read as ascending from right to left
|
|
self.assertEqual(k1.content(), [4, 3, 2, 1])
|
|
# this is one tuple
|
|
self.assertEqual(k1.getNumTuples(), 1)
|
|
|
|
k1.clear()
|
|
k1.addList([4, 3, 2, 1])
|
|
# these are 4 tuples:
|
|
self.assertEqual(k1.content(), [1, 2, 3, 4])
|
|
self.assertEqual(k1.getNumTuples(), 4)
|
|
|
|
self.assertEqual(k1.getTuples(2), [3, 4])
|
|
self.assertEqual(k1.getTuples(3), [2, 3, 4])
|
|
|
|
|
|
k2 = Roundabout(RIGHT)
|
|
self.assertEqual(k2.isEmpty(), True)
|
|
k2.addList([1, 2, 3, 4, 5, 6])
|
|
# in a right rotationg roundabout: read tuples from left to right
|
|
self.assertEqual(k2.content(), [1, 2, 3, 4, 5, 6])
|
|
self.assertEqual(k2.getNumTuples(), 1)
|
|
k2.clear()
|
|
k2.addList([6, 5, 4, 3, 2, 1])
|
|
self.assertEqual(k2.getNumTuples(), 6)
|
|
|
|
self.assertEqual(k2.getTuples(3), [4, 5, 6])
|
|
self.assertEqual(k2.getTuples(5), [2, 3, 4, 5, 6])
|
|
|
|
|
|
def test_switch(self):
|
|
k1 = Roundabout()
|
|
k2 = Roundabout()
|
|
sw = Switch(k1, k2)
|
|
self.assertEqual(sw.set_to_left(), 0)
|
|
sw.set_to_right()
|
|
self.assertEqual(sw.is_right(), True)
|
|
self.assertEqual(sw.is_left(), False)
|
|
|
|
def test_pair(self):
|
|
lK = Roundabout()
|
|
lK.addList([6, 5, 4, 3, 2, 1])
|
|
rK = Roundabout(RIGHT)
|
|
sw = Switch(lK, rK)
|
|
p = RoundaboutPair(lK, rK, sw)
|
|
self.assertEqual(lK.content(), [1, 2, 3, 4, 5, 6])
|
|
self.assertEqual(p.show(), ([1, 2, 3, 4, 5, 6], []))
|
|
|
|
p.sortStepPickSort()
|
|
self.assertEqual(p.show(), ([6, 1, 2, 3, 4, 5], []))
|
|
p.sortStepPickSort()
|
|
self.assertEqual(p.show(), ([5, 6, 1, 2, 3, 4], []))
|
|
p.sortStepPickSort()
|
|
self.assertEqual(p.show(), ([4, 5, 6, 1, 2, 3], []))
|
|
p.sortStepPickSort()
|
|
self.assertEqual(p.show(), ([3, 4, 5, 6, 1, 2], []))
|
|
p.sortStepPickSort()
|
|
self.assertEqual(p.show(), ([2, 3, 4, 5, 6, 1], []))
|
|
p.sortStepPickSort()
|
|
self.assertEqual(p.show(), ([2, 3, 4, 5, 6], [1]))
|
|
|
|
def test_picksort(self):
|
|
lK = Roundabout()
|
|
lK.addList([6, 5, 4, 3, 2, 1])
|
|
rK = Roundabout(RIGHT)
|
|
sw = Switch(lK, rK)
|
|
p = RoundaboutPair(lK, rK, sw)
|
|
self.assertEqual(lK.content(), [1, 2, 3, 4, 5, 6])
|
|
|
|
p.runPickSort()
|
|
self.assertEqual(p.show(), ([], [1, 2, 3, 4, 5, 6]))
|
|
|
|
def test_tuplesort_equal(self):
|
|
lK = Roundabout()
|
|
lK.addList([3, 2, 1])
|
|
rK = Roundabout(RIGHT)
|
|
rK.addList([6, 5, 4])
|
|
sw = Switch(lK, rK)
|
|
p = RoundaboutPair(lK, rK, sw)
|
|
sw.set_to_right()
|
|
self.assertEqual(p.show(), ([1, 2, 3], [6, 5, 4])) # -> 3, 6
|
|
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([1, 2], [5, 4, 3, 6])) # -> 2, 5
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([5, 2, 1], [4, 3, 6])) # -> 1, 4
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([5, 2], [3, 6, 1, 4])) # -> 2, 3, 5, 6
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([6, 5, 3, 2], [1, 4])) # -> 1, 2, 3, 4, 5, 6
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([], [1, 2, 3, 4, 5, 6]))
|
|
|
|
def test_tuplesort_stepbystep(self):
|
|
lK = Roundabout()
|
|
lK.addList([6, 5, 4, 3, 2, 1])
|
|
rK = Roundabout(RIGHT)
|
|
rK.addList([])
|
|
sw = Switch(lK, rK)
|
|
p = RoundaboutPair(lK, rK, sw)
|
|
sw.set_to_right()
|
|
self.assertEqual(p.show(), ([1, 2, 3, 4, 5, 6], []))
|
|
|
|
# p.sortStepTupleSort()
|
|
# self.assertEqual(p.show(), ([1, 2], [5, 4, 3, 6]))
|
|
# p.sortStepTupleSort()
|
|
# self.assertEqual(p.show(), ([5, 2, 1], [4, 3, 6]))
|
|
# p.sortStepTupleSort()
|
|
# self.assertEqual(p.show(), ([5, 2], [3, 6, 1, 4]))
|
|
# p.sortStepTupleSort()
|
|
# self.assertEqual(p.show(), ([6, 5, 3, 2], [1, 4]))
|
|
# p.sortStepTupleSort()
|
|
# self.assertEqual(p.show(), ([], [1, 2, 3, 4, 5, 6]))
|
|
|
|
def test_tuplesort_onlyleft(self):
|
|
# Roundabouts befüllen
|
|
lK = Roundabout()
|
|
lK.addList([1, 2, 3, 4, 5])
|
|
rK = Roundabout(RIGHT)
|
|
rK.addList([])
|
|
|
|
sw = Switch(lK, rK)
|
|
p = RoundaboutPair(lK, rK, sw)
|
|
self.assertEqual(p.show(), ([5, 4, 3, 2, 1], [] ))
|
|
sw.set_to_right()
|
|
|
|
# Sortierung starten
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([], [1, 2, 3, 4, 5] ))
|
|
|
|
def test_tuplesort_presorted(self):
|
|
lK = Roundabout()
|
|
lK.addList([2, 5])
|
|
rK = Roundabout(RIGHT)
|
|
rK.addList([3, 6, 1, 4])
|
|
|
|
sw = Switch(lK, rK)
|
|
p = RoundaboutPair(lK, rK, sw)
|
|
self.assertEqual(p.show(), ([5, 2], [3, 6, 1, 4] ))
|
|
|
|
sw.set_to_left()
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([6, 5, 3, 2], [1, 4] )) # r
|
|
p.sortStepTupleSort()
|
|
self.assertEqual(p.show(), ([], [1, 2, 3, 4, 5, 6] )) # l
|
|
|
|
def test_tuplesort_init(self):
|
|
lK = Roundabout()
|
|
lK.addList([6, 5, 4, 3, 2, 1])
|
|
rK = Roundabout(RIGHT)
|
|
rK.addList([])
|
|
sw = Switch(lK, rK)
|
|
p = RoundaboutPair(lK, rK, sw)
|
|
sw.set_to_right()
|
|
self.assertEqual(p.show(), ([1, 2, 3, 4, 5, 6], []))
|
|
|
|
|
|
p.initTupleSort()
|
|
|
|
self.assertEqual(p.show(), ([1, 2, 3], [6, 5, 4]))
|
|
|
|
|
|
if __name__ == '__main__':
|
|
unittest.main()
|
|
|
|
|