Structure to handle collisions
| 34 | |
| 35 | |
| 36 | class IHT: |
| 37 | "Structure to handle collisions" |
| 38 | |
| 39 | def __init__(self, sizeval): |
| 40 | self.size = sizeval |
| 41 | self.overfullCount = 0 |
| 42 | self.dictionary = {} |
| 43 | |
| 44 | def __str__(self): |
| 45 | "Prepares a string for printing whenever this object is printed" |
| 46 | return ( |
| 47 | "Collision table:" |
| 48 | + " size:" |
| 49 | + str(self.size) |
| 50 | + " overfullCount:" |
| 51 | + str(self.overfullCount) |
| 52 | + " dictionary:" |
| 53 | + str(len(self.dictionary)) |
| 54 | + " items" |
| 55 | ) |
| 56 | |
| 57 | def count(self): |
| 58 | return len(self.dictionary) |
| 59 | |
| 60 | def fullp(self): |
| 61 | return len(self.dictionary) >= self.size |
| 62 | |
| 63 | def getindex(self, obj, readonly=False): |
| 64 | d = self.dictionary |
| 65 | if obj in d: |
| 66 | return d[obj] |
| 67 | elif readonly: |
| 68 | return None |
| 69 | size = self.size |
| 70 | count = self.count() |
| 71 | if count >= size: |
| 72 | if self.overfullCount == 0: |
| 73 | print("IHT full, starting to allow collisions") |
| 74 | self.overfullCount += 1 |
| 75 | return basehash(obj) % self.size |
| 76 | else: |
| 77 | d[obj] = count |
| 78 | return count |
| 79 | |
| 80 | |
| 81 | def hashcoords(coordinates, m, readonly=False): |