Java/Collections Data Structure/Array Collections
Версия от 18:01, 31 мая 2010; (обсуждение)
Содержание
- 1 ArrayEnumeration class (implements Enumeration)
- 2 Array Int Set
- 3 Array Set
- 4 Convert an Array to a List
- 5 Convert an array to a Map
- 6 Converting a Collection of String to an Array
- 7 Converting a Collection of user objects to an Array
- 8 Converting an Array to a Collection
- 9 Converts array into a java.util.Map.
- 10 Custom ArrayMap implementation (extends AbstractMap)
- 11 Custom ArraySet implementation (extends AbstractSet)
- 12 Remove duplicate element from array
- 13 Treating an Array as an Enumeration
ArrayEnumeration class (implements Enumeration)
import java.lang.reflect.Array;
import java.util.Enumeration;
public class ArrayEnumeration implements Enumeration {
private final int size;
private int cursor;
private final Object array;
public ArrayEnumeration(Object obj) {
Class type = obj.getClass();
if (!type.isArray()) {
throw new IllegalArgumentException("Invalid type: " + type);
}
size = Array.getLength(obj);
array = obj;
}
public boolean hasMoreElements() {
return (cursor < size);
}
public Object nextElement() {
return Array.get(array, cursor++);
}
public static void main(String args[]) {
Object obj = new int[] { 2, 3, 5, 8, 13, 21 };
ArrayEnumeration e = new ArrayEnumeration(obj);
while (e.hasMoreElements()) {
System.out.println(e.nextElement());
}
try {
e = new ArrayEnumeration(ArrayEnumeration.class);
} catch (IllegalArgumentException ex) {
System.out.println(ex.getMessage());
}
}
}
Array Int Set
/*
* Copyright (c) 2002-2008 "Neo Technology,"
* Network Engine for Objects in Lund AB [http://neotechnology.ru]
*
* This file is part of Neo4j.
*
* Neo4j is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, 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 Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
// use array for first few properties to decrease memory footprint (and
// to some extent boost performance) for nodes/rels with few properties
public class ArrayIntSet
{
private int maxRelSize = 256;
private int[] rels = new int[2];
// TODO: figure out if we need volatile here?
private int arrayCount = 0;
private Set<Integer> relationshipSet = null;
public boolean add( int id )
{
for ( int i = 0; i < arrayCount; i++ )
{
if ( rels[i] == id )
{
return false;
}
}
if ( arrayCount == rels.length && rels.length * 2 <= maxRelSize )
{
int newRels[] = new int[rels.length * 2];
System.arraycopy( rels, 0, newRels, 0, rels.length );
rels = newRels;
}
if ( arrayCount != -1 )
{
if ( arrayCount < rels.length )
{
rels[arrayCount++] = id;
return true;
}
relationshipSet = new HashSet<Integer>();
for ( int i = 0; i < arrayCount; i++ )
{
relationshipSet.add( rels[i] );
}
arrayCount = -1;
}
return relationshipSet.add( id );
}
public Iterator<Integer> iterator()
{
if ( arrayCount == -1 )
{
return relationshipSet.iterator();
}
return new ArrayIntIterator( rels, arrayCount );
}
public boolean remove( int id )
{
for ( int i = 0; i < arrayCount; i++ )
{
if ( rels[i] == id )
{
int[] dest = rels;
if ( arrayCount - 1 < rels.length / 3 )
{
dest = new int[rels.length / 2];
System.arraycopy( rels, 0, dest, 0, arrayCount );
}
if ( i + 1 < dest.length && (arrayCount - i - 1) > 0 )
{
System.arraycopy( rels, i + 1, dest, i, arrayCount - i - 1 );
rels = dest;
}
arrayCount--;
return true;
}
}
if ( arrayCount == -1 )
{
return relationshipSet.remove( id );
}
return false;
}
public Iterable<Integer> values()
{
if ( arrayCount == -1 )
{
return relationshipSet;
}
return new ArrayIntIterator( rels, arrayCount );
}
private static class ArrayIntIterator implements Iterator<Integer>,
Iterable<Integer>
{
private int[] intArray;
private int pos = -1;
private int arrayCount;
ArrayIntIterator( int[] array, int count )
{
this.intArray = array;
this.arrayCount = count;
}
public boolean hasNext()
{
return pos + 1 < arrayCount;
}
public Integer next()
{
return intArray[++pos];
}
public void remove()
{
throw new UnsupportedOperationException();
}
public Iterator<Integer> iterator()
{
return this;
}
}
public boolean contains( int id )
{
for ( int i = 0; i < arrayCount; i++ )
{
if ( rels[i] == id )
{
return true;
}
}
if ( arrayCount == -1 )
{
return relationshipSet.contains( id );
}
return false;
}
public int size()
{
if ( arrayCount != -1 )
{
return arrayCount;
}
return relationshipSet.size();
}
}
Array Set
/* Copyright (c) 2006, 2009, Carl Burch. License information is located in the
* com.cburch.logisim.Main source code and at www.cburch.ru/logisim/. */
import java.util.AbstractSet;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class ArraySet extends AbstractSet {
private static final Object[] EMPTY_ARRAY = new Object[0];
private class ArrayIterator implements Iterator {
int itVersion = version;
int pos = 0; // position of next item to return
boolean hasNext = values.length > 0;
boolean removeOk = false;
public boolean hasNext() {
return hasNext;
}
public Object next() {
if(itVersion != version) {
throw new ConcurrentModificationException();
} else if(!hasNext) {
throw new NoSuchElementException();
} else {
Object ret = values[pos];
++pos;
hasNext = pos < values.length;
removeOk = true;
return ret;
}
}
public void remove() {
if(itVersion != version) {
throw new ConcurrentModificationException();
} else if(!removeOk) {
throw new IllegalStateException();
} else if(values.length == 1) {
values = EMPTY_ARRAY;
++version;
itVersion = version;
removeOk = false;
} else {
Object[] newValues = new Object[values.length - 1];
if(pos > 1) {
System.arraycopy(values, 0, newValues, 0, pos - 1);
}
if(pos < values.length) {
System.arraycopy(values, pos, newValues, pos - 1, values.length - pos);
}
values = newValues;
--pos;
++version;
itVersion = version;
removeOk = false;
}
}
}
private int version = 0;
private Object[] values = EMPTY_ARRAY;
public ArraySet() { }
public Object[] toArray() {
return values;
}
public Object clone() {
ArraySet ret = new ArraySet();
if(this.values == EMPTY_ARRAY) {
ret.values = EMPTY_ARRAY;
} else {
ret.values = (Object[]) this.values.clone();
}
return ret;
}
public void clear() {
values = EMPTY_ARRAY;
++version;
}
public boolean isEmpty() {
return values.length == 0;
}
public int size() {
return values.length;
}
public boolean add(Object value) {
int n = values.length;
for(int i = 0; i < n; i++) {
if(values[i].equals(value)) return false;
}
Object[] newValues = new Object[n + 1];
System.arraycopy(values, 0, newValues, 0, n);
newValues[n] = value;
values = newValues;
++version;
return true;
}
public boolean contains(Object value) {
for(int i = 0, n = values.length; i < n; i++) {
if(values[i].equals(value)) return true;
}
return false;
}
public Iterator iterator() {
return new ArrayIterator();
}
public static void main(String[] args) throws java.io.IOException {
ArraySet set = new ArraySet();
java.io.BufferedReader in = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
while(true) {
System.out.print(set.size() + ":"); //OK
for(Iterator it = set.iterator(); it.hasNext(); ) {
System.out.print(" " + it.next()); //OK
}
System.out.println(); //OK
System.out.print("> "); //OK
String cmd = in.readLine();
if(cmd == null) break;
cmd = cmd.trim();
if(cmd.equals("")) {
;
} else if(cmd.startsWith("+")) {
set.add(cmd.substring(1));
} else if(cmd.startsWith("-")) {
set.remove(cmd.substring(1));
} else if(cmd.startsWith("?")) {
boolean ret = set.contains(cmd.substring(1));
System.out.println(" " + ret); //OK
} else {
System.out.println("unrecognized command"); //OK
}
}
}
}
Convert an Array to a List
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) {
String[] cars = {"A", "B", "C", "D"};
List<String> carList = Arrays.asList(cars);
for (String car : carList) {
System.out.println(car);
}
}
}
Convert an array to a Map
import java.util.Map;
import org.apache.rumons.lang.ArrayUtils;
public class Main {
public static void main(String[] args) {
String[][] countries = { { "United States", "New York" }, { "United Kingdom", "London" },
{ "Netherland", "Amsterdam" }, { "Japan", "Tokyo" }, { "France", "Paris" } };
Map countryCapitals = ArrayUtils.toMap(countries);
System.out.println("Capital of Japan is " + countryCapitals.get("Japan"));
System.out.println("Capital of France is " + countryCapitals.get("France"));
}
}
Converting a Collection of String to an Array
import java.util.ArrayList;
import java.util.Collection;
public class PlanetSet {
public static void main(String args[]) {
String names[] = { "Mercury", "Venus", "Earth", "Mars", "Jupiter",
"Saturn", "Uranus", "Neptune", "Pluto" };
Collection planets = new ArrayList();
for (int i = 0, n = names.length; i < n; i++) {
planets.add(names[i]);
}
String s[] = (String[]) planets.toArray(new String[0]);
for (int i = 0, n = s.length; i < n; i++) {
System.out.println(s[i]);
}
planets.remove(names[3]);
System.out.println(names[1] + " " + planets.contains(names[1]));
System.out.println(names[3] + " " + planets.contains(names[3]));
}
}
Converting a Collection of user objects to an Array
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] argv) throws Exception {
List list = new ArrayList();
Object[] objectArray = list.toArray();
MyClass[] array = (MyClass[]) list.toArray(new MyClass[list.size()]);
}
}
class MyClass {
}
Converting an Array to a Collection
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] argv) throws Exception {
int[] array = new int[10];
// Fixed-size list
List list = Arrays.asList(array);
}
}
Converts array into a java.util.Map.
import java.util.HashMap;
import java.util.Map;
/*
* 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.
*
*
*/
/**
* @author Stephen Colebourne
* @author Moritz Petersen
* @author
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/
public class Main {
// To map
//-----------------------------------------------------------------------
/**
* <p>Converts the given array into a {@link java.util.Map}. Each element of the array
* must be either a {@link java.util.Map.Entry} or an Array, containing at least two
* elements, where the first element is used as key and the second as
* value.</p>
*
* <p>This method can be used to initialize:</p>
* <pre>
* // Create a Map mapping colors.
* Map colorMap = MapUtils.toMap(new String[][] {{
* {"RED", "#FF0000"},
* {"GREEN", "#00FF00"},
* {"BLUE", "#0000FF"}});
* </pre>
*
* <p>This method returns <code>null</code> for a <code>null</code> input array.</p>
*
* @param array an array whose elements are either a {@link java.util.Map.Entry} or
* an Array containing at least two elements, may be <code>null</code>
* @return a <code>Map</code> that was created from the array
* @throws IllegalArgumentException if one element of this Array is
* itself an Array containing less then two elements
* @throws IllegalArgumentException if the array contains elements other
* than {@link java.util.Map.Entry} and an Array
*/
public static Map toMap(Object[] array) {
if (array == null) {
return null;
}
final Map map = new HashMap((int) (array.length * 1.5));
for (int i = 0; i < array.length; i++) {
Object object = array[i];
if (object instanceof Map.Entry) {
Map.Entry entry = (Map.Entry) object;
map.put(entry.getKey(), entry.getValue());
} else if (object instanceof Object[]) {
Object[] entry = (Object[]) object;
if (entry.length < 2) {
throw new IllegalArgumentException("Array element " + i + ", ""
+ object
+ "", has a length less than 2");
}
map.put(entry[0], entry[1]);
} else {
throw new IllegalArgumentException("Array element " + i + ", ""
+ object
+ "", is neither of type Map.Entry nor an Array");
}
}
return map;
}
}
Custom ArrayMap implementation (extends AbstractMap)
import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class ArrayMap extends AbstractMap implements Cloneable, Serializable {
static class Entry implements Map.Entry {
protected Object key, value;
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
}
public Object getKey() {
return key;
}
public Object getValue() {
return value;
}
public Object setValue(Object newValue) {
Object oldValue = value;
value = newValue;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry e = (Map.Entry) o;
return (key == null ? e.getKey() == null : key.equals(e.getKey()))
&& (value == null ? e.getValue() == null : value.equals(e
.getValue()));
}
public int hashCode() {
int keyHash = (key == null ? 0 : key.hashCode());
int valueHash = (value == null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
private Set entries = null;
private ArrayList list;
public ArrayMap() {
list = new ArrayList();
}
public ArrayMap(Map map) {
list = new ArrayList();
putAll(map);
}
public ArrayMap(int initialCapacity) {
list = new ArrayList(initialCapacity);
}
public Set entrySet() {
if (entries == null) {
entries = new AbstractSet() {
public void clear() {
list.clear();
}
public Iterator iterator() {
return list.iterator();
}
public int size() {
return list.size();
}
};
}
return entries;
}
public Object put(Object key, Object value) {
int size = list.size();
Entry entry = null;
int i;
if (key == null) {
for (i = 0; i < size; i++) {
entry = (Entry) (list.get(i));
if (entry.getKey() == null) {
break;
}
}
} else {
for (i = 0; i < size; i++) {
entry = (Entry) (list.get(i));
if (key.equals(entry.getKey())) {
break;
}
}
}
Object oldValue = null;
if (i < size) {
oldValue = entry.getValue();
entry.setValue(value);
} else {
list.add(new Entry(key, value));
}
return oldValue;
}
public Object clone() {
return new ArrayMap(this);
}
public static void main(String args[]) {
Map map = new ArrayMap(13);
map.put("1", "One");
map.put("2", "Two");
map.put("3", "Three");
map.put("4", "Four");
map.put("5", "Five");
map.put("6", "Six");
map.put("7", "Seven");
map.put("8", "Eight");
map.put("9", "Nine");
map.put("10", "Ten");
map.put("11", "Eleven");
map.put("12", "Twelve");
map.put("13", "Thirteen");
System.out.println(map);
System.out.println(map.keySet());
System.out.println(map.values());
}
}
Custom ArraySet implementation (extends AbstractSet)
import java.io.Serializable;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
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();
}
}
public static void main(String args[]) {
String elements[] = { "Java", "Source", "and",
"Support", "." };
Set set = new ArraySet(Arrays.asList(elements));
Iterator iter = set.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}
Remove duplicate element from array
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
public static void main(String[] args) {
// A string array with duplicate values
String[] data = { "A", "C", "B", "D", "A", "B", "E", "D", "B", "C" };
System.out.println("Original array : " + Arrays.toString(data));
List<String> list = Arrays.asList(data);
Set<String> set = new HashSet<String>(list);
System.out.print("Remove duplicate result: ");
String[] result = new String[set.size()];
set.toArray(result);
for (String s : result) {
System.out.print(s + ", ");
}
}
}
Treating an Array as an Enumeration
import java.lang.reflect.Array;
import java.util.Enumeration;
final public class ArrayEnumerationFactory {
static public Enumeration makeEnumeration(final Object obj) {
Class type = obj.getClass();
if (!type.isArray()) {
throw new IllegalArgumentException(obj.getClass().toString());
} else {
return (new Enumeration() {
int size = Array.getLength(obj);
int cursor;
public boolean hasMoreElements() {
return (cursor < size);
}
public Object nextElement() {
return Array.get(obj, cursor++);
}
});
}
}
public static void main(String args[]) {
Enumeration e = makeEnumeration(args);
while (e.hasMoreElements()) {
System.out.println(e.nextElement());
}
e = makeEnumeration(new int[] { 1, 3, 4, 5 });
while (e.hasMoreElements()) {
System.out.println(e.nextElement());
}
try {
e = makeEnumeration(new Double(Math.PI));
} catch (IllegalArgumentException ex) {
System.err.println("Can"t enumerate that: " + ex.getMessage());
}
}
}
