You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Michael Smith <mi...@iammichael.org> on 2002/02/01 07:07:23 UTC
[collections][PATCH] SequencedHashMap violates Map contract, has poor performance
I've submitted this patch twice now (once back in mid-November, once a
week ago), but it still has yet to be committed. The patch is
essentially a complete rewrite of the SequencedHashMap class and fixes
the following problems:
- Adding and removing from the map is O(n) because the linked list
needs to be traversed to find the object to remove (when adding, the
object needs to be removed so it can be readded at the front as the most
recently used). There's been recent discussion on the commons list
about a LRU/MRU thing that is implemented using a linked list/hashtable
combination that had similar performance problems. This class
demonstrates a manner in which the O(n) performance of using the
LinkedList can be avoided by implementing a custom linked list in the
map entries themselves.
- The sets and collections returned by keySet(), values(), and
entries() are not properly backed by the map (in violation of the
java.util.Map contract).
The patch also adds an additional test case to verify that the remove()
method of the Iterator returned from keySet().iterator() is properly
backed by the map.
Regards,
Michael
p.s. Since the changes to SequencedHashMap were significant, I'm also
attaching a full version of the file for ease of glancing over the new
code.
Index:
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa
che/commons/collections/SequencedHashMap.java
===================================================================
RCS file:
/home/cvspublic/jakarta-commons/collections/src/java/org/apache/commons/
collections/SequencedHashMap.java,v
retrieving revision 1.1
diff -u -r1.1 SequencedHashMap.java
---
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa
che/commons/collections/SequencedHashMap.java 17 Sep 2001 16:43:49 -0000
1.1
+++
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/java/org/apa
che/commons/collections/SequencedHashMap.java 1 Feb 2002 06:00:35 -0000
@@ -54,258 +54,507 @@
* <http://www.apache.org/>.
*/
+import java.util.Collections;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
-import java.util.LinkedList;
+import java.util.AbstractCollection;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Set;
+import java.util.NoSuchElementException;
/**
- * <p>A {@link java.util.HashMap} whose keys are sequenced. The
- * sequencing of the keys allow easy access to the values in the order
- * which they were added in. This class is thread safe.</p>
+ * A map of objects whose mapping entries are sequenced based on the
order in
+ * which they were added. This data structure has fast <I>O(1)</I>
search
+ * time, deletion time, and insertion time.
*
- * <p>Implementing the List interface is not possible due to a instance
- * method name clash between the Collection and the List interface:
+ * This class inherits from {@link java.util.HashMap} purely for
backwards
+ * compatibility. It should really be inheriting from {@link
+ * java.util.AbstractMap}, or with a tiny extra bit of work, implement
the
+ * full map interface on its own. APIs should not rely on this class
being an
+ * actual {@link java.util.HashMap}, and instead should recognize it
only as a
+ * generic {@link java.util.Map} (unless, of course, you need the
sequencing
+ * functionality, but even in that case, this class should not be
referred to
+ * as a HashMap).
*
- * <table>
- * <tr><td>Collections</td><td>boolean remove(Object o)</td></tr>
- * <tr><td>Lists</td><td>Object remove(Object o)</td></tr>
- * </table>
- * </p>
+ * <P>Although this map is sequenced, it cannot implement {@link
+ * java.util.List} because of incompatible interface definitions. The
remove
+ * methods in List and Map have different return values (see: {@link
+ * java.util.List#remove(Object)} and {@link
java.util.Map#remove(Object)}).
*
- * <p>So one cannot implement both interfaces at the same, which is
- * unfortunate because the List interface would be very nice in
- * conjuction with <a
- * href="http://jakarta.apache.org/velocity/">Velocity</a>.</p>
- *
- * <p>A slightly more complex implementation and interface could
involve
- * the use of a list of <code>Map.Entry</code> objects.</p>
+ * <P>This class is not thread safe. When a thread safe
implementation is
+ * required, wrap this class using {@link
Collections#synchronizedMap(Map)},
+ * or use explicit synchronization controls.
*
+ * @author <a href="mailto:michael@iammichael.org">Michael A.
Smith</A>
* @author <a href="mailto:dlr@collab.net">Daniel Rall</a>
* @author <a href="mailto:hps@intermeta.de">Henning P.
Schmiedehausen</a>
*/
-public class SequencedHashMap extends HashMap
-{
- /**
- * The index of the eldest element in the collection.
- */
- protected static final int ELDEST_INDEX = 0;
-
- /**
- * Indicator for an unknown index.
- */
- private static final int UNKNOWN_INDEX = -1;
-
- /**
- * The sequence used to keep track of the hash keys. Younger
objects are
- * kept towards the end of the list. Does not allow duplicates.
- */
- private LinkedList keySequence;
-
- /**
- * Creates a new instance with default storage.
- */
- public SequencedHashMap ()
- {
- keySequence = new LinkedList();
- }
-
- /**
- * Creates a new instance with the specified storage.
- *
- * @param size The storage to allocate up front.
- */
- public SequencedHashMap (int size)
- {
- super(size);
- keySequence = new LinkedList();
- }
-
- /**
- * Clears all elements.
- */
- public void clear ()
- {
- super.clear();
- keySequence.clear();
- }
-
- /**
- * Creates a shallow copy of this object, preserving the internal
- * structure by copying only references. The keys, values, and
- * sequence are not <code>clone()</code>'d.
- *
- * @return A clone of this instance.
- */
- public Object clone ()
- {
- SequencedHashMap seqHash = (SequencedHashMap) super.clone();
- seqHash.keySequence = (LinkedList) keySequence.clone();
- return seqHash;
- }
-
- /**
- * Returns the key at the specified index.
- */
- public Object get (int index)
- {
- return keySequence.get(index);
- }
-
- /**
- * Returns the value at the specified index.
- */
- public Object getValue (int index)
- {
- return get(get(index));
- }
-
- /**
- * Returns the index of the specified key.
- */
- public int indexOf (Object key)
- {
- return keySequence.indexOf(key);
- }
-
- /**
- * Returns a key iterator.
- */
- public Iterator iterator ()
- {
- return keySequence.iterator();
- }
-
- /**
- * Returns the last index of the specified key.
- */
- public int lastIndexOf (Object key)
- {
- return keySequence.lastIndexOf(key);
- }
-
- /**
- * Returns the ordered sequence of keys.
- *
- * This method is meant to be used for retrieval of Key / Value
pairs
- * in e.g. Velocity:
- * <PRE>
- * ## $table contains a sequenced hashtable
- * #foreach ($key in $table.sequence())
- * <TR>
- * <TD>Key: $key</TD>
- * </TD>Value: $table.get($key)</TD>
- * </TR>
- * #end
- * </PRE>
- *
- * @return The ordered list of keys.
- */
- public List sequence()
- {
- return keySequence;
- }
-
- /**
- * Stores the provided key/value pair. Freshens the sequence of
existing
- * elements.
- *
- * @param key The key to the provided value.
- * @param value The value to store.
- * @return The previous value for the specified key, or
- * <code>null</code> if none.
- */
- public Object put (Object key, Object value)
- {
- Object prevValue = super.put(key, value);
- freshenSequence(key, prevValue);
- return prevValue;
- }
-
- /**
- * Freshens the sequence of the element <code>value</code> if
- * <code>value</code> is not <code>null</code>.
- *
- * @param key The key whose sequence to freshen.
- * @param value The value whose existance to check before removing
the old
- * key sequence.
- */
- protected void freshenSequence(Object key, Object value)
- {
- if (value != null)
- {
- // Freshening existing element's sequence.
- keySequence.remove(key);
- }
- keySequence.add(key);
- }
+public class SequencedHashMap extends HashMap {
- /**
- * Stores the provided key/value pairs.
- *
- * @param t The key/value pairs to store.
- */
- public void putAll (Map t)
- {
- Set set = t.entrySet();
- for (Iterator iter = set.iterator(); iter.hasNext(); )
- {
- Map.Entry e = (Map.Entry)iter.next();
- put(e.getKey(), e.getValue());
+ /**
+ * {@link java.util.Map.Entry} that doubles as a node in the linked
list
+ * of sequenced mappings.
+ **/
+ private static class Entry implements Map.Entry {
+ private final Object key_;
+ private Object value_;
+
+ Entry next = null;
+ Entry prev = null;
+
+ public Entry(Object key, Object value) {
+ this.key_ = key;
+ this.value_ = value;
+ }
+
+ public Object getKey() {
+ return this.key_;
+ }
+
+ public Object getValue() {
+ return this.value_;
+ }
+
+ public Object setValue(Object value) {
+ Object oldValue = this.value_;
+ this.value_ = value;
+ return oldValue;
+ }
+
+ public int hashCode() {
+ // per Map.Entry.hashCode() api docs
+ return ((getKey() == null ? 0 : getKey().hashCode()) ^
+ (getValue()==null ? 0 : getValue().hashCode()));
+ }
+
+ public boolean equals(Object obj) {
+ if(obj == null) return false;
+ if(obj == this) return true;
+ if(!(obj instanceof Map.Entry)) return false;
+
+ Map.Entry other = (Map.Entry)obj;
+
+ // per Map.Entry.equals(Object api docs)
+ return((getKey() == null ?
+ other.getKey() == null :
+ getKey().equals(other.getKey())) &&
+ (getValue() == null ?
+ other.getValue() == null :
+ getValue().equals(other.getValue())));
+ }
+ public String toString() {
+ return "[" + getKey() + "=" + getValue() + "]";
+ }
+ }
+
+ private static final Entry createSentinel() {
+ Entry s = new Entry(null, null);
+ s.prev = s;
+ s.next = s;
+ return s;
+ }
+
+ private Entry sentinel;
+ private HashMap entries;
+
+ public SequencedHashMap() {
+ sentinel = createSentinel();
+ entries = new HashMap();
+ }
+
+ public SequencedHashMap(int initialSize) {
+ sentinel = createSentinel();
+ entries = new HashMap(initialSize);
+ }
+
+ public SequencedHashMap(int initialSize, float loadFactor) {
+ sentinel = createSentinel();
+ entries = new HashMap(initialSize, loadFactor);
+ }
+
+ public SequencedHashMap(Map m) {
+ this();
+ putAll(m);
+ }
+
+ /**
+ * Removes an internal entry from the linked list. This does not
remove
+ * it from the underlying map.
+ **/
+ private void removeEntry(Entry entry) {
+ entry.next.prev = entry.prev;
+ entry.prev.next = entry.next;
+ }
+
+ /**
+ * Inserts a new internal entry to the linked list. This does not
add the
+ * entry to the underlying map.
+ **/
+ private void insertEntry(Entry entry) {
+ entry.next = sentinel;
+ entry.prev = sentinel.prev;
+ sentinel.prev.next = entry;
+ sentinel.prev = entry;
+ }
+
+ public int size() {
+ return entries.size();
+ }
+
+ public boolean isEmpty() {
+ return entries.isEmpty();
+ }
+
+ public boolean containsKey(Object key) {
+ return entries.containsKey(key);
+ }
+
+ public boolean containsValue(Object value) {
+ return entries.containsValue(value);
+ }
+
+ public Object get(Object o) {
+ // find entry for the specified key
+ Entry entry = (Entry)entries.get(o);
+ if(entry == null) return null;
+
+ return entry.getValue();
+ }
+
+ public Object put(Object key, Object value) {
+
+ Object oldValue = null;
+
+ Entry e = (Entry)entries.get(key);
+ if(e != null) {
+ // remove from list so the entry gets "moved" to the front of
list
+ removeEntry(e);
+
+ // update value in map
+ oldValue = e.setValue(value);
+ } else {
+ // add new entry
+ e = new Entry(key, value);
+ entries.put(key, e);
+ }
+ // entry in map, but not list
+
+ // add to list
+ insertEntry(e);
+
+ return oldValue;
+ }
+
+ public Object remove(Object key) {
+ Entry e = (Entry)entries.remove(key);
+ if(e == null) return null;
+ removeEntry(e);
+ return e.getValue();
+ }
+
+ // use abstract map impl
+ //void putAll(Map t)
+
+ public void clear() {
+ entries.clear();
+ sentinel.next = sentinel;
+ sentinel.prev = sentinel;
+ }
+
+ public Set keySet() {
+ return new AbstractSet() {
+
+ // required impl
+ public Iterator iterator() { return new OrderedIterator(KEY); }
+ public boolean remove(Object o) {
+ return SequencedHashMap.this.remove(o) != null;
+ }
+
+ // more efficient impls than abstract set
+ public void clear() {
+ SequencedHashMap.this.clear();
+ }
+ public int size() {
+ return SequencedHashMap.this.size();
+ }
+ public boolean isEmpty() {
+ return SequencedHashMap.this.isEmpty();
+ }
+ public boolean contains(Object o) {
+ return SequencedHashMap.this.containsKey(o);
+ }
+
+ };
+ }
+
+ public Collection values() {
+ return new AbstractCollection() {
+ // required impl
+ public Iterator iterator() { return new OrderedIterator(VALUE); }
+ public boolean remove(Object o) {
+ for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next)
{
+ if((pos.getValue() == null && o == null) ||
+ (pos.getValue() != null && pos.getValue().equals(o))) {
+ SequencedHashMap.this.remove(pos.getKey());
+ return true;
+ }
}
- }
+ return false;
+ }
- /**
- * Removes the element at the specified index.
- *
- * @param index The index of the object to remove.
- * @return The previous value coressponding the
<code>key</code>, or
- * <code>null</code> if none existed.
- */
- public Object remove (int index)
- {
- return remove(index, null);
- }
-
- /**
- * Removes the element with the specified key.
- *
- * @param key The <code>Map</code> key of the object to remove.
- * @return The previous value coressponding the
<code>key</code>, or
- * <code>null</code> if none existed.
- */
- public Object remove (Object key)
- {
- return remove(UNKNOWN_INDEX, key);
- }
-
- /**
- * Removes the element with the specified key or index.
- *
- * @param index The index of the object to remove, or
- * <code>UNKNOWN_INDEX</code> if not known.
- * @param key The <code>Map</code> key of the object to remove.
- * @return The previous value coressponding the
<code>key</code>, or
- * <code>null</code> if none existed.
- */
- private final Object remove (int index, Object key)
- {
- if (index == UNKNOWN_INDEX)
- {
- index = indexOf(key);
- }
- if (key == null)
- {
- key = get(index);
- }
- if (index != UNKNOWN_INDEX)
- {
- keySequence.remove(index);
- }
- return super.remove(key);
- }
-}
+ // more efficient impls than abstract collection
+ public void clear() {
+ SequencedHashMap.this.clear();
+ }
+ public int size() {
+ return SequencedHashMap.this.size();
+ }
+ public boolean isEmpty() {
+ return SequencedHashMap.this.isEmpty();
+ }
+ public boolean contains(Object o) {
+ return SequencedHashMap.this.containsValue(o);
+ }
+ };
+ }
+
+ public Set entrySet() {
+ return new AbstractSet() {
+ // helper
+ private Entry findEntry(Object o) {
+ if(o == null) return null;
+ if(!(o instanceof Map.Entry)) return null;
+
+ Map.Entry e = (Map.Entry)o;
+ Entry entry = (Entry)entries.get(e.getKey());
+ if(entry.equals(e)) return entry;
+ else return null;
+ }
+
+ // required impl
+ public Iterator iterator() {
+ return new OrderedIterator(ENTRY);
+ }
+ public boolean remove(Object o) {
+ Entry e = findEntry(o);
+ if(e == null) return false;
+
+ return SequencedHashMap.this.remove(e.getKey()) != null;
+ }
+
+ // more efficient impls than abstract collection
+ public void clear() {
+ SequencedHashMap.this.clear();
+ }
+ public int size() {
+ return SequencedHashMap.this.size();
+ }
+ public boolean isEmpty() {
+ return SequencedHashMap.this.isEmpty();
+ }
+ public boolean contains(Object o) {
+ return findEntry(o) != null;
+ }
+ };
+ }
+
+ private static final int KEY = 0;
+ private static final int VALUE = 1;
+ private static final int ENTRY = 2;
+
+ private class OrderedIterator implements Iterator {
+
+ private int returnType;
+ private Entry pos = sentinel;
+ boolean removable = false;
+
+ public OrderedIterator(int returnType) {
+ this.returnType = returnType;
+ }
+
+ public boolean hasNext() {
+ return pos.next != sentinel;
+ }
+
+ public Object next() {
+ if(pos.next == sentinel) {
+ throw new NoSuchElementException();
+ }
+ pos = pos.next;
+ removable = true;
+ switch(returnType) {
+ case KEY:
+ return pos.getKey();
+ case VALUE:
+ return pos.getValue();
+ case ENTRY:
+ return pos;
+ default:
+ throw new Error("bad iterator type");
+ }
+
+ }
+
+ public void remove() {
+ if(!removable) {
+ throw new IllegalStateException("remove() must follow next()");
+ }
+
+ SequencedHashMap.this.remove(pos.getKey());
+ }
+ }
+
+ // APIs maintained from previous version of SequencedHashMap for
backwards
+ // compatibility
+
+ /**
+ * Creates a shallow copy of this object, preserving the internal
+ * structure by copying only references. The keys, values, and
+ * sequence are not <code>clone()</code>'d.
+ *
+ * @return A clone of this instance.
+ */
+ public Object clone () {
+ // yes, calling super.clone() silly since we're just blowing away
all
+ // the stuff that super might be doing anyway, but for motivations
on
+ // this, see:
+ // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html
+ SequencedHashMap map = (SequencedHashMap)super.clone();
+ map.sentinel = createSentinel();
+
+ // note: this does not preserve the initial capacity and load
factor.
+ map.entries = new HashMap();
+
+ map.putAll(this);
+
+ return map;
+ }
+
+ /**
+ * Returns the Map.Entry at the specified index
+ *
+ * @exception ArrayIndexOutOfBoundsException if the specified index
is
+ * <code>< 0</code> or <code>></code> the size of the map.
+ **/
+ private Map.Entry getEntry(int index) {
+ Entry pos = sentinel;
+
+ if(index < 0) {
+ throw new ArrayIndexOutOfBoundsException(index + " < 0");
+ }
+
+ // loop to one before the position
+ int i = -1;
+ while(i < index && pos.next != sentinel) {
+ i++;
+ pos = pos.next;
+ }
+ // pos.next is the requested position
+
+ // if sentinel is next, past end of list
+ if(pos.next == sentinel) {
+ throw new ArrayIndexOutOfBoundsException(index + " >= " + (i +
1));
+ }
+
+ return pos.next;
+ }
+
+ /**
+ * Returns the key at the specified index.
+ *
+ * @exception ArrayIndexOutOfBoundsException if the
<code>index</code> is
+ * <code>< 0</code> or <code>></code> the size of the map.
+ */
+ public Object get (int index)
+ {
+ return getEntry(index).getKey();
+ }
+
+ /**
+ * Returns the value at the specified index.
+ *
+ * @exception ArrayIndexOutOfBoundsException if the
<code>index</code> is
+ * <code>< 0</code> or <code>></code> the size of the map.
+ */
+ public Object getValue (int index)
+ {
+ return getEntry(index).getValue();
+ }
+
+ /**
+ * Returns the index of the specified key.
+ */
+ public int indexOf (Object key)
+ {
+ Entry e = (Entry)entries.get(key);
+ int pos = 0;
+ while(e.prev != sentinel) {
+ pos++;
+ e = e.prev;
+ }
+ return pos;
+ }
+
+ /**
+ * Returns a key iterator.
+ */
+ public Iterator iterator ()
+ {
+ return keySet().iterator();
+ }
+
+ /**
+ * Returns the last index of the specified key.
+ */
+ public int lastIndexOf (Object key)
+ {
+ // keys in a map are guarunteed to be unique
+ return indexOf(key);
+ }
+
+ /**
+ * Returns a List view of the keys rather than a set view. The
returned
+ * list is unmodifiable. This is required because changes to the
values of
+ * the list (using {@link java.util.ListIterator#set(Object)}) will
+ * effectively remove the value from the list and reinsert that value
at
+ * the end of the list, which is an unexpected side effect of
changing the
+ * value of a list. This occurs because changing the key, changes
when the
+ * mapping is added to the map and thus where it appears in the list.
+ *
+ * <P>An alternative to this method is to use {@link #keySet()}
+ *
+ * @see #keySet()
+ * @return The ordered list of keys.
+ */
+ public List sequence()
+ {
+ List l = new ArrayList(size());
+ Iterator iter = keySet().iterator();
+ while(iter.hasNext()) {
+ l.add(iter.next());
+ }
+
+ return Collections.unmodifiableList(l);
+ }
+
+ /**
+ * Removes the element at the specified index.
+ *
+ * @param index The index of the object to remove.
+ * @return The previous value coressponding the
<code>key</code>, or
+ * <code>null</code> if none existed.
+ *
+ * @exception ArrayIndexOutOfBoundsException if the
<code>index</code> is
+ * <code>< 0</code> or <code>></code> the size of the map.
+ */
+ public Object remove (int index)
+ {
+ return remove(get(index));
+ }
+}
Index:
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/test/org/apa
che/commons/collections/TestSequencedHashMap.java
===================================================================
RCS file:
/home/cvspublic/jakarta-commons/collections/src/test/org/apache/commons/
collections/TestSequencedHashMap.java,v
retrieving revision 1.1
diff -u -r1.1 TestSequencedHashMap.java
---
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/test/org/apa
che/commons/collections/TestSequencedHashMap.java 17 Sep 2001
16:43:49 -0000 1.1
+++
D:/home/michael/dev/jakarta/jakarta-commons/collections/src/test/org/apa
che/commons/collections/TestSequencedHashMap.java 1 Feb 2002
06:00:36 -0000
@@ -107,6 +107,42 @@
return new Object[] { "bar", "frob", new Object() };
}
+ public void testKeySetIteratorRemove() {
+ Object[] keys = getKeys();
+ Object[] values = getValues();
+ for(int i = 0; i < keys.length; i++) {
+ labRat.put(keys[i], values[i]);
+ }
+
+ for(int i = keys.length - 1; i >= 0; i--) {
+ // go to last key in the key set view of the map
+ Iterator iter = labRat.keySet().iterator();
+ while(iter.hasNext()) {
+ iter.next();
+ }
+
+ // and remove it
+ iter.remove();
+
+ assertEquals("size() does not match expected size after " +
+ "remove using key set iterator",
+ i, labRat.size());
+
+ // make sure that iterator() has the correct number of
entries in
+ // it as well.
+ int count = 0;
+ iter = labRat.iterator();
+ while(iter.hasNext()) {
+ iter.next();
+ count++;
+ }
+
+ assertEquals("iterator() does not have the same number of "
+
+ "values as the map",
+ labRat.size(), count);
+ }
+ }
+
public void testSequenceMap() throws Throwable {
Object[] keys = getKeys();
int expectedSize = keys.length;
@@ -150,4 +186,4 @@
protected void tearDown() {
labRat = null;
}
-}
\ No newline at end of file
+}
Re: [collections][PATCH] SequencedHashMap violates Map contract,
has poor performance
Posted by "Michael A. Smith" <ia...@iammichael.org>.
On Fri, 1 Feb 2002, Remy Maucherat wrote:
> No, there's no general rule and no Coding Style Police either :-)
> If you contribute to a component, the general rule is that you're supposed
> to follow the component's coding style.
that's rule number one in the Elements of Java Style. :)
michael
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Posted by Remy Maucherat <re...@apache.org>.
> Just 2 comments:
> - I understand the use of the sentinel but in the very fast glance I
> took at the code I still did not understand a couple of bits of
> code related to it. Since it was a very fast glance, it is very
> probable that everything is ok and that I just didn't get it yet.
>
> - I should have been more explicit about "code style". I mean "code
> formatting style". This is an ongoing discussion and I am not sure
> that the "right way" is well defined at the commons.
>
> Hey everybody!
> Is there a well defined rule for Code Formatting Style at the Commons?
No, there's no general rule and no Coding Style Police either :-)
If you contribute to a component, the general rule is that you're supposed
to follow the component's coding style.
> The Jakarta general rule at:
> http://jakarta.apache.org/site/source.html
>
> is:
> All Java Language source code in the repository must be written in
> conformance to the "Code Conventions for the Java Programming
> Language as published by Sun, or in conformance with another
> well-defined convention specified by the subproject. See the FAQ
> page for links to subproject conventions.
>
> Some projects like Velocity:
> http://jakarta.apache.org/velocity/code-standards.html
> define such non-Sun conventions.
There are indeed plenty of projects which don't follow this (not that I
care).
Remy
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [collections][PATCH] SequencedHashMap violates Map contract,
has poor performance
Posted by "Michael A. Smith" <ia...@iammichael.org>.
On Fri, 1 Feb 2002, Paulo Gaspar wrote:
> - I understand the use of the sentinel but in the very fast glance I
> took at the code I still did not understand a couple of bits of
> code related to it. Since it was a very fast glance, it is very
> probable that everything is ok and that I just didn't get it yet.
ah. if you get a chance to look at it in more depth, pass on any comments
you may have. When I have time, I'll still add a few more comments about
the implementation algorithm.
> - I should have been more explicit about "code style". I mean "code
> formatting style". This is an ongoing discussion and I am not sure
> that the "right way" is well defined at the commons.
Yeah, I've been following the debate. I'm not nitpicky on style, so as
soon as one is well defined, I'll update my patch (or provide a new patch
if the code is committed) to updat the style.
> Hey everybody!
> Is there a well defined rule for Code Formatting Style at the Commons?
>
> The Jakarta general rule at:
> http://jakarta.apache.org/site/source.html
>
> is:
> All Java Language source code in the repository must be written in
> conformance to the "Code Conventions for the Java Programming
> Language as published by Sun, or in conformance with another
> well-defined convention specified by the subproject. See the FAQ
> page for links to subproject conventions.
>
> Some projects like Velocity:
> http://jakarta.apache.org/velocity/code-standards.html
> define such non-Sun conventions.
>
>
> The Commons should either define their own rules or (argh!) follow
> the Sun guidelines.
At one point, I saw a proposal to use the "Elements of Java Style" as the
coding guidelines with the modification to prefix class variables with an
underscore (if that isn't already in it). I don't remembering seeing any
disagreement with that, so maybe we should set that as the commons
guidelines? The Elements of Java Style largely agree with Sun guidelines
with notable exceptions in the indent style: tabs in indents and indents
of two spaces (while Sun uses four space indents and a tab in place of
eight consecutive spaces). There may be a few other differences as well.
regards,
michael
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Posted by Paulo Gaspar <pa...@krankikom.de>.
Just 2 comments:
- I understand the use of the sentinel but in the very fast glance I
took at the code I still did not understand a couple of bits of
code related to it. Since it was a very fast glance, it is very
probable that everything is ok and that I just didn't get it yet.
- I should have been more explicit about "code style". I mean "code
formatting style". This is an ongoing discussion and I am not sure
that the "right way" is well defined at the commons.
Hey everybody!
Is there a well defined rule for Code Formatting Style at the Commons?
The Jakarta general rule at:
http://jakarta.apache.org/site/source.html
is:
All Java Language source code in the repository must be written in
conformance to the "Code Conventions for the Java Programming
Language as published by Sun, or in conformance with another
well-defined convention specified by the subproject. See the FAQ
page for links to subproject conventions.
Some projects like Velocity:
http://jakarta.apache.org/velocity/code-standards.html
define such non-Sun conventions.
The Commons should either define their own rules or (argh!) follow
the Sun guidelines.
Have fun,
Paulo Gaspar
> -----Original Message-----
> From: Michael Smith [mailto:michael@iammichael.org]
> Sent: Friday, February 01, 2002 3:25 PM
> To: Jakarta Commons Developers List
> Subject: RE: [collections][PATCH] SequencedHashMap violates Map
> contract, has poor performance
>
>
> > -----Original Message-----
> >
> > I just took a look at the code.
> >
> > There were a couple of details that are still not clear to me (as
> > around the "sentinel" use) but it looks much better than what we have
> > and it is e very complete implementation of the Map interface.
>
> The sentinel style linked list is based on the algorithm described in
> "Introduction to Algorithms" by Cormen Leiserson and Rivest, a book that
> I highly recommend. It allows you to pretty much ignore the boundary
> conditions.
>
> There are references to using sentinels on the web as well:
> http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Dllists/
> http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Dlists/lectur
> e.html
> http://www.cs.sunysb.edu/~algorith/lectures-good/node7.html
> http://dept-info.labri.u-bordeaux.fr/~strandh/Teaching/MTP/Common/Strand
> h-Tutorial/sentinel.html
>
> > However (playing Jon) there is a code style issue there.
>
> In using a sentinel? I can update the code to describe the algorithm
> used. I'll do that as soon as I have time -- either this evening or
> tomorrow.
>
> > Michael, you sure save on lines of code but is is not so easy to read
> > that way.
>
> If you're still referring to the sentinel thing, it's not about lines of
> code. It's about efficiency of the algorithm.
>
> Compare:
>
> void remove(Entry e) {
> if(e == head) {
> // entry is at head of list, update head rather than previous's
> next
> head = e.next;
> } else {
> e.prev.next = e.next;
> }
> if(e == tail) {
> // entry is at tail of list, update tail rather than next's
> previous
> tail = e.prev;
> } else {
> e.next.prev = e.prev;
> }
> }
>
> To:
>
> void remove(Entry e) {
> e.next.prev = e.prev
> e.prev.next = e.next
> }
>
>
> > Have fun,
>
> always!
>
> > Paulo Gaspar
>
> regards,
> michael
>
> >
> > > -----Original Message-----
> > > From: James Strachan [mailto:james_strachan@yahoo.co.uk]
> > > Sent: Friday, February 01, 2002 2:01 PM
> > > To: Jakarta Commons Developers List
> > > Subject: Re: [collections][PATCH] SequencedHashMap violates Map
> > > contract, has poor performance
> > >
> > >
> > > +1
> > >
> > > Sounds good to me.
> > >
> > > James
> > > ----- Original Message -----
> > > From: "Remy Maucherat" <re...@apache.org>
> > > > > I've submitted this patch twice now (once back in
> > mid-November, once a
> > > > > week ago), but it still has yet to be committed.
> > > >
> > > > If nobody has time to apply or look at Michael's patches, how
> > > about giving
> > > > him karma on jakarta-commons ?
> > > >
> > > > Remy
> > > >
> > > >
> > > > --
> > > > To unsubscribe, e-mail:
> > > <ma...@jakarta.apache.org>
> > > > For additional commands, e-mail:
> > > <ma...@jakarta.apache.org>
> > >
> > >
> > > _________________________________________________________
> > > Do You Yahoo!?
> > > Get your free @yahoo.com address at http://mail.yahoo.com
> > >
> > >
> > > --
> > > To unsubscribe, e-mail:
> > <ma...@jakarta.apache.org>
> > For additional commands, e-mail:
> > <ma...@jakarta.apache.org>
> >
> >
> > --
> > To unsubscribe, e-mail:
> <ma...@jakarta.apache.org>
> For additional commands, e-mail:
> <ma...@jakarta.apache.org>
>
>
>
> --
> To unsubscribe, e-mail:
> <ma...@jakarta.apache.org>
> For additional commands, e-mail:
> <ma...@jakarta.apache.org>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Posted by Michael Smith <mi...@iammichael.org>.
> -----Original Message-----
>
> I just took a look at the code.
>
> There were a couple of details that are still not clear to me (as
> around the "sentinel" use) but it looks much better than what we have
> and it is e very complete implementation of the Map interface.
The sentinel style linked list is based on the algorithm described in
"Introduction to Algorithms" by Cormen Leiserson and Rivest, a book that
I highly recommend. It allows you to pretty much ignore the boundary
conditions.
There are references to using sentinels on the web as well:
http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Dllists/
http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Dlists/lectur
e.html
http://www.cs.sunysb.edu/~algorith/lectures-good/node7.html
http://dept-info.labri.u-bordeaux.fr/~strandh/Teaching/MTP/Common/Strand
h-Tutorial/sentinel.html
> However (playing Jon) there is a code style issue there.
In using a sentinel? I can update the code to describe the algorithm
used. I'll do that as soon as I have time -- either this evening or
tomorrow.
> Michael, you sure save on lines of code but is is not so easy to read
> that way.
If you're still referring to the sentinel thing, it's not about lines of
code. It's about efficiency of the algorithm.
Compare:
void remove(Entry e) {
if(e == head) {
// entry is at head of list, update head rather than previous's
next
head = e.next;
} else {
e.prev.next = e.next;
}
if(e == tail) {
// entry is at tail of list, update tail rather than next's
previous
tail = e.prev;
} else {
e.next.prev = e.prev;
}
}
To:
void remove(Entry e) {
e.next.prev = e.prev
e.prev.next = e.next
}
> Have fun,
always!
> Paulo Gaspar
regards,
michael
>
> > -----Original Message-----
> > From: James Strachan [mailto:james_strachan@yahoo.co.uk]
> > Sent: Friday, February 01, 2002 2:01 PM
> > To: Jakarta Commons Developers List
> > Subject: Re: [collections][PATCH] SequencedHashMap violates Map
> > contract, has poor performance
> >
> >
> > +1
> >
> > Sounds good to me.
> >
> > James
> > ----- Original Message -----
> > From: "Remy Maucherat" <re...@apache.org>
> > > > I've submitted this patch twice now (once back in
> mid-November, once a
> > > > week ago), but it still has yet to be committed.
> > >
> > > If nobody has time to apply or look at Michael's patches, how
> > about giving
> > > him karma on jakarta-commons ?
> > >
> > > Remy
> > >
> > >
> > > --
> > > To unsubscribe, e-mail:
> > <ma...@jakarta.apache.org>
> > > For additional commands, e-mail:
> > <ma...@jakarta.apache.org>
> >
> >
> > _________________________________________________________
> > Do You Yahoo!?
> > Get your free @yahoo.com address at http://mail.yahoo.com
> >
> >
> > --
> > To unsubscribe, e-mail:
> <ma...@jakarta.apache.org>
> For additional commands, e-mail:
> <ma...@jakarta.apache.org>
>
>
> --
> To unsubscribe, e-mail:
<ma...@jakarta.apache.org>
For additional commands, e-mail:
<ma...@jakarta.apache.org>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
RE: [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Posted by Paulo Gaspar <pa...@krankikom.de>.
I just took a look at the code.
There were a couple of details that are still not clear to me (as
around the "sentinel" use) but it looks much better than what we have
and it is e very complete implementation of the Map interface.
However (playing Jon) there is a code style issue there.
Michael, you sure save on lines of code but is is not so easy to read
that way.
Have fun,
Paulo Gaspar
> -----Original Message-----
> From: James Strachan [mailto:james_strachan@yahoo.co.uk]
> Sent: Friday, February 01, 2002 2:01 PM
> To: Jakarta Commons Developers List
> Subject: Re: [collections][PATCH] SequencedHashMap violates Map
> contract, has poor performance
>
>
> +1
>
> Sounds good to me.
>
> James
> ----- Original Message -----
> From: "Remy Maucherat" <re...@apache.org>
> > > I've submitted this patch twice now (once back in mid-November, once a
> > > week ago), but it still has yet to be committed.
> >
> > If nobody has time to apply or look at Michael's patches, how
> about giving
> > him karma on jakarta-commons ?
> >
> > Remy
> >
> >
> > --
> > To unsubscribe, e-mail:
> <ma...@jakarta.apache.org>
> > For additional commands, e-mail:
> <ma...@jakarta.apache.org>
>
>
> _________________________________________________________
> Do You Yahoo!?
> Get your free @yahoo.com address at http://mail.yahoo.com
>
>
> --
> To unsubscribe, e-mail:
<ma...@jakarta.apache.org>
For additional commands, e-mail:
<ma...@jakarta.apache.org>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Posted by James Strachan <ja...@yahoo.co.uk>.
+1
Sounds good to me.
James
----- Original Message -----
From: "Remy Maucherat" <re...@apache.org>
> > I've submitted this patch twice now (once back in mid-November, once a
> > week ago), but it still has yet to be committed.
>
> If nobody has time to apply or look at Michael's patches, how about giving
> him karma on jakarta-commons ?
>
> Remy
>
>
> --
> To unsubscribe, e-mail:
<ma...@jakarta.apache.org>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>
_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Posted by Remy Maucherat <re...@apache.org>.
> I've submitted this patch twice now (once back in mid-November, once a
> week ago), but it still has yet to be committed.
If nobody has time to apply or look at Michael's patches, how about giving
him karma on jakarta-commons ?
Remy
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>