import operator
def _bisect_left(array, element, lo = 0, hi = None, comp = None):
if comp is None:
comp = operator.lt
if hi is None:
hi = len(array)
while lo < hi:
middle = (lo+hi) // 2
if not comp(array[middle], element):
hi = middle
else:
lo = middle+1
return hi
class longest_subsequence_result(object):
def __init__(self, sequence, positions, endingElements, ordering):
self.length = len(endingElements) - 1
if self.length > 0:
self.positions_ = self.computePositions(positions, endingElements)
self.elements_ = self.computeElements(sequence)
else:
self.positions_ = []
self.elements_ = []
self.ordering = ordering
def __len__(self):
return self.length
def computePositions(self, positions, endingElements):
positions_ = [None] * self.length
scan = endingElements[self.length]
for i in reversed(xrange(0,self.length)):
positions_[i] = scan
scan = positions[positions_[i]]
return positions_
def computeElements(self, sequence):
return [ sequence[index] for index in self.positions_ ]
def __len__(self):
return self._length
def get_ordering():
return self.ordering
def get_elements(self):
return self.elements_
def get_positions(self):
return self.positions_
def longest_subsequence(sequence, comp = None):
if not sequence:
return longest_subsequence_result( None, None, [], comp )
if comp is None:
comp = operator.lt
endingElements = [None]
previousElements = []
for index, element in enumerate(sequence):
insertionPos = _bisect_left(endingElements, element, lo = 1, comp=lambda a, b: comp(sequence[a],b))
if insertionPos == len(endingElements):
endingElements.append(index)
else:
endingElements[ insertionPos ] = index
previousElements.append( endingElements[ insertionPos - 1 ] )
return longest_subsequence_result( sequence, previousElements, endingElements, comp )
if __name__ == "__main__":
array = [0,1,4,6,3,2,3,4,5,1,23,34,12,-1,23,54,1,2]
print longest_subsequence( array ).get_elements()
print longest_subsequence( array, operator.le ).get_elements()
print longest_subsequence( array, operator.gt ).get_elements()
