moarchiving.moarchiving_utils.ArchiveSortedList

class documentation

class ArchiveSortedList(SortedKeyList):

Constructor: ArchiveSortedList(iterable, key)

View In Hierarchy

A class to represent a sorted list of nodes, together with additional methods that follow the definition in the paper.

Method __init__ Initialize the sorted list with the given iterable and key function.
Method __str__ Return a string representation of the sorted list.
Method add_x Insert point p into the list, if s_x < p_x < next_x(s)_x or p_x < head_x_x
Method add_y Insert point p into the list, if s_y < p_y < next_y(s)_y or p_y < head_y_y
Method head_x Return the point q from the list, with the smallest q_x
Method head_y Return the point q from the list, with the smallest q_y
Method next_x Return the point q from the list, with the smallest q_x > s_x, for a given point s from the list
Method next_y Return the point q from the list, with the smallest q_y > s_y, for a given point s from the list
Method outer_delimiter_x Return the point q from the list, with the smallest q_x > p_x, such that q_y < p_y
Method outer_delimiter_y Return the point q from the list, with the smallest q_y > p_y, such that q_x < p_x
Method remove_dominated_x For s = outer_delimiter_y(p), remove all points q, such that p* <= q* from the list, and return them sorted by ascending order of q_x
Method remove_dominated_y For s = outer_delimiter_x(p), remove all points q, such that p* <= q* from the list, and return them sorted by ascending order of q_y
def __init__(self, iterable=None, key=(lambda node: node.x[1])):

Initialize the sorted list with the given iterable and key function.

def __str__(self):

Return a string representation of the sorted list.

def add_x(self, p, s):

Insert point p into the list, if s_x < p_x < next_x(s)_x or p_x < head_x_x

def add_y(self, p, s):

Insert point p into the list, if s_y < p_y < next_y(s)_y or p_y < head_y_y

def head_x(self):

Return the point q from the list, with the smallest q_x

def head_y(self):

Return the point q from the list, with the smallest q_y

def next_x(self, s):

Return the point q from the list, with the smallest q_x > s_x, for a given point s from the list

def next_y(self, s):

Return the point q from the list, with the smallest q_y > s_y, for a given point s from the list

def outer_delimiter_x(self, p):

Return the point q from the list, with the smallest q_x > p_x, such that q_y < p_y

def outer_delimiter_y(self, p):

Return the point q from the list, with the smallest q_y > p_y, such that q_x < p_x

def remove_dominated_x(self, p, s):

For s = outer_delimiter_y(p), remove all points q, such that p* <= q* from the list, and return them sorted by ascending order of q_x

def remove_dominated_y(self, p, s):

For s = outer_delimiter_x(p), remove all points q, such that p* <= q* from the list, and return them sorted by ascending order of q_y