+++ /dev/null
-/*--------------------------------------------------------------------------\r
- * Copyright 2008 Taro L. Saito\r
- *\r
- * Licensed under the Apache License, Version 2.0 (the "License");\r
- * you may not use this file except in compliance with the License.\r
- * You may obtain a copy of the License at\r
- *\r
- * http://www.apache.org/licenses/LICENSE-2.0\r
- *\r
- * Unless required by applicable law or agreed to in writing, software\r
- * distributed under the License is distributed on an "AS IS" BASIS,\r
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
- * See the License for the specific language governing permissions and\r
- * limitations under the License.\r
- *--------------------------------------------------------------------------*/\r
-//--------------------------------------\r
-// XerialJ\r
-//\r
-// IndexedContainer.java\r
-// Since: 2008/11/08 11:32:29\r
-//\r
-// $URL$\r
-// $Author$\r
-//--------------------------------------\r
-package org.xerial.util;\r
-\r
-import java.util.ArrayList;\r
-import java.util.Collection;\r
-import java.util.HashMap;\r
-import java.util.Iterator;\r
-import java.util.Set;\r
-import java.util.TreeSet;\r
-\r
-/**\r
- * Set container, each element of which is assigned an unique ID in the set.\r
- * \r
- * @author leo\r
- * \r
- * @param <T>\r
- * element type to store\r
- */\r
-public class IndexedSet<T> implements Set<T>\r
-{\r
- public final static int INVALID_ID = -1;\r
- private int elementCount = 0;\r
- private HashMap<T, Integer> elementToID = new HashMap<T, Integer>();\r
- private ArrayList<T> elementArray = new ArrayList<T>();\r
-\r
- public Collection<Integer> getIDSet()\r
- {\r
- return elementToID.values();\r
- }\r
-\r
- public boolean containsID(int id)\r
- {\r
- return id < elementArray.size() && getByID(id) != null;\r
- }\r
-\r
- /**\r
- * get the element ID\r
- * \r
- * @param element\r
- * @return the element ID. if no corresponding element found in the set,\r
- * returns {@link IndexedSet#INVALID_ID}\r
- */\r
- public int getID(T element)\r
- {\r
- Integer id = elementToID.get(element);\r
- return (id == null) ? INVALID_ID : id;\r
- }\r
-\r
- /**\r
- * get the element ID. If the element is not present in the set, add the\r
- * element to the set and return the new element ID\r
- * \r
- * @param element\r
- * @return\r
- */\r
- public int getIDwithAddition(T element)\r
- {\r
- if (contains(element))\r
- return getID(element);\r
- else\r
- {\r
- return addNewElement(element);\r
- }\r
- }\r
-\r
- /**\r
- * Get the element using the element ID\r
- * \r
- * @param elementID\r
- * @return\r
- */\r
- public T getByID(int elementID)\r
- {\r
- return elementArray.get(elementID);\r
- }\r
-\r
- public T set(int id, T element)\r
- {\r
- T oldValue = elementArray.set(id, element); // range check occurs\r
- elementToID.put(element, id);\r
- return oldValue;\r
- }\r
-\r
- /**\r
- * Add an new element, and return the assigned element ID\r
- * \r
- * @param element\r
- * @return the new element ID\r
- */\r
- private int addNewElement(T element)\r
- {\r
- assert (!elementToID.containsKey(element));\r
-\r
- int newNodeID = elementCount++;\r
- elementToID.put(element, newNodeID);\r
- elementArray.add(element);\r
- return newNodeID;\r
- }\r
-\r
- public boolean add(T element)\r
- {\r
- if (elementToID.containsKey(element))\r
- {\r
- return false;\r
- }\r
- else\r
- {\r
- addNewElement(element);\r
- return true;\r
- }\r
- }\r
-\r
- public boolean addAll(Collection< ? extends T> elementCollection)\r
- {\r
- boolean collectionIsChanged = false;\r
- for (T each : elementCollection)\r
- {\r
- collectionIsChanged |= add(each);\r
- }\r
- return collectionIsChanged;\r
- }\r
-\r
- public void clear()\r
- {\r
- elementToID.clear();\r
- elementArray.clear();\r
- elementCount = 0;\r
-\r
- }\r
-\r
- public boolean contains(Object element)\r
- {\r
- return elementToID.containsKey(element);\r
- }\r
-\r
- public boolean containsAll(Collection< ? > elementList)\r
- {\r
- for (Object each : elementList)\r
- {\r
- if (!contains(each))\r
- return false;\r
- }\r
- return true;\r
- }\r
-\r
- public boolean isEmpty()\r
- {\r
- return elementToID.isEmpty();\r
- }\r
-\r
- public Iterator<T> iterator()\r
- {\r
- return new Iterator<T>() {\r
- int next = 0;\r
-\r
- public boolean hasNext()\r
- {\r
- return next < size();\r
- }\r
-\r
- public T next()\r
- {\r
- return getByID(next++);\r
- }\r
-\r
- public void remove()\r
- {\r
- throw new UnsupportedOperationException("remove");\r
- }\r
-\r
- };\r
- }\r
-\r
- @SuppressWarnings("unchecked")\r
- public boolean remove(Object element)\r
- {\r
- int id = getID((T) element);\r
- if (id == INVALID_ID)\r
- return false;\r
-\r
- elementToID.remove(element);\r
- elementArray.set(id, null);\r
- return true;\r
- }\r
-\r
- public boolean removeAll(Collection< ? > elementListToRemove)\r
- {\r
- boolean hasAnyChange = false;\r
- for (Object each : elementListToRemove)\r
- {\r
- hasAnyChange |= remove(each);\r
- }\r
- return hasAnyChange;\r
- }\r
-\r
- public boolean retainAll(Collection< ? > elementsToRetain)\r
- {\r
- throw new UnsupportedOperationException("retainAll");\r
- }\r
-\r
- public int size()\r
- {\r
- return elementToID.size();\r
- }\r
-\r
- public Object[] toArray()\r
- {\r
- return elementToID.keySet().toArray();\r
- }\r
-\r
- @SuppressWarnings("hiding")\r
- public <T> T[] toArray(T[] array)\r
- {\r
- return elementToID.keySet().toArray(array);\r
- }\r
-\r
- @Override\r
- public String toString()\r
- {\r
- ArrayList<String> elementList = new ArrayList<String>();\r
- TreeSet<Integer> sortedIDSet = new TreeSet<Integer>(getIDSet());\r
- for (int elementID : sortedIDSet)\r
- {\r
- elementList.add(String.format("%d:%s", elementID, getByID(elementID)));\r
- }\r
-\r
- return String.format("{%s}", StringUtil.join(elementList, ", "));\r
- }\r
-\r
-}\r