Java AbstractList

2018-10-24

Java AbstractList

介绍

AbstractList文件的内部结构是这样的

AbstractList.java
- class AbstractList
  - class Itr
  - class ListItr
- class SubList
- class RandomAccess

AbstractCollection

AbstractList 继承 AbastractCollection

AbstractCollection 内部具体实现了

isEmpty
contains
toArray
T[] toArray
remove
containsAll
addAll
removeAll
retainAll
clear
toString

这些方法,只有 iterator和size 作为抽象方法交由子类实现

AbstractList

AbstractList extends AbstractCollection implements List

这个类只是实现了

indexOf
lastIndexOf
clear
addAll

同时,AbstractList内部还有两个子类

Itr
ListItr

Itr & ListItr

其中 Itr 有下面这两个方法

next
remove

而 ListItr extends Itr implements ListIterator
实现了

previous
previousIndex
nextIndex
set
add
equals
..
等方法.

总结

到这一步为止,nextIndex,previousIndex这些方法通过迭代器中的cursor变量得以实现.equals方法也是通过迭代器的hasNext()+next()完成.但是get,set,add等方法还未曾有具体的实现.

目前为止AbstractList是一个抽象类,SubList继承了AbstractList,
在SubList中,set,get方法会调用SubList内部的private AbstractList 变量实现. 但是AbstractList内部,并没有对set,get方法进行实现.

set 方法会抛出异常,而get方法还是一个抽象方法.

源码

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
  protected AbstractList(){

  }

  public boolean add(E e){
    add(size(), e);
    return true;
  }

  abstract public E get(int index);

  public E set(int index , E elemnt ){
    throw new UnsupportedOperationException();
  }

  public void add(int index, E element){
    throw new UnsupportedOperationException();
  }

  public E remove(int index ){
    throw new UnsupportedOperationException();
  }

  public int indexOf(Object o){
    ListIterator<E> it = listIterator();
    if(o == null){
      while(it.hasNext()){
        if(it.next() == null)
          return it.previousIndex();
      }
    } else {
      while(it.hasNext()){
        if(o.equals(it.next()))
          return it.previousIndex();
      }
    }

    return -1;
  }

  public int lastIndexOf(Object o ){
    ListIterator<E> it = listIterator();
    if( o == null){
      while(it.hasPrevious()){
        if(it.previous() == null)
          return it.nextIndex();
      }
    } else {
      while(it.hasPrevious()){
        if(o.equals(it.previous()))
          return it.nextIndex();
      }
    }
    return -1;
  }

  public void clear(){
    removeRange(0,size());
  }

  public boolean addAll(int index, Collection<? extends E> c){
    rangeCheckForAdd(index);
    boolean modified = false;
    for(E e : c){
      add(index++,e);
      mmodified = true;
    }

    return modified;
  }

  public ListIterator<E> listIterator(){
    return listIterator(0);
  }

  public ListIterator<E> listIterator(final int index){
    rangeCheckForAdd(index);
    return new ListItr(index);
  }

  private class Itr implements Iterator<E> {
    int cursor = 0;

    int lastRet = -1 ;

    int expectedModCount = modCount;

    public E next(){
      checkForComodification();
      try{
        int i = cursor;
        E next = get(i);
        lastRet = i;
        cursor = i +1 ;
        return next;
      } catch(IndexOutofBoundsException e){
        checkForComodification();
        throw new NoSuchElementException();
      }
    }

    public void remove(){
      if(lastRet <0)
        throw new IllegalStateException();
      checkForComodification();

      try{
        AbstractList.this.remove(lastRet);
        if(lastRet < cursor)
          cursor--;
        lastRet = -1;
        expectedModCount = modCount;
      } catch(IndexOutofBoundsException e) {
        throw new ConcurrentModificationException();
      }
    }

    final void checkForComodification(){
      if(modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
  }

  private class ListItr extends   Itr implements ListIterator<E>{
    ListItr(int index ) { cursor = index;}

    public boolean hasPrevious{ return cursor != 0;}

    public E previous(){
      checkForComodification();
      try{
        int i = cursor -1;
        E previous = get(i);
        lastRet = cursor = i;
        return previous;
      } catch(IndexOutofBoundsException e){
        checkForComodification();
        throw new NoSuchElementException();
      }
    }

    public int nextIndex(){
      return cursor;
    }

    public int previousIndex(){
      return cursor -1;
    }

    public set(E e){
      if(lastRet < 0)
        throw new IllegalStateException();
      checkForComodification();

      try{
        AbastractList.this.set(lastRet,e);
        expectedModCount = modCount;
      } catch( IndexOutofBoundsException ex){
        throw new ConcurrentModificationException();
      }
    }

    public void add(E e){
      checkForComodification();

      try{
        int i = cursor;

        AbstractList.this.add(i,e);
        lastRet = -1;
        cursor  =i+1;
        expectedModCount = modCount;
      } catch(IndexOutofBoundsException ex){
        throw new ConcurrentModificationException();
      }
    }

    public List<E> subList(int fromIndex, int toIndex){
      return (this instanceof RandomAccess ? new RandomAccessSubList<>(this,fromIndex,toIndex) : new SubList<>(this,fromIndex,toIndex));
    }

    public boolean equals(Object c){
      if( o == this){
        return true;
      }

      if (!(o instanceof List))
        return false;

      ListIterator<E> e1 = listIterator();
      ListIterator<?> e2 = ((List<?>) o).listIterator();

      while(e1.hasNext() && e2.hasNext()){
        E o1 =  e1.next();
        Object o2 = e2.next();
        if(!(o1 == null ? o2 == null : o1.equals(o2)))
          return false;
      }

      return !(e1.hasNext() || e2.hasNext());
    }

    public int hashCode(){
      int hashCode = 1;
      for (E e : this){
        hashCode = 31* hashCode + (e == null ?  0 : e.hashCode());
      }
      return hashCode;
    }

    protected void removeRange(int fromIndex, int toIndex){
      ListIterator<E> it = listIterator(fromIndex)
      for(int i =0, n  = toIndex- fromIndex; i<n;i++){
        it.next();
        it.remove();
      }
    }

    protected transient int modCount = 0;

    private void rangeCheckForAdd(int index){
      if(index<0 || index > size)
        throw new IndexOutofBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index){
      return "index " + index+ ", size :"+ size();
    }
  }

}

class SubList<E> extends AbstractList<E>{
  private final AbstractList<E> l;
  private final int offset;

  private int size;


      SubList(AbstractList<E> list, int fromIndex, int toIndex) {
          if (fromIndex < 0)
              throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
          if (toIndex > list.size())
              throw new IndexOutOfBoundsException("toIndex = " + toIndex);
          if (fromIndex > toIndex)
              throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                                 ") > toIndex(" + toIndex + ")");
          l = list;
          offset = fromIndex;
          size = toIndex - fromIndex;
          this.modCount = l.modCount;
      }

      public E set(int index, E element) {
          rangeCheck(index);
          checkForComodification();
          return l.set(index+offset, element);
      }

      public E get(int index) {
          rangeCheck(index);
          checkForComodification();
          return l.get(index+offset);
      }

      public int size() {
          checkForComodification();
          return size;
      }

      public void add(int index, E element) {
          rangeCheckForAdd(index);
          checkForComodification();
          l.add(index+offset, element);
          this.modCount = l.modCount;
          size++;
      }

      public E remove(int index) {
          rangeCheck(index);
          checkForComodification();
          E result = l.remove(index+offset);
          this.modCount = l.modCount;
          size--;
          return result;
      }

      protected void removeRange(int fromIndex, int toIndex) {
          checkForComodification();
          l.removeRange(fromIndex+offset, toIndex+offset);
          this.modCount = l.modCount;
          size -= (toIndex-fromIndex);
      }

      public boolean addAll(Collection<? extends E> c) {
          return addAll(size, c);
      }

      public boolean addAll(int index, Collection<? extends E> c) {
          rangeCheckForAdd(index);
          int cSize = c.size();
          if (cSize==0)
              return false;

          checkForComodification();
          l.addAll(offset+index, c);
          this.modCount = l.modCount;
          size += cSize;
          return true;
      }

      public Iterator<E> iterator() {
          return listIterator();
      }

      public ListIterator<E> listIterator(final int index) {
          checkForComodification();
          rangeCheckForAdd(index);

          return new ListIterator<E>() {
              private final ListIterator<E> i = l.listIterator(index+offset);

              public boolean hasNext() {
                  return nextIndex() < size;
              }

              public E next() {
                  if (hasNext())
                      return i.next();
                  else
                      throw new NoSuchElementException();
              }

              public boolean hasPrevious() {
                  return previousIndex() >= 0;
              }

              public E previous() {
                  if (hasPrevious())
                      return i.previous();
                  else
                      throw new NoSuchElementException();
              }

              public int nextIndex() {
                  return i.nextIndex() - offset;
              }

              public int previousIndex() {
                  return i.previousIndex() - offset;
              }

              public void remove() {
                  i.remove();
                  SubList.this.modCount = l.modCount;
                  size--;
              }

              public void set(E e) {
                  i.set(e);
              }

              public void add(E e) {
                  i.add(e);
                  SubList.this.modCount = l.modCount;
                  size++;
              }
          };
      }

      public List<E> subList(int fromIndex, int toIndex) {
          return new SubList<>(this, fromIndex, toIndex);
      }

      private void rangeCheck(int index) {
          if (index < 0 || index >= size)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }

      private void rangeCheckForAdd(int index) {
          if (index < 0 || index > size)
              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
      }

      private String outOfBoundsMsg(int index) {
          return "Index: "+index+", Size: "+size;
      }

      private void checkForComodification() {
          if (this.modCount != l.modCount)
              throw new ConcurrentModificationException();
      }
}

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

Java ListIterator

2018-10-24

Java ListIterator

ListIterator extends Iterator,比起Iterator主要只有forEach方法,而ListIterator增加了大量的List处理的方法

源码

public ListIterator<E>  extends Iterator<E>{
  boolean hasNext();

  E next();

  boolean hasPrevious();

  E previous();

  int nextIndex();

  int previousIndex();

  void remove();

  void set(E e);

  void add(E e);
}

显而易见,

Java Comparator

2018-10-24

Java Comparator

源码

@FunctionalInterface
public interface Comparator<T>{

  int compare(T o1, T o2);

  boolean equals(Object obj);

  default Comparator<T> reversed(){
    return Collections.reverseOrder(this);
  }

  default Comparator<T> thenComparing(Comparator<? super T> other){
    Objects.requireNonNull(other);
    return (Comparator<T> & Serializable)(c1,c2)->{
      int res = compare(c1,c2);
      return (res != 0) > ? res :other.compare(c1,c2);  
    }
  }

  default <U> Comparator<T> thenComparing(Function<? super T, ? extends U> keyExtractor,  Comparator<? super U> keyComparator){
      return thenComparing(comparing(keyExtractor,keyComparator));
  }


  default <U extends Comparable<? super U>> Comparator<T> thenComparing( Function<? super T, ? extends U> keyExtractor){
    return thenComparing(comparing(keyExtractor));
  }

  default Comparator<T> thenComparing(ToIntFunction<? super T> keyExtractor){
    return thenComparing(comparingInt(keyExtractor));
  }

  default Comparator<T> thenComparingLong(ToLongFunction<? super T> keyExtractor) {
    return thenComparing(comparingLong(keyExtractor));
  }

  default Comparator<T> thenComparingDouble(ToDoubleFunction<? super T> keyExtractor) {
    return thenComparing(comparingDouble(keyExtractor));
  }

  public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
      return Collections.reverseOrder();
  }

  public static <T extends Comparable<? super T>> Comparator<T> naturalOrder(){
    return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
  }

  public static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator){
    return new Comparators.NullComparator<>(true,comparator);
  }

  public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator){
    return new Comparators.NullComparator<>(false,comparator);
  }

  public static <T,U> Comparator<T> comparing(Function<? super T, ? extends U> keyExtractor,Comparator<? super U> keyComparator){
    Objects.requireNonNull(keyExtractor);
    Objects.requireNonNull(keyComparator);
    return (Comparator<T> & Serializable)(c1,c2) ->keyComparator.compare(keyExtractor.apply(c1),keyExtractor.apply(c2));
  }

  public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
       Objects.requireNonNull(keyExtractor);
       return (Comparator<T> & Serializable)
           (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
   }

  public static <T> Comparator<T> comparingLong(ToLongFunction<? super T> keyExtractor) {
      Objects.requireNonNull(keyExtractor);
      return (Comparator<T> & Serializable)
          (c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2));
  }


  public static<T> Comparator<T> comparingDouble(ToDoubleFunction<? super T> keyExtractor) {
       Objects.requireNonNull(keyExtractor);
       return (Comparator<T> & Serializable)
           (c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2));
   }

}

解析

首先,Comparator的源码中出现了大量的

1	(Comparator<T> & Serializable)

这个表示强制类型转换为 Comparator 和 Serializable[1]

[1](Comparator & Serializable)

Java @FunctionalInterface Function

2018-10-23

Java @FunctionalInterface Function

[TOC]

源码

@FunctionalInterface
public interface Function<T,R>{
  R apply(T t);

  default <V> Function<V,R> compose(Function<? extends V,? extends T> before){
    Objects.requireNonNull(before);
    return (V v)-> apply(before.apply);
  }


  default <V> Function<T,V> andThen(Function<? super R,? superOb V> after){
    Objects.requireNonNull(after);
    return (T t)-> after.apply(apply(t));
  }

  static <T> Function<T, T> identity(){ return t -> t;}
}

介绍

Function<T,R> ,这里我翻译一下api上的内容

Type Parameters

T 函数的输入类型
R 函数的输出类型

All Known Subinterface

UnaryOperator

Functional Interface

这是一个函数式接口,因此可以作为lambda表达式或者方法引用的赋值对象

方法

apply 实现执行处理
compose 构建一个新的Function, 将before的输出作为新Function的apply的输入,新apply的实现同当前
andThen 同理

java @FunctionalInterface UnaryOperator

2018-10-23

Java @FunctionalInterface UnaryOperator

源码

@FunctionalInterface
public interface UnaryOperator<T> extends Function<T,T> {

  static <T> UnaryOperator<T> identity(){return t -> t;}

}

介绍

其实就是一个输入输出类型相同的Function<T,E>.此时T 同 E.

Java Interface List

2018-10-23

List

实现了List接口的方法:

AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

解析

可以看到 List 继承了 Collection 接口.比起Collection而言List多了很多方法,同时还重写了Spliterator方法.以及默认实现了部分方法.

默认实现的方法
- replaceAll
- sort
没有实现的方法
- 很多很多

下面先看一看已经默认实现了的方法

replaceAll

可以看到,replaceAll的实现方式是:

传入一个UnaryOperator
调用this.listIterator();
如果迭代器有下一个元素
- 将下一个元素的值赋值为UnaryOperator.apply的结果
如果没有
- 结束

使用demo

public class Main {

    public static void main(String[] args){

        List list = new ArrayList<Integer>();
        for(int i = 0; i < 10 ; i++){
            list.add(i);
        }


        for(int i =0 ; i < list.size();i++){
            System.out.print(list.get(i));
        }

        System.out.println();

        list.replaceAll(new UnaryOperator<Integer>() {
            @Override
            public Integer apply(Integer integer) {
                return integer <= 4 ? integer : 4;
            }
        });

        for(int i =0 ; i < list.size();i++){
            System.out.print(list.get(i));
        }

        System.out.println();
    }


}

输出结果

1 2	0123456789 0123444444

用lambda表达式

1	list.replaceAll(o -> (Integer) o > 4? 4:o);

结果一样

sort

default void sort(Comparator<? extends E> c){
  Object[] a = this.toArray();
  Arrays.sort(a,(Comparator)c);
  ListIterator<E> i = this.listIterator();
  for (Object e : a){
    i.next();
    i.set((E)e );
  }
}


``` java
  public interface List<E> extends Collection<E> {
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    boolean add(E e);

    boolean remove(Object o);

    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean addAll(int index, Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    boolean retainAll(Collection<?> c);

    default void replaceAll(UnaryOperator<E> operator){
      Objects.requireNonNull(operator);

      final ListIterator<E> li = this.listIterator();
      while( li.hasNext()){
        li.set(operator.apply(li.next()));
      }
    }

    default void sort(Comparator<? extends E> c){
      Object[] a = this.toArray();
      Arrays.sort(a,(Comparator)c);
      ListIterator<E> i = this.listIterator();
      for (Object e : a){
        i.next();
        i.set((E)e );
      }
    }

    void clear();

    boolean equals(Object o);

    int hashCode();

    E get(int index);

    E set(int index, E element);

    void add(int index, E element);

    E remove(int index);

    int indexOf(Object o);

    int lastIndexOf(Object o);

    ListIterator<E> listIterator();

    ListIterator<E> listIterator(int index);

    List<E> subList(int fromIndex, int toIndex);

    @Override
    default Spliterator<E> Spliterator(){
      return Spliterators.spliterator(this,Spliterator.ORDERED);
    }
  }


- 先把List转换成数组
- 然后通过Arrays的静态方法传入数组和Comparator进行排序
- 获取迭代器,调用迭代器的next(),set()方法按序赋值

### Arrays

是一个工具类,包含了控制数组的各个方法

进程与线程

2018-10-23

进程与线程

Process与Thread

进程是系统资源调度的基本单位
一个进程可以分为多个线程,

线程是cpu调度的基本单位

Linux跨进程通信

文件共享
消息队列

Java @Flow

2018-10-23

Java @Flow

找不到相关有效的文档,只在这里看过一点点说明

TODO : 到时候翻译一下..

@Flow

Java Collection

2018-10-23

Java Collection

public interface Collection<E> extends Iterable<E>{
  int size();

  boolean isEmpty();

  boolean contains(Object o);

  @NotNull Iterable<E> iterator();

  @NotNull @Flow(sourceContainer = true ,targetContainer = true) Object[] toArray();

  @NotNull @Flow(sourceContainer = true ,targetContainer = true) <T> T[] toArray(@NotNull T[] a);

  @Contract(mutates="this") boolean add(E e);

  @Contract(mutates="this") boolean remove(Object o);

  boolean containsAll(@NotNull Collection<?> c);

  @Contract(mutates="this") boolean addAll(@NotNull @Flow(sourceContainer = true, targetContainer = true) Collection<? extends E> c);

  @Contract(mutates="this") boolean removeAll(@NotNull Collection<?> c);

  @Contract(mutates="this") default boolean removeIf(Predicate<? super E> filter){
    Object.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while(each.hasNext()){
      if(filter.test(each.next())){
        each.remove();
        removed = true;
      }
    }

    return removed;
  }

  @Contract(mutates="this") boolean retainAll(@NotNull Collection<?> c);

  @Contract(mutates="this") void clear();

  boolean equals(Object o);

  int hashCode();

  @Contract(pure=true) @Override
  default Spliterator<E> spliterator(){ return Spliterators.spliterator(this,0);}

  @Contract(pure=true)
  default Stream<E> stream() { return StreamSupport.stream(spliterator(),false);}

  @Contract(pure=true)
  default Stream<E> parallelStream(){ return StreamSupport.stream(spliterator(),true);}
}

算法整理囖

2018-10-22

基本思想

穷举
递推
- 斐波那契数列
递归
- 阶乘
分治
概率
- 蒙特卡罗

排序

冒泡
前与后比较,交换,重复
选择
选最值放到开头/末尾
插入
[0]
[0,1]比较
[0,1,2]比较
Shell
分治,增量,插入排序
快排
[0,n] -> [0,m][m][m,n]
[0,m],[m,n]重复
堆排序
合并排序
输入(两个有序) 输出一个有序
桶排序

查找

顺序
遍历
折半(二分查找)
- 有序数据
数据结构
- 顺序表
- 链表
- 树
- 图