<commit_before>"""Search implementation using a wifi database."""

from collections import defaultdict, namedtuple
from operator import attrgetter

import numpy
from sqlalchemy.orm import load_only
from sqlalchemy.sql import or_

from ichnaea.api.locate.constants import (
    DataSource,
    MAX_WIFI_CLUSTER_METERS,
    MIN_WIFIS_IN_CLUSTER,
    MAX_WIFIS_IN_CLUSTER,
    WIFI_MAX_ACCURACY,
    WIFI_MIN_ACCURACY,
)
from ichnaea.api.locate.result import Position
from ichnaea.api.locate.source import PositionSource
from ichnaea.constants import (
    PERMANENT_BLOCKLIST_THRESHOLD,
    TEMPORARY_BLOCKLIST_DURATION,
)
from ichnaea.geocalc import (
    aggregate_position,
    distance,
)
from ichnaea.models import WifiShard
from ichnaea import util

Network = namedtuple('Network', 'mac lat lon radius signal')


def cluster_elements(items, distance_fn, threshold):
    """
    Generic pairwise clustering routine.

    :param items: A list of elements to cluster.
    :param distance_fn: A pairwise distance function over elements.
    :param threshold: A numeric threshold for clustering;
                      clusters P, Q will be joined if
                      distance_fn(a,b) <= threshold,
                      for any a in P, b in Q.

    :returns: A list of lists of elements, each sub-list being a cluster.
    """
    distance_matrix = [[distance_fn(a, b) for a in items] for b in items]
    clusters = [[i] for i in range(len(items))]

    def cluster_distance(a, b):
        return min([distance_matrix[i][j] for i in a for j in b])

    merged_one = True
    while merged_one:
        merged_one = False
        for i in range(len(clusters)):
            if merged_one:
                break
            for j in range(len(clusters)):
                if merged_one:
                    break
                if i == j:
                    continue
                a = clusters[i]
                b = clusters[j]
                if cluster_distance(a, b) <= threshold:
                    clusters.pop(j)
                    a.extend(b)
                    merged_one = True

    return [[items[i] for i in c] for c in clusters]


def get_clusters(wifis, lookups):
    """
    Given a list of wifi models and wifi lookups, return
    a list of clusters of nearby wifi networks.
    """

    # Create a dict of WiFi macs mapped to their signal strength.
    # Estimate signal strength at -100 dBm if none is provided,
    # which is worse than the 99th percentile of wifi dBms we
    # see in practice (-98).
    wifi_signals = {}
    for lookup in lookups:
        wifi_signals[lookup.mac] = lookup.signal or -100

    wifi_networks = [
        Network(w.mac, w.lat, w.lon, w.radius, wifi_signals[w.mac])
        for w in wifis]

    # Sort networks by signal strengths in query.
    wifi_networks.sort(key=attrgetter('signal'), reverse=True)

    def wifi_distance(one, two):
        return distance(one.lat, one.lon, two.lat, two.lon)

    clusters = cluster_elements(
        wifi_networks, wifi_distance, MAX_WIFI_CLUSTER_METERS)

    # Only consider clusters that have at least 2 found networks
    # inside them. Otherwise someone could use a combination of
    # one real network and one fake and therefor not found network to
    # get the position of the real network.
    return [c for c in clusters if len(c) >= MIN_WIFIS_IN_CLUSTER]


def pick_best_cluster(clusters):<commit_msg>Simplify cluster_elements to only deal with WiFi networks.<commit_after>"""Search implementation using a wifi database."""

from collections import defaultdict, namedtuple
from operator import attrgetter

import numpy
from sqlalchemy.orm import load_only
from sqlalchemy.sql import or_

from ichnaea.api.locate.constants import (
    DataSource,
    MAX_WIFI_CLUSTER_METERS,
    MIN_WIFIS_IN_CLUSTER,
    MAX_WIFIS_IN_CLUSTER,
    WIFI_MAX_ACCURACY,
    WIFI_MIN_ACCURACY,
)
from ichnaea.api.locate.result import Position
from ichnaea.api.locate.source import PositionSource
from ichnaea.constants import (
    PERMANENT_BLOCKLIST_THRESHOLD,
    TEMPORARY_BLOCKLIST_DURATION,
)
from ichnaea.geocalc import (
    aggregate_position,
    distance,
)
from ichnaea.models import WifiShard
from ichnaea import util

Network = namedtuple('Network', 'mac lat lon radius signal')


def cluster_wifis(wifis):
    distance_matrix = [
        [distance(a.lat, a.lon, b.lat, b.lon)
         for a in wifis] for b in wifis]
    clusters = [[i] for i in range(len(wifis))]

    def cluster_distance(a, b):
        return min([distance_matrix[i][j] for i in a for j in b])

    merged_one = True
    while merged_one:
        merged_one = False
        for i in range(len(clusters)):
            if merged_one:
                break
            for j in range(len(clusters)):
                if merged_one:
                    break
                if i == j:
                    continue
                a = clusters[i]
                b = clusters[j]
                if cluster_distance(a, b) <= MAX_WIFI_CLUSTER_METERS:
                    clusters.pop(j)
                    a.extend(b)
                    merged_one = True

    return [[wifis[i] for i in c] for c in clusters]


def get_clusters(wifis, lookups):
    """
    Given a list of wifi models and wifi lookups, return
    a list of clusters of nearby wifi networks.
    """

    # Create a dict of WiFi macs mapped to their signal strength.
    # Estimate signal strength at -100 dBm if none is provided,
    # which is worse than the 99th percentile of wifi dBms we
    # see in practice (-98).
    wifi_signals = {}
    for lookup in lookups:
        wifi_signals[lookup.mac] = lookup.signal or -100

    wifi_networks = [
        Network(w.mac, w.lat, w.lon, w.radius, wifi_signals[w.mac])
        for w in wifis]

    # Sort networks by signal strengths in query.
    wifi_networks.sort(key=attrgetter('signal'), reverse=True)

    clusters = cluster_wifis(wifi_networks)

    # Only consider clusters that have at least 2 found networks
    # inside them. Otherwise someone could use a combination of
    # one real network and one fake and therefor not found network to
    # get the position of the real network.
    return [c for c in clusters if len(c) >= MIN_WIFIS_IN_CLUSTER]


def pick_best_cluster(clusters):
{'fraction_non_alphanumeric': 0.07322508755173511, 'fraction_numerical': 0.0035020694046482012, 'mean_word_length': 2.5297752808988765, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '486505', 'n_tokens_mistral': 1975, 'n_tokens_neox': 1885, 'n_words': 639}