На Java проверить элементы списка на нарушение естественного порядка сортировки (Natural Sort Order)

Рейтинг: 2Ответов: 2Опубликовано: 27.06.2023

Я пишу метод, который проверяет порядок элементов входного списка и в случае, если элемент не нарушает естественный порядок сортировки (т.е. больше или равен предыдущему), добавляет в другой список.

Данные во входном списке могут быть или Integer, или String (предварительно я отсеиваю из списка строки, которые не соответствуют указанному типу данных, так что в списке лишь строки, которые можно привести к Integer или те, что нельзя). Я храню данные в списке, параметризированном типом String, потому что любой тип можно привести к строке. Вот что у меня получается:

    private static void checkOrder(List<String> firstList) {
        // предыдущий элемент списка
        String previous = null;

        if (getDataType() == DataType.INTEGER) { // режим работы с целыми числами
            for (String i: firstList) {
                if (previous == null ||
                        (Integer.parseInt(i) - Integer.parseInt(previous) >= 0)) {
                    secondList.add(i); // List<String> secondList = new ArrayList<>();
                    previous = i;
                }
            }
        }
        else { // DataType.STRING
            for (String i: firstList) {
                if (previous == null || i.compareTo(previous) >= 0) {
                    secondList.add(i);
                    previous = i;
                }
            }
        }
    }

Увы, но это работает не совсем корректно. Так, если работаем с данными типа String и в firstList данные: [img4, img30, abc, z2, z10] , то в secondList окажется: [img4, z2], а не [img4, img30, z2, z10]

Кроме того, что не получается "починить" метод, хотелось бы написать его более красиво и толково. В идеале мне хотелось бы создать единую проверку, которой было бы все равно, Integer в firstList или String.

Вот что я так же безуспешно пробовал по совету интырнета:

     private static <T extends Comparable<? super T>> void checkOrder(List<T> firstList) {
        T previous = null;
        
            for (T i: firstList) {
                if (previous == null || i.compareTo(previous) >= 0) {
                    allValidData.add((String) element);
                    previousElement = element;
                }
            }
    }

Но это некорректно работает уже не только с данными типа String, но и с данными типа Integer.

Буду благодарен, если кто-нибудь любезно наставит на путь истинный.

java сортировка
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Вариант реализации с разбиением каждой строки в исходном списке на подстроки, содержащие только цифры и не-цифры соответственно и соответствующим компаратором.

  • getSorted -- отфильтровывает значения в "натуральном порядке" (практически аналог метода checkOrder)
  • List<String> parse(String s) -- метод для преобразования строки в список подстрок (с использованием Stream API)
  • Кастомный компаратор строк MyComparator, который фактически сравнивает списки подстрок, проверяя, является ли i-ая подстрока числом или строкой.
import java.util.*;
import java.util.stream.*;
import java.util.regex.*;

public class MyClass {
    
    public static List<String> getSorted(List<String> data) {
        List<String> result = new ArrayList<>();
        
        if (!data.isEmpty()) {
            String prev = null;
            
            Comparator<String> cmp = new MyComparator();
            
            for (String it : data) {
                if (prev == null || cmp.compare(prev, it) <= 0) {
                    result.add(it);
                }
                prev = it;
            }
        }
        
        return result;
    }
    
    private static final Pattern PAT = Pattern.compile("(\\D*)(\\d*)"); 
    private static List<String> parse(String s) {
        return PAT.matcher(s)
            .results()  // Stream<MatchResult>
            .filter(mr -> !mr.group(0).isEmpty()) // игнорировать пустые совпадения
            .flatMap(mr -> Stream.of(mr.group(1), mr.group(2))) // Stream<String>
            .collect(Collectors.toList()); // получить список-результат
    }    
    
    private static class MyComparator implements Comparator<String> {
        Map<String, List<String>> map = new HashMap<>();
        
        @Override
        public int compare(String s1, String s2) {
            List<String> lst1 = map.computeIfAbsent(s1, MyClass::parse);
            List<String> lst2 = map.computeIfAbsent(s2, MyClass::parse);
            
            for (int i = 0, n = Math.min(lst1.size(), lst2.size()); i < n; i++) {
                String p1 = lst1.get(i);
                String p2 = lst2.get(i);
                
                int r;
                if (p1.matches("\\d+") && p2.matches("\\d+")) {
                    r = Long.valueOf(p1).compareTo(Long.valueOf(p2));
                } else {
                    r = p1.compareTo(p2);
                }
                if (r != 0) return r;
            }
            return Integer.compare(lst1.size(), lst2.size());
        }
    }
}

Тест:

System.out.println(getSorted(Arrays.asList("img4", "img30", "abc", "z2", "z10")));

Результат (отфильтровано значение "abc"):

[img4, img30, z2, z10]

Соответственно, такой компаратор можно использовать для обычной сортировки входного списка строк в "натуральном порядке", чтобы не было потерь данных при фильтрации.

(Обновление) Тест:

List<String> list = Arrays.asList("#1", "1", ":1", "a1", "a#1", "a:1");
MyComparator c = new MyComparator();
list.sort(c);
System.out.println(list);
System.out.println(c.map);

[1, #1, :1, a1, a#1, a:1]
{a1=[a, 1], 1=[, 1], :1=[:, 1], a:1=[a:, 1], a#1=[a#, 1], #1=[#, 1]}
▲ 2

Вместо сравнения строк, будем сравнивать последовательности пар специального вида. Все не-цифры в строке преобразуются в пары (<символ>, 0), а все группы цифр в пары ("0", <число>).

Каждая строка отображается в последовательность пар. Две последовательности сравниваются лексикографически.

В этом примере разница на последней паре:

"img2"  -> ("i", 0), ("m", 0), ("g", 0), ("0",  2)
"img10" -> ("i", 0), ("m", 0), ("g", 0), ("0", 10)

Item - класс пары (<символ>, <число>). Элементы упорядочены по символу. Если символы равны, то по числу.

Items превращает строку в последовательность элементов Item.

nat - компаратор для строк. Числа внутри строк сравниваются "естественным" образом.

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Temp {

    private static class Item implements Comparable<Item> {
        private final String s;
        private final long v;
        public Item(String s, long v) {
            this.s = s;
            this.v = v;
        }

        @Override
        public int compareTo(Item o) {
            int c = s.compareTo(o.s);
            if (c != 0) {
                return c;
            }
            return Long.compare(v, o.v);
        }
    }

    private static class Items {
        private static final Pattern p = Pattern.compile("[1-9][0-9]*|.");
        private final Matcher m;

        public Items(String s) {
            m = p.matcher(s);
        }

        public Item next() {
            if (m.find()) {
                String s = m.group();
                if (Character.isDigit(s.charAt(0))) {
                    return new Item("0", Long.parseLong(s));
                }
                return new Item(s, 0);
            }
            return null;
        }
    }

    private static final Comparator<String> nat = new Comparator<String>() {
        @Override
        public int compare(String s1, String s2) {
            Items items1 = new Items(s1);
            Items items2 = new Items(s2);
            Item i1 = items1.next();
            Item i2 = items2.next();
            while (i1 != null || i2 != null) {
                if (i1 == null) { return -1; }
                if (i2 == null) { return  1; }
                int c = i1.compareTo(i2);
                if (c != 0) {
                    return c;
                }
                i1 = items1.next();
                i2 = items2.next();
            }
            return 0;
        }
    };

    private static void checkOrder(List<String> list) {
        String prev = null;
        for (String s : list) {
            if (prev == null || nat.compare(prev, s) <= 0) {
                System.out.println(s);
            }
            prev = s;
        }
    }

    public static void main(String... args) {
        checkOrder(Arrays.asList(args));
    }
}

$ javac Temp.java && java Temp img4 img30 abc z2 z10
img4
img30
z2
z10

P.S. Посмотрите ещё этот вопрос Проблема с сортировкой списка.