Mailing-List: contact commits-help@harmony.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@harmony.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r627476 - in
 /harmony/enhanced/classlib/trunk/modules/luni/src:
 main/java/java/util/ test/api/common/org/apache/harmony/luni/tests/java/util/
Date: Wed, 13 Feb 2008 15:33:54 -0000
To: commits@harmony.apache.org
From: tellison@apache.org
Message-Id: <20080213153357.496131A983E@eris.apache.org>

Author: tellison
Date: Wed Feb 13 07:33:52 2008
New Revision: 627476

URL: http://svn.apache.org/viewvc?rev=627476&view=rev
Log:
Apply patch for HARMONY-5475 ([classlib][luni]TreeMap problems) including
slightly modified version of test case (copyright notices, and package and type renaming).

Added:
    harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/RefSortedMap.java   (with props)
    harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/SortedMapTestBase.java   (with props)
    harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/TreeMapRndTest.java   (with props)
Modified:
    harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java

Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java?rev=627476&r1=627475&r2=627476&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/TreeMap.java Wed Feb 13 07:33:52 2008
@@ -43,6 +43,82 @@
     transient Set<Map.Entry<K, V>> entrySet;
 
     transient Node<K, V> root;
+    
+class MapEntry implements Map.Entry<K, V>, Cloneable {
+		
+		final int offset;
+		final Node<K, V> node;
+		final K key;
+		
+	    MapEntry(Node<K, V> node, int offset) {
+	    	this.node = node;
+	    	this.offset = offset;
+	    	key = node.keys[offset];
+	    }
+
+	    @Override
+	    public Object clone() {
+	        try {
+	            return super.clone();
+	        } catch (CloneNotSupportedException e) {
+	            return null;
+	        }
+	    }
+
+	    @Override
+	    public boolean equals(Object object) {
+	        if (this == object) {
+	            return true;
+	        }
+	        if (object instanceof Map.Entry) {
+	            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;	            
+	            V value = getValue();
+	            return (key == null ? entry.getKey() == null : key.equals(entry
+	                    .getKey()))
+	                    && (value == null ? entry.getValue() == null : value
+	                            .equals(entry.getValue()));
+	        }
+	        return false;
+	    }
+
+	    public K getKey() {
+	        return key;
+	    }
+
+	    public V getValue() {
+	    	if (node.keys[offset] == key) {
+	    		return node.values[offset];
+	    	}
+	    	if (containsKey(key)) {
+	    		return get(key);
+	    	}
+	    	throw new IllegalStateException();
+	    }
+
+	    @Override
+	    public int hashCode() {
+	    	V value = getValue();
+	        return (key == null ? 0 : key.hashCode())
+	                ^ (value == null ? 0 : value.hashCode());
+	    }
+
+	    public V setValue(V object) {
+	    	if (node.keys[offset] == key) {
+	    		V res = node.values[offset];
+	    		node.values[offset] = object;
+	    		return res;
+	    	}
+	    	if (containsKey(key)) {
+	    		return put(key, object);
+	    	}
+	    	throw new IllegalStateException();
+	    }
+
+	    @Override
+	    public String toString() {
+	        return key + "=" + getValue();
+	    }
+	}
 
     static class Node <K,V> implements Cloneable {
         static final int NODE_SIZE = 64;
@@ -137,7 +213,7 @@
             if (expectedModCount == backingMap.modCount) {
                 if (lastNode != null) {
                     int idx = lastNode.right_idx - lastOffset;
-                    backingMap.remove(lastNode, idx);
+                    backingMap.removeFromIterator(lastNode, idx);
                     lastNode = null;
                     expectedModCount++;
                 } else {
@@ -163,7 +239,7 @@
         public Map.Entry<K, V> next() {
             makeNext();
             int idx = lastNode.right_idx - lastOffset;
-            return new MapEntry<K, V>(lastNode.keys[idx], lastNode.values[idx]);
+            return backingMap.new MapEntry(lastNode, idx);
         }
     }
 
@@ -208,7 +284,7 @@
 
         BoundedMapIterator(Node<K, V> startNode, int startOffset, TreeMap<K, V> map,
                            Node<K, V> finalNode, int finalOffset) {
-            super(map, startNode, startOffset);
+            super(map, finalNode==null? null : startNode, startOffset);
             this.finalNode = finalNode;
             this.finalOffset = finalOffset;
         }
@@ -227,9 +303,8 @@
         }
 
         void makeBoundedNext() {
-            boolean endOfIterator = node == finalNode && offset == finalOffset;
             makeNext();
-            if (endOfIterator) {
+            if (lastNode == finalNode && lastOffset == finalOffset) {
                 node = null;
             }
         }
@@ -246,7 +321,7 @@
         public Map.Entry<K, V> next() {
             makeBoundedNext();
             int idx = lastNode.right_idx - lastOffset;
-            return new MapEntry<K, V>(lastNode.keys[idx], lastNode.values[idx]);
+            return backingMap.new MapEntry(lastNode, idx);
         }
     }
 
@@ -1739,7 +1814,7 @@
                 node = node.left;
             } else if (result == 0) {
                 V value = node.values[left_idx];
-                remove(node, left_idx);
+                removeLeftmost(node);
                 return value;
             } else {
                 int right_idx = node.right_idx;
@@ -1750,7 +1825,7 @@
                     node = node.right;
                 } else if (result == 0) {
                     V value = node.values[right_idx];
-                    remove(node, right_idx);
+                    removeRightmost(node);
                     return value;
                 } else { /*search in node*/
                     int low = left_idx + 1, mid = 0, high = right_idx - 1;
@@ -1761,7 +1836,7 @@
                             low = mid + 1;
                         } else if (result == 0) {
                             V value = node.values[mid];
-                            remove(node, mid);
+                            removeMiddleElement(node, mid);
                             return value;
                         } else {
                             high = mid - 1;
@@ -1774,133 +1849,290 @@
         return null;
     }
 
-    void remove(Node<K, V> node, int index) {
+    void removeLeftmost(Node<K, V> node) {
+        int index = node.left_idx;
         if (node.size == 1) {
             deleteNode(node);
         } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
             // move all to prev node and kill it
             Node<K, V> prev = node.prev;
-            int left_idx = node.left_idx;
-            if (index != left_idx) {
-                int size = index - left_idx;
-                System.arraycopy(node.keys,   left_idx, prev.keys,   prev.right_idx + 1, size);
-                System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size);
-                prev.right_idx += size;
-            }
-            int right_idx = node.right_idx;
-            if (index != right_idx) {
-                int size = right_idx - index;
-                System.arraycopy(node.keys,   index + 1, prev.keys,   prev.right_idx + 1, size);
-                System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size);
-                prev.right_idx += size;
+            int size = node.right_idx - index;
+            System.arraycopy(node.keys,   index + 1, prev.keys,   prev.right_idx + 1, size);
+            System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size);
+            prev.right_idx += size;
+            prev.size += size;
+            deleteNode(node);
+        } else if (node.next != null && (node.next.left_idx) > node.size) {
+            // move all to next node and kill it
+            Node<K, V> next = node.next;
+            int size = node.right_idx - index;
+            int next_new_left = next.left_idx - size;
+            next.left_idx = next_new_left;
+            System.arraycopy(node.keys,   index + 1, next.keys,   next_new_left, size);
+            System.arraycopy(node.values, index + 1, next.values, next_new_left, size);
+            next.size += size;
+            deleteNode(node);
+        } else {
+            node.keys[index] = null;
+            node.values[index] = null;
+            node.left_idx++;
+            node.size--;
+            Node<K, V> prev = node.prev;
+            if (prev != null && prev.size == 1) {
+                node.size++;
+                node.left_idx--;
+                node.keys  [node.left_idx] = prev.keys  [prev.left_idx];
+                node.values[node.left_idx] = prev.values[prev.left_idx];
+                deleteNode(prev);
             }
-            prev.size += (node.size - 1);
+        }
+        modCount++;
+        size--;
+    }
+
+    void removeRightmost(Node<K, V> node) {
+        int index = node.right_idx;
+        if (node.size == 1) {
+            deleteNode(node);
+        } else if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
+            // move all to prev node and kill it
+            Node<K, V> prev = node.prev;
+            int left_idx = node.left_idx;
+            int size = index - left_idx;
+            System.arraycopy(node.keys,   left_idx, prev.keys,   prev.right_idx + 1, size);
+            System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size);
+            prev.right_idx += size;
+            prev.size += size;
             deleteNode(node);
         } else if (node.next != null && (node.next.left_idx) > node.size) {
             // move all to next node and kill it
             Node<K, V> next = node.next;
             int left_idx = node.left_idx;
-            int next_new_left = next.left_idx + node.size - 1;
+            int size = index - left_idx;
+            int next_new_left = next.left_idx - size;
             next.left_idx = next_new_left;
-            if (index != left_idx) {
-                int size = index - left_idx;
-                System.arraycopy(node.keys,   left_idx, next.keys,   next_new_left, size);
-                System.arraycopy(node.values, left_idx, next.values, next_new_left, size);
-                next_new_left += size;
-            }
-            int right_idx = node.right_idx;
-            if (index != right_idx) {
-                int size = right_idx - index;
-                System.arraycopy(node.keys,   index + 1, next.keys,   next_new_left, size);
-                System.arraycopy(node.values, index + 1, next.values, next_new_left, size);
-            }
-            next.size += (node.size - 1);
+            System.arraycopy(node.keys,   left_idx, next.keys,   next_new_left, size);
+            System.arraycopy(node.values, left_idx, next.values, next_new_left, size);
+            next.size += size;
             deleteNode(node);
         } else {
-            if (index == node.left_idx) {
-                node.keys[index] = null;
-                node.values[index] = null;
-                node.left_idx++;
-            } else if (index == node.right_idx) {
-                node.keys[index] = null;
-                node.values[index] = null;
-                node.right_idx--;
-            } else if (node.right_idx - index <= index - node.left_idx) {
-                System.arraycopy(node.keys,   index + 1, node.keys,   index, node.right_idx - index);
-                System.arraycopy(node.values, index + 1, node.values, index, node.right_idx - index);
-                node.right_idx--;
-            } else {
-                System.arraycopy(node.keys,   node.left_idx, node.keys,   node.left_idx + 1, index - node.left_idx);
-                System.arraycopy(node.values, node.left_idx, node.values, node.left_idx + 1, index - node.left_idx);
-                node.left_idx++;
-            }
+            node.keys[index] = null;
+            node.values[index] = null;
+            node.right_idx--;
             node.size--;
             Node<K, V> next = node.next;
-            Node<K, V> prev = node.prev;
-            if (next != null && node.right_idx < Node.NODE_SIZE - 1 && next.size == 1) {
+            if (next != null && next.size == 1) {
                 node.size++;
                 node.right_idx++;
                 node.keys[node.right_idx]   = next.keys[next.left_idx];
                 node.values[node.right_idx] = next.values[next.left_idx];
                 deleteNode(next);
-            } else if (prev != null && node.left_idx > 0 && prev.size == 1) {
-                node.size++;
-                node.left_idx--;
-                node.keys[node.left_idx]   = prev.keys[prev.left_idx];
-                node.values[node.left_idx] = prev.values[prev.left_idx];
-                deleteNode(prev);
             }
         }
         modCount++;
         size--;
     }
 
-    private void deleteNode(Node<K, V> node) {
-        Node<K, V> toDelete, toConnect;
-        if (node.right == null || node.left == null) {
-            toDelete = node;
+    void removeMiddleElement(Node<K, V> node, int index) {
+        // this function is called iff index if some middle element;
+        // so node.left_idx < index < node.right_idx
+        // condition above assume that node.size > 1
+        if (node.prev != null && (Node.NODE_SIZE - 1 - node.prev.right_idx) > node.size) {
+            // move all to prev node and kill it
+            Node<K, V> prev = node.prev;
+            int left_idx = node.left_idx;
+            int size = index - left_idx;
+            System.arraycopy(node.keys,   left_idx, prev.keys,   prev.right_idx + 1, size);
+            System.arraycopy(node.values, left_idx, prev.values, prev.right_idx + 1, size);
+            prev.right_idx += size;
+            size = node.right_idx - index;
+            System.arraycopy(node.keys,   index + 1, prev.keys,   prev.right_idx + 1, size);
+            System.arraycopy(node.values, index + 1, prev.values, prev.right_idx + 1, size);
+            prev.right_idx += size;
+            prev.size += (node.size - 1);
+            deleteNode(node);
+        } else if (node.next != null && (node.next.left_idx) > node.size) {
+            // move all to next node and kill it
+            Node<K, V> next = node.next;
+            int left_idx = node.left_idx;
+            int next_new_left = next.left_idx - node.size + 1;
+            next.left_idx = next_new_left;
+            int size = index - left_idx;
+            System.arraycopy(node.keys,   left_idx, next.keys,   next_new_left, size);
+            System.arraycopy(node.values, left_idx, next.values, next_new_left, size);
+            next_new_left += size;
+            size = node.right_idx - index;
+            System.arraycopy(node.keys,   index + 1, next.keys,   next_new_left, size);
+            System.arraycopy(node.values, index + 1, next.values, next_new_left, size);
+            next.size += (node.size - 1);
+            deleteNode(node);
         } else {
-            toDelete = node.next;
+            int moveFromRight = node.right_idx - index;
+            int left_idx = node.left_idx;
+            int moveFromLeft = index - left_idx ;
+            if (moveFromRight <= moveFromLeft) {
+                System.arraycopy(node.keys,   index + 1, node.keys,   index, moveFromRight);
+                System.arraycopy(node.values, index + 1, node.values, index, moveFromRight);
+                Node<K, V> next = node.next;
+                if (next != null && next.size == 1) {
+                    node.keys  [node.right_idx] = next.keys  [next.left_idx];
+                    node.values[node.right_idx] = next.values[next.left_idx];
+                    deleteNode(next);
+                } else {
+                    node.keys  [node.right_idx] = null;
+                    node.values[node.right_idx] = null;
+                    node.right_idx--;
+                    node.size--;
+                }
+            } else {
+                System.arraycopy(node.keys,   left_idx , node.keys,   left_idx  + 1, moveFromLeft);
+                System.arraycopy(node.values, left_idx , node.values, left_idx + 1, moveFromLeft);
+                Node<K, V> prev = node.prev;
+                if (prev != null && prev.size == 1) {
+                    node.keys  [left_idx ] = prev.keys  [prev.left_idx];
+                    node.values[left_idx ] = prev.values[prev.left_idx];
+                    deleteNode(prev);
+                } else {
+                    node.keys  [left_idx ] = null;
+                    node.values[left_idx ] = null;
+                    node.left_idx++;
+                    node.size--;
+                }
+            }
         }
-        if (toDelete.left != null) {
-            toConnect = toDelete.left;
+        modCount++;
+        size--;
+    }
+
+    void removeFromIterator(Node<K, V> node, int index) {
+        if (node.size == 1) {
+            // it is safe to delete the whole node here.
+            // iterator already moved to the next node;
+            deleteNode(node);
         } else {
-            toConnect = toDelete.right;
+            int left_idx = node.left_idx;
+            if (index == left_idx) {
+                Node<K, V> prev = node.prev;
+                if (prev != null && prev.size == 1) {
+                    node.keys  [left_idx] = prev.keys  [prev.left_idx];
+                    node.values[left_idx] = prev.values[prev.left_idx];
+                    deleteNode(prev);
+                } else {
+                    node.keys  [left_idx] = null;
+                    node.values[left_idx] = null;
+                    node.left_idx++;
+                    node.size--;
+                }
+            } else if (index == node.right_idx) {
+                node.keys  [index] = null;
+                node.values[index] = null;
+                node.right_idx--;
+                node.size--;
+            } else {
+                int moveFromRight = node.right_idx - index;
+                int moveFromLeft = index - left_idx;
+                if (moveFromRight <= moveFromLeft) {
+                    System.arraycopy(node.keys,   index + 1, node.keys,   index, moveFromRight );
+                    System.arraycopy(node.values, index + 1, node.values, index, moveFromRight );
+                    node.keys  [node.right_idx] = null;
+                    node.values[node.right_idx] = null;
+                    node.right_idx--;
+                    node.size--;
+                } else {
+                    System.arraycopy(node.keys,   left_idx, node.keys,   left_idx+ 1, moveFromLeft);
+                    System.arraycopy(node.values, left_idx, node.values, left_idx+ 1, moveFromLeft);
+                    node.keys  [left_idx] = null;
+                    node.values[left_idx] = null;
+                    node.left_idx++;
+                    node.size--;
+               }
+            }
         }
-        if (toConnect != null) {
-            toConnect.parent = toDelete.parent;
+        modCount++;
+        size--;
+    }
+
+    private void deleteNode(Node<K, V> node) {
+        if (node.right == null) {
+            if (node.left != null) {
+                attachToParent(node, node.left);
+           } else {
+                attachNullToParent(node);
+            }
+            fixNextChain(node);
+        } else if(node.left == null) { // node.right != null
+            attachToParent(node, node.right);
+            fixNextChain(node);
+        } else {
+            // Here node.left!=nul && node.right!=null
+            // node.next should replace node in tree
+            // node.next!=null by tree logic.
+            // node.next.left==null by tree logic.
+            // node.next.right may be null or non-null
+            Node<K, V> toMoveUp = node.next;
+            fixNextChain(node);
+            if(toMoveUp.right==null){
+                attachNullToParent(toMoveUp);
+            } else {
+                attachToParent(toMoveUp, toMoveUp.right);
+            }
+            // Here toMoveUp is ready to replace node
+            toMoveUp.left = node.left;
+            if (node.left != null) {
+            	node.left.parent = toMoveUp;
+            }
+            toMoveUp.right = node.right;
+            if (node.right != null) {
+            	node.right.parent = toMoveUp;
+            }
+            attachToParentNoFixup(node,toMoveUp);
+            toMoveUp.color = node.color;
         }
-        if (toDelete.parent == null) {
+    }
+
+    private void attachToParentNoFixup(Node<K, V> toDelete, Node<K, V> toConnect) {
+        // assert toConnect!=null
+        Node<K,V> parent = toDelete.parent;
+        toConnect.parent = parent;
+        if (parent == null) {
             root = toConnect;
-        } else if (toDelete == toDelete.parent.left) {
-            toDelete.parent.left = toConnect;
+        } else if (toDelete == parent.left) {
+            parent.left = toConnect;
         } else {
-            toDelete.parent.right = toConnect;
+            parent.right = toConnect;
         }
-        if (toDelete != node) {
-            node.keys = toDelete.keys;
-            node.values = toDelete.values;
-            node.size = toDelete.size;
-            node.left_idx = toDelete.left_idx;
-            node.right_idx = toDelete.right_idx;
-            node.next = toDelete.next;
-            if (node.next != null) {
-                node.next.prev = node;
-            }
+    }
+
+    private void attachToParent(Node<K, V> toDelete, Node<K, V> toConnect) {
+        // assert toConnect!=null
+        attachToParentNoFixup(toDelete,toConnect);
+        if (!toDelete.color) {
+            fixup(toConnect);
+        }
+    }
+
+    private void attachNullToParent(Node<K, V> toDelete) {
+        Node<K, V> parent = toDelete.parent;
+        if (parent == null) {
+            root = null;
         } else {
-            if (node.prev != null) {
-                node.prev.next = node.next;
+            if (toDelete == parent.left) {
+                parent.left = null;
+            } else {
+                parent.right = null;
             }
-            if (node.next != null) {
-                node.next.prev = node.prev;
+            if (!toDelete.color) {
+                fixup(parent);
             }
         }
-        if (!toDelete.color && root != null) {
-            if (toConnect == null) {
-                fixup(toDelete.parent);
-            } else {
-                fixup(toConnect);
-            }
+    }
+
+    private void fixNextChain(Node<K, V> node) {
+        if (node.prev != null) {
+            node.prev.next = node.next;
+        }
+        if (node.next != null) {
+            node.next.prev = node.prev;
         }
     }
 

Added: harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/RefSortedMap.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/RefSortedMap.java?rev=627476&view=auto
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/RefSortedMap.java (added)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/RefSortedMap.java Wed Feb 13 07:33:52 2008
@@ -0,0 +1,402 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package org.apache.harmony.luni.tests.java.util;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Set;
+import java.util.SortedMap;
+
+public class RefSortedMap<K, V> extends java.util.AbstractMap<K, V>
+        implements SortedMap<K, V>, Cloneable, Serializable {
+    
+    private static final long serialVersionUID = 1L;
+    
+    private static final class MapEntry<K, V> implements Map.Entry<K, V> {
+        
+        final K key;
+        V value;
+        
+        MapEntry(K key, V value) {
+            this.key = key;
+            this.value = value;
+        }
+        
+        public K getKey() {
+            return key;
+        }
+
+        public V getValue() {
+            return value;
+        }
+
+        public V setValue(V v) {
+            V res = value;
+            value = v;
+            return res;
+        }
+
+        public int hashCode() {
+            return (getKey() == null ? 0 : getKey().hashCode())
+                    ^ (getValue() == null ? 0 : getValue().hashCode());
+        }
+        
+        public boolean equals(Object object) {
+            if (this == object) {
+                return true;
+            }
+            if (object instanceof Map.Entry) {
+                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
+                return (getKey() == null ? entry.getKey() == null : getKey().equals(entry
+                        .getKey()))
+                        && (getValue() == null ? entry.getValue() == null : getValue()
+                                .equals(entry.getValue()));
+            }
+            return false;
+        }
+    }
+    
+    transient ArrayList<MapEntry<K, V>> entries = new ArrayList<MapEntry<K, V>>();
+    transient int modCnt;
+
+    private final Comparator<? super K> comparator;
+    
+    class SubMap extends java.util.AbstractMap<K, V> 
+            implements SortedMap<K, V>, Cloneable {     
+
+        final boolean hasStart, hasEnd;
+        final K start, end;
+        
+        SubMap(boolean hasFirst, K first, boolean hasLast, K last) {
+            this.hasStart = hasFirst;
+            this.start = first;
+            this.hasEnd = hasLast;
+            this.end = last;
+            if (hasStart && hasEnd && compare(start, end) >= 0) {
+                throw new IllegalArgumentException();
+            }
+        }
+        
+        @Override
+        public Set<java.util.Map.Entry<K, V>> entrySet() {
+            return new AbstractSet<Entry<K,V>> () {             
+                
+                @Override
+                public Iterator<java.util.Map.Entry<K, V>> iterator() {
+                    return new Iterator<Entry<K,V>>() {
+                        int modCnt = RefSortedMap.this.modCnt;
+                        int offset = SubMap.this.size() > 0 ? 
+                                bsearch(SubMap.this.firstKey()) - 1 :
+                                entries.size(); 
+                        
+                        public boolean hasNext() {
+                            if (modCnt != RefSortedMap.this.modCnt) {
+                                throw new ConcurrentModificationException();
+                            }                           
+                            return offset + 1 < entries.size() 
+                                && isInRange(entries.get(offset + 1).getKey());
+                        }
+
+                        public Map.Entry<K, V> next() {
+                            if (modCnt != RefSortedMap.this.modCnt) {
+                                throw new ConcurrentModificationException();
+                            }
+                            if (!hasNext()) {
+                                throw new NoSuchElementException();
+                            }
+                            offset++;
+                            return entries.get(offset);
+                        }
+
+                        public void remove() {
+                            if (modCnt != RefSortedMap.this.modCnt) {
+                                throw new ConcurrentModificationException();
+                            }
+                            modCnt++;
+                            RefSortedMap.this.modCnt++;
+                            RefSortedMap.this.entries.remove(offset);
+                            offset--;
+                        }
+                        
+                    };
+                }
+
+                @Override
+                public int size() {
+                    try {
+                        int lastIdx = bsearch(SubMap.this.lastKey());
+                        int firstIdx = bsearch(SubMap.this.firstKey()); 
+                        return lastIdx - firstIdx + 1;
+                    } catch (NoSuchElementException e) {
+                        return 0;
+                    } catch (ArrayIndexOutOfBoundsException e) {
+                        return 0;
+                    }                   
+                }
+                
+            };
+        }
+
+        public Comparator<? super K> comparator() {
+            return RefSortedMap.this.comparator();
+        }
+
+        public K firstKey() {
+            if (!hasStart) {
+                K res = RefSortedMap.this.firstKey();
+                if (!isInRange(res)) {
+                    throw new NoSuchElementException();
+                }
+                return res;
+            }
+            int idx = bsearch(start);
+            if (idx >= 0) {
+                return start;
+            }
+            if (-idx - 1 >= entries.size() || !isInRange(entries.get(-idx - 1).getKey())) { 
+                throw new NoSuchElementException();
+            }
+            return entries.get(-idx - 1).getKey();
+        }
+
+        public SortedMap<K, V> headMap(K key) {
+            if (!isInRange(key)) {
+                throw new IllegalArgumentException();
+            }
+            return new SubMap(hasStart, start, true, key);
+        }
+
+        public K lastKey() {
+            if (!hasEnd) {
+                K res = RefSortedMap.this.lastKey();
+                if (!isInRange(res)) {
+                    throw new NoSuchElementException();
+                }
+                return res;
+            }
+            int idx = bsearch(end);
+            idx = idx >= 0 ? idx - 1 : -idx -2; 
+            if (idx < 0 || !isInRange(entries.get(idx).getKey())) {
+                throw new NoSuchElementException();
+            }
+            return entries.get(idx).getKey();
+        }
+
+        public SortedMap<K, V> subMap(K startKey, K endKey) {
+            if (!isInRange(startKey)) {
+                throw new IllegalArgumentException();
+            }
+            if (!isInRange(endKey)) {
+                throw new IllegalArgumentException();
+            }
+            return new SubMap(true, startKey, true, endKey);
+        }
+
+        public SortedMap<K, V> tailMap(K key) {
+            if (!isInRange(key)) {
+                throw new IllegalArgumentException();
+            }
+            return new SubMap(true, key, hasEnd, end);
+        }
+        
+        private boolean isInRange(K key) {
+            if (hasStart && compare(key, start) < 0) {
+                    return false;
+            }
+            if (hasEnd && compare(key, end) >= 0) {
+                    return false;
+            }
+            return true;
+        }
+        
+    }       
+    
+    public RefSortedMap() {
+        this((Comparator<? super K>) null);
+    }
+
+    @SuppressWarnings("unchecked")
+    public int compare(K start, K end) {        
+        return comparator != null ? comparator.compare(start, end) 
+                : ((Comparable<K>) start).compareTo(end);
+    }
+
+    @SuppressWarnings("unchecked")
+    public RefSortedMap(Comparator<? super K> comparator) {
+        this.comparator = comparator;
+        cmp = createCmp();
+    }
+
+    public RefSortedMap(Map<? extends K, ? extends V> map) {
+        this();
+        putAll(map);
+    }
+
+    public RefSortedMap(SortedMap<K, ? extends V> map) {
+        this(map.comparator());
+        putAll(map);
+    }
+
+    public Comparator<? super K> comparator() {
+        return comparator;
+    }
+
+    public Set<Map.Entry<K, V>> entrySet() {
+        return tailMap(firstKey()).entrySet();
+    }
+
+    public K firstKey() {
+        return entries.get(0).getKey();
+    }
+
+    public SortedMap<K, V> headMap(K key) {     
+        return new SubMap(false, null, true, key);
+    }
+
+    public Set<K> keySet() {
+        return tailMap(firstKey()).keySet();
+    }
+
+    public K lastKey() {
+        return entries.get(entries.size() - 1).getKey();
+    }
+
+    public SortedMap<K, V> subMap(K startKey, K endKey) {
+        return new SubMap(true, startKey, true, endKey);
+    }
+
+    public SortedMap<K, V> tailMap(K key) {
+        return new SubMap(true, key, false, null);
+    }
+
+    public Collection<V> values() {
+        return tailMap(firstKey()).values();
+    }
+
+    public void clear() {
+        entries.clear();
+    }
+
+    public boolean containsKey(Object arg0) {
+        return bsearch(arg0) >= 0;
+    }
+
+    public boolean containsValue(Object arg0) {
+        for (V v : values()) {
+            if (arg0.equals(v)) {
+                return true;
+            }
+        }
+        return false;
+    }
+    
+    @SuppressWarnings("unchecked")
+    public V get(Object arg0) {
+        int idx = bsearch(arg0);
+        return idx >= 0 ? entries.get(idx).getValue() : null;
+    }
+
+    public boolean isEmpty() {
+        return entries.isEmpty();
+    }
+
+    public V put(K arg0, V arg1) {
+        modCnt++;
+        int idx = bsearch(arg0);
+        if (idx >= 0) {         
+            return entries.get(idx).setValue(arg1);
+        }
+        entries.add(-idx -1, new MapEntry<K, V>(arg0, arg1));
+        return null;
+    }
+
+    public void putAll(Map<? extends K, ? extends V> arg0) {
+        for (Map.Entry<? extends K, ? extends V> e : arg0.entrySet()) {
+            put(e.getKey(), e.getValue());
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    public V remove(Object arg0) {
+        modCnt++;
+        int idx = bsearch(arg0);
+        if (idx < 0) {
+            return null;
+        }       
+        return entries.remove(idx).getValue();
+    }
+    
+    transient private Comparator<MapEntry<K, V>> cmp = createCmp();
+    
+    Comparator<MapEntry<K, V>> createCmp() {
+        return new Comparator<MapEntry<K, V>>() {
+    
+            public int compare(MapEntry<K, V> arg0, MapEntry<K, V> arg1) {
+                return RefSortedMap.this.compare(arg0.getKey(), arg1.getKey());
+            }
+            
+        };
+    }
+
+    @SuppressWarnings("unchecked")
+    private int bsearch(Object arg0) {
+        return Collections.binarySearch(entries, new MapEntry<K, V>((K) arg0, null), cmp);
+    }
+
+    public int size() {
+        return entries.size();
+    }
+    
+    public RefSortedMap<K, V> clone() {
+        return new RefSortedMap<K, V>(this);        
+    }
+    
+    private void writeObject(ObjectOutputStream stream) throws IOException {
+        stream.defaultWriteObject();
+        stream.writeInt(size());
+        for (Map.Entry<K, V> e : entrySet()) {
+            stream.writeObject(e.getKey());
+            stream.writeObject(e.getValue());
+        }
+    }
+
+    @SuppressWarnings("unchecked")
+    private void readObject(ObjectInputStream stream) throws IOException,
+            ClassNotFoundException {
+
+        cmp = createCmp();
+        stream.defaultReadObject();
+        int size = stream.readInt();
+        entries = new ArrayList<MapEntry<K, V>>(size);
+        for (int i = 0; i < size; i++) {
+            put((K) stream.readObject(), (V) stream.readObject());
+        }
+    }
+
+}

Propchange: harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/RefSortedMap.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/SortedMapTestBase.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/SortedMapTestBase.java?rev=627476&view=auto
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/SortedMapTestBase.java (added)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/SortedMapTestBase.java Wed Feb 13 07:33:52 2008
@@ -0,0 +1,369 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package org.apache.harmony.luni.tests.java.util;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.lang.reflect.Method;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Random;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.TreeMap;
+
+import junit.framework.TestCase;
+
+public abstract class SortedMapTestBase extends TestCase {
+    
+    final int N = 1000;
+    final int TRIES = 100; 
+    
+    SortedMap<Integer, Integer> map;
+    SortedMap<Integer, Integer> ref;
+    
+    Random rnd;
+    
+    protected void setUp() throws Exception {
+        rnd = new Random(-1);
+        for (int i = 0;  i < N ; i++) {
+            ref.put(rnd.nextInt(N) * 2, rnd.nextBoolean() ? null : rnd.nextInt(N) * 2);
+        }
+    }
+        
+    public final void testClear() {
+        map.clear();
+        assertTrue(map.isEmpty());
+    }
+    
+    public final void testContainsKey() {
+        for (int i = 0; i < TRIES; i++) {
+            int key = rnd.nextInt(N);
+            assertEquals(ref.containsKey(key), map.containsKey(key));
+        }       
+    }
+
+    
+    public final void testContainsValue() {
+        for (int i = 0; i < TRIES; i++) {
+            int value = rnd.nextInt(N);
+            assertEquals(ref.containsValue(value), map.containsValue(value));
+        }               
+    }
+
+    
+    public final void testEntrySet() {
+        Set<Map.Entry<Integer,Integer>> refSet = ref.entrySet();
+        Set<Map.Entry<Integer,Integer>> mapSet = map.entrySet();
+        for (Map.Entry<Integer,Integer> e : refSet) {
+            assertTrue(mapSet.contains(e));
+        }
+        for (Map.Entry<Integer,Integer> e : mapSet) {
+            assertTrue(refSet.contains(e));
+        }
+        assertEquals(ref.entrySet(), map.entrySet());
+    }
+
+    
+    public final void testGet() {
+        for (int i = 0; i < TRIES; i++) {
+            int key = rnd.nextInt(N);
+            assertEquals(ref.get(key), map.get(key));
+        }       
+    }
+
+    
+    public final void testKeySet() {
+        assertEquals(ref.keySet(), map.keySet());
+        Iterator<Integer> i = ref.keySet().iterator();
+        Iterator<Integer> j = map.keySet().iterator();
+        while (i.hasNext()) {           
+            assertEquals(i.next(), j.next());
+            if (rnd.nextBoolean()) {
+                j.remove();
+                i.remove();
+            }
+        }
+    }
+
+    
+    public final void testPut() {
+        for (int i = 0; i < TRIES; i++) {
+            int key = rnd.nextInt(N);
+            int value = rnd.nextInt(N);
+            assertEquals(ref.put(key, value), map.put(key, value));
+            assertEquals(ref.get(key), map.get(key));
+            assertEquals(ref, map);
+        }       
+    }
+
+    public final void testPut0() {
+        ref.clear();
+        map.clear();
+        for (int i = 0; i < N; i++) {
+            int key = rnd.nextInt(N);
+            int value = rnd.nextInt(N);
+            assertEquals(ref.put(key, value), map.put(key, value));
+            assertEquals(ref.get(key), map.get(key));
+        }       
+    }   
+    
+    public final void testPutAll() {
+        Map<Integer, Integer> mixin = new HashMap<Integer, Integer>(TRIES);
+        for (int i = 0; i < TRIES; i++) {
+            mixin.put(rnd.nextInt(N), rnd.nextInt(N));          
+        }
+        ref.putAll(mixin);
+        map.putAll(mixin);
+        assertEquals(ref, map);
+    }
+
+    
+    public final void testRemove() {
+        for (int i = 0; i < N; i++) {
+            int key = rnd.nextInt(N);
+            assertEquals(ref.remove(key), map.remove(key));
+            if (i % (N / TRIES) == 0) {
+                assertEquals(ref, map);
+            }
+        }       
+    }
+
+    public final void testRemove0() {
+        while (!ref.isEmpty()) {
+            int key = ref.tailMap((ref.firstKey() + ref.lastKey()) / 2)
+                .firstKey();
+            assertEquals(ref.remove(key), map.remove(key));
+        }       
+    }
+    
+    public final void testSize() {
+        assertEquals(ref.size(), map.size());
+    }
+
+    
+    public final void testValues() {
+        assertEquals(ref.values().size(), map.values().size());
+        assertTrue(ref.values().containsAll(map.values()));
+        assertTrue(map.values().containsAll(ref.values()));
+        
+        Iterator<Integer> i = ref.values().iterator();
+        Iterator<Integer> j = map.values().iterator();
+        while (i.hasNext()) {
+            assertEquals(i.next(), j.next());
+            if (rnd.nextBoolean()) {
+                j.remove();
+                i.remove();
+            }
+        }
+    }
+                
+    public final void testComparator() {
+        assertEquals(ref.comparator(), map.comparator());
+    }
+
+    
+    public final void testFirstKey() {
+        assertEquals(ref.firstKey(), map.firstKey());
+    }
+
+    
+    public final void testHeadMap() {
+        for (int i = 0; i < TRIES; i++) {
+            int key = rnd.nextInt(N);
+            checkSubMap(ref.headMap(key), map.headMap(key));        
+        }
+        checkSubMap(ref.headMap(-1), map.headMap(-1));      
+    }
+    
+    public final void testLastKey() {
+        assertEquals(ref.lastKey(), map.lastKey());
+    }
+        
+    public final void testSubMap() {
+        for (int i = 0; i < TRIES; i++) {
+            int key0 = rnd.nextInt(N/2);
+            int key1 = rnd.nextInt(N/2) + N/2;
+            if (ref.comparator() != null && 
+                    ref.comparator().compare(key0, key1) > 0) {
+                
+                int tmp = key0;
+                key0 = key1;
+                key1 = tmp;
+            }
+            checkSubMap(ref.subMap(key0, key1), map.subMap(key0, key1));
+        }
+        boolean caught = false;
+        try {
+            if (ref.comparator() != null && ref.comparator().compare(100, 0) < 0) {
+                map.subMap(0, 100);
+            } else {
+                map.subMap(100, 0);             
+            }           
+        } catch (IllegalArgumentException e) {
+            caught = true;
+        }
+        assertTrue(caught);
+        
+        int firstKey = ref.firstKey();
+        Map.Entry<Integer, Integer> refE = ref.entrySet().iterator().next();
+        Map.Entry<Integer, Integer> mapE = map.entrySet().iterator().next();
+        mapE.setValue(-1);
+        refE.setValue(-1);
+        assertEquals(ref.get(firstKey), map.get(firstKey));
+    }
+
+    
+    public final void testTailMap() {
+        for (int i = 0; i < TRIES; i++) {
+            int key = rnd.nextInt(2 * N);
+            checkSubMap(ref.tailMap(key), map.tailMap(key));
+        }
+        checkSubMap(ref.tailMap(2 * N + 1), map.tailMap(2 * N + 1));
+    }
+
+    
+    public final void testHashCode() {
+        assertEquals(ref.hashCode(), map.hashCode());
+    }
+    
+    public final void testEqualsObject() {
+        assertTrue(map.equals(ref));
+        map.put(N + 1, N + 1);
+        assertFalse(map.equals(ref));
+    }
+
+    
+    public final void testIsEmpty() {
+        assertEquals(ref.isEmpty(), map.isEmpty());
+    }
+    
+    public final void testIsEmpty2() {
+        TreeMap<String, String> map = new TreeMap<String, String>();
+        map.put("one", "1");
+        assertEquals("size should be one", 1, map.size());
+        map.clear();
+        assertEquals("size should be zero", 0, map.size());
+        assertTrue("Should not have entries", !map.entrySet().iterator()
+                .hasNext());
+
+        map.put("one", "1");
+        assertEquals("size should be one", 1, map.size());
+        map.remove("one");
+        assertEquals("size should be zero", 0, map.size());
+        assertTrue("Should not have entries", !map.entrySet().iterator()
+                .hasNext());
+
+        map.clear();
+        map.put("0", "1");
+        map.clear();
+        assertTrue(map.isEmpty());
+        assertFalse(map.entrySet().iterator().hasNext());
+        assertFalse(map.keySet().iterator().hasNext());
+        assertFalse(map.values().iterator().hasNext());
+    }
+    
+    public final void testToString() {
+        assertEquals(ref.toString(), map.toString());
+    }
+    
+    private void checkSubMap(SortedMap<Integer, Integer> ref, 
+            SortedMap<Integer, Integer> map) {
+        
+        assertEquals(ref.size(), map.size());
+        assertEquals(ref, map);
+        assertEquals(ref.isEmpty(), map.isEmpty());
+        if (!ref.isEmpty()) {
+            assertEquals(ref.firstKey(), map.firstKey());
+            assertEquals(ref.lastKey(), map.lastKey());
+            
+            testViews(ref, map);
+        } else {
+            boolean caught = false;
+            try {
+                map.firstKey();
+            } catch (NoSuchElementException e) {                
+                caught = true;
+            }
+            caught = false;
+            try {
+                map.lastKey();
+            } catch (NoSuchElementException e) {                
+                caught = true;
+            }
+            assertTrue(caught);
+        }
+        
+    }
+    
+    public final void testViews() {
+        testViews(ref, map);
+    }
+    
+    private void testViews(SortedMap<Integer, Integer> ref, SortedMap<Integer, Integer> map) {
+        assertEquals(ref.keySet().size(), map.keySet().size());
+        assertEquals(ref.keySet(), map.keySet());
+        compareIterators(ref.keySet(), map.keySet());
+
+        assertEquals(ref.values().size(), map.values().size());
+        compareIterators(ref.values(), map.values());
+        
+        assertEquals(ref.entrySet(), map.entrySet());
+        compareIterators(ref.entrySet(), map.entrySet());
+    }
+
+    private void compareIterators(Collection ref, Collection map) {
+        Iterator i = ref.iterator();
+        Iterator j = map.iterator();
+        while (i.hasNext()) {
+            assertEquals(i.next(), j.next());
+            if (rnd.nextBoolean()) {
+                j.remove();
+                i.remove();             
+                assertEquals(ref.size(), map.size());
+            }
+        }
+    }
+    
+    @SuppressWarnings("unchecked")
+    public final void testSerialization() throws IOException, ClassNotFoundException {
+        ByteArrayOutputStream baos = new ByteArrayOutputStream();
+        ObjectOutputStream oos = new ObjectOutputStream(baos);
+        oos.writeObject(map);
+        oos.close();
+        ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(baos.toByteArray()));
+        Object read = ois.readObject();
+        assertEquals(ref, read);
+    }
+    
+    public final void testClone() throws Exception {
+        Method refClone = ref.getClass().getMethod("clone", null);
+        Method mapClone = map.getClass().getMethod("clone", null);
+        SortedMap<Integer, Integer> map2 = (SortedMap<Integer, Integer>) mapClone.invoke(map, null);
+        assertEquals(refClone.invoke(ref, null), map2);
+        map2.remove(map2.lastKey());
+        assertFalse(ref.equals(map2));
+    }
+    
+}

Propchange: harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/SortedMapTestBase.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/TreeMapRndTest.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/TreeMapRndTest.java?rev=627476&view=auto
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/TreeMapRndTest.java (added)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/TreeMapRndTest.java Wed Feb 13 07:33:52 2008
@@ -0,0 +1,28 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package org.apache.harmony.luni.tests.java.util;
+
+import java.util.TreeMap;
+
+public class TreeMapRndTest extends SortedMapTestBase {
+    protected void setUp() throws Exception {
+        ref = new RefSortedMap<Integer, Integer>();
+        super.setUp();
+        map = new TreeMap<Integer, Integer>(ref);
+    }
+}

Propchange: harmony/enhanced/classlib/trunk/modules/luni/src/test/api/common/org/apache/harmony/luni/tests/java/util/TreeMapRndTest.java
------------------------------------------------------------------------------
    svn:eol-style = native