<commit_before>/*
 * Copyright 2015 MiLaboratory.com
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.milaboratory.core.alignment.kaligner2;

import com.milaboratory.test.TestUtil;
import gnu.trove.set.hash.TIntHashSet;
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.random.Well19937c;
import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created by dbolotin on 29/09/15.
 */
public class CrossTest {
    @Test
    public void test1() throws Exception {
        Line l1 = new Line(10, 20, 100), l2 = new Line(20, 15, 200);
        Assert.assertTrue(l1.crosses(l2));
    }

    @Test
    public void testCHeckAlgorithm() throws Exception {
        RandomGenerator rg = new Well19937c();

        final UntanglingAlgorithm algorithm = SUBSUM_ADD_ALGORITHM;

        int K = 10000;
        System.out.println("Burning JVM...");
        System.out.print("BF: ");
        go(BRUTE_FORCE, 5, K, rg);
        System.out.print("ALG: ");
        go(algorithm, 5, K, rg);
        System.out.println();
        System.out.println("Run.");
        System.out.println();
        for (int N = 2; N < 14; N++) {
            System.out.print("BF: ");
            go(BRUTE_FORCE, N, K, rg);
            System.out.print("ALG: ");
            go(algorithm, N, K, rg);
            System.out.println();
        }
    }

    public static void go(UntanglingAlgorithm algorithm, int N, int K, RandomGenerator rg) {
        long start, time;
        long meanTime = 0, maxTime = 0, errors = 0, fails = 0;
        for (int z = 0; z < K; z++) {
            Line[] lines = randomData(N, rg);

            Line[] correctAnswer = bruteForce(lines);
            start = System.nanoTime();
            Line[] algorithmResult = algorithm.calculate(lines);

            Assert.assertFalse(hasCrosses(algorithmResult));

            time = System.nanoTime() - start;
            maxTime = Math.max(maxTime, time);
            meanTime += time;
            Arrays.sort(correctAnswer);
            Arrays.sort(algorithmResult);
            if (!Arrays.equals(correctAnswer, algorithmResult))
                errors++;
        }
        meanTime /= K;
        System.out.println("N=" + N + "  Errors=" + TestUtil.DECIMAL_FORMAT.format(100.0 * errors / K) + "%  Failed=" + TestUtil.DECIMAL_FORMAT.format(100.0 * fails / K) + " Mean=" + TestUtil.time(meanTime) + "   Max=" + TestUtil.time(maxTime));
    }

    public static Line[] randomData(int N, RandomGenerator rg) {
        TIntHashSet generated = new TIntHashSet();
        Line[] lines = new Line[N];

        int[] limits = {300, 300, 700};
        for (int i = 0; i < N; i++) {
            int numbers[] = new int[3];
            for (int j = 0; j < 3; j++)
                while (!generated.add(numbers[j] = rg.nextInt(limits[j]))) ;
            lines[i] = new Line(numbers[0], numbers[1], numbers[2]);
        }
        return lines;
    }

    @Test
    public void testRandom() throws Exception {
        RandomGenerator rg = new Well19937c();

        int N = 10;

        for (int z = 0; z < 100000; z++) {

            TIntHashSet generated = new TIntHashSet();
            Line[] lines = new Line[N];

            int[] limits = {300, 300, 700};
            for (int i = 0; i < N; i++) {
                int numbers[] = new int[3];
                for (int j = 0; j < 3; j++)
                    while (!generated.add(numbers[j] = rg.nextInt(limits[j]))) ;
                lines[i] = new Line(numbers[0], numbers[1], numbers[2]);
            }

            Arrays.sort(lines);

            //for (Line l : lines)
            //    System.out.println(l);
            //
            //System.out.println("-----");

            long start = System.nanoTime();
            Line[] answer = bruteForce(lines);
            System.out.println(TestUtil.time(System.nanoTime() - start));
            //for (Line bestLine : answer) {
            //    System.out.println(bestLine);
            //}
        }
    }

    interface UntanglingAlgorithm {
        Line[] calculate(Line[] lines);
    }

    public static final UntanglingAlgorithm SUBSUM_ADD_ALGORITHM = new UntanglingAlgorithm() {
        @Override
        public Line[] calculate(Line[] lines) {
            Arrays.sort(lines);
            LineWrapper1[] wrappers = new LineWrapper1[lines.length];

            for (int i = 0; i < lines.length; i++)
                wrappers[i] = new LineWrapper1(lines[i]);

            for (int i = 0; i < lines.length; i++)
                wrappers[i].score = lines[i].score;

            for (int i = 0; i < lines.length; i++)
                for (int j = i + 1; j < lines.length; j++) {
                    if (lines[i].crosses(lines[j])) {
                        wrappers[i].score -= lines[j].score / 2;
                        wrappers[j].score -= lines[i].score / 2;
                    }
                }

            Arrays.sort(wrappers);

            List<Line> result = new ArrayList<>(lines.length);

            OUTER:
            for (int i = 0; i < wrappers.length; i++) {
                for (Line fromResult : result) {
                    if (fromResult.crosses(wrappers[i].line))
                        continue OUTER;
                }
                result.add(wrappers[i].line);
            }

            return result.toArray(new Line[result.size()]);
        }
    };

    public static final UntanglingAlgorithm SUBSUM_REMOVE_ALGORITHM = new UntanglingAlgorithm() {
        @Override
        public Line[] calculate(Line[] lines) {
            Arrays.sort(lines);
            List<LineWrapper1> wrappers = new ArrayList<>();

            for (int i = 0; i < lines.length; i++)
                wrappers.add(new LineWrapper1(lines[i]));

            OUTER:
            while (true) {
                for (int i = 0; i < wrappers.size(); i++)
                    wrappers.get(i).score = wrappers.get(i).line.score;

                for (int i = 0; i < wrappers.size(); i++)
                    for (int j = i + 1; j < wrappers.size(); j++) {
                        if (wrappers.get(i).line.crosses(wrappers.get(j).line)) {
                            wrappers.get(i).score -= wrappers.get(j).line.score / 2;
                            wrappers.get(j).score -= wrappers.get(i).line.score / 2;
                        }
                    }

                Collections.sort(wrappers);
<commit_msg>NoDiv2.<commit_after>/*
 * Copyright 2015 MiLaboratory.com
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.milaboratory.core.alignment.kaligner2;

import com.milaboratory.test.TestUtil;
import gnu.trove.set.hash.TIntHashSet;
import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.random.Well19937c;
import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created by dbolotin on 29/09/15.
 */
public class CrossTest {
    @Test
    public void test1() throws Exception {
        Line l1 = new Line(10, 20, 100), l2 = new Line(20, 15, 200);
        Assert.assertTrue(l1.crosses(l2));
    }

    @Test
    public void testCHeckAlgorithm() throws Exception {
        RandomGenerator rg = new Well19937c();

        final UntanglingAlgorithm algorithm = SUBSUM_ADD_ALGORITHM;

        int K = 10000;
        System.out.println("Burning JVM...");
        System.out.print("BF: ");
        go(BRUTE_FORCE, 5, K, rg);
        System.out.print("ALG: ");
        go(algorithm, 5, K, rg);
        System.out.println();
        System.out.println("Run.");
        System.out.println();
        for (int N = 2; N < 14; N++) {
            System.out.print("BF: ");
            go(BRUTE_FORCE, N, K, rg);
            System.out.print("ALG: ");
            go(algorithm, N, K, rg);
            System.out.println();
        }
    }

    public static void go(UntanglingAlgorithm algorithm, int N, int K, RandomGenerator rg) {
        long start, time;
        long meanTime = 0, maxTime = 0, errors = 0, fails = 0;
        for (int z = 0; z < K; z++) {
            Line[] lines = randomData(N, rg);

            Line[] correctAnswer = bruteForce(lines);
            start = System.nanoTime();
            Line[] algorithmResult = algorithm.calculate(lines);

            Assert.assertFalse(hasCrosses(algorithmResult));

            time = System.nanoTime() - start;
            maxTime = Math.max(maxTime, time);
            meanTime += time;
            Arrays.sort(correctAnswer);
            Arrays.sort(algorithmResult);
            if (!Arrays.equals(correctAnswer, algorithmResult))
                errors++;
        }
        meanTime /= K;
        System.out.println("N=" + N + "  Errors=" + TestUtil.DECIMAL_FORMAT.format(100.0 * errors / K) + "%  Failed=" + TestUtil.DECIMAL_FORMAT.format(100.0 * fails / K) + " Mean=" + TestUtil.time(meanTime) + "   Max=" + TestUtil.time(maxTime));
    }

    public static Line[] randomData(int N, RandomGenerator rg) {
        TIntHashSet generated = new TIntHashSet();
        Line[] lines = new Line[N];

        int[] limits = {300, 300, 700};
        for (int i = 0; i < N; i++) {
            int numbers[] = new int[3];
            for (int j = 0; j < 3; j++)
                while (!generated.add(numbers[j] = rg.nextInt(limits[j]))) ;
            lines[i] = new Line(numbers[0], numbers[1], numbers[2]);
        }
        return lines;
    }

    @Test
    public void testRandom() throws Exception {
        RandomGenerator rg = new Well19937c();

        int N = 10;

        for (int z = 0; z < 100000; z++) {

            TIntHashSet generated = new TIntHashSet();
            Line[] lines = new Line[N];

            int[] limits = {300, 300, 700};
            for (int i = 0; i < N; i++) {
                int numbers[] = new int[3];
                for (int j = 0; j < 3; j++)
                    while (!generated.add(numbers[j] = rg.nextInt(limits[j]))) ;
                lines[i] = new Line(numbers[0], numbers[1], numbers[2]);
            }

            Arrays.sort(lines);

            //for (Line l : lines)
            //    System.out.println(l);
            //
            //System.out.println("-----");

            long start = System.nanoTime();
            Line[] answer = bruteForce(lines);
            System.out.println(TestUtil.time(System.nanoTime() - start));
            //for (Line bestLine : answer) {
            //    System.out.println(bestLine);
            //}
        }
    }

    interface UntanglingAlgorithm {
        Line[] calculate(Line[] lines);
    }

    public static final UntanglingAlgorithm SUBSUM_ADD_ALGORITHM = new UntanglingAlgorithm() {
        @Override
        public Line[] calculate(Line[] lines) {
            Arrays.sort(lines);
            LineWrapper1[] wrappers = new LineWrapper1[lines.length];

            for (int i = 0; i < lines.length; i++)
                wrappers[i] = new LineWrapper1(lines[i]);

            for (int i = 0; i < lines.length; i++)
                wrappers[i].score = lines[i].score;

            for (int i = 0; i < lines.length; i++)
                for (int j = i + 1; j < lines.length; j++) {
                    if (lines[i].crosses(lines[j])) {
                        wrappers[i].score -= lines[j].score;
                        wrappers[j].score -= lines[i].score;
                    }
                }

            Arrays.sort(wrappers);

            List<Line> result = new ArrayList<>(lines.length);

            OUTER:
            for (int i = 0; i < wrappers.length; i++) {
                for (Line fromResult : result) {
                    if (fromResult.crosses(wrappers[i].line))
                        continue OUTER;
                }
                result.add(wrappers[i].line);
            }

            return result.toArray(new Line[result.size()]);
        }
    };

    public static final UntanglingAlgorithm SUBSUM_REMOVE_ALGORITHM = new UntanglingAlgorithm() {
        @Override
        public Line[] calculate(Line[] lines) {
            Arrays.sort(lines);
            List<LineWrapper1> wrappers = new ArrayList<>();

            for (int i = 0; i < lines.length; i++)
                wrappers.add(new LineWrapper1(lines[i]));

            OUTER:
            while (true) {
                for (int i = 0; i < wrappers.size(); i++)
                    wrappers.get(i).score = wrappers.get(i).line.score;

                for (int i = 0; i < wrappers.size(); i++)
                    for (int j = i + 1; j < wrappers.size(); j++) {
                        if (wrappers.get(i).line.crosses(wrappers.get(j).line)) {
                            wrappers.get(i).score -= wrappers.get(j).line.score;
                            wrappers.get(j).score -= wrappers.get(i).line.score;
                        }
                    }

                Collections.sort(wrappers);

{'fraction_non_alphanumeric': 0.13304323013268654, 'fraction_numerical': 0.018761592238550433, 'mean_word_length': 1.7937425269031486, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '1374408', 'n_tokens_mistral': 4395, 'n_tokens_neox': 4062, 'n_words': 1058}