Build has been canceled!

#244

Committed 22 Sep 2023 01:19PM UTC coverage: 89.857% (+0.06%) from 89.793%

Build # #244

Build Type

push

Committed by

renelink

Commit Message

Added longest common sequence implementation.

Run Details

28 of 28 new or added lines in 1 file covered. (100.0%)

7459 of 8301 relevant lines covered (89.86%)

0.9 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.86

/lis-commons-util/src/main/java/com/link_intersystems/util/diff/LongestCommonSequence.java

package com.link_intersystems.util.diff;

import com.link_intersystems.util.CharacterSequence;
import com.link_intersystems.util.ListSequence;
import com.link_intersystems.util.ReversedList;
import com.link_intersystems.util.Sequence;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

import static java.util.Objects.*;

public class LongestCommonSequence<E> implements Sequence<E> {

    public static Sequence<Character> of(CharSequence charSequence1, CharSequence charSequence2) {
        return new LongestCommonSequence<>(new CharacterSequence(charSequence1), new CharacterSequence(charSequence2));
    }

    private Sequence<E> sequence1;
    private Sequence<E> sequence2;

    private Sequence<E> lcs;

    public LongestCommonSequence(List<E> list1, List<E> list2) {
        this(new ListSequence<E>(list1), new ListSequence<E>(list2));
    }

    public LongestCommonSequence(Sequence<E> sequence1, Sequence<E> sequence2) {
        this.sequence1 = requireNonNull(sequence1);
        this.sequence2 = requireNonNull(sequence2);
    }

    protected Sequence<E> getLcs() {
        if (lcs == null) {
            int[][] table = new int[sequence1.length() + 1][sequence2.length() + 1];

            for (int row = 1; row <= sequence1.length(); row++) {
                for (int column = 1; column <= sequence2.length(); column++) {
                    if (Objects.equals(sequence1.elementAt(row - 1), sequence2.elementAt(column - 1))) {
                        table[row][column] = table[row - 1][column - 1] + 1;
                    } else {
                        table[row][column] = Math.max(table[row - 1][column], table[row][column - 1]);
                    }
                }
            }

            List<E> longestCommonSubsequence = new ArrayList<>();

            int row = sequence1.length(), column = sequence2.length();
            while (row > 0 && column > 0) {
                if (Objects.equals(sequence1.elementAt(row - 1), sequence2.elementAt(column - 1))) {

                    longestCommonSubsequence.add(sequence1.elementAt(row - 1));
                    row--;
                    column--;
                } else if (table[row - 1][column] > table[row][column - 1]) {
                    row--;
                } else {
                    column--;
                }
            }

            lcs = new ListSequence<>(new ReversedList<>(longestCommonSubsequence));
        }

        return lcs;
    }

    @Override
    public E elementAt(int index) {
        return getLcs().elementAt(index);
    }

    @Override
    public int length() {
        return getLcs().length();
    }


}

1	package com.link_intersystems.util.diff;
2
3	import com.link_intersystems.util.CharacterSequence;
4	import com.link_intersystems.util.ListSequence;
5	import com.link_intersystems.util.ReversedList;
6	import com.link_intersystems.util.Sequence;
7
8	import java.util.ArrayList;
9	import java.util.List;
10	import java.util.Objects;
11
12	import static java.util.Objects.*;
13
14	public class LongestCommonSequence<E> implements Sequence<E> {
15
16	public static Sequence<Character> of(CharSequence charSequence1, CharSequence charSequence2) {
17	return new LongestCommonSequence<>(new CharacterSequence(charSequence1), new CharacterSequence(charSequence2));	1✔
18	}
19
20	private Sequence<E> sequence1;
21	private Sequence<E> sequence2;
22
23	private Sequence<E> lcs;
24
25	public LongestCommonSequence(List<E> list1, List<E> list2) {
26	this(new ListSequence<E>(list1), new ListSequence<E>(list2));	×
27	}	×
28
29	public LongestCommonSequence(Sequence<E> sequence1, Sequence<E> sequence2) {	1✔
30	this.sequence1 = requireNonNull(sequence1);	1✔
31	this.sequence2 = requireNonNull(sequence2);	1✔
32	}	1✔
33
34	protected Sequence<E> getLcs() {
35	if (lcs == null) {	1✔
36	int[][] table = new int[sequence1.length() + 1][sequence2.length() + 1];	1✔
37
38	for (int row = 1; row <= sequence1.length(); row++) {	1✔
39	for (int column = 1; column <= sequence2.length(); column++) {	1✔
40	if (Objects.equals(sequence1.elementAt(row - 1), sequence2.elementAt(column - 1))) {	1✔
41	table[row][column] = table[row - 1][column - 1] + 1;	1✔
42	} else {
43	table[row][column] = Math.max(table[row - 1][column], table[row][column - 1]);	1✔
44	}
45	}
46	}
47
48	List<E> longestCommonSubsequence = new ArrayList<>();	1✔
49
50	int row = sequence1.length(), column = sequence2.length();	1✔
51	while (row > 0 && column > 0) {	1✔
52	if (Objects.equals(sequence1.elementAt(row - 1), sequence2.elementAt(column - 1))) {	1✔
53
54	longestCommonSubsequence.add(sequence1.elementAt(row - 1));	1✔
55	row--;	1✔
56	column--;	1✔
57	} else if (table[row - 1][column] > table[row][column - 1]) {	1✔
58	row--;	1✔
59	} else {
60	column--;	1✔
61	}
62	}
63
64	lcs = new ListSequence<>(new ReversedList<>(longestCommonSubsequence));	1✔
65	}
66
67	return lcs;	1✔
68	}
69
70	@Override
71	public E elementAt(int index) {
72	return getLcs().elementAt(index);	1✔
73	}
74
75	@Override
76	public int length() {
77	return getLcs().length();	1✔
78	}
79
80
81	}

link-intersystems / lis-commons / #244

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous