| 50 | |
| 51 | |
| 52 | class SkipList[KT, VT]: |
| 53 | def __init__(self, p: float = 0.5, max_level: int = 16): |
| 54 | self.head: Node[KT, VT] = Node[KT, VT]() |
| 55 | self.level = 0 |
| 56 | self.p = p |
| 57 | self.max_level = max_level |
| 58 | |
| 59 | def __str__(self) -> str: |
| 60 | """ |
| 61 | :return: Visual representation of SkipList |
| 62 | |
| 63 | >>> skip_list = SkipList() |
| 64 | >>> print(skip_list) |
| 65 | SkipList(level=0) |
| 66 | >>> skip_list.insert("Key1", "Value") |
| 67 | >>> print(skip_list) # doctest: +ELLIPSIS |
| 68 | SkipList(level=... |
| 69 | [root]--... |
| 70 | [Key1]--Key1... |
| 71 | None *... |
| 72 | >>> skip_list.insert("Key2", "OtherValue") |
| 73 | >>> print(skip_list) # doctest: +ELLIPSIS |
| 74 | SkipList(level=... |
| 75 | [root]--... |
| 76 | [Key1]--Key1... |
| 77 | [Key2]--Key2... |
| 78 | None *... |
| 79 | """ |
| 80 | |
| 81 | items = list(self) |
| 82 | |
| 83 | if len(items) == 0: |
| 84 | return f"SkipList(level={self.level})" |
| 85 | |
| 86 | label_size = max((len(str(item)) for item in items), default=4) |
| 87 | label_size = max(label_size, 4) + 4 |
| 88 | |
| 89 | node = self.head |
| 90 | lines = [] |
| 91 | |
| 92 | forwards = node.forward.copy() |
| 93 | lines.append(f"[{node.key}]".ljust(label_size, "-") + "* " * len(forwards)) |
| 94 | lines.append(" " * label_size + "| " * len(forwards)) |
| 95 | |
| 96 | while len(node.forward) != 0: |
| 97 | node = node.forward[0] |
| 98 | |
| 99 | lines.append( |
| 100 | f"[{node.key}]".ljust(label_size, "-") |
| 101 | + " ".join(str(n.key) if n.key == node.key else "|" for n in forwards) |
| 102 | ) |
| 103 | lines.append(" " * label_size + "| " * len(forwards)) |
| 104 | forwards[: node.level] = node.forward |
| 105 | |
| 106 | lines.append("None".ljust(label_size) + "* " * len(forwards)) |
| 107 | return f"SkipList(level={self.level})\n" + "\n".join(lines) |
| 108 | |
| 109 | def __iter__(self): |
no outgoing calls