Source code for tryalgo.partition_refinement

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
Partition refinement
christoph dürr - 2016-2019

log: 10/11/2016 modified to preserve class order after refinement
     15/11/2016 this was nonsense, moved back

__all__ = ["PartitionRefinement"]

# pylint: disable=missing-docstring
class DoubleLinkedListItem:
    """Item of a circular double linked list

    def __init__(self, anchor=None):
        """Create a new item to be inserted before item anchor.
           if anchor is None: create a single item circular double linked list
        if anchor:
            self.prec = self
            self.succ = self

    def remove(self):
        self.prec.succ = self.succ
        self.succ.prec = self.prec

    def insert(self, anchor):
        """insert list item before anchor
        self.prec = anchor.prec        # point to neighbors
        self.succ = anchor
        self.succ.prec = self          # make neighbors point to item
        self.prec.succ = self

    def __iter__(self):
        """iterate trough circular list.
        warning: might end stuck in an infinite loop if chaining is not valid
        curr = self
        yield self
        while curr.succ != self:
            curr = curr.succ
            yield curr

class PartitionClass(DoubleLinkedListItem):
    """A partition is a list of classes

    def __init__(self, anchor=None):
        DoubleLinkedListItem.__init__(self, anchor)
        self.items = None         # empty list
        self.split = None         # reference to split class

    def append(self, item):
        """add item to the end of the item list
        if not self.items:        # was list empty ?
            self.items = item     # then this is the new head

class PartitionItem(DoubleLinkedListItem):
    """A class is a list of items

    def __init__(self, val, theclass):
        self.val = val
        self.theclass = theclass

    def remove(self):
        """remove item from its class
        DoubleLinkedListItem.remove(self)     # remove from double linked list
        if self.succ is self:                 # list was a singleton
            self.theclass.items = None        # class is empty
        elif self.theclass.items is self:     # oups we removed the head
            self.theclass.items = self.succ   # head is now successor

[docs]class PartitionRefinement: """This data structure implements an order preserving partition with refinements. """ def __init__(self, n): """Start with the partition consisting of the unique class {0,1,..,n-1} complexity: O(n) both in time and space """ c = PartitionClass() # initially there is a single class of size n self.classes = c # reference to first class in class list self.items = [PartitionItem(i, c) for i in range(n)] # value-ordered
[docs] def refine(self, pivot): """Split every class C in the partition into C intersection pivot and C setminus pivot complexity: linear in size of pivot """ has_split = [] # remember which classes split for i in pivot: if 0 <= i < len(self.items): # ignore if outside of domain x = self.items[i] c = x.theclass # c = class of x if not c.split: # possibly create new split class c.split = PartitionClass(c) if self.classes is c: self.classes = c.split # always point to 1st class has_split.append(c) x.remove() # remove from its class x.theclass = c.split c.split.append(x) # append to the split class for c in has_split: # clean information about split classes c.split = None if not c.items: # delete class if it became empty c.remove() del c
[docs] def tolist(self): """produce a list representation of the partition """ return [[x.val for x in theclass.items] for theclass in self.classes]
[docs] def order(self): """Produce a flatten list of the partition, ordered by classes """ return [x.val for theclass in self.classes for x in theclass.items]