Java Knowledge series 7
2024-09-04 11:55:21
Pepole who make a greate contribution on common libaraies deserve our respect.
Component(Widget) / STL / Container(Collection)
- 合成不会强迫我们的程序设计进入继承的分级结构中has-a relationship。同时，合成显得更加灵活，因为可以动态选择一种类型（以及行为），而继承要求在编译期间准确地知道一种类型。
- Java的工具（实用程序）库提供了一些“集合类”（亦称作“容器类”，但该术语已由AWT使用，所以这里仍采用“集合”这一称呼）。利用这些集合类，我们可以容纳乃至操纵自己的对象。Aggregate; container;
- 有两方面的问题将数组与其他集合类型区分开来：效率efficiency 和类型type。
- 对于Java来说，为保存和访问一系列对象（实际是对象的句柄 handle, or pointer in C++）数组，最有效的方法莫过于数组。数组实际代表一个简单的线性序列，它使得元素的访问速度非常快，但我们却要为这种速度付出代价：创建一个数组对象时，它的大小是固定的，而且不可在那个数组对象的“存在时间”内发生改变。可创建特定大小的一个数组，然后假如用光了存储空间，就再创建一个新数组，将所有句柄从旧数组移到新数组。这属于“矢量”（Vector）类的行为.
- 在Java中，由于对数组和集合都要进行范围检查，所以对性能有一定的影响。
- 这些类都涉及对对象的处理——好象它们没有特定的类型。换言之，它们将其当作Object类型处理（Object类型是Java中所有类的“根”类）。从某个角度看，这种处理方法是非常合理的：我们仅需构建一个集合，然后任何Java对象都可以进入那个集合（除基本数据类型外built-in type——可用Java的基本类型封装类将其作为常数置入集合，或者将其封装到自己的类内，作为可以变化的值使用）。这再一次反映了数组优于常规集合：创建一个数组时，可令其容纳一种特定的类型。这意味着可进行编译期类型检查，预防自己设置了错误的类型，或者错误指定了准备提取的类型。
- 无论使用的数组属于什么类型，数组标识符实际都是指向真实对象的一个句柄。那些对象本身是在内存“堆”里创建的。堆对象既可“隐式”创建（即默认产生），亦可“显式”创建（即明确指定，用一个new表达式）。堆对象的一部分（实际是我们能访问的唯一字段或方法）是只读的length（长度）成员，它告诉我们那个数组对象里最多能容纳多少元素。
- 集合类只能容纳对象句柄。但对一个数组，却既可令其直接容纳基本类型的数据，亦可容纳指向对象的句柄。利用象Integer、Double之类的“封装器”类，可将基本数据类型的值置入一个集合里。
- 象C和C++这样的语言会使问题复杂化，因为我们不能返回一个数组，只能返回指向数组的一个指针。这样就非常麻烦，因为很难控制数组的“存在时间”，它很容易造成内存“漏洞”的出现。Java采用的是类似的方法，但我们能“返回一个数组”。当然，此时返回的实际仍是指向数组的指针。但在Java里，我们永远不必担心那个数组的是否可用——只要需要，它就会自动存在。而且垃圾收集器会在我们完成后自动将其清除。
- 为容纳一组对象，最适宜的选择应当是数组。而且假如容纳的是一系列基本数据类型，更是必须采用数组。Have to use array when containing built-in type.
- 当我们编写程序时，通常并不能确切地知道最终需要多少个对象。有些时候甚至想用更复杂的方式来保存对象。为解决这个问题，Java提供了四种类型的“集合类”：Vector（矢量）、BitSet（位集）、Stack（堆栈）以及Hashtable（散列表）。
- 使用Java集合的“缺点”是在将对象置入一个集合时丢失了类型信息。之所以会发生这种情况，是由于当初编写集合时，那个集合的程序员根本不知道用户到底想把什么类型置入集合。若指示某个集合只允许特定的类型，会妨碍它成为一个“常规用途”的工具，为用户带来麻烦。为解决这个问题，集合实际容纳的是类型为Object的一些对象的句柄。这种类型当然代表Java中的所有对象，因为它是所有类的根。当然，也要注意这并不包括基本数据类型，因为它们并不是从“任何东西”继承来的。(It is solved with template in C++)这是一个很好的方案，只是不适用下述场合：
- (1) 将一个对象句柄置入集合时，由于类型信息会被抛弃，所以任何类型的对象都可进入我们的集合——即便特别指示它只能容纳特定类型的对象。举个例子来说，虽然指示它只能容纳猫，但事实上任何人都可以把一条狗扔进来。
- (2) 由于类型信息不复存在，所以集合能肯定的唯一事情就是自己容纳的是指向一个对象的句柄。正式使用它之前，必须对其进行造型，使其具有正确的类型。
- 参数化类型 parameterization type这类问题并不是孤立的——我们许多时候都要在其他类型的基础上创建新类型。此时，在编译期间拥有特定的类型信息是非常有帮助的。这便是“参数化类型”的概念。在C++中，它由语言通过“模板Template” 获得了直接支持。至少，Java保留了关键字generic，期望有一天能够支持参数化类型。但我们现在无法确定这一天何时会来临。
- 可利用“反复器”（Iterator）的概念达到这个目的。它可以是一个对象，作用是遍历一系列对象，并选择那个序列中的每个对象，同时不让客户程序员知道或关注那个序列的基础结构。此外，我们通常认为反复器是一种“轻量级”对象；也就是说，创建它只需付出极少的代价。但也正是由于这个原因，我们常发现反复器存在一些似乎很奇怪的限制。例如，有些反复器只能朝一个方向移动。Java的Enumeration（枚举，注释②）便是具有这些限制的一个反复器的例子。除下面这些外，不可再用它做其他任何事情：
- (1) 用一个名为elements()的方法要求集合为我们提供一个Enumeration。我们首次调用它的nextElement()时 The de facto meaning is to move to next element and return the current element，这个Enumeration会返回序列中的第一个元素。
- (2) 用nextElement()获得下一个对象。
- (3) 用hasMoreElements()检查序列中是否还有更多的对象。
- ②：“反复器”这个词在C++和OOP的其他地方是经常出现的，所以很难确定为什么Java的开发者采用了这样一个奇怪的名字。Java 1.2的集合库修正了这个问题以及其他许多问题。
- BitSet实际是由“二进制位”构成的一个Vector。如果希望高效率地保存大量“开－关”信息，就应使用BitSet。它只有从尺寸的角度看才有意义；如果希望的高效率的访问，那么它的速度会比使用一些固有类型的数组慢一些。此外，BitSet的最小长度是一个长整数（Long）的长度：64位。这意味着假如我们准备保存比这更小的数据，如8位数据，那么BitSet就显得浪费了。所以最好创建自己的类，用它容纳自己的标志位。
- Stack有时也可以称为“后入先出”（LIFO）集合。换言之，我们在堆栈里最后“压入”的东西将是以后第一个“弹出”的。和其他所有Java集合一样，我们压入和弹出的都是“对象”，所以必须对自己弹出的东西进行“造型”。一种很少见的做法是拒绝使用Vector作为一个Stack的基本构成元素，而是从Vector里“继承”一个Stack。这样一来，它就拥有了一个Vector的所有特征及行为，另外加上一些额外的Stack行为。很难判断出设计者到底是明确想这样做，还是属于一种固有的设计。
- 这种“从一系列对象中选择”的概念亦可叫作一个“映射 map”、“字典 dictionary”或者“关联数组 relation array”。从概念上讲，它看起来象一个Vector，但却不是通过数字来查找对象，而是用另一个对象来查找它们！这通常都属于一个程序中的重要进程。
- 这个概念具体反映到抽象类Dictionary身上。该类的接口是非常直观的size()告诉我们其中包含了多少元素；isEmpty()判断是否包含了元素（是则为true）；put(Object key, Object value)添加一个值（我们希望的东西），并将其同一个键关联起来（想用于搜索它的东西）；get(Object key)获得与某个键对应的值；而remove(Object Key)用于从列表中删除“键－值”对。还可以使用枚举技术：keys()产生对键的一个枚举（Enumeration）；而elements()产生对所有值的一个枚举。这便是一个Dictionary（字典）的全部。
- 散列码可以获取对象中的信息，然后将其转换成那个对象“相对唯一”的整数（int）。所有对象都有一个散列码，而hashCode()是根类Object的一个方法。Hashtable获取对象的hashCode()，然后用它快速查找键。这样可使性能得到大幅度提升（④）。
- 大家或许认为此时要做的全部事情就是正确地覆盖hashCode()。但这样做依然行不能，除非再做另一件事情：覆盖也属于Object一部分的equals()。当散列表试图判断我们的键是否等于表内的某个键时，就会用到这个方法。同样地，默认的Object.equals()只是简单地比较对象地址，了在散列表中将自己的类作为键使用，必须同时覆盖override hashCode() 和equals() befor objectize
- 调用了一个名为getProperties()的static方法，用于获得一个特殊的Properties对象，对系统的某些特征进行描述。list()属于Properties的一个方法，可将内容发给我们选择的任何流式输出。也有一个save()方法，可用它将属性列表写入一个文件，以便日后用load()方法读取。尽管Properties类是从Hashtable继承的，但它也包含了一个散列表，用于容纳“默认”属性的列表。所以假如没有在主列表里找到一个属性，就会自动搜索默认属性。
- JGL实现了许多功能，可满足对一个集合库的大多数常规需求，它与C++的模板机制非常相似。JGL包括相互链接起来的列表、设置、队列、映射、堆栈、序列以及反复器，它们的功能比Enumeration（枚举）强多了。同时提供了一套完整的算法，如检索和排序等。
- JGL已包括到一些厂商发行的Java套件中，而且ObjectSpace公司自己也允许所有用户免费使用JGL，包括商业性的使用。详细情况和软件下载可访问http://www.ObjectSpace.com。与JGL配套提供的联机文档做得非常好，可作为自己的一个绝佳起点使用。
- 我感觉特别好的一个是用“反复器”（Inerator）代替了“枚举”（Enumeration）。
- 此次重新设计也加强了集合库的功能。现在新增的行为包括链接列表、队列以及撤消组队（即“双终点队列”）。集合库的设计是相当困难的（会遇到大量库设计问题）。在C++中，STL用多个不同的类来覆盖基础。这种做法比起STL以前是个很大的进步，那时根本没做这方面的考虑。但仍然没有很好地转换到Java里面。结果就是一大堆特别容易混淆的类。在另一个极端，我曾发现一个集合库由单个类构成：colleciton，它同时作为Vector和Hashtable使用。新集合库的设计者则希望达到一种新的平衡：实现人们希望从一个成熟集合库上获得的完整功能，同时又要比STL和其他类似的集合库更易学习和使用。这样得到的结果在某些场合显得有些古怪。但和早期Java库的一些决策不同，这些古怪之处并非偶然出现的，而是以复杂性作为代价，在进行仔细权衡之后得到的结果。这样做也许会延长人们掌握一些库概念的时间，但很快就会发现自己很乐于使用那些新工具，而且变得越来越离不了它。
- 新的集合库考虑到了“容纳自己对象”的问题，并将其分割成两个明确的概念：
- (1) 集合（Collection）：一组单独的元素，通常应用了某种规则。在这里，一个List（列表）必须按特定的顺序容纳元素，而一个Set（集）不可包含任何重复的元素。相反，“包”（Bag）的概念未在新的集合库中实现，因为“列表”已提供了类似的功能。
- (2) 映射（Map）：一系列“键－值”对（这已在散列表身上得到了充分的体现）。从表面看，这似乎应该成为一个“键－值”对的“集合”，但假若试图按那种方式实现它，就会发现实现过程相当笨拙。这进一步证明了应该分离成单独的概念。另一方面，可以方便地查看Map的某个部分。只需创建一个集合，然后用它表示那一部分即可。这样一来，Map就可以返回自己键的一个Set、一个包含自己值的List或者包含自己“键－值”对的一个List。
- 利用iterator()方法，所有集合都能生成一个“反复器”（Iterator）。反复器其实就象一个“枚举”（Enumeration），是后者的一个替代物，只是：
- (1) 它采用了一个历史上默认、而且早在OOP中得到广泛采纳的名字（反复器）。
- (2) 采用了比Enumeration更短的名字：hasNext()代替了hasMoreElement()，而next()代替了nextElement()。
- (3) 添加了一个名为remove()的新方法，可删除由Iterator生成的上一个元素。所以每次调用next()的时候，只需调用remove()一次。在SimpleCollection.java中，大家可看到创建了一个反复器，并用它在集合里遍历，打印出每个元素。
- 用一个集合能做的所有事情（亦可对Set和List做同样的事情，尽管List还提供了一些额外的功能）。Map不是从Collection继承的，所以要单独对待
- Set拥有与Collection完全相同的接口，所以和两种不同的List不同，它没有什么额外的功能。相反，Set完全就是一个Collection，只是具有不同的行为（这是实例和多形性最理想的应用：用于表达不同的行为）。在这里，一个Set只允许每个对象存在一个实例（正如大家以后会看到的那样，一个对象的“值”的构成是相当复杂的）。
- Set（接口） 添加到Set的每个元素都必须是独一无二的；否则Set就不会添加重复的元素。添加到Set里的对象必须定义equals()，从而建立对象的唯一性。Set拥有与Collection完全相同的接口。一个Set不能保证自己可按任何特定的顺序维持自己的元素
- HashSet＊ 用于除非常小的以外的所有Set。对象也必须定义hashCode()
- ArraySet 由一个数组后推得到的Set。面向非常小的Set设计，特别是那些需要频繁创建和删除的。对于小Set，与HashSet相比，ArraySet创建和反复所需付出的代价都要小得多。但随着Set的增大，它的性能也会大打折扣。不需要HashCode()
- TreeSet 由一个“红黑树”后推得到的顺序Set（注释⑦）。这样一来，我们就可以从一个Set里提到一个顺序集合
- Map（接口） 维持“键－值”对应关系（对），以便通过一个键查找相应的值
- HashMap＊ 基于一个散列表实现（用它代替Hashtable）。针对“键－值”对的插入和检索，这种形式具有最稳定的性能。可通过构建器对这一性能进行调整，以便设置散列表的“能力”和“装载因子”ArrayMap 由一个ArrayList后推得到的Map。对反复的顺序提供了精确的控制。面向非常小的Map设计，特别是那些需要经常创建和删除的。对于非常小的Map，创建和反复所付出的代价要比HashMap低得多。但在Map变大以后，性能也会相应地大幅度降低TreeMap 在一个“红－黑”树的基础上实现。
- 可在ArraySet以及HashSet间作出选择，具体取决于Set的大小（如果需要从一个Set中获得一个顺序列表，请用TreeSet；注释⑧）
- 选择不同的Map实施方案时，注意Map的大小对于性能的影响是最大的.
- Arrays类为所有基本数据类型的数组提供了一个过载的sort()和binarySearch()，它们亦可用于String和Object。
- 可用与数组相同的形式排序和搜索一个列表（List）。用于排序和搜索列表的静态方法包含在类Collections中，但它们拥有与Arrays中差不多的签名：sort(List)用于对一个实现了Comparable的对象列表进行排序；binarySearch(List,Object)用于查找列表中的某个对象；sort(List,Comparator)利用一个“比较器”对一个列表进行排序；而binarySearch(List,Object,Comparator)则用于查找那个列表中的一个对象（注释⑨）。
- Synchronized关键字是“多线程”机制一个非常重要的部分。
- 数组包含了对象的数字化索引。它容纳的是一种已知类型的对象，所以在查找一个对象时，不必对结果进行造型处理。数组可以是多维的，而且能够容纳基本数据类型。但是，一旦把它创建好以后，大小便不能变化了。
- Vector（矢量）也包含了对象的数字索引——可将数组和Vector想象成随机访问集合。当我们加入更多的元素时，Vector能够自动改变自身的大小。但Vector只能容纳对象的句柄，所以它不可包含基本数据类型；而且将一个对象句柄从集合中取出来的时候，必须对结果进行造型处理。
- Hashtable（散列表）属于Dictionary（字典）的一种类型，是一种将对象（而不是数字）同其他对象关联到一起的方式。散列表也支持对对象的随机访问，事实上，它的整个设计方案都在突出访问的“高速度”。
- Stack（堆栈）是一种“后入先出”（LIFO）的队列.
• Collection Interfaces - Represent different types of collections, such as sets, lists and maps. These interfaces form the basis of the framework.
• General-purpose Implementations - Primary implementations of the collection interfaces.
• Legacy Implementations
- The collection classes from earlier releases, Vector and Hashtable,
have been retrofitted to implement the collection interfaces.
• Special-purpose Implementations
- Implementations designed for use in special situations. These
implementations display nonstandard performance characteristics, usage
restrictions, or behavior.
• Concurrent Implementations - Implementations designed for highly concurrent use.
• Wrapper Implementations - Add functionality, such as synchronization, to other implementations.
• Convenience Implementations - High-performance "mini-implementations" of the collection interfaces.
• Abstract Implementations - Partial implementations of the collection interfaces to facilitate custom implementations.
• Algorithms - Static methods that perform useful functions on collections, such as sorting a list.
• Infrastructure - Interfaces that provide essential support for the collection interfaces.
• Array Utilities
- Utility functions for arrays of primitives and reference objects.
Not, strictly speaking, a part of the Collections Framework, this
functionality was added to the Java platform at the same time and relies
on some of the same infrastructure.
Iterable Interface
import java.util.Iterator;
/**
* Instances of classes that implement this interface can be used with
* the enhanced for loop.
*
* @since 1.5
*/
public interface Iterable<T> { /**
* Returns an {@link Iterator} for the elements in this object.
*
* @return An {@code Iterator} instance.
*/
Iterator<T> iterator();
}
Collection Interface
package java.util; /**
* {@code Collection} is the root of the collection hierarchy. It defines operations on
* data collections and the behavior that they will have in all implementations
* of {@code Collection}s.
*
* All direct or indirect implementations of {@code Collection} should implement at
* least two constructors. One with no parameters which creates an empty
* collection and one with a parameter of type {@code Collection}. This second
* constructor can be used to create a collection of different type as the
* initial collection but with the same elements. Implementations of {@code Collection}
* cannot be forced to implement these two constructors but at least all
* implementations under {@code java.util} do.
*
* Methods that change the content of a collection throw an
* {@code UnsupportedOperationException} if the underlying collection does not
* support that operation, though it's not mandatory to throw such an {@code Exception}
* in cases where the requested operation would not change the collection. In
* these cases it's up to the implementation whether it throws an
* {@code UnsupportedOperationException} or not.
*
* Methods marked with (optional) can throw an
* {@code UnsupportedOperationException} if the underlying collection doesn't
* support that method.
*/
public interface Collection<E> extends Iterable<E> { /**
* Attempts to add {@code object} to the contents of this
* {@code Collection} (optional).
*
* After this method finishes successfully it is guaranteed that the object
* is contained in the collection.
*
* If the collection was modified it returns {@code true}, {@code false} if
* no changes were made.
*
* An implementation of {@code Collection} may narrow the set of accepted
* objects, but it has to specify this in the documentation. If the object
* to be added does not meet this restriction, then an
* {@code IllegalArgumentException} is thrown.
*
* If a collection does not yet contain an object that is to be added and
* adding the object fails, this method <i>must</i> throw an appropriate
* unchecked Exception. Returning false is not permitted in this case
* because it would violate the postcondition that the element will be part
* of the collection after this method finishes.
*
* @param object
* the object to add.
* @return {@code true} if this {@code Collection} is
* modified, {@code false} otherwise.
*
* @throws UnsupportedOperationException
* if adding to this {@code Collection} is not supported.
* @throws ClassCastException
* if the class of the object is inappropriate for this
* collection.
* @throws IllegalArgumentException
* if the object cannot be added to this {@code Collection}.
* @throws NullPointerException
* if null elements cannot be added to the {@code Collection}.
*/
public boolean add(E object); /**
* Attempts to add all of the objects contained in {@code Collection}
* to the contents of this {@code Collection} (optional). If the passed {@code Collection}
* is changed during the process of adding elements to this {@code Collection}, the
* behavior is not defined.
*
* @param collection
* the {@code Collection} of objects.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if adding to this {@code Collection} is not supported.
* @throws ClassCastException
* if the class of an object is inappropriate for this
* {@code Collection}.
* @throws IllegalArgumentException
* if an object cannot be added to this {@code Collection}.
* @throws NullPointerException
* if {@code collection} is {@code null}, or if it
* contains {@code null} elements and this {@code Collection} does
* not support such elements.
*/
public boolean addAll(Collection<? extends E> collection); /**
* Removes all elements from this {@code Collection}, leaving it empty (optional).
*
* @throws UnsupportedOperationException
* if removing from this {@code Collection} is not supported.
*
* @see #isEmpty
* @see #size
*/
public void clear(); /**
* Tests whether this {@code Collection} contains the specified object. Returns
* {@code true} if and only if at least one element {@code elem} in this
* {@code Collection} meets following requirement:
* {@code (object==null ? elem==null : object.equals(elem))}.
*
* @param object
* the object to search for.
* @return {@code true} if object is an element of this {@code Collection},
* {@code false} otherwise.
* @throws ClassCastException
* if the object to look for isn't of the correct
* type.
* @throws NullPointerException
* if the object to look for is {@code null} and this
* {@code Collection} doesn't support {@code null} elements.
*/
public boolean contains(Object object); /**
* Tests whether this {@code Collection} contains all objects contained in the
* specified {@code Collection}. If an element {@code elem} is contained several
* times in the specified {@code Collection}, the method returns {@code true} even
* if {@code elem} is contained only once in this {@code Collection}.
*
* @param collection
* the collection of objects.
* @return {@code true} if all objects in the specified {@code Collection} are
* elements of this {@code Collection}, {@code false} otherwise.
* @throws ClassCastException
* if one or more elements of {@code collection} isn't of the
* correct type.
* @throws NullPointerException
* if {@code collection} contains at least one {@code null}
* element and this {@code Collection} doesn't support {@code null}
* elements.
* @throws NullPointerException
* if {@code collection} is {@code null}.
*/
public boolean containsAll(Collection<?> collection); /**
* Compares the argument to the receiver, and returns true if they represent
* the <em>same</em> object using a class specific comparison.
*
* @param object
* the object to compare with this object.
* @return {@code true} if the object is the same as this object and
* {@code false} if it is different from this object.
* @see #hashCode
*/
public boolean equals(Object object); /**
* Returns an integer hash code for the receiver. Objects which are equal
* return the same value for this method.
*
* @return the receiver's hash.
*
* @see #equals
*/
public int hashCode(); /**
* Returns if this {@code Collection} contains no elements.
*
* @return {@code true} if this {@code Collection} has no elements, {@code false}
* otherwise.
*
* @see #size
*/
public boolean isEmpty(); /**
* Returns an instance of {@link Iterator} that may be used to access the
* objects contained by this {@code Collection}. The order in which the elements are
* returned by the iterator is not defined. Only if the instance of the
* {@code Collection} has a defined order the elements are returned in that order.
*
* @return an iterator for accessing the {@code Collection} contents.
*/
public Iterator<E> iterator(); /**
* Removes one instance of the specified object from this {@code Collection} if one
* is contained (optional). The element {@code elem} that is removed
* complies with {@code (object==null ? elem==null : object.equals(elem)}.
*
* @param object
* the object to remove.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code Collection} is not supported.
* @throws ClassCastException
* if the object passed is not of the correct type.
* @throws NullPointerException
* if {@code object} is {@code null} and this {@code Collection}
* doesn't support {@code null} elements.
*/
public boolean remove(Object object); /**
* Removes all occurrences in this {@code Collection} of each object in the
* specified {@code Collection} (optional). After this method returns none of the
* elements in the passed {@code Collection} can be found in this {@code Collection}
* anymore.
*
* @param collection
* the collection of objects to remove.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
*
* @throws UnsupportedOperationException
* if removing from this {@code Collection} is not supported.
* @throws ClassCastException
* if one or more elements of {@code collection}
* isn't of the correct type.
* @throws NullPointerException
* if {@code collection} contains at least one
* {@code null} element and this {@code Collection} doesn't support
* {@code null} elements.
* @throws NullPointerException
* if {@code collection} is {@code null}.
*/
public boolean removeAll(Collection<?> collection); /**
* Removes all objects from this {@code Collection} that are not also found in the
* {@code Collection} passed (optional). After this method returns this {@code Collection}
* will only contain elements that also can be found in the {@code Collection}
* passed to this method.
*
* @param collection
* the collection of objects to retain.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code Collection} is not supported.
* @throws ClassCastException
* if one or more elements of {@code collection}
* isn't of the correct type.
* @throws NullPointerException
* if {@code collection} contains at least one
* {@code null} element and this {@code Collection} doesn't support
* {@code null} elements.
* @throws NullPointerException
* if {@code collection} is {@code null}.
*/
public boolean retainAll(Collection<?> collection); /**
* Returns a count of how many objects this {@code Collection} contains.
*
* @return how many objects this {@code Collection} contains, or Integer.MAX_VALUE
* if there are more than Integer.MAX_VALUE elements in this
* {@code Collection}.
*/
public int size(); /**
* Returns a new array containing all elements contained in this {@code Collection}.
*
* If the implementation has ordered elements it will return the element
* array in the same order as an iterator would return them.
*
* The array returned does not reflect any changes of the {@code Collection}. A new
* array is created even if the underlying data structure is already an
* array.
*
* @return an array of the elements from this {@code Collection}.
*/
public Object[] toArray(); /**
* Returns an array containing all elements contained in this {@code Collection}. If
* the specified array is large enough to hold the elements, the specified
* array is used, otherwise an array of the same type is created. If the
* specified array is used and is larger than this {@code Collection}, the array
* element following the {@code Collection} elements is set to null.
*
* If the implementation has ordered elements it will return the element
* array in the same order as an iterator would return them.
*
* {@code toArray(new Object[0])} behaves exactly the same way as
* {@code toArray()} does.
*
* @param array
* the array.
* @return an array of the elements from this {@code Collection}.
*
* @throws ArrayStoreException
* if the type of an element in this {@code Collection} cannot be
* stored in the type of the specified array.
*/
public <T> T[] toArray(T[] array);
}
List Interface
package java.util; /**
* A {@code List} is a collection which maintains an ordering for its elements. Every
* element in the {@code List} has an index. Each element can thus be accessed by its
* index, with the first index being zero. Normally, {@code List}s allow duplicate
* elements, as compared to Sets, where elements have to be unique.
*/
public interface List<E> extends Collection<E> {
/**
* Inserts the specified object into this {@code List} at the specified location.
* The object is inserted before the current element at the specified
* location. If the location is equal to the size of this {@code List}, the object
* is added at the end. If the location is smaller than the size of this
* {@code List}, then all elements beyond the specified location are moved by one
* position towards the end of the {@code List}.
*
* @param location
* the index at which to insert.
* @param object
* the object to add.
* @throws UnsupportedOperationException
* if adding to this {@code List} is not supported.
* @throws ClassCastException
* if the class of the object is inappropriate for this
* {@code List}.
* @throws IllegalArgumentException
* if the object cannot be added to this {@code List}.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location > size()}
*/
public void add(int location, E object); /**
* Adds the specified object at the end of this {@code List}.
*
* @param object
* the object to add.
* @return always true.
* @throws UnsupportedOperationException
* if adding to this {@code List} is not supported.
* @throws ClassCastException
* if the class of the object is inappropriate for this
* {@code List}.
* @throws IllegalArgumentException
* if the object cannot be added to this {@code List}.
*/
public boolean add(E object); /**
* Inserts the objects in the specified collection at the specified location
* in this {@code List}. The objects are added in the order they are returned from
* the collection's iterator.
*
* @param location
* the index at which to insert.
* @param collection
* the collection of objects to be inserted.
* @return true if this {@code List} has been modified through the insertion, false
* otherwise (i.e. if the passed collection was empty).
* @throws UnsupportedOperationException
* if adding to this {@code List} is not supported.
* @throws ClassCastException
* if the class of an object is inappropriate for this
* {@code List}.
* @throws IllegalArgumentException
* if an object cannot be added to this {@code List}.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || > size()}
*/
public boolean addAll(int location, Collection<? extends E> collection); /**
* Adds the objects in the specified collection to the end of this {@code List}. The
* objects are added in the order in which they are returned from the
* collection's iterator.
*
* @param collection
* the collection of objects.
* @return {@code true} if this {@code List} is modified, {@code false} otherwise
* (i.e. if the passed collection was empty).
* @throws UnsupportedOperationException
* if adding to this {@code List} is not supported.
* @throws ClassCastException
* if the class of an object is inappropriate for this
* {@code List}.
* @throws IllegalArgumentException
* if an object cannot be added to this {@code List}.
*/
public boolean addAll(Collection<? extends E> collection); /**
* Removes all elements from this {@code List}, leaving it empty.
*
* @throws UnsupportedOperationException
* if removing from this {@code List} is not supported.
* @see #isEmpty
* @see #size
*/
public void clear(); /**
* Tests whether this {@code List} contains the specified object.
*
* @param object
* the object to search for.
* @return {@code true} if object is an element of this {@code List}, {@code false}
* otherwise
*/
public boolean contains(Object object); /**
* Tests whether this {@code List} contains all objects contained in the
* specified collection.
*
* @param collection
* the collection of objects
* @return {@code true} if all objects in the specified collection are
* elements of this {@code List}, {@code false} otherwise.
*/
public boolean containsAll(Collection<?> collection); /**
* Compares the given object with the {@code List}, and returns true if they
* represent the <em>same</em> object using a class specific comparison. For
* {@code List}s, this means that they contain the same elements in exactly the same
* order.
*
* @param object
* the object to compare with this object.
* @return boolean {@code true} if the object is the same as this object,
* and {@code false} if it is different from this object.
* @see #hashCode
*/
public boolean equals(Object object); /**
* Returns the element at the specified location in this {@code List}.
*
* @param location
* the index of the element to return.
* @return the element at the specified location.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || >= size()}
*/
public E get(int location); /**
* Returns the hash code for this {@code List}. It is calculated by taking each
* element' hashcode and its position in the {@code List} into account.
*
* @return the hash code of the {@code List}.
*/
public int hashCode(); /**
* Searches this {@code List} for the specified object and returns the index of the
* first occurrence.
*
* @param object
* the object to search for.
* @return the index of the first occurrence of the object or -1 if the
* object was not found.
*/
public int indexOf(Object object); /**
* Returns whether this {@code List} contains no elements.
*
* @return {@code true} if this {@code List} has no elements, {@code false}
* otherwise.
* @see #size
*/
public boolean isEmpty(); /**
* Returns an iterator on the elements of this {@code List}. The elements are
* iterated in the same order as they occur in the {@code List}.
*
* @return an iterator on the elements of this {@code List}.
* @see Iterator
*/
public Iterator<E> iterator(); /**
* Searches this {@code List} for the specified object and returns the index of the
* last occurrence.
*
* @param object
* the object to search for.
* @return the index of the last occurrence of the object, or -1 if the
* object was not found.
*/
public int lastIndexOf(Object object); /**
* Returns a {@code List} iterator on the elements of this {@code List}. The elements are
* iterated in the same order that they occur in the {@code List}.
*
* @return a {@code List} iterator on the elements of this {@code List}
*
* @see ListIterator
*/
public ListIterator<E> listIterator(); /**
* Returns a list iterator on the elements of this {@code List}. The elements are
* iterated in the same order as they occur in the {@code List}. The iteration
* starts at the specified location.
*
* @param location
* the index at which to start the iteration.
* @return a list iterator on the elements of this {@code List}.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location > size()}
* @see ListIterator
*/
public ListIterator<E> listIterator(int location); /**
* Removes the object at the specified location from this {@code List}.
*
* @param location
* the index of the object to remove.
* @return the removed object.
* @throws UnsupportedOperationException
* if removing from this {@code List} is not supported.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || >= size()}
*/
public E remove(int location); /**
* Removes the first occurrence of the specified object from this {@code List}.
*
* @param object
* the object to remove.
* @return true if this {@code List} was modified by this operation, false
* otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code List} is not supported.
*/
public boolean remove(Object object); /**
* Removes all occurrences in this {@code List} of each object in the specified
* collection.
*
* @param collection
* the collection of objects to remove.
* @return {@code true} if this {@code List} is modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code List} is not supported.
*/
public boolean removeAll(Collection<?> collection); /**
* Removes all objects from this {@code List} that are not contained in the
* specified collection.
*
* @param collection
* the collection of objects to retain.
* @return {@code true} if this {@code List} is modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code List} is not supported.
*/
public boolean retainAll(Collection<?> collection); /**
* Replaces the element at the specified location in this {@code List} with the
* specified object. This operation does not change the size of the {@code List}.
*
* @param location
* the index at which to put the specified object.
* @param object
* the object to insert.
* @return the previous element at the index.
* @throws UnsupportedOperationException
* if replacing elements in this {@code List} is not supported.
* @throws ClassCastException
* if the class of an object is inappropriate for this
* {@code List}.
* @throws IllegalArgumentException
* if an object cannot be added to this {@code List}.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || >= size()}
*/
public E set(int location, E object); /**
* Returns the number of elements in this {@code List}.
*
* @return the number of elements in this {@code List}.
*/
public int size(); /**
* Returns a {@code List} of the specified portion of this {@code List} from the given start
* index to the end index minus one. The returned {@code List} is backed by this
* {@code List} so changes to it are reflected by the other.
*
* @param start
* the index at which to start the sublist.
* @param end
* the index one past the end of the sublist.
* @return a list of a portion of this {@code List}.
* @throws IndexOutOfBoundsException
* if {@code start < 0, start > end} or {@code end >
* size()}
*/
public List<E> subList(int start, int end); /**
* Returns an array containing all elements contained in this {@code List}.
*
* @return an array of the elements from this {@code List}.
*/
public Object[] toArray(); /**
* Returns an array containing all elements contained in this {@code List}. If the
* specified array is large enough to hold the elements, the specified array
* is used, otherwise an array of the same type is created. If the specified
* array is used and is larger than this {@code List}, the array element following
* the collection elements is set to null.
*
* @param array
* the array.
* @return an array of the elements from this {@code List}.
* @throws ArrayStoreException
* if the type of an element in this {@code List} cannot be stored
* in the type of the specified array.
*/
public <T> T[] toArray(T[] array);
}
Set Interface
package java.util; /**
* A {@code Set} is a data structure which does not allow duplicate elements.
*
* @since 1.2
*/
public interface Set<E> extends Collection<E> { /**
* Adds the specified object to this set. The set is not modified if it
* already contains the object.
*
* @param object
* the object to add.
* @return {@code true} if this set is modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* when adding to this set is not supported.
* @throws ClassCastException
* when the class of the object is inappropriate for this set.
* @throws IllegalArgumentException
* when the object cannot be added to this set.
*/
public boolean add(E object); /**
* Adds the objects in the specified collection which do not exist yet in
* this set.
*
* @param collection
* the collection of objects.
* @return {@code true} if this set is modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* when adding to this set is not supported.
* @throws ClassCastException
* when the class of an object is inappropriate for this set.
* @throws IllegalArgumentException
* when an object cannot be added to this set.
*/
public boolean addAll(Collection<? extends E> collection); /**
* Removes all elements from this set, leaving it empty.
*
* @throws UnsupportedOperationException
* when removing from this set is not supported.
* @see #isEmpty
* @see #size
*/
public void clear(); /**
* Searches this set for the specified object.
*
* @param object
* the object to search for.
* @return {@code true} if object is an element of this set, {@code false}
* otherwise.
*/
public boolean contains(Object object); /**
* Searches this set for all objects in the specified collection.
*
* @param collection
* the collection of objects.
* @return {@code true} if all objects in the specified collection are
* elements of this set, {@code false} otherwise.
*/
public boolean containsAll(Collection<?> collection); /**
* Compares the specified object to this set, and returns true if they
* represent the <em>same</em> object using a class specific comparison.
* Equality for a set means that both sets have the same size and the same
* elements.
*
* @param object
* the object to compare with this object.
* @return boolean {@code true} if the object is the same as this object,
* and {@code false} if it is different from this object.
* @see #hashCode
*/
public boolean equals(Object object); /**
* Returns the hash code for this set. Two set which are equal must return
* the same value.
*
* @return the hash code of this set.
*
* @see #equals
*/
public int hashCode(); /**
* Returns true if this set has no elements.
*
* @return {@code true} if this set has no elements, {@code false}
* otherwise.
* @see #size
*/
public boolean isEmpty(); /**
* Returns an iterator on the elements of this set. The elements are
* unordered.
*
* @return an iterator on the elements of this set.
* @see Iterator
*/
public Iterator<E> iterator(); /**
* Removes the specified object from this set.
*
* @param object
* the object to remove.
* @return {@code true} if this set was modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* when removing from this set is not supported.
*/
public boolean remove(Object object); /**
* Removes all objects in the specified collection from this set.
*
* @param collection
* the collection of objects to remove.
* @return {@code true} if this set was modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* when removing from this set is not supported.
*/
public boolean removeAll(Collection<?> collection); /**
* Removes all objects from this set that are not contained in the specified
* collection.
*
* @param collection
* the collection of objects to retain.
* @return {@code true} if this set was modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* when removing from this set is not supported.
*/
public boolean retainAll(Collection<?> collection); /**
* Returns the number of elements in this set.
*
* @return the number of elements in this set.
*/
public int size(); /**
* Returns an array containing all elements contained in this set.
*
* @return an array of the elements from this set.
*/
public Object[] toArray(); /**
* Returns an array containing all elements contained in this set. If the
* specified array is large enough to hold the elements, the specified array
* is used, otherwise an array of the same type is created. If the specified
* array is used and is larger than this set, the array element following
* the collection elements is set to null.
*
* @param array
* the array.
* @return an array of the elements from this set.
* @throws ArrayStoreException
* when the type of an element in this set cannot be stored in
* the type of the specified array.
* @see Collection#toArray(Object[])
*/
public <T> T[] toArray(T[] array);
}
Queue Interface
public interface Queue<E> extends Collection<E> {
/**
* Inserts the specified element into this queue if it is possible to do so
* immediately without violating capacity restrictions, returning
* <tt>true</tt> upon success and throwing an <tt>IllegalStateException</tt>
* if no space is currently available.
*
* @param e the element to add
* @return <tt>true</tt> (as specified by {@link Collection#add})
* @throws IllegalStateException if the element cannot be added at this
* time due to capacity restrictions
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean add(E e);
/**
* Inserts the specified element into this queue if it is possible to do
* so immediately without violating capacity restrictions.
* When using a capacity-restricted queue, this method is generally
* preferable to {@link #add}, which can fail to insert an element only
* by throwing an exception.
*
* @param e the element to add
* @return <tt>true</tt> if the element was added to this queue, else
* <tt>false</tt>
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean offer(E e);
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll poll} only in that it throws an exception if this
* queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E remove();
/**
* Retrieves and removes the head of this queue,
* or returns <tt>null</tt> if this queue is empty.
*
* @return the head of this queue, or <tt>null</tt> if this queue is empty
*/
E poll();
/**
* Retrieves, but does not remove, the head of this queue. This method
* differs from {@link #peek peek} only in that it throws an exception
* if this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E element();
/**
* Retrieves, but does not remove, the head of this queue,
* or returns <tt>null</tt> if this queue is empty.
*
* @return the head of this queue, or <tt>null</tt> if this queue is empty
*/
E peek();
}
SortedSet Interface
package java.util;
public interface SortedSet<E> extends Set<E> {
public Comparator<? super E> comparator();
public E first();
public SortedSet<E> headSet(E end);
public E last();
public SortedSet<E> subSet(E start, E end);
public SortedSet<E> tailSet(E start);
}
NavigableSet Interface
public interface NavigableSet<E> extends SortedSet<E> {
E lower(E e);
E floor(E e);
E ceiling(E e);
E higher(E e);
E pollFirst();
E pollLast();
Iterator<E> iterator();
NavigableSet<E> descendingSet();
Iterator<E> descendingIterator();
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive);
NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
}
AbstractCollection Abstract Class
public abstract class AbstractCollection<E> implements Collection<E> {
/**
* Constructs a new instance of this AbstractCollection.
*/
protected AbstractCollection() {
}
public boolean add(E object) {
throw new UnsupportedOperationException();
}
/**
* Attempts to add all of the objects contained in {@code collection}
* to the contents of this {@code Collection} (optional). This implementation
* iterates over the given {@code Collection} and calls {@code add} for each
* element. If any of these calls return {@code true}, then {@code true} is
* returned as result of this method call, {@code false} otherwise. If this
* {@code Collection} does not support adding elements, an {@code
* UnsupportedOperationException} is thrown.
* <p>
* If the passed {@code Collection} is changed during the process of adding elements
* to this {@code Collection}, the behavior depends on the behavior of the passed
* {@code Collection}.
*
* @param collection
* the collection of objects.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if adding to this {@code Collection} is not supported.
* @throws ClassCastException
* if the class of an object is inappropriate for this
* {@code Collection}.
* @throws IllegalArgumentException
* if an object cannot be added to this {@code Collection}.
* @throws NullPointerException
* if {@code collection} is {@code null}, or if it contains
* {@code null} elements and this {@code Collection} does not support
* such elements.
*/
public boolean addAll(Collection<? extends E> collection) {
boolean result = false;
Iterator<? extends E> it = collection.iterator();
while (it.hasNext()) {
if (add(it.next())) {
result = true;
}
}
return result;
}
/**
* Removes all elements from this {@code Collection}, leaving it empty (optional).
* This implementation iterates over this {@code Collection} and calls the {@code
* remove} method on each element. If the iterator does not support removal
* of elements, an {@code UnsupportedOperationException} is thrown.
* <p>
* Concrete implementations usually can clear a {@code Collection} more efficiently
* and should therefore overwrite this method.
*
* @throws UnsupportedOperationException
* it the iterator does not support removing elements from
* this {@code Collection}
* @see #iterator
* @see #isEmpty
* @see #size
*/
public void clear() {
Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
/**
* Tests whether this {@code Collection} contains the specified object. This
* implementation iterates over this {@code Collection} and tests, whether any
* element is equal to the given object. If {@code object != null} then
* {@code object.equals(e)} is called for each element {@code e} returned by
* the iterator until the element is found. If {@code object == null} then
* each element {@code e} returned by the iterator is compared with the test
* {@code e == null}.
*
* @param object
* the object to search for.
* @return {@code true} if object is an element of this {@code Collection}, {@code
* false} otherwise.
* @throws ClassCastException
* if the object to look for isn't of the correct type.
* @throws NullPointerException
* if the object to look for is {@code null} and this
* {@code Collection} doesn't support {@code null} elements.
*/
public boolean contains(Object object) {
Iterator<E> it = iterator();
if (object != null) {
while (it.hasNext()) {
if (object.equals(it.next())) {
return true;
}
}
} else {
while (it.hasNext()) {
if (it.next() == null) {
return true;
}
}
}
return false;
}
/**
* Tests whether this {@code Collection} contains all objects contained in the
* specified {@code Collection}. This implementation iterates over the specified
* {@code Collection}. If one element returned by the iterator is not contained in
* this {@code Collection}, then {@code false} is returned; {@code true} otherwise.
*
* @param collection
* the collection of objects.
* @return {@code true} if all objects in the specified {@code Collection} are
* elements of this {@code Collection}, {@code false} otherwise.
* @throws ClassCastException
* if one or more elements of {@code collection} isn't of the
* correct type.
* @throws NullPointerException
* if {@code collection} contains at least one {@code null}
* element and this {@code Collection} doesn't support {@code null}
* elements.
* @throws NullPointerException
* if {@code collection} is {@code null}.
*/
public boolean containsAll(Collection<?> collection) {
Iterator<?> it = collection.iterator();
while (it.hasNext()) {
if (!contains(it.next())) {
return false;
}
}
return true;
}
/**
* Returns if this {@code Collection} contains no elements. This implementation
* tests, whether {@code size} returns 0.
*
* @return {@code true} if this {@code Collection} has no elements, {@code false}
* otherwise.
*
* @see #size
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns an instance of {@link Iterator} that may be used to access the
* objects contained by this {@code Collection}. The order in which the elements are
* returned by the {@link Iterator} is not defined unless the instance of the
* {@code Collection} has a defined order. In that case, the elements are returned in that order.
* <p>
* In this class this method is declared abstract and has to be implemented
* by concrete {@code Collection} implementations.
*
* @return an iterator for accessing the {@code Collection} contents.
*/
public abstract Iterator<E> iterator();
/**
* Removes one instance of the specified object from this {@code Collection} if one
* is contained (optional). This implementation iterates over this
* {@code Collection} and tests for each element {@code e} returned by the iterator,
* whether {@code e} is equal to the given object. If {@code object != null}
* then this test is performed using {@code object.equals(e)}, otherwise
* using {@code object == null}. If an element equal to the given object is
* found, then the {@code remove} method is called on the iterator and
* {@code true} is returned, {@code false} otherwise. If the iterator does
* not support removing elements, an {@code UnsupportedOperationException}
* is thrown.
*
* @param object
* the object to remove.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code Collection} is not supported.
* @throws ClassCastException
* if the object passed is not of the correct type.
* @throws NullPointerException
* if {@code object} is {@code null} and this {@code Collection}
* doesn't support {@code null} elements.
*/
public boolean remove(Object object) {
Iterator<?> it = iterator();
if (object != null) {
while (it.hasNext()) {
if (object.equals(it.next())) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (it.next() == null) {
it.remove();
return true;
}
}
}
return false;
}
/**
* Removes all occurrences in this {@code Collection} of each object in the
* specified {@code Collection} (optional). After this method returns none of the
* elements in the passed {@code Collection} can be found in this {@code Collection}
* anymore.
* <p>
* This implementation iterates over this {@code Collection} and tests for each
* element {@code e} returned by the iterator, whether it is contained in
* the specified {@code Collection}. If this test is positive, then the {@code
* remove} method is called on the iterator. If the iterator does not
* support removing elements, an {@code UnsupportedOperationException} is
* thrown.
*
* @param collection
* the collection of objects to remove.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code Collection} is not supported.
* @throws ClassCastException
* if one or more elements of {@code collection} isn't of the
* correct type.
* @throws NullPointerException
* if {@code collection} contains at least one {@code null}
* element and this {@code Collection} doesn't support {@code null}
* elements.
* @throws NullPointerException
* if {@code collection} is {@code null}.
*/
public boolean removeAll(Collection<?> collection) {
boolean result = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (collection.contains(it.next())) {
it.remove();
result = true;
}
}
return result;
}
/**
* Removes all objects from this {@code Collection} that are not also found in the
* {@code Collection} passed (optional). After this method returns this {@code Collection}
* will only contain elements that also can be found in the {@code Collection}
* passed to this method.
* <p>
* This implementation iterates over this {@code Collection} and tests for each
* element {@code e} returned by the iterator, whether it is contained in
* the specified {@code Collection}. If this test is negative, then the {@code
* remove} method is called on the iterator. If the iterator does not
* support removing elements, an {@code UnsupportedOperationException} is
* thrown.
*
* @param collection
* the collection of objects to retain.
* @return {@code true} if this {@code Collection} is modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if removing from this {@code Collection} is not supported.
* @throws ClassCastException
* if one or more elements of {@code collection}
* isn't of the correct type.
* @throws NullPointerException
* if {@code collection} contains at least one
* {@code null} element and this {@code Collection} doesn't support
* {@code null} elements.
* @throws NullPointerException
* if {@code collection} is {@code null}.
*/
public boolean retainAll(Collection<?> collection) {
boolean result = false;
Iterator<?> it = iterator();
while (it.hasNext()) {
if (!collection.contains(it.next())) {
it.remove();
result = true;
}
}
return result;
}
/**
* Returns a count of how many objects this {@code Collection} contains.
* <p>
* In this class this method is declared abstract and has to be implemented
* by concrete {@code Collection} implementations.
*
* @return how many objects this {@code Collection} contains, or {@code Integer.MAX_VALUE}
* if there are more than {@code Integer.MAX_VALUE} elements in this
* {@code Collection}.
*/
public abstract int size();
public Object[] toArray() {
int size = size(), index = 0;
Iterator<?> it = iterator();
Object[] array = new Object[size];
while (index < size) {
array[index++] = it.next();
}
return array;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] contents) {
int size = size(), index = 0;
if (size > contents.length) {
Class<?> ct = contents.getClass().getComponentType();
contents = (T[]) Array.newInstance(ct, size);
}
for (E entry : this) {
contents[index++] = (T) entry;
}
if (index < contents.length) {
contents[index] = null;
}
return contents;
}
/**
* Returns the string representation of this {@code Collection}. The presentation
* has a specific format. It is enclosed by square brackets ("[]"). Elements
* are separated by ', ' (comma and space).
*
* @return the string representation of this {@code Collection}.
*/
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder buffer = new StringBuilder(size() * 16);
buffer.append('[');
Iterator<?> it = iterator();
while (it.hasNext()) {
Object next = it.next();
if (next != this) {
buffer.append(next);
} else {
buffer.append("(this Collection)");
}
if (it.hasNext()) {
buffer.append(", ");
}
}
buffer.append(']');
return buffer.toString();
}
}
AbstractSet AbstractClass
public abstract class AbstractSet<E> extends AbstractCollection<E> implements
Set<E> { /**
* Constructs a new instance of this AbstractSet.
*/
protected AbstractSet() {
} /**
* Compares the specified object to this Set and returns true if they are
* equal. The object must be an instance of Set and contain the same
* objects.
*
* @param object
* the object to compare with this set.
* @return {@code true} if the specified object is equal to this set,
* {@code false} otherwise
* @see #hashCode
*/
@Override
public boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof Set) {
Set<?> s = (Set<?>) object; try {
return size() == s.size() && containsAll(s);
} catch (NullPointerException ignored) {
return false;
} catch (ClassCastException ignored) {
return false;
}
}
return false;
} /**
* Returns the hash code for this set. Two set which are equal must return
* the same value. This implementation calculates the hash code by adding
* each element's hash code.
*
* @return the hash code of this set.
* @see #equals
*/
@Override
public int hashCode() {
int result = 0;
Iterator<?> it = iterator();
while (it.hasNext()) {
Object next = it.next();
result += next == null ? 0 : next.hashCode();
}
return result;
} /**
* Removes all occurrences in this collection which are contained in the
* specified collection.
*
* @param collection
* the collection of objects to remove.
* @return {@code true} if this collection was modified, {@code false}
* otherwise.
* @throws UnsupportedOperationException
* if removing from this collection is not supported.
*/
@Override
public boolean removeAll(Collection<?> collection) {
boolean result = false;
if (size() <= collection.size()) {
Iterator<?> it = iterator();
while (it.hasNext()) {
if (collection.contains(it.next())) {
it.remove();
result = true;
}
}
} else {
Iterator<?> it = collection.iterator();
while (it.hasNext()) {
result = remove(it.next()) || result;
}
}
return result;
}
}
HashSet
package java.util; import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable; public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable,
Serializable { private static final long serialVersionUID = -5024744406713321676L; transient HashMap<E, HashSet<E>> backingMap; /**
* Constructs a new empty instance of {@code HashSet}.
*/
public HashSet() {
this(new HashMap<E, HashSet<E>>());
} /**
* Constructs a new instance of {@code HashSet} with the specified capacity.
*
* @param capacity
* the initial capacity of this {@code HashSet}.
*/
public HashSet(int capacity) {
this(new HashMap<E, HashSet<E>>(capacity));
} /**
* Constructs a new instance of {@code HashSet} with the specified capacity
* and load factor.
*
* @param capacity
* the initial capacity.
* @param loadFactor
* the initial load factor.
*/
public HashSet(int capacity, float loadFactor) {
this(new HashMap<E, HashSet<E>>(capacity, loadFactor));
} /**
* Constructs a new instance of {@code HashSet} containing the unique
* elements in the specified collection.
*
* @param collection
* the collection of elements to add.
*/
public HashSet(Collection<? extends E> collection) {
this(new HashMap<E, HashSet<E>>(collection.size() < 6 ? 11 : collection
.size() * 2));
for (E e : collection) {
add(e);
}
} HashSet(HashMap<E, HashSet<E>> backingMap) {
this.backingMap = backingMap;
} /**
* Adds the specified object to this {@code HashSet} if not already present.
*
* @param object
* the object to add.
* @return {@code true} when this {@code HashSet} did not already contain
* the object, {@code false} otherwise
*/
@Override
public boolean add(E object) {
return backingMap.put(object, this) == null;
} /**
* Removes all elements from this {@code HashSet}, leaving it empty.
*
* @see #isEmpty
* @see #size
*/
@Override
public void clear() {
backingMap.clear();
} /**
* Returns a new {@code HashSet} with the same elements and size as this
* {@code HashSet}.
*
* @return a shallow copy of this {@code HashSet}.
* @see java.lang.Cloneable
*/
@Override
@SuppressWarnings("unchecked")
public Object clone() {
try {
HashSet<E> clone = (HashSet<E>) super.clone();
clone.backingMap = (HashMap<E, HashSet<E>>) backingMap.clone();
return clone;
} catch (CloneNotSupportedException e) {
throw new AssertionError(e);
}
} /**
* Searches this {@code HashSet} for the specified object.
*
* @param object
* the object to search for.
* @return {@code true} if {@code object} is an element of this
* {@code HashSet}, {@code false} otherwise.
*/
@Override
public boolean contains(Object object) {
return backingMap.containsKey(object);
} /**
* Returns true if this {@code HashSet} has no elements, false otherwise.
*
* @return {@code true} if this {@code HashSet} has no elements,
* {@code false} otherwise.
* @see #size
*/
@Override
public boolean isEmpty() {
return backingMap.isEmpty();
} /**
* Returns an Iterator on the elements of this {@code HashSet}.
*
* @return an Iterator on the elements of this {@code HashSet}.
* @see Iterator
*/
@Override
public Iterator<E> iterator() {
return backingMap.keySet().iterator();
} /**
* Removes the specified object from this {@code HashSet}.
*
* @param object
* the object to remove.
* @return {@code true} if the object was removed, {@code false} otherwise.
*/
@Override
public boolean remove(Object object) {
return backingMap.remove(object) != null;
} /**
* Returns the number of elements in this {@code HashSet}.
*
* @return the number of elements in this {@code HashSet}.
*/
@Override
public int size() {
return backingMap.size();
} private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeInt(backingMap.table.length);
stream.writeFloat(HashMap.DEFAULT_LOAD_FACTOR);
stream.writeInt(size());
for (E e : this) {
stream.writeObject(e);
}
} @SuppressWarnings("unchecked")
private void readObject(ObjectInputStream stream) throws IOException,
ClassNotFoundException {
stream.defaultReadObject();
int length = stream.readInt();
float loadFactor = stream.readFloat();
backingMap = createBackingMap(length, loadFactor);
int elementCount = stream.readInt();
for (int i = elementCount; --i >= 0;) {
E key = (E) stream.readObject();
backingMap.put(key, this);
}
} HashMap<E, HashSet<E>> createBackingMap(int capacity, float loadFactor) {
return new HashMap<E, HashSet<E>>(capacity, loadFactor);
}
}
TreeSet
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/ package java.util; import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable; /**
* TreeSet is an implementation of SortedSet. All optional operations (adding
* and removing) are supported. The elements can be any objects which are
* comparable to each other either using their natural order or a specified
* Comparator.
*
* @since 1.2
*/
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>,
Cloneable, Serializable { private static final long serialVersionUID = -2479143000061671589L; /** Keys are this set's elements. Values are always Boolean.TRUE */
private transient NavigableMap<E, Object> backingMap; private transient NavigableSet<E> descendingSet; TreeSet(NavigableMap<E, Object> map) {
backingMap = map;
} /**
* Constructs a new empty instance of {@code TreeSet} which uses natural
* ordering.
*/
public TreeSet() {
backingMap = new TreeMap<E, Object>();
} /**
* Constructs a new instance of {@code TreeSet} which uses natural ordering
* and containing the unique elements in the specified collection.
*
* @param collection
* the collection of elements to add.
* @throws ClassCastException
* when an element in the collection does not implement the
* Comparable interface, or the elements in the collection
* cannot be compared.
*/
public TreeSet(Collection<? extends E> collection) {
this();
addAll(collection);
} /**
* Constructs a new empty instance of {@code TreeSet} which uses the
* specified comparator.
*
* @param comparator
* the comparator to use.
*/
public TreeSet(Comparator<? super E> comparator) {
backingMap = new TreeMap<E, Object>(comparator);
} /**
* Constructs a new instance of {@code TreeSet} containing the elements of
* the specified SortedSet and using the same Comparator.
*
* @param set
* the SortedSet of elements to add.
*/
public TreeSet(SortedSet<E> set) {
this(set.comparator());
Iterator<E> it = set.iterator();
while (it.hasNext()) {
add(it.next());
}
} /**
* Adds the specified object to this {@code TreeSet}.
*
* @param object
* the object to add.
* @return {@code true} when this {@code TreeSet} did not already contain
* the object, {@code false} otherwise.
* @throws ClassCastException
* when the object cannot be compared with the elements in this
* {@code TreeSet}.
* @throws NullPointerException
* when the object is null and the comparator cannot handle
* null.
*/
@Override
public boolean add(E object) {
return backingMap.put(object, Boolean.TRUE) == null;
} /**
* Adds the objects in the specified collection to this {@code TreeSet}.
*
* @param collection
* the collection of objects to add.
* @return {@code true} if this {@code TreeSet} was modified, {@code false}
* otherwise.
* @throws ClassCastException
* when an object in the collection cannot be compared with the
* elements in this {@code TreeSet}.
* @throws NullPointerException
* when an object in the collection is null and the comparator
* cannot handle null.
*/
@Override
public boolean addAll(Collection<? extends E> collection) {
return super.addAll(collection);
} /**
* Removes all elements from this {@code TreeSet}, leaving it empty.
*
* @see #isEmpty
* @see #size
*/
@Override
public void clear() {
backingMap.clear();
} /**
* Returns a new {@code TreeSet} with the same elements, size and comparator
* as this {@code TreeSet}.
*
* @return a shallow copy of this {@code TreeSet}.
* @see java.lang.Cloneable
*/
@SuppressWarnings("unchecked")
@Override
public Object clone() {
try {
TreeSet<E> clone = (TreeSet<E>) super.clone();
if (backingMap instanceof TreeMap) {
clone.backingMap = (NavigableMap<E, Object>) ((TreeMap<E, Object>) backingMap)
.clone();
} else {
clone.backingMap = new TreeMap<E, Object>(backingMap);
}
return clone;
} catch (CloneNotSupportedException e) {
throw new AssertionError(e);
}
} /**
* Returns the comparator used to compare elements in this {@code TreeSet}.
*
* @return a Comparator or null if the natural ordering is used
*/
public Comparator<? super E> comparator() {
return backingMap.comparator();
} /**
* Searches this {@code TreeSet} for the specified object.
*
* @param object
* the object to search for.
* @return {@code true} if {@code object} is an element of this
* {@code TreeSet}, {@code false} otherwise.
* @throws ClassCastException
* when the object cannot be compared with the elements in this
* {@code TreeSet}.
* @throws NullPointerException
* when the object is null and the comparator cannot handle
* null.
*/
@Override
public boolean contains(Object object) {
return backingMap.containsKey(object);
} /**
* Returns true if this {@code TreeSet} has no element, otherwise false.
*
* @return true if this {@code TreeSet} has no element.
* @see #size
*/
@Override
public boolean isEmpty() {
return backingMap.isEmpty();
} /**
* Returns an Iterator on the elements of this {@code TreeSet}.
*
* @return an Iterator on the elements of this {@code TreeSet}.
* @see Iterator
*/
@Override
public Iterator<E> iterator() {
return backingMap.keySet().iterator();
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#descendingIterator()
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return descendingSet().iterator();
} /**
* Removes an occurrence of the specified object from this {@code TreeSet}.
*
* @param object
* the object to remove.
* @return {@code true} if this {@code TreeSet} was modified, {@code false}
* otherwise.
* @throws ClassCastException
* when the object cannot be compared with the elements in this
* {@code TreeSet}.
* @throws NullPointerException
* when the object is null and the comparator cannot handle
* null.
*/
@Override
public boolean remove(Object object) {
return backingMap.remove(object) != null;
} /**
* Returns the number of elements in this {@code TreeSet}.
*
* @return the number of elements in this {@code TreeSet}.
*/
@Override
public int size() {
return backingMap.size();
} /**
* Returns the first element in this set.
* @exception NoSuchElementException when this TreeSet is empty
*/
public E first() {
return backingMap.firstKey();
} /**
* Returns the last element in this set.
* @exception NoSuchElementException when this TreeSet is empty
*/
public E last() {
return backingMap.lastKey();
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#pollFirst()
* @since 1.6
*/
public E pollFirst() {
Map.Entry<E, Object> entry = backingMap.pollFirstEntry();
return (entry == null) ? null : entry.getKey();
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#pollLast()
* @since 1.6
*/
public E pollLast() {
Map.Entry<E, Object> entry = backingMap.pollLastEntry();
return (entry == null) ? null : entry.getKey();
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#higher(java.lang.Object)
* @since 1.6
*/
public E higher(E e) {
return backingMap.higherKey(e);
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#lower(java.lang.Object)
* @since 1.6
*/
public E lower(E e) {
return backingMap.lowerKey(e);
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#ceiling(java.lang.Object)
* @since 1.6
*/
public E ceiling(E e) {
return backingMap.ceilingKey(e);
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#floor(java.lang.Object)
* @since 1.6
*/
public E floor(E e) {
return backingMap.floorKey(e);
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#descendingSet()
* @since 1.6
*/
public NavigableSet<E> descendingSet() {
return (descendingSet != null) ? descendingSet
: (descendingSet = new TreeSet<E>(backingMap.descendingMap()));
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#subSet(Object, boolean, Object, boolean)
* @since 1.6
*/
@SuppressWarnings("unchecked")
public NavigableSet<E> subSet(E start, boolean startInclusive, E end,
boolean endInclusive) {
Comparator<? super E> c = backingMap.comparator();
int compare = (c == null) ? ((Comparable<E>) start).compareTo(end) : c
.compare(start, end);
if (compare <= 0) {
return new TreeSet<E>(backingMap.subMap(start, startInclusive, end,
endInclusive));
}
throw new IllegalArgumentException();
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#headSet(Object, boolean)
* @since 1.6
*/
@SuppressWarnings("unchecked")
public NavigableSet<E> headSet(E end, boolean endInclusive) {
// Check for errors
Comparator<? super E> c = backingMap.comparator();
if (c == null) {
((Comparable<E>) end).compareTo(end);
} else {
c.compare(end, end);
}
return new TreeSet<E>(backingMap.headMap(end, endInclusive));
} /**
* {@inheritDoc}
*
* @see java.util.NavigableSet#tailSet(Object, boolean)
* @since 1.6
*/
@SuppressWarnings("unchecked")
public NavigableSet<E> tailSet(E start, boolean startInclusive) {
// Check for errors
Comparator<? super E> c = backingMap.comparator();
if (c == null) {
((Comparable<E>) start).compareTo(start);
} else {
c.compare(start, start);
}
return new TreeSet<E>(backingMap.tailMap(start, startInclusive));
} /**
* Returns a {@code SortedSet} of the specified portion of this {@code TreeSet} which
* contains elements greater or equal to the start element but less than the
* end element. The returned SortedSet is backed by this TreeSet so changes
* to one are reflected by the other.
*
* @param start
* the start element
* @param end
* the end element
* @return a subset where the elements are greater or equal to
* <code>start</code> and less than <code>end</code>
*
* @exception ClassCastException
* when the start or end object cannot be compared with the
* elements in this TreeSet
* @exception NullPointerException
* when the start or end object is null and the comparator
* cannot handle null
*/
@SuppressWarnings("unchecked")
public SortedSet<E> subSet(E start, E end) {
return subSet(start, true, end, false);
} /**
* Returns a {@code SortedSet} of the specified portion of this {@code TreeSet} which
* contains elements less than the end element. The returned SortedSet is
* backed by this TreeSet so changes to one are reflected by the other.
*
* @param end
* the end element
* @return a subset where the elements are less than <code>end</code>
*
* @exception ClassCastException
* when the end object cannot be compared with the elements
* in this TreeSet
* @exception NullPointerException
* when the end object is null and the comparator cannot
* handle null
*/
@SuppressWarnings("unchecked")
public SortedSet<E> headSet(E end) {
return headSet(end, false);
} /**
* Returns a {@code SortedSet} of the specified portion of this {@code TreeSet} which
* contains elements greater or equal to the start element. The returned
* SortedSet is backed by this TreeSet so changes to one are reflected by
* the other.
*
* @param start
* the start element
* @return a subset where the elements are greater or equal to
* <code>start</code>
*
* @exception ClassCastException
* when the start object cannot be compared with the elements
* in this TreeSet
* @exception NullPointerException
* when the start object is null and the comparator cannot
* handle null
*/
@SuppressWarnings("unchecked")
public SortedSet<E> tailSet(E start) {
return tailSet(start, true);
} private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeObject(backingMap.comparator());
int size = backingMap.size();
stream.writeInt(size);
if (size > 0) {
Iterator<E> it = backingMap.keySet().iterator();
while (it.hasNext()) {
stream.writeObject(it.next());
}
}
} @SuppressWarnings("unchecked")
private void readObject(ObjectInputStream stream) throws IOException,
ClassNotFoundException {
stream.defaultReadObject();
TreeMap<E, Object> map = new TreeMap<E, Object>(
(Comparator<? super E>) stream.readObject());
int size = stream.readInt();
if (size > 0) {
for (int i=0; i<size; i++) {
E elem = (E)stream.readObject();
map.put(elem, Boolean.TRUE);
}
}
backingMap = map;
}
}
AbstractList AbstractClass
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/ package java.util; public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { /**
* A counter for changes to the list.
*/
protected transient int modCount; private class SimpleListIterator implements Iterator<E> {
int pos = -1; int expectedModCount; int lastPosition = -1; SimpleListIterator() {
expectedModCount = modCount;
} public boolean hasNext() {
return pos + 1 < size();
} public E next() {
if (expectedModCount == modCount) {
try {
E result = get(pos + 1);
lastPosition = ++pos;
return result;
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
} public void remove() {
if (this.lastPosition == -1) {
throw new IllegalStateException();
} if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
} try {
AbstractList.this.remove(lastPosition);
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
} expectedModCount = modCount;
if (pos == lastPosition) {
pos--;
}
lastPosition = -1;
}
} private final class FullListIterator extends SimpleListIterator implements ListIterator<E> {
FullListIterator(int start) {
if (start >= 0 && start <= size()) {
pos = start - 1;
} else {
throw new IndexOutOfBoundsException();
}
} public void add(E object) {
if (expectedModCount == modCount) {
try {
AbstractList.this.add(pos + 1, object);
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
pos++;
lastPosition = -1;
if (modCount != expectedModCount) {
expectedModCount = modCount;
}
} else {
throw new ConcurrentModificationException();
}
} public boolean hasPrevious() {
return pos >= 0;
} public int nextIndex() {
return pos + 1;
} public E previous() {
if (expectedModCount == modCount) {
try {
E result = get(pos);
lastPosition = pos;
pos--;
return result;
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
} public int previousIndex() {
return pos;
} public void set(E object) {
if (expectedModCount == modCount) {
try {
AbstractList.this.set(lastPosition, object);
} catch (IndexOutOfBoundsException e) {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
} private static final class SubAbstractListRandomAccess<E> extends
SubAbstractList<E> implements RandomAccess {
SubAbstractListRandomAccess(AbstractList<E> list, int start, int end) {
super(list, start, end);
}
} private static class SubAbstractList<E> extends AbstractList<E> {
private final AbstractList<E> fullList; private int offset; private int size; private static final class SubAbstractListIterator<E> implements
ListIterator<E> {
private final SubAbstractList<E> subList; private final ListIterator<E> iterator; private int start; private int end; SubAbstractListIterator(ListIterator<E> it,
SubAbstractList<E> list, int offset, int length) {
iterator = it;
subList = list;
start = offset;
end = start + length;
} public void add(E object) {
iterator.add(object);
subList.sizeChanged(true);
end++;
} public boolean hasNext() {
return iterator.nextIndex() < end;
} public boolean hasPrevious() {
return iterator.previousIndex() >= start;
} public E next() {
if (iterator.nextIndex() < end) {
return iterator.next();
}
throw new NoSuchElementException();
} public int nextIndex() {
return iterator.nextIndex() - start;
} public E previous() {
if (iterator.previousIndex() >= start) {
return iterator.previous();
}
throw new NoSuchElementException();
} public int previousIndex() {
int previous = iterator.previousIndex();
if (previous >= start) {
return previous - start;
}
return -1;
} public void remove() {
iterator.remove();
subList.sizeChanged(false);
end--;
} public void set(E object) {
iterator.set(object);
}
} SubAbstractList(AbstractList<E> list, int start, int end) {
fullList = list;
modCount = fullList.modCount;
offset = start;
size = end - start;
} @Override
public void add(int location, E object) {
if (modCount == fullList.modCount) {
if (location >= 0 && location <= size) {
fullList.add(location + offset, object);
size++;
modCount = fullList.modCount;
} else {
throw new IndexOutOfBoundsException();
}
} else {
throw new ConcurrentModificationException();
}
} @Override
public boolean addAll(int location, Collection<? extends E> collection) {
if (modCount == fullList.modCount) {
if (location >= 0 && location <= size) {
boolean result = fullList.addAll(location + offset,
collection);
if (result) {
size += collection.size();
modCount = fullList.modCount;
}
return result;
}
throw new IndexOutOfBoundsException();
}
throw new ConcurrentModificationException();
} @Override
public boolean addAll(Collection<? extends E> collection) {
if (modCount == fullList.modCount) {
boolean result = fullList.addAll(offset + size, collection);
if (result) {
size += collection.size();
modCount = fullList.modCount;
}
return result;
}
throw new ConcurrentModificationException();
} @Override
public E get(int location) {
if (modCount == fullList.modCount) {
if (location >= 0 && location < size) {
return fullList.get(location + offset);
}
throw new IndexOutOfBoundsException();
}
throw new ConcurrentModificationException();
} @Override
public Iterator<E> iterator() {
return listIterator(0);
} @Override
public ListIterator<E> listIterator(int location) {
if (modCount == fullList.modCount) {
if (location >= 0 && location <= size) {
return new SubAbstractListIterator<E>(fullList
.listIterator(location + offset), this, offset,
size);
}
throw new IndexOutOfBoundsException();
}
throw new ConcurrentModificationException();
} @Override
public E remove(int location) {
if (modCount == fullList.modCount) {
if (location >= 0 && location < size) {
E result = fullList.remove(location + offset);
size--;
modCount = fullList.modCount;
return result;
}
throw new IndexOutOfBoundsException();
}
throw new ConcurrentModificationException();
} @Override
protected void removeRange(int start, int end) {
if (start != end) {
if (modCount == fullList.modCount) {
fullList.removeRange(start + offset, end + offset);
size -= end - start;
modCount = fullList.modCount;
} else {
throw new ConcurrentModificationException();
}
}
} @Override
public E set(int location, E object) {
if (modCount == fullList.modCount) {
if (location >= 0 && location < size) {
return fullList.set(location + offset, object);
}
throw new IndexOutOfBoundsException();
}
throw new ConcurrentModificationException();
} @Override
public int size() {
if (modCount == fullList.modCount) {
return size;
}
throw new ConcurrentModificationException();
} void sizeChanged(boolean increment) {
if (increment) {
size++;
} else {
size--;
}
modCount = fullList.modCount;
}
} /**
* Constructs a new instance of this AbstractList.
*/
protected AbstractList() {
} /**
* Inserts the specified object into this List at the specified location.
* The object is inserted before any previous element at the specified
* location. If the location is equal to the size of this List, the object
* is added at the end.
* <p>
* Concrete implementations that would like to support the add functionality
* must override this method.
*
* @param location
* the index at which to insert.
* @param object
* the object to add.
*
* @throws UnsupportedOperationException
* if adding to this List is not supported.
* @throws ClassCastException
* if the class of the object is inappropriate for this
* List
* @throws IllegalArgumentException
* if the object cannot be added to this List
* @throws IndexOutOfBoundsException
* if {@code location < 0 || >= size()}
*/
public void add(int location, E object) {
throw new UnsupportedOperationException();
} /**
* Adds the specified object at the end of this List.
*
*
* @param object
* the object to add
* @return true
*
* @throws UnsupportedOperationException
* if adding to this List is not supported
* @throws ClassCastException
* if the class of the object is inappropriate for this
* List
* @throws IllegalArgumentException
* if the object cannot be added to this List
*/
@Override
public boolean add(E object) {
add(size(), object);
return true;
} /**
* Inserts the objects in the specified Collection at the specified location
* in this List. The objects are added in the order they are returned from
* the collection's iterator.
*
* @param location
* the index at which to insert.
* @param collection
* the Collection of objects
* @return {@code true} if this List is modified, {@code false} otherwise.
* @throws UnsupportedOperationException
* if adding to this list is not supported.
* @throws ClassCastException
* if the class of an object is inappropriate for this list.
* @throws IllegalArgumentException
* if an object cannot be added to this list.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || > size()}
*/
public boolean addAll(int location, Collection<? extends E> collection) {
Iterator<? extends E> it = collection.iterator();
while (it.hasNext()) {
add(location++, it.next());
}
return !collection.isEmpty();
} /**
* Removes all elements from this list, leaving it empty.
*
* @throws UnsupportedOperationException
* if removing from this list is not supported.
* @see List#isEmpty
* @see List#size
*/
@Override
public void clear() {
removeRange(0, size());
} @Override
public boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof List) {
List<?> list = (List<?>) object;
if (list.size() != size()) {
return false;
} Iterator<?> it1 = iterator(), it2 = list.iterator();
while (it1.hasNext()) {
Object e1 = it1.next(), e2 = it2.next();
if (!(e1 == null ? e2 == null : e1.equals(e2))) {
return false;
}
}
return true;
}
return false;
}
public abstract E get(int location); @Override
public int hashCode() {
int result = 1;
Iterator<?> it = iterator();
while (it.hasNext()) {
Object object = it.next();
result = (31 * result) + (object == null ? 0 : object.hashCode());
}
return result;
}
public int indexOf(Object object) {
ListIterator<?> it = listIterator();
if (object != null) {
while (it.hasNext()) {
if (object.equals(it.next())) {
return it.previousIndex();
}
}
} else {
while (it.hasNext()) {
if (it.next() == null) {
return it.previousIndex();
}
}
}
return -1;
} @Override
public Iterator<E> iterator() {
return new SimpleListIterator();
} public int lastIndexOf(Object object) {
ListIterator<?> it = listIterator(size());
if (object != null) {
while (it.hasPrevious()) {
if (object.equals(it.previous())) {
return it.nextIndex();
}
}
} else {
while (it.hasPrevious()) {
if (it.previous() == null) {
return it.nextIndex();
}
}
}
return -1;
} public ListIterator<E> listIterator() {
return listIterator(0);
} public ListIterator<E> listIterator(int location) {
return new FullListIterator(location);
} public E remove(int location) {
throw new UnsupportedOperationException();
} protected void removeRange(int start, int end) {
Iterator<?> it = listIterator(start);
for (int i = start; i < end; i++) {
it.next();
it.remove();
}
} public E set(int location, E object) {
throw new UnsupportedOperationException();
} public List<E> subList(int start, int end) {
if (start >= 0 && end <= size()) {
if (start <= end) {
if (this instanceof RandomAccess) {
return new SubAbstractListRandomAccess<E>(this, start, end);
}
return new SubAbstractList<E>(this, start, end);
}
throw new IllegalArgumentException();
}
throw new IndexOutOfBoundsException();
}
}
Vector
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/ package java.util; import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array; /**
* Vector is an implementation of {@link List}, backed by an array and synchronized.
* All optional operations including adding, removing, and replacing elements are supported.
*
* <p>All elements are permitted, including null.
*
* <p>This class is equivalent to {@link ArrayList} with synchronized operations. This has a
* performance cost, and the synchronization is not necessarily meaningful to your application:
* synchronizing each call to {@code get}, for example, is not equivalent to synchronizing on the
* list and iterating over it (which is probably what you intended). If you do need very highly
* concurrent access, you should also consider {@link java.util.concurrent.CopyOnWriteArrayList}.
*
* @param <E> The element type of this list.
*/
public class Vector<E> extends AbstractList<E> implements List<E>,
RandomAccess, Cloneable, Serializable { private static final long serialVersionUID = -2767605614048989439L; /**
* The number of elements or the size of the vector.
*/
protected int elementCount; /**
* The elements of the vector.
*/
protected Object[] elementData; /**
* How many elements should be added to the vector when it is detected that
* it needs to grow to accommodate extra entries. If this value is zero or
* negative the size will be doubled if an increase is needed.
*/
protected int capacityIncrement; private static final int DEFAULT_SIZE = 10; /**
* Constructs a new vector using the default capacity.
*/
public Vector() {
this(DEFAULT_SIZE, 0);
} /**
* Constructs a new vector using the specified capacity.
*
* @param capacity
* the initial capacity of the new vector.
* @throws IllegalArgumentException
* if {@code capacity} is negative.
*/
public Vector(int capacity) {
this(capacity, 0);
} /**
* Constructs a new vector using the specified capacity and capacity
* increment.
*
* @param capacity
* the initial capacity of the new vector.
* @param capacityIncrement
* the amount to increase the capacity when this vector is full.
* @throws IllegalArgumentException
* if {@code capacity} is negative.
*/
public Vector(int capacity, int capacityIncrement) {
if (capacity < 0) {
throw new IllegalArgumentException();
}
elementData = newElementArray(capacity);
elementCount = 0;
this.capacityIncrement = capacityIncrement;
} /**
* Constructs a new instance of {@code Vector} containing the elements in
* {@code collection}. The order of the elements in the new {@code Vector}
* is dependent on the iteration order of the seed collection.
*
* @param collection
* the collection of elements to add.
*/
public Vector(Collection<? extends E> collection) {
this(collection.size(), 0);
Iterator<? extends E> it = collection.iterator();
while (it.hasNext()) {
elementData[elementCount++] = it.next();
}
} @SuppressWarnings("unchecked")
private E[] newElementArray(int size) {
return (E[]) new Object[size];
} /**
* Adds the specified object into this vector at the specified location. The
* object is inserted before any element with the same or a higher index
* increasing their index by 1. If the location is equal to the size of this
* vector, the object is added at the end.
*
* @param location
* the index at which to insert the element.
* @param object
* the object to insert in this vector.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location > size()}.
* @see #addElement
* @see #size
*/
@Override
public void add(int location, E object) {
insertElementAt(object, location);
} /**
* Adds the specified object at the end of this vector.
*
* @param object
* the object to add to the vector.
* @return {@code true}
*/
@Override
public synchronized boolean add(E object) {
if (elementCount == elementData.length) {
growByOne();
}
elementData[elementCount++] = object;
modCount++;
return true;
} /**
* Inserts the objects in the specified collection at the specified location
* in this vector. The objects are inserted in the order in which they are
* returned from the Collection iterator. The elements with an index equal
* or higher than {@code location} have their index increased by the size of
* the added collection.
*
* @param location
* the location to insert the objects.
* @param collection
* the collection of objects.
* @return {@code true} if this vector is modified, {@code false} otherwise.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0} or {@code location > size()}.
*/
@Override
public synchronized boolean addAll(int location, Collection<? extends E> collection) {
if (location >= 0 && location <= elementCount) {
int size = collection.size();
if (size == 0) {
return false;
}
int required = size - (elementData.length - elementCount);
if (required > 0) {
growBy(required);
}
int count = elementCount - location;
if (count > 0) {
System.arraycopy(elementData, location, elementData, location
+ size, count);
}
Iterator<? extends E> it = collection.iterator();
while (it.hasNext()) {
elementData[location++] = it.next();
}
elementCount += size;
modCount++;
return true;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
} /**
* Adds the objects in the specified collection to the end of this vector.
*
* @param collection
* the collection of objects.
* @return {@code true} if this vector is modified, {@code false} otherwise.
*/
@Override
public synchronized boolean addAll(Collection<? extends E> collection) {
return addAll(elementCount, collection);
} /**
* Adds the specified object at the end of this vector.
*
* @param object
* the object to add to the vector.
*/
public synchronized void addElement(E object) {
if (elementCount == elementData.length) {
growByOne();
}
elementData[elementCount++] = object;
modCount++;
} /**
* Returns the number of elements this vector can hold without growing.
*
* @return the capacity of this vector.
* @see #ensureCapacity
* @see #size
*/
public synchronized int capacity() {
return elementData.length;
} /**
* Removes all elements from this vector, leaving it empty.
*
* @see #isEmpty
* @see #size
*/
@Override
public void clear() {
removeAllElements();
} /**
* Returns a new vector with the same elements, size, capacity and capacity
* increment as this vector.
*
* @return a shallow copy of this vector.
* @see java.lang.Cloneable
*/
@Override
@SuppressWarnings("unchecked")
public synchronized Object clone() {
try {
Vector<E> vector = (Vector<E>) super.clone();
vector.elementData = elementData.clone();
return vector;
} catch (CloneNotSupportedException e) {
throw new AssertionError(e);
}
} /**
* Searches this vector for the specified object.
*
* @param object
* the object to look for in this vector.
* @return {@code true} if object is an element of this vector,
* {@code false} otherwise.
* @see #indexOf(Object)
* @see #indexOf(Object, int)
* @see java.lang.Object#equals
*/
@Override
public boolean contains(Object object) {
return indexOf(object, 0) != -1;
} /**
* Searches this vector for all objects in the specified collection.
*
* @param collection
* the collection of objects.
* @return {@code true} if all objects in the specified collection are
* elements of this vector, {@code false} otherwise.
*/
@Override
public synchronized boolean containsAll(Collection<?> collection) {
return super.containsAll(collection);
} /**
* Attempts to copy elements contained by this {@code Vector} into the
* corresponding elements of the supplied {@code Object} array.
*
* @param elements
* the {@code Object} array into which the elements of this
* vector are copied.
* @throws IndexOutOfBoundsException
* if {@code elements} is not big enough.
* @see #clone
*/
public synchronized void copyInto(Object[] elements) {
System.arraycopy(elementData, 0, elements, 0, elementCount);
} /**
* Returns the element at the specified location in this vector.
*
* @param location
* the index of the element to return in this vector.
* @return the element at the specified location.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
@SuppressWarnings("unchecked")
public synchronized E elementAt(int location) {
if (location < elementCount) {
return (E) elementData[location];
}
throw arrayIndexOutOfBoundsException(location, elementCount);
} /**
* Returns an enumeration on the elements of this vector. The results of the
* enumeration may be affected if the contents of this vector is modified.
*
* @return an enumeration of the elements of this vector.
* @see #elementAt
* @see Enumeration
*/
public Enumeration<E> elements() {
return new Enumeration<E>() {
int pos = 0; public boolean hasMoreElements() {
return pos < elementCount;
} @SuppressWarnings("unchecked")
public E nextElement() {
synchronized (Vector.this) {
if (pos < elementCount) {
return (E) elementData[pos++];
}
}
throw new NoSuchElementException();
}
};
} /**
* Ensures that this vector can hold the specified number of elements
* without growing.
*
* @param minimumCapacity
* the minimum number of elements that this vector will hold
* before growing.
* @see #capacity
*/
public synchronized void ensureCapacity(int minimumCapacity) {
if (elementData.length < minimumCapacity) {
int next = (capacityIncrement <= 0 ? elementData.length
: capacityIncrement)
+ elementData.length;
grow(minimumCapacity > next ? minimumCapacity : next);
}
} /**
* Compares the specified object to this vector and returns if they are
* equal. The object must be a List which contains the same objects in the
* same order.
*
* @param object
* the object to compare with this object
* @return {@code true} if the specified object is equal to this vector,
* {@code false} otherwise.
* @see #hashCode
*/
@Override
public synchronized boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof List) {
List<?> list = (List<?>) object;
if (list.size() != elementCount) {
return false;
} int index = 0;
Iterator<?> it = list.iterator();
while (it.hasNext()) {
Object e1 = elementData[index++], e2 = it.next();
if (!(e1 == null ? e2 == null : e1.equals(e2))) {
return false;
}
}
return true;
}
return false;
} /**
* Returns the first element in this vector.
*
* @return the element at the first position.
* @throws NoSuchElementException
* if this vector is empty.
* @see #elementAt
* @see #lastElement
* @see #size
*/
@SuppressWarnings("unchecked")
public synchronized E firstElement() {
if (elementCount > 0) {
return (E) elementData[0];
}
throw new NoSuchElementException();
} /**
* Returns the element at the specified location in this vector.
*
* @param location
* the index of the element to return in this vector.
* @return the element at the specified location.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
@Override
public E get(int location) {
return elementAt(location);
} private void grow(int newCapacity) {
E[] newData = newElementArray(newCapacity);
// Assumes elementCount is <= newCapacity
assert elementCount <= newCapacity;
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
} /**
* JIT optimization
*/
private void growByOne() {
int adding = 0;
if (capacityIncrement <= 0) {
if ((adding = elementData.length) == 0) {
adding = 1;
}
} else {
adding = capacityIncrement;
} E[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
} private void growBy(int required) {
int adding = 0;
if (capacityIncrement <= 0) {
if ((adding = elementData.length) == 0) {
adding = required;
}
while (adding < required) {
adding += adding;
}
} else {
adding = (required / capacityIncrement) * capacityIncrement;
if (adding < required) {
adding += capacityIncrement;
}
}
E[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
} /**
* Returns an integer hash code for the receiver. Objects which are equal
* return the same value for this method.
*
* @return the receiver's hash.
* @see #equals
*/
@Override
public synchronized int hashCode() {
int result = 1;
for (int i = 0; i < elementCount; i++) {
result = (31 * result)
+ (elementData[i] == null ? 0 : elementData[i].hashCode());
}
return result;
} /**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the beginning and moves towards the end of this
* vector.
*
* @param object
* the object to find in this vector.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @see #contains
* @see #lastIndexOf(Object)
* @see #lastIndexOf(Object, int)
*/
@Override
public int indexOf(Object object) {
return indexOf(object, 0);
} /**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the specified location and moves towards the end
* of this vector.
*
* @param object
* the object to find in this vector.
* @param location
* the index at which to start searching.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0}.
* @see #contains
* @see #lastIndexOf(Object)
* @see #lastIndexOf(Object, int)
*/
public synchronized int indexOf(Object object, int location) {
if (object != null) {
for (int i = location; i < elementCount; i++) {
if (object.equals(elementData[i])) {
return i;
}
}
} else {
for (int i = location; i < elementCount; i++) {
if (elementData[i] == null) {
return i;
}
}
}
return -1;
} /**
* Inserts the specified object into this vector at the specified location.
* This object is inserted before any previous element at the specified
* location. All elements with an index equal or greater than
* {@code location} have their index increased by 1. If the location is
* equal to the size of this vector, the object is added at the end.
*
* @param object
* the object to insert in this vector.
* @param location
* the index at which to insert the element.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location > size()}.
* @see #addElement
* @see #size
*/
public synchronized void insertElementAt(E object, int location) {
if (location >= 0 && location <= elementCount) {
if (elementCount == elementData.length) {
growByOne();
}
int count = elementCount - location;
if (count > 0) {
System.arraycopy(elementData, location, elementData,
location + 1, count);
}
elementData[location] = object;
elementCount++;
modCount++;
} else {
throw arrayIndexOutOfBoundsException(location, elementCount);
}
} /**
* Returns if this vector has no elements, a size of zero.
*
* @return {@code true} if this vector has no elements, {@code false}
* otherwise.
* @see #size
*/
@Override
public synchronized boolean isEmpty() {
return elementCount == 0;
} /**
* Returns the last element in this vector.
*
* @return the element at the last position.
* @throws NoSuchElementException
* if this vector is empty.
* @see #elementAt
* @see #firstElement
* @see #size
*/
@SuppressWarnings("unchecked")
public synchronized E lastElement() {
try {
return (E) elementData[elementCount - 1];
} catch (IndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
} /**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the end and moves towards the start of this
* vector.
*
* @param object
* the object to find in this vector.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @see #contains
* @see #indexOf(Object)
* @see #indexOf(Object, int)
*/
@Override
public synchronized int lastIndexOf(Object object) {
return lastIndexOf(object, elementCount - 1);
} /**
* Searches in this vector for the index of the specified object. The search
* for the object starts at the specified location and moves towards the
* start of this vector.
*
* @param object
* the object to find in this vector.
* @param location
* the index at which to start searching.
* @return the index in this vector of the specified element, -1 if the
* element isn't found.
* @throws ArrayIndexOutOfBoundsException
* if {@code location >= size()}.
* @see #contains
* @see #indexOf(Object)
* @see #indexOf(Object, int)
*/
public synchronized int lastIndexOf(Object object, int location) {
if (location < elementCount) {
if (object != null) {
for (int i = location; i >= 0; i--) {
if (object.equals(elementData[i])) {
return i;
}
}
} else {
for (int i = location; i >= 0; i--) {
if (elementData[i] == null) {
return i;
}
}
}
return -1;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
} /**
* Removes the object at the specified location from this vector. All
* elements with an index bigger than {@code location} have their index
* decreased by 1.
*
* @param location
* the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
*/
@SuppressWarnings("unchecked")
@Override
public synchronized E remove(int location) {
if (location < elementCount) {
E result = (E) elementData[location];
elementCount--;
int size = elementCount - location;
if (size > 0) {
System.arraycopy(elementData, location + 1, elementData,
location, size);
}
elementData[elementCount] = null;
modCount++;
return result;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
} /**
* Removes the first occurrence, starting at the beginning and moving
* towards the end, of the specified object from this vector. All elements
* with an index bigger than the element that gets removed have their index
* decreased by 1.
*
* @param object
* the object to remove from this vector.
* @return {@code true} if the specified object was found, {@code false}
* otherwise.
* @see #removeAllElements
* @see #removeElementAt
* @see #size
*/
@Override
public boolean remove(Object object) {
return removeElement(object);
} /**
* Removes all occurrences in this vector of each object in the specified
* Collection.
*
* @param collection
* the collection of objects to remove.
* @return {@code true} if this vector is modified, {@code false} otherwise.
* @see #remove(Object)
* @see #contains(Object)
*/
@Override
public synchronized boolean removeAll(Collection<?> collection) {
return super.removeAll(collection);
} /**
* Removes all elements from this vector, leaving the size zero and the
* capacity unchanged.
*
* @see #isEmpty
* @see #size
*/
public synchronized void removeAllElements() {
for (int i = 0; i < elementCount; i++) {
elementData[i] = null;
}
modCount++;
elementCount = 0;
} /**
* Removes the first occurrence, starting at the beginning and moving
* towards the end, of the specified object from this vector. All elements
* with an index bigger than the element that gets removed have their index
* decreased by 1.
*
* @param object
* the object to remove from this vector.
* @return {@code true} if the specified object was found, {@code false}
* otherwise.
* @see #removeAllElements
* @see #removeElementAt
* @see #size
*/
public synchronized boolean removeElement(Object object) {
int index;
if ((index = indexOf(object, 0)) == -1) {
return false;
}
removeElementAt(index);
return true;
} /**
* Removes the element found at index position {@code location} from
* this {@code Vector}. All elements with an index bigger than
* {@code location} have their index decreased by 1.
*
* @param location
* the index of the element to remove.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #removeElement
* @see #removeAllElements
* @see #size
*/
public synchronized void removeElementAt(int location) {
if (location >= 0 && location < elementCount) {
elementCount--;
int size = elementCount - location;
if (size > 0) {
System.arraycopy(elementData, location + 1, elementData,
location, size);
}
elementData[elementCount] = null;
modCount++;
} else {
throw arrayIndexOutOfBoundsException(location, elementCount);
}
} /**
* Removes the objects in the specified range from the start to the, but not
* including, end index. All elements with an index bigger than or equal to
* {@code end} have their index decreased by {@code end - start}.
*
* @param start
* the index at which to start removing.
* @param end
* the index one past the end of the range to remove.
* @throws IndexOutOfBoundsException
* if {@code start < 0, start > end} or
* {@code end > size()}.
*/
@Override
protected void removeRange(int start, int end) {
if (start >= 0 && start <= end && end <= elementCount) {
if (start == end) {
return;
}
if (end != elementCount) {
System.arraycopy(elementData, end, elementData, start,
elementCount - end);
int newCount = elementCount - (end - start);
Arrays.fill(elementData, newCount, elementCount, null);
elementCount = newCount;
} else {
Arrays.fill(elementData, start, elementCount, null);
elementCount = start;
}
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
} /**
* Removes all objects from this vector that are not contained in the
* specified collection.
*
* @param collection
* the collection of objects to retain.
* @return {@code true} if this vector is modified, {@code false} otherwise.
* @see #remove(Object)
*/
@Override
public synchronized boolean retainAll(Collection<?> collection) {
return super.retainAll(collection);
} /**
* Replaces the element at the specified location in this vector with the
* specified object.
*
* @param location
* the index at which to put the specified object.
* @param object
* the object to add to this vector.
* @return the previous element at the location.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
@SuppressWarnings("unchecked")
@Override
public synchronized E set(int location, E object) {
if (location < elementCount) {
E result = (E) elementData[location];
elementData[location] = object;
return result;
}
throw arrayIndexOutOfBoundsException(location, elementCount);
} /**
* Replaces the element at the specified location in this vector with the
* specified object.
*
* @param object
* the object to add to this vector.
* @param location
* the index at which to put the specified object.
* @throws ArrayIndexOutOfBoundsException
* if {@code location < 0 || location >= size()}.
* @see #size
*/
public synchronized void setElementAt(E object, int location) {
if (location < elementCount) {
elementData[location] = object;
} else {
throw arrayIndexOutOfBoundsException(location, elementCount);
}
} /**
* This method was extracted to encourage VM to inline callers.
* TODO: when we have a VM that can actually inline, move the test in here too!
*/
private static ArrayIndexOutOfBoundsException arrayIndexOutOfBoundsException(int index, int size) {
throw new ArrayIndexOutOfBoundsException(size, index);
} /**
* Sets the size of this vector to the specified size. If there are more
* than length elements in this vector, the elements at end are lost. If
* there are less than length elements in the vector, the additional
* elements contain null.
*
* @param length
* the new size of this vector.
* @see #size
*/
public synchronized void setSize(int length) {
if (length == elementCount) {
return;
}
ensureCapacity(length);
if (elementCount > length) {
Arrays.fill(elementData, length, elementCount, null);
}
elementCount = length;
modCount++;
} /**
* Returns the number of elements in this vector.
*
* @return the number of elements in this vector.
* @see #elementCount
* @see #lastElement
*/
@Override
public synchronized int size() {
return elementCount;
} /**
* Returns a List of the specified portion of this vector from the start
* index to one less than the end index. The returned List is backed by this
* vector so changes to one are reflected by the other.
*
* @param start
* the index at which to start the sublist.
* @param end
* the index one past the end of the sublist.
* @return a List of a portion of this vector.
* @throws IndexOutOfBoundsException
* if {@code start < 0} or {@code end > size()}.
* @throws IllegalArgumentException
* if {@code start > end}.
*/
@Override
public synchronized List<E> subList(int start, int end) {
return new Collections.SynchronizedRandomAccessList<E>(super.subList(
start, end), this);
} /**
* Returns a new array containing all elements contained in this vector.
*
* @return an array of the elements from this vector.
*/
@Override
public synchronized Object[] toArray() {
Object[] result = new Object[elementCount];
System.arraycopy(elementData, 0, result, 0, elementCount);
return result;
} /**
* Returns an array containing all elements contained in this vector. If the
* specified array is large enough to hold the elements, the specified array
* is used, otherwise an array of the same type is created. If the specified
* array is used and is larger than this vector, the array element following
* the collection elements is set to null.
*
* @param contents
* the array to fill.
* @return an array of the elements from this vector.
* @throws ArrayStoreException
* if the type of an element in this vector cannot be
* stored in the type of the specified array.
*/
@Override
@SuppressWarnings("unchecked")
public synchronized <T> T[] toArray(T[] contents) {
if (elementCount > contents.length) {
Class<?> ct = contents.getClass().getComponentType();
contents = (T[]) Array.newInstance(ct, elementCount);
}
System.arraycopy(elementData, 0, contents, 0, elementCount);
if (elementCount < contents.length) {
contents[elementCount] = null;
}
return contents;
} /**
* Returns the string representation of this vector.
*
* @return the string representation of this vector.
* @see #elements
*/
@Override
public synchronized String toString() {
if (elementCount == 0) {
return "[]";
}
int length = elementCount - 1;
StringBuilder buffer = new StringBuilder(elementCount * 16);
buffer.append('[');
for (int i = 0; i < length; i++) {
if (elementData[i] == this) {
buffer.append("(this Collection)");
} else {
buffer.append(elementData[i]);
}
buffer.append(", ");
}
if (elementData[length] == this) {
buffer.append("(this Collection)");
} else {
buffer.append(elementData[length]);
}
buffer.append(']');
return buffer.toString();
} /**
* Sets the capacity of this vector to be the same as the size.
*
* @see #capacity
* @see #ensureCapacity
* @see #size
*/
public synchronized void trimToSize() {
if (elementData.length != elementCount) {
grow(elementCount);
}
} private synchronized void writeObject(ObjectOutputStream stream)
throws IOException {
stream.defaultWriteObject();
}
}
ArrayList
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/ package java.util; import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array;
import libcore.util.EmptyArray; /**
* ArrayList is an implementation of {@link List}, backed by an array.
* All optional operations including adding, removing, and replacing elements are supported.
*
* <p>All elements are permitted, including null.
*
* <p>This class is a good choice as your default {@code List} implementation.
* {@link Vector} synchronizes all operations, but not necessarily in a way that's
* meaningful to your application: synchronizing each call to {@code get}, for example, is not
* equivalent to synchronizing the list and iterating over it (which is probably what you intended).
* {@link java.util.concurrent.CopyOnWriteArrayList} is intended for the special case of very high
* concurrency, frequent traversals, and very rare mutations.
*
* @param <E> The element type of this list.
* @since 1.2
*/
public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
/**
* The minimum amount by which the capacity of an ArrayList will increase.
* This tuning parameter controls a time-space tradeoff. This value (12)
* gives empirically good results and is arguably consistent with the
* RI's specified default initial capacity of 10: instead of 10, we start
* with 0 (sans allocation) and jump to 12.
*/
private static final int MIN_CAPACITY_INCREMENT = 12; /**
* The number of elements in this list.
*/
int size; /**
* The elements in this list, followed by nulls.
*/
transient Object[] array; /**
* Constructs a new instance of {@code ArrayList} with the specified
* initial capacity.
*
* @param capacity
* the initial capacity of this {@code ArrayList}.
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException();
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
} /**
* Constructs a new {@code ArrayList} instance with zero initial capacity.
*/
public ArrayList() {
array = EmptyArray.OBJECT;
} /**
* Constructs a new instance of {@code ArrayList} containing the elements of
* the specified collection.
*
* @param collection
* the collection of elements to add.
*/
public ArrayList(Collection<? extends E> collection) {
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
} /**
* Adds the specified object at the end of this {@code ArrayList}.
*
* @param object
* the object to add.
* @return always true
*/
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
} /**
* Inserts the specified object into this {@code ArrayList} at the specified
* location. The object is inserted before any previous element at the
* specified location. If the location is equal to the size of this
* {@code ArrayList}, the object is added at the end.
*
* @param index
* the index at which to insert the object.
* @param object
* the object to add.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || > size()}
*/
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
} if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
} /**
* This method controls the growth of ArrayList capacities. It represents
* a time-space tradeoff: we don't want to grow lists too frequently
* (which wastes time and fragments storage), but we don't want to waste
* too much space in unused excess capacity.
*
* NOTE: This method is inlined into {@link #add(Object)} for performance.
* If you change the method, change it there too!
*/
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
} /**
* Adds the objects in the specified collection to this {@code ArrayList}.
*
* @param collection
* the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
*/
@Override public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
} /**
* Inserts the objects in the specified collection at the specified location
* in this List. The objects are added in the order they are returned from
* the collection's iterator.
*
* @param index
* the index at which to insert.
* @param collection
* the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || > size()}
*/
@Override
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
} /**
* This method was extracted to encourage VM to inline callers.
* TODO: when we have a VM that can actually inline, move the test in here too!
*/
static IndexOutOfBoundsException throwIndexOutOfBoundsException(int index, int size) {
throw new IndexOutOfBoundsException("Invalid index " + index + ", size is " + size);
} /**
* Removes all elements from this {@code ArrayList}, leaving it empty.
*
* @see #isEmpty
* @see #size
*/
@Override public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
} /**
* Returns a new {@code ArrayList} with the same elements, the same size and
* the same capacity as this {@code ArrayList}.
*
* @return a shallow copy of this {@code ArrayList}
* @see java.lang.Cloneable
*/
@Override public Object clone() {
try {
ArrayList<?> result = (ArrayList<?>) super.clone();
result.array = array.clone();
return result;
} catch (CloneNotSupportedException e) {
throw new AssertionError();
}
} /**
* Ensures that after this operation the {@code ArrayList} can hold the
* specified number of elements without further growing.
*
* @param minimumCapacity
* the minimum capacity asked for.
*/
public void ensureCapacity(int minimumCapacity) {
Object[] a = array;
if (a.length < minimumCapacity) {
Object[] newArray = new Object[minimumCapacity];
System.arraycopy(a, 0, newArray, 0, size);
array = newArray;
modCount++;
}
} @SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
} /**
* Returns the number of elements in this {@code ArrayList}.
*
* @return the number of elements in this {@code ArrayList}.
*/
@Override public int size() {
return size;
} @Override public boolean isEmpty() {
return size == 0;
} /**
* Searches this {@code ArrayList} for the specified object.
*
* @param object
* the object to search for.
* @return {@code true} if {@code object} is an element of this
* {@code ArrayList}, {@code false} otherwise
*/
@Override public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
} @Override public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;
}
}
}
return -1;
} @Override public int lastIndexOf(Object object) {
Object[] a = array;
if (object != null) {
for (int i = size - 1; i >= 0; i--) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (a[i] == null) {
return i;
}
}
}
return -1;
} /**
* Removes the object at the specified location from this list.
*
* @param index
* the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || >= size()}
*/
@Override public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
} @Override public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
}
return false;
} @Override protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex == toIndex) {
return;
}
Object[] a = array;
int s = size;
if (fromIndex >= s) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " >= size " + size);
}
if (toIndex > s) {
throw new IndexOutOfBoundsException("toIndex " + toIndex
+ " > size " + size);
}
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " > toIndex " + toIndex);
} System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromIndex;
Arrays.fill(a, s - rangeSize, s, null);
size = s - rangeSize;
modCount++;
} /**
* Replaces the element at the specified location in this {@code ArrayList}
* with the specified object.
*
* @param index
* the index at which to put the specified object.
* @param object
* the object to add.
* @return the previous element at the index.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || >= size()}
*/
@Override public E set(int index, E object) {
Object[] a = array;
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
a[index] = object;
return result;
} /**
* Returns a new array containing all elements contained in this
* {@code ArrayList}.
*
* @return an array of the elements from this {@code ArrayList}
*/
@Override public Object[] toArray() {
int s = size;
Object[] result = new Object[s];
System.arraycopy(array, 0, result, 0, s);
return result;
} /**
* Returns an array containing all elements contained in this
* {@code ArrayList}. If the specified array is large enough to hold the
* elements, the specified array is used, otherwise an array of the same
* type is created. If the specified array is used and is larger than this
* {@code ArrayList}, the array element following the collection elements
* is set to null.
*
* @param contents
* the array.
* @return an array of the elements from this {@code ArrayList}.
* @throws ArrayStoreException
* when the type of an element in this {@code ArrayList} cannot
* be stored in the type of the specified array.
*/
@Override public <T> T[] toArray(T[] contents) {
int s = size;
if (contents.length < s) {
@SuppressWarnings("unchecked") T[] newArray
= (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
contents = newArray;
}
System.arraycopy(this.array, 0, contents, 0, s);
if (contents.length > s) {
contents[s] = null;
}
return contents;
} /**
* Sets the capacity of this {@code ArrayList} to be the same as the current
* size.
*
* @see #size
*/
public void trimToSize() {
int s = size;
if (s == array.length) {
return;
}
if (s == 0) {
array = EmptyArray.OBJECT;
} else {
Object[] newArray = new Object[s];
System.arraycopy(array, 0, newArray, 0, s);
array = newArray;
}
modCount++;
} @Override public Iterator<E> iterator() {
return new ArrayListIterator();
} private class ArrayListIterator implements Iterator<E> {
/** Number of elements remaining in this iteration */
private int remaining = size; /** Index of element that remove() would remove, or -1 if no such elt */
private int removalIndex = -1; /** The expected modCount value */
private int expectedModCount = modCount; public boolean hasNext() {
return remaining != 0;
} @SuppressWarnings("unchecked") public E next() {
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (rem == 0) {
throw new NoSuchElementException();
}
remaining = rem - 1;
return (E) ourList.array[removalIndex = ourList.size - rem];
} public void remove() {
Object[] a = array;
int removalIdx = removalIndex;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (removalIdx < 0) {
throw new IllegalStateException();
}
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak
removalIndex = -1;
expectedModCount = ++modCount;
}
} @Override public int hashCode() {
Object[] a = array;
int hashCode = 1;
for (int i = 0, s = size; i < s; i++) {
Object e = a[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
} @Override public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof List)) {
return false;
}
List<?> that = (List<?>) o;
int s = size;
if (that.size() != s) {
return false;
}
Object[] a = array;
if (that instanceof RandomAccess) {
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object ethat = that.get(i);
if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
return false;
}
}
} else { // Argument list is not random access; use its iterator
Iterator<?> it = that.iterator();
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object eThat = it.next();
if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
return false;
}
}
}
return true;
} private static final long serialVersionUID = 8683452581122892189L; private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeInt(array.length);
for (int i = 0; i < size; i++) {
stream.writeObject(array[i]);
}
} private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
stream.defaultReadObject();
int cap = stream.readInt();
if (cap < size) {
throw new InvalidObjectException(
"Capacity: " + cap + " < size: " + size);
}
array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]);
for (int i = 0; i < size; i++) {
array[i] = stream.readObject();
}
}
}
package java.util;
public abstract class Dictionary<K, V> {
public Dictionary() {
}
public abstract Enumeration<V> elements();
public abstract V get(Object key);
public abstract boolean isEmpty();
public abstract Enumeration<K> keys();
public abstract V put(K key, V value);
public abstract V remove(Object key);
public abstract int size();
}
Map Interface
package java.util;
public interface Map<K,V> {
/**
* {@code Map.Entry} is a key/value mapping contained in a {@code Map}.
*/
public static interface Entry<K,V> {
public boolean equals(Object object);
public K getKey();
public V getValue();
public int hashCode();
public V setValue(V object);
};
public void clear();
public boolean containsKey(Object key);
public boolean containsValue(Object value);
public Set<Map.Entry<K,V>> entrySet();
public boolean equals(Object object);
public V get(Object key);
public int hashCode();
public boolean isEmpty();
public Set<K> keySet();
public V put(K key, V value);
public void putAll(Map<? extends K,? extends V> map);
public V remove(Object key);
public int size();
public Collection<V> values();
}
SortedMap Interface
package java.util;
public interface SortedMap<K,V> extends Map<K,V> {
public Comparator<? super K> comparator();
public K firstKey();
public SortedMap<K,V> headMap(K endKey);
public K lastKey();
public SortedMap<K,V> subMap(K startKey, K endKey);
public SortedMap<K,V> tailMap(K startKey);
}
AbstractMap
package java.util;
import java.io.Serializable;
public abstract class AbstractMap<K, V> implements Map<K, V> { // Lazily initialized key set.
Set<K> keySet;
Collection<V> valuesCollection;
public static class SimpleImmutableEntry<K, V>
implements Map.Entry<K, V>, Serializable {
private static final long serialVersionUID = 7138329143949025153L; private final K key;
private final V value; public SimpleImmutableEntry(K theKey, V theValue) {
key = theKey;
value = theValue;
}
public SimpleImmutableEntry(Map.Entry<? extends K, ? extends V> copyFrom) {
key = copyFrom.getKey();
value = copyFrom.getValue();
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V object) {
throw new UnsupportedOperationException();
}
@Override
public boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof Map.Entry) {
Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
return (key == null ? entry.getKey() == null : key.equals(entry
.getKey()))
&& (value == null ? entry.getValue() == null : value
.equals(entry.getValue()));
}
return false;
}
@Override public int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}
@Override public String toString() {
return key + "=" + value;
}
}
public static class SimpleEntry<K, V> implements Map.Entry<K, V>, Serializable {
private static final long serialVersionUID = -8499721149061103585L; private final K key;
private V value; public SimpleEntry(K theKey, V theValue) {
key = theKey;
value = theValue;
}
public SimpleEntry(Map.Entry<? extends K, ? extends V> copyFrom) {
key = copyFrom.getKey();
value = copyFrom.getValue();
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V object) {
V result = value;
value = object;
return result;
}
@Override
public boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof Map.Entry) {
Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
return (key == null ? entry.getKey() == null : key.equals(entry
.getKey()))
&& (value == null ? entry.getValue() == null : value
.equals(entry.getValue()));
}
return false;
}
@Override
public int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
}
@Override
public String toString() {
return key + "=" + value;
}
}
protected AbstractMap() {
} public void clear() {
entrySet().clear();
} public boolean containsKey(Object key) {
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
if (key != null) {
while (it.hasNext()) {
if (key.equals(it.next().getKey())) {
return true;
}
}
} else {
while (it.hasNext()) {
if (it.next().getKey() == null) {
return true;
}
}
}
return false;
}
public boolean containsValue(Object value) {
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
if (value != null) {
while (it.hasNext()) {
if (value.equals(it.next().getValue())) {
return true;
}
}
} else {
while (it.hasNext()) {
if (it.next().getValue() == null) {
return true;
}
}
}
return false;
} public abstract Set<Map.Entry<K, V>> entrySet();
@Override
public boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof Map) {
Map<?, ?> map = (Map<?, ?>) object;
if (size() != map.size()) {
return false;
} try {
for (Entry<K, V> entry : entrySet()) {
K key = entry.getKey();
V mine = entry.getValue();
Object theirs = map.get(key);
if (mine == null) {
if (theirs != null || !map.containsKey(key)) {
return false;
}
} else if (!mine.equals(theirs)) {
return false;
}
}
} catch (NullPointerException ignored) {
return false;
} catch (ClassCastException ignored) {
return false;
}
return true;
}
return false;
}
public V get(Object key) {
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
if (key != null) {
while (it.hasNext()) {
Map.Entry<K, V> entry = it.next();
if (key.equals(entry.getKey())) {
return entry.getValue();
}
}
} else {
while (it.hasNext()) {
Map.Entry<K, V> entry = it.next();
if (entry.getKey() == null) {
return entry.getValue();
}
}
}
return null;
}
@Override public int hashCode() {
int result = 0;
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
while (it.hasNext()) {
result += it.next().hashCode();
}
return result;
}
public boolean isEmpty() {
return size() == 0;
}
public Set<K> keySet() {
if (keySet == null) {
keySet = new AbstractSet<K>() {
@Override public boolean contains(Object object) {
return containsKey(object);
} @Override public int size() {
return AbstractMap.this.size();
} @Override public Iterator<K> iterator() {
return new Iterator<K>() {
Iterator<Map.Entry<K, V>> setIterator = entrySet().iterator(); public boolean hasNext() {
return setIterator.hasNext();
} public K next() {
return setIterator.next().getKey();
} public void remove() {
setIterator.remove();
}
};
}
};
}
return keySet;
}
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
public void putAll(Map<? extends K, ? extends V> map) {
for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
public V remove(Object key) {
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
if (key != null) {
while (it.hasNext()) {
Map.Entry<K, V> entry = it.next();
if (key.equals(entry.getKey())) {
it.remove();
return entry.getValue();
}
}
} else {
while (it.hasNext()) {
Map.Entry<K, V> entry = it.next();
if (entry.getKey() == null) {
it.remove();
return entry.getValue();
}
}
}
return null;
}
public int size() {
return entrySet().size();
}
@Override public String toString() {
if (isEmpty()) {
return "{}";
} StringBuilder buffer = new StringBuilder(size() * 28);
buffer.append('{');
Iterator<Map.Entry<K, V>> it = entrySet().iterator();
while (it.hasNext()) {
Map.Entry<K, V> entry = it.next();
Object key = entry.getKey();
if (key != this) {
buffer.append(key);
} else {
buffer.append("(this Map)");
}
buffer.append('=');
Object value = entry.getValue();
if (value != this) {
buffer.append(value);
} else {
buffer.append("(this Map)");
}
if (it.hasNext()) {
buffer.append(", ");
}
}
buffer.append('}');
return buffer.toString();
}
public Collection<V> values() {
if (valuesCollection == null) {
valuesCollection = new AbstractCollection<V>() {
@Override public int size() {
return AbstractMap.this.size();
} @Override public boolean contains(Object object) {
return containsValue(object);
} @Override public Iterator<V> iterator() {
return new Iterator<V>() {
Iterator<Map.Entry<K, V>> setIterator = entrySet().iterator(); public boolean hasNext() {
return setIterator.hasNext();
} public V next() {
return setIterator.next().getValue();
} public void remove() {
setIterator.remove();
}
};
}
};
}
return valuesCollection;
}
@SuppressWarnings("unchecked")
@Override
protected Object clone() throws CloneNotSupportedException {
AbstractMap<K, V> result = (AbstractMap<K, V>) super.clone();
result.keySet = null;
result.valuesCollection = null;
return result;
}
}
HashMap
package java.util;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.ObjectStreamField;
import java.io.Serializable;
import java.util.Map.Entry; import libcore.util.Objects; /**
* HashMap is an implementation of {@link Map}. All optional operations are supported.
*
* <p>All elements are permitted as keys or values, including null.
*
* <p>Note that the iteration order for HashMap is non-deterministic. If you want
* deterministic iteration, use {@link LinkedHashMap}.
*
* <p>Note: the implementation of {@code HashMap} is not synchronized.
* If one thread of several threads accessing an instance modifies the map
* structurally, access to the map needs to be synchronized. A structural
* modification is an operation that adds or removes an entry. Changes in
* the value of an entry are not structural changes.
*
* <p>The {@code Iterator} created by calling the {@code iterator} method
* may throw a {@code ConcurrentModificationException} if the map is structurally
* changed while an iterator is used to iterate over the elements. Only the
* {@code remove} method that is provided by the iterator allows for removal of
* elements during iteration. It is not possible to guarantee that this
* mechanism works in all cases of unsynchronized concurrent modification. It
* should only be used for debugging purposes.
*
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*/
public class HashMap<K, V> extends AbstractMap<K, V> implements Cloneable, Serializable {
/**
* Min capacity (other than zero) for a HashMap. Must be a power of two
* greater than 1 (and less than 1 << 30).
*/
private static final int MINIMUM_CAPACITY = 4; /**
* Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY.
*/
private static final int MAXIMUM_CAPACITY = 1 << 30; /**
* An empty table shared by all zero-capacity maps (typically from default
* constructor). It is never written to, and replaced on first put. Its size
* is set to half the minimum, so that the first resize will create a
* minimum-sized table.
*/
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1]; /**
* The default load factor. Note that this implementation ignores the
* load factor, but cannot do away with it entirely because it's
* mentioned in the API.
*
* <p>Note that this constant has no impact on the behavior of the program,
* but it is emitted as part of the serialized form. The load factor of
* .75 is hardwired into the program, which uses cheap shifts in place of
* expensive division.
*/
static final float DEFAULT_LOAD_FACTOR = .75F; /**
* The hash table. If this hash map contains a mapping for null, it is
* not represented this hash table.
*/
transient HashMapEntry<K, V>[] table; /**
* The entry representing the null key, or null if there's no such mapping.
*/
transient HashMapEntry<K, V> entryForNullKey; /**
* The number of mappings in this hash map.
*/
transient int size; /**
* Incremented by "structural modifications" to allow (best effort)
* detection of concurrent modification.
*/
transient int modCount; /**
* The table is rehashed when its size exceeds this threshold.
* The value of this field is generally .75 * capacity, except when
* the capacity is zero, as described in the EMPTY_TABLE declaration
* above.
*/
private transient int threshold; // Views - lazily initialized
private transient Set<K> keySet;
private transient Set<Entry<K, V>> entrySet;
private transient Collection<V> values; /**
* Constructs a new empty {@code HashMap} instance.
*/
@SuppressWarnings("unchecked")
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
} /**
* Constructs a new {@code HashMap} instance with the specified capacity.
*
* @param capacity
* the initial capacity of this hash map.
* @throws IllegalArgumentException
* when the capacity is less than zero.
*/
public HashMap(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity: " + capacity);
} if (capacity == 0) {
@SuppressWarnings("unchecked")
HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
table = tab;
threshold = -1; // Forces first put() to replace EMPTY_TABLE
return;
} if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {
capacity = roundUpToPowerOfTwo(capacity);
}
makeTable(capacity);
} /**
* Constructs a new {@code HashMap} instance with the specified capacity and
* load factor.
*
* @param capacity
* the initial capacity of this hash map.
* @param loadFactor
* the initial load factor.
* @throws IllegalArgumentException
* when the capacity is less than zero or the load factor is
* less or equal to zero or NaN.
*/
public HashMap(int capacity, float loadFactor) {
this(capacity); if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
} /*
* Note that this implementation ignores loadFactor; it always uses
* a load factor of 3/4. This simplifies the code and generally
* improves performance.
*/
} /**
* Constructs a new {@code HashMap} instance containing the mappings from
* the specified map.
*
* @param map
* the mappings to add.
*/
public HashMap(Map<? extends K, ? extends V> map) {
this(capacityForInitSize(map.size()));
constructorPutAll(map);
} /**
* Inserts all of the elements of map into this HashMap in a manner
* suitable for use by constructors and pseudo-constructors (i.e., clone,
* readObject). Also used by LinkedHashMap.
*/
final void constructorPutAll(Map<? extends K, ? extends V> map) {
for (Entry<? extends K, ? extends V> e : map.entrySet()) {
constructorPut(e.getKey(), e.getValue());
}
} /**
* Returns an appropriate capacity for the specified initial size. Does
* not round the result up to a power of two; the caller must do this!
* The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive).
*/
static int capacityForInitSize(int size) {
int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY
return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY;
} /**
* Returns a shallow copy of this map.
*
* @return a shallow copy of this map.
*/
@SuppressWarnings("unchecked")
@Override public Object clone() {
/*
* This could be made more efficient. It unnecessarily hashes all of
* the elements in the map.
*/
HashMap<K, V> result;
try {
result = (HashMap<K, V>) super.clone();
} catch (CloneNotSupportedException e) {
throw new AssertionError(e);
} // Restore clone to empty state, retaining our capacity and threshold
result.makeTable(table.length);
result.entryForNullKey = null;
result.size = 0;
result.keySet = null;
result.entrySet = null;
result.values = null; result.init(); // Give subclass a chance to initialize itself
result.constructorPutAll(this); // Calls method overridden in subclass!!
return result;
} /**
* This method is called from the pseudo-constructors (clone and readObject)
* prior to invoking constructorPut/constructorPutAll, which invoke the
* overridden constructorNewEntry method. Normally it is a VERY bad idea to
* invoke an overridden method from a pseudo-constructor (Effective Java
* Item 17). In this case it is unavoidable, and the init method provides a
* workaround.
*/
void init() { } /**
* Returns whether this map is empty.
*
* @return {@code true} if this map has no elements, {@code false}
* otherwise.
* @see #size()
*/
@Override public boolean isEmpty() {
return size == 0;
} /**
* Returns the number of elements in this map.
*
* @return the number of elements in this map.
*/
@Override public int size() {
return size;
} /**
* Returns the value of the mapping with the specified key.
*
* @param key
* the key.
* @return the value of the mapping with the specified key, or {@code null}
* if no mapping for the specified key is found.
*/
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
} // Doug Lea's supplemental secondaryHash function (inlined)
int hash = key.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12);
hash ^= (hash >>> 7) ^ (hash >>> 4); HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next)
{
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
} /**
* Returns whether this map contains the specified key.
*
* @param key
* the key to search for.
* @return {@code true} if this map contains the specified key,
* {@code false} otherwise.
*/
@Override public boolean containsKey(Object key) {
if (key == null) {
return entryForNullKey != null;
} // Doug Lea's supplemental secondaryHash function (inlined)
int hash = key.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12);
hash ^= (hash >>> 7) ^ (hash >>> 4); HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return true;
}
}
return false;
} /**
* Returns whether this map contains the specified value.
*
* @param value
* the value to search for.
* @return {@code true} if this map contains the specified value,
* {@code false} otherwise.
*/
@Override public boolean containsValue(Object value) {
HashMapEntry[] tab = table;
int len = tab.length;
if (value == null) {
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (e.value == null) {
return true;
}
}
}
return entryForNullKey != null && entryForNullKey.value == null;
} // value is non-null
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (value.equals(e.value)) {
return true;
}
}
}
return entryForNullKey != null && value.equals(entryForNullKey.value);
} /**
* Maps the specified key to the specified value.
*
* @param key
* the key.
* @param value
* the value.
* @return the value of any previous mapping with the specified key or
* {@code null} if there was no such mapping.
*/
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
} int hash = secondaryHash(key.hashCode());
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
} // No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
} private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
addNewEntryForNullKey(value);
size++;
modCount++;
return null;
} else {
preModify(entry);
V oldValue = entry.value;
entry.value = value;
return oldValue;
}
} /**
* Give LinkedHashMap a chance to take action when we modify an existing
* entry.
*
* @param e the entry we're about to modify.
*/
void preModify(HashMapEntry<K, V> e) { } /**
* This method is just like put, except that it doesn't do things that
* are inappropriate or unnecessary for constructors and pseudo-constructors
* (i.e., clone, readObject). In particular, this method does not check to
* ensure that capacity is sufficient, and does not increment modCount.
*/
private void constructorPut(K key, V value) {
if (key == null) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
entryForNullKey = constructorNewEntry(null, value, 0, null);
size++;
} else {
entry.value = value;
}
return;
} int hash = secondaryHash(key.hashCode());
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
HashMapEntry<K, V> first = tab[index];
for (HashMapEntry<K, V> e = first; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
e.value = value;
return;
}
} // No entry for (non-null) key is present; create one
tab[index] = constructorNewEntry(key, value, hash, first);
size++;
} /**
* Creates a new entry for the given key, value, hash, and index and
* inserts it into the hash table. This method is called by put
* (and indirectly, putAll), and overridden by LinkedHashMap. The hash
* must incorporate the secondary hash function.
*/
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
} /**
* Creates a new entry for the null key, and the given value and
* inserts it into the hash table. This method is called by put
* (and indirectly, putAll), and overridden by LinkedHashMap.
*/
void addNewEntryForNullKey(V value) {
entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
} /**
* Like newEntry, but does not perform any activity that would be
* unnecessary or inappropriate for constructors. In this class, the
* two methods behave identically; in LinkedHashMap, they differ.
*/
HashMapEntry<K, V> constructorNewEntry(
K key, V value, int hash, HashMapEntry<K, V> first) {
return new HashMapEntry<K, V>(key, value, hash, first);
} /**
* Copies all the mappings in the specified map to this map. These mappings
* will replace all mappings that this map had for any of the keys currently
* in the given map.
*
* @param map
* the map to copy mappings from.
*/
@Override public void putAll(Map<? extends K, ? extends V> map) {
ensureCapacity(map.size());
super.putAll(map);
} /**
* Ensures that the hash table has sufficient capacity to store the
* specified number of mappings, with room to grow. If not, it increases the
* capacity as appropriate. Like doubleCapacity, this method moves existing
* entries to new buckets as appropriate. Unlike doubleCapacity, this method
* can grow the table by factors of 2^n for n > 1. Hopefully, a single call
* to this method will be faster than multiple calls to doubleCapacity.
*
* <p>This method is called only by putAll.
*/
private void ensureCapacity(int numMappings) {
int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings));
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (newCapacity <= oldCapacity) {
return;
}
if (newCapacity == oldCapacity * 2) {
doubleCapacity();
return;
} // We're growing by at least 4x, rehash in the obvious way
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size != 0) {
int newMask = newCapacity - 1;
for (int i = 0; i < oldCapacity; i++) {
for (HashMapEntry<K, V> e = oldTable[i]; e != null;) {
HashMapEntry<K, V> oldNext = e.next;
int newIndex = e.hash & newMask;
HashMapEntry<K, V> newNext = newTable[newIndex];
newTable[newIndex] = e;
e.next = newNext;
e = oldNext;
}
}
}
} /**
* Allocate a table of the given capacity and set the threshold accordingly.
* @param newCapacity must be a power of two
*/
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
= (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
table = newTable;
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
return newTable;
} /**
* Doubles the capacity of the hash table. Existing entries are placed in
* the correct bucket on the enlarged table. If the current capacity is,
* MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which
* will be new unless we were already at MAXIMUM_CAPACITY.
*/
private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
int newCapacity = oldCapacity * 2;
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
if (size == 0) {
return newTable;
} for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];
if (e == null) {
continue;
}
int highBit = e.hash & oldCapacity;
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
} /**
* Removes the mapping with the specified key from this map.
*
* @param key
* the key of the mapping to remove.
* @return the value of the removed mapping or {@code null} if no mapping
* for the specified key was found.
*/
@Override public V remove(Object key) {
if (key == null) {
return removeNullKey();
}
int hash = secondaryHash(key.hashCode());
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index], prev = null;
e != null; prev = e, e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
modCount++;
size--;
postRemove(e);
return e.value;
}
}
return null;
} private V removeNullKey() {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null) {
return null;
}
entryForNullKey = null;
modCount++;
size--;
postRemove(e);
return e.value;
} /**
* Subclass overrides this method to unlink entry.
*/
void postRemove(HashMapEntry<K, V> e) { } /**
* Removes all mappings from this hash map, leaving it empty.
*
* @see #isEmpty
* @see #size
*/
@Override public void clear() {
if (size != 0) {
Arrays.fill(table, null);
entryForNullKey = null;
modCount++;
size = 0;
}
} /**
* Returns a set of the keys contained in this map. The set is backed by
* this map so changes to one are reflected by the other. The set does not
* support adding.
*
* @return a set of the keys.
*/
@Override public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null) ? ks : (keySet = new KeySet());
} /**
* Returns a collection of the values contained in this map. The collection
* is backed by this map so changes to one are reflected by the other. The
* collection supports remove, removeAll, retainAll and clear operations,
* and it does not support add or addAll operations.
* <p>
* This method returns a collection which is the subclass of
* AbstractCollection. The iterator method of this subclass returns a
* "wrapper object" over the iterator of map's entrySet(). The {@code size}
* method wraps the map's size method and the {@code contains} method wraps
* the map's containsValue method.
* </p>
* <p>
* The collection is created when this method is called for the first time
* and returned in response to all subsequent calls. This method may return
* different collections when multiple concurrent calls occur, since no
* synchronization is performed.
* </p>
*
* @return a collection of the values contained in this map.
*/
@Override public Collection<V> values() {
Collection<V> vs = values;
return (vs != null) ? vs : (values = new Values());
} /**
* Returns a set containing all of the mappings in this map. Each mapping is
* an instance of {@link Map.Entry}. As the set is backed by this map,
* changes in one will be reflected in the other.
*
* @return a set of the mappings.
*/
public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
} static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashMapEntry<K, V> next; HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
} public final K getKey() {
return key;
} public final V getValue() {
return value;
} public final V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
} @Override public final boolean equals(Object o) {
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> e = (Entry<?, ?>) o;
return Objects.equal(e.getKey(), key)
&& Objects.equal(e.getValue(), value);
} @Override public final int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
} @Override public final String toString() {
return key + "=" + value;
}
} private abstract class HashIterator {
int nextIndex;
HashMapEntry<K, V> nextEntry = entryForNullKey;
HashMapEntry<K, V> lastEntryReturned;
int expectedModCount = modCount; HashIterator() {
if (nextEntry == null) {
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = null;
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
}
} public boolean hasNext() {
return nextEntry != null;
} HashMapEntry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == null)
throw new NoSuchElementException(); HashMapEntry<K, V> entryToReturn = nextEntry;
HashMapEntry<K, V>[] tab = table;
HashMapEntry<K, V> next = entryToReturn.next;
while (next == null && nextIndex < tab.length) {
next = tab[nextIndex++];
}
nextEntry = next;
return lastEntryReturned = entryToReturn;
} public void remove() {
if (lastEntryReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
HashMap.this.remove(lastEntryReturned.key);
lastEntryReturned = null;
expectedModCount = modCount;
}
} private final class KeyIterator extends HashIterator
implements Iterator<K> {
public K next() { return nextEntry().key; }
} private final class ValueIterator extends HashIterator
implements Iterator<V> {
public V next() { return nextEntry().value; }
} private final class EntryIterator extends HashIterator
implements Iterator<Entry<K, V>> {
public Entry<K, V> next() { return nextEntry(); }
} /**
* Returns true if this map contains the specified mapping.
*/
private boolean containsMapping(Object key, Object value) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e != null && Objects.equal(value, e.value);
} int hash = secondaryHash(key.hashCode());
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
return Objects.equal(value, e.value);
}
}
return false; // No entry for key
} /**
* Removes the mapping from key to value and returns true if this mapping
* exists; otherwise, returns does nothing and returns false.
*/
private boolean removeMapping(Object key, Object value) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null || !Objects.equal(value, e.value)) {
return false;
}
entryForNullKey = null;
modCount++;
size--;
postRemove(e);
return true;
} int hash = secondaryHash(key.hashCode());
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index], prev = null;
e != null; prev = e, e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
if (!Objects.equal(value, e.value)) {
return false; // Map has wrong value for key
}
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
modCount++;
size--;
postRemove(e);
return true;
}
}
return false; // No entry for key
} // Subclass (LinkedHashMap) overrides these for correct iteration order
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Entry<K, V>> newEntryIterator() { return new EntryIterator(); } private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
int oldSize = size;
HashMap.this.remove(o);
return size != oldSize;
}
public void clear() {
HashMap.this.clear();
}
} private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
} private final class EntrySet extends AbstractSet<Entry<K, V>> {
public Iterator<Entry<K, V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Entry))
return false;
Entry<?, ?> e = (Entry<?, ?>) o;
return containsMapping(e.getKey(), e.getValue());
}
public boolean remove(Object o) {
if (!(o instanceof Entry))
return false;
Entry<?, ?> e = (Entry<?, ?>)o;
return removeMapping(e.getKey(), e.getValue());
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
HashMap.this.clear();
}
} /**
* Applies a supplemental hash function to a given hashCode, which defends
* against poor quality hash functions. This is critical because HashMap
* uses power-of-two length hash tables, that otherwise encounter collisions
* for hashCodes that do not differ in lower or upper bits.
*/
private static int secondaryHash(int h) {
// Doug Lea's supplemental hash function
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
} /**
* Returns the smallest power of two >= its argument, with several caveats:
* If the argument is negative but not Integer.MIN_VALUE, the method returns
* zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method
* returns Integer.MIN_VALUE. If the argument is zero, the method returns
* zero.
*/
private static int roundUpToPowerOfTwo(int i) {
i--; // If input is a power of two, shift its high-order bit right // "Smear" the high-order bit all the way to the right
i |= i >>> 1;
i |= i >>> 2;
i |= i >>> 4;
i |= i >>> 8;
i |= i >>> 16; return i + 1;
} private static final long serialVersionUID = 362498820763181265L; private static final ObjectStreamField[] serialPersistentFields = {
new ObjectStreamField("loadFactor", float.class)
}; private void writeObject(ObjectOutputStream stream) throws IOException {
// Emulate loadFactor field for other implementations to read
ObjectOutputStream.PutField fields = stream.putFields();
fields.put("loadFactor", DEFAULT_LOAD_FACTOR);
stream.writeFields(); stream.writeInt(table.length); // Capacity
stream.writeInt(size);
for (Entry<K, V> e : entrySet()) {
stream.writeObject(e.getKey());
stream.writeObject(e.getValue());
}
} private void readObject(ObjectInputStream stream) throws IOException,
ClassNotFoundException {
stream.defaultReadObject();
int capacity = stream.readInt();
if (capacity < 0) {
throw new InvalidObjectException("Capacity: " + capacity);
}
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {
capacity = roundUpToPowerOfTwo(capacity);
}
makeTable(capacity); int size = stream.readInt();
if (size < 0) {
throw new InvalidObjectException("Size: " + size);
} init(); // Give subclass (LinkedHashMap) a chance to initialize itself
for (int i = 0; i < size; i++) {
@SuppressWarnings("unchecked") K key = (K) stream.readObject();
@SuppressWarnings("unchecked") V val = (V) stream.readObject();
constructorPut(key, val);
}
}
}
TreeMap
package java.util;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectInputStream.GetField;
import java.io.ObjectOutputStream;
import java.io.ObjectStreamException;
import java.io.Serializable;
import static java.util.TreeMap.Bound.*;
import static java.util.TreeMap.Relation.*;
import libcore.util.Objects;
/**
* A map whose entries are sorted by their keys. All optional operations such as
* {@link #put} and {@link #remove} are supported.
*
* <p>This map sorts keys using either a user-supplied comparator or the key's
* natural order:
* <ul>
* <li>User supplied comparators must be able to compare any pair of keys in
* this map. If a user-supplied comparator is in use, it will be returned
* by {@link #comparator}.
* <li>If no user-supplied comparator is supplied, keys will be sorted by
* their natural order. Keys must be <i>mutually comparable</i>: they must
* implement {@link Comparable} and {@link Comparable#compareTo
* compareTo()} must be able to compare each key with any other key in
* this map. In this case {@link #comparator} will return null.
* </ul>
* With either a comparator or a natural ordering, comparisons should be
* <i>consistent with equals</i>. An ordering is consistent with equals if for
* every pair of keys {@code a} and {@code b}, {@code a.equals(b)} if and only
* if {@code compare(a, b) == 0}.
*
* <p>When the ordering is not consistent with equals the behavior of this
* class is well defined but does not honor the contract specified by {@link
* Map}. Consider a tree map of case-insensitive strings, an ordering that is
* not consistent with equals: <pre> {@code
* TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
* map.put("a", "android");
*
* // The Map API specifies that the next line should print "null" because
* // "a".equals("A") is false and there is no mapping for upper case "A".
* // But the case insensitive ordering says compare("a", "A") == 0. TreeMap
* // uses only comparators/comparable on keys and so this prints "android".
* System.out.println(map.get("A"));
* }</pre>
*
* @since 1.2
*/
public class TreeMap<K, V> extends AbstractMap<K, V>
implements SortedMap<K, V>, NavigableMap<K, V>, Cloneable, Serializable { @SuppressWarnings("unchecked") // to avoid Comparable<Comparable<Comparable<...>>>
private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() {
public int compare(Comparable a, Comparable b) {
return a.compareTo(b);
}
}; Comparator<? super K> comparator;
Node<K, V> root;
int size = 0;
int modCount = 0; /**
* Create a natural order, empty tree map whose keys must be mutually
* comparable and non-null.
*/
@SuppressWarnings("unchecked") // unsafe! this assumes K is comparable
public TreeMap() {
this.comparator = (Comparator<? super K>) NATURAL_ORDER;
} /**
* Create a natural order tree map populated with the key/value pairs of
* {@code copyFrom}. This map's keys must be mutually comparable and
* non-null.
*
* <p>Even if {@code copyFrom} is a {@code SortedMap}, the constructed map
* <strong>will not</strong> use {@code copyFrom}'s ordering. This
* constructor always creates a naturally-ordered map. Because the {@code
* TreeMap} constructor overloads are ambiguous, prefer to construct a map
* and populate it in two steps: <pre> {@code
* TreeMap<String, Integer> customOrderedMap
* = new TreeMap<String, Integer>(copyFrom.comparator());
* customOrderedMap.putAll(copyFrom);
* }</pre>
*/
public TreeMap(Map<? extends K, ? extends V> copyFrom) {
this();
for (Map.Entry<? extends K, ? extends V> entry : copyFrom.entrySet()) {
putInternal(entry.getKey(), entry.getValue());
}
} /**
* Create a tree map ordered by {@code comparator}. This map's keys may only
* be null if {@code comparator} permits.
*
* @param comparator the comparator to order elements with, or {@code null} to use the natural
* ordering.
*/
@SuppressWarnings("unchecked") // unsafe! if comparator is null, this assumes K is comparable
public TreeMap(Comparator<? super K> comparator) {
if (comparator != null) {
this.comparator = comparator;
} else {
this.comparator = (Comparator<? super K>) NATURAL_ORDER;
}
} /**
* Create a tree map with the ordering and key/value pairs of {@code
* copyFrom}. This map's keys may only be null if the {@code copyFrom}'s
* ordering permits.
*
* <p>The constructed map <strong>will always use</strong> {@code
* copyFrom}'s ordering. Because the {@code TreeMap} constructor overloads
* are ambigous, prefer to construct a map and populate it in two steps:
* <pre> {@code
* TreeMap<String, Integer> customOrderedMap
* = new TreeMap<String, Integer>(copyFrom.comparator());
* customOrderedMap.putAll(copyFrom);
* }</pre>
*/
@SuppressWarnings("unchecked") // if copyFrom's keys are comparable this map's keys must be also
public TreeMap(SortedMap<K, ? extends V> copyFrom) {
Comparator<? super K> sourceComparator = copyFrom.comparator();
if (sourceComparator != null) {
this.comparator = sourceComparator;
} else {
this.comparator = (Comparator<? super K>) NATURAL_ORDER;
}
for (Map.Entry<K, ? extends V> entry : copyFrom.entrySet()) {
putInternal(entry.getKey(), entry.getValue());
}
} @Override public Object clone() {
try {
@SuppressWarnings("unchecked") // super.clone() must return the same type
TreeMap<K, V> map = (TreeMap<K, V>) super.clone();
map.root = root != null ? root.copy(null) : null;
map.entrySet = null;
map.keySet = null;
return map;
} catch (CloneNotSupportedException e) {
throw new AssertionError();
}
} @Override public int size() {
return size;
} @Override public boolean isEmpty() {
return size == 0;
} @Override public V get(Object key) {
Entry<K, V> entry = findByObject(key);
return entry != null ? entry.getValue() : null;
} @Override public boolean containsKey(Object key) {
return findByObject(key) != null;
} @Override public V put(K key, V value) {
return putInternal(key, value);
} @Override public void clear() {
root = null;
size = 0;
modCount++;
} @Override public V remove(Object key) {
Node<K, V> node = removeInternalByKey(key);
return node != null ? node.value : null;
} /*
* AVL methods
*/ enum Relation {
LOWER,
FLOOR,
EQUAL,
CREATE,
CEILING,
HIGHER; /**
* Returns a possibly-flipped relation for use in descending views.
*
* @param ascending false to flip; true to return this.
*/
Relation forOrder(boolean ascending) {
if (ascending) {
return this;
} switch (this) {
case LOWER:
return HIGHER;
case FLOOR:
return CEILING;
case EQUAL:
return EQUAL;
case CEILING:
return FLOOR;
case HIGHER:
return LOWER;
default:
throw new IllegalStateException();
}
}
} V putInternal(K key, V value) {
Node<K, V> created = find(key, Relation.CREATE);
V result = created.value;
created.value = value;
return result;
} /**
* Returns the node at or adjacent to the given key, creating it if requested.
*
* @throws ClassCastException if {@code key} and the tree's keys aren't mutually comparable.
*/
Node<K, V> find(K key, Relation relation) {
if (root == null) {
if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) {
throw new ClassCastException(key.getClass().getName() + " is not Comparable"); // NullPointerException ok
}
if (relation == Relation.CREATE) {
root = new Node<K, V>(null, key);
size = 1;
modCount++;
return root;
} else {
return null;
}
} /*
* Micro-optimization: avoid polymorphic calls to Comparator.compare().
* This is 10% faster for naturally ordered trees.
*/
@SuppressWarnings("unchecked") // will throw a ClassCastException below if there's trouble
Comparable<Object> comparableKey = (comparator == NATURAL_ORDER)
? (Comparable<Object>) key
: null; Node<K, V> nearest = root;
while (true) {
int comparison = (comparableKey != null)
? comparableKey.compareTo(nearest.key)
: comparator.compare(key, nearest.key); /*
* We found the requested key.
*/
if (comparison == 0) {
switch (relation) {
case LOWER:
return nearest.prev();
case FLOOR:
case EQUAL:
case CREATE:
case CEILING:
return nearest;
case HIGHER:
return nearest.next();
}
} Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right;
if (child != null) {
nearest = child;
continue;
} /*
* We found a nearest node. Every key not in the tree has up to two
* nearest nodes, one lower and one higher.
*/ if (comparison < 0) { // nearest.key is higher
switch (relation) {
case LOWER:
case FLOOR:
return nearest.prev();
case CEILING:
case HIGHER:
return nearest;
case EQUAL:
return null;
case CREATE:
Node<K, V> created = new Node<K, V>(nearest, key);
nearest.left = created;
size++;
modCount++;
rebalance(nearest, true);
return created;
}
} else { // comparison > 0, nearest.key is lower
switch (relation) {
case LOWER:
case FLOOR:
return nearest;
case CEILING:
case HIGHER:
return nearest.next();
case EQUAL:
return null;
case CREATE:
Node<K, V> created = new Node<K, V>(nearest, key);
nearest.right = created;
size++;
modCount++;
rebalance(nearest, true);
return created;
}
}
}
} @SuppressWarnings("unchecked") // this method throws ClassCastExceptions!
Node<K, V> findByObject(Object key) {
return find((K) key, EQUAL);
} /**
* Returns this map's entry that has the same key and value as {@code
* entry}, or null if this map has no such entry.
*
* <p>This method uses the comparator for key equality rather than {@code
* equals}. If this map's comparator isn't consistent with equals (such as
* {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code
* contains()} will violate the collections API.
*/
Node<K, V> findByEntry(Entry<?, ?> entry) {
Node<K, V> mine = findByObject(entry.getKey());
boolean valuesEqual = mine != null && Objects.equal(mine.value, entry.getValue());
return valuesEqual ? mine : null;
} /**
* Removes {@code node} from this tree, rearranging the tree's structure as
* necessary.
*/
void removeInternal(Node<K, V> node) {
Node<K, V> left = node.left;
Node<K, V> right = node.right;
Node<K, V> originalParent = node.parent;
if (left != null && right != null) { /*
* To remove a node with both left and right subtrees, move an
* adjacent node from one of those subtrees into this node's place.
*
* Removing the adjacent node may change this node's subtrees. This
* node may no longer have two subtrees once the adjacent node is
* gone!
*/ Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first();
removeInternal(adjacent); // takes care of rebalance and size-- int leftHeight = 0;
left = node.left;
if (left != null) {
leftHeight = left.height;
adjacent.left = left;
left.parent = adjacent;
node.left = null;
}
int rightHeight = 0;
right = node.right;
if (right != null) {
rightHeight = right.height;
adjacent.right = right;
right.parent = adjacent;
node.right = null;
}
adjacent.height = Math.max(leftHeight, rightHeight) + 1;
replaceInParent(node, adjacent);
return;
} else if (left != null) {
replaceInParent(node, left);
node.left = null;
} else if (right != null) {
replaceInParent(node, right);
node.right = null;
} else {
replaceInParent(node, null);
} rebalance(originalParent, false);
size--;
modCount++;
} Node<K, V> removeInternalByKey(Object key) {
Node<K, V> node = findByObject(key);
if (node != null) {
removeInternal(node);
}
return node;
} private void replaceInParent(Node<K, V> node, Node<K, V> replacement) {
Node<K, V> parent = node.parent;
node.parent = null;
if (replacement != null) {
replacement.parent = parent;
} if (parent != null) {
if (parent.left == node) {
parent.left = replacement;
} else {
assert (parent.right == node);
parent.right = replacement;
}
} else {
root = replacement;
}
} /**
* Rebalances the tree by making any AVL rotations necessary between the
* newly-unbalanced node and the tree's root.
*
* @param insert true if the node was unbalanced by an insert; false if it
* was by a removal.
*/
private void rebalance(Node<K, V> unbalanced, boolean insert) {
for (Node<K, V> node = unbalanced; node != null; node = node.parent) {
Node<K, V> left = node.left;
Node<K, V> right = node.right;
int leftHeight = left != null ? left.height : 0;
int rightHeight = right != null ? right.height : 0; int delta = leftHeight - rightHeight;
if (delta == -2) {
Node<K, V> rightLeft = right.left;
Node<K, V> rightRight = right.right;
int rightRightHeight = rightRight != null ? rightRight.height : 0;
int rightLeftHeight = rightLeft != null ? rightLeft.height : 0; int rightDelta = rightLeftHeight - rightRightHeight;
if (rightDelta == -1 || (rightDelta == 0 && !insert)) {
rotateLeft(node); // AVL right right
} else {
assert (rightDelta == 1);
rotateRight(right); // AVL right left
rotateLeft(node);
}
if (insert) {
break; // no further rotations will be necessary
} } else if (delta == 2) {
Node<K, V> leftLeft = left.left;
Node<K, V> leftRight = left.right;
int leftRightHeight = leftRight != null ? leftRight.height : 0;
int leftLeftHeight = leftLeft != null ? leftLeft.height : 0; int leftDelta = leftLeftHeight - leftRightHeight;
if (leftDelta == 1 || (leftDelta == 0 && !insert)) {
rotateRight(node); // AVL left left
} else {
assert (leftDelta == -1);
rotateLeft(left); // AVL left right
rotateRight(node);
}
if (insert) {
break; // no further rotations will be necessary
} } else if (delta == 0) {
node.height = leftHeight + 1; // leftHeight == rightHeight
if (insert) {
break; // the insert caused balance, so rebalancing is done!
} } else {
assert (delta == -1 || delta == 1);
node.height = Math.max(leftHeight, rightHeight) + 1;
if (!insert) {
break; // the height hasn't changed, so rebalancing is done!
}
}
}
} /**
* Rotates the subtree so that its root's right child is the new root.
*/
private void rotateLeft(Node<K, V> root) {
Node<K, V> left = root.left;
Node<K, V> pivot = root.right;
Node<K, V> pivotLeft = pivot.left;
Node<K, V> pivotRight = pivot.right; // move the pivot's left child to the root's right
root.right = pivotLeft;
if (pivotLeft != null) {
pivotLeft.parent = root;
} replaceInParent(root, pivot); // move the root to the pivot's left
pivot.left = root;
root.parent = pivot; // fix heights
root.height = Math.max(left != null ? left.height : 0,
pivotLeft != null ? pivotLeft.height : 0) + 1;
pivot.height = Math.max(root.height,
pivotRight != null ? pivotRight.height : 0) + 1;
} /**
* Rotates the subtree so that its root's left child is the new root.
*/
private void rotateRight(Node<K, V> root) {
Node<K, V> pivot = root.left;
Node<K, V> right = root.right;
Node<K, V> pivotLeft = pivot.left;
Node<K, V> pivotRight = pivot.right; // move the pivot's right child to the root's left
root.left = pivotRight;
if (pivotRight != null) {
pivotRight.parent = root;
} replaceInParent(root, pivot); // move the root to the pivot's right
pivot.right = root;
root.parent = pivot; // fixup heights
root.height = Math.max(right != null ? right.height : 0,
pivotRight != null ? pivotRight.height : 0) + 1;
pivot.height = Math.max(root.height,
pivotLeft != null ? pivotLeft.height : 0) + 1;
} /*
* Navigable methods.
*/ /**
* Returns an immutable version of {@param entry}. Need this because we allow entry to be null,
* in which case we return a null SimpleImmutableEntry.
*/
private SimpleImmutableEntry<K, V> immutableCopy(Entry<K, V> entry) {
return entry == null ? null : new SimpleImmutableEntry<K, V>(entry);
} public Entry<K, V> firstEntry() {
return immutableCopy(root == null ? null : root.first());
} private Entry<K, V> internalPollFirstEntry() {
if (root == null) {
return null;
}
Node<K, V> result = root.first();
removeInternal(result);
return result;
} public Entry<K, V> pollFirstEntry() {
return immutableCopy(internalPollFirstEntry());
} public K firstKey() {
if (root == null) {
throw new NoSuchElementException();
}
return root.first().getKey();
} public Entry<K, V> lastEntry() {
return immutableCopy(root == null ? null : root.last());
} private Entry<K, V> internalPollLastEntry() {
if (root == null) {
return null;
}
Node<K, V> result = root.last();
removeInternal(result);
return result;
} public Entry<K, V> pollLastEntry() {
return immutableCopy(internalPollLastEntry());
} public K lastKey() {
if (root == null) {
throw new NoSuchElementException();
}
return root.last().getKey();
} public Entry<K, V> lowerEntry(K key) {
return immutableCopy(find(key, LOWER));
} public K lowerKey(K key) {
Entry<K, V> entry = find(key, LOWER);
return entry != null ? entry.getKey() : null;
} public Entry<K, V> floorEntry(K key) {
return immutableCopy(find(key, FLOOR));
} public K floorKey(K key) {
Entry<K, V> entry = find(key, FLOOR);
return entry != null ? entry.getKey() : null;
} public Entry<K, V> ceilingEntry(K key) {
return immutableCopy(find(key, CEILING));
} public K ceilingKey(K key) {
Entry<K, V> entry = find(key, CEILING);
return entry != null ? entry.getKey() : null;
} public Entry<K, V> higherEntry(K key) {
return immutableCopy(find(key, HIGHER));
} public K higherKey(K key) {
Entry<K, V> entry = find(key, HIGHER);
return entry != null ? entry.getKey() : null;
} public Comparator<? super K> comparator() {
return comparator != NATURAL_ORDER ? comparator : null;
} /*
* View factory methods.
*/ private EntrySet entrySet;
private KeySet keySet; @Override public Set<Entry<K, V>> entrySet() {
EntrySet result = entrySet;
return result != null ? result : (entrySet = new EntrySet());
} @Override public Set<K> keySet() {
KeySet result = keySet;
return result != null ? result : (keySet = new KeySet());
} public NavigableSet<K> navigableKeySet() {
KeySet result = keySet;
return result != null ? result : (keySet = new KeySet());
} public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) {
Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE;
Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE;
return new BoundedMap(true, from, fromBound, to, toBound);
} public SortedMap<K, V> subMap(K fromInclusive, K toExclusive) {
return new BoundedMap(true, fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE);
} public NavigableMap<K, V> headMap(K to, boolean inclusive) {
Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE;
return new BoundedMap(true, null, NO_BOUND, to, toBound);
} public SortedMap<K, V> headMap(K toExclusive) {
return new BoundedMap(true, null, NO_BOUND, toExclusive, EXCLUSIVE);
} public NavigableMap<K, V> tailMap(K from, boolean inclusive) {
Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE;
return new BoundedMap(true, from, fromBound, null, NO_BOUND);
} public SortedMap<K, V> tailMap(K fromInclusive) {
return new BoundedMap(true, fromInclusive, INCLUSIVE, null, NO_BOUND);
} public NavigableMap<K, V> descendingMap() {
return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND);
} public NavigableSet<K> descendingKeySet() {
return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet();
} static class Node<K, V> implements Map.Entry<K, V> {
Node<K, V> parent;
Node<K, V> left;
Node<K, V> right;
final K key;
V value;
int height; Node(Node<K, V> parent, K key) {
this.parent = parent;
this.key = key;
this.height = 1;
} Node<K, V> copy(Node<K, V> parent) {
Node<K, V> result = new Node<K, V>(parent, key);
if (left != null) {
result.left = left.copy(result);
}
if (right != null) {
result.right = right.copy(result);
}
result.value = value;
result.height = height;
return result;
} public K getKey() {
return key;
} public V getValue() {
return value;
} public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
} @Override public boolean equals(Object o) {
if (o instanceof Map.Entry) {
Map.Entry other = (Map.Entry) o;
return (key == null ? other.getKey() == null : key.equals(other.getKey()))
&& (value == null ? other.getValue() == null : value.equals(other.getValue()));
}
return false;
} @Override public int hashCode() {
return (key == null ? 0 : key.hashCode())
^ (value == null ? 0 : value.hashCode());
} @Override public String toString() {
return key + "=" + value;
} /**
* Returns the next node in an inorder traversal, or null if this is the
* last node in the tree.
*/
Node<K, V> next() {
if (right != null) {
return right.first();
} Node<K, V> node = this;
Node<K, V> parent = node.parent;
while (parent != null) {
if (parent.left == node) {
return parent;
}
node = parent;
parent = node.parent;
}
return null;
} /**
* Returns the previous node in an inorder traversal, or null if this is
* the first node in the tree.
*/
public Node<K, V> prev() {
if (left != null) {
return left.last();
} Node<K, V> node = this;
Node<K, V> parent = node.parent;
while (parent != null) {
if (parent.right == node) {
return parent;
}
node = parent;
parent = node.parent;
}
return null;
} /**
* Returns the first node in this subtree.
*/
public Node<K, V> first() {
Node<K, V> node = this;
Node<K, V> child = node.left;
while (child != null) {
node = child;
child = node.left;
}
return node;
} /**
* Returns the last node in this subtree.
*/
public Node<K, V> last() {
Node<K, V> node = this;
Node<K, V> child = node.right;
while (child != null) {
node = child;
child = node.right;
}
return node;
}
} /**
* Walk the nodes of the tree left-to-right or right-to-left. Note that in
* descending iterations, {@code next} will return the previous node.
*/
abstract class MapIterator<T> implements Iterator<T> {
protected Node<K, V> next;
protected Node<K, V> last;
protected int expectedModCount = modCount; MapIterator(Node<K, V> next) {
this.next = next;
} public boolean hasNext() {
return next != null;
} protected Node<K, V> stepForward() {
if (next == null) {
throw new NoSuchElementException();
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
last = next;
next = next.next();
return last;
} protected Node<K, V> stepBackward() {
if (next == null) {
throw new NoSuchElementException();
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
last = next;
next = next.prev();
return last;
} public void remove() {
if (last == null) {
throw new IllegalStateException();
}
removeInternal(last);
expectedModCount = modCount;
last = null;
}
} /*
* View implementations.
*/ class EntrySet extends AbstractSet<Map.Entry<K, V>> {
@Override public int size() {
return size;
} @Override public Iterator<Entry<K, V>> iterator() {
return new MapIterator<Entry<K, V>>(root == null ? null : root.first()) {
public Entry<K, V> next() {
return stepForward();
}
};
} @Override public boolean contains(Object o) {
return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null;
} @Override public boolean remove(Object o) {
if (!(o instanceof Entry)) {
return false;
} Node<K, V> node = findByEntry((Entry<?, ?>) o);
if (node == null) {
return false;
}
removeInternal(node);
return true;
} @Override public void clear() {
TreeMap.this.clear();
}
} class KeySet extends AbstractSet<K> implements NavigableSet<K> {
@Override public int size() {
return size;
} @Override public Iterator<K> iterator() {
return new MapIterator<K>(root == null ? null : root.first()) {
public K next() {
return stepForward().key;
}
};
} public Iterator<K> descendingIterator() {
return new MapIterator<K>(root == null ? null : root.last()) {
public K next() {
return stepBackward().key;
}
};
} @Override public boolean contains(Object o) {
return containsKey(o);
} @Override public boolean remove(Object key) {
return removeInternalByKey(key) != null;
} @Override public void clear() {
TreeMap.this.clear();
} public Comparator<? super K> comparator() {
return TreeMap.this.comparator();
} /*
* Navigable methods.
*/ public K first() {
return firstKey();
} public K last() {
return lastKey();
} public K lower(K key) {
return lowerKey(key);
} public K floor(K key) {
return floorKey(key);
} public K ceiling(K key) {
return ceilingKey(key);
} public K higher(K key) {
return higherKey(key);
} public K pollFirst() {
Entry<K, V> entry = internalPollFirstEntry();
return entry != null ? entry.getKey() : null;
} public K pollLast() {
Entry<K, V> entry = internalPollLastEntry();
return entry != null ? entry.getKey() : null;
} /*
* View factory methods.
*/ public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) {
return TreeMap.this.subMap(from, fromInclusive, to, toInclusive).navigableKeySet();
} public SortedSet<K> subSet(K fromInclusive, K toExclusive) {
return TreeMap.this.subMap(fromInclusive, true, toExclusive, false).navigableKeySet();
} public NavigableSet<K> headSet(K to, boolean inclusive) {
return TreeMap.this.headMap(to, inclusive).navigableKeySet();
} public SortedSet<K> headSet(K toExclusive) {
return TreeMap.this.headMap(toExclusive, false).navigableKeySet();
} public NavigableSet<K> tailSet(K from, boolean inclusive) {
return TreeMap.this.tailMap(from, inclusive).navigableKeySet();
} public SortedSet<K> tailSet(K fromInclusive) {
return TreeMap.this.tailMap(fromInclusive, true).navigableKeySet();
} public NavigableSet<K> descendingSet() {
return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet();
}
} /*
* Bounded views implementations.
*/ enum Bound {
INCLUSIVE {
@Override public String leftCap(Object from) {
return "[" + from;
}
@Override public String rightCap(Object to) {
return to + "]";
}
},
EXCLUSIVE {
@Override public String leftCap(Object from) {
return "(" + from;
}
@Override public String rightCap(Object to) {
return to + ")";
}
},
NO_BOUND {
@Override public String leftCap(Object from) {
return ".";
}
@Override public String rightCap(Object to) {
return ".";
}
}; public abstract String leftCap(Object from);
public abstract String rightCap(Object to);
} /**
* A map with optional limits on its range.
*/
final class BoundedMap extends AbstractMap<K, V> implements NavigableMap<K, V>, Serializable {
private final transient boolean ascending;
private final transient K from;
private final transient Bound fromBound;
private final transient K to;
private final transient Bound toBound; BoundedMap(boolean ascending, K from, Bound fromBound, K to, Bound toBound) {
/*
* Validate the bounds. In addition to checking that from <= to, we
* verify that the comparator supports our bound objects.
*/
if (fromBound != NO_BOUND && toBound != NO_BOUND) {
if (comparator.compare(from, to) > 0) {
throw new IllegalArgumentException(from + " > " + to);
}
} else if (fromBound != NO_BOUND) {
comparator.compare(from, from);
} else if (toBound != NO_BOUND) {
comparator.compare(to, to);
} this.ascending = ascending;
this.from = from;
this.fromBound = fromBound;
this.to = to;
this.toBound = toBound;
} @Override public int size() {
return count(entrySet().iterator());
} @Override public boolean isEmpty() {
return endpoint(true) == null;
} @Override public V get(Object key) {
return isInBounds(key) ? TreeMap.this.get(key) : null;
} @Override public boolean containsKey(Object key) {
return isInBounds(key) && TreeMap.this.containsKey(key);
} @Override public V put(K key, V value) {
if (!isInBounds(key)) {
throw outOfBounds(key, fromBound, toBound);
}
return putInternal(key, value);
} @Override public V remove(Object key) {
return isInBounds(key) ? TreeMap.this.remove(key) : null;
} /**
* Returns true if the key is in bounds.
*/
@SuppressWarnings("unchecked") // this method throws ClassCastExceptions!
private boolean isInBounds(Object key) {
return isInBounds((K) key, fromBound, toBound);
} /**
* Returns true if the key is in bounds. Use this overload with
* NO_BOUND to skip bounds checking on either end.
*/
private boolean isInBounds(K key, Bound fromBound, Bound toBound) {
if (fromBound == INCLUSIVE) {
if (comparator.compare(key, from) < 0) {
return false; // less than from
}
} else if (fromBound == EXCLUSIVE) {
if (comparator.compare(key, from) <= 0) {
return false; // less than or equal to from
}
} if (toBound == INCLUSIVE) {
if (comparator.compare(key, to) > 0) {
return false; // greater than 'to'
}
} else if (toBound == EXCLUSIVE) {
if (comparator.compare(key, to) >= 0) {
return false; // greater than or equal to 'to'
}
} return true;
} /**
* Returns the entry if it is in bounds, or null if it is out of bounds.
*/
private Node<K, V> bound(Node<K, V> node, Bound fromBound, Bound toBound) {
return node != null && isInBounds(node.getKey(), fromBound, toBound) ? node : null;
} /*
* Navigable methods.
*/ public Entry<K, V> firstEntry() {
return immutableCopy(endpoint(true));
} public Entry<K, V> pollFirstEntry() {
Node<K, V> result = endpoint(true);
if (result != null) {
removeInternal(result);
}
return immutableCopy(result);
} public K firstKey() {
Entry<K, V> entry = endpoint(true);
if (entry == null) {
throw new NoSuchElementException();
}
return entry.getKey();
} public Entry<K, V> lastEntry() {
return immutableCopy(endpoint(false));
} public Entry<K, V> pollLastEntry() {
Node<K, V> result = endpoint(false);
if (result != null) {
removeInternal(result);
}
return immutableCopy(result);
} public K lastKey() {
Entry<K, V> entry = endpoint(false);
if (entry == null) {
throw new NoSuchElementException();
}
return entry.getKey();
} /**
* @param first true for the first element, false for the last.
*/
private Node<K, V> endpoint(boolean first) {
Node<K, V> node;
if (ascending == first) {
switch (fromBound) {
case NO_BOUND:
node = root == null ? null : root.first();
break;
case INCLUSIVE:
node = find(from, CEILING);
break;
case EXCLUSIVE:
node = find(from, HIGHER);
break;
default:
throw new AssertionError();
}
return bound(node, NO_BOUND, toBound);
} else {
switch (toBound) {
case NO_BOUND:
node = root == null ? null : root.last();
break;
case INCLUSIVE:
node = find(to, FLOOR);
break;
case EXCLUSIVE:
node = find(to, LOWER);
break;
default:
throw new AssertionError();
}
return bound(node, fromBound, NO_BOUND);
}
} /**
* Performs a find on the underlying tree after constraining it to the
* bounds of this view. Examples:
*
* bound is (A..C)
* findBounded(B, FLOOR) stays source.find(B, FLOOR)
*
* bound is (A..C)
* findBounded(C, FLOOR) becomes source.find(C, LOWER)
*
* bound is (A..C)
* findBounded(D, LOWER) becomes source.find(C, LOWER)
*
* bound is (A..C]
* findBounded(D, FLOOR) becomes source.find(C, FLOOR)
*
* bound is (A..C]
* findBounded(D, LOWER) becomes source.find(C, FLOOR)
*/
private Entry<K, V> findBounded(K key, Relation relation) {
relation = relation.forOrder(ascending);
Bound fromBoundForCheck = fromBound;
Bound toBoundForCheck = toBound; if (toBound != NO_BOUND && (relation == LOWER || relation == FLOOR)) {
int comparison = comparator.compare(to, key);
if (comparison <= 0) {
key = to;
if (toBound == EXCLUSIVE) {
relation = LOWER; // 'to' is too high
} else if (comparison < 0) {
relation = FLOOR; // we already went lower
}
}
toBoundForCheck = NO_BOUND; // we've already checked the upper bound
} if (fromBound != NO_BOUND && (relation == CEILING || relation == HIGHER)) {
int comparison = comparator.compare(from, key);
if (comparison >= 0) {
key = from;
if (fromBound == EXCLUSIVE) {
relation = HIGHER; // 'from' is too low
} else if (comparison > 0) {
relation = CEILING; // we already went higher
}
}
fromBoundForCheck = NO_BOUND; // we've already checked the lower bound
} return bound(find(key, relation), fromBoundForCheck, toBoundForCheck);
} public Entry<K, V> lowerEntry(K key) {
return immutableCopy(findBounded(key, LOWER));
} public K lowerKey(K key) {
Entry<K, V> entry = findBounded(key, LOWER);
return entry != null ? entry.getKey() : null;
} public Entry<K, V> floorEntry(K key) {
return immutableCopy(findBounded(key, FLOOR));
} public K floorKey(K key) {
Entry<K, V> entry = findBounded(key, FLOOR);
return entry != null ? entry.getKey() : null;
} public Entry<K, V> ceilingEntry(K key) {
return immutableCopy(findBounded(key, CEILING));
} public K ceilingKey(K key) {
Entry<K, V> entry = findBounded(key, CEILING);
return entry != null ? entry.getKey() : null;
} public Entry<K, V> higherEntry(K key) {
return immutableCopy(findBounded(key, HIGHER));
} public K higherKey(K key) {
Entry<K, V> entry = findBounded(key, HIGHER);
return entry != null ? entry.getKey() : null;
} public Comparator<? super K> comparator() {
if (ascending) {
return TreeMap.this.comparator();
} else {
return Collections.reverseOrder(comparator);
}
} /*
* View factory methods.
*/ private transient BoundedEntrySet entrySet;
private transient BoundedKeySet keySet; @Override public Set<Entry<K, V>> entrySet() {
BoundedEntrySet result = entrySet;
return result != null ? result : (entrySet = new BoundedEntrySet());
} @Override public Set<K> keySet() {
return navigableKeySet();
} public NavigableSet<K> navigableKeySet() {
BoundedKeySet result = keySet;
return result != null ? result : (keySet = new BoundedKeySet());
} public NavigableMap<K, V> descendingMap() {
return new BoundedMap(!ascending, from, fromBound, to, toBound);
} public NavigableSet<K> descendingKeySet() {
return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet();
} public NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive) {
Bound fromBound = fromInclusive ? INCLUSIVE : EXCLUSIVE;
Bound toBound = toInclusive ? INCLUSIVE : EXCLUSIVE;
return subMap(from, fromBound, to, toBound);
} public NavigableMap<K, V> subMap(K fromInclusive, K toExclusive) {
return subMap(fromInclusive, INCLUSIVE, toExclusive, EXCLUSIVE);
} public NavigableMap<K, V> headMap(K to, boolean inclusive) {
Bound toBound = inclusive ? INCLUSIVE : EXCLUSIVE;
return subMap(null, NO_BOUND, to, toBound);
} public NavigableMap<K, V> headMap(K toExclusive) {
return subMap(null, NO_BOUND, toExclusive, EXCLUSIVE);
} public NavigableMap<K, V> tailMap(K from, boolean inclusive) {
Bound fromBound = inclusive ? INCLUSIVE : EXCLUSIVE;
return subMap(from, fromBound, null, NO_BOUND);
} public NavigableMap<K, V> tailMap(K fromInclusive) {
return subMap(fromInclusive, INCLUSIVE, null, NO_BOUND);
} private NavigableMap<K, V> subMap(K from, Bound fromBound, K to, Bound toBound) {
if (!ascending) {
K fromTmp = from;
Bound fromBoundTmp = fromBound;
from = to;
fromBound = toBound;
to = fromTmp;
toBound = fromBoundTmp;
} /*
* If both the current and requested bounds are exclusive, the isInBounds check must be
* inclusive. For example, to create (C..F) from (A..F), the bound 'F' is in bounds.
*/ if (fromBound == NO_BOUND) {
from = this.from;
fromBound = this.fromBound;
} else {
Bound fromBoundToCheck = fromBound == this.fromBound ? INCLUSIVE : this.fromBound;
if (!isInBounds(from, fromBoundToCheck, this.toBound)) {
throw outOfBounds(to, fromBoundToCheck, this.toBound);
}
} if (toBound == NO_BOUND) {
to = this.to;
toBound = this.toBound;
} else {
Bound toBoundToCheck = toBound == this.toBound ? INCLUSIVE : this.toBound;
if (!isInBounds(to, this.fromBound, toBoundToCheck)) {
throw outOfBounds(to, this.fromBound, toBoundToCheck);
}
} return new BoundedMap(ascending, from, fromBound, to, toBound);
} private IllegalArgumentException outOfBounds(Object value, Bound fromBound, Bound toBound) {
return new IllegalArgumentException(value + " not in range "
+ fromBound.leftCap(from) + ".." + toBound.rightCap(to));
} /*
* Bounded view implementations.
*/ abstract class BoundedIterator<T> extends MapIterator<T> {
protected BoundedIterator(Node<K, V> next) {
super(next);
} @Override protected Node<K, V> stepForward() {
Node<K, V> result = super.stepForward();
if (next != null && !isInBounds(next.key, NO_BOUND, toBound)) {
next = null;
}
return result;
} @Override protected Node<K, V> stepBackward() {
Node<K, V> result = super.stepBackward();
if (next != null && !isInBounds(next.key, fromBound, NO_BOUND)) {
next = null;
}
return result;
}
} final class BoundedEntrySet extends AbstractSet<Entry<K, V>> {
@Override public int size() {
return BoundedMap.this.size();
} @Override public boolean isEmpty() {
return BoundedMap.this.isEmpty();
} @Override public Iterator<Entry<K, V>> iterator() {
return new BoundedIterator<Entry<K, V>>(endpoint(true)) {
public Entry<K, V> next() {
return ascending ? stepForward() : stepBackward();
}
};
} @Override public boolean contains(Object o) {
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> entry = (Entry<?, ?>) o;
return isInBounds(entry.getKey()) && findByEntry(entry) != null;
} @Override public boolean remove(Object o) {
if (!(o instanceof Entry)) {
return false;
}
Entry<?, ?> entry = (Entry<?, ?>) o;
return isInBounds(entry.getKey()) && TreeMap.this.entrySet().remove(entry);
}
} final class BoundedKeySet extends AbstractSet<K> implements NavigableSet<K> {
@Override public int size() {
return BoundedMap.this.size();
} @Override public boolean isEmpty() {
return BoundedMap.this.isEmpty();
} @Override public Iterator<K> iterator() {
return new BoundedIterator<K>(endpoint(true)) {
public K next() {
return (ascending ? stepForward() : stepBackward()).key;
}
};
} public Iterator<K> descendingIterator() {
return new BoundedIterator<K>(endpoint(false)) {
public K next() {
return (ascending ? stepBackward() : stepForward()).key;
}
};
} @Override public boolean contains(Object key) {
return isInBounds(key) && findByObject(key) != null;
} @Override public boolean remove(Object key) {
return isInBounds(key) && removeInternalByKey(key) != null;
} /*
* Navigable methods.
*/ public K first() {
return firstKey();
} public K pollFirst() {
Entry<K, ?> entry = pollFirstEntry();
return entry != null ? entry.getKey() : null;
} public K last() {
return lastKey();
} public K pollLast() {
Entry<K, ?> entry = pollLastEntry();
return entry != null ? entry.getKey() : null;
} public K lower(K key) {
return lowerKey(key);
} public K floor(K key) {
return floorKey(key);
} public K ceiling(K key) {
return ceilingKey(key);
} public K higher(K key) {
return higherKey(key);
} public Comparator<? super K> comparator() {
return BoundedMap.this.comparator();
} /*
* View factory methods.
*/ public NavigableSet<K> subSet(K from, boolean fromInclusive, K to, boolean toInclusive) {
return subMap(from, fromInclusive, to, toInclusive).navigableKeySet();
} public SortedSet<K> subSet(K fromInclusive, K toExclusive) {
return subMap(fromInclusive, toExclusive).navigableKeySet();
} public NavigableSet<K> headSet(K to, boolean inclusive) {
return headMap(to, inclusive).navigableKeySet();
} public SortedSet<K> headSet(K toExclusive) {
return headMap(toExclusive).navigableKeySet();
} public NavigableSet<K> tailSet(K from, boolean inclusive) {
return tailMap(from, inclusive).navigableKeySet();
} public SortedSet<K> tailSet(K fromInclusive) {
return tailMap(fromInclusive).navigableKeySet();
} public NavigableSet<K> descendingSet() {
return new BoundedMap(!ascending, from, fromBound, to, toBound).navigableKeySet();
}
} Object writeReplace() throws ObjectStreamException {
return ascending
? new AscendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound)
: new DescendingSubMap<K, V>(TreeMap.this, from, fromBound, to, toBound);
}
} /**
* Returns the number of elements in the iteration.
*/
static int count(Iterator<?> iterator) {
int count = 0;
while (iterator.hasNext()) {
iterator.next();
count++;
}
return count;
} /*
* Serialization
*/ private static final long serialVersionUID = 919286545866124006L; private void writeObject(ObjectOutputStream stream) throws IOException {
stream.putFields().put("comparator", comparator != NATURAL_ORDER ? comparator : null);
stream.writeFields();
stream.writeInt(size);
for (Map.Entry<K, V> entry : entrySet()) {
stream.writeObject(entry.getKey());
stream.writeObject(entry.getValue());
}
} @SuppressWarnings("unchecked") // we have to trust that keys are Ks and values are Vs
private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
GetField fields = stream.readFields();
comparator = (Comparator<? super K>) fields.get("comparator", null);
if (comparator == null) {
comparator = (Comparator<? super K>) NATURAL_ORDER;
}
int size = stream.readInt();
for (int i = 0; i < size; i++) {
putInternal((K) stream.readObject(), (V) stream.readObject());
}
} static abstract class NavigableSubMap<K, V> extends AbstractMap<K, V> implements Serializable {
private static final long serialVersionUID = -2102997345730753016L;
TreeMap<K, V> m;
Object lo;
Object hi;
boolean fromStart;
boolean toEnd;
boolean loInclusive;
boolean hiInclusive; NavigableSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) {
this.m = delegate;
this.lo = from;
this.hi = to;
this.fromStart = fromBound == NO_BOUND;
this.toEnd = toBound == NO_BOUND;
this.loInclusive = fromBound == INCLUSIVE;
this.hiInclusive = toBound == INCLUSIVE;
} @Override public Set<Entry<K, V>> entrySet() {
throw new UnsupportedOperationException();
} @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks
protected Object readResolve() throws ObjectStreamException {
Bound fromBound = fromStart ? NO_BOUND : (loInclusive ? INCLUSIVE : EXCLUSIVE);
Bound toBound = toEnd ? NO_BOUND : (hiInclusive ? INCLUSIVE : EXCLUSIVE);
boolean ascending = !(this instanceof DescendingSubMap);
return m.new BoundedMap(ascending, (K) lo, fromBound, (K) hi, toBound);
}
} static class DescendingSubMap<K, V> extends NavigableSubMap<K, V> {
private static final long serialVersionUID = 912986545866120460L;
Comparator<K> reverseComparator;
DescendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) {
super(delegate, from, fromBound, to, toBound);
}
} static class AscendingSubMap<K, V> extends NavigableSubMap<K, V> {
private static final long serialVersionUID = 912986545866124060L;
AscendingSubMap(TreeMap<K, V> delegate, K from, Bound fromBound, K to, Bound toBound) {
super(delegate, from, fromBound, to, toBound);
}
} class SubMap extends AbstractMap<K, V> implements Serializable {
private static final long serialVersionUID = -6520786458950516097L;
Object fromKey;
Object toKey;
boolean fromStart;
boolean toEnd; @Override public Set<Entry<K, V>> entrySet() {
throw new UnsupportedOperationException();
} @SuppressWarnings("unchecked") // we have to trust that the bounds are Ks
protected Object readResolve() throws ObjectStreamException {
Bound fromBound = fromStart ? NO_BOUND : INCLUSIVE;
Bound toBound = toEnd ? NO_BOUND : EXCLUSIVE;
return new BoundedMap(true, (K) fromKey, fromBound, (K) toKey, toBound);
}
}
}
|
|
Implementations |
|||||
|
Hash Table |
Resizable Array |
Balanced Tree |
Linked List |
Hash Table + Linked List |
||
|
Interfaces |
Set |
|
|
|||
|
List |
|
|
|
|||
|
Deque |
|
|
|
|||
|
Map |
|
|
||||
|
是否有序 |
是否允许重复 |
是否线程同步 |
||
|
Collection |
否 |
是 |
||
|
List |
ArrayList |
是 |
是 |
否 |
|
Vector |
是 |
|||
|
LinkedList |
否 |
|||
|
Set |
HashSet |
否 |
否 |
否 |
|
TreeSet |
是 |
否 |
||
|
Map |
HashMap |
否 |
<key, value>， key不允许重复 |
否 |
|
TreeMap |
是 |
否 |
||
|
Hashtable |
否 |
是 |
||
How to use:http://www.cnblogs.com/kiant71/archive/2008/09/04/1752079.html
最新文章
- 自定义搭建PHP开发环境
- c++ 宏定义声明类,并在类中实现回调
- 用java实现文件下载，提示java.lang.IllegalStateException: getOutputStream() has already been called for this response
- Python统计学技术环境
- css布局左右技巧分享
- 第四周psp
- URAL - 1920 Titan Ruins: the Infinite Power of Magic(乱搞)
- eclipse导入Android项目后，项目的名称变为了主Activity的名称
- python基本数据结构-集合-方法
- nfs文件系统挂载失败解决方法
- 初识 .NET平台下作业调度器——Quartz.NET
- [USACO09MAR]地震损失2Earthquake Damage 2
- caffe+opencv3.3dnn模块 完成手写数字图片识别
- docker环境 mysql读写分离 mycat maxscale
- docker swarm的常用操作
- jar 包启动脚本
- java 连接SQL Server
- easy-ui treegrid 实现分页 并且添加自定义checkbox
- 关于JSON CSRF的一些思考
- 20155206 Exp8 WEB基础实践