[prev in list] [next in list] [prev in thread] [next in thread]
List: jibx-cvs
Subject: [Jibx-cvs] core/build/src/org/jibx/runtime/impl ArrayRangeIterator.java,NONE,1.1 SparseArrayIterator
From: Dennis Sosnoski <dsosnoski () users ! sourceforge ! net>
Date: 2005-06-24 20:03:42
Message-ID: E1DluOs-0006sb-O4 () sc8-pr-cvs1 ! sourceforge ! net
[Download RAW message or body]
Update of /cvsroot/jibx/core/build/src/org/jibx/runtime/impl
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26403/build/src/org/jibx/runtime/impl
Added Files:
ArrayRangeIterator.java SparseArrayIterator.java
StringIntHashMap.java
Log Message:
Add classes used by binding factory code for class to index lookup.
--- NEW FILE: SparseArrayIterator.java ---
/*
* Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
* IN THE SOFTWARE.
*/
package org.jibx.runtime.impl;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* Iterator class for sparse values in an array. This type of iterator
* can be used for an object array which has references interspersed with
* <code>null</code>s.
*
* @author Dennis M. Sosnoski
* @version 1.1
*/
public class SparseArrayIterator implements Iterator
{
/** Array supplying values for iteration. */
protected Object[] m_array;
/** Offset of next iteration value. */
protected int m_offset;
/**
* Internal constructor.
*
* @param array array containing values to be iterated
*/
private SparseArrayIterator(Object[] array) {
m_array = array;
m_offset = -1;
advance();
}
/**
* Advance to next iteration value. This advances the current position in
* the array to the next non-<code>null</code> value.
*
* @return <code>true</code> if element available, <code>false</code> if
* not
*/
protected boolean advance() {
while (++m_offset < m_array.length) {
if (m_array[m_offset] != null) {
return true;
}
}
return false;
}
/**
* Check for iteration element available.
*
* @return <code>true</code> if element available, <code>false</code> if
* not
*/
public boolean hasNext() {
return m_offset < m_array.length;
}
/**
* Get next iteration element.
*
* @return next iteration element
* @exception NoSuchElementException if past end of iteration
*/
public Object next() {
if (m_offset < m_array.length) {
Object result = m_array[m_offset];
advance();
return result;
} else {
throw new NoSuchElementException();
}
}
/**
* Remove element from iteration. This optional operation is not supported
* and always throws an exception.
*
* @exception UnsupportedOperationException for unsupported operation
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Build iterator.
*
* @param array array containing values to be iterated (may be
* <code>null</code>)
* @return constructed iterator
*/
public static Iterator buildIterator(Object[] array) {
if (array == null || array.length == 0) {
return ArrayRangeIterator.EMPTY_ITERATOR;
} else {
return new SparseArrayIterator(array);
}
}
}
--- NEW FILE: StringIntHashMap.java ---
/*
* Copyright (c) 2000-2005, 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.
*/
package org.jibx.runtime.impl;
/**
* Hash map using <code>String</code> values as keys mapped to primitive
* <code>int</code> values. This implementation is unsynchronized in order to
* provide the best possible performance for typical usage scenarios, so
* explicit synchronization must be implemented by a wrapper class or directly
* by the application in cases where instances are modified in a multithreaded
* environment. The map implementation is not very efficient when resizing, but
* works well when the size of the map is known in advance.
*
* @author Dennis M. Sosnoski
* @version 1.1
*/
public class StringIntHashMap
{
/** Default value returned when key not found in table. */
public static final int DEFAULT_NOT_FOUND = Integer.MIN_VALUE;
/** Default fill fraction allowed before growing table. */
protected static final double DEFAULT_FILL = 0.3d;
/** Minimum size used for hash table. */
protected static final int MINIMUM_SIZE = 31;
/** Fill fraction allowed for this hash table. */
protected final double m_fillFraction;
/** Number of entries present in table. */
protected int m_entryCount;
/** Entries allowed before growing table. */
protected int m_entryLimit;
/** Size of array used for keys. */
protected int m_arraySize;
/** Offset added (modulo table size) to slot number on collision. */
protected int m_hitOffset;
/** Array of key table slots. */
protected String[] m_keyTable;
/** Array of value table slots. */
protected int[] m_valueTable;
/** Value returned when key not found in table. */
protected int m_notFoundValue;
/**
* Constructor with full specification.
*
* @param count number of values to assume in initial sizing of table
* @param fill fraction full allowed for table before growing
* @param miss value returned when key not found in table
*/
public StringIntHashMap(int count, double fill, int miss) {
// check the passed in fill fraction
if (fill <= 0.0d || fill >= 1.0d) {
throw new IllegalArgumentException("fill value out of range");
}
m_fillFraction = fill;
// compute initial table size (ensuring odd)
m_arraySize = Math.max((int)(count / m_fillFraction), MINIMUM_SIZE);
m_arraySize += (m_arraySize + 1) % 2;
// initialize the table information
m_entryLimit = (int)(m_arraySize * m_fillFraction);
m_hitOffset = m_arraySize / 2;
m_keyTable = new String[m_arraySize];
m_valueTable = new int[m_arraySize];
m_notFoundValue = miss;
}
/**
* Constructor with size and fill fraction specified. Uses default hash
* technique and value returned when key not found in table.
*
* @param count number of values to assume in initial sizing of table
* @param fill fraction full allowed for table before growing
*/
public StringIntHashMap(int count, double fill) {
this(count, fill, DEFAULT_NOT_FOUND);
}
/**
* Constructor with only size supplied. Uses default hash technique and
* values for fill fraction and value returned when key not found in table.
*
* @param count number of values to assume in initial sizing of table
*/
public StringIntHashMap(int count) {
this(count, DEFAULT_FILL);
}
/**
* Default constructor.
*/
public StringIntHashMap() {
this(0, DEFAULT_FILL);
}
/**
* Copy (clone) constructor.
*
* @param base instance being copied
*/
public StringIntHashMap(StringIntHashMap base) {
// copy the basic occupancy information
m_fillFraction = base.m_fillFraction;
m_entryCount = base.m_entryCount;
m_entryLimit = base.m_entryLimit;
m_arraySize = base.m_arraySize;
m_hitOffset = base.m_hitOffset;
m_notFoundValue = base.m_notFoundValue;
// copy table of items
m_keyTable = new String[m_arraySize];
System.arraycopy(base.m_keyTable, 0, m_keyTable, 0, m_arraySize);
m_valueTable = new int[m_arraySize];
System.arraycopy(base.m_valueTable, 0, m_valueTable, 0, m_arraySize);
}
/**
* Step the slot number for an entry. Adds the collision offset (modulo
* the table size) to the slot number.
*
* @param slot slot number to be stepped
* @return stepped slot number
*/
private final int stepSlot(int slot) {
return (slot + m_hitOffset) % m_arraySize;
}
/**
* Find free slot number for entry. Starts at the slot based directly
* on the hashed key value. If this slot is already occupied, it adds
* the collision offset (modulo the table size) to the slot number and
* checks that slot, repeating until an unused slot is found.
*
* @param slot initial slot computed from key
* @return slot at which entry was added
*/
private final int freeSlot(int slot) {
while (m_keyTable[slot] != null) {
slot = stepSlot(slot);
}
return slot;
}
/**
* Standard base slot computation for a key.
*
* @param key key value to be computed
* @return base slot for key
*/
private final int standardSlot(Object key) {
return (key.hashCode() & Integer.MAX_VALUE) % m_arraySize;
}
/**
* Standard find key in table. This method may be used directly for key
* lookup using either the <code>hashCode()</code> method defined for the
* key objects or the <code>System.identityHashCode()</code> method, and
* either the <code>equals()</code> method defined for the key objects or
* the <code>==</code> operator, as selected by the hash technique
* constructor parameter. To implement a hash class based on some other
* methods of hashing and/or equality testing, define a separate method in
* the subclass with a different name and use that method instead. This
* avoids the overhead caused by overrides of a very heavily used method.
*
* @param key to be found in table
* @return index of matching key, or <code>-index-1</code> of slot to be
* used for inserting key in table if not already present (always negative)
*/
private int standardFind(Object key) {
// find the starting point for searching table
int slot = standardSlot(key);
// scan through table to find target key
while (m_keyTable[slot] != null) {
// check if we have a match on target key
if (m_keyTable[slot].equals(key)) {
return slot;
} else {
slot = stepSlot(slot);
}
}
return -slot-1;
}
/**
* Reinsert an entry into the hash map. This is used when the table is being
* directly modified, and does not adjust the count present or check the
* table capacity.
*
* @param slot position of entry to be reinserted into hash map
* @return <code>true</code> if the slot number used by the entry has has
* changed, <code>false</code> if not
*/
private boolean reinsert(int slot) {
String key = m_keyTable[slot];
m_keyTable[slot] = null;
return assignSlot(key, m_valueTable[slot]) != slot;
}
/**
* Internal remove pair from the table. Removes the pair from the table
* by setting the key entry to <code>null</code> and adjusting the count
* present, then chains through the table to reinsert any other pairs
* which may have collided with the removed pair. If the associated value
* is an object reference, it should be set to <code>null</code> before
* this method is called.
*
* @param slot index number of pair to be removed
*/
protected void internalRemove(int slot) {
// delete pair from table
m_keyTable[slot] = null;
m_entryCount--;
while (m_keyTable[(slot = stepSlot(slot))] != null) {
// reinsert current entry in table to fill holes
reinsert(slot);
}
}
/**
* Restructure the table. This is used when the table is increasing or
* decreasing in size, and works directly with the old table representation
* arrays. It inserts pairs from the old arrays directly into the table
* without adjusting the count present or checking the table size.
*
* @param keys array of keys
* @param values array of values
*/
private void restructure(String[] keys, int[] values) {
for (int i = 0; i < keys.length; i++) {
if (keys[i] != null) {
assignSlot(keys[i], values[i]);
}
}
}
/**
* Assign slot for entry. Starts at the slot found by the hashed key value.
* If this slot is already occupied, it steps the slot number and checks the
* resulting slot, repeating until an unused slot is found. This method does
* not check for duplicate keys, so it should only be used for internal
* reordering of the tables.
*
* @param key to be added to table
* @param value associated value for key
* @return slot at which entry was added
*/
private int assignSlot(String key, int value) {
int offset = freeSlot(standardSlot(key));
m_keyTable[offset] = key;
m_valueTable[offset] = value;
return offset;
}
/**
* Add an entry to the table. If the key is already present in the table,
* this replaces the existing value associated with the key.
*
* @param key key to be added to table (non- <code>null</code>)
* @param value associated value for key
* @return value previously associated with key, or reserved not found value
* if key not previously present in table
*/
public int add(String key, int value) {
// first validate the parameters
if (key == null) {
throw new IllegalArgumentException("null key not supported");
} else if (value == m_notFoundValue) {
throw new IllegalArgumentException(
"value matching not found return not supported");
} else {
// check space available
int min = m_entryCount + 1;
if (min > m_entryLimit) {
// find the array size required
int size = m_arraySize;
int limit = m_entryLimit;
while (limit < min) {
size = size * 2 + 1;
limit = (int) (size * m_fillFraction);
}
// set parameters for new array size
m_arraySize = size;
m_entryLimit = limit;
m_hitOffset = size / 2;
// restructure for larger arrays
String[] keys = m_keyTable;
m_keyTable = new String[m_arraySize];
int[] values = m_valueTable;
m_valueTable = new int[m_arraySize];
restructure(keys, values);
}
// find slot of table
int offset = standardFind(key);
if (offset >= 0) {
// replace existing value for key
int prior = m_valueTable[offset];
m_valueTable[offset] = value;
return prior;
} else {
// add new pair to table
m_entryCount++;
offset = -offset - 1;
m_keyTable[offset] = key;
m_valueTable[offset] = value;
return m_notFoundValue;
}
}
}
/**
* Check if an entry is present in the table. This method is supplied to
* support the use of values matching the reserved not found value.
*
* @param key key for entry to be found
* @return <code>true</code> if key found in table, <code>false</code>
* if not
*/
public final boolean containsKey(String key) {
return standardFind(key) >= 0;
}
/**
* Find an entry in the table.
*
* @param key key for entry to be returned
* @return value for key, or reserved not found value if key not found
*/
public final int get(String key) {
int slot = standardFind(key);
if (slot >= 0) {
return m_valueTable[slot];
} else {
return m_notFoundValue;
}
}
/**
* Remove an entry from the table. If multiple entries are present with the
* same key value, only the first one found will be removed.
*
* @param key key to be removed from table
* @return value associated with removed key, or reserved not found value if
* key not found in table
*/
public int remove(String key) {
int slot = standardFind(key);
if (slot >= 0) {
int value = m_valueTable[slot];
internalRemove(slot);
return value;
} else {
return m_notFoundValue;
}
}
/**
* Construct a copy of the table.
*
* @return shallow copy of table
*/
public Object clone() {
return new StringIntHashMap(this);
}
}
--- NEW FILE: ArrayRangeIterator.java ---
/*
Copyright (c) 2000-2005, 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.
*/
package org.jibx.runtime.impl;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* Iterator class for values contained in an array range. This type of iterator
* can be used for any contiguous range of items in an object array.
*
* @author Dennis M. Sosnoski
* @version 1.1
*/
public class ArrayRangeIterator implements Iterator
{
/** Empty iterator used whenever possible. */
public static final ArrayRangeIterator EMPTY_ITERATOR =
new ArrayRangeIterator(null, 0, 0);
/** Array supplying values for iteration. */
protected Object[] m_array;
/** Offset of next iteration value. */
protected int m_offset;
/** Ending offset for values. */
protected int m_limit;
/**
* Internal constructor.
*
* @param array array containing values to be iterated
* @param start starting offset in array
* @param limit offset past end of values
*/
private ArrayRangeIterator(Object[] array, int start, int limit) {
m_array = array;
m_offset = start;
m_limit = limit;
}
/**
* Check for iteration element available.
*
* @return <code>true</code> if element available, <code>false</code> if
* not
*/
public boolean hasNext() {
return m_offset < m_limit;
}
/**
* Get next iteration element.
*
* @return next iteration element
* @exception NoSuchElementException if past end of iteration
*/
public Object next() {
if (m_offset < m_limit) {
return m_array[m_offset++];
} else {
throw new NoSuchElementException();
}
}
/**
* Remove element from iteration. This optional operation is not supported
* and always throws an exception.
*
* @exception UnsupportedOperationException for unsupported operation
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Build iterator.
*
* @param array array containing values to be iterated (may be
* <code>null</code>)
* @param start starting offset in array
* @param limit offset past end of values
* @return constructed iterator
*/
public static Iterator buildIterator(Object[] array, int start, int limit) {
if (array == null || start >= limit) {
return EMPTY_ITERATOR;
} else {
return new ArrayRangeIterator(array, start, limit);
}
}
}
-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
_______________________________________________
Jibx-cvs mailing list
Jibx-cvs@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jibx-cvs
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic