Apache的commons的jar包和源码、文档

/* * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements. See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package org.apache.commons.collections4.trie; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.util.AbstractCollection; import java.util.AbstractMap; import java.util.AbstractSet; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; import java.util.SortedMap; import org.apache.commons.collections4.OrderedMapIterator; /** * This class implements the base PATRICIA algorithm and everything that * is related to the {@link Map} interface. * * @since 4.0 * @version $Id: AbstractPatriciaTrie.java 1543928 2013-11-20 20:15:35Z tn $ */ abstract class AbstractPatriciaTrie<K, V> extends AbstractBitwiseTrie<K, V> { private static final long serialVersionUID = 5155253417231339498L; /** The root node of the {@link Trie}. */ private transient TrieEntry<K, V> root = new TrieEntry<K, V>(null, null, -1); /** * Each of these fields are initialized to contain an instance of the * appropriate view the first time this view is requested. The views are * stateless, so there's no reason to create more than one of each. */ private transient volatile Set<K> keySet; private transient volatile Collection<V> values; private transient volatile Set<Map.Entry<K,V>> entrySet; /** The current size of the {@link Trie}. */ private transient int size = 0; /** * The number of times this {@link Trie} has been modified. * It's used to detect concurrent modifications and fail-fast the {@link Iterator}s. */ protected transient int modCount = 0; protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer) { super(keyAnalyzer); } /** * Constructs a new {@link org.apache.commons.collections4.Trie Trie} using the given * {@link KeyAnalyzer} and initializes the {@link org.apache.commons.collections4.Trie Trie} * with the values from the provided {@link Map}. */ protected AbstractPatriciaTrie(final KeyAnalyzer<? super K> keyAnalyzer, final Map<? extends K, ? extends V> map) { super(keyAnalyzer); putAll(map); } //----------------------------------------------------------------------- @Override public void clear() { root.key = null; root.bitIndex = -1; root.value = null; root.parent = null; root.left = root; root.right = null; root.predecessor = root; size = 0; incrementModCount(); } @Override public int size() { return size; } /** * A helper method to increment the {@link Trie} size and the modification counter. */ void incrementSize() { size++; incrementModCount(); } /** * A helper method to decrement the {@link Trie} size and increment the modification counter. */ void decrementSize() { size--; incrementModCount(); } /** * A helper method to increment the modification counter. */ private void incrementModCount() { ++modCount; } @Override public V put(final K key, final V value) { if (key == null) { throw new NullPointerException("Key cannot be null"); } final int lengthInBits = lengthInBits(key); // The only place to store a key with a length // of zero bits is the root node if (lengthInBits == 0) { if (root.isEmpty()) { incrementSize(); } else { incrementModCount(); } return root.setKeyValue(key, value); } final TrieEntry<K, V> found = getNearestEntryForKey(key, lengthInBits); if (compareKeys(key, found.key)) { if (found.isEmpty()) { // <- must be the root incrementSize(); } else { incrementModCount(); } return found.setKeyValue(key, value); } final int bitIndex = bitIndex(key, found.key); if (!KeyAnalyzer.isOutOfBoundsIndex(bitIndex)) { if (KeyAnalyzer.isValidBitIndex(bitIndex)) { // in 99.999...9% the case /* NEW KEY+VALUE TUPLE */ final TrieEntry<K, V> t = new TrieEntry<K, V>(key, value, bitIndex); addEntry(t, lengthInBits); incrementSize(); return null; } else if (KeyAnalyzer.isNullBitKey(bitIndex)) { // A bits of the Key are zero. The only place to // store such a Key is the root Node! /* NULL BIT KEY */ if (root.isEmpty()) { incrementSize(); } else { incrementModCount(); } return root.setKeyValue(key, value); } else if (KeyAnalyzer.isEqualBitKey(bitIndex)) { // This is a very special and rare case. /* REPLACE OLD KEY+VALUE */ if (found != root) { incrementModCount(); return found.setKeyValue(key, value); } } } throw new IllegalArgumentException("Failed to put: " + key + " -> " + value + ", " + bitIndex); } /** * Adds the given {@link TrieEntry} to the {@link Trie}. */ TrieEntry<K, V> addEntry(final TrieEntry<K, V> entry, final int lengthInBits) { TrieEntry<K, V> current = root.left; TrieEntry<K, V> path = root; while(true) { if (current.bitIndex >= entry.bitIndex || current.bitIndex <= path.bitIndex) { entry.predecessor = entry; if (!isBitSet(entry.key, entry.bitIndex, lengthInBits)) { entry.left = entry; entry.right = current; } else { entry.left = current; entry.right = entry; } entry.parent = path; if (current.bitIndex >= entry.bitIndex) { current.parent = entry; } // if we inserted an uplink, set the predecessor on it if (current.bitIndex <= path.bitIndex) { current.predecessor = entry; } if (path == root || !isBitSet(entry.key, path.bitIndex, lengthInBits)) { path.left = entry; } else { path.right = entry; } return entry; } path = current; if (!isBitSet(entry.key, current.bitIndex, lengthInBits)) { current = current.left; } else { current = current.right; } } } @Override public V get(final Object k) { final TrieEntry<K, V> entry = getEntry(k); return entry != null ? e