jpaul.DataStructs
Class DSUtil

java.lang.Object
  extended by jpaul.DataStructs.DSUtil

public abstract class DSUtil
extends java.lang.Object

DSUtil contains commonly used data-structure utilities.

Version:
$Id: DSUtil.java,v 1.18 2005/10/05 16:34:56 salcianu Exp $
Author:
Alexandru Salcianu - salcianu@alum.mit.edu

Constructor Summary
DSUtil()
           
 
Method Summary
static
<E> boolean
checkEq(E obj1, E obj2)
          Checks equality of two objects; deals with the case when obj1 is null, and next invokes equals.
static
<S,A extends S,B extends S>
boolean
disjoint(java.util.Collection<A> c1, java.util.Collection<B> c2)
          Checks whether two collections are disjoint.
static
<E> java.util.Collection<E>
filterColl(java.lang.Iterable<E> coll, Predicate<E> pred, java.util.Collection<E> newColl)
          Put in newColl all elements of coll that satisfy the predicate pred.
static
<E> E
getFirst(java.lang.Iterable<E> iterable)
           
static
<E> java.util.Collection<E>
iterable2coll(java.lang.Iterable<E> itrbl)
          Returns an immutable Collection view of an Iterable.
static
<E> boolean
iterableContains(java.lang.Iterable<E> itrbl, E elem)
          Checks whether itrbl contains the element elem.
static
<E> int
iterableSize(java.lang.Iterable<E> itrbl)
          Computes, in linear time, the length of an Iterable.
static
<E> boolean
iterableSizeEq(java.lang.Iterable<E> itrbl, int k)
          Checks whether the iterable itrbl has exactly k elements.
static
<E> boolean
iterableSizeGt(java.lang.Iterable<E> itrbl, int k)
          Checks whether the iterable itrbl has more than k elements.
static
<E> java.lang.String
iterableToString(java.lang.Iterable<E> itrbl)
           
static
<K,V> Function<K,V>
map2fun(java.util.Map<K,V> map)
          Construct a Function based on a map.
static
<E1,E2> java.util.Collection<E2>
mapColl(java.lang.Iterable<E1> coll, Function<E1,E2> func, java.util.Collection<E2> newColl)
          Maps collection coll into a new collection (stored in newColl), according to the function func.
static
<E1,E2> java.util.Collection<E2>
mapColl(java.lang.Iterable<E1> coll, java.util.Map<E1,E2> map, java.util.Collection<E2> newColl)
          Similar to teh other mapColl method, but the function is given as a map.
static
<E1,E2> java.util.Collection<E2>
mapColl2(java.lang.Iterable<E1> coll, Function<E1,E2> func, java.util.Collection<E2> newColl)
          Similar to mapColl, but filters out all null elements produced by func.
static
<A,B> java.lang.Iterable<B>
mapIterable(java.lang.Iterable<A> itrblA, Function<A,B> f)
           
static
<A,B> java.util.Iterator<B>
mapIterator(java.util.Iterator<A> it, Function<A,B> f)
           
static
<A,B> java.util.List<B>
mapList(java.util.List<A> list, Function<A,B> f)
           
static
<E> java.util.List<E>
select(java.util.List<E> list, java.util.List<java.lang.Integer> indices, java.util.List<E> sel)
           
static java.lang.String toString(java.lang.Object o)
          Returns "null" if the argument o is null, and o.toString() otherwise.
static
<E> java.util.Collection<E>
unionColl(java.util.Collection<E> c1, java.util.Collection<E> c2)
          Returns the immutable union of two collections.
static
<E> java.util.Collection<E>
unionColl(java.util.Collection<E> c1, java.util.Collection<E> c2, java.util.Collection<E> c3)
          Returns the immutable union of three collections.
static
<E> java.lang.Iterable<E>
unionIterable(java.lang.Iterable<E> it1, java.lang.Iterable<E> it2)
          Returns an immutable Iterable that is the union of two Iterables.
static
<E> java.lang.Iterable<E>
unionIterable(java.lang.Iterable<java.lang.Iterable<E>> its)
          Returns an immutable Iterable that is the union of several Iterables (in the order thet are given in its).
static
<E> java.util.List<E>
unionList(java.util.List<E> l1, java.util.List<E> l2)
          Returns an immutable List that is the union of two lists: it contains first the elements from l1, and next the elements from l2.
static
<E> java.lang.Iterable<E>
unmodifiableIterable(java.lang.Iterable<E> itrbl)
          Transforms a normal Iterable into an unmodifiable one.
static
<E> java.util.Iterator<E>
unmodifiableIterator(java.util.Iterator<E> it)
          Transforms a normal Iterator into an unmodifiable one.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DSUtil

public DSUtil()
Method Detail

checkEq

public static <E> boolean checkEq(E obj1,
                                  E obj2)
Checks equality of two objects; deals with the case when obj1 is null, and next invokes equals.


toString

public static java.lang.String toString(java.lang.Object o)
Returns "null" if the argument o is null, and o.toString() otherwise.


unmodifiableIterator

public static <E> java.util.Iterator<E> unmodifiableIterator(java.util.Iterator<E> it)
Transforms a normal Iterator into an unmodifiable one. The resulting iterator does not support remove.


unmodifiableIterable

public static <E> java.lang.Iterable<E> unmodifiableIterable(java.lang.Iterable<E> itrbl)
Transforms a normal Iterable into an unmodifiable one. The iterator over the resulting Iterable does not support remove.


iterableSize

public static <E> int iterableSize(java.lang.Iterable<E> itrbl)
Computes, in linear time, the length of an Iterable. This is done by iterating over all elements from itrbl and counting their number.


iterableSizeEq

public static <E> boolean iterableSizeEq(java.lang.Iterable<E> itrbl,
                                         int k)
Checks whether the iterable itrbl has exactly k elements. Instead of computing the length of itrbl (complexity: linear in the length) and comparing it with k, we try to iterate exactly k times and next check that itrbl is exhausted. Complexity: linear in k. Hence, this test is very fast for small ks.


iterableSizeGt

public static <E> boolean iterableSizeGt(java.lang.Iterable<E> itrbl,
                                         int k)
Checks whether the iterable itrbl has more than k elements. Instead of computing the length of itrbl (complexity: linear in the length) and comparing it with k, we try to iterate exactly k times and next check that itrbl is NOT exhausted. Complexity: linear in k. Hence, this test is very fast for small ks.


iterableContains

public static <E> boolean iterableContains(java.lang.Iterable<E> itrbl,
                                           E elem)
Checks whether itrbl contains the element elem.


iterable2coll

public static <E> java.util.Collection<E> iterable2coll(java.lang.Iterable<E> itrbl)
Returns an immutable Collection view of an Iterable.


unionList

public static <E> java.util.List<E> unionList(java.util.List<E> l1,
                                              java.util.List<E> l2)
Returns an immutable List that is the union of two lists: it contains first the elements from l1, and next the elements from l2.


unionColl

public static <E> java.util.Collection<E> unionColl(java.util.Collection<E> c1,
                                                    java.util.Collection<E> c2)
Returns the immutable union of two collections.


unionColl

public static <E> java.util.Collection<E> unionColl(java.util.Collection<E> c1,
                                                    java.util.Collection<E> c2,
                                                    java.util.Collection<E> c3)
Returns the immutable union of three collections.


unionIterable

public static <E> java.lang.Iterable<E> unionIterable(java.lang.Iterable<E> it1,
                                                      java.lang.Iterable<E> it2)
Returns an immutable Iterable that is the union of two Iterables. The resulting Iterable contains first all elements from it1, and next all elements from it2.


unionIterable

public static <E> java.lang.Iterable<E> unionIterable(java.lang.Iterable<java.lang.Iterable<E>> its)
Returns an immutable Iterable that is the union of several Iterables (in the order thet are given in its).


filterColl

public static <E> java.util.Collection<E> filterColl(java.lang.Iterable<E> coll,
                                                     Predicate<E> pred,
                                                     java.util.Collection<E> newColl)
Put in newColl all elements of coll that satisfy the predicate pred.

Returns:
newColl, the collection with the filtered elements.

mapColl

public static <E1,E2> java.util.Collection<E2> mapColl(java.lang.Iterable<E1> coll,
                                                       Function<E1,E2> func,
                                                       java.util.Collection<E2> newColl)
Maps collection coll into a new collection (stored in newColl), according to the function func.


mapColl2

public static <E1,E2> java.util.Collection<E2> mapColl2(java.lang.Iterable<E1> coll,
                                                        Function<E1,E2> func,
                                                        java.util.Collection<E2> newColl)
Similar to mapColl, but filters out all null elements produced by func.

See Also:
mapColl(java.lang.Iterable, jpaul.Misc.Function, java.util.Collection)

mapColl

public static <E1,E2> java.util.Collection<E2> mapColl(java.lang.Iterable<E1> coll,
                                                       java.util.Map<E1,E2> map,
                                                       java.util.Collection<E2> newColl)
Similar to teh other mapColl method, but the function is given as a map. This map is expected to map all elements from the entry collection coll.

See Also:
mapColl(Iterable, Function, Collection)

map2fun

public static <K,V> Function<K,V> map2fun(java.util.Map<K,V> map)
Construct a Function based on a map. The resulting function will throw an exception if invoked on an element that is unassigned in map.


getFirst

public static <E> E getFirst(java.lang.Iterable<E> iterable)
Returns:
Returns the first element from iterable. Returns null if iterable is empty.

mapIterator

public static <A,B> java.util.Iterator<B> mapIterator(java.util.Iterator<A> it,
                                                      Function<A,B> f)

mapIterable

public static <A,B> java.lang.Iterable<B> mapIterable(java.lang.Iterable<A> itrblA,
                                                      Function<A,B> f)

mapList

public static <A,B> java.util.List<B> mapList(java.util.List<A> list,
                                              Function<A,B> f)

disjoint

public static <S,A extends S,B extends S> boolean disjoint(java.util.Collection<A> c1,
                                                           java.util.Collection<B> c2)
Checks whether two collections are disjoint. The two collections must contain elements with a common superclass S. The worst-case complexity is proportional to the product of the lengths of the two collections. The implementation checks that none of the elements of the smallest collection is present in the second one. If membership testing is O(1), the complexity of the disjointness test is linear in the length of the smallest of the two collections.


select

public static <E> java.util.List<E> select(java.util.List<E> list,
                                           java.util.List<java.lang.Integer> indices,
                                           java.util.List<E> sel)

iterableToString

public static <E> java.lang.String iterableToString(java.lang.Iterable<E> itrbl)


Copyright 2005 Alexandru Salcianu - salcianu@alum.mit.edu