"""
TreeSet implementation using Red-Black Tree for efficient sorted set operations.
This module provides a TreeSet class that implements a sorted set data structure
using an underlying Red-Black Tree. It offers efficient insertion, deletion, and
lookup operations while maintaining elements in sorted order.
Classes
-------
TreeSet
A sorted set implementation that maintains unique elements in sorted order
using a Red-Black Tree as the underlying data structure.
"""
import sys
from PyQt5.QtWidgets import QApplication
from typing import Iterator, Optional, Sequence, Any, Callable
from red_black_tree import RedBlackTree
from tree_applet import TreeView
[docs]
class TreeSet:
"""
Implements a TreeSet using a Red-Black Tree.
Attributes
----------
_tree: RedBlackTree
The underlying Red-Black Tree used to store the elements.
_size: int
The number of elements in the TreeSet.
"""
def __init__(self, item_type: type, collection: Optional[Sequence[Any]] = None, funct: Optional[Callable[[Any], Any]] = None):
self._tree = RedBlackTree(item_type, comparator=funct)
self._size = 0
if collection:
self.add_all(collection)
[docs]
def add(self, value: object) -> bool:
"""
Adds a value to the TreeSet.
Args:
value (object): The value to be added to the TreeSet.
Returns:
bool: True if the value was added, False if it was already present.
Raises:
TypeError: If the value is not of the correct type for the TreeSet.
ValueError: If the value is None or if it cannot be compared with existing elements.
"""
if not self._tree.insert(value)[0]:
self._size += 1
return True
return False
[docs]
def add_all(self, collection: Sequence[Any]) -> bool:
"""
Adds all elements from a collection to the TreeSet.
Args:
collection (Sequence[Any]): A sequence of elements to be added to the TreeSet.
Returns:
bool: True if any elements were added, False if the collection was empty or all elements were already present.
"""
changed = False
for item in collection:
if self.add(item):
changed = True
return changed
[docs]
def ceiling(self, value: object) -> object:
"""
Returns the least element in the set greater than or equal to the given value.
Args:
value (object): The value to compare against. Returns
object: The least element greater than or equal to the given value, or None if no such element exists.
"""
return self._tree.higher(value, True)
[docs]
def clear(self):
"""
Clears the TreeSet, removing all elements.
"""
self._tree = RedBlackTree(self._tree.type)
self._size = 0
[docs]
def clone(self):
"""
Creates a shallow copy of the TreeSet.
Returns
-------
TreeSet
A new TreeSet instance containing the same elements.
"""
return TreeSet(self._tree.type, self._tree.items())
[docs]
def contains(self, value: object) -> bool:
"""
Checks if the TreeSet contains a specific value.
Args:
value (object): The value to check for presence in the TreeSet.
Returns:
bool: True if the value is present, False otherwise.
Raises:
TypeError: If the value is not of the correct type for the TreeSet.
ValueError: If the value is None or if it cannot be compared with existing elements.
"""
return True if not self._tree.find(value)[0] else False
[docs]
def descending_iterator(self) -> Iterator[Any]:
"""
Returns an iterator that traverses the elements of the TreeSet in descending order.
Returns
-------
Iterator[Any]
An iterator that yields elements in descending order.
"""
datos = self._tree.items()[::-1]
class MyIterator:
def __init__(self, datos: Sequence[Any]):
self.datos = datos
self.indice = 0
def __iter__(self):
return self
def __next__(self):
if self.indice >= len(self.datos):
raise StopIteration
valor = self.datos[self.indice]
self.indice += 1
return valor
return MyIterator(datos)
[docs]
def first(self) -> object:
"""
Returns the first (smallest) element in the TreeSet.
Returns
-------
object
The first element in the TreeSet, or None if the set is empty.
"""
return self._tree.smallest
[docs]
def floor(self, value: object) -> object:
"""
Returns the greatest element in the set less than or equal to the given value.
Args:
value (object): The value to compare against.
Returns:
object: The greatest element less than or equal to the given value, or None if no such element exists.
"""
return self._tree.lower(value, True)
[docs]
def higher(self, value: object) -> object:
"""
Returns the least element in the set strictly greater than the given value.
Args:
value (object): The value to compare against.
Returns:
object: The least element strictly greater than the given value, or None if no such element exists.
"""
return self._tree.higher(value, False)
[docs]
def is_empty(self) -> bool:
"""
Checks if the TreeSet is empty.
Returns:
bool: True if the TreeSet is empty, False otherwise.
"""
return self._size == 0
[docs]
def iterator(self) -> Iterator[Any]:
"""
Returns an iterator that traverses the elements of the TreeSet in ascending order.
Returns:
Iterator[Any]: An iterator that yields elements in ascending order.
"""
datos = self._tree.items()
class MyIterator:
def __init__(self, datos: Sequence[Any]):
self.datos = datos
self.indice = 0
def __iter__(self) -> Iterator[Any]:
return self
def __next__(self) -> Any:
if self.indice >= len(self.datos):
raise StopIteration
valor = self.datos[self.indice]
self.indice += 1
return valor
return MyIterator(datos)
[docs]
def last(self) -> object:
"""
Returns the last (largest) element in the TreeSet.
Returns:
object: The last element in the TreeSet, or None if the set is empty.
"""
return self._tree.largest
[docs]
def lower(self, value: object) -> object:
"""
Returns the greatest element in the set strictly less than the given value.
Args:
value (object): The value to compare against.
Returns:
object: The greatest element strictly less than the given value, or None if no such element exists.
"""
return self._tree.lower(value, False)
[docs]
def poll_first(self) -> object:
"""
Removes and returns the first (smallest) element in the TreeSet.
Returns:
object: The first element in the TreeSet, or None if the set is empty.
"""
if self._size == 0:
return None
smallest = self._tree.smallest
self._tree.remove(smallest)
self._size -= 1
return smallest
[docs]
def poll_last(self) -> object:
"""
Removes and returns the last (largest) element in the TreeSet.
Returns:
object: The last element in the TreeSet, or None if the set is empty.
"""
if self._size == 0:
return None
largest = self._tree.largest
self._tree.remove(largest)
self._size -= 1
return largest
[docs]
def remove(self, value: object) -> bool:
"""
Removes a specific value from the TreeSet.
Args:
value (object): The value to be removed from the TreeSet.
Returns:
bool: True if the value was removed, False if it was not present in the TreeSet.
Raises:
TypeError: If the value is not of the correct type for the TreeSet.
ValueError: If the value is None or if it cannot be compared with existing elements.
"""
if not self._tree.remove(value)[0]:
self._size -= 1
return True
return False
[docs]
def size(self) -> int:
"""
Returns the number of elements in the TreeSet.
Returns:
int: The number of elements in the TreeSet.
"""
return self._size
[docs]
def visualize_tree(self):
"""
Visualizes the Red-Black Tree using a PyQt5 application.
This method creates a PyQt5 application and displays the tree in a graphical view.
"""
app = QApplication(sys.argv)
view = TreeView(self._tree)
view.resize(1200, 800)
view.show()
# 4. Execute the app
app.exec_()