/*
* Copyright (C) 2002-2014 Sebastiano Vigna
*
* 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.
*/
package PACKAGE;
import it.unimi.dsi.fastutil.objects.ObjectSortedSet;
import it.unimi.dsi.fastutil.objects.ObjectSortedSets;
import java.util.Comparator;
import java.util.Map;
import java.util.SortedMap;
import java.util.NoSuchElementException;
/** A class providing static methods and objects that do useful things with type-specific sorted maps.
*
* @see java.util.Collections
*/
public class SORTED_MAPS {
private SORTED_MAPS() {}
/** Returns a comparator for entries based on a given comparator on keys.
*
* @param comparator a comparator on keys.
* @return the associated comparator on entries.
*/
public static KEY_GENERIC Comparator<? super Map.Entry<KEY_GENERIC_CLASS, ?>> entryComparator( final KEY_COMPARATOR KEY_GENERIC comparator ) {
return new Comparator<Map.Entry<KEY_GENERIC_CLASS, ?>>() {
public int compare( Map.Entry<KEY_GENERIC_CLASS, ?> x, Map.Entry<KEY_GENERIC_CLASS, ?> y ) {
return comparator.compare( x.getKey(), y.getKey() );
}
};
}
/** An immutable class representing an empty type-specific sorted map.
*
* <P>This class may be useful to implement your own in case you subclass
* a type-specific sorted map.
*/
public static class EmptySortedMap KEY_VALUE_GENERIC extends MAPS.EmptyMap KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable, Cloneable {
private static final long serialVersionUID = -7046029254386353129L;
protected EmptySortedMap() {}
public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { return null; }
@SuppressWarnings("unchecked")
public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { return ObjectSortedSets.EMPTY_SET; }
@SuppressWarnings("unchecked")
public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return ObjectSortedSets.EMPTY_SET; }
SUPPRESS_WARNINGS_KEY_UNCHECKED
public SORTED_SET KEY_GENERIC keySet() { return SORTED_SETS.EMPTY_SET; }
SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
public SORTED_MAP KEY_VALUE_GENERIC subMap( final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to ) { return EMPTY_MAP; }
SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
public SORTED_MAP KEY_VALUE_GENERIC headMap( final KEY_GENERIC_TYPE to ) { return EMPTY_MAP; }
SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
public SORTED_MAP KEY_VALUE_GENERIC tailMap( final KEY_GENERIC_TYPE from ) { return EMPTY_MAP; }
public KEY_GENERIC_TYPE FIRST_KEY() { throw new NoSuchElementException(); }
public KEY_GENERIC_TYPE LAST_KEY() { throw new NoSuchElementException(); }
#if #keys(primitive)
public SORTED_MAP KEY_VALUE_GENERIC headMap( KEY_GENERIC_CLASS oto ) { return headMap( KEY_CLASS2TYPE( oto ) ); }
public SORTED_MAP KEY_VALUE_GENERIC tailMap( KEY_GENERIC_CLASS ofrom ) { return tailMap( KEY_CLASS2TYPE( ofrom ) ); }
public SORTED_MAP KEY_VALUE_GENERIC subMap( KEY_GENERIC_CLASS ofrom, KEY_GENERIC_CLASS oto ) { return subMap( KEY_CLASS2TYPE( ofrom ), KEY_CLASS2TYPE( oto ) ); }
public KEY_GENERIC_CLASS firstKey() { return KEY2OBJ( FIRST_KEY() ); }
public KEY_GENERIC_CLASS lastKey() { return KEY2OBJ( LAST_KEY() ); }
#endif
}
/** An empty type-specific sorted map (immutable). It is serializable and cloneable. */
SUPPRESS_WARNINGS_KEY_VALUE_RAWTYPES
public static final EmptySortedMap EMPTY_MAP = new EmptySortedMap();
/** An immutable class representing a type-specific singleton sorted map.
*
* <P>This class may be useful to implement your own in case you subclass
* a type-specific sorted map.
*/
public static class Singleton KEY_VALUE_GENERIC extends MAPS.Singleton KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable, Cloneable {
private static final long serialVersionUID = -7046029254386353129L;
protected final KEY_COMPARATOR KEY_SUPER_GENERIC comparator;
protected Singleton( final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value, KEY_COMPARATOR KEY_SUPER_GENERIC comparator ) {
super( key, value );
this.comparator = comparator;
}
protected Singleton( final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value ) {
this( key, value, null );
}
SUPPRESS_WARNINGS_KEY_UNCHECKED
final int compare( final KEY_GENERIC_TYPE k1, final KEY_GENERIC_TYPE k2 ) {
return comparator == null ? KEY_CMP( k1, k2 ) : comparator.compare( k1, k2 );
}
public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { return comparator; }
SUPPRESS_WARNINGS_KEY_UNCHECKED
public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { if ( entries == null ) entries = ObjectSortedSets.singleton( (MAP.Entry KEY_VALUE_GENERIC)new SingletonEntry(), (Comparator<? super MAP.Entry KEY_VALUE_GENERIC>)entryComparator( comparator ) ); return (ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>)entries; }
@SuppressWarnings({ "rawtypes", "unchecked" })
public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return (ObjectSortedSet)ENTRYSET(); }
public SORTED_SET KEY_GENERIC keySet() { if ( keys == null ) keys = SORTED_SETS.singleton( key, comparator ); return (SORTED_SET KEY_GENERIC)keys; }
SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
public SORTED_MAP KEY_VALUE_GENERIC subMap( final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to ) { if ( compare( from, key ) <= 0 && compare( key, to ) < 0 ) return this; return EMPTY_MAP; }
SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
public SORTED_MAP KEY_VALUE_GENERIC headMap( final KEY_GENERIC_TYPE to ) { if ( compare( key, to ) < 0 ) return this; return EMPTY_MAP; }
SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
public SORTED_MAP KEY_VALUE_GENERIC tailMap( final KEY_GENERIC_TYPE from ) { if ( compare( from, key ) <= 0 ) return this; return EMPTY_MAP; }
public KEY_GENERIC_TYPE FIRST_KEY() { return key; }
public KEY_GENERIC_TYPE LAST_KEY() { return key; }
#if #keys(primitive)
public SORTED_MAP KEY_VALUE_GENERIC headMap( KEY_GENERIC_CLASS oto ) { return headMap( KEY_CLASS2TYPE( oto ) ); }
public SORTED_MAP KEY_VALUE_GENERIC tailMap( KEY_GENERIC_CLASS ofrom ) { return tailMap( KEY_CLASS2TYPE( ofrom ) ); }
public SORTED_MAP KEY_VALUE_GENERIC subMap( KEY_GENERIC_CLASS ofrom, KEY_GENERIC_CLASS oto ) { return subMap( KEY_CLASS2TYPE( ofrom ), KEY_CLASS2TYPE( oto ) ); }
public KEY_GENERIC_CLASS firstKey() { return KEY2OBJ( FIRST_KEY() ); }
public KEY_GENERIC_CLASS lastKey() { return KEY2OBJ( LAST_KEY() ); }
#endif
}
/** Returns a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
*
* <P>Note that albeit the returned map is immutable, its default return value may be changed.
*
* @param key the only key of the returned sorted map.
* @param value the only value of the returned sorted map.
* @return a type-specific immutable sorted map containing just the pair <code><key,value></code>.
*/
public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton( final KEY_GENERIC_CLASS key, VALUE_GENERIC_CLASS value ) {
return new Singleton KEY_VALUE_GENERIC( KEY_CLASS2TYPE( key ), VALUE_CLASS2TYPE( value ) );
}
/** RETURNS a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
*
* <P>Note that albeit the returned map is immutable, its default return value may be changed.
*
* @param key the only key of the returned sorted map.
* @param value the only value of the returned sorted map.
* @param comparator the comparator to use in the returned sorted map.
* @return a type-specific immutable sorted map containing just the pair <code><key,value></code>.
*/
public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton( final KEY_GENERIC_CLASS key, VALUE_GENERIC_CLASS value, KEY_COMPARATOR KEY_SUPER_GENERIC comparator ) {
return new Singleton KEY_VALUE_GENERIC( KEY_CLASS2TYPE( key ), VALUE_CLASS2TYPE( value ), comparator );
}
#if #keys(primitive) || #values(primitive)
/** Returns a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
*
* <P>Note that albeit the returned map is immutable, its default return value may be changed.
*
* @param key the only key of the returned sorted map.
* @param value the only value of the returned sorted map.
* @return a type-specific immutable sorted map containing just the pair <code><key,value></code>.
*/
public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton( final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value ) {
return new Singleton KEY_VALUE_GENERIC( key, value );
}
/** Returns a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
*
* <P>Note that albeit the returned map is immutable, its default return value may be changed.
*
* @param key the only key of the returned sorted map.
* @param value the only value of the returned sorted map.
* @param comparator the comparator to use in the returned sorted map.
* @return a type-specific immutable sorted map containing just the pair <code><key,value></code>.
*/
public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton( final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value, KEY_COMPARATOR KEY_SUPER_GENERIC comparator ) {
return new Singleton KEY_VALUE_GENERIC( key, value, comparator );
}
#endif
/** A synchronized wrapper class for sorted maps. */
public static class SynchronizedSortedMap KEY_VALUE_GENERIC extends MAPS.SynchronizedMap KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable {
private static final long serialVersionUID = -7046029254386353129L;
protected final SORTED_MAP KEY_VALUE_GENERIC sortedMap;
protected SynchronizedSortedMap( final SORTED_MAP KEY_VALUE_GENERIC m, final Object sync ) {
super( m, sync );
sortedMap = m;
}
protected SynchronizedSortedMap( final SORTED_MAP KEY_VALUE_GENERIC m ) {
super( m );
sortedMap = m;
}
public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { synchronized( sync ) { return sortedMap.comparator(); } }
public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { if ( entries == null ) entries = ObjectSortedSets.synchronize( sortedMap.ENTRYSET(), sync ); return (ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>)entries; }
@SuppressWarnings({ "rawtypes", "unchecked" })
public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return (ObjectSortedSet)ENTRYSET(); }
public SORTED_SET KEY_GENERIC keySet() { if ( keys == null ) keys = SORTED_SETS.synchronize( sortedMap.keySet(), sync ); return (SORTED_SET KEY_GENERIC)keys; }
public SORTED_MAP KEY_VALUE_GENERIC subMap( final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( sortedMap.subMap( from, to ), sync ); }
public SORTED_MAP KEY_VALUE_GENERIC headMap( final KEY_GENERIC_TYPE to ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( sortedMap.headMap( to ), sync ); }
public SORTED_MAP KEY_VALUE_GENERIC tailMap( final KEY_GENERIC_TYPE from ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( sortedMap.tailMap( from ), sync ); }
public KEY_GENERIC_TYPE FIRST_KEY() { synchronized( sync ) { return sortedMap.FIRST_KEY(); } }
public KEY_GENERIC_TYPE LAST_KEY() { synchronized( sync ) { return sortedMap.LAST_KEY(); } }
#if #keys(primitive)
public KEY_GENERIC_CLASS firstKey() { synchronized( sync ) { return sortedMap.firstKey(); } }
public KEY_GENERIC_CLASS lastKey() { synchronized( sync ) { return sortedMap.lastKey(); } }
public SORTED_MAP KEY_VALUE_GENERIC subMap( final KEY_GENERIC_CLASS from, final KEY_GENERIC_CLASS to ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( sortedMap.subMap( from, to ), sync ); }
public SORTED_MAP KEY_VALUE_GENERIC headMap( final KEY_GENERIC_CLASS to ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( sortedMap.headMap( to ), sync ); }
public SORTED_MAP KEY_VALUE_GENERIC tailMap( final KEY_GENERIC_CLASS from ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( sortedMap.tailMap( from ), sync ); }
#endif
}
/** Returns a synchronized type-specific sorted map backed by the given type-specific sorted map.
*
* @param m the sorted map to be wrapped in a synchronized sorted map.
* @return a synchronized view of the specified sorted map.
* @see java.util.Collections#synchronizedSortedMap(SortedMap)
*/
public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC synchronize( final SORTED_MAP KEY_VALUE_GENERIC m ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( m ); }
/** Returns a synchronized type-specific sorted map backed by the given type-specific sorted map, using an assigned object to synchronize.
*
* @param m the sorted map to be wrapped in a synchronized sorted map.
* @param sync an object that will be used to synchronize the access to the sorted sorted map.
* @return a synchronized view of the specified sorted map.
* @see java.util.Collections#synchronizedSortedMap(SortedMap)
*/
public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC synchronize( final SORTED_MAP KEY_VALUE_GENERIC m, final Object sync ) { return new SynchronizedSortedMap KEY_VALUE_GENERIC( m, sync ); }
/** An unmodifiable wrapper class for sorted maps. */
public static class UnmodifiableSortedMap KEY_VALUE_GENERIC extends MAPS.UnmodifiableMap KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable {
private static final long serialVersionUID = -7046029254386353129L;
protected final SORTED_MAP KEY_VALUE_GENERIC sortedMap;
protected UnmodifiableSortedMap( final SORTED_MAP KEY_VALUE_GENERIC m ) {
super( m );
sortedMap = m;
}
public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { return sortedMap.comparator(); }
public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { if ( entries == null ) entries = ObjectSortedSets.unmodifiable( sortedMap.ENTRYSET() ); return (ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>)entries; }
@SuppressWarnings({ "rawtypes", "unchecked" })
public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return (ObjectSortedSet)ENTRYSET(); }
public SORTED_SET KEY_GENERIC keySet() { if ( keys == null ) keys = SORTED_SETS.unmodifiable( sortedMap.keySet() ); return (SORTED_SET KEY_GENERIC)keys; }
public SORTED_MAP KEY_VALUE_GENERIC subMap( final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to ) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC( sortedMap.subMap( from, to ) ); }
public SORTED_MAP KEY_VALUE_GENERIC headMap( final KEY_GENERIC_TYPE to ) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC( sortedMap.headMap( to ) ); }
public SORTED_MAP KEY_VALUE_GENERIC tailMap( final KEY_GENERIC_TYPE from ) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC( sortedMap.tailMap( from ) ); }
public KEY_GENERIC_TYPE FIRST_KEY() { return sortedMap.FIRST_KEY(); }
public KEY_GENERIC_TYPE LAST_KEY() { return sortedMap.LAST_KEY(); }
#if #keys(primitive)
public KEY_GENERIC_CLASS firstKey() { return sortedMap.firstKey(); }
public KEY_GENERIC_CLASS lastKey() { return sortedMap.lastKey(); }
public SORTED_MAP KEY_VALUE_GENERIC subMap( final KEY_GENERIC_CLASS from, final KEY_GENERIC_CLASS to ) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC( sortedMap.subMap( from, to ) ); }
public SORTED_MAP KEY_VALUE_GENERIC headMap( final KEY_GENERIC_CLASS to ) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC( sortedMap.headMap( to ) ); }
public SORTED_MAP KEY_VALUE_GENERIC tailMap( final KEY_GENERIC_CLASS from ) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC( sortedMap.tailMap( from ) ); }
#endif
}
/** Returns an unmodifiable type-specific sorted map backed by the given type-specific sorted map.
*
* @param m the sorted map to be wrapped in an unmodifiable sorted map.
* @return an unmodifiable view of the specified sorted map.
* @see java.util.Collections#unmodifiableSortedMap(SortedMap)
*/
public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC unmodifiable( final SORTED_MAP KEY_VALUE_GENERIC m ) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC( m ); }
#if defined(TEST) && ! #keyclass(Reference)
private static long seed = System.currentTimeMillis();
private static java.util.Random r = new java.util.Random( seed );
private static KEY_TYPE genKey() {
#if #keyclass(Byte) || #keyclass(Short) || #keyclass(Character)
return (KEY_TYPE)(r.nextInt());
#elif #keys(primitive)
return r.NEXT_KEY();
#else
return Integer.toBinaryString( r.nextInt() );
#endif
}
private static VALUE_TYPE genValue() {
#if #valueclass(Byte) || #valueclass(Short) || #valueclass(Character)
return (VALUE_TYPE)(r.nextInt());
#elif #values(primitive)
return r.NEXT_VALUE();
#elif !#valueclass(Reference) || #keyclass(Reference)
return Integer.toBinaryString( r.nextInt() );
#else
return new java.io.Serializable() {};
#endif
}
private static java.text.NumberFormat format = new java.text.DecimalFormat( "#,###.00" );
private static java.text.FieldPosition p = new java.text.FieldPosition( 0 );
private static String format( double d ) {
StringBuffer s = new StringBuffer();
return format.format( d, s, p ).toString();
}
private static void speedTest( int n, boolean comp ) {
System.out.println( "There are presently no speed tests for this class." );
}
private static boolean valEquals(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
private static void fatal( String msg ) {
System.out.println( msg );
System.exit( 1 );
}
private static void ensure( boolean cond, String msg ) {
if ( cond ) return;
fatal( msg );
}
private static Object[] k, v, nk;
private static KEY_TYPE kt[];
private static KEY_TYPE nkt[];
private static VALUE_TYPE vt[];
private static SORTED_MAP topMap;
protected static void testMaps( SORTED_MAP m, SortedMap t, int n, int level ) {
long ms;
boolean mThrowsIllegal, tThrowsIllegal, mThrowsNoElement, tThrowsNoElement, mThrowsUnsupp, tThrowsUnsupp;
Object rt = null, rm = null;
if ( level > 1 ) return;
/* Now we check that both maps agree on first/last keys. */
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;
try {
m.firstKey();
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
try {
t.firstKey();
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): firstKey() divergence at start in java.util.NoSuchElementException (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
if ( ! mThrowsNoElement ) ensure( t.firstKey().equals( m.firstKey() ), "Error (" + level + ", " + seed + "): m and t differ at start on their first key (" + m.firstKey() + ", " + t.firstKey() +")" );
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;
try {
m.lastKey();
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
try {
t.lastKey();
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): lastKey() divergence at start in java.util.NoSuchElementException (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
if ( ! mThrowsNoElement ) ensure( t.lastKey().equals( m.lastKey() ), "Error (" + level + ", " + seed + "): m and t differ at start on their last key (" + m.lastKey() + ", " + t.lastKey() +")");
/* Now we check that m and t are equal. */
if ( !m.equals( t ) || ! t.equals( m ) ) System.err.println("m: " + m + " t: " + t);
ensure( m.equals( t ), "Error (" + level + ", " + seed + "): ! m.equals( t ) at start" );
ensure( t.equals( m ), "Error (" + level + ", " + seed + "): ! t.equals( m ) at start" );
/* Now we check that m actually holds that data. */
for(java.util.Iterator i=t.entrySet().iterator(); i.hasNext(); ) {
java.util.Map.Entry e = (java.util.Map.Entry)i.next();
ensure( valEquals(e.getValue(), m.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after insertion (iterating on t)" );
}
/* Now we check that m actually holds that data, but iterating on m. */
for(java.util.Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
java.util.Map.Entry e = (java.util.Map.Entry)i.next();
ensure( valEquals(e.getValue(), t.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after insertion (iterating on m)" );
}
/* Now we check that m actually holds the same keys. */
for(java.util.Iterator i=t.keySet().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( m.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+") after insertion (iterating on t)" );
ensure( m.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+", in keySet()) after insertion (iterating on t)" );
}
/* Now we check that m actually holds the same keys, but iterating on m. */
for(java.util.Iterator i=m.keySet().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( t.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key after insertion (iterating on m)" );
ensure( t.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key (in keySet()) after insertion (iterating on m)" );
}
/* Now we check that m actually hold the same values. */
for(java.util.Iterator i=t.values().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( m.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after insertion (iterating on t)" );
ensure( m.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after insertion (iterating on t)" );
}
/* Now we check that m actually hold the same values, but iterating on m. */
for(java.util.Iterator i=m.values().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( t.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after insertion (iterating on m)");
ensure( t.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after insertion (iterating on m)");
}
/* Now we check that inquiries about random data give the same answer in m and t. For
m we use the polymorphic method. */
for(int i=0; i<n; i++ ) {
KEY_TYPE T = genKey();
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;
try {
m.containsKey(KEY2OBJ(T));
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { mThrowsIllegal = true; }
try {
t.containsKey(KEY2OBJ(T));
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { tThrowsIllegal = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): containsKey() divergence in java.util.NoSuchElementException (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
ensure( mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): containsKey() divergence in IllegalArgumentException (" + mThrowsIllegal + ", " + tThrowsIllegal + ")" );
if ( !mThrowsNoElement && !mThrowsIllegal ) {
ensure( m.containsKey(KEY2OBJ(T)) == t.containsKey(KEY2OBJ(T)), "Error (" + level + ", " + seed + "): divergence in keys between t and m (polymorphic method)" );
#if #keyclass(Object) && ! ( #values(reference) )
if ((m.GET_VALUE(T) != VALUE_NULL) != ((t.get(KEY2OBJ(T)) == null ? VALUE_NULL : VALUE_OBJ2TYPE(t.get(KEY2OBJ(T)))) != VALUE_NULL) ||
t.get(KEY2OBJ(T)) != null &&
! VALUE2OBJ(m.GET_VALUE(T)).equals(t.get(KEY2OBJ(T))))
#else
if ((m.get(T) != VALUE_NULL) != ((t.get(KEY2OBJ(T)) == null ? VALUE_NULL : VALUE_OBJ2TYPE(t.get(KEY2OBJ(T)))) != VALUE_NULL) ||
t.get(KEY2OBJ(T)) != null &&
! m.get(KEY2OBJ(T)).equals(t.get(KEY2OBJ(T))))
#endif
{
System.out.println("Error (" + level + ", " + seed + "): divergence between t and m (polymorphic method)");
System.exit( 1 );
}
}
}
/* Again, we check that inquiries about random data give the same answer in m and t, but
for m we use the standard method. */
for(int i=0; i<n; i++ ) {
KEY_TYPE T = genKey();
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;
try {
m.get(KEY2OBJ(T));
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { mThrowsIllegal = true; }
try {
t.get(KEY2OBJ(T));
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { tThrowsIllegal = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): get() divergence in java.util.NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
ensure( mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): get() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")" );
if ( !mThrowsNoElement && !mThrowsIllegal ) ensure( valEquals(m.get(KEY2OBJ(T)), t.get(KEY2OBJ(T))), "Error (" + level + ", " + seed + "): divergence between t and m (standard method)" );
}
/* Now we put and remove random data in m and t, checking that the result is the same. */
for(int i=0; i<20*n; i++ ) {
KEY_TYPE T = genKey();
VALUE_TYPE U = genValue();
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = mThrowsUnsupp = tThrowsUnsupp = false;
try {
rm = m.put(KEY2OBJ(T), VALUE2OBJ(U));
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { mThrowsIllegal = true; }
catch ( UnsupportedOperationException e ) { mThrowsUnsupp = true; }
try {
rt = t.put(KEY2OBJ(T), VALUE2OBJ(U));
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { tThrowsIllegal = true; }
catch ( UnsupportedOperationException e ) { tThrowsUnsupp = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): put() divergence in java.util.NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
ensure( mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): put() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")" );
ensure( mThrowsUnsupp == tThrowsUnsupp, "Error (" + level + ", " + seed + "): put() divergence in UnsupportedOperationException for " + T + " (" + mThrowsUnsupp + ", " + tThrowsUnsupp + ") " + m );
if ( !mThrowsNoElement && !mThrowsIllegal && !mThrowsUnsupp ) ensure( valEquals( rm, rt ), "Error (" + level + ", " + seed + "): divergence in put() between t and m (" + rt + ", " + rm + ")" );
T = genKey();
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = mThrowsUnsupp = tThrowsUnsupp = false;
try {
rm = m.remove(KEY2OBJ(T));
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { mThrowsIllegal = true; }
catch ( UnsupportedOperationException e ) { mThrowsUnsupp = true; }
try {
rt = t.remove(KEY2OBJ(T));
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
catch ( IllegalArgumentException e ) { tThrowsIllegal = true; }
catch ( UnsupportedOperationException e ) { tThrowsUnsupp = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): remove() divergence in java.util.NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
ensure( mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): remove() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")" );
ensure( mThrowsUnsupp == tThrowsUnsupp, "Error (" + level + ", " + seed + "): remove() divergence in UnsupportedOperationException for " + T + " (" + mThrowsUnsupp + ", " + tThrowsUnsupp + ") " + m );
if ( !mThrowsNoElement && !mThrowsIllegal && !mThrowsUnsupp ) ensure( valEquals( rm, rt ), "Error (" + level + ", " + seed + "): divergence in remove() between t and m (" + rt + ", " + rm + ")" );
}
ensure( m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals( t ) after removal" );
ensure( t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals( m ) after removal" );
/* Now we check that m actually holds the same data. */
for(java.util.Iterator i=t.entrySet().iterator(); i.hasNext(); ) {
java.util.Map.Entry e = (java.util.Map.Entry)i.next();
ensure( valEquals(e.getValue(), m.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after removal (iterating on t)");
}
/* Now we check that m actually holds that data, but iterating on m. */
for(java.util.Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
java.util.Map.Entry e = (java.util.Map.Entry)i.next();
ensure( valEquals(e.getValue(), t.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after removal (iterating on m)" );
}
/* Now we check that m actually holds the same keys. */
for(java.util.Iterator i=t.keySet().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( m.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+") after removal (iterating on t)");
ensure( m.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+", in keySet()) after removal (iterating on t)");
}
/* Now we check that m actually holds the same keys, but iterating on m. */
for(java.util.Iterator i=m.keySet().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( t.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key after removal (iterating on m)");
ensure( t.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key (in keySet()) after removal (iterating on m)");
}
/* Now we check that m actually hold the same values. */
for(java.util.Iterator i=t.values().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( m.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after removal (iterating on t)" );
ensure( m.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after removal (iterating on t)");
}
/* Now we check that m actually hold the same values, but iterating on m. */
for(java.util.Iterator i=m.values().iterator(); i.hasNext(); ) {
Object o = i.next();
ensure( t.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after removal (iterating on m)");
ensure( t.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after removal (iterating on m)");
}
/* Now we check that both maps agree on first/last keys. */
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;
try {
m.firstKey();
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
try {
t.firstKey();
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): firstKey() divergence in java.util.NoSuchElementException (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
if ( ! mThrowsNoElement ) ensure( t.firstKey().equals( m.firstKey() ), "Error (" + level + ", " + seed + "): m and t differ on their first key (" + m.firstKey() + ", " + t.firstKey() +")" );
mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;
try {
m.lastKey();
}
catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = true; }
try {
t.lastKey();
}
catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = true; }
ensure( mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): lastKey() divergence in java.util.NoSuchElementException (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
if ( ! mThrowsNoElement ) ensure( t.lastKey().equals( m.lastKey() ), "Error (" + level + ", " + seed + "): m and t differ on their last key (" + m.lastKey() + ", " + t.lastKey() +")");
/* Now we check cloning. */
if ( level == 0 ) {
ensure( m.equals( ((Singleton)m).clone() ), "Error (" + level + ", " + seed + "): m does not equal m.clone()" );
ensure( ((Singleton)m).clone().equals( m ), "Error (" + level + ", " + seed + "): m.clone() does not equal m" );
m = (SORTED_MAP)((Singleton)m).clone();
}
int h = m.hashCode();
/* Now we save and read m. */
SORTED_MAP m2 = null;
try {
java.io.File ff = new java.io.File("it.unimi.dsi.fastutil.test");
java.io.OutputStream os = new java.io.FileOutputStream(ff);
java.io.ObjectOutputStream oos = new java.io.ObjectOutputStream(os);
oos.writeObject(m);
oos.close();
java.io.InputStream is = new java.io.FileInputStream(ff);
java.io.ObjectInputStream ois = new java.io.ObjectInputStream(is);
m2 = (SORTED_MAP)ois.readObject();
ois.close();
ff.delete();
}
catch(Exception e) {
e.printStackTrace();
System.exit( 1 );
}
#if !#valueclass(Reference)
ensure( m2.hashCode() == h, "Error (" + level + ", " + seed + "): hashCode() changed after save/read" );
/* Now we check that m2 actually holds that data. */
ensure( m2.equals(t), "Error (" + level + ", " + seed + "): ! m2.equals( t ) after save/read" );
ensure( t.equals(m2), "Error (" + level + ", " + seed + "): ! t.equals( m2 ) after save/read" );
/* Now we take out of m everything, and check that it is empty. */
#endif
/* Now we play with iterators. */
{
java.util.ListIterator i, j;
Object J;
i = (java.util.ListIterator)m.entrySet().iterator();
j = new java.util.LinkedList( t.entrySet() ).listIterator();
for( int k = 0; k < 2*n; k++ ) {
ensure( i.hasNext() == j.hasNext(), "Error (" + level + ", " + seed + "): divergence in hasNext()" );
ensure( i.hasPrevious() == j.hasPrevious(), "Error (" + level + ", " + seed + "): divergence in hasPrevious()" );
if ( r.nextFloat() < .8 && i.hasNext() ) {
ensure( ((java.util.Map.Entry)i.next()).getKey().equals( J = ((Map.Entry)j.next()).getKey() ), "Error (" + level + ", " + seed + "): divergence in next()" );
}
else if ( r.nextFloat() < .2 && i.hasPrevious() ) {
ensure( ((java.util.Map.Entry)i.previous()).getKey().equals( J = ((Map.Entry)j.previous()).getKey() ), "Error (" + level + ", " + seed + "): divergence in previous()" );
}
ensure( i.nextIndex() == j.nextIndex(), "Error (" + level + ", " + seed + "): divergence in nextIndex()" );
ensure( i.previousIndex() == j.previousIndex(), "Error (" + level + ", " + seed + "): divergence in previousIndex()" );
}
}
{
boolean badPrevious = false;
Object previous = null;
it.unimi.dsi.fastutil.BidirectionalIterator i;
java.util.ListIterator j;
Object I, J;
KEY_TYPE from = genKey();
j = new java.util.LinkedList( t.keySet() ).listIterator();
while( j.hasNext() ) {
Object k = j.next();
if ( ((Comparable)k).compareTo( KEY2OBJ( from ) ) > 0 ) {
badPrevious = true;
j.previous();
break;
}
previous = k;
}
i = (it.unimi.dsi.fastutil.BidirectionalIterator)((SORTED_SET)m.keySet()).iterator( from );
for( int k = 0; k < 2*n; k++ ) {
ensure( i.hasNext() == j.hasNext(), "Error (" + level + ", " + seed + "): divergence in hasNext() (iterator with starting point " + from + ")" );
ensure( i.hasPrevious() == j.hasPrevious() || badPrevious && ( i.hasPrevious() == ( previous != null ) ), "Error (" + level + ", " + seed + "): divergence in hasPrevious() (iterator with starting point " + from + ")" + badPrevious );
if ( r.nextFloat() < .8 && i.hasNext() ) {
ensure( ( I = i.next() ).equals( J = j.next() ), "Error (" + level + ", " + seed + "): divergence in next() (" + I + ", " + J + ", iterator with starting point " + from + ")" );
//System.err.println("Done next " + I + " " + J + " " + badPrevious);
badPrevious = false;
if ( r.nextFloat() < 0.5 ) {
}
}
else if ( !badPrevious && r.nextFloat() < .2 && i.hasPrevious() ) {
ensure( ( I = i.previous() ).equals( J = j.previous() ), "Error (" + level + ", " + seed + "): divergence in previous() (" + I + ", " + J + ", iterator with starting point " + from + ")" );
if ( r.nextFloat() < 0.5 ) {
}
}
}
}
/* Now we check that m actually holds that data. */
ensure( m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals( t ) after iteration" );
ensure( t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals( m ) after iteration" );
/* Now we select a pair of keys and create a submap. */
if ( ! m.isEmpty() ) {
java.util.ListIterator i;
Object start = m.firstKey(), end = m.firstKey();
for( i = (java.util.ListIterator)m.keySet().iterator(); i.hasNext() && r.nextFloat() < .3; start = end = i.next() );
for( ; i.hasNext() && r.nextFloat() < .95; end = i.next() );
//System.err.println("Checking subMap from " + start + " to " + end + " (level=" + (level+1) + ")..." );
testMaps( (SORTED_MAP)m.subMap( (KEY_CLASS)start, (KEY_CLASS)end ), t.subMap( start, end ), n, level + 1 );
ensure( m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals( t ) after subMap" );
ensure( t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals( m ) after subMap" );
//System.err.println("Checking headMap to " + end + " (level=" + (level+1) + ")..." );
testMaps( (SORTED_MAP)m.headMap( (KEY_CLASS)end ), t.headMap( end ), n, level + 1 );
ensure( m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals( t ) after headMap" );
ensure( t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals( m ) after headMap" );
//System.err.println("Checking tailMap from " + start + " (level=" + (level+1) + ")..." );
testMaps( (SORTED_MAP)m.tailMap( (KEY_CLASS)start ), t.tailMap( start ), n, level + 1 );
ensure( m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals( t ) after tailMap" );
ensure( t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals( m ) after tailMap" );
}
}
private static void test() {
int n = 1;
k = new Object[n];
v = new Object[n];
nk = new Object[n];
kt = new KEY_TYPE[n];
nkt = new KEY_TYPE[n];
vt = new VALUE_TYPE[n];
for( int i = 0; i < n; i++ ) {
#if #keyclass(Object)
k[i] = kt[i] = genKey();
nk[i] = nkt[i] = genKey();
#else
k[i] = new KEY_CLASS( kt[i] = genKey() );
nk[i] = new KEY_CLASS( nkt[i] = genKey() );
#endif
#if #values(reference)
v[i] = vt[i] = genValue();
#else
v[i] = new VALUE_CLASS( vt[i] = genValue() );
#endif
}
SORTED_MAP m = new Singleton( kt[0], vt[0] );
topMap = m;
SortedMap t1 = new java.util.TreeMap();
t1.put( k[0], v[0] );
SortedMap t = java.util.Collections.unmodifiableSortedMap( t1 );
testMaps( m, t, n, 0 );
System.out.println("Test OK");
return;
}
public static void main( String args[] ) {
if ( args.length > 1 ) r = new java.util.Random( seed = Long.parseLong( args[ 1 ] ) );
try {
test();
} catch( Throwable e ) {
e.printStackTrace( System.err );
System.err.println( "seed: " + seed );
}
}
#endif
}