Java/Collections Data Structure/Set
Версия от 18:01, 31 мая 2010; (обсуждение)
Содержание
- 1 An IdentitySet that uses reference-equality instead of object-equality
- 2 An implementation of the java.util.Stack based on an ArrayList instead of a Vector, so it is not synchronized to protect against multi-threaded access.
- 3 Another Set demo
- 4 Array Set extends AbstractSet
- 5 A thin wrapper around a List transforming it into a modifiable Set.
- 6 A thread-safe Set that manages canonical objects
- 7 Converts a char array to a Set
- 8 Converts a string to a Set
- 9 Copy all the elements from set2 to set1 (set1 += set2), set1 becomes the union of set1 and set2
- 10 Demonstrate the Set interface
- 11 Extend AbstractSet to Create Simple Set
- 12 Get the intersection of set1 and set2, set1 becomes the intersection of set1 and set2
- 13 Implements the Set interface, backed by a ConcurrentHashMap instance
- 14 Int Set
- 15 List Set implements Set
- 16 One Item Set
- 17 Putting your own type in a Set
- 18 Remove all elements from a set
- 19 Remove all the elements in set1 from set2 (set1 -= set2), set1 becomes the asymmetric difference of set1 and set2
- 20 Set and TreeSet
- 21 Set Copy
- 22 Set, HashSet and TreeSet
- 23 Set implementation that use == instead of equals()
- 24 Set operations: union, intersection, difference, symmetric difference, is subset, is superset
- 25 Set subtraction
- 26 Set that compares object by identity rather than equality
- 27 Set union and intersection
- 28 Set with values iterated in insertion order.
- 29 Show the union and intersection of two sets
- 30 Small sets whose elements are known to be unique by construction
- 31 Sync Test
- 32 Tail
- 33 Things you can do with Sets
- 34 TreeSet Demo
- 35 Use set
- 36 What you can do with a TreeSet
- 37 Working with HashSet and TreeSet
An IdentitySet that uses reference-equality instead of object-equality
/*
* Copyright 2005 Ralf Joachim
*
* Licensed 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.
*/
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* An IdentitySet that uses reference-equality instead of object-equality. According
* to its special function it violates some design contracts of the <code>Set</code>
* interface.
*
* @author
* @version $Revision: 7491 $ $Date: 2006-04-13 10:49:49 -0600 (Thu, 13 Apr 2006) $
* @since 0.9.9
*/
public final class IdentitySet implements Set {
//--------------------------------------------------------------------------
/** Default number of buckets. */
private static final int DEFAULT_CAPACITY = 17;
/** Default load factor. */
private static final float DEFAULT_LOAD = 0.75f;
/** Default number of entries. */
private static final int DEFAULT_ENTRIES = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD);
/** Default factor to increment capacity. */
private static final int DEFAULT_INCREMENT = 2;
/** First prime number to check is 3 as we prevent 2 by design. */
private static final int FIRST_PRIME_TO_CHECK = 3;
//--------------------------------------------------------------------------
/** Number of buckets. */
private int _capacity;
/** Maximum number of entries before rehashing. */
private int _maximum;
/** Buckets. */
private Entry[] _buckets;
/** Number of map entries. */
private int _entries = 0;
//--------------------------------------------------------------------------
/**
* Construct a set with default capacity.
*/
public IdentitySet() {
_capacity = DEFAULT_CAPACITY;
_maximum = DEFAULT_ENTRIES;
_buckets = new Entry[DEFAULT_CAPACITY];
}
/**
* Construct a set with given capacity.
*
* @param capacity The capacity of entries this set should be initialized with.
*/
public IdentitySet(final int capacity) {
_capacity = capacity;
_maximum = (int) (capacity * DEFAULT_LOAD);
_buckets = new Entry[capacity];
}
/**
* {@inheritDoc}
* @see java.util.Collection#clear()
*/
public void clear() {
_capacity = DEFAULT_CAPACITY;
_maximum = DEFAULT_ENTRIES;
_buckets = new Entry[DEFAULT_CAPACITY];
_entries = 0;
}
/**
* {@inheritDoc}
* @see java.util.Collection#size()
*/
public int size() { return _entries; }
/**
* {@inheritDoc}
* @see java.util.Collection#isEmpty()
*/
public boolean isEmpty() { return (_entries == 0); }
/**
* {@inheritDoc}
* @see java.util.Collection#add(java.lang.Object)
*/
public boolean add(final Object key) {
int hash = System.identityHashCode(key);
int index = hash % _capacity;
if (index < 0) { index = -index; }
Entry entry = _buckets[index];
Entry prev = null;
while (entry != null) {
if (entry.getKey() == key) {
// There is already a mapping for this key.
return false;
}
prev = entry;
entry = entry.getNext();
}
if (prev == null) {
// There is no previous entry in this bucket.
_buckets[index] = new Entry(key, hash);
} else {
// Next entry is empty so we have no mapping for this key.
prev.setNext(new Entry(key, hash));
}
_entries++;
if (_entries > _maximum) { rehash(); }
return true;
}
/**
* Rehash the map into a new array with increased capacity.
*/
private void rehash() {
long nextCapacity = _capacity * DEFAULT_INCREMENT;
if (nextCapacity > Integer.MAX_VALUE) { return; }
nextCapacity = nextPrime(nextCapacity);
if (nextCapacity > Integer.MAX_VALUE) { return; }
int newCapacity = (int) nextCapacity;
Entry[] newBuckets = new Entry[newCapacity];
Entry entry = null;
Entry temp = null;
Entry next = null;
int newIndex = 0;
for (int index = 0; index < _capacity; index++) {
entry = _buckets[index];
while (entry != null) {
next = entry.getNext();
newIndex = entry.getHash() % newCapacity;
if (newIndex < 0) { newIndex = -newIndex; }
temp = newBuckets[newIndex];
if (temp == null) {
// First entry of the bucket.
entry.setNext(null);
} else {
// Hook entry into beginning of the buckets chain.
entry.setNext(temp);
}
newBuckets[newIndex] = entry;
entry = next;
}
}
_capacity = newCapacity;
_maximum = (int) (newCapacity * DEFAULT_LOAD);
_buckets = newBuckets;
}
/**
* Find next prime number greater than minimum.
*
* @param minimum The minimum (exclusive) value of the next prime number.
* @return The next prime number greater than minimum.
*/
private long nextPrime(final long minimum) {
long candidate = ((minimum + 1) / 2) * 2 + 1;
while (!isPrime(candidate)) { candidate += 2; }
return candidate;
}
/**
* Check for prime number.
*
* @param candidate Number to be checked for being a prime number.
* @return <code>true</code> if the given number is a prime number
* <code>false</code> otherwise.
*/
private boolean isPrime(final long candidate) {
if ((candidate / 2) * 2 == candidate) { return false; }
long stop = candidate / 2;
for (long i = FIRST_PRIME_TO_CHECK; i < stop; i += 2) {
if ((candidate / i) * i == candidate) { return false; }
}
return true;
}
/**
* {@inheritDoc}
* @see java.util.Collection#contains(java.lang.Object)
*/
public boolean contains(final Object key) {
int hash = System.identityHashCode(key);
int index = hash % _capacity;
if (index < 0) { index = -index; }
Entry entry = _buckets[index];
while (entry != null) {
if (entry.getKey() == key) { return true; }
entry = entry.getNext();
}
return false;
}
/**
* {@inheritDoc}
* @see java.util.Collection#remove(java.lang.Object)
*/
public boolean remove(final Object key) {
int hash = System.identityHashCode(key);
int index = hash % _capacity;
if (index < 0) { index = -index; }
Entry entry = _buckets[index];
Entry prev = null;
while (entry != null) {
if (entry.getKey() == key) {
// Found the entry.
if (prev == null) {
// First element in bucket matches.
_buckets[index] = entry.getNext();
} else {
// Remove the entry from the chain.
prev.setNext(entry.getNext());
}
_entries--;
return true;
}
prev = entry;
entry = entry.getNext();
}
return false;
}
/**
* {@inheritDoc}
* @see java.util.Collection#iterator()
*/
public Iterator iterator() {
return new IdentityIterator();
}
/**
* {@inheritDoc}
* @see java.util.Collection#toArray()
*/
public Object[] toArray() {
Object[] result = new Object[_entries];
int j = 0;
for (int i = 0; i < _capacity; i++) {
Entry entry = _buckets[i];
while (entry != null) {
result[j++] = entry.getKey();
entry = entry.getNext();
}
}
return result;
}
/**
* {@inheritDoc}
* @see java.util.Collection#toArray(java.lang.Object[])
*/
public Object[] toArray(final Object[] a) {
Object[] result = a;
if (result.length < _entries) {
result = (Object[]) java.lang.reflect.Array.newInstance(
result.getClass().getComponentType(), _entries);
}
int j = 0;
for (int i = 0; i < _capacity; i++) {
Entry entry = _buckets[i];
while (entry != null) {
result[j++] = entry.getKey();
entry = entry.getNext();
}
}
while (j < result.length) {
result[j++] = null;
}
return result;
}
/**
* In contrast with the design contract of the <code>Set</code> interface this method
* has not been implemented and throws a <code>UnsupportedOperationException</code>.
*
* {@inheritDoc}
* @see java.util.Set#containsAll
*/
public boolean containsAll(final Collection c) {
throw new UnsupportedOperationException();
}
/**
* This optional method has not been implemented for <code>IdentitySet</code> instead
* it throws a <code>UnsupportedOperationException</code> as defined in the
* <code>Set</code> interface.
*
* {@inheritDoc}
* @see java.util.Set#addAll
*/
public boolean addAll(final Collection c) {
throw new UnsupportedOperationException();
}
/**
* This optional method has not been implemented for <code>IdentitySet</code> instead
* it throws a <code>UnsupportedOperationException</code> as defined in the
* <code>Set</code> interface.
*
* {@inheritDoc}
* @see java.util.Set#removeAll
*/
public boolean removeAll(final Collection c) {
throw new UnsupportedOperationException();
}
/**
* This optional method has not been implemented for <code>IdentitySet</code> instead
* it throws a <code>UnsupportedOperationException</code> as defined in the
* <code>Set</code> interface.
*
* {@inheritDoc}
* @see java.util.Set#retainAll
*/
public boolean retainAll(final Collection c) {
throw new UnsupportedOperationException();
}
//--------------------------------------------------------------------------
/**
* An entry of the <code>IdentitySet</code>.
*/
public final class Entry {
/** Key of entry. */
private Object _key;
/** Identity hashcode of key. */
private int _hash;
/** Reference to next entry. */
private Entry _next = null;
/**
* Construct an entry.
*
* @param key Key of entry.
* @param hash Identity hashcode of key.
*/
public Entry(final Object key, final int hash) {
_key = key;
_hash = hash;
}
/**
* Get key of entry.
*
* @return Key of entry.
*/
public Object getKey() { return _key; }
/**
* Get identity hashcode of key.
*
* @return Identity hashcode of key.
*/
public int getHash() { return _hash; }
/**
* Set reference to next entry.
*
* @param next New reference to next entry.
*/
public void setNext(final Entry next) { _next = next; }
/**
* Get reference to next entry.
*
* @return Reference to next entry.
*/
public Entry getNext() { return _next; }
}
//--------------------------------------------------------------------------
/**
* An iterator over all entries of the <code>IdentitySet</code>.
*/
private class IdentityIterator implements Iterator {
/** Index of the current bucket. */
private int _index = 0;
/** The next entry to be returned. <code>null</code> when there is none. */
private Entry _next = _buckets[0];
/**
* Construct a iterator over all entries of the <code>IdentitySet</code>.
*/
public IdentityIterator() {
if (_entries > 0) {
while ((_next == null) && (++_index < _capacity)) {
_next = _buckets[_index];
}
}
}
/**
* {@inheritDoc}
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return (_next != null);
}
/**
* {@inheritDoc}
* @see java.util.Iterator#next()
*/
public Object next() {
Entry entry = _next;
if (entry == null) { throw new NoSuchElementException(); }
_next = entry.getNext();
while ((_next == null) && (++_index < _capacity)) {
_next = _buckets[_index];
}
return entry.getKey();
}
/**
* This optional method is not implemented for <code>IdentityIterator</code>
* instead it throws a <code>UnsupportedOperationException</code> as defined
* in the <code>Iterator</code> interface.
*
* @see java.util.Iterator#remove()
*/
public void remove() {
throw new UnsupportedOperationException();
}
}
//--------------------------------------------------------------------------
}
An implementation of the java.util.Stack based on an ArrayList instead of a Vector, so it is not synchronized to protect against multi-threaded access.
/*
* 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.
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.EmptyStackException;
import java.util.NoSuchElementException;
/**
* An implementation of the {@link java.util.Stack} API that is based on an
* <code>ArrayList</code> instead of a <code>Vector</code>, so it is not
* synchronized to protect against multi-threaded access. The implementation
* is therefore operates faster in environments where you do not need to
* worry about multiple thread contention.
* <p>
* The removal order of an <code>ArrayStack</code> is based on insertion
* order: The most recently added element is removed first. The iteration
* order is <i>not</i> the same as the removal order. The iterator returns
* elements from the bottom up, whereas the {@link #remove()} method removes
* them from the top down.
* <p>
* Unlike <code>Stack</code>, <code>ArrayStack</code> accepts null entries.
* <p>
* <strong>Note:</strong> this class should be bytecode-identical to the
* version in commons collections. This is required to allow backwards
* compability with both previous versions of BeanUtils and also allow
* coexistance with both collections 2.1 and 3.0.
*
* @see java.util.Stack
* @since Commons Collections 1.0
* @version $Revision: 555824 $ $Date: 2007-07-13 01:27:15 +0100 (Fri, 13 Jul 2007) $
*
* @author Craig R. McClanahan
* @author Paul Jack
* @author Stephen Colebourne
*/
public class ArrayStack extends ArrayList implements Buffer {
/** Ensure serialization compatibility */
private static final long serialVersionUID = 2130079159931574599L;
/**
* Constructs a new empty <code>ArrayStack</code>. The initial size
* is controlled by <code>ArrayList</code> and is currently 10.
*/
public ArrayStack() {
super();
}
/**
* Constructs a new empty <code>ArrayStack</code> with an initial size.
*
* @param initialSize the initial size to use
* @throws IllegalArgumentException if the specified initial size
* is negative
*/
public ArrayStack(int initialSize) {
super(initialSize);
}
/**
* Return <code>true</code> if this stack is currently empty.
* <p>
* This method exists for compatibility with <code>java.util.Stack</code>.
* New users of this class should use <code>isEmpty</code> instead.
*
* @return true if the stack is currently empty
*/
public boolean empty() {
return isEmpty();
}
/**
* Returns the top item off of this stack without removing it.
*
* @return the top item on the stack
* @throws EmptyStackException if the stack is empty
*/
public Object peek() throws EmptyStackException {
int n = size();
if (n <= 0) {
throw new EmptyStackException();
} else {
return get(n - 1);
}
}
/**
* Returns the n"th item down (zero-relative) from the top of this
* stack without removing it.
*
* @param n the number of items down to go
* @return the n"th item on the stack, zero relative
* @throws EmptyStackException if there are not enough items on the
* stack to satisfy this request
*/
public Object peek(int n) throws EmptyStackException {
int m = (size() - n) - 1;
if (m < 0) {
throw new EmptyStackException();
} else {
return get(m);
}
}
/**
* Pops the top item off of this stack and return it.
*
* @return the top item on the stack
* @throws EmptyStackException if the stack is empty
*/
public Object pop() throws EmptyStackException {
int n = size();
if (n <= 0) {
throw new EmptyStackException();
} else {
return remove(n - 1);
}
}
/**
* Pushes a new item onto the top of this stack. The pushed item is also
* returned. This is equivalent to calling <code>add</code>.
*
* @param item the item to be added
* @return the item just pushed
*/
public Object push(Object item) {
add(item);
return item;
}
/**
* Returns the one-based position of the distance from the top that the
* specified object exists on this stack, where the top-most element is
* considered to be at distance <code>1</code>. If the object is not
* present on the stack, return <code>-1</code> instead. The
* <code>equals()</code> method is used to compare to the items
* in this stack.
*
* @param object the object to be searched for
* @return the 1-based depth into the stack of the object, or -1 if not found
*/
public int search(Object object) {
int i = size() - 1; // Current index
int n = 1; // Current distance
while (i >= 0) {
Object current = get(i);
if ((object == null && current == null) ||
(object != null && object.equals(current))) {
return n;
}
i--;
n++;
}
return -1;
}
/**
* Returns the element on the top of the stack.
*
* @return the element on the top of the stack
* @throws BufferUnderflowException if the stack is empty
*/
public Object get() {
int size = size();
if (size == 0) {
throw new BufferUnderflowException();
}
return get(size - 1);
}
/**
* Removes the element on the top of the stack.
*
* @return the removed element
* @throws BufferUnderflowException if the stack is empty
*/
public Object remove() {
int size = size();
if (size == 0) {
throw new BufferUnderflowException();
}
return remove(size - 1);
}
}
/*
* 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.
*/
/**
* Defines a collection that allows objects to be removed in some well-defined order.
* <p>
* The removal order can be based on insertion order (eg, a FIFO queue or a
* LIFO stack), on access order (eg, an LRU cache), on some arbitrary comparator
* (eg, a priority queue) or on any other well-defined ordering.
* <p>
* Note that the removal order is not necessarily the same as the iteration
* order. A <code>Buffer</code> implementation may have equivalent removal
* and iteration orders, but this is not required.
* <p>
* This interface does not specify any behavior for
* {@link Object#equals(Object)} and {@link Object#hashCode} methods. It
* is therefore possible for a <code>Buffer</code> implementation to also
* also implement {@link java.util.List}, {@link java.util.Set} or
* {@link Bag}.
* <p>
* <strong>Note:</strong> this class should be bytecode-identical to the
* version in commons collections. This is required to allow backwards
* compability with both previous versions of BeanUtils and also allow
* coexistance with both collections 2.1 and 3.0.
*
* @since Commons Collections 2.1
* @version $Revision: 555824 $ $Date: 2007-07-13 01:27:15 +0100 (Fri, 13 Jul 2007) $
*
* @author Avalon
* @author Berin Loritsch
* @author Paul Jack
* @author Stephen Colebourne
*/
interface Buffer extends Collection {
/**
* Gets and removes the next object from the buffer.
*
* @return the next object in the buffer, which is also removed
* @throws BufferUnderflowException if the buffer is already empty
*/
Object remove();
/**
* Gets the next object from the buffer without removing it.
*
* @return the next object in the buffer, which is not removed
* @throws BufferUnderflowException if the buffer is empty
*/
Object get();
}
/*
* 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.
*/
/**
* The BufferUnderflowException is used when the buffer is already empty.
* <p>
* NOTE: From version 3.0, this exception extends NoSuchElementException.
*
* @since Commons Collections 2.1
* @version $Revision: 555824 $ $Date: 2007-07-13 01:27:15 +0100 (Fri, 13 Jul 2007) $
*
* @author Avalon
* @author Berin Loritsch
* @author Jeff Turner
* @author Paul Jack
* @author Stephen Colebourne
*/
class BufferUnderflowException extends NoSuchElementException {
/** The root cause throwable */
private final Throwable throwable;
/**
* Constructs a new <code>BufferUnderflowException</code>.
*/
public BufferUnderflowException() {
super();
throwable = null;
}
/**
* Construct a new <code>BufferUnderflowException</code>.
*
* @param message the detail message for this exception
*/
public BufferUnderflowException(String message) {
this(message, null);
}
/**
* Construct a new <code>BufferUnderflowException</code>.
*
* @param message the detail message for this exception
* @param exception the root cause of the exception
*/
public BufferUnderflowException(String message, Throwable exception) {
super(message);
throwable = exception;
}
/**
* Gets the root cause of the exception.
*
* @return the root cause
*/
public final Throwable getCause() {
return throwable;
}
}
Another Set demo
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class SetMembership {
final static String[] keywordarray = { "abstract", "assert", "boolean",
"break", "byte", "while" };
final static Set keywords = new HashSet(Arrays.asList(keywordarray));
static boolean isKeyword1(String id) {
return keywords.contains(id);
}
static boolean isKeyword2(String id) {
return Arrays.binarySearch(keywordarray, id) >= 0;
}
}
Array Set extends AbstractSet
import java.io.Serializable;
import java.util.*;
public class ArraySet extends AbstractSet
implements Cloneable, Serializable {
private ArrayList list;
public ArraySet() {
list = new ArrayList();
}
public ArraySet(Collection col) {
list = new ArrayList();
// No need to check for dups if col is a set
Iterator itor = col.iterator();
if (col instanceof Set) {
while (itor.hasNext()) {
list.add(itor.next());
}
} else {
while(itor.hasNext()) {
add(itor.next());
}
}
}
public Iterator iterator() {
return list.iterator();
}
public int size() {
return list.size();
}
public boolean add(Object element) {
boolean modified;
if (modified = !list.contains(element)) {
list.add(element);
}
return modified;
}
public boolean remove(Object element) {
return list.remove(element);
}
public boolean isEmpty() {
return list.isEmpty();
}
public boolean contains(Object element) {
return list.contains(element);
}
public void clear() {
list.clear();
}
public Object clone() {
try {
ArraySet newSet = (ArraySet)super.clone();
newSet.list = (ArrayList)list.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
}
A thin wrapper around a List transforming it into a modifiable Set.
import java.io.Serializable;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/**
* A thin wrapper around a <code>List</code> transforming it into a modifiable
* <code>Set</code>.
*
* @version <tt>$Revision: 2800 $</tt>
* @author
*/
@SuppressWarnings("unchecked")
public class ListSet extends AbstractSet implements Set, Cloneable, Serializable {
/** The serialVersionUID */
private static final long serialVersionUID = 7333619218072079496L;
/** The <tt>List</tt> which will be used for element storage. */
protected final List list;
/**
* Construct a <tt>ListSet</tt>.
*
* @param list
* The <tt>List</tt> which will be used for element storage.
*
* @throws IllegalArgumentException
* List is <tt>null</tt> or contains duplicate entries.
*/
public ListSet(final List list) {
if (list == null)
throw new RuntimeException("list");
// make sure there are no duplicates
int size = list.size();
for (int i = 0; i < size; i++) {
Object obj = list.get(i);
if (list.indexOf(obj) != list.lastIndexOf(obj)) {
throw new IllegalArgumentException("list contains duplicate entries");
}
}
this.list = list;
}
/**
* Construct a <tt>ListSet</tt> using an <tt>ArrayList</tt> for backing.
*/
public ListSet() {
this(new ArrayList());
}
/**
* Construct a <tt>ListSet</tt> using an <tt>ArrayList</tt> for backing
* and populated with the given elements.
*
* @param elements
* The elements for the list.
*/
public ListSet(final Collection elements) {
this(new ArrayList(elements));
}
public List getList() {
return list;
}
/**
* Return the size of the set.
*
* @return The size of the set.
*/
public int size() {
return list.size();
}
/**
* Return an iteration over the elements in the set.
*
* @return An iteration over the elements in the set.
*/
public Iterator iterator() {
return list.iterator();
}
/**
* Add an element to the set.
*
* @param obj
* Element to add to the set.
* @return True if the element was added.
*/
public boolean add(final Object obj) {
boolean added = false;
if (!list.contains(obj)) {
added = list.add(obj);
}
return added;
}
/**
* Returns <tt>true</tt> if this set contains no elements.
*
* @return <tt>true</tt> if this set contains no elements.
*/
public boolean isEmpty() {
return list.isEmpty();
}
/**
* Returns <tt>true</tt> if this set contains the specified element.
*
* @param obj
* Element whose presence in this set is to be tested.
* @return <tt>true</tt> if this set contains the specified element.
*/
public boolean contains(final Object obj) {
return list.contains(obj);
}
/**
* Removes the given element from this set if it is present.
*
* @param obj
* Object to be removed from this set, if present.
* @return <tt>true</tt> if the set contained the specified element.
*/
public boolean remove(final Object obj) {
return list.remove(obj);
}
/**
* Removes all of the elements from this set.
*/
public void clear() {
list.clear();
}
/**
* Returns a shallow copy of this <tt>ListSet</tt> instance.
*
* @return A shallow copy of this set.
*/
public Object clone() {
try {
return super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
}
A thread-safe Set that manages canonical objects
/*
* Copyright 2004 Brian S O"Neill
*
* Licensed 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.
*/
//revised from cojen
import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* A thread-safe Set that manages canonical objects: sharable objects that are
* typically immutable. Call the {@link #put put} method for supplying the
* WeakCanonicalSet with candidate canonical instances.
* <p>
* Objects that do not customize the hashCode and equals methods don"t make
* sense to be canonicalized because each instance will be considered unique.
* The object returned from the {@link #put put} method will always be the same
* as the one passed in.
*
* @author Brian S O"Neill
*/
public class WeakCanonicalSet<T> extends AbstractSet<T> {
private Entry<T>[] table;
private int count;
private int threshold;
private final float loadFactor;
private final ReferenceQueue<T> queue;
public WeakCanonicalSet() {
final int initialCapacity = 101;
final float loadFactor = 0.75f;
this.loadFactor = loadFactor;
this.table = new Entry[initialCapacity];
this.threshold = (int)(initialCapacity * loadFactor);
this.queue = new ReferenceQueue<T>();
}
/**
* Pass in a candidate canonical object and get a unique instance from this
* set. The returned object will always be of the same type as that passed
* in. If the object passed in does not equal any object currently in the
* set, it will be added to the set, becoming canonical.
*
* @param obj candidate canonical object; null is also accepted
*/
public synchronized <U extends T> U put(U obj) {
// This implementation is based on the WeakIdentityMap.put method.
if (obj == null) {
return null;
}
Entry<T>[] tab = this.table;
// Cleanup after cleared References.
{
ReferenceQueue queue = this.queue;
Reference ref;
while ((ref = queue.poll()) != null) {
// Since buckets are single-linked, traverse entire list and
// cleanup all cleared references in it.
int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
for (Entry<T> e = tab[index], prev = null; e != null; e = e.next) {
if (e.get() == null) {
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else {
prev = e;
}
}
}
}
int hash = hashCode(obj);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<T> e = tab[index], prev = null; e != null; e = e.next) {
T iobj = e.get();
if (iobj == null) {
// Clean up after a cleared Reference.
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash &&
obj.getClass() == iobj.getClass() &&
equals(obj, iobj)) {
// Found canonical instance.
return (U) iobj;
} else {
prev = e;
}
}
if (this.count >= this.threshold) {
// Rehash the table if the threshold is exceeded.
rehash();
tab = this.table;
index = (hash & 0x7fffffff) % tab.length;
}
// Create a new entry.
tab[index] = new Entry<T>(obj, this.queue, hash, tab[index]);
this.count++;
return obj;
}
public Iterator<T> iterator() {
return new SetIterator();
}
public int size() {
return this.count;
}
public synchronized boolean contains(Object obj) {
if (obj == null) {
return false;
}
Entry<T>[] tab = this.table;
int hash = hashCode(obj);
int index = (hash & 0x7fffffff) % tab.length;
for (Entry<T> e = tab[index], prev = null; e != null; e = e.next) {
Object iobj = e.get();
if (iobj == null) {
// Clean up after a cleared Reference.
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
this.count--;
} else if (e.hash == hash &&
obj.getClass() == iobj.getClass() &&
equals(obj, iobj)) {
// Found canonical instance.
return true;
} else {
prev = e;
}
}
return false;
}
protected int hashCode(Object obj) {
return obj.hashCode();
}
protected boolean equals(Object a, Object b) {
return a.equals(b);
}
private void rehash() {
int oldCapacity = this.table.length;
Entry<T>[] tab = this.table;
int newCapacity = oldCapacity * 2 + 1;
Entry<T>[] newTab = new Entry[newCapacity];
this.threshold = (int)(newCapacity * this.loadFactor);
this.table = newTab;
for (int i = oldCapacity; i-- > 0; ) {
for (Entry<T> old = tab[i]; old != null; ) {
Entry<T> e = old;
old = old.next;
// Only copy entry if it hasn"t been cleared.
if (e.get() == null) {
this.count--;
} else {
int index = (e.hash & 0x7fffffff) % newCapacity;
e.next = newTab[index];
newTab[index] = e;
}
}
}
}
private static class Entry<T> extends WeakReference<T> {
int hash;
Entry<T> next;
Entry(T canonical, ReferenceQueue<T> queue, int hash, Entry<T> next) {
super(canonical, queue);
this.hash = hash;
this.next = next;
}
}
private class SetIterator implements Iterator<T> {
private final Entry<T>[] table;
private int index;
// To ensure that the iterator doesn"t return cleared entries, keep a
// hard reference to the canonical object. Its existence will prevent
// the weak reference from being cleared.
private T entryCanonical;
private Entry<T> entry;
SetIterator() {
this.table = WeakCanonicalSet.this.table;
this.index = table.length;
}
public boolean hasNext() {
while (this.entry == null || (this.entryCanonical = this.entry.get()) == null) {
if (this.entry != null) {
// Skip past a cleared Reference.
this.entry = this.entry.next;
} else {
if (this.index <= 0) {
return false;
} else {
this.entry = this.table[--this.index];
}
}
}
return true;
}
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
this.entry = this.entry.next;
return this.entryCanonical;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
}
Converts a char array to a Set
/*
* The contents of this file are subject to the Sapient Public License
* Version 1.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://carbon.sf.net/License.html.
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
* the specific language governing rights and limitations under the License.
*
* The Original Code is The Carbon Component Framework.
*
* The Initial Developer of the Original Code is Sapient Corporation
*
* Copyright (C) 2003 Sapient Corporation. All Rights Reserved.
*/
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
/**
* <p>Utilities for strings.</p>
*
*
* Copyright 2002 Sapient
* @since carbon 1.0
* @author Greg Hinkle, May 2002
* @version $Revision: 1.5 $($Author: dvoet $ / $Date: 2003/05/05 21:21:24 $)
*/
public class StringUtil {
/**
* <p> Converts a string to a Set. Breaks the string to characters and store
* each character in a Set.
*
* @param string the string to convert
* @return a <code>Set</code> containing all characters in the text string parameter
*/
public static Set convertToSet(String string) {
// Result hashset
Set resultSet = new HashSet();
for (int i = 0; i < string.length(); i++) {
resultSet.add(new Character(string.charAt(i)));
}
// Return result
return resultSet;
}
/**
* <p> Converts a char array to a Set. Puts all characters in the array to a Set.
*
* @param charArray an array of <CODE>char</CODE>s
* @return a <code>set</code> containing all characters in the char array
*/
public static Set convertToSet(char[] charArray) {
// Result hashset
Set resultSet = new HashSet();
for (int i = 0; i < charArray.length; i++) {
resultSet.add(new Character(charArray[i]));
}
// Return result
return resultSet;
}
}
Converts a string to a Set
/*
* The contents of this file are subject to the Sapient Public License
* Version 1.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://carbon.sf.net/License.html.
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
* the specific language governing rights and limitations under the License.
*
* The Original Code is The Carbon Component Framework.
*
* The Initial Developer of the Original Code is Sapient Corporation
*
* Copyright (C) 2003 Sapient Corporation. All Rights Reserved.
*/
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
/**
* <p>Utilities for strings.</p>
*
*
* Copyright 2002 Sapient
* @since carbon 1.0
* @author Greg Hinkle, May 2002
* @version $Revision: 1.5 $($Author: dvoet $ / $Date: 2003/05/05 21:21:24 $)
*/
public class StringUtil {
/**
* <p> Converts a string to a Set. Breaks the string to characters and store
* each character in a Set.
*
* @param string the string to convert
* @return a <code>Set</code> containing all characters in the text string parameter
*/
public static Set convertToSet(String string) {
// Result hashset
Set resultSet = new HashSet();
for (int i = 0; i < string.length(); i++) {
resultSet.add(new Character(string.charAt(i)));
}
// Return result
return resultSet;
}
/**
* <p> Converts a char array to a Set. Puts all characters in the array to a Set.
*
* @param charArray an array of <CODE>char</CODE>s
* @return a <code>set</code> containing all characters in the char array
*/
public static Set convertToSet(char[] charArray) {
// Result hashset
Set resultSet = new HashSet();
for (int i = 0; i < charArray.length; i++) {
resultSet.add(new Character(charArray[i]));
}
// Return result
return resultSet;
}
}
Copy all the elements from set2 to set1 (set1 += set2), set1 becomes the union of set1 and set2
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] argv) throws Exception {
Set set1 = new HashSet();
Set set2 = new HashSet();
set1.addAll(set2);
}
}
Demonstrate the Set interface
/*
* Copyright (c) Ian F. Darwin, http://www.darwinsys.ru/, 1996-2002.
* All rights reserved. Software written by Ian F. Darwin and others.
* $Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp $
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS""
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Java, the Duke mascot, and all variants of Sun"s Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun"s, and James Gosling"s,
* pioneering role in inventing and promulgating (and standardizing) the Java
* language and environment is gratefully acknowledged.
*
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/
import java.util.*;
/**
* Demonstrate the Set interface
* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version $Id: SetDemo.java,v 1.4 2004/02/09 03:34:04 ian Exp $
*/
public class SetDemo {
public static void main(String[] argv) {
//+
Set h = new HashSet();
h.add("One");
h.add("Two");
h.add("One"); // DUPLICATE
h.add("Three");
Iterator it = h.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
//-
}
}
Extend AbstractSet to Create Simple Set
/* SimpleSet Copyright (C) 1998-2002 Jochen Hoenicke.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this program; see the file COPYING.LESSER. If not, write to
* the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*
* $Id: SimpleSet.java.in,v 1.1.2.1 2002/05/28 17:34:24 hoenicke Exp $
*/
import java.util.AbstractSet;
import java.util.Iterator;
public class SimpleSet extends AbstractSet implements Cloneable
{
Object[] elementObjects;
int count = 0;
public SimpleSet() {
this(2);
}
public SimpleSet(int initialSize) {
elementObjects = new Object[initialSize];
}
public int size() {
return count;
}
public boolean add(Object element) {
if (element == null)
throw new NullPointerException();
for (int i=0; i< count; i++) {
if (element.equals(elementObjects[i]))
return false;
}
if (count == elementObjects.length) {
Object[] newArray = new Object[(count+1)*3/2];
System.arraycopy(elementObjects,0,newArray,0,count);
elementObjects = newArray;
}
elementObjects[count++] = element;
return true;
}
public Object clone() {
try {
SimpleSet other = (SimpleSet) super.clone();
other.elementObjects = (Object[]) elementObjects.clone();
return other;
} catch (CloneNotSupportedException ex) {
}
}
public Iterator iterator() {
return new Iterator() {
int pos = 0;
public boolean hasNext() {
return pos < count;
}
public Object next() {
return elementObjects[pos++];
}
public void remove() {
if (pos < count)
System.arraycopy(elementObjects, pos,
elementObjects, pos-1, count - pos);
count--;
pos--;
}
};
}
}
Get the intersection of set1 and set2, set1 becomes the intersection of set1 and set2
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] argv) throws Exception {
Set set1 = new HashSet();
Set set2 = new HashSet();
set1.retainAll(set2);
// Remove all elements from a set
set1.clear();
}
}
Implements the Set interface, backed by a ConcurrentHashMap instance
/*
* 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.
*/
import java.io.IOException;
import java.io.ObjectInputStream;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
/**
* This class implements the <tt>Set</tt> interface, backed by a ConcurrentHashMap instance.
*
* @author Matt Tucker
* @param <E>
*/
public class ConcurrentHashSet<E> extends AbstractSet<E>
implements
Set<E>,
Cloneable,
java.io.Serializable
{
/** */
private static final long serialVersionUID = 1L;
private transient ConcurrentHashMap<E, Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>ConcurrentHashMap</tt> instance has default
* initial capacity (16) and load factor (0.75).
*/
public ConcurrentHashSet()
{
map = new ConcurrentHashMap<E, Object>();
}
/**
* Constructs a new set containing the elements in the specified collection. The
* <tt>ConcurrentHashMap</tt> is created with default load factor (0.75) and an initial capacity
* sufficient to contain the elements in the specified collection.
*
* @param c
* the collection whose elements are to be placed into this set.
* @throws NullPointerException
* if the specified collection is null.
*/
public ConcurrentHashSet(Collection<? extends E> c)
{
map = new ConcurrentHashMap<E, Object>(Math.max((int)(c.size() / .75f) + 1, 16));
addAll(c);
}
/**
* Constructs a new, empty set; the backing <tt>ConcurrentHashMap</tt> instance has the
* specified initial capacity and the specified load factor.
*
* @param initialCapacity
* the initial capacity of the hash map.
* @param loadFactor
* the load factor of the hash map.
* @throws IllegalArgumentException
* if the initial capacity is less than zero, or if the load factor is nonpositive.
*/
public ConcurrentHashSet(int initialCapacity, float loadFactor)
{
map = new ConcurrentHashMap<E, Object>(initialCapacity, loadFactor, 16);
}
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has the specified initial
* capacity and default load factor, which is <tt>0.75</tt>.
*
* @param initialCapacity
* the initial capacity of the hash table.
* @throws IllegalArgumentException
* if the initial capacity is less than zero.
*/
public ConcurrentHashSet(int initialCapacity)
{
map = new ConcurrentHashMap<E, Object>(initialCapacity);
}
/**
*
* @see java.util.AbstractCollection#iterator()
*/
@Override
public Iterator<E> iterator()
{
return map.keySet().iterator();
}
/**
*
* @see java.util.AbstractCollection#size()
*/
@Override
public int size()
{
return map.size();
}
/**
*
* @see java.util.AbstractCollection#isEmpty()
*/
@Override
public boolean isEmpty()
{
return map.isEmpty();
}
/**
*
* @see java.util.AbstractCollection#contains(java.lang.Object)
*/
@Override
public boolean contains(Object o)
{
return map.containsKey(o);
}
/**
*
* @see java.util.AbstractCollection#add(java.lang.Object)
*/
@Override
public boolean add(E o)
{
return map.put(o, PRESENT) == null;
}
/**
*
* @see java.util.AbstractCollection#remove(java.lang.Object)
*/
@Override
public boolean remove(Object o)
{
return map.remove(o) == PRESENT;
}
/**
*
* @see java.util.AbstractCollection#clear()
*/
@Override
public void clear()
{
map.clear();
}
/**
*
* @see java.lang.Object#clone()
*/
@SuppressWarnings("unchecked")
@Override
public Object clone()
{
try
{
ConcurrentHashSet<E> newSet = (ConcurrentHashSet<E>)super.clone();
newSet.map.putAll(map);
return newSet;
}
catch (CloneNotSupportedException e)
{
throw new InternalError();
}
}
/**
*
* @param s
* @throws java.io.IOException
*/
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException
{
s.defaultWriteObject();
s.writeInt(map.size());
for (Iterator<E> i = map.keySet().iterator(); i.hasNext();)
{
s.writeObject(i.next());
}
}
/**
* Re-constitute the <tt>HashSet</tt> instance from a stream.
*
* @param inputStream
* @throws ClassNotFoundException
* @throws IOException
*/
private void readObject(ObjectInputStream inputStream) throws ClassNotFoundException,
IOException
{
inputStream.defaultReadObject();
map = new ConcurrentHashMap<E, Object>();
int size = inputStream.readInt();
for (int i = 0; i < size; i++)
{
E e = (E)inputStream.readObject();
map.put(e, PRESENT);
}
}
}
Int Set
/* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
*
* This program and the accompanying materials are made available under
* the terms of the Common Public License v1.0 which accompanies this distribution,
* and is available at http://www.eclipse.org/legal/cpl-v10.html
*
* $Id: IntSet.java,v 1.1.1.1 2004/05/09 16:57:53 vlad_r Exp $
*/
// ----------------------------------------------------------------------------
/**
*
* MT-safety: an instance of this class is <I>not</I> safe for access from
* multiple concurrent threads [even if access is done by a single thread at a
* time]. The caller is expected to synchronize externally on an instance [the
* implementation does not do internal synchronization for the sake of efficiency].
* java.util.ConcurrentModificationException is not supported either.
*
* @author Vlad Roubtsov, (C) 2001
*/
public
final class IntSet
{
// public: ................................................................
/**
* Equivalent to <CODE>IntSet(11, 0.75F)</CODE>.
*/
public IntSet ()
{
this (11, 0.75F);
}
/**
* Equivalent to <CODE>IntSet(capacity, 0.75F)</CODE>.
*/
public IntSet (final int initialCapacity)
{
this (initialCapacity, 0.75F);
}
/**
* Constructs an IntSet with specified initial capacity and load factor.
*
* @param initialCapacity initial number of hash buckets in the table [may not be negative, 0 is equivalent to 1].
* @param loadFactor the load factor to use to determine rehashing points [must be in (0.0, 1.0] range].
*/
public IntSet (int initialCapacity, final float loadFactor)
{
if (initialCapacity < 0) throw new IllegalArgumentException ("negative input: initialCapacity [" + initialCapacity + "]");
if ((loadFactor <= 0.0) || (loadFactor >= 1.0 + 1.0E-6))
throw new IllegalArgumentException ("loadFactor not in (0.0, 1.0] range: " + loadFactor);
if (initialCapacity == 0) initialCapacity = 1;
m_loadFactor = loadFactor > 1.0 ? 1.0F : loadFactor;
m_sizeThreshold = (int) (initialCapacity * loadFactor);
m_buckets = new Entry [initialCapacity];
}
/**
* Overrides Object.toString() for debug purposes.
*/
public String toString ()
{
final StringBuffer s = new StringBuffer ();
debugDump (s);
return s.toString ();
}
/**
* Returns the number of key-value mappings in this map.
*/
public int size ()
{
return m_size;
}
public boolean contains (final int key)
{
// index into the corresponding hash bucket:
final Entry [] buckets = m_buckets;
final int bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
// traverse the singly-linked list of entries in the bucket:
for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
{
if (key == entry.m_key)
return true;
}
return false;
}
public int [] values ()
{
if (m_size == 0)
return new int[0];
else
{
final int [] result = new int [m_size];
int scan = 0;
for (int b = 0; b < m_buckets.length; ++ b)
{
for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
{
result [scan ++] = entry.m_key;
}
}
return result;
}
}
public void values (final int [] target, final int offset)
{
if (m_size != 0)
{
int scan = offset;
for (int b = 0; b < m_buckets.length; ++ b)
{
for (Entry entry = m_buckets [b]; entry != null; entry = entry.m_next)
{
target [scan ++] = entry.m_key;
}
}
}
}
public boolean add (final int key)
{
Entry currentKeyEntry = null;
// detect if "key" is already in the table [in which case, set "currentKeyEntry" to point to its entry]:
// index into the corresponding hash bucket:
int bucketIndex = (key & 0x7FFFFFFF) % m_buckets.length;
// traverse the singly-linked list of entries in the bucket:
Entry [] buckets = m_buckets;
for (Entry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
{
if (key == entry.m_key)
{
currentKeyEntry = entry;
break;
}
}
if (currentKeyEntry == null)
{
// add a new entry:
if (m_size >= m_sizeThreshold) rehash ();
buckets = m_buckets;
bucketIndex = (key & 0x7FFFFFFF) % buckets.length;
final Entry bucketListHead = buckets [bucketIndex];
final Entry newEntry = new Entry (key, bucketListHead);
buckets [bucketIndex] = newEntry;
++ m_size;
return true;
}
else
return false;
}
// protected: .............................................................
// package: ...............................................................
void debugDump (final StringBuffer out)
{
if (out != null)
{
out.append (super.toString ()); out.append (EOL);
out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
out.append ("size threshold = " + m_sizeThreshold + EOL);
}
}
// private: ...............................................................
/**
* The structure used for chaining colliding keys.
*/
private static final class Entry
{
Entry (final int key, final Entry next)
{
m_key = key;
m_next = next;
}
final int m_key;
Entry m_next; // singly-linked list link
} // end of nested class
/**
* Re-hashes the table into a new array of buckets.
*/
private void rehash ()
{
// TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
// and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
// only grow in size
final Entry [] buckets = m_buckets;
final int newBucketCount = (m_buckets.length << 1) + 1;
final Entry [] newBuckets = new Entry [newBucketCount];
// rehash all entry chains in every bucket:
for (int b = 0; b < buckets.length; ++ b)
{
for (Entry entry = buckets [b]; entry != null; )
{
final Entry next = entry.m_next; // remember next pointer because we are going to reuse this entry
final int entryKey = entry.m_key;
// index into the corresponding new hash bucket:
final int newBucketIndex = (entryKey & 0x7FFFFFFF) % newBucketCount;
final Entry bucketListHead = newBuckets [newBucketIndex];
entry.m_next = bucketListHead;
newBuckets [newBucketIndex] = entry;
entry = next;
}
}
m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
m_buckets = newBuckets;
}
private final float m_loadFactor; // determines the setting of m_sizeThreshold
private Entry [] m_buckets; // table of buckets
private int m_size; // number of keys in the table, not cleared as of last check
private int m_sizeThreshold; // size threshold for rehashing
private static final String EOL = System.getProperty ("line.separator", "\n");
} // end of class
// ----------------------------------------------------------------------------
List Set implements Set
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
/*
*
* JAFFA - Java Application Framework For All
*
* Copyright (C) 2002 JAFFA Development Group
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* Redistribution and use of this software and associated documentation ("Software"),
* with or without modification, are permitted provided that the following conditions are met:
* 1. Redistributions of source code must retain copyright statements and notices.
* Redistributions must also contain a copy of this document.
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
* 3. The name "JAFFA" must not be used to endorse or promote products derived from
* this Software without prior written permission. For written permission,
* please contact mail to: jaffagroup@yahoo.ru.
* 4. Products derived from this Software may not be called "JAFFA" nor may "JAFFA"
* appear in their names without prior written permission.
* 5. Due credit should be given to the JAFFA Project (http://jaffa.sourceforge.net).
*
* THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
*/
/**
* This class is backed by an ArrayList. Features are
* 1) Ensure the Set functionality of unique elements(including a null) in this data structure
* 2) Iterate through the list in the order in which the entries were made
*/
class ListSet implements Set, Cloneable, Serializable {
List m_set = null;
/** Creates new ListSet */
public ListSet() {
m_set = new ArrayList();
}
/** Creates new ListSet specifying the initial capacity.
* @param initialCapacity The initial capacity.
*/
public ListSet(int initialCapacity) {
m_set = new ArrayList(initialCapacity);
}
/** Creates new ListSet from an existing Collection.
* @param c An existing collection.
*/
public ListSet(Collection c) {
m_set = new ArrayList();
if (c != null) {
for (Iterator itr = c.iterator(); itr.hasNext();) {
Object obj = itr.next();
if ( !m_set.contains(obj) )
m_set.add(obj);
}
}
}
// *** Set Interface methods ***
/** Retains only the elements in this set that are contained in the specified collection.
* @param c collection that defines which elements this set will retain.
* @return true if this collection changed as a result of the call.
*/
public boolean retainAll(Collection c) {
return m_set.retainAll(c);
}
/** Returns true if this set contains the specified element.
* @param o element whose presence in this set is to be tested.
* @return true if this set contains the specified element.
*/
public boolean contains(Object o) {
return m_set.contains(o);
}
/** Returns an array containing all of the elements in this set.
* @return an array containing all of the elements in this set.
*/
public Object[] toArray() {
return m_set.toArray();
}
/** Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array.
* @param a the array into which the elements of this set are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
* @return an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array
*/
public Object[] toArray(Object[] a) {
return m_set.toArray(a);
}
/** Returns an iterator over the elements in this set.
* @return an iterator over the elements in this set.
*/
public Iterator iterator() {
return m_set.iterator();
}
/** Removes from this set all of its elements that are contained in the specified collection.
* @param c collection that defines which elements will be removed from this set.
* @return true if this set changed as a result of the call.
*/
public boolean removeAll(Collection c) {
return m_set.removeAll(c);
}
/** Removes the specified element from this set if it is present.
* @param o object to be removed from this set, if present.
* @return true if the set contained the specified element.
*/
public boolean remove(Object o) {
return m_set.remove(o);
}
/** Removes all of the elements from this set.*/
public void clear() {
m_set.clear();
}
/** Returns the hash code value for this set.
* @return the hash code value for this set.
*/
public int hashCode() {
return m_set.hashCode();
}
/** Adds all of the elements in the specified collection to this set if they"re not already present.
* @param c collection whose elements are to be added to this set.
* @return true if this set changed as a result of the call.
*/
public boolean addAll(Collection c) {
boolean added = false;
if (c != null) {
for (Iterator itr = c.iterator(); itr.hasNext();) {
Object obj = itr.next();
if ( !m_set.contains(obj) ) {
m_set.add(obj);
added = true;
}
}
}
return added;
}
/** Returns the number of elements in this set.
* @return the number of elements in this set.
*/
public int size() {
return m_set.size();
}
/** Returns true if this set contains all of the elements of the specified collection.
* @param c collection to be checked for containment in this set.
* @return true if this set contains all of the elements of the specified collection.
*/
public boolean containsAll(Collection c) {
return m_set.containsAll(c);
}
/** Adds the specified element to this set if it is not already present.
* @param o element to be added to this set.
* @return true if this set did not already contain the specified element.
*/
public boolean add(Object o) {
boolean added = false;
if ( !m_set.contains(o) ) {
m_set.add(o);
added = true;
}
return added;
}
/** Compares the specified object with this set for equality.
* @param o Object to be compared for equality with this set.
* @return true if the specified Object is equal to this set.
*/
public boolean equals(Object o) {
return m_set.equals(o);
}
/** Returns true if this set contains no elements.
* @return true if this set contains no elements.
*/
public boolean isEmpty() {
return m_set.isEmpty();
}
// *** Additional Methods ***
/** Adds the specified element to this set if it is not already present, at the specified index.
* @param index The position at which the element is to be added.
* @param o element to be added to this set.
*/
public void add(int index, Object o) {
if ( !m_set.contains(o) )
m_set.add(index, o);
}
/** Returns the element from the specified position.
* @param index The position from which the element is to be retrieved.
* @return the element from the specified position.
*/
public Object get(int index) {
return m_set.get(index);
}
/** Remove the element from the specified position.
* @param index The position from which the element is to be removed.
* @return the element being removed.
*/
public Object remove(int index) {
return m_set.remove(index);
}
/** Returns the index of the element in this set.
* @param o The element whose index is to be found.
* @return the index of the element in this set.
*/
public int indexOf(Object o) {
return m_set.indexOf(o);
}
// *** CLONEABLE INTERFACE METHODS ***
/** Returns a clone of the Set.
* @throws CloneNotSupportedException if cloning is not supported. Should never happen.
* @return a clone of the Set.
*/
public Object clone() throws CloneNotSupportedException {
Object obj = super.clone();
if (m_set != null && m_set instanceof Cloneable)
( (ListSet) obj ).m_set = (List) ( (ArrayList) m_set ).clone();
return obj;
}
}
One Item Set
/* $Id$
*
* Behavior Protocols Tools - Parsers, Transformations
* Copyright (C) 2006-2007 DSRG, Charles University in Prague
* http://dsrg.mff.cuni.cz/
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301 USA
*
*/
import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
*
* @author thorm
*/
public class OneItemSet<E> extends AbstractCollection<E> implements Serializable{
public boolean add(E i) {
if (item == i) {
return false;
}
if (item == null) {
item = i;
return true;
}
throw new IllegalArgumentException();
}
public Iterator<E> iterator() {
return new Iterator() {
public boolean hasNext() {
return hasNxt;
}
public E next() {
if (hasNxt) {
hasNxt = false;
return item;
}
throw new NoSuchElementException();
}
public void remove() {
item = null;
}
boolean hasNxt = true;
};
}
public int size() {
return (item == null) ? 0 : 1;
}
public int hashCode() {
return item.hashCode();
}
public boolean equals(Object o) {
return (o instanceof OneItemSet) && item.equals(((OneItemSet) o).item);
}
E item;
}
Putting your own type in a Set
// : c11:Set2.java
// Putting your own type in a Set.
// From "Thinking in Java, 3rd ed." (c) Bruce Eckel 2002
// www.BruceEckel.ru. See copyright notice in CopyRight.txt.
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class Set2 {
public static Set fill(Set a, int size) {
for (int i = 0; i < size; i++)
a.add(new Integer(i));
return a;
}
public static void test(Set a) {
fill(a, 10);
fill(a, 10); // Try to add duplicates
fill(a, 10);
a.addAll(fill(new TreeSet(), 10));
System.out.println(a);
}
public static void main(String[] args) {
test(new HashSet());
test(new TreeSet());
test(new LinkedHashSet());
}
} ///:~
Remove all elements from a set
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] argv) throws Exception {
Set set1 = new HashSet();
set1.clear();
}
}
Remove all the elements in set1 from set2 (set1 -= set2), set1 becomes the asymmetric difference of set1 and set2
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] argv) throws Exception {
Set set1 = new HashSet();
Set set2 = new HashSet();
set1.removeAll(set2);
}
}
Set and TreeSet
import java.util.*;
public class Comp {
public static void main (String args[]) throws Exception {
String elements[] = {"Irish Setter", "Poodle",
"English Setter", "Gordon Setter", "Pug"};
Set set = new TreeSet(Collections.reverseOrder());
for (int i=0, n=elements.length; i<n; i++) {
set.add(elements[i]);
}
System.out.println(set);
System.out.println(((TreeSet)set).ruparator());
}
}
Set Copy
import java.io.*;
import java.util.*;
public class Copy {
public static void main (String args[]) throws Exception {
String elements[] = {"Irish Setter", "Poodle",
"English Setter", "Gordon Setter", "Pug"};
Set set = new HashSet(Arrays.asList(elements));
Set set2 = ((Set)((HashSet)set).clone());
System.out.println(set2);
FileOutputStream fos = new FileOutputStream("set.ser");
ObjectOutputStream oos = new ObjectOutputStream(fos);
oos.writeObject(set);
oos.close();
FileInputStream fis = new FileInputStream("set.ser");
ObjectInputStream ois = new ObjectInputStream(fis);
Set set3 = (Set)ois.readObject();
ois.close();
System.out.println(set3);
}
}
Set, HashSet and TreeSet
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String args[]) {
Set<String> hs = new HashSet<String>();
hs.add("one");
hs.add("two");
hs.add("three");
System.out.println("Here is the HashSet: " + hs);
if (!hs.add("three"))
System.out.println("Attempt to add duplicate. " + "Set is unchanged: " + hs);
TreeSet<Integer> ts = new TreeSet<Integer>();
ts.add(8);
ts.add(19);
ts.add(-2);
ts.add(3);
System.out.println(ts);
System.out.println("First element in ts: " + ts.first());
System.out.println("Last element in ts: " + ts.last());
System.out.println("First element > 15: " + ts.higher(15));
System.out.println("First element < 15: " + ts.lower(15));
}
}
Set implementation that use == instead of equals()
/*
* Hibernate, Relational Persistence for Idiomatic Java
*
* Copyright (c) 2008, Red Hat Middleware LLC or third-party contributors as
* indicated by the @author tags or express copyright attribution
* statements applied by the authors. All third-party contributions are
* distributed under license by Red Hat Middleware LLC.
*
* This copyrighted material is made available to anyone wishing to use, modify,
* copy, or redistribute it subject to the terms and conditions of the GNU
* Lesser General Public License, as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
* for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this distribution; if not, write to:
* Free Software Foundation, Inc.
* 51 Franklin Street, Fifth Floor
* Boston, MA 02110-1301 USA
*
*/
import java.util.Collection;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Set;
/**
* Set implementation that use == instead of equals() as its comparison
* mechanism. This is achieved by internally using an IdentityHashMap.
*
* @author Emmanuel Bernard
*/
public class IdentitySet implements Set {
private static final Object DUMP_VALUE = new Object();
private final IdentityHashMap map;
/**
* Create an IdentitySet with default sizing.
*/
public IdentitySet() {
this.map = new IdentityHashMap();
}
/**
* Create an IdentitySet with the given sizing.
*
* @param sizing The sizing of the set to create.
*/
public IdentitySet(int sizing) {
this.map = new IdentityHashMap( sizing );
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.get( o ) == DUMP_VALUE;
}
public Iterator iterator() {
return map.entrySet().iterator();
}
public Object[] toArray() {
return map.entrySet().toArray();
}
public Object[] toArray(Object[] a) {
return map.entrySet().toArray( a );
}
public boolean add(Object o) {
return map.put( o, DUMP_VALUE ) == null;
}
public boolean remove(Object o) {
return map.remove( o ) == DUMP_VALUE;
}
public boolean containsAll(Collection c) {
Iterator it = c.iterator();
while ( it.hasNext() ) {
if ( !map.containsKey( it.next() ) ) {
return false;
}
}
return true;
}
public boolean addAll(Collection c) {
Iterator it = c.iterator();
boolean changed = false;
while ( it.hasNext() ) {
if ( this.add( it.next() ) ) {
changed = true;
}
}
return changed;
}
public boolean retainAll(Collection c) {
//doable if needed
throw new UnsupportedOperationException();
}
public boolean removeAll(Collection c) {
Iterator it = c.iterator();
boolean changed = false;
while ( it.hasNext() ) {
if ( this.remove( it.next() ) ) {
changed = true;
}
}
return changed;
}
public void clear() {
map.clear();
}
}
Set operations: union, intersection, difference, symmetric difference, is subset, is superset
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static <T> Set<T> union(Set<T> setA, Set<T> setB) {
Set<T> tmp = new TreeSet<T>(setA);
tmp.addAll(setB);
return tmp;
}
public static <T> Set<T> intersection(Set<T> setA, Set<T> setB) {
Set<T> tmp = new TreeSet<T>();
for (T x : setA)
if (setB.contains(x))
tmp.add(x);
return tmp;
}
public static <T> Set<T> difference(Set<T> setA, Set<T> setB) {
Set<T> tmp = new TreeSet<T>(setA);
tmp.removeAll(setB);
return tmp;
}
public static <T> Set<T> symDifference(Set<T> setA, Set<T> setB) {
Set<T> tmpA;
Set<T> tmpB;
tmpA = union(setA, setB);
tmpB = intersection(setA, setB);
return difference(tmpA, tmpB);
}
public static <T> boolean isSubset(Set<T> setA, Set<T> setB) {
return setB.containsAll(setA);
}
public static <T> boolean isSuperset(Set<T> setA, Set<T> setB) {
return setA.containsAll(setB);
}
public static void main(String args[]) {
TreeSet<Character> set1 = new TreeSet<Character>();
TreeSet<Character> set2 = new TreeSet<Character>();
set1.add("A");
set1.add("B");
set1.add("C");
set1.add("D");
set2.add("C");
set2.add("D");
set2.add("E");
set2.add("F");
System.out.println("set1: " + set1);
System.out.println("set2: " + set2);
System.out.println("Union: " + union(set1, set2));
System.out.println("Intersection: " + intersection(set1, set2));
System.out.println("Difference (set1 - set2): " + difference(set1, set2));
System.out.println("Symmetric Difference: " + symDifference(set1, set2));
TreeSet<Character> set3 = new TreeSet<Character>(set1);
set3.remove("D");
System.out.println("set3: " + set3);
System.out.println("Is set1 a subset of set2? " + isSubset(set1, set3));
System.out.println("Is set1 a superset of set2? " + isSuperset(set1, set3));
System.out.println("Is set3 a subset of set1? " + isSubset(set3, set1));
System.out.println("Is set3 a superset of set1? " + isSuperset(set3, set1));
}
}
Set subtraction
import java.util.HashSet;
import java.util.Set;
public class FindDupsAndUnique {
public static void main(String args[]) {
Set uniques = new HashSet();
Set dups = new HashSet();
String[] values = new String[] { "java", "java2", "jexp", "javas",
"java" };
for (int i = 0; i < values.length; i++)
if (!uniques.add(values[i]))
dups.add(values[i]);
uniques.removeAll(dups); // Destructive set-difference
System.out.println("Unique words: " + uniques);
System.out.println("Duplicate words: " + dups);
}
}
Set that compares object by identity rather than equality
// $Id: IdentitySet.java 16179 2009-03-18 11:08:10Z hardy.ferentschik $
/*
* JBoss, Home of Professional Open Source
* Copyright 2008, Red Hat Middleware LLC, and individual contributors
* by the @authors tag. See the copyright.txt in the distribution for a
* full listing of individual contributors.
*
* Licensed 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.
*/
import java.util.Collection;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
* Set that compares object by identity rather than equality. Wraps around a <code>IdentityHashMap</code>
*
* @author Emmanuel Bernard
*/
public class IdentitySet implements Set {
private Map<Object, Object> map;
private Object CONTAINS = new Object();
public IdentitySet() {
this( 10 );
}
public IdentitySet(int size) {
this.map = new IdentityHashMap<Object, Object>( size );
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey( o );
}
public Iterator iterator() {
return map.keySet().iterator();
}
public Object[] toArray() {
return map.keySet().toArray();
}
public boolean add(Object o) {
return map.put( o, CONTAINS ) == null;
}
public boolean remove(Object o) {
return map.remove( o ) == CONTAINS;
}
public boolean addAll(Collection c) {
boolean doThing = false;
for ( Object o : c ) {
doThing = doThing || add( o );
}
return doThing;
}
public void clear() {
map.clear();
}
public boolean removeAll(Collection c) {
boolean remove = false;
for ( Object o : c ) {
remove = remove || remove( o );
}
return remove;
}
public boolean retainAll(Collection c) {
throw new UnsupportedOperationException();
}
public boolean containsAll(Collection c) {
for ( Object o : c ) {
if ( !contains( o ) ) {
return false;
}
}
return true;
}
public Object[] toArray(Object[] a) {
return map.keySet().toArray( a );
}
@Override
public String toString() {
return "IdentitySet{" +
"map=" + map +
"}";
}
}
Set union and intersection
/* *****************************************************************************
* SetUils.java
* ****************************************************************************/
/* J_LZ_COPYRIGHT_BEGIN *******************************************************
* Copyright 2001-2004 Laszlo Systems, Inc. All Rights Reserved. *
* Use is subject to license terms. *
* J_LZ_COPYRIGHT_END *********************************************************/
import java.util.*;
/**
* A utility class containing set utility functions.
*
* @author Oliver Steele
*/
public abstract class SetUtils {
public static boolean containsAny(Set a, Set b) {
for (Iterator iter = b.iterator(); iter.hasNext(); ) {
if (a.contains(iter.next())) {
return true;
}
}
return false;
}
public static Set intersection(Set a, Set b) {
Set c = new HashSet();
for (Iterator iter = b.iterator(); iter.hasNext(); ) {
Object e = iter.next();
if (a.contains(e)) {
c.add(e);
}
}
return c;
}
}
Set with values iterated in insertion order.
/*
Copyright (c) 2007, Dennis M. Sosnoski
All rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
* Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
* Neither the name of JiBX nor the names of its contributors may be used
to endorse or promote products derived from this software without specific
prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/**
* Set with values iterated in insertion order. This is similar to the Java 1.4
* java.util.LinkedHashSet class, but compatible with earlier JVM versions. This
* implementation is for insert-only sets.
*/
public class InsertionOrderedSet implements Set
{
private final Set m_baseMap;
private final ArrayList m_insertList;
public InsertionOrderedSet() {
m_baseMap = new HashSet();
m_insertList = new ArrayList();
}
/* (non-Javadoc)
* @see java.util.Map#clear()
*/
public void clear() {
m_baseMap.clear();
m_insertList.clear();
}
/* (non-Javadoc)
* @see java.util.Set#isEmpty()
*/
public boolean isEmpty() {
return m_baseMap.isEmpty();
}
/* (non-Javadoc)
* @see java.util.Set#size()
*/
public int size() {
return m_baseMap.size();
}
/* (non-Javadoc)
* @see java.util.Set#add(java.lang.Object)
*/
public boolean add(Object o) {
if (m_baseMap.contains(o)) {
return false;
} else {
m_baseMap.add(o);
m_insertList.add(o);
return true;
}
}
/* (non-Javadoc)
* @see java.util.Set#addAll(java.util.Collection)
*/
public boolean addAll(Collection c) {
boolean changed = false;
for (Iterator iter = c.iterator(); iter.hasNext();) {
Object item = (Object)iter.next();
if (add(item)) {
changed = true;
}
}
return changed;
}
/* (non-Javadoc)
* @see java.util.Set#contains(java.lang.Object)
*/
public boolean contains(Object o) {
return m_baseMap.contains(o);
}
/* (non-Javadoc)
* @see java.util.Set#containsAll(java.util.Collection)
*/
public boolean containsAll(Collection c) {
return m_baseMap.containsAll(c);
}
/* (non-Javadoc)
* @see java.util.Set#iterator()
*/
public Iterator iterator() {
return m_insertList.iterator();
}
/* (non-Javadoc)
* @see java.util.Set#remove(java.lang.Object)
*/
public boolean remove(Object o) {
throw new UnsupportedOperationException("add-only set");
}
/* (non-Javadoc)
* @see java.util.Set#removeAll(java.util.Collection)
*/
public boolean removeAll(Collection c) {
throw new UnsupportedOperationException("add-only set");
}
/* (non-Javadoc)
* @see java.util.Set#retainAll(java.util.Collection)
*/
public boolean retainAll(Collection c) {
throw new UnsupportedOperationException("add-only set");
}
/* (non-Javadoc)
* @see java.util.Set#toArray()
*/
public Object[] toArray() {
return m_insertList.toArray();
}
/* (non-Javadoc)
* @see java.util.Set#toArray(T[])
*/
public Object[] toArray(Object[] a) {
return m_insertList.toArray(a);
}
/**
* Convenience method to add every item in an array.
*
* @param objs
*/
public void addAll(Object[] objs) {
for (int i = 0; i < objs.length; i++) {
add(objs[i]);
}
}
/**
* Get list of values in order added. The returned list is live, and will
* grow as new items are added to the set.
*
* @return list
*/
public ArrayList asList() {
return m_insertList;
}
}
Show the union and intersection of two sets
/*
* Copyright (c) Ian F. Darwin, http://www.darwinsys.ru/, 1996-2002.
* All rights reserved. Software written by Ian F. Darwin and others.
* $Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp $
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS""
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Java, the Duke mascot, and all variants of Sun"s Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun"s, and James Gosling"s,
* pioneering role in inventing and promulgating (and standardizing) the Java
* language and environment is gratefully acknowledged.
*
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/
import java.util.*;
/** Show the union and instersection of two sets. */
public class SetStuff {
public static void main(String[] args) {
// Create two sets.
Set s1 = new HashSet();
s1.add("Ian Darwin");
s1.add("Bill Dooley");
s1.add("Jesse James");
Set s2 = new HashSet();
s2.add("Ian Darwin");
s2.add("Doolin" Dalton");
Set union = new TreeSet(s1);
union.addAll(s2); // now contains the union
print("union", union);
Set intersect = new TreeSet(s1);
intersect.retainAll(s2);
print("intersection", intersect);
}
protected static void print(String label, Collection c) {
System.out.println("--------------" + label + "--------------");
Iterator it = c.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
Small sets whose elements are known to be unique by construction
/*
* JGraphT : a free Java graph-theory library
*
*
* Project Info: http://jgrapht.sourceforge.net/
* Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
*
* (C) Copyright 2003-2007, by Barak Naveh and Contributors.
*
* This library is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or
* (at your option) any later version.
*
* This library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library; if not, write to the Free Software Foundation,
* Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
*/
/* -----------------
* ArrayUnenforcedSet.java
* -----------------
* (C) Copyright 2006-2007, by John V. Sichi and Contributors.
*
* Original Author: John V. Sichi
* Contributor(s): -
*
* $Id: ArrayUnenforcedSet.java 568 2007-09-30 00:12:18Z perfecthash $
*
* Changes
* -------
* 07-May-2006 : Initial version (JVS);
*/
import java.util.*;
/**
* Helper for efficiently representing small sets whose elements are known to be
* unique by construction, implying we don"t need to enforce the uniqueness
* property in the data structure itself. Use with caution.
*
* <p>Note that for equals/hashCode, the class implements the Set behavior
* (unordered), not the list behavior (ordered); the fact that it subclasses
* ArrayList should be considered an implementation detail.
*
* @author John V. Sichi
*/
public class ArrayUnenforcedSet<E>
extends ArrayList<E>
implements Set<E>
{
//~ Static fields/initializers ---------------------------------------------
private static final long serialVersionUID = -7413250161201811238L;
//~ Constructors -----------------------------------------------------------
public ArrayUnenforcedSet()
{
super();
}
public ArrayUnenforcedSet(Collection<? extends E> c)
{
super(c);
}
public ArrayUnenforcedSet(int n)
{
super(n);
}
//~ Methods ----------------------------------------------------------------
public boolean equals(Object o)
{
return new SetForEquality().equals(o);
}
public int hashCode()
{
return new SetForEquality().hashCode();
}
//~ Inner Classes ----------------------------------------------------------
/**
* Multiple inheritance helper.
*/
private class SetForEquality
extends AbstractSet<E>
{
public Iterator<E> iterator()
{
return ArrayUnenforcedSet.this.iterator();
}
public int size()
{
return ArrayUnenforcedSet.this.size();
}
}
}
// End ArrayUnenforcedSet.java
Sync Test
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class SyncTest {
public static void main(String args[]) {
Set simpsons = new HashSet();
simpsons.add("Bart");
simpsons.add("Hugo");
simpsons.add("Lisa");
simpsons.add("Marge");
simpsons.add("Homer");
simpsons.add("Maggie");
simpsons.add("Roy");
simpsons = Collections.synchronizedSet(simpsons);
synchronized (simpsons) {
Iterator iter = simpsons.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
Map map = Collections.synchronizedMap(new HashMap(89));
Set set = map.entrySet();
synchronized (map) {
Iterator iter = set.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}
}
Tail
import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;
public class Tail {
public static void main(String args[]) throws Exception {
String elements[] = { "Irish Setter", "Poodle", "English Setter",
"Gordon Setter", "Pug" };
SortedSet set = new TreeSet(Arrays.asList(elements));
System.out.println(set.tailSet("Irish Setter"));
System.out.println(set.headSet("Irish Setter"));
System.out.println(set.headSet("Irish Setter\0"));
System.out.println(set.tailSet("Irish Setter\0"));
System.out.println(set.subSet("Irish Setter", "Poodle\0"));
System.out.println(set.subSet("Irish Setter", "Irish Setter\0"));
System.out.println(set.subSet("Irish Setter", "Irish Setter"));
}
}
Things you can do with Sets
// : c11:Set1.java
// Things you can do with Sets.
// From "Thinking in Java, 3rd ed." (c) Bruce Eckel 2002
// www.BruceEckel.ru. See copyright notice in CopyRight.txt.
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class Set1 {
static void fill(Set s) {
s.addAll(Arrays.asList("one two three four five six seven".split(" ")));
}
public static void test(Set s) {
// Strip qualifiers from class name:
System.out.println(s.getClass().getName().replaceAll("\\w+\\.", ""));
fill(s);
fill(s);
fill(s);
System.out.println(s); // No duplicates!
// Add another set to this one:
s.addAll(s);
s.add("one");
s.add("one");
s.add("one");
System.out.println(s);
// Look something up:
System.out.println("s.contains(\"one\"): " + s.contains("one"));
}
public static void main(String[] args) {
test(new HashSet());
test(new TreeSet());
test(new LinkedHashSet());
}
} ///:~
TreeSet Demo
/*
* Copyright (c) Ian F. Darwin, http://www.darwinsys.ru/, 1996-2002.
* All rights reserved. Software written by Ian F. Darwin and others.
* $Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp $
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS""
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Java, the Duke mascot, and all variants of Sun"s Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun"s, and James Gosling"s,
* pioneering role in inventing and promulgating (and standardizing) the Java
* language and environment is gratefully acknowledged.
*
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/
import java.util.TreeSet;
/**
* TreeSet Demo.
*
* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version $Id: TreeSetDemo.java,v 1.3 2004/02/09 03:34:04 ian Exp $
*/
public class TreeSetDemo {
public static void main(String[] argv) {
//+
/*
* A TreeSet keeps objects in sorted order. We use a Comparator
* published by String for case-insensitive sorting order.
*/
TreeSet tm = new TreeSet(String.CASE_INSENSITIVE_ORDER);
tm.add("Gosling");
tm.add("da Vinci");
tm.add("van Gogh");
tm.add("Java To Go");
tm.add("Vanguard");
tm.add("Darwin");
tm.add("Darwin"); // TreeSet is Set, ignores duplicates.
// Since it is sorted we can ask for various subsets
System.out.println("Lowest (alphabetically) is " + tm.first());
// Print how many elements are greater than "k"
System.out.println(tm.tailSet("k").toArray().length
+ " elements higher than \"k\"");
// Print the whole list in sorted order
System.out.println("Sorted list:");
java.util.Iterator t = tm.iterator();
while (t.hasNext())
System.out.println(t.next());
//-
}
}
Use set
import java.util.HashSet;
import java.util.Set;
public class FindDups {
public static void main(String args[]) {
Set s = new HashSet();
String[] values = new String[] { "java", "java2", "jexp", "javas",
"java" };
for (int i = 0; i < values.length; i++)
if (!s.add(values[i]))
System.out.println("Duplicate detected: " + values[i]);
System.out.println(s.size() + " distinct words detected: " + s);
}
}
What you can do with a TreeSet
// : c11:SortedSetDemo.java
// What you can do with a TreeSet.
// From "Thinking in Java, 3rd ed." (c) Bruce Eckel 2002
// www.BruceEckel.ru. See copyright notice in CopyRight.txt.
import java.util.Arrays;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortedSetDemo {
public static void main(String[] args) {
SortedSet sortedSet = new TreeSet(Arrays
.asList("one two three four five six seven eight".split(" ")));
System.out.println(sortedSet);
Object low = sortedSet.first(), high = sortedSet.last();
System.out.println(low);
System.out.println(high);
Iterator it = sortedSet.iterator();
for (int i = 0; i <= 6; i++) {
if (i == 3)
low = it.next();
if (i == 6)
high = it.next();
else
it.next();
}
System.out.println(low);
System.out.println(high);
System.out.println(sortedSet.subSet(low, high));
System.out.println(sortedSet.headSet(high));
System.out.println(sortedSet.tailSet(low));
}
} ///:~
Working with HashSet and TreeSet
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class ItemSet {
public static void main(String args[]) {
String names[] = { "Item 1", "Item 2", "Item 3"};
Set moons = new HashSet();
int namesLen = names.length;
int index;
for (int i = 0; i < 100; i++) {
index = (int) (Math.random() * namesLen);
moons.add(names[index]);
}
Iterator it = moons.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
System.out.println("---");
Set orderedMoons = new TreeSet(moons);
it = orderedMoons.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
