2016-07-10 14:32:36 +0000   |     java thinking in java container array   |   Viewed times   |    

Array不是一般意义上的“容器”

讲容器之前,请允许我先把Array和其他所有的容器区分开来。它是Java语言内置(compiler-supported type)的数据类型,它是唯一可以存放基本型的容器。而且Array非常地高效。 这里有一篇好文章:《历史上的 Collection 类 ― 数组》,可以帮助我们了解Array的基本情况。

Array为什么效率高呢?这要从Array本身在内存中的结构说起(下图): ArrayMemory1 对于Array的具体实现,有下面几个重要事实:

ArrayMemory2 如上图,多维数组的实现方式,是靠一个“引用的数组”来过度的。第一层数组的每一个地址,只储存指向具体数据数组的一个引用。

Array效率高的秘密,就在于它在内存中占据的空间是连续的。因此如下图,只要掌握了在内存中的首地址,以及数组的长度,对于任意想要的元素,数组只要在首地址基础上加上偏移值,就能找到该元素。而对内存的操作,seek偏移值的开销是非常小的。 ArrayMemory2

但连续空间是把双刃剑,副作用是Array声明的时候必须固定长度,之后不能修改。这极大地限制了Array的使用,因为大多数的使用场景,声明数据的时候,并不知道我们需要多大的容器。这才导致了后面其他容器的出现。

int[] myArray = new int[10];

由于Java类库已经经历了近20年的改进和打磨,java容器的效率已经有了明显的提升,尤其随着应用场景的复杂化,说Array的效率完胜容器已经不合时宜了。对一些常用的操作,比如说批量插入,或者遍历,容器提供的现成方法的效率,已经可以完胜我们自己用Array慢慢瞎捣鼓的代码了。更不用说对于更复杂的比如说并发应用。自己动手造轮子的时代已经过去了。

java.util类库中的容器

先声明,这一章只负责告诉读者一些关于util类库定义的容器的一些有用的结论,来帮助我们在编程的时候尽量选择正确合适的容器。至于容器内部的一些算法细节,会在之后的《容器深谈》这一章中探讨。

Java类库java.util提供的容器到底有哪些?下面这张图略简陋,但有助于整理思路。 container

容器两大分支:Collection和Map

uitl类库容器的共同特征是:动态调节长度。为了弥补Array固定长度的遗憾。 但鱼和熊掌不可兼得。实现动态扩展数组长度,必然就要牺牲效率,为它们的弹性付出代价。因此它们的效率都不如Array。但它们之所以存在,除了动态长度外,都具备各自特色的功能,各有所长。

总的来说,容器分为两大类,都以接口形式存在,

  1. Collection 指的是一组元素的集合。强调的是元素本身。
  2. Map 的特殊功用在于它为每个元素维护的一组“KEY-VALUE”对。Key用来搜索value值。典型的应用就是“词典”。

Collection的三大将

它们也都是接口,而且各有所长,

  1. List:最正统。强调“一组元素的序列”。通常是元素插入集合时候的顺序。
  2. Set:的特点是其中元素的唯一性。插入新元素前会检查已有列表,如果已经有了,就不会再插入。
  3. Queue:虽然也强调的是序列,但更主要的是“获取下一个元素的顺序”。最简单的一种就是“FIFO(First In First Out)”先进先出。

关于List

事实上最常用的List只需要记住两种,

  1. ArrayList
  2. LinkedList

剩下一个Vector被作者说成是过时的容器,不推荐使用。而另一个CopyOnWriteList是用于并发系统,确保多线程访问时数据同步安全性的,不属于常规使用。

ArrayList和LinkedList它们俩个经常被拿来比较性能。互为对方一生的羁绊。关于它们俩,需要记住的重要事实是,

  1. ArrayList的实现基于Array。精髓在于:随机访问get(int index)方法。复杂度是常数O(1)。** 但缺点是:add(int index, element),remove(int index)的时候要逐个前移或后移操作位后面的所有元素,所以复杂度是O(n)。
  2. LinkedList的精髓在于同时实现了Queue的接口。 在Queue只是个接口,以及Java官方枪毙Stack的情况下,无论是FIFO还是LIFO,都要靠LinkedList来扛起大旗。
  3. 总体性能ArrayList完胜。 并不像传说的LinkedList更善于插入和删除动作。LinkedList的add(int index, element)和remove(int index)方法,复杂度要实现O(1)的前提是,你必须提前获得操作元素的引用。不然LinkedList还是需要遍历到那个元素,最坏的情况下仍然是O(n)复杂度。StackOverFlow上关于这个问题的回答:[**《How is LinkedList's add(int, E) of O(1) complexity?》**](http://stackoverflow.com/questions/15732334/how-is-linkedlists-addint-e-of-o1-complexity)

这里附上1. ArrayList和LinkedList的几个重要操作的复杂度对比: ll_al

ArrayList的实现

虽然说好了这章不细究具体实现。但还是忍不住看了一眼java.util.ArrayList的源代码。贴几个重要的片段上来,共赏。

public class ArrayList<E> extends AbstractList<E>  implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

英雄先问出处,ArrayList继承自AbstractList,是对List接口的一个通用实现。后面实现了4种接口,除了最重要的List之外,Cloneable接口为了调用Object.clone()方法。其他两个RandomAccess和Serializable都是标记型接口,只为了语义功能,并没有定义任何内容。

     /**
      * The array buffer into which the elements of the ArrayList are stored.
      * The capacity of the ArrayList is the length of this array buffer.
      */
     private transient Object[] elementData;	//ArrayList基于Array实现

     /**
      * The size of the ArrayList (the number of elements it contains).
      *
      * @serial
      */
     private int size;

接下来看成员字段。关键看到Object[] elementData,就知道ArrayList和传说中一样,是基于Array实现的。

	/**
     * Constructs an empty list with the specified initial capacity.
     */
    public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
    this(10);	//默认长度10
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     */
    public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    size = elementData.length;
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

3种构造函数,对应于3种不同的声明方式。可以看到,ArrayList的默认初始大小是10。

public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!! 可变长度由这个方法实现
    elementData[size++] = e;
    return true;
}

这一段是add()方法。看到ensureCapacity(size + 1)这里,ArrayList的可变长度的功能就在这个方法里了。

/**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param   minCapacity   the desired minimum capacity
     */
    public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;	//关键算法:不够了长度就乘以1.5
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

可变长度ensureCapacity()方法长这样,代码里一行关键的算法,透露了ArrayList的动态控制长度功能,是在长度不够的时候扩展为原来的1.5倍。不要小看这个简单的1.5倍。肯定是无数次实验的最优配置。智慧的结晶啊。

不能再写下去了,这没有底。以后专门写一个读JDK源代码的笔记吧。

LinkedList的实现

java.util.LinkedList的源代码也只贴几个重要的片段上来,共赏。先看一个LinkedList数据结构的简单图解,

linkedlist 双链LinkedList的数据结构很简单,由一系列节点组成。每个节点包含一个数据储存单元,和两个指针,分别指向序列中的前一个节点,以及下一个节点。

// 链表的表头,表头不包含任何数据。Entry是个链表类数据结构。
private transient Entry<E> header = new Entry<E>(null, null, null);

// LinkedList中元素个数
private transient int size = 0;

上面两行就能看出,LinkedList里的节点名叫Entry。初始化的时候只有一个header节点。下面再看节点的数据结构,

// 双向链表的节点所对应的数据结构。
// 包含3部分:上一节点,下一节点,当前节点值。
private static class Entry<E> {
// 当前节点所包含的值
E element;
// 下一个节点
Entry<E> next;
// 上一个节点
Entry<E> previous;

	/**
	* 链表节点的构造函数。
	* 参数说明:
	*   element  —— 节点所包含的数据
	*   next      —— 下一个节点
	*   previous —— 上一个节点
	*/
	Entry(E element, Entry<E> next, Entry<E> previous) {
    	this.element = element;
    	this.next = next;
    	this.previous = previous;
	}
}

也很简单,就像之前说的,中间一个element泛型数据本体,一前一后两个指向前一个和下一个节点的指针。

// 将节点从链表中删除
private E remove(Entry<E> e) {
    if (e == header)
        throw new NoSuchElementException();

    E result = e.element;	//复制本体
    e.previous.next = e.next;	//让前一节点的指针跳过它,直接连到它的下一个节点。
	e.next.previous = e.previous;	//相反操作
	e.next = e.previous = null;	//消灭节点
	e.element = null;	//消灭节点
	size--;
	modCount++;
	return result;
}

LinkedList所谓效率胜过ArrayList的remove()方法,每次删除都分两步走:

关于Map

已经说过,Map的特殊功用在于它为每个元素维护的一组“KEY-VALUE”对。Key用来搜索value值。选用Map的目的在于用户关心根据元素key搜寻元素value值的速度,而对元素在容器中的顺序不在乎。Map就相当于一个小型的搜索引擎。

Map手下最常用的是HashMap。它的 get(Object key) 方法效率最高。大多数情况下,能达到Array的 O(1) 的表现。我这里不想太深入,简单讲几点HashMap实现的大致原理,但实际上HashMap实现的每一步都是值得深究的。

hashMap 如上图,

put(K key, V value) 方法的步骤如下,

综上所述,Java 8开始改成红黑树以后,一般情况下,put(K key, V value)动作是常数复杂度O(1)。最坏情况碰撞严重,最多O(logn)。还是可以接受的。

get(Object key) 方法的步骤如下,

综上所述,和插入put()方法一样,Java 8开始改成红黑树以后,一般情况下,搜索get(Object key)动作是常数复杂度O(1)。最坏情况碰撞严重,最多O(logn)。

看下面的HashMap的源码,可以清楚地看到HashMap也是基于Array实现复杂度为O(1)的快速随机访问。

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];	//这一行,证明HashMap也是基于Array实现复杂度为O(1)的快速随机访问
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

下面这个是HashMap的hash算法。

    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();	//k的哈希值和哈希种子做异或运算(哈希种子为零,就相当于保留哈希值)
							//异或:相同则结果为0,不同则结果为1

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);	//h和他自己的右位移20位做异或,再和它的右位移12为做异或。
        return h ^ (h >>> 7) ^ (h >>> 4);	//h再和他自己的右位移7位做异或,再和它的右位移4为做异或。
    }

HashMap的Hash算法具体过程如下,

我还不太明白这算法背后的数学意义,但一点是肯定的,从java的hash()算法因为只是简单的位操作,复杂度是常数O(1)。

我另外一个好奇的事是这个Java每个对象自带的 Object.hashCode() 方法,到底是怎么返回哈希值的。毕竟HashMap的代码也都只是在系统给的哈希值的基础上做文章。StackOverFlow该问题的最高票答案《How is hashCode() calculated in Java?》是这样说的:

hashCode()是每个对象自带的方法。但几乎每个类都会重写这个方法。所以hashCode()的哈希值计算方法每种数据类型都是不同的。

下面举两个最常用的例子,int整型的哈希值等于它本身。

   public int hashCode() {
       return value;
   }

String的哈希值算法稍微复杂一点,基本就是根据它自身的长度迭代,每次都乘以31再加上它的偏移值。

   public int hashCode() {
       int h = hash;
       if (h == 0) {
           int off = offset;
           char val[] = value;
           int len = count;
		   //关键算法在这里
           for (int i = 0; i < len; i++) {
               h = 31*h + val[off++];
           }
           hash = h;
       }
       return h;
   }

对于HashMap具体的工作原理,会在以后的章节深入研究。下图总结一下HashMap的put(K key, V value)方法和get(Object key)方法的具体复杂度: hashMapComplexity

最后,如果我们希望Map中元素以某种特殊的比较顺序排列,可以用TreeMap。如果希望元素保持插入时的顺序,可以用LinkedHashMap。但效率方面就要打一点折扣了。

关于Set

前文说了Set是为了保持集合中元素的唯一性。和Map一样,同样有三种不同的实现:

其中最常用的还是HashSet。TreeSet主要用于排序。排序算法取决于给定的Comparator。比如String.CASE_INSENSITIVE_ORDER.(按字母升序)

#####关于Queue Queue接口有两个主要实现:

关于Iterator迭代器和容器接口

设计Iterator迭代器的最重要原因不是为了迭代的效率。因为用普通的for语句迭代同样高效。

Iterator的真正目的是为了让使用不同容器的代码之间可以去耦合。

容器根据功能用途的不同,都被统一设计成了接口。Collection,List, Set, Map最常用的四大接口。和Iterator一样,为使用不同容器的代码去耦合才是设计这些接口的真正用意。

实际上,对于程序员自己开发的新容器而言,实现Iterator接口远比实现Collection接口要容易。因为Iterator接口只定义了hasNext()和next()两大方法。而Collection则复杂地多。因此Iterator才是简单去耦合的最佳方法。C++没有Collection接口,只有Iterator。

另外一个关于Iterator,我必须知道的是是:Java的foreach语法是面向Iterable接口的。任何类只要实现了Iterable接口都可以用foreach语法。foreach语法长这样,

for(Element e : Collection<Element>){
	//do something
}

记住,所有Collection接口都实现了Iterable接口。但Maps和Array没有。

关于过时的容器

书中作者提到的明确过时的容器有三个,这三个好汉分别是:

关于Utilities

Utilities就是对于容器的一组实用静态方法。本身不需要实例化,专门用来操作对应类型的容器实例。 三大Utilities,分别用来专门操作各自的对应容器,

里面都是静态的方法。

练习

Exercise 1

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise1 {
    public static class Gerbil {
        private static int count = 0;
        private final int id = ++count;
        public void hop() {
            System.out.println("Gerbil#" + id + " is hopping!");
        }
    }
    public static void main(String[] args) {
        List<Exercise1.Gerbil> list = new ArrayList<Exercise1.Gerbil>();
        for(int i = 0; i < 10; i++) {
            list.add(new Exercise1.Gerbil());
        }
        for(Exercise1.Gerbil gerbil : list) {
            gerbil.hop();
        }
    }
}

Exercise 2

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise2 {
    public static void main(String[] args) {
        Set<Integer> c = new HashSet<Integer>();
            for(int i = 0; i < 10; i++) {
                c.add(i); // Autoboxing
            }
            for(Integer i : c) {
                System.out.print(i + ", ");
            }
    }
}

Exercise 3

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise3 {
    public static interface Selector {
        boolean end();
        Object current();
        void next();
    }
    public static class Sequence {
        private List<Object> items;
        public Sequence() { items = new ArrayList<Object>(); }
        public void add(Object x) {
            items.add(x);
        }
        private class SequenceSelector implements Selector {
            private int i = 0;
            public boolean end() {
                return i == items.size();
            }
            public Object current() {
                return items.get(i);
            }
            public void next() {
                if(i < items.size()) {
                    i++;
                }
            }
        }
        public Selector selector() {
            return new SequenceSelector();
        }
    }
    public static void main(String[] args) {
        Sequence sequence = new Sequence();
        for(int i = 0; i < 100; i++) {
            sequence.add(Integer.toString(i));
        }
        Selector selector = sequence.selector();
        while(!selector.end()) {
            System.out.print(selector.current() + " ");
            selector.next();
        }
    }
}

Exercise 4

Generator.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise4 {
    public static interface Generator<T> {
        public T next();
    }
    public static class FilmGenerator implements Generator<String> {
        private static final String[] FILMNAME={"肖申克的救赎", "这个杀手不太冷", "阿甘正传", "霸王别姬", "美丽人生",
            "千与千寻", "辛德勒的名单", "海上钢琴师", "机器人总动员", "盗梦空间", "泰坦尼克号",
            "三傻大闹宝莱坞", "放牛班的春天", "忠犬八公的故事", "大话西游", "龙猫", "教父",
            "乱世佳人", "天堂电影院", "当幸福来敲门", "搏击俱乐部", "楚门的世界", "触不可及",
            "指环王3","罗马假日"};
        private static final int LENGTH = FILMNAME.length;
        private static int count = 0;

        private final int id = ++count;
        private int cursor = 0;
        public String next() {
            if (cursor == LENGTH) {
                cursor =  0;
            }
            return FILMNAME[cursor++];
        }
    }
    public static Generator<String> getFilmGenerator(){
        return new FilmGenerator();
    }
    public static String[] getFilms(String[] array) {
        Generator<String> gen = getFilmGenerator();
        for (int i = 0; i < array.length; i++) {
            array[i] = gen.next();
        }
        return array;
    }
    public static Collection<String> getFilms(Collection<String> c, int filmNum) {
        Generator<String> gen = getFilmGenerator();
        for (int i = 0; i < filmNum; i++) {
            c.add(gen.next());
        }
        return c;
    }

    @SuppressWarnings({"unchecked","rawtypes"})
    public static void main(String[] args){
        int size = 10;
        //fil array
        System.out.println(">>>Array:  ");
        System.out.println(Arrays.toString(getFilms(new String[size])));
        //fil arraylist
        System.out.println(">>>ArrayList:  ");
        System.out.println(getFilms(new ArrayList(),size));
        //fil lindelist
        System.out.println(">>>LinkedList:  ");
        System.out.println(getFilms(new LinkedList(),size));
        //fil hashset
        System.out.println(">>>HashSet:  ");
        System.out.println(getFilms(new HashSet(),size));
        //fil linkedhashset
        System.out.println(">>>LinkedHashSet:  ");
        System.out.println(getFilms(new LinkedHashSet(),size));
        //fil treeset
        System.out.println(">>>TreeSet:  ");
        System.out.println(getFilms(new TreeSet(),size));
    }
}

Exercise 5

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise5 {
    private static final Random RAND = new Random();
    private static final int MAX = 1000;
    public static List<Integer> getIntegerArrayList(int size) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < size; i++) {
            list.add(RAND.nextInt(MAX));
        }
        return list;
    }
    public static Integer random() {
        return RAND.nextInt(MAX);
    }
    public static void main(String[] args) {
        List<Integer> intList= getIntegerArrayList(7);
        System.out.println("1: " + intList);
        Integer oneInt = random();
        intList.add(oneInt); // Automatically resizes
        System.out.println("2: " + intList);
        System.out.println("3: " + intList.contains(oneInt));
        intList.remove(oneInt); // Remove by object
        Integer p = intList.get(2);
        System.out.println("4: " + p + " " + intList.indexOf(p));
        Integer aNewInt = random();
        System.out.println("5: " + intList.indexOf(aNewInt));
        System.out.println("6: " + intList.remove(aNewInt));
        // Must be the exact object:
        System.out.println("7: " + intList.remove(p));
        System.out.println("8: " + intList);
        intList.add(3, random()); // Insert at an index
        System.out.println("9: " + intList);
        List<Integer> sub = intList.subList(1, 4);
        System.out.println("subList: " + sub);
        System.out.println("10: " + intList.containsAll(sub));
        Collections.sort(sub); // In-place sort
        System.out.println("sorted subList: " + sub);
        // Order is not important in containsAll():
        System.out.println("11: " + intList.containsAll(sub));
        Collections.shuffle(sub, RAND); // Mix it up
        System.out.println("shuffled subList: " + sub);
        System.out.println("12: " + intList.containsAll(sub));
        List<Integer> copy = new ArrayList<Integer>(intList);
        sub = Arrays.asList(intList.get(1), intList.get(4));
        System.out.println("sub: " + sub);
        copy.retainAll(sub);
        System.out.println("13: " + copy);
        copy = new ArrayList<Integer>(intList); // Get a fresh copy
        copy.remove(2); // Remove by index
        System.out.println("14: " + copy);
        copy.removeAll(sub); // Only removes exact objects
        System.out.println("15: " + copy);
        copy.set(1, random()); // Replace an element
        System.out.println("16: " + copy);
        copy.addAll(2, sub); // Insert a list in the middle
        System.out.println("17: " + copy);
        System.out.println("18: " + intList.isEmpty());
        intList.clear(); // Remove all elements
        System.out.println("19: " + intList);
        System.out.println("20: " + intList.isEmpty());
        intList.addAll(getIntegerArrayList(4));
        System.out.println("21: " + intList);
        Object[] o = intList.toArray();
        System.out.println("22: " + o[3]);
        Integer[] pa = intList.toArray(new Integer[0]);
        System.out.println("23: " + pa[3]);
    }
}

Exercise 6

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise6 {
    public static interface Generator<T> {
        public T next();
        public List<T> createList(int listSize);
    }
    public static class StringGenerator implements Generator<String> {
        private static final Random RAND = new Random();
        private int length = 10;    //number of characters in each string
        public StringGenerator() {}
        public StringGenerator(int len) {
            length = len;
        }
        public List<String> createList(int listSize) {
            List<String> list = new ArrayList<String>();
            for (int i= 0; i < listSize; i++) {
                list.add(next());
            }
            return list;
        }
        public String next() {
            char[] result = new char[length];
            for (int i = 0; i < length; i++) {
                char letter = (char)(((int)'a') + RAND.nextInt(26));    //random a-z
                result[i] = letter;
            }
            return new String(result);
        }
    }
    public static void testUnitNext(int length) {
        StringGenerator gen = new StringGenerator(length);
        System.out.println(gen.next());
    }
    public static void testUnitCreatList(int listSize) {
        StringGenerator gen = new StringGenerator();
        System.out.println(gen.createList(listSize));
    }
    public static void main(String[] args) {
        /**
         * Unit Test
         */
        //int strLength = 7;
        //testUnitNext(strLength);
        //int listSize = 20;
        //testUnitCreatList(listSize);

        /**
         * Exercise 6
         */
        int strLength = 7;
        int initListSize = 20;
        StringGenerator gen = new StringGenerator(strLength);
        List<String> list = gen.createList(initListSize);
        System.out.println("1: " + list);
        String str = gen.next();
        list.add(str); // Automatically resizes
        System.out.println("2: " + list);
        System.out.println("3: " + list.contains(str));
        list.remove(str); // Remove by object
        String second = list.get(2);
        System.out.println("4: " + second + " " + list.indexOf(second));
        String str2 = gen.next();
        System.out.println("5: " + list.indexOf(str2));
        System.out.println("6: " + list.remove(str2));
        // Must be the exact object:
        System.out.println("7: " + list.remove(second));
        System.out.println("8: " + list);
        list.add(3, gen.next()); // Insert at an index
        System.out.println("9: " + list);
        List<String> sub = list.subList(1, 4);
        System.out.println("subList: " + sub);
        System.out.println("10: " + list.containsAll(sub));
        Collections.sort(sub); // In-place sort
        System.out.println("sorted subList: " + sub);
        // Order is not important in containsAll():
        System.out.println("11: " + list.containsAll(sub));
        Collections.shuffle(sub, StringGenerator.RAND); // Mix it up
        System.out.println("shuffled subList: " + sub);
        System.out.println("12: " + list.containsAll(sub));
        List<String> copy = new ArrayList<String>(list);
        sub = Arrays.asList(list.get(1), list.get(4));
        System.out.println("sub: " + sub);
        copy.retainAll(sub);
        System.out.println("13: " + copy);
        copy = new ArrayList<String>(list); // Get a fresh copy
        copy.remove(2); // Remove by index
        System.out.println("14: " + copy);
        copy.removeAll(sub); // Only removes exact objects
        System.out.println("15: " + copy);
        copy.set(1, gen.next()); // Replace an element
        System.out.println("16: " + copy);
        copy.addAll(2, sub); // Insert a list in the middle
        System.out.println("17: " + copy);
        System.out.println("18: " + list.isEmpty());
        list.clear(); // Remove all elements
        System.out.println("19: " + list);
        System.out.println("20: " + list.isEmpty());
        list.addAll(gen.createList(4));
        System.out.println("21: " + list);
        Object[] o = list.toArray();
        System.out.println("22: " + o[3]);
        String[] pa = list.toArray(new String[0]);
        System.out.println("23: " + pa[3]);
    }
}

Exercise 7

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise7 {
    public static class Table {
        private static int count = 0;
        private final int ID = ++count;
        public String toString() {
            return "Table#" + ID;
        }
    }
    public static void main(String[] args) {
        int arrayLength = 10;
        Table[] tableArray = new Table[10];
                for (int i = 0; i < tableArray.length; i++) {
            tableArray[i] = new Table();
        }
        System.out.println("Table Array >>>");
        System.out.println(Arrays.toString(tableArray));
        List<Table> tableList = Arrays.asList(tableArray);
        System.out.println("Table list >>>");
        System.out.println(tableList);
        List<Table> subTableList = tableList.subList(0,tableList.size()/2);
        System.out.println("Table sub list >>>");
        System.out.println(subTableList);
    }
}

Exercise 8

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise8 {
    public static class Gerbil {
        private static int count = 0;
        private final int ID = ++count;
        public void hop() {
            System.out.println("Gerbil#" + ID + " is hopping!");
        }
    }
    public static void main(String[] args) {
        List<Gerbil> list = new ArrayList<Gerbil>();
        for(int i = 0; i < 10; i++) {
            list.add(new Gerbil());
        }
        Iterator<Gerbil> ite = list.iterator();
        while (ite.hasNext()) {
            ite.next().hop();
        }
    }
}

Exercise 9

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise9 {
    public static class Sequence implements Iterable<Object> {
        private Object[] items;
        private int next = 0;
        public Sequence(int size) { items = new Object[size]; }
        public void add(Object x) {
            if (next < items.length) {
                items[next++] = x;
            }
        }
        public Iterator<Object> iterator() {
            return new SequenceIterator();
        }
        private class SequenceIterator implements Iterator<Object> {
            private int cursor = 0;
            public boolean hasNext() {
                return cursor < items.length;
            }
            public Object next() {
                if (hasNext()) {
                    return items[cursor++];
                }
                return null;
            }
        }
    }
    public static void main(String[] args) {
        int seqLength = 10;
        Sequence sequence = new Sequence(seqLength);
        for(int i = 0; i < seqLength; i++) {
            sequence.add(Integer.toString(i));
        }
        //for (Object obj : sequence) {
        //    System.out.println(obj);
        //}
        Iterator<Object> ite = sequence.iterator();
        while (ite.hasNext()) {
            System.out.println(ite.next());
        }
    }
}

Exercise 10

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise10 {
    public static interface Rodent {
        public void hop();
    }
    public static class Mouse implements Rodent {
        private static String NAME = "Mouse";
        private static int count = 0;
        private int ID = ++count;
        public void hop() {
            System.out.println(NAME + "#" + ID + " is hopping!");
        }
    }
    public static class Gerbil implements Rodent {
        private static String NAME = "Gerbil";
        private static int count = 0;
        private int ID = ++count;
        public void hop() {
            System.out.println(NAME + "#" + ID + " is hopping!");
        }
    }
    public static class Hamster implements Rodent {
        protected static String NAME = "Hamster";
        protected static int count = 0;
        protected int ID = ++count;
        public void hop() {
            System.out.println(NAME + "#" + ID + " is hopping!");
        }
    }

    public static void main(String[] args) {
        List<Rodent> rodents = new ArrayList<Rodent>();
        int rodentsNum = 10;
        for (int i = 0; i < rodentsNum; i++) {
            rodents.add(new Mouse());
            rodents.add(new Gerbil());
            rodents.add(new Hamster());
        }
        Iterator<Rodent> rodentIte = rodents.iterator();
        while (rodentIte.hasNext()) {
            rodentIte.next().hop();
        }
    }
}

Exercise 11

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise11 {
    public static Collection<Object> fillCollection(Collection<Object> c, Class<?> klass, int size) {
        try {
            for (int i = 0; i < size; i++) {
                c.add(klass.newInstance());
            }
        } catch (InstantiationException e) {
            throw new RuntimeException(e);
        } catch (IllegalAccessException e) {
            throw new RuntimeException(e);
        }
        return c;
    }
    public static <T> void parseCollection(Collection<T> c) {
        Iterator<T> ite = c.iterator();
        while (ite.hasNext()) {
            System.out.println(ite.next());
        }
    }
    public static class MyObject implements Comparable<MyObject> {
        private static int count = 0;
        private final int ID = ++count;
        public MyObject() {}
        public String toString() {
            return "MyObject#" + ID + "!";
        }
        public int getId() {
            return ID;
        }
        public int compareTo(MyObject o) {
            return o.getId() - getId();
        }
    }
    public static void main(String[] args) {
        Class<?> klass;
        try {
            klass = Class.forName("com.ciaoshen.thinkinjava.chapter11.Exercise11$MyObject");
        } catch (ClassNotFoundException e) {
            throw new RuntimeException(e);
        }
        int size = 10;
        //ArrayList
        parseCollection(fillCollection(new ArrayList<Object>(), klass, size));
        //LinkedList
        parseCollection(fillCollection(new LinkedList<Object>(), klass, size));
        //HashSet
        parseCollection(fillCollection(new HashSet<Object>(), klass, size));
        //TreeSet
        parseCollection(fillCollection(new TreeSet<Object>(), klass, size));
        //LinkedHashSet
        parseCollection(fillCollection(new LinkedHashSet<Object>(), klass, size));
    }
}

Exercise 12

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise12 {
    public static void main(String[] args) {
        Random rand = new Random();
        List<Integer> list1 = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();
        int listSize = 10;
        int max = 1000;
        for (int i = 0; i < listSize; i++) {
            list1.add(new Integer(rand.nextInt(max)));
            list2.add(new Integer(rand.nextInt(max)));
        }
        ListIterator<Integer> ite = list1.listIterator(list1.size());
        while (ite.hasPrevious()) {
            list2.add(ite.previous());
        }
        System.out.println(list1);
        System.out.println(list2);
    }
}

Exercise 13

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise13 {
    public static class Controller {
        private List<Event> eventList = new ArrayList<Event>();
        public void addEvent(Event c) { eventList.add(c); }
        public void run() {
            while(eventList.size() > 0) {
                // Make a copy so you’re not modifying the list
                // while you’re selecting the elements in it:
                for(Event e : new ArrayList<Event>(eventList)) {
                    if(e.ready()) {
                        System.out.println(e);
                        e.action();
                        eventList.remove(e);
                    }
                }
            }
        }
    }
    public static abstract class Event {
        private long eventTime;
        protected final long delayTime;
        public Event(long delayTime) {
            this.delayTime = delayTime;
            start();
        }
        public void start() { // Allows restarting
            eventTime = System.nanoTime() + delayTime;
        }
        public boolean ready() {
            return System.nanoTime() >= eventTime;
        }
        public abstract void action();
    }
    public static class GreenhouseControls extends Controller {
        private boolean light = false;
        public class LightOn extends Event {
            public LightOn(long delayTime) { super(delayTime); }
            public void action() {
                // Put hardware control code here to
                // physically turn on the light.
                light = true;
            }
            public String toString() { return "Light is on"; }
        }
        public class LightOff extends Event {
            public LightOff(long delayTime) { super(delayTime); }
            public void action() {
                // Put hardware control code here to
                // physically turn off the light.
                light = false;
            }
            public String toString() { return "Light is off"; }
        }
        private boolean water = false;
        public class WaterOn extends Event {
            public WaterOn(long delayTime) { super(delayTime); }
            public void action() {
                // Put hardware control code here.
                water = true;
            }
            public String toString() {
                return "Greenhouse water is on";
            }
        }
        public class WaterOff extends Event {
            public WaterOff(long delayTime) { super(delayTime); }
            public void action() {
                // Put hardware control code here.
                water = false;
            }
            public String toString() {
                return "Greenhouse water is off";
            }
        }
        private String thermostat = "Day";
        public class ThermostatNight extends Event {
            public ThermostatNight(long delayTime) {
                super(delayTime);
            }
            public void action() {
                // Put hardware control code here.
                thermostat = "Night";
            }
            public String toString() {
                return "Thermostat on night setting";
            }
        }
        public class ThermostatDay extends Event {
            public ThermostatDay(long delayTime) {
                super(delayTime);
            }
            public void action() {
                // Put hardware control code here.
                thermostat = "Day";
            }
            public String toString() {
                return "Thermostat on day setting";
            }
        }
        // An example of an action() that inserts a
        // new one of itself into the event list:
        public class Bell extends Event {
            public Bell(long delayTime) { super(delayTime); }
            public void action() {
                addEvent(new Bell(delayTime));
            }
            public String toString() { return "Bing!"; }
        }
        public class Restart extends Event {
            private List<Event> eventList;
            public Restart(long delayTime, List<Event> eventList) {
                super(delayTime);
                this.eventList = eventList;
                for(Event e : eventList)
                    addEvent(e);
                }
            public void action() {
                for(Event e : eventList) {
                    e.start(); // Rerun each event
                    addEvent(e);
                }
                start(); // Rerun this Event
                addEvent(this);
            }
            public String toString() {
                return "Restarting system";
            }
        }
        public static class Terminate extends Event {
            public Terminate(long delayTime) { super(delayTime); }
            public void action() { System.exit(0); }
            public String toString() { return "Terminating"; }
        }
    }

    public static void main(String[] args) {
        GreenhouseControls gc = new GreenhouseControls();
        // Instead of hard-wiring, you could parse
        // configuration information from a text file here:
        gc.addEvent(gc.new Bell(900));
        List<Event> eventList = new LinkedList<Event>();
        eventList.add(gc.new ThermostatNight(0));
        eventList.add(gc.new LightOn(200));
        eventList.add(gc.new LightOff(400));
        eventList.add(gc.new WaterOn(600));
        eventList.add(gc.new WaterOff(800));
        eventList.add(gc.new ThermostatDay(1400));
        gc.addEvent(gc.new Restart(2000, eventList));
        int delayTime = 5000;
        gc.addEvent(new GreenhouseControls.Terminate(new Integer(delayTime)));
        gc.run();
    }
}

Exercise 14

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise14 {
    public static List<Integer> insertInMiddle(List<Integer> list, Integer num) { //insert a num 1-1000 in the middle of the list
        int halfLength = list.size()/2;
        ListIterator<Integer> ite = list.listIterator();
        List<Integer> resultList = new LinkedList<Integer>();
        for (int i = 0; i < halfLength; i++) {
            resultList.add(ite.next());
        }
        resultList.add(num);
        while (ite.hasNext()) {
            resultList.add(ite.next());
        }
        return resultList;
    }
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<Integer>();
        int times = 10;
        for (int i = 0; i < times; i++) {
            list = insertInMiddle(list,i);
        }
        System.out.println(list);
    }
}

Exercise 15

这题我用LinkedList自己实现了一个Stack。

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise15 {
    private LinkedList<String> list = new LinkedList<String>();
    public boolean empty() {
        return list.size() == 0;
    }
    public String peek() {
        return list.peek();
    }
    public String pop() {
        return list.pop();
    }
    public String push(String item) {
        list.addFirst(item);
        return item;
    }
    @SuppressWarnings("unchecked")
    public int search(Object o) {
        return list.indexOf((String)o);
    }
    public String toString() {
        return list.toString();
    }

    public static interface Generator<T> {
        public T next();
    }
    public class StringGenerator implements Generator<String> {
        private int length = 7;
        private final Random RAND = new Random();
        public StringGenerator(int l) {
            length = l;
        }
        public String next() {
            char[] charArray = new char[length];
            for (int i = 0; i < length; i++) {
                char c = (char)((int)'a' + RAND.nextInt(26));
                charArray[i] = c;
            }
            return new String(charArray);
        }
    }
    public Generator<String> generator(int length) {
        return this.new StringGenerator(length);
    }
    enum ScanStatus {READ, WRITE}
    public class CommentErrorException extends Exception {
        private static final long serialVersionUID = 0;
        public CommentErrorException(String offset) {   //offset is the index where the error occurs
            super(offset);
        }
    }
    public void scanComment(String comment) throws CommentErrorException {
        ScanStatus myStatus = ScanStatus.WRITE;
        List<String> commentList = Arrays.asList(comment.split(""));
        ListIterator<String> commentIte = commentList.listIterator();
        String cursor = ""; //current comment
        int offset = 0; //index of cursor
        while (commentIte.hasNext()) {
            offset = commentIte.nextIndex();
            cursor = commentIte.next();
            if (myStatus == ScanStatus.WRITE) {
                if (cursor.equals("+")) {
                    myStatus = ScanStatus.READ;
                    continue;
                }
                if (cursor.equals("-")) {
                    if (empty()) {
                        throw new CommentErrorException("Position " + Integer.toString(offset) + ": stack is empty! nothing to pop!");
                    }
                    System.out.print(pop());
                    continue;
                }
                throw new CommentErrorException("Got \"" + cursor + "\" at position " + Integer.toString(offset) + ": need +- operation here!");
            }
            if (myStatus == ScanStatus.READ) {
                list.push(cursor);
                myStatus = ScanStatus.WRITE;
                continue;
            }
        }
    }
    public static void main(String[] args) {
        Exercise15 stack = new Exercise15();
        int stackLength = 10;
        for (int i = 0; i < stackLength; i++) {
            stack.push(Integer.toString(i));
        }
        System.out.println(stack);
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
        System.out.println("Stack is empty? " + stack.empty());

        String comment = "+U+n+c-+e+r+t-+a-+i-+n+t+y-+ -+r+u-+l+e+s-";
        try {
            stack.scanComment(comment);
        } catch(CommentErrorException e) {
            e.printStackTrace();
        }
    }
}

Exercise 16

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;
import java.io.*;
import java.util.regex.*;

public class Exercise16 {
    private static final String SPLITER = "\n";
    //read file
    public static String readFile(String path) {
        StringBuilder sb = new StringBuilder();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(path)));
            try {
                String line = new String("");
                while (true) {
                    line = br.readLine();
                    if (line == null) {break;}
                    sb.append(line + SPLITER);
                }
            } finally {
                br.close();
            }
        } catch(FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch(IOException e) {
            throw new RuntimeException(e);
        }
        return sb.toString();
    }
    //word segment
    public static Map<String,Integer> segmentWords(String content) {
        if (content == null || content.isEmpty()) {
            throw new RuntimeException("Content for segmentWords() method is null or empty!");
        }
        Map<String,Integer> freqMap = new HashMap<String,Integer>();
        Pattern wordP = Pattern.compile("\\w+");
        Matcher wordM = wordP.matcher(content);
        String word = "";
        while (wordM.find()) {
            word = wordM.group();
            if (freqMap.containsKey(word)) {
                freqMap.put(word, freqMap.get(word)+1);
                continue;
            }
            freqMap.put(word, 1);
        }
        return freqMap;
    }

    //count vowels
    public static void countVowels(Map<String, Integer> wordsMap) {
        int totalVowelNum = 0;
        int wordVowelCount = 0;
        Pattern vowelP = Pattern.compile("[aeiouAEIOU]");
        Matcher vowelM = vowelP.matcher("");
        if (wordsMap == null || wordsMap.isEmpty()) {
            throw new RuntimeException("The wordsMap for countVowels() method is null or empty!");
        }
        Formatter f = new Formatter(System.out);
        f.format("%-20.20s | %5s %5.5s \n", "WORD", "VOWEL", "FQ");
        f.format("%-35.35s \n", "----------------------------------------------");
        for (Map.Entry<String,Integer> record : wordsMap.entrySet()) {
            wordVowelCount = 0;
            vowelM = vowelM.reset(record.getKey());
            while (vowelM.find()) {
                wordVowelCount++;
            }
            f.format("%-20.20s | %5d %5.5s \n", record.getKey(), wordVowelCount, "*" + Integer.toString(record.getValue()));
            totalVowelNum += wordVowelCount * record.getValue();
        }
        f.format("%-35.35s \n", "---------------------------------------------");
        f.format("%-20.20s | %5.5s \n", "Total Vowel:", Integer.toString(totalVowelNum));
    }

    //test Unit
    private static class UnitTest {
        private static final String WRONGPATH = "/Users/HelloKitty/hello.java";
        private static final String RIGHTPATH = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/Exercise16.java";
        private static void testReadFile() {
            System.out.println(readFile(WRONGPATH));
            System.out.println(readFile(RIGHTPATH));
        }
        private static void testSegmentWords() {
            System.out.println(segmentWords(readFile(RIGHTPATH)));
        }
        private static void testCountVowels() {
            countVowels(segmentWords(readFile(RIGHTPATH)));
        }
    }
    public static void main(String[] args) {
        //UnitTest.testReadFile();
        //UnitTest.testSegmentWords();
        UnitTest.testCountVowels();
    }
}

Exercise 17

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise17 {
    public static class Gerbil {
        private static int count = 0;
        private final int id = ++count;
        private final String name;
        public Gerbil(String name) {
            this.name = name;
        }
        public void hop() {
            System.out.println("Gerbil#" + id + ": " + name + ", is hopping!");
        }
        public String getName() {
            return name;
        }
    }
    public static void main(String[] args) {
        Gerbil fuzzy = new Gerbil("Fuzzy");
        Gerbil spot = new Gerbil("Spot");
        Gerbil piupiu = new Gerbil("PiuPiu");
        Map<String, Gerbil> gerbilMap = new HashMap<String, Gerbil>();
        gerbilMap.put(fuzzy.getName(),fuzzy);
        gerbilMap.put(spot.getName(),spot);
        gerbilMap.put(piupiu.getName(),piupiu);
        Iterator<Map.Entry<String, Gerbil>> ite = gerbilMap.entrySet().iterator();
        while (ite.hasNext()) {
            Map.Entry<String, Gerbil> entry = ite.next();
            System.out.print("(Gerbil: " + entry.getKey() + ")    >>>     ");
            entry.getValue().hop();
        }
    }
}

Exercise 18

Exercise 18: (3) Fill a HashMap with key-value pairs. Print the results to show ordering by hash code. Extract the pairs, sort by key, and place the result into a LinkedHashMap. Show that the insertion order is maintained.

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise18 {
    public static void main(String[] args) {
        // insert HashMap
        Map<String, Integer> hashMap = new HashMap<String, Integer>();
        hashMap.put("one", 1);
        hashMap.put("two", 2);
        hashMap.put("three", 3);
        hashMap.put("four", 4);
        hashMap.put("five", 5);
        // print HashMap
        System.out.println(hashMap);
        // extract to ArrayList
        Set<Map.Entry<String,Integer>> set = hashMap.entrySet();
        List<Map.Entry<String,Integer>> list = new ArrayList<Map.Entry<String,Integer>>();
        list.addAll(set);
        // sort ArrayList
        Collections.sort(list, new Comparator<Map.Entry<String,Integer>>() {
            public int compare(Map.Entry<String,Integer> entry1, Map.Entry<String,Integer> entry2) {
                return Integer.compare(entry1.getValue(),  entry2.getValue());
            }
        });
        // insert into LinkedHashMap
        Map<String,Integer> linkedHashMap = new LinkedHashMap<String,Integer>();
        for (Map.Entry<String,Integer> entry : list) {
            linkedHashMap.put(entry.getKey(), entry.getValue());
        }
        // print LinkedHashMap
        System.out.println(linkedHashMap);
    }
}

Exercise 19

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise19 {
    public static void main(String[] args) {
        // fill HashSet
        HashSet<String> hashSet = new HashSet<String>();
        hashSet.add("one");
        hashSet.add("two");
        hashSet.add("three");
        hashSet.add("four");
        hashSet.add("five");
        // print HashSet
        System.out.println(hashSet);
        // transit to list
        List<String> list = new ArrayList<String>();
        list.addAll(hashSet);
        // sort list
        Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
        // insert into LinkedHashSet
        Set<String> linkedHashSet = new LinkedHashSet<String>();
        linkedHashSet.addAll(list);
        // print LinkedHashSet
        System.out.println(linkedHashSet);
    }
}

Exercise 20

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;
import java.io.*;
import java.util.regex.*;

public class Exercise20 {
    private static final String SPLITER = "\n";
    //read file
    public static String readFile(String path) {
        StringBuilder sb = new StringBuilder();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(path)));
            try {
                String line = new String("");
                while (true) {
                    line = br.readLine();
                    if (line == null) {break;}
                    sb.append(line + SPLITER);
                }
            } finally {
                br.close();
            }
        } catch(FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch(IOException e) {
            throw new RuntimeException(e);
        }
        return sb.toString();
    }
    //word segment
    public static Map<String,Integer> segmentWords(String content) {
        if (content == null || content.isEmpty()) {
            throw new RuntimeException("Content for segmentWords() method is null or empty!");
        }
        Map<String,Integer> freqMap = new HashMap<String,Integer>();
        Pattern wordP = Pattern.compile("\\w+");
        Matcher wordM = wordP.matcher(content);
        String word = "";
        while (wordM.find()) {
            word = wordM.group();
            if (freqMap.containsKey(word)) {
                freqMap.put(word, freqMap.get(word)+1);
                continue;
            }
            freqMap.put(word, 1);
        }
        return freqMap;
    }

    //count vowels
    public static void countVowels(Map<String, Integer> wordsMap) {
        int totalVowelNum = 0;
        int wordVowelCount = 0;
        int aCount = 0;
        int eCount = 0;
        int iCount = 0;
        int oCount = 0;
        int uCount = 0;
        Pattern vowelP = Pattern.compile("[aeiouAEIOU]");
        Matcher vowelM = vowelP.matcher("");
        Matcher aM = Pattern.compile("[aA]").matcher("");
        Matcher eM = Pattern.compile("[eE]").matcher("");
        Matcher iM = Pattern.compile("[iI]").matcher("");
        Matcher oM = Pattern.compile("[oO]").matcher("");
        Matcher uM = Pattern.compile("[uU]").matcher("");
        if (wordsMap == null || wordsMap.isEmpty()) {
            throw new RuntimeException("The wordsMap for countVowels() method is null or empty!");
        }
        Formatter f = new Formatter(System.out);
        f.format("%-20.20s | %5s %5.5s \n", "WORD", "VOWEL", "FQ");
        f.format("%-35.35s \n", "----------------------------------------------");
        for (Map.Entry<String,Integer> record : wordsMap.entrySet()) {
            wordVowelCount = 0;
            String word = record.getKey();
            vowelM = vowelM.reset(word);
            while (vowelM.find()) {
                wordVowelCount++;
            }
            aM = aM.reset(word);
            while (aM.find()) {
                aCount++;
            }
            eM = eM.reset(word);
            while (eM.find()) {
                eCount++;
            }
            iM = iM.reset(word);
            while (iM.find()) {
                iCount++;
            }
            oM = oM.reset(word);
            while (oM.find()) {
                oCount++;
            }
            uM = uM.reset(word);
            while (uM.find()) {
                uCount++;
            }
            f.format("%-20.20s | %5d %5.5s \n", record.getKey(), wordVowelCount, "*" + Integer.toString(record.getValue()));
            totalVowelNum += wordVowelCount * record.getValue();
        }
        f.format("%-35.35s \n", "---------------------------------------------");
        f.format("%-20.20s | %5.5s \n", "Total a/A:", Integer.toString(aCount));
        f.format("%-20.20s | %5.5s \n", "Total e/E:", Integer.toString(eCount));
        f.format("%-20.20s | %5.5s \n", "Total i/I:", Integer.toString(iCount));
        f.format("%-20.20s | %5.5s \n", "Total o/O:", Integer.toString(oCount));
        f.format("%-20.20s | %5.5s \n", "Total u/U:", Integer.toString(uCount));
        f.format("%-20.20s | %5.5s \n", "Total Vowel:", Integer.toString(totalVowelNum));
    }

    //test Unit
    private static class UnitTest {
        private static final String WRONGPATH = "/Users/HelloKitty/hello.java";
        private static final String RIGHTPATH = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/Exercise16.java";
        private static void testReadFile() {
            System.out.println(readFile(WRONGPATH));
            System.out.println(readFile(RIGHTPATH));
        }
        private static void testSegmentWords() {
            System.out.println(segmentWords(readFile(RIGHTPATH)));
        }
        private static void testCountVowels() {
            countVowels(segmentWords(readFile(RIGHTPATH)));
        }
    }
    public static void main(String[] args) {
        //UnitTest.testReadFile();
        //UnitTest.testSegmentWords();
        UnitTest.testCountVowels();
    }
}

Exercise 21

MyReader.java
package com.ciaoshen.thinkinjava.chapter11;
import java.io.*;

public class MyReader {
    private static String spliter = "\n";
    public MyReader(){}
    public MyReader(String s) {
        spliter = s;
    }
    public String readFile(String path) {
        StringBuilder sb = new StringBuilder();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(path)));
            String line = "";
            try {
                while (true) {
                    line = br.readLine();
                    if (line == null) {
                        break;
                    }
                    sb.append(line + spliter);
                }
            } finally {
                br.close();
            }
        } catch(FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch(IOException e) {
            throw new RuntimeException(e);
        }
        return sb.toString();
    }
    private class TestUnit {
        private final String WRONGPATH = "/Users/HelloKitty/hello.java";
        private final String RIGHTPATH = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/MyReader.java";
        private void testReadFile() {
            System.out.println(readFile(RIGHTPATH));
            System.out.println(readFile(WRONGPATH));
        }
    }
    public static void main(String[] args) {
        TestUnit test = new MyReader().new TestUnit();
        test.testReadFile();
    }
}
Exercise21.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;
import java.util.regex.*;

public class Exercise21 {
    private static Map<String, Integer> uniqueWords(String path) {
        MyReader reader = new MyReader();
        String content = reader.readFile(path);
        if (content == null || content.isEmpty()) {
            throw new RuntimeException(path + " is null or empty!");
        }
        Matcher wordM = Pattern.compile("\\w+").matcher(content);
        Map<String,Integer> wordsMap = new HashMap<String,Integer>();
        String word = "";
        while (wordM.find()) {
            word = wordM.group();
            if (wordsMap.containsKey(word)) {
                wordsMap.put(word,wordsMap.get(word) + 1);
                continue;
            }
            wordsMap.put(word,1);
        }
        return wordsMap;
    }
    public static Map<String, Integer> sortedUniqueWords(String path) {
        Map<String,Integer> wordsMap = uniqueWords(path);
        if (wordsMap == null || wordsMap.isEmpty()) {
            throw new RuntimeException("The words map for the file " + path + " is null or empty!");
        }
        List<String> list = new ArrayList<String>();
        list.addAll(wordsMap.keySet());
        Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
        Map<String, Integer> linkedHashMap = new LinkedHashMap<String, Integer>();
        for (String word : list) {
            Integer feq = wordsMap.get(word);
            if (feq == null) {
                continue;
            }
            linkedHashMap.put(word, feq);
        }
        return linkedHashMap;
    }
    public static void display(Map<String, Integer> map) {
        if (map == null || map.isEmpty()) {
            throw new RuntimeException("The args Map for display() method is null or empty!");
        }
        Formatter f = new Formatter(System.out);
        f.format("%1$20.20s %2$-5.5s \n", "WORD", "FQ");
        Set<Map.Entry<String, Integer>> set = map.entrySet();
        for (Map.Entry<String, Integer> entry : set) {
            f.format("%1$20.20s %2$-5d \n", entry.getKey(), entry.getValue());
        }
    }
    public static void main(String[] args) {
        String path = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/Exercise21.java";
        //System.out.println(uniqueWords(path));
        //System.out.println(sortedUniqueWords(path));
        display(sortedUniqueWords(path));
    }
}

Exercise 22

MyReader.java
package com.ciaoshen.thinkinjava.chapter11;
import java.io.*;

public class MyReader {
    private static String spliter = "\n";
    public MyReader(){}
    public MyReader(String s) {
        spliter = s;
    }
    public String readFile(String path) {
        StringBuilder sb = new StringBuilder();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(path)));
            String line = "";
            try {
                while (true) {
                    line = br.readLine();
                    if (line == null) {
                        break;
                    }
                    sb.append(line + spliter);
                }
            } finally {
                br.close();
            }
        } catch(FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch(IOException e) {
            throw new RuntimeException(e);
        }
        return sb.toString();
    }
    private class TestUnit {
        private final String WRONGPATH = "/Users/HelloKitty/hello.java";
        private final String RIGHTPATH = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/MyReader.java";
        private void testReadFile() {
            System.out.println(readFile(RIGHTPATH));
            System.out.println(readFile(WRONGPATH));
        }
    }
    public static void main(String[] args) {
        TestUnit test = new MyReader().new TestUnit();
        test.testReadFile();
    }
}
Exercise22.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;
import java.util.regex.*;

public class Exercise22 {
    private static class Pair implements Comparable<Pair> {
        private String key = "";
        private int value = 0;
        public Pair() {}
        public Pair(String word, int freq) {
            key = word;
            value = freq;
        }
        public String getKey() {
            return key;
        }
        public int getValue() {
            return value;
        }
        public void setKey(String word) {
            key = word;
        }
        public void setValue(int freq) {
            value = freq;
        }
        public String toString() {
            return "(" + key + "," + value + ")";
        }
        public int compareTo(Pair p) {
            return String.CASE_INSENSITIVE_ORDER.compare(this.key, p.getKey());
        }
        @Override
        public boolean equals(Object o) {
            Pair p = (Pair)o;
            return this.key.equals(p.getKey());
        }
        @Override
        public int hashCode() {
            return this.key.hashCode();
        }
    }
    private static Set<Pair> uniqueWords(String path) {
        MyReader reader = new MyReader();
        String content = reader.readFile(path);
        if (content == null || content.isEmpty()) {
            throw new RuntimeException(path + " is null or empty!");
        }
        Matcher wordM = Pattern.compile("\\w+").matcher(content);
        Set<Pair> pairSet = new HashSet<Pair>();
        while (wordM.find()) {
            Pair word = new Pair(wordM.group(), 1);
            if (pairSet.contains(word)) {
                if (updateSet(pairSet, word)) {
                    continue;
                }
            }
            pairSet.add(word);
        }
        return pairSet;
    }
    private static boolean updateSet(Set<Pair> set, Pair p) {
        Iterator<Pair> ite = set.iterator();
        while (ite.hasNext()) {
            Pair current = ite.next();
            if (current.equals(p)) {
                String key = current.getKey();
                int freq = current.getValue();
                Pair newPair = new Pair(key, freq + 1);
                set.remove(p);
                set.add(newPair);
                return true;
            }
        }
        return false;
    }
    public static List<Pair> sortedUniqueWords(String path) {
        Set<Pair> pairSet = uniqueWords(path);
        if (pairSet == null || pairSet.isEmpty()) {
            throw new RuntimeException("The pair set for the file " + path + " is null or empty!");
        }
        List<Pair> list = new ArrayList<Pair>();
        list.addAll(pairSet);
        Collections.sort(list);
        return list;
    }
    public static void display(List<Pair> list) {
        if (list == null || list.isEmpty()) {
            throw new RuntimeException("The args list for display() method is null or empty!");
        }
        Formatter f = new Formatter(System.out);
        f.format("%1$20.20s %2$-5.5s \n", "WORD", "FQ");
        for (Pair pair : list) {
            f.format("%1$20.20s %2$-5d \n", pair.getKey(), pair.getValue());
        }
    }
    public static void main(String[] args) {
        String path = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/Exercise21.java";
        //System.out.println(uniqueWords(path));
        //System.out.println(sortedUniqueWords(path));
        display(sortedUniqueWords(path));
    }
}

Exercise 23

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise23 {
    private static Map<Integer,Integer> randomNum(int size) {
        Random rand = new Random();
        Map<Integer,Integer> m = new HashMap<Integer,Integer>();
        for(int i = 0; i < 10000; i++) {
            // Produce a number between 0 and 20:
            int r = rand.nextInt(size);
            Integer freq = m.get(r);
            m.put(r, freq == null ? 1 : freq + 1);
        }
        return m;
    }
    // merge the second map to the first map
    private static Map<Integer,Integer> mergeMap(Map<Integer,Integer> map1, Map<Integer,Integer> map2) {
        if (map1 == null || map1.isEmpty() || map2 == null || map2.isEmpty()) {
            return map1;
        }
        Set<Map.Entry<Integer,Integer>> set1 = map1.entrySet();
        Set<Map.Entry<Integer,Integer>> set2 = map2.entrySet();
        Map<Integer,Integer> result = new HashMap<Integer,Integer>();
        for (Map.Entry<Integer,Integer> entry1 : set1) {
            Integer key1 = entry1.getKey();
            Integer value1 = entry1.getValue();
            for (Map.Entry<Integer,Integer> entry2 : set2) {
                Integer key2 = entry2.getKey();
                Integer value2 = entry2.getValue();
                if (key2 != null && value2 != null && key2.equals(key1)) {
                    result.put(key1, value1 + entry2.getValue());
                    break;
                }
                result.put(key1,value1);
            }
        }
        return result;
    }
    public static Map<Integer,Integer> repeatRandomNum(int times, int size) {
        Map<Integer,Integer> result = randomNum(size);
        for (int i = 0; i < times-1; i++) {
            result = mergeMap(result,randomNum(size));
        }
        return result;
    }
    public static void main(String[] args) {
        System.out.println(repeatRandomNum(10,20));
    }
}

Exercise 24

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise24 {
    public static class Dog {
        private static int count = 0;
        private final int ID = ++count;
        private final String NAME;
        public Dog(String name) {
            NAME = name;
        }
        public String toString() {
            return "Dog#" + ID + " called " + NAME;
        }
    }
    public static String randomName(int length) {
        Random rand = new Random();
        char[] name = new char[length];
        for (int i = 0; i < length; i++) {
            name[i] = (char)((int)'a' + rand.nextInt(26));
        }
        return new String(name);
    }
    public static void main(String[] args) {
        Map<String,Dog> dogMap = new LinkedHashMap<String,Dog>();
        int mapSize = 20;
        int nameLength =4;
        for (int i = 0; i < mapSize; i++) {
            String dogName = randomName(nameLength);
            dogMap.put(dogName,new Dog(dogName));
        }
        //System.out.println(dogMap);
        Set<Map.Entry<String,Dog>> dogSet = dogMap.entrySet();
        List<Map.Entry<String,Dog>> dogList = new ArrayList<Map.Entry<String,Dog>>();
        dogList.addAll(dogSet);
        //System.out.println(dogList);
        Collections.sort(dogList, new Comparator<Map.Entry<String,Dog>>() {
            public int compare(Map.Entry<String,Dog> entry1, Map.Entry<String,Dog> entry2) {
                return String.CASE_INSENSITIVE_ORDER.compare(entry1.getKey(),entry2.getKey());
            }
        });
        //System.out.println(dogList);
        Map<String,Dog> sortedDogMap = new LinkedHashMap<String,Dog>();
        for (Map.Entry<String,Dog> entry : dogList) {
            sortedDogMap.put(entry.getKey(),entry.getValue());
        }
        System.out.println(sortedDogMap);
    }
}

Exercise 25

MyReader.java
package com.ciaoshen.thinkinjava.chapter11;
import java.io.*;

public class MyReader {
    private static String spliter = "\n";
    public MyReader(){}
    public MyReader(String s) {
        spliter = s;
    }
    public String readFile(String path) {
        StringBuilder sb = new StringBuilder();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(path)));
            String line = "";
            try {
                while (true) {
                    line = br.readLine();
                    if (line == null) {
                        break;
                    }
                    sb.append(line + spliter);
                }
            } finally {
                br.close();
            }
        } catch(FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch(IOException e) {
            throw new RuntimeException(e);
        }
        return sb.toString();
    }
    private class TestUnit {
        private final String WRONGPATH = "/Users/HelloKitty/hello.java";
        private final String RIGHTPATH = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/MyReader.java";
        private void testReadFile() {
            System.out.println(readFile(RIGHTPATH));
            System.out.println(readFile(WRONGPATH));
        }
    }
    public static void main(String[] args) {
        TestUnit test = new MyReader().new TestUnit();
        test.testReadFile();
    }
}
Exercise25.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;
import java.util.regex.*;

// statistics the word and their positions in the file
public class Exercise25 {
    public static Map<String,ArrayList<Integer>> statistic(String path, String regex) {
        if (path == null || regex == null) {
            throw new RuntimeException("Argument content or regex is null!");
        }
        String content = new MyReader().readFile(path);
        if (content == null) {
            throw new RuntimeException("The content in " + path + " is null!");
        }
        Matcher matcher = Pattern.compile(regex).matcher(content);
        Map<String,ArrayList<Integer>> result = new HashMap<String,ArrayList<Integer>>();
        ArrayList<Integer> value = new ArrayList<Integer>();
        String key = "";
        while (matcher.find()) {
            key = matcher.group();
            if (result.containsKey(key)) {
                value = result.get(key);
                value.add(matcher.start());
                result.put(key,value);
                continue;
            }
            result.put(matcher.group(), new ArrayList<Integer>(Arrays.asList(matcher.start())));
        }
        return result;
    }
    public static void main(String[] args) {
        String path = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/Exercise25.java";
        String regex = "\\w+";
        System.out.println(statistic(path,regex));
    }
}

Exercise 26

MyReader.java
package com.ciaoshen.thinkinjava.chapter11;
import java.io.*;

public class MyReader {
    private static String spliter = "\n";
    public MyReader(){}
    public MyReader(String s) {
        spliter = s;
    }
    public String readFile(String path) {
        StringBuilder sb = new StringBuilder();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(path)));
            String line = "";
            try {
                while (true) {
                    line = br.readLine();
                    if (line == null) {
                        break;
                    }
                    sb.append(line + spliter);
                }
            } finally {
                br.close();
            }
        } catch(FileNotFoundException e) {
            throw new RuntimeException(e);
        } catch(IOException e) {
            throw new RuntimeException(e);
        }
        return sb.toString();
    }
    private class TestUnit {
        private final String WRONGPATH = "/Users/HelloKitty/hello.java";
        private final String RIGHTPATH = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/MyReader.java";
        private void testReadFile() {
            System.out.println(readFile(RIGHTPATH));
            System.out.println(readFile(WRONGPATH));
        }
    }
    public static void main(String[] args) {
        TestUnit test = new MyReader().new TestUnit();
        test.testReadFile();
    }
}
Exercise25.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;
import java.util.regex.*;

// statistics the word and their positions in the file
public class Exercise25 {
    public static Map<String,ArrayList<Integer>> statistic(String path, String regex) {
        if (path == null || regex == null) {
            throw new RuntimeException("Argument content or regex is null!");
        }
        String content = new MyReader().readFile(path);
        if (content == null) {
            throw new RuntimeException("The content in " + path + " is null!");
        }
        Matcher matcher = Pattern.compile(regex).matcher(content);
        Map<String,ArrayList<Integer>> result = new HashMap<String,ArrayList<Integer>>();
        ArrayList<Integer> value = new ArrayList<Integer>();
        String key = "";
        while (matcher.find()) {
            key = matcher.group();
            if (result.containsKey(key)) {
                value = result.get(key);
                value.add(matcher.start());
                result.put(key,value);
                continue;
            }
            result.put(matcher.group(), new ArrayList<Integer>(Arrays.asList(matcher.start())));
        }
        return result;
    }
    public static void main(String[] args) {
        String path = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/Exercise25.java";
        String regex = "\\w+";
        System.out.println(statistic(path,regex));
    }
}
Exercise26.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise26 {
    public static LinkedHashMap<String,ArrayList<Integer>> sortedStatistic(String path, String regex) {
        Map<String,ArrayList<Integer>> shuffleWordMap = Exercise25.statistic(path,regex);
        Map<Integer,String> indexMap = getIndexMap(shuffleWordMap);
        List<Map.Entry<Integer,String>> indexList = new ArrayList<Map.Entry<Integer,String>>();
        indexList.addAll(indexMap.entrySet());
        Collections.sort(indexList, new Comparator<Map.Entry<Integer,String>>() {
            public int compare(Map.Entry<Integer,String> entry1, Map.Entry<Integer,String> entry2) {
                return entry1.getKey().compareTo(entry2.getKey());
            }
        });
        LinkedHashMap<String,ArrayList<Integer>> sortedWordMap = new LinkedHashMap<String,ArrayList<Integer>>();
        for (Map.Entry<Integer,String> entry : indexList) {
            String word = entry.getValue();
            sortedWordMap.put(word,shuffleWordMap.get(word));
        }
        return sortedWordMap;
    }
    public static Map<Integer,String> getIndexMap(Map<String,ArrayList<Integer>> shuffleMap) {
        Map<Integer,String> resultIndex = new HashMap<Integer,String>();
        for (Map.Entry<String,ArrayList<Integer>> entry : shuffleMap.entrySet()) {
            resultIndex.put(entry.getValue().get(0),entry.getKey());
        }
        return resultIndex;
    }
    public static void main(String[] args) {
        String path = "/Users/Wei/java/com/ciaoshen/thinkinjava/chapter11/Exercise25.java";
        String regex = "\\w+";
        System.out.println(sortedStatistic(path,regex));
    }
}

Exercise 27

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;
import java.lang.reflect.*;

public class Exercise27 {
    private static enum LinuxCommand {
        CD,LS,GREP,FIND,CP,MV,RM,PS,KILL,FILE,TAR,CAT;
        public String toString() {
            return name().toLowerCase();
        }
        public static LinuxCommand random() {
            Random rand = new Random();
            LinuxCommand[] values = LinuxCommand.class.getEnumConstants();
            return values[rand.nextInt(values.length)];
        }
    }
    public static class Command {
        private static int count = 0;
        private final int ID = ++count;
        private final String COMMAND;
        public Command(String str) {
            COMMAND = str;
        }
        public void operation() {
            System.out.println(this);
        }
        public String toString() {
            return "Command#" + ID + ": " + COMMAND;
        }
    }
    public static Queue<Command> fillCommandQueue(int size) {
        Queue<Command> queue = new LinkedList<Command>();
        for (int i = 0; i < size; i++) {
            queue.add(new Command(LinuxCommand.random().toString()));
        }
        return queue;
    }
    public static void printCommands(Queue<Command> commands) {
        for (Command command : commands) {
            command.operation();
        }
    }
    public static void main(String[] args) {
        //System.out.println(fillCommandQueue(20));
        printCommands(fillCommandQueue(20));
    }
}

Exercise 28

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise28 {
    public static void main(String[] args) {
        Random rand = new Random();
        PriorityQueue<Double> pq = new PriorityQueue<Double>();
        for (int i = 0; i < 10; i++) {
            pq.offer(rand.nextDouble());
        }
        for (int i = 0; i < 10; i++) {
            System.out.println(pq.poll());
        }
    }
}

Exercise 29

要么构造PriorityQueue的时候给一个Comparator。不然,PriorityQueue里的元素必须实现Comparable接口。

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise29 {
    private static class NoMemberClass extends Object {}
    public static void main(String[] args) {
        PriorityQueue<NoMemberClass> pq = new PriorityQueue<NoMemberClass>();
        for (int i = 0; i < 10; i++) {
            pq.offer(new NoMemberClass());
        }
    }
}

####Exercise 30

Exercise30.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise30 {
    private static enum LinuxCommand {
        CD,LS,GREP,FIND,CP,MV,RM,PS,KILL,FILE,TAR,CAT;
        public String toString() {
            return name().toLowerCase();
        }
        private static LinuxCommand random() {
            Random rand = new Random();
            LinuxCommand[] values = LinuxCommand.class.getEnumConstants();
            return values[rand.nextInt(values.length)];
        }
        private static LinuxCommand[] randomProgram(int size) {
            LinuxCommand[] program = new LinuxCommand[size];
            for (int i = 0; i < size; i++) {
                program[i] = random();
            }
            return program;
        }
    }
    public static class CommandSequence implements Collection<LinuxCommand> {
        // object array
        private LinuxCommand[] program;
        private int cursor = 0;
        public CommandSequence(int size) {
            program = LinuxCommand.randomProgram(size);
        }
        public boolean add(LinuxCommand c) {    //数组如果满了,循环从头插入
            if (c == null) {
                return false;
            }
            program[cursor++] = c;
            if (cursor == program.length) {
                cursor = 0;
            }
            return true;
        }
        public boolean addAll(Collection<? extends LinuxCommand> c) {
            if (c == null || c.isEmpty()) {
                return false;
            }
            for (LinuxCommand command : c) {
                if (!add(command)) {
                    return false;
                }
            }
            return true;
        }
        public void clear() {
            program = new LinuxCommand[program.length];
        }
        public boolean contains(Object o) {
            LinuxCommand c = (LinuxCommand)o;
            for (LinuxCommand ele : program) {
                if (ele == c) {
                    return true;
                }
            }
            return false;
        }
        public boolean containsAll(Collection<?> c) {
            if (c == null || c.isEmpty()) {
                return false;
            }
            for (Object o : c) {
                if (! contains(o)) {
                    return false;
                }
            }
            return true;
        }
        public boolean isEmpty() {
            return size() == 0;
        }
        public boolean remove(Object o) {
            if (!(o instanceof LinuxCommand)) {
                return false;
            }
            for (int i = 0; i < program.length; i++) {
                if (program[i] == (LinuxCommand)o) {
                    program[i] = null;
                    return true;
                }
            }
            return false;
        }
        public boolean removeAll(Collection<?> c) {
            boolean changed = false;
            if (c == null || c.isEmpty()) {
                return changed;
            }
            for (Object o : c) {
                if (remove(o)) {
                    changed = true;
                }
            }
            return changed;
        }
        public boolean retainAll(Collection<?> c) {
            boolean changed = false;
            if (c == null || c.isEmpty()) {
                return changed;
            }
            for (Object o : this) {
                if (!c.contains(o)) {
                    if(remove(o)) {
                        changed = true;
                    }
                }
            }
            return changed;
        }
        public Object[] toArray() {
            Object[] result = new Object[program.length];
            for (int i = 0; i < program.length; i++) {
                result[i] = program[i];
            }
            return result;
        }
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] array) {
            Object[] result = new Object[program.length];
            for (int i = 0; i < program.length; i++) {
                result[i] = program[i];
            }
            return (T[])result;
        }
        public int size() { return program.length; }
        public Iterator<LinuxCommand> iterator() {
            return new Iterator<LinuxCommand>() {
                private int index = 0;
                public boolean hasNext() {
                    return index < program.length;
                }
                public LinuxCommand next() { return program[index++]; }
                public void remove() { // Not implemented
                    throw new UnsupportedOperationException();
                }
            };
        }
    }
    public static class InterfaceVsIterator {
        public static <T> void display(Collection<T> c) {
            for (T ele : c) {
                System.out.println(ele);
            }
        }
        public static <T> void display(Iterator<T> ite) {
            while (ite.hasNext()) {
                System.out.println(ite.next());
            }
        }
    }
    public static void main(String[] args) {
        CommandSequence c = new CommandSequence(10);
        InterfaceVsIterator.display(c);
        InterfaceVsIterator.display(c.iterator());
    }
}
Exercise30V2.java

也有个偷懒的办法,只写一个Iterator类和iterator()方法。其他用不到方法都抛出UnsupportedOperationException。

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise30V2 {
    private static enum LinuxCommand {
        CD,LS,GREP,FIND,CP,MV,RM,PS,KILL,FILE,TAR,CAT;
        public String toString() {
            return name().toLowerCase();
        }
        private static LinuxCommand random() {
            Random rand = new Random();
            LinuxCommand[] values = LinuxCommand.class.getEnumConstants();
            return values[rand.nextInt(values.length)];
        }
        private static LinuxCommand[] randomProgram(int size) {
            LinuxCommand[] program = new LinuxCommand[size];
            for (int i = 0; i < size; i++) {
                program[i] = random();
            }
            return program;
        }
    }
    public static class CommandSequence implements Collection<LinuxCommand> {
        // object array
        private LinuxCommand[] program;
        private int cursor = 0; //current pointer
        public CommandSequence(int size) {
            program = LinuxCommand.randomProgram(size);
        }
        public boolean add(LinuxCommand c) {    //数组如果满了,循环从头插入
            throw new UnsupportedOperationException();
        }
        public boolean addAll(Collection<? extends LinuxCommand> c) {
            throw new UnsupportedOperationException();
        }
        public void clear() {
            throw new UnsupportedOperationException();
        }
        public boolean contains(Object o) {
            throw new UnsupportedOperationException();
        }
        public boolean containsAll(Collection<?> c) {
            throw new UnsupportedOperationException();
        }
        public boolean isEmpty() {
            throw new UnsupportedOperationException();
        }
        public boolean remove(Object o) {
            throw new UnsupportedOperationException();
        }
        public boolean removeAll(Collection<?> c) {
            throw new UnsupportedOperationException();
        }
        public boolean retainAll(Collection<?> c) {
            throw new UnsupportedOperationException();
        }
        public Object[] toArray() {
            throw new UnsupportedOperationException();
        }
        public <T> T[] toArray(T[] array) {
            throw new UnsupportedOperationException();
        }
        public int size() {
            throw new UnsupportedOperationException();
        }
        public Iterator<LinuxCommand> iterator() {
            return new Iterator<LinuxCommand>() {
                private int index = 0;
                public boolean hasNext() {
                    return index < program.length;
                }
                public LinuxCommand next() { return program[index++]; }
                public void remove() { // Not implemented
                    throw new UnsupportedOperationException();
                }
            };
        }
    }
    public static class InterfaceVsIterator {
        public static <T> void display(Collection<T> c) {
            for (T ele : c) {
                System.out.println(ele);
            }
        }
        public static <T> void display(Iterator<T> ite) {
            while (ite.hasNext()) {
                System.out.println(ite.next());
            }
        }
    }
    public static void main(String[] args) {
        CommandSequence c = new CommandSequence(10);
        InterfaceVsIterator.display(c);
        InterfaceVsIterator.display(c.iterator());
    }
}

Exercise 31

package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise31 {
    public static class Shape {
        public void draw() {}
        public void erase() {}
    }
    public static class Circle extends Shape {
        public void draw() { System.out.println("Circle.draw()"); }
        public void erase() { System.out.println("Circle.erase()"); }
    }
    public static class Square extends Shape {
        public void draw() { System.out.println("Square.draw()"); }
        public void erase() { System.out.println("Square.erase()"); }
    }
    public static class Triangle extends Shape {
        public void draw() { System.out.println("Triangle.draw()"); }
        public void erase() { System.out.println("Triangle.erase()"); }
    }
    public static class RandomShapeGenerator implements Iterable<Shape> {
        private Random rand = new Random();
        private final int size;
        public RandomShapeGenerator(int num) {
            size = num;
        }
        public Iterator<Shape> iterator() {
            return new Iterator<Shape>() {
                private int index = 0;
                public boolean hasNext() {
                    return index < size;
                }
                public Shape next() {
                    index++;
                    switch(rand.nextInt(3)) {
                        default:
                        case 0: return new Circle();
                        case 1: return new Square();
                        case 2: return new Triangle();
                    }
                }
            };
        }
    }
    public static void main(String[] args) {
        int shapeNum = 10;
        RandomShapeGenerator gen = new RandomShapeGenerator(shapeNum);
        for (Shape s : gen) {
            s.draw();
        }
    }
}

Exercise 32

LinuxCommand.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public enum LinuxCommand {
    CD,LS,GREP,FIND,CP,MV,RM,PS,KILL,FILE,TAR,CAT;
    public String toString() {
        int id = ordinal() + 1;
        String name = name().toLowerCase();
        return "Command#" + id + ": " + name;
    }
    public static LinuxCommand random() {
        Random rand = new Random();
        LinuxCommand[] values = LinuxCommand.class.getEnumConstants();
        return values[rand.nextInt(values.length)];
    }
    public static LinuxCommand orderGet(int index) {
        LinuxCommand[] values = LinuxCommand.class.getEnumConstants();
        return values[(index % values.length)];
    }
    public static LinuxCommand[] randomProgram(int size) {
        LinuxCommand[] program = new LinuxCommand[size];
        for (int i = 0; i < size; i++) {
            program[i] = random();
        }
        return program;
    }
    public static LinuxCommand[] orderProgram(int size) {
        LinuxCommand[] program = new LinuxCommand[size];
        for (int i = 0; i < size; i++) {
            program[i] = orderGet(i);
        }
        return program;
    }
}
Exercise32.java
package com.ciaoshen.thinkinjava.chapter11;
import java.util.*;

public class Exercise32 {
    public static class CommandSequence {
        protected final LinuxCommand[] commands;
        public CommandSequence(int size) {
            commands = LinuxCommand.orderProgram(size);
        }
    }
    public static class NonCollectionCommandSequence extends CommandSequence implements Iterable<LinuxCommand> {
        public NonCollectionCommandSequence(int size) {
            super(size);
        }
        public Iterator<LinuxCommand> iterator() {
            return new Iterator<LinuxCommand>() {
                private int index = 0;
                public boolean hasNext() {
                    return index < commands.length;
                }
                public LinuxCommand next() {
                    return commands[index++];
                }
            };
        }
    }
    public static class MultiIterableCommandSequence extends NonCollectionCommandSequence {
        public MultiIterableCommandSequence(int size) {
            super(size);
        }
        public Iterable<LinuxCommand> reverse() {
            return new Iterable<LinuxCommand>() {
                public Iterator<LinuxCommand> iterator() {
                    return new Iterator<LinuxCommand>() {
                        private int index = commands.length-1;  //begin from the last element
                        public boolean hasNext() {
                            return index >= 0;
                        }
                        public LinuxCommand next() {
                            return commands[index--];
                        }
                    };
                }
            };
        }
        public Iterable<LinuxCommand> shuffle() {
            return new Iterable<LinuxCommand>() {
                public Iterator<LinuxCommand> iterator() {
                    ArrayList<LinuxCommand> commandsCopyList = new ArrayList<LinuxCommand>(Arrays.asList(commands));
                    Collections.shuffle(commandsCopyList);
                    return commandsCopyList.iterator();
                }
            };
        }
    }
    public static void main(String[] args) {
        MultiIterableCommandSequence commands = new MultiIterableCommandSequence(10);
        System.out.println("NORMAL ORDER >>>");
        for (LinuxCommand command : commands) {
            System.out.println(command);
        }
        System.out.println("REVERSE ORDER >>>");
        for (LinuxCommand command : commands.reverse()) {
            System.out.println(command);
        }
        System.out.println("SHUFFLE ORDER >>>");
        for (LinuxCommand command : commands.shuffle()) {
            System.out.println(command);
        }
    }
}