#243

Committed 22 Sep 2023 01:08PM UTC coverage: 89.793% (-0.3%) from 90.043%

Build # #243

Build Type

push

Committed by

Commit Message

Added longest common sequence implementation.

Run Details

74 of 74 new or added lines in 2 files covered. (100.0%)

7495 of 8347 relevant lines covered (89.79%)

0.9 hits per line

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

93.1

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

package com.link_intersystems.util.diff;

import com.link_intersystems.util.*;

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) {
            Table<Integer> table = createLCSTable();

            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))) {
                        // add 1 in the cell of the previous row and column and fill the current cell with it
                        table.setCell(row, column, table.getCell(row - 1, column - 1) + 1);
                    } else {
                        //find the maximum value from the cell of the previous row and current column and the cell of the current row and previous column
                        table.setCell(row, column, Math.max(table.getCell(row - 1, column), table.getCell(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.getCell(row - 1, column) > table.getCell(row, column - 1))
                    row--;
                else
                    column--;
            }

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

        return lcs;
    }

    protected ArrayTable<Integer> createLCSTable() {
        return new ArrayTable<>(Integer.class, 0);
    }


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

link-intersystems / lis-commons / #243

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