def can_place_at(self, system, plan):
        """
        Check if the starlane altering monster fleet ''plan'' can be placed at ''system''
        without disjoining the galaxy map.
        Compute the disjoint set of the galaxy without the starlanes
        from the proposed system.  Return False if there will be more
        connected regions than the number of placed starlane altering
        monsters plus one, otherwise True.
        """
        local_lanes = {(min(system, s), max(system, s)) for s in fo.sys_get_starlanes(system)}

        dsets = DisjointSets()
        for s in self.systems:
            dsets.add(s)

        for lane in self.starlanes:
            if lane in self.removed_lanes or lane in local_lanes:
                continue
            dsets.link(lane[0], lane[1])

        num_contiguous_regions = len(dsets.complete_sets())
        expected_num_contiguous_regions = (len(self.placed) + 2)

        if num_contiguous_regions > expected_num_contiguous_regions:
            return False

        if num_contiguous_regions < expected_num_contiguous_regions:
            report_error("Number of contiguous regions %d is below the expected number "
                         "of contiguous regions %d when placing %d monster %s that can "
                         "break starlanes."
                         % (num_contiguous_regions, expected_num_contiguous_regions,
                            len(self.placed) + 1, plan.name()))
            return False

        return True

def stitching_positions(p1, p2):
    """
    Returns a list of positions between p1 and p2 between MIN_SYSTEM_SEPARATION and MAX_STARLANE_LENGTH apart
    """
    if 2 * universe_tables.MIN_SYSTEM_SEPARATION >= universe_tables.MAX_STARLANE_LENGTH:
        util.report_error("MAX_STARLANE_LENGTH must be twice MIN_SYSTEM_SEPARATION to "
                          "allow extra positions to be added to enforce MAX_STARLANE_LENGTH")
        return []

    max_dist = universe_tables.MAX_STARLANE_LENGTH
    min_dist = universe_tables.MIN_SYSTEM_SEPARATION
    p1_p2_dist = util.distance(p1, p2)
    if p1_p2_dist < max_dist:
        return []

    # Pick a random point in an 2:1 ratio ellipse and then rotate and slide it in between p1 and p2
    p1_p2_theta = acos((p2[0] - p1[0]) / p1_p2_dist)
    p1_p2_scale = (p1_p2_dist - 2*min_dist) / 2
    p1_p2_translation = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)

    radius_0space = uniform(0.0, 1.0)
    angle_0space = uniform(0.0, 2.0 * pi)
    rotated_point = (radius_0space * p1_p2_scale * cos(angle_0space + p1_p2_theta),
                     radius_0space * p1_p2_scale * sin(angle_0space + p1_p2_theta))

    p3 = (rotated_point[0] + p1_p2_translation[0], rotated_point[1] + p1_p2_translation[1])

    return [p3] + stitching_positions(p1, p3) + stitching_positions(p2, p3)

    def __distribute(self, dl_info):
        assert isinstance(dl_info, download_info)
        
        util.report_info("Verifying <%s> ..." % dl_info.res_path)

        # Verify distribute source
        if not os.path.isfile(dl_info.store_path):
            util.report_error("File <%s> is not existed. Please check your network state and re-run build script." % dl_info.res_path)

        if fhash.hash_file(dl_info.store_path) != dl_info.tag:
            util.report_error("File <%s> verificaition is failed. Please check your network state and re-run build script." % dl_info.res_path)

        util.report_info("Distributing <%s> ..." % dl_info.res_path)

        # Clean target if file is existed.
        if dl_info.res_type in [RAW_FILE, COMPRESSED_FILE]:
            if os.path.isfile(dl_info.dist_path):
                os.remove(dl_info.dist_path)
        elif dl_info.res_type in [COMPRESSED_FOLDER]:
            if os.path.isdir(dl_info.dist_path):
                shutil.rmtree(dl_info.dist_path)

        dist_parent = os.path.dirname(dl_info.dist_path)
        if dl_info.res_type in [COMPRESSED_FILE, COMPRESSED_FOLDER]:
            self.__decompress(dl_info.store_path, dist_parent)
        else:
            shutil.copy(dl_info.store_path, dist_parent)

def calc_planet_size(star_type, orbit, planet_density, galaxy_shape):
    """
    Calculate planet size for a potential new planet based on planet density setup option, star type and orbit number.
    """
    # try to pick a planet size by making a series of "rolls" (1-100)
    # for each planet size, and take the highest modified roll
    planet_size = fo.planetSize.unknown
    try:
        max_roll = 0
        for size in planet_sizes_all:
            roll = (random.randint(1, 100)
                    + base_chance_of_planet(planet_density, galaxy_shape, star_type, orbit, size))
            if max_roll < roll:
                max_roll = roll
                planet_size = size
    except:
        # in case of an error play it safe and set planet size to invalid
        planet_size = fo.planetSize.unknown
        util.report_error("Python calc_planet_size: Pick planet size failed" + str(sys.exc_info()[1]))

    # if we got an invalid planet size (for whatever reason),
    # just select one randomly from the global tuple based
    # only on the planet density setup option
    if planet_size == fo.planetSize.unknown:
        if random.randint(1, 10) <= planet_density:
            planet_size = random.choice(planet_sizes)
        else:
            planet_size = fo.planetSize.noWorld

    return planet_size

def pick_star_type(galaxy_age):
    """
    Picks and returns a star type based on universe tables distribution modifiers.
    """

    # try to pick a star type by making a series of "rolls" (1-100)
    # for each star type, and take the highest modified roll
    star_type = fo.starType.unknown
    try:
        max_roll = 0
        for candidate in star_types:
            roll = random.randint(1, 100) \
                + fo.universe_age_mod_to_star_type_dist(galaxy_age, candidate) \
                + fo.base_star_type_dist(candidate)
            if max_roll < roll:
                max_roll = roll
                star_type = candidate
    except:
        # in case of an error play save and set star type to invalid
        star_type = fo.starType.unknown
        util.report_error("Python pick_star_type: Pick star type failed\n" + sys.exc_info()[1])

    # if we got an invalid star type (for whatever reason),
    # just select one randomly from the global tuple
    if star_type == fo.starType.unknown:
        star_type = random.choice(star_types)
    return star_type

def calc_planet_size(star_type, orbit, planet_density, galaxy_shape):
    """
    Calculate planet size for a potential new planet based on planet density setup option, star type and orbit number.
    """

    # try to pick a planet size by making a series of "rolls" (1-100)
    # for each planet size, and take the highest modified roll
    planet_size = fo.planetSize.unknown
    try:
        max_roll = 0
        for candidate in planet_sizes_all:
            roll = random.randint(1, 100) \
                + tables.DENSITY_MOD_TO_PLANET_SIZE_DIST[planet_density][candidate] \
                + tables.STAR_TYPE_MOD_TO_PLANET_SIZE_DIST[star_type][candidate] \
                + tables.ORBIT_MOD_TO_PLANET_SIZE_DIST[orbit][candidate] \
                + tables.GALAXY_SHAPE_MOD_TO_PLANET_SIZE_DIST[galaxy_shape][candidate]
            if max_roll < roll:
                max_roll = roll
                planet_size = candidate
    except:
        # in case of an error play it safe and set planet size to invalid
        planet_size = fo.planetSize.unknown
        util.report_error("Python calc_planet_size: Pick planet size failed" + str(sys.exc_info()[1]))

    # if we got an invalid planet size (for whatever reason),
    # just select one randomly from the global tuple based
    # only on the planet density setup option
    if planet_size == fo.planetSize.unknown:
        if random.randint(1, 10) <= planet_density:
            planet_size = random.choice(planet_sizes)
        else:
            planet_size = fo.planetSize.noWorld

    return planet_size

def generate_a_planet(system, star_type, orbit, planet_density, galaxy_shape):
    """
    Place a planet in an orbit of a system. Return True on success
    """
    planet_size = calc_planet_size(star_type, orbit, planet_density, galaxy_shape)
    if planet_size not in planet_sizes:
        return False
    # ok, we want a planet, determine planet type and generate the planet
    planet_type = calc_planet_type(star_type, orbit, planet_size)
    if planet_type == fo.planetType.unknown:
        return False
    if fo.create_planet(planet_size, planet_type, system, orbit, "") == fo.invalid_object():
        # create planet failed, report an error
        util.report_error("Python generate_systems: create planet in system %d failed" % system)
        return False
    return True

def actually_save_file(package_name, orig_url, pkg, runtime_id):
    # `pkg` is a CKAN dataset
    success = False
    directory = app.config['DATA_STORAGE_DIR']

    print "Attempting to fetch package", package_name, "from", orig_url
    url = fixURL(orig_url)
    path = os.path.join(directory, package_name + '.xml')

    success = manage_download(path, url)

    with report_error("  Wrote metadata to DB", 
                      "  Couldn't write metadata to DB"):
        metadata_to_db(pkg, package_name, success, runtime_id)

    with report_error("  Package tested",
                      "  Couldn't test package %s" % package_name):
        dqruntests.start_testing(package_name)

def copy_package_fields(package, pkg):
    fields = [ 
        "activity_period-from", "activity_period-to",
        "activity_count", "country", "filetype", "verified" 
        ]
    for field in fields:
        with report_error(None, None):
            field_name = "package_" + field.replace("-", "_")
            setattr(package, field_name, pkg["extras"][field])

def generate_systems(pos_list, gsd):
    """
    Generates and populates star systems at all positions in specified list.
    """
    sys_list = []
    for position in pos_list:
        star_type = pick_star_type(gsd.age)
        system = fo.create_system(star_type, "", position[0], position[1])
        if system == fo.invalid_object():
            # create system failed, report an error and try to continue with next position
            util.report_error("Python generate_systems: create system at position (%f, %f) failed"
                              % (position[0], position[1]))
            continue
        sys_list.append(system)

        orbits = range(fo.sys_get_num_orbits(system))

        if not planets.can_have_planets(star_type, orbits, gsd.planet_density, gsd.shape):
            continue

        # Try to generate planets in each orbit.
        # If after each orbit is tried once there are no planets then
        # keep trying until a single planet is placed.
        # Except for black hole systems, which can be empty.

        at_least_one_planet = False
        random.shuffle(orbits)
        for orbit in orbits:
            if planets.generate_a_planet(system, star_type, orbit, gsd.planet_density, gsd.shape):
                at_least_one_planet = True

        if at_least_one_planet or can_have_no_planets(star_type):
            continue

        recursion_limit = 1000
        for _, orbit in product(range(recursion_limit), orbits):
            if planets.generate_a_planet(system, star_type, orbit, gsd.planet_density, gsd.shape):
                break
        else:
            # Intentionally non-modal.  Should be a warning.
            print >> sys.stderr, ("Python generate_systems: place planets in system %d at position (%.2f, %.2f) failed"
                                  % (system, position[0], position[1]))

    return sys_list

def copy_newer( src, dst ):
	if not( os.path.isfile(src) ):
		util.report_error('Error: src parameter of copy_newer is a file path.')
	target = None
	
	if os.path.isdir(dst):
		target = os.path.join( dst, os.path.basename(src) )
	else:
		target = dst
		
	if os.path.exists(target):
		if os.path.getmtime(target) < os.path.getmtime(src):
			os.remove(target)
		
	if not os.path.exists(target):
		shutil.copy2( src, target )
		return True
	else:
		return False

def generate_fields(systems):
    """
    Generates stationary fields in some randomly chosen empty no star systems.
    """
    # filter out all empty no star systems
    candidates = [s for s in systems if (fo.sys_get_star_type(s) == fo.starType.noStar) and (not fo.sys_get_planets(s))]
    # make sure we have at least one empty no star system, otherwise return without creating any fields
    if not candidates:
        print "...no empty no star systems found, no fields created"
        return
    # pick 10-20% of all empty no star systems to create stationary fields in them, but at least one
    accepted = sample(candidates, max(int(len(candidates) * uniform(0.1, 0.2)), 1))
    for system in accepted:
        # randomly pick a field type
        field_type = choice(["FLD_NEBULA_1", "FLD_NEBULA_2"])
        # and create the field
        if fo.create_field_in_system(field_type, uniform(40, 120), system) == fo.invalid_object():
            # create field failed, report an error
            report_error("Python generate_fields: create field %s in system %d failed" % (field_type, system))
    print "...fields created in %d systems out of %d empty no star systems" % (len(accepted), len(candidates))

def boost_version( boost_root ):
	"""
	Get boost version. 
	If it didn't include boost or unknown versioned boost,
	it will return None.
	"""
	version_hpp = os.path.join( boost_root, 'boost', 'version.hpp' )
	try:
		f = open(version_hpp)
	except:
		util.report_error('Cannot find boost/version.hpp. Please specify correct boost directory.')
	if f is None:
		return None
	version_lines = f.readlines()
	f.close()
	for line in version_lines:
		matched = re.match('\s*#\s*define\s+BOOST_VERSION\s+(?P<version>\d+)\s*', line )
		if matched and not matched.groupdict() is None:
			if 'version' in matched.groupdict():
				return version_object( int(matched.group('version')) )
	return None

def setup_package_group(package, pkg):
    with util.report_error(None, "Error saving package_group"):
        # there is a group, so use that group ID, or create one
        if 'groups' not in pkg:
            print "Warning: package %s has no groups key" % pkg['name']
            return

        group = pkg['organization']["name"]
        pg = models.PackageGroup.query.filter_by(name=group).first()
        if pg is None:
            pg = create_package_group(group, handle_country=False)
        package.package_group = pg.id

def compile_home_system_list(num_home_systems, systems):
    """
    Compiles a list with a requested number of home systems.
    """

    # if the list of systems to choose home systems from is empty, report an error and return empty list
    if not systems:
        util.report_error("Python generate_home_system_list: no systems to choose from")
        return []

    # calculate an initial minimal number of jumps that the home systems should be apart,
    # based on the total number of systems to choose from and the requested number of home systems
    min_jumps = max(int(float(len(systems)) / float(num_home_systems * 2)), 5)
    # try to find the home systems, decrease the min jumps until enough systems can be found, or the min jump distance
    # gets reduced to 0 (meaning we don't have enough systems to choose from at all)
    while min_jumps > 0:
        print "Trying to find", num_home_systems, "home systems that are at least", min_jumps, "jumps apart"
        # try to find home systems...
        home_systems = find_systems_with_min_jumps_between(num_home_systems, systems, min_jumps)
        # ...check if we got enough...
        if len(home_systems) >= num_home_systems:
            # ...yes, we got what we need, so let's break out of the loop
            break
        print "Home system min jump conflict: %d systems and %d empires, tried %d min jump and failed"\
              % (len(systems), num_home_systems, min_jumps)
        # ...no, decrease the min jump distance and try again
        min_jumps -= 1

    # check if the loop above delivered a list with enough home systems, or if it exited because the min jump distance
    # has been decreased to 0 without finding enough systems
    # in that case, our galaxy obviously is too crowded, report an error and return an empty list
    if len(home_systems) < num_home_systems:
        util.report_error("Python generate_home_system_list: requested %d homeworlds in a galaxy with %d systems"
                          % (num_home_systems, len(systems)))
        return []

    # make sure all our home systems have a "real" star (that is, a star that is not a neutron star, black hole,
    # or even no star at all) and at least one planet in it
    for home_system in home_systems:
        # if this home system has no "real" star, change star type to a randomly selected "real" star
        if fo.sys_get_star_type(home_system) not in starsystems.star_types_real:
            star_type = random.choice(starsystems.star_types_real)
            print "Home system", home_system, "has star type", fo.sys_get_star_type(home_system),\
                  ", changing that to", star_type
            fo.sys_set_star_type(home_system, star_type)

        # if this home system has no planets, create one in a random orbit
        # we take random values for type and size, as these will be set to suitable values later
        if not fo.sys_get_planets(home_system):
            print "Home system", home_system, "has no planets, adding one"
            planet = fo.create_planet(random.choice(planets.planet_sizes_real),
                                      random.choice(planets.planet_types_real),
                                      home_system, random.randint(0, fo.sys_get_num_orbits(home_system) - 1), "")
            # if we couldn't create the planet, report an error and return an empty list
            if planet == fo.invalid_object():
                util.report_error("Python generate_home_system_list: couldn't create planet in home system")
                return []

    return home_systems

    def stitch_clusters(self, p1, p2, stitches):
        """
        Stitch the clusters containing ''p1'' and ''p2''
        together with the positions in ''stitches''

        This assumes that the stitching is correctly formed.
        ''p1'' and ''p2'' are the closest positions between
        the clusters and the positions in ''stitches'' are only
        between ''p1'' and ''p2''

        After stitch_clusters there will be one fewer clusters in
        the clusterer, unless there were fewer than two clusters
        to begin with.

        If ''p1'' or ''p2'' are not in clusters then stitch_clusters
        just stitches two random clusters together.  This preserves
        the invariant that stitch_clusters always reduces the number
        of clusters.
        """
        len_dset1 = None
        len_dset2 = None
        for len_dset in self.clusters:
            if p1 in len_dset[1]:
                len_dset1 = len_dset
            if p2 in len_dset[1]:
                len_dset2 = len_dset

        if not len_dset1 or not len_dset2:
            util.report_error("p1 and p2 must be points in disjoint sets of positions")
            if len(self.clusters) < 2:
                return
            len_dset1, len_dset2 = list(self.clusters)[0:2]

        self.clusters.remove(len_dset1)
        self.clusters.remove(len_dset2)
        # Decorate the new cluster with its length to speed sorting
        new_set = len_dset1[1].union(len_dset2[1]).union(frozenset(stitches))
        self.clusters.add((len(new_set), new_set))

def generate_systems(pos_list, gsd):
    """
    Generates and populates star systems at all positions in specified list.
    """
    sys_list = []
    for position in pos_list:
        star_type = pick_star_type(gsd.age)
        system = fo.create_system(star_type, "", position.x, position.y)
        if system == fo.invalid_object():
            # create system failed, report an error and try to continue with next position
            util.report_error("Python generate_systems: create system at position (%f, %f) failed"
                              % (position.x, position.y))
            continue
        sys_list.append(system)
        for orbit in range(0, fo.sys_get_num_orbits(system) - 1):
            # check for each orbit if a planet shall be created by determining planet size
            planet_size = planets.calc_planet_size(star_type, orbit, gsd.planetDensity, gsd.shape)
            if planet_size in planets.planet_sizes:
                # ok, we want a planet, determine planet type and generate the planet
                planet_type = planets.calc_planet_type(star_type, orbit, planet_size)
                if fo.create_planet(planet_size, planet_type, system, orbit, "") == fo.invalid_object():
                    # create planet failed, report an error and try to continue with next orbit
                    util.report_error("Python generate_systems: create planet in system %d failed" % system)
    return sys_list

def copy_package_attributes(package, pkg):
    mapping = [
        ("package_ckan_id", "id"),
        ("package_name", "name"),
        ("package_title", "title"),
        ("package_license_id", "license_id"),
        ("package_license", "license"),
        ("package_metadata_created", "metadata_created"),
        ("package_metadata_modified", "metadata_modified"),
        ("package_revision_id", "revision_id")
        ]

    for attr, key in mapping:
        with report_error(None, None):
            setattr(package, attr, pkg[key])

def actually_save_manual_file(package_name):
    success = False
    directory = app.config['DATA_STORAGE_DIR']

    package = models.Package.query.filter_by(
        package_name=package_name).first()

    url = fixURL(package.source_url)
    path = os.path.join(directory, package_name + '.xml')

    success = manage_download(path, url)

    with db.session.begin():
        package.hash = 'retrieved'
        db.session.add(package)

    with report_error("  Package tested",
                      "  Couldn't test package %s" % package_name):
        dqruntests.start_testing(package_name)

def save_file(package_id, package_name, runtime_id, man_auto):
    if man_auto == 'auto':
        print "Trying to get auto package"
        registry = ckanclient.CkanClient(base_location=CKANurl)
        try:
            pkg = registry.package_entity_get(package_name)
            resources = pkg.get('resources', [])
        except Exception, e:
            print "Couldn't get URL from CKAN for package", package_name, e
            return

        print package_id, package_name, runtime_id
        if resources == []:
            return
        if len(resources) > 1:
            print "WARNING: multiple resources found; attempting to use first"

        url = resources[0]['url']
        print url

        with report_error("Saving %s" % url, None):
            actually_save_file(package_name, url, pkg, runtime_id)