Last active
November 3, 2023 04:59
-
-
Save james4388/aa4c91ddecf19975ea24a1b8f8c4baba to your computer and use it in GitHub Desktop.
String Tree implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from abc import ABC, abstractmethod | |
class Node(ABC): | |
length: int = 0 | |
@abstractmethod | |
def char_at(self, index: int) -> str: | |
raise IndexError() | |
@abstractmethod | |
def sub_string(self, start: int, end: int) -> str: | |
raise IndexError() | |
@abstractmethod | |
def delete(self, index:int) -> None: | |
raise IndexError() | |
class InternalNode(Node): | |
def __init__(self, length=0, left=None, right=None): | |
self.length = length | |
self.left = left | |
self.right = right | |
def char_at(self, index: int) -> str: | |
if index >= self.length: | |
raise IndexError() | |
if self.left and index < self.left.length: | |
return self.left.char_at(index) | |
if self.right: | |
return self.right.char_at(index - self.left.length) | |
raise IndexError() | |
def sub_string(self, start: int, end: int) -> str: | |
substr = [] | |
if self.left and start < self.left.length: | |
substr.append(self.left.sub_string(start, min(end, self.left.length - 1))) | |
if self.right and end >= self.left.length: | |
substr.append(self.right.sub_string(0, end - self.left.length)) | |
return ''.join(substr) | |
def delete(self, index:int) -> None: | |
if index >= self.length: | |
raise IndexError() | |
if self.left and index < self.left.length: | |
return self.left.delete(index) | |
if self.right: | |
return self.right.delete(index - self.left.length) | |
class Leaf(Node): | |
def __init__(self, string: str='', length=0): | |
self.string = string | |
self.length = length or len(string) | |
def char_at(self, index: int) -> str: | |
if index >= self.length: | |
raise IndexError() | |
return self.string[index] | |
def sub_string(self, start: int, end: int) -> str: | |
return self.string[start:end + 1] | |
def delete(self, index:int) -> None: | |
if index >= self.length: | |
raise IndexError() | |
self.string = self.string[:index] + self.string[index + 1:] | |
self.length -= 1 | |
class StringTree: | |
def __init__(self): | |
self.root = InternalNode() | |
if __name__ == '__main__': | |
leaf1 = Leaf(string='ABCDE') | |
leaf2 = Leaf(string='FGHIJKLMNO') | |
leaf3 = Leaf(string='PQRSTUVWXYZ') | |
inode1 = InternalNode(21, left=leaf2, right=leaf3) | |
root = InternalNode(26, left=leaf1, right=inode1) | |
print(root.char_at(25)) | |
print(root.sub_string(1, 3)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment