读Collections源码 博客分类: java集合 java
程序员文章站
2024-03-14 12:12:10
...
//一个操作集合的工具类,里面全部都是静态方法。 //根据元素的自然顺序进行排序 public static <T extends Comparable<? super T>> void sort(List<T> list) { //转为array Object[] a = list.toArray(); //排序 Arrays.sort(a); ListIterator<T> i = list.listIterator(); //设置值 for (int j=0; j<a.length; j++) { i.next(); i.set((T)a[j]); } } //根据传入的比较器对元素进行排序 public static <T> void sort(List<T> list, Comparator<? super T> c) { Object[] a = list.toArray(); Arrays.sort(a, (Comparator)c); ListIterator i = list.listIterator(); for (int j=0; j<a.length; j++) { i.next(); i.set(a[j]); } } //使用二分查找法根据指定key查询对象 public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) { //没有传入比较器 if (c==null) return binarySearch((List) list, key); if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key, c); else return Collections.iteratorBinarySearch(list, key, c); } public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); } private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) { int low = 0; int high = list.size()-1; while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = list.get(mid); int cmp = midVal.compareTo(key); //比他小往右边找 if (cmp < 0) low = mid + 1; //比他大往左边找 else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found } //将指定元素添加到collection中 public static <T> boolean addAll(Collection<? super T> c, T... elements) { boolean result = false; for (T element : elements) result |= c.add(element); return result; } //以后进先出的形式返回某个deque视图 public static <T> Queue<T> asLifoQueue(Deque<T> deque) { return new AsLIFOQueue<>(deque); } //返回一个动态类型安全的collection插入错误的类型会直接抛出ClassCastException异常 //其实现就是在添加元素的时候加入类型检查 public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type) { return new CheckedCollection<>(c, type); } //返回一个动态类型安全的list插入错误的类型会直接抛出ClassCastException异常 //其实现就是在添加元素的时候加入类型检查 public static <E> List<E> checkedList(List<E> list, Class<E> type) { return (list instanceof RandomAccess ? new CheckedRandomAccessList<>(list, type) : new CheckedList<>(list, type)); } //返回一个动态类型安全的map插入错误的类型会直接抛出ClassCastException异常 //其实现就是在添加元素的时候加入类型检查 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType) { return new CheckedMap<>(m, keyType, valueType); } //将元素从一个列表复制到另一个列表 public static <T> void copy(List<? super T> dest, List<? extends T> src) { int srcSize = src.size(); if (srcSize > dest.size()) throw new IndexOutOfBoundsException("Source does not fit in dest"); if (srcSize < COPY_THRESHOLD || (src instanceof RandomAccess && dest instanceof RandomAccess)) { for (int i=0; i<srcSize; i++) dest.set(i, src.get(i)); } else { ListIterator<? super T> di=dest.listIterator(); ListIterator<? extends T> si=src.listIterator(); for (int i=0; i<srcSize; i++) { di.next(); di.set(si.next()); } } } //如果两个集合中没有相同的元素则返回true public static boolean disjoint(Collection<?> c1, Collection<?> c2) { Collection<?> contains = c2; Collection<?> iterate = c1; //注释上写的这样效率更高 if (c1 instanceof Set) { iterate = c2; contains = c1; } else if (!(c2 instanceof Set)) { int c1size = c1.size(); int c2size = c2.size(); if (c1size == 0 || c2size == 0) { return true; } //大的包含小的效率更高 if (c1size > c2size) { iterate = c2; contains = c1; } } for (Object e : iterate) { if (contains.contains(e)) { // Found a common element. Collections are not disjoint. return false; } } return true; } //用指定的元素替换列表中的所有元素 public static <T> void fill(List<? super T> list, T obj) { int size = list.size(); //小于25或者支持随机访问 if (size < FILL_THRESHOLD || list instanceof RandomAccess) { for (int i=0; i<size; i++) list.set(i, obj); } else { ListIterator<? super T> itr = list.listIterator(); for (int i=0; i<size; i++) { itr.next(); itr.set(obj); } } } //返回集合中等于元素的个数 public static int frequency(Collection<?> c, Object o) { int result = 0; if (o == null) { for (Object e : c) if (e == null) result++; } else { for (Object e : c) if (o.equals(e)) result++; } return result; } //返回source中第一次出现在target的位置 public static int indexOfSubList(List<?> source, List<?> target) { int sourceSize = source.size(); int targetSize = target.size(); //如果源列表比目标列表短则直接返回-1 int maxCandidate = sourceSize - targetSize; if (sourceSize < INDEXOFSUBLIST_THRESHOLD || (source instanceof RandomAccess&&target instanceof RandomAccess)) { nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) { for (int i=0, j=candidate; i<targetSize; i++, j++) //如果不相等则重新循环 if (!eq(target.get(i), source.get(j))) continue nextCand; return candidate; } } else { // Iterator version of above algorithm ListIterator<?> si = source.listIterator(); nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) { ListIterator<?> ti = target.listIterator(); for (int i=0; i<targetSize; i++) { if (!eq(ti.next(), si.next())) { //回溯si的指针 for (int j=0; j<i; j++) si.previous(); continue nextCand; } } return candidate; } } return -1; // No candidate matched the target } //返回source中最后一次出现在target的位置 public static int lastIndexOfSubList(List<?> source, List<?> target) { int sourceSize = source.size(); int targetSize = target.size(); int maxCandidate = sourceSize - targetSize; if (sourceSize < INDEXOFSUBLIST_THRESHOLD || source instanceof RandomAccess) { // Index access version nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) { for (int i=0, j=candidate; i<targetSize; i++, j++) if (!eq(target.get(i), source.get(j))) continue nextCand; // Element mismatch, try next cand return candidate; // All elements of candidate matched target } } else { // Iterator version of above algorithm if (maxCandidate < 0) return -1; ListIterator<?> si = source.listIterator(maxCandidate); nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) { ListIterator<?> ti = target.listIterator(); for (int i=0; i<targetSize; i++) { if (!eq(ti.next(), si.next())) { if (candidate != 0) { // Back up source iterator to next candidate for (int j=0; j<=i+1; j++) si.previous(); } continue nextCand; } } return candidate; } } return -1; // No candidate matched the target } //根据元素的自然顺序返回最大值 public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) { Iterator<? extends T> i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (next.compareTo(candidate) > 0) candidate = next; } return candidate; } //根据比较器比较返回Collection中的最大值 public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) { if (comp==null) return (T)max((Collection<SelfComparable>) (Collection) coll); Iterator<? extends T> i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (comp.compare(next, candidate) > 0) candidate = next; } return candidate; } //根据自然顺序返回集合中的最小值 public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) { Iterator<? extends T> i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (next.compareTo(candidate) < 0) candidate = next; } return candidate; } //根据比较器比较返回Collection中的最小值 public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) { if (comp==null) return (T)min((Collection<SelfComparable>) (Collection) coll); Iterator<? extends T> i = coll.iterator(); T candidate = i.next(); while (i.hasNext()) { T next = i.next(); if (comp.compare(next, candidate) < 0) candidate = next; } return candidate; } //返回由n个o组成的不可变集合 public static <T> List<T> nCopies(int n, T o) { if (n < 0) throw new IllegalArgumentException("List length = " + n); return new CopiesList<>(n, o); } //替换旧值 public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) { boolean result = false; int size = list.size(); if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) { if (oldVal==null) { for (int i=0; i<size; i++) { if (list.get(i)==null) { list.set(i, newVal); result = true; } } } else { for (int i=0; i<size; i++) { if (oldVal.equals(list.get(i))) { list.set(i, newVal); result = true; } } } } else { ListIterator<T> itr=list.listIterator(); if (oldVal==null) { for (int i=0; i<size; i++) { if (itr.next()==null) { itr.set(newVal); result = true; } } } else { for (int i=0; i<size; i++) { if (oldVal.equals(itr.next())) { itr.set(newVal); result = true; } } } } return result; } //反转整个list public static void reverse(List<?> list) { int size = list.size(); if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) //交换i和j位置的值 swap(list, i, j); } else { ListIterator fwd = list.listIterator(); ListIterator rev = list.listIterator(size); for (int i=0, mid=list.size()>>1; i<mid; i++) { Object tmp = fwd.next(); fwd.set(rev.previous()); rev.set(tmp); } } } public static void swap(List<?> list, int i, int j) { final List l = list; l.set(i, l.set(j, l.get(i))); } //随机交换list元素的位置 public static void shuffle(List<?> list) { Random rnd = r; if (rnd == null) r = rnd = new Random(); shuffle(list, rnd); } public static void shuffle(List<?> list, Random rnd) { int size = list.size(); if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { for (int i=size; i>1; i--) swap(list, i-1, rnd.nextInt(i)); } else { Object arr[] = list.toArray(); // Shuffle array for (int i=size; i>1; i--) swap(arr, i-1, rnd.nextInt(i)); // Dump array back into list ListIterator it = list.listIterator(); for (int i=0; i<arr.length; i++) { it.next(); it.set(arr[i]); } } } //返回一个逆转顺序的比较器 public static <T> Comparator<T> reverseOrder() { return (Comparator<T>) ReverseComparator.REVERSE_ORDER; } //逆转比较器顺序 public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) { if (cmp == null) return reverseOrder(); if (cmp instanceof ReverseComparator2) return ((ReverseComparator2<T>)cmp).cmp; return new ReverseComparator2<>(cmp); } //将list中的元素移动distance距离 public static void rotate(List<?> list, int distance) { if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD) rotate1(list, distance); else rotate2(list, distance); } private static <T> void rotate1(List<T> list, int distance) { int size = list.size(); if (size == 0) return; distance = distance % size; if (distance < 0) distance += size; if (distance == 0) return; for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) { T displaced = list.get(cycleStart); int i = cycleStart; do { i += distance; if (i >= size) i -= size; displaced = list.set(i, displaced); nMoved ++; } while (i != cycleStart); //返回只包含一个元素的不可变set public static <T> Set<T> singleton(T o) { return new SingletonSet<>(o); } //将此collection转为同步的 public static <T> Collection<T> synchronizedCollection(Collection<T> c) { return new SynchronizedCollection<>(c); } //将集合转为不可变集合 public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) { return new UnmodifiableCollection<>(c); }
推荐阅读
-
读ThreadLocal源代码 博客分类: java多线程 java
-
读Collections源码 博客分类: java集合 java
-
看String源码的疑惑 博客分类: java String
-
读ThreadLocal源代码 博客分类: java多线程 java
-
读Collections源码 博客分类: java集合 java
-
读Exchanger源码 博客分类: java多线程 java
-
微信公众账号第三方平台全网发布源码(java) 博客分类: java微信jeewx
-
jdk-源码中的一些坑 博客分类: JAVA基础JAVA进阶JDK源码 jdkRunnableTask
-
未完 Java Collections | 容器 博客分类: Java Foundation java容器collection
-
javaweb读取任意目录的下的properties配置文件(解决普通java类读web-inf下任意目录) 博客分类: JAVA java