Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #bin class
- class Bin:
- def __init__(self):
- """Takes in no args, initializes to an empty list"""
- self.content = []
- def push(self,a_input):
- """Adds an item to the front of the que"""
- self.content.append(a_input)
- def pop(self):
- """Returns the item at the front of the que, then deletes it"""
- self.check_empty()
- result = self.content[0]
- del self.content[0]
- return result
- def peek(self):
- """Returns the item at the front of the que"""
- self.check_empty()
- return self.content[0]
- def check_empty(self):
- """Raises an error if the list if empty"""
- if len(self.content) == 0:
- raise Exception("Bin is empty")
- def check_size(self):
- return len(self.content)
- #bin unit tests
- import unittest
- import Bin
- class BinTest(unittest.TestCase):
- def testBin(self):
- x = Bin.Bin()
- x.push(1)
- self.assertEqual(x.peek(),1)
- x.push(2)
- self.assertEqual(x.pop(),1)
- self.assertEqual(x.peek(),2)
- self.assertEqual(x.pop(), 2)
- self.assertRaises(Exception, x.check_empty)
- self.assertRaises(Exception, x.peek)
- self.assertRaises(Exception, x.pop)
- if __name__ == '__main__':
- unittest.main()
- #radix class
- import Bin
- class Radix:
- def __init__(self):
- self.one = Bin.Bin()
- self.two = Bin.Bin()
- self.three = Bin.Bin()
- self.four = Bin.Bin()
- self.five = Bin.Bin()
- self.six = Bin.Bin()
- self.seven = Bin.Bin()
- self.eight = Bin.Bin()
- self.nine = Bin.Bin()
- self.zero = Bin.Bin()
- self.main = Bin.Bin()
- @staticmethod
- def check_if_list(args):
- if type(args) != list:
- raise TypeError("Must take in a list")
- @staticmethod
- def split_string(args):
- """Turns all list items into strings as preparation for manipulation"""
- Radix.check_if_list(args)
- for i in range(len(args)):
- args[i] = str(args[i])
- return args
- @staticmethod
- def equalize(args):
- """Formats all list items to have the same # of digits, ex 200, 2, 20 become 200, 002, 020 - probably
- unneccesary and can be removed and refactored if performance is an issue, returns max length of items in arg"""
- max_len = Radix.get_max_len(args)
- index = 0
- for i in args:
- while len(str(i)) < max_len:
- i = "0" + i
- args[index] = i
- index += 1
- return args
- def print(self):
- while self.main.check_size() > 0:
- print(self.main.pop())
- @staticmethod
- def get_max_len(args):
- max_len = 0
- for i in args:
- if len(str(i)) > max_len:
- max_len = len(str(i))
- return max_len
- def sort(self, args):
- args = Radix.split_string(args) #converts the list to strings
- args = Radix.equalize(args) #makes all the values in the list the same size (appends zeros to the front)
- size_of = len(args)
- max_len = Radix.get_max_len(args)-1
- for i in args:
- self.main.push(i) #starts by throwing all of the values into the main bin
- for i in range(max_len+1): #for every digit, split the digits into their respective buckets and then throw them back into main
- self.split_digits(i,max_len)
- def place_into_bucket(self,num,max_len):
- if self.main.peek()[max_len-num] == '0':
- self.zero.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '1':
- self.one.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '2':
- self.two.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '3':
- self.three.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '4':
- self.four.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '5':
- self.five.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '6':
- self.six.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '7':
- self.seven.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '8':
- self.eight.push(self.main.pop())
- elif self.main.peek()[max_len - num] == '9':
- self.nine.push(self.main.pop())
- """Determines which bucket the number should go in, then puts it in there while popping it off main"""
- def empty_buckets(self):
- """Removes all values from buckets, puts them all into main bucket in order"""
- while self.zero.check_size() > 0:
- self.main.push(self.zero.pop())
- while self.one.check_size() > 0:
- self.main.push(self.one.pop())
- while self.two.check_size() > 0:
- self.main.push(self.two.pop())
- while self.three.check_size() > 0:
- self.main.push(self.three.pop())
- while self.four.check_size() > 0:
- self.main.push(self.four.pop())
- while self.five.check_size() > 0:
- self.main.push(self.five.pop())
- while self.six.check_size() > 0:
- self.main.push(self.six.pop())
- while self.seven.check_size() > 0:
- self.main.push(self.seven.pop())
- while self.eight.check_size() > 0:
- self.main.push(self.eight.pop())
- while self.nine.check_size() > 0:
- self.main.push(self.nine.pop())
- def split_digits(self,num,max_len):
- while self.main.check_size() > 0:
- self.place_into_bucket(num,max_len)
- self.empty_buckets()
- #main
- import Radix
- x = Radix.Radix()
- y = [123,456,789,101112,542,1234993,324903249239,352,1234234,3212,1234234523,342564,656,7657,856765,435324,12312,5435,67,654546,75454678,8657657]
- x.sort(y)
- x.print()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement