01-Generics-Iterator-Comparator

wildcard [ˈwaɪldˌkɑrd] n. 未知数;未知因素

1. 算法

1. 可以解决具体问题：eg：1+2+3+4+...+99+100
   • 解题流程 => 算法
2. 有设计解决的具体的流程
   • 算法1：1+2=3, 3+3=6, 6+4=10.....加到100 => 5050
   • 算法2：(1 + 100) * 50 = 101 * 50 = 5050 => 高斯算法
3. 有评价这个算法的具体指标 => 时间复杂度、空间复杂度（从数学角度考虑）

2. 数据结构

1. 计算机在缓存，内存，硬盘，如何存储、组织、管理数据的。重点在结构，按照什么结构来组织管理数据
2. 分类
   1. 物理结构（真实结构 ）：
      • 紧密结构（顺序结构）=> 数组
      • 跳转结构（链式结构）=> 链表
   2. 逻辑结构（思想上结构）：
      • 线性表（数组、链表）、栈、队列、树、图

3. 数组

1. 特点

1. 长度固定
   • int[] arr = new int[6];
2. 类型固定
   • int[] arr, String[] s, double[] d

2. 缺点

1. 长度不可以更改
2. 删除、增加元素效率低
3. 数组实际元素数量没有办法获取
4. 无序的，不可重复数据，数组不能满足要求

• 正因为上面的缺点，引入了一个新的存储数据的结构 => 集合
• 容器 | 集合：对多个数据进行存储操作
• PS：这里的存储指的是内存层面的存储，而不是持久化存储（.txt、.avi、.jpg、数据库）

4. 线性表

• n个类型相同数据元素的有限序列。通常记作a0, a1, ... an-1
• 逻辑结构如图所示：

1. 特点

1. 相同数据类型
   • 意味着在内存中存储时，每个元素会占用相同大小的内存空间，便于后续的查询定位
2. 序列（顺序性）
   • 相邻数据元素之间存在顺序关系
3. 有限

2. 数组

• 紧密结构

1. 优点：寻址快 => 查询元素效率高（首元素地址 + 元素长度 * n）
2. 缺点：删除、增加元素效率低

3. 链表

• 跳转结构

1. 优点：删除、插入元素效率高
2. 缺点：查询元素效率低
3. 分类
   1. 单向链表
   2. 双向链表
   3. 循环链表

5. Generics

1. JDK1.5之后，使用泛型来确定容器中元素类型
2. 泛型必须为引用类型

1. Generics_Class

1. 不指定泛型，相当于<Object>
2. 指定泛型<Integer>
3. 父类指定泛型，子类为普通类
4. 父类不指定泛型，子类必为泛型类
5. 范型类可以多个泛型
6. 构造方法不能有泛型
7. static不能泛型
8. 泛型不能new

/**
 * 泛型类
 * 1. <E>相当于一个占位
 * 2. 必须引用类型，不是基本类型
 */
class Generics<E> {
    int age;
    String name;
    E sex;

    public void a(E n) {
    }

    public void b(E[] m) {
    }
}

/**
 * 泛型类<E>
 */
public class T1_Generics {

    @Test
    public void T1_threshold() {
        // 1. 不指定泛型，相当于<Object>
        Generics g1 = new Generics<>();
        g1.a("abc");
        g1.a(17);
        g1.a(9.8);
        g1.b(new String[]{"a", "b", "c"});

        // 2. 指定泛型。编译时对类型检查
        // JDK1.7后，可直接<>。钻石运算符
        Generics<String> g2 = new Generics<>();
        g2.sex = "男";
        g2.a("abc");
        g2.b(new String[]{"a", "b", "c"});

        // 3. 父类指定泛型，子类为普通类
        SubGenerics sgt = new SubGenerics();
        sgt.a(19);

        // 4. 父类不指定泛型，子类必为泛型类
        SubGenericsX<String> s = new SubGenericsX<>();
        s.a("abc");
        s.sex = "女";
    }
}

// 3. 父类指定泛型，子类为普通类
class SubGenerics extends Generics<Integer> {
}

// 4. 父类不指定泛型，子类必为泛型类
class SubGenericsX<E> extends Generics<E> {
}

// 5. 范型类可以多个泛型
class MultiGenerics<A, B, C> {

    // 6. 构造方法不能有泛型
    public MultiGenerics/*<A, B, C>*/() {
    }

    // 7. static不能泛型
    public /*static*/ void ooxx(A a) {

        // 8. 泛型不能new
        // A a1 = new A();
        // A[] as = new A[10];

        A o = (A) new Object();
        A[] as = (A[]) new Object[10];
    }
}

2. Generics_Method

• 泛型方法
  1. 返回值前加<X>
  2. <X>通过形参类型确定。是否为泛型类，泛型类的泛型无关
  3. 泛型方法，可以为static方法

/**
 * 泛型方法
 * 1. 返回值前加<X>
 * 2. <X>通过形参类型确定。是否为泛型类，泛型类的泛型无关
 * 3. 泛型方法，可以为static方法
 * 4. redisTemplateObj.<String, Integer>opsForHash().get(key, limitEnum.getUrl());
 */
class Generics_method<E> {

    // 不是泛型方法
    public void A(E e) {
    }

    // 1. 泛型方法
    public <T> T B(T t) {
        return t;
    }

    // 2. 泛型方法，可以为static方法
    public static <X> X b(X x) {
        return x;
    }

    public static void main(String[] args) {
        Generics_method<String> gm = new Generics_method<>();
        gm.A("String");

        // 泛型方法
        Integer t = gm.B(1);
        Boolean x = gm.B(true);
    }
}

3. wildcard

1. ?通配符，相当于<>父类
2. 泛型继承关系，集合并列关系。底层都是Object[]存数据

class wildcard {
    public void m1() {
        Object o = new Object();
        String str = new String();
        o = str;

        Object[] objs = new Object[10];
        String[] strs = new String[10];
        objs = strs;

        // 泛型继承关系，集合并列关系。底层都是Object[]存数据
        ArrayList<Object> objAL = new ArrayList<>();
        ArrayList<String> strAL = new ArrayList<>();
        ArrayList<Integer> intAL = new ArrayList<>();
        // objAL = strAL;

        // ? 通配符，相当于<>父类
        List<?> list = null;
        list = objAL;
        list = strAL;
        list = intAL;

      	// error(strAL);

        wildcard(objAL);
        wildcard(strAL);
        wildcard(intAL);
    }

    public void error(List<Object> list) {
    }

    public void wildcard(List<?> list) {
        // 遍历
        for (Object o : list) {
            System.out.println(o);
        }

        // 写入，错误
        // list.add(111);

        // 读取
        Object o = list.get(1);
    }
}

4. limit

1. 泛型上限（upper_limit）： List<? extends Person>
2. 泛型下限（lower_limit）： List<? super Person>

class limit {
    static class Person {
    }

    static class Student extends Person {
    }

    public static void main(String[] args) {
        // a, b, c三个集合是并列的关系
        List<Object> a = new ArrayList<>();
        List<Person> b = new ArrayList<>();
        List<Student> c = new ArrayList<>();

        // 1. upper_limit（泛型上限）
        List<? extends Person> list1 = null;
        // list1 = a; 报错
        list1 = b;
        list1 = c;

        // 2. lower_limit（泛型下限）
        List<? super Person> list2 = null;
        list2 = a;
        list2 = b;
        // list2 = c; 报错
    }
}

6. Iterator

• 集合内部类，增加cursor, lastRet属性。实现集合遍历

// 1. Iterable<T>接口下，iterator()抽象方法，返回Iterator<T>实现类
interface _Iterable<T> {
    _Iterator<T> iterator();
}

interface _Iterator<E> {
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
}

1. SC

/**
 * 2. ArrayList_SC
 */
public class T2_Iterator<E> implements _Iterable<E> {

    transient Object[] elementData;
    private int size;
    protected transient int modCount = 0;

    public _Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * 实现Iterator<E>的容器内部类
     */
    @NoArgsConstructor
    private class Itr implements _Iterator<E> {
        int cursor;        // curr_index
        int lastRet = -1;  // 上次index
        int expectedModCount = modCount;

      	Itr() {
        }

        public boolean hasNext() {
            return cursor != size;
        }

        public E next() {
            int i = cursor;
            Object[] elementData = T2_Iterator.this.elementData;
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            T2_Iterator.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        }
    }


    public E remove(int index) {
        final Object[] es = elementData;

        E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }

    /**
     * 数组删除指定index元素
     */
    private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            // index后的元素向前移动一位
            System.arraycopy(es, i + 1, es, i, newSize - i);

        // 最后的index置为null
        es[size = newSize] = null;
    }
}

2. 增强for循环

• 底层Iterator实现

for (String one : list) {
    System.out.println(one);
}

3. ListIterator

1. 遍历过程的增add()、删remove()、改set()
2. 逆向遍历

// 3. ListIterator
class _ListIterator {

    /*
     * 1. ArrayList和iterator同时操作数组异常
     *      java.util.ConcurrentModificationException
     * 2. 遍历过程remove()
     */
    @Test
    public void iterator() {
        ArrayList<String> list = new ArrayList<>();
        list.add("aa");
        list.add("bb");
        list.add("cc");

        // list.removeIf("bb"::equals);
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            if ("bb".equals(it.next())) {

                // 1. it和list同时操作数组
                // list.add("kk");

                // 2. 遍历过程删除
                it.remove();
            }
        }
        System.out.println("list = " + list);
    }

    /**
     * 3. 遍历过程的增add()、删remove()、改set()
     * 4. 逆向遍历
     */
    @Test
    public void listIterator() {
        ArrayList<String> list = new ArrayList<>();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        ListIterator<String> it = list.listIterator();
        while (it.hasNext()) {
            if ("bb".equals(it.next())) {

                // 1. 遍历途中新增
                it.add("kk");

                // 2. 遍历途中更新
                it.set("ooxx");

                // 3. 遍历途中删除
                it.remove();
            }
        }
        System.out.println("list = " + list);

        System.out.println("it.hasNext() = " + it.hasNext());
        System.out.println("it.hasPrevious() = " + it.hasPrevious());
        // 4. 逆向遍历
        while (it.hasPrevious()) {
            System.out.println(it.previous());
        }
    }
}

7. Comparator

1. inner_Comparator => Comparable接口compareTo()
2. outer_Comparator => Comparator接口compare()

1. inner_Comparator

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
class One implements Comparable<One> {
    private Integer age;
    private Double height;
    private String name;

    @Override
    public int compareTo(One o) {
        // 1. 年龄比较
        // return this.getAge() - o.getAge();
        // 2. 身高比较
        // return Double.compare(this.getHeight(), o.getHeight());
        // 3. 名字比较
        return this.getName().compareTo(o.getName());
    }
}

@Test
public void inner_Comparator() {
    One o1 = new One(14, 160.5, "alili");
    One o2 = new One(14, 170.5, "bnana");
    System.out.println(o1.compareTo(o2));
}

2. outer_Comparator

• sort()
  1. 倒序reverseOrder()
  2. 排序元素为null
  3. 排序字段为null

public class T3_Comparator {

    @Test
    public void outer_Comparator() {
        One o1 = new One(14, 160.5, "alili");
        One o2 = new One(14, 170.5, "bnana");

        class Comparator_age implements Comparator<One> {
            @Override
            public int compare(One o1, One o2) {
                return o1.getAge() - o2.getAge();
            }
        }
        // 1. 定义类
        Comparator_age ct_age = new Comparator_age();
        System.out.println("ct_age.compare(o1, o2) = " + ct_age.compare(o1, o2));

        // 2. lambda
        Comparator<One> ct_int = Comparator.comparingInt(One::getAge);

        // 3. 反转 reversed()
        Comparator<One> ct_double = Comparator.comparingDouble(One::getHeight).reversed();

        // 4. JDK8 => Comparator.comparing()
        Comparator<One> ct_string = (a, b) -> a.getName().compareTo(b.getName());
        Comparator<One> ct_str = Comparator.comparing(One::getName);

        // 5. JDK8 => Comparator.thenComparing()
        Comparator<One> thenComparing = Comparator.comparing(One::getHeight).thenComparing(One::getAge);
    }

    @Test
    void list_sort() {
        List<One> list = Lists.newArrayList(
                new One(14, 160.5, "alili"),
                new One(13, 170.5, "bnana")
        );

        // 1. JDK8中List.sort
        // Collections.sort(ones, Comparator.comparingInt(One::getAge));
        list.sort(Comparator.comparingInt(One::getAge));

        // 2. reverseOrder
        list.sort(Comparator.comparing(One::getName, Comparator.reverseOrder()));

        // 3. stream
        List<One> list_order = list.stream()
                .sorted(Comparator.comparingInt(One::getAge))
                .collect(Collectors.toList());

        // 4. stream_reverse
        List<One> list_reverse = list.stream()
                .sorted(Comparator.comparing(One::getName, Comparator.reverseOrder()))
                .collect(Collectors.toList());
    }

    /**
     * 1. 排序元素为null
     * 2. 排序字段为null
     */
    @Test
    void null_list() {
        List<One> null_list = Lists.newArrayList(
                null,
                new One(14, 160.5, "alili"),
                new One(13, 170.5, "bnana"),
                new One(null, 170.5, "bnana")
        );

        // NullPointerException
        // null_list.sort(Comparator.comparingInt(One::getAge));

        // 1. 排序元素为null
        null_list.sort(Comparator.nullsLast(Comparator.comparing(One::getName)));
        System.out.println("null_list = " + null_list);

        null_list.sort(Comparator.nullsFirst(Comparator.comparing(One::getName)));
        System.out.println("null_list = " + null_list);

        // 2. 排序字段为null
        Comparator<One> null_com = Comparator.nullsFirst(
                Comparator.comparing(
                        One::getAge,
                        Comparator.nullsLast(Comparator.naturalOrder())
                )
        );

        null_list.sort(null_com);
        System.out.println("null_list = " + null_list);
    }
}