From e26434979adc33bd949566ba7bf02dff64e80a3e Mon Sep 17 00:00:00 2001 From: Chris Dyer Date: Tue, 2 Oct 2012 00:19:43 -0400 Subject: cdec cleanup, remove bayesian stuff, parsing stuff --- jam-files/boost-build/util/order.py | 121 ------------------------------------ 1 file changed, 121 deletions(-) delete mode 100644 jam-files/boost-build/util/order.py (limited to 'jam-files/boost-build/util/order.py') diff --git a/jam-files/boost-build/util/order.py b/jam-files/boost-build/util/order.py deleted file mode 100644 index 4e67b3f1..00000000 --- a/jam-files/boost-build/util/order.py +++ /dev/null @@ -1,121 +0,0 @@ -# Copyright (C) 2003 Vladimir Prus -# Use, modification, and distribution is subject to the Boost Software -# License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy -# at http://www.boost.org/LICENSE_1_0.txt) - -class Order: - """Allows ordering arbitrary objects with regard to arbitrary binary relation. - - The primary use case is the gcc toolset, which is sensitive to - library order: if library 'a' uses symbols from library 'b', - then 'a' must be present before 'b' on the linker's command line. - - This requirement can be lifted for gcc with GNU ld, but for gcc with - Solaris LD (and for Solaris toolset as well), the order always matters. - - So, we need to store order requirements and then order libraries - according to them. It it not possible to use dependency graph as - order requirements. What we need is "use symbols" relationship - while dependency graph provides "needs to be updated" relationship. - - For example:: - lib a : a.cpp b; - lib b ; - - For static linking, the 'a' library need not depend on 'b'. However, it - still should come before 'b' on the command line. - """ - - def __init__ (self): - self.constraints_ = [] - - def add_pair (self, first, second): - """ Adds the constraint that 'first' should precede 'second'. - """ - self.constraints_.append ((first, second)) - - def order (self, objects): - """ Given a list of objects, reorder them so that the constains specified - by 'add_pair' are satisfied. - - The algorithm was adopted from an awk script by Nikita Youshchenko - (yoush at cs dot msu dot su) - """ - # The algorithm used is the same is standard transitive closure, - # except that we're not keeping in-degree for all vertices, but - # rather removing edges. - result = [] - - if not objects: - return result - - constraints = self.__eliminate_unused_constraits (objects) - - # Find some library that nobody depends upon and add it to - # the 'result' array. - obj = None - while objects: - new_objects = [] - while objects: - obj = objects [0] - - if self.__has_no_dependents (obj, constraints): - # Emulate break ; - new_objects.extend (objects [1:]) - objects = [] - - else: - new_objects.append (obj) - obj = None - objects = objects [1:] - - if not obj: - raise BaseException ("Circular order dependencies") - - # No problem with placing first. - result.append (obj) - - # Remove all containts where 'obj' comes first, - # since they are already satisfied. - constraints = self.__remove_satisfied (constraints, obj) - - # Add the remaining objects for further processing - # on the next iteration - objects = new_objects - - return result - - def __eliminate_unused_constraits (self, objects): - """ Eliminate constraints which mention objects not in 'objects'. - In graph-theory terms, this is finding subgraph induced by - ordered vertices. - """ - result = [] - for c in self.constraints_: - if c [0] in objects and c [1] in objects: - result.append (c) - - return result - - def __has_no_dependents (self, obj, constraints): - """ Returns true if there's no constraint in 'constraints' where - 'obj' comes second. - """ - failed = False - while constraints and not failed: - c = constraints [0] - - if c [1] == obj: - failed = True - - constraints = constraints [1:] - - return not failed - - def __remove_satisfied (self, constraints, obj): - result = [] - for c in constraints: - if c [0] != obj: - result.append (c) - - return result -- cgit v1.2.3