Make sure the elements are sorted in an encoded annotation
diff --git a/dexlib2/src/main/java/org/jf/dexlib2/iface/Annotation.java b/dexlib2/src/main/java/org/jf/dexlib2/iface/Annotation.java
index 251ac12..7c107a4 100644
--- a/dexlib2/src/main/java/org/jf/dexlib2/iface/Annotation.java
+++ b/dexlib2/src/main/java/org/jf/dexlib2/iface/Annotation.java
@@ -55,7 +55,7 @@
      *
      * @return The type of this annotation
      */
-    @Nonnull String getType();
+    @Nonnull @Override String getType();
 
     /**
      * Gets a set of the name/value elements associated with this annotation.
@@ -64,7 +64,7 @@
      *
      * @return A set of AnnotationElements
      */
-    @Nonnull Set<? extends AnnotationElement> getElements();
+    @Nonnull @Override Set<? extends AnnotationElement> getElements();
 
     /**
      * Returns a hashcode for this Annotation.
diff --git a/dexlib2/src/main/java/org/jf/dexlib2/writer/DexWriter.java b/dexlib2/src/main/java/org/jf/dexlib2/writer/DexWriter.java
index dd6ec9f..0650ab3 100644
--- a/dexlib2/src/main/java/org/jf/dexlib2/writer/DexWriter.java
+++ b/dexlib2/src/main/java/org/jf/dexlib2/writer/DexWriter.java
@@ -572,7 +572,6 @@
         }
     }
 
-
     private void writeAnnotationSets(@Nonnull DexDataWriter writer) throws IOException {
         writer.align();
         annotationSetSectionOffset = writer.getPosition();
diff --git a/dexlib2/src/main/java/org/jf/dexlib2/writer/EncodedValueWriter.java b/dexlib2/src/main/java/org/jf/dexlib2/writer/EncodedValueWriter.java
index 53d77b3..def326c 100644
--- a/dexlib2/src/main/java/org/jf/dexlib2/writer/EncodedValueWriter.java
+++ b/dexlib2/src/main/java/org/jf/dexlib2/writer/EncodedValueWriter.java
@@ -31,7 +31,9 @@
 
 package org.jf.dexlib2.writer;
 
+import com.google.common.collect.Ordering;
 import org.jf.dexlib2.ValueType;
+import org.jf.dexlib2.base.BaseAnnotationElement;
 import org.jf.dexlib2.iface.reference.FieldReference;
 import org.jf.dexlib2.iface.reference.MethodReference;
 
@@ -40,7 +42,8 @@
 import java.util.Collection;
 
 public abstract class EncodedValueWriter<StringKey, TypeKey, FieldRefKey extends FieldReference,
-        MethodRefKey extends MethodReference, AnnotationElement, EncodedValue> {
+        MethodRefKey extends MethodReference, AnnotationElement extends org.jf.dexlib2.iface.AnnotationElement,
+        EncodedValue> {
     @Nonnull private final DexDataWriter writer;
     @Nonnull private final StringSection<StringKey, ?> stringSection;
     @Nonnull private final TypeSection<?, TypeKey, ?> typeSection;
@@ -70,7 +73,11 @@
         writer.writeEncodedValueHeader(ValueType.ANNOTATION, 0);
         writer.writeUleb128(typeSection.getItemIndex(annotationType));
         writer.writeUleb128(elements.size());
-        for (AnnotationElement element: elements) {
+
+        Collection<? extends AnnotationElement> sortedElements = Ordering.from(BaseAnnotationElement.BY_NAME)
+                .immutableSortedCopy(elements);
+
+        for (AnnotationElement element: sortedElements) {
             writer.writeUleb128(stringSection.getItemIndex(annotationSection.getElementName(element)));
             writeEncodedValue(annotationSection.getElementValue(element));
         }
diff --git a/dexlib2/src/test/java/org/jf/dexlib2/writer/DexWriterTest.java b/dexlib2/src/test/java/org/jf/dexlib2/writer/DexWriterTest.java
index 66abe06..8ba975a 100644
--- a/dexlib2/src/test/java/org/jf/dexlib2/writer/DexWriterTest.java
+++ b/dexlib2/src/test/java/org/jf/dexlib2/writer/DexWriterTest.java
@@ -41,10 +41,12 @@
 import org.jf.dexlib2.iface.Annotation;
 import org.jf.dexlib2.iface.AnnotationElement;
 import org.jf.dexlib2.iface.ClassDef;
+import org.jf.dexlib2.iface.value.AnnotationEncodedValue;
 import org.jf.dexlib2.immutable.ImmutableAnnotation;
 import org.jf.dexlib2.immutable.ImmutableAnnotationElement;
 import org.jf.dexlib2.immutable.ImmutableClassDef;
 import org.jf.dexlib2.immutable.ImmutableDexFile;
+import org.jf.dexlib2.immutable.value.ImmutableAnnotationEncodedValue;
 import org.jf.dexlib2.immutable.value.ImmutableNullEncodedValue;
 import org.jf.dexlib2.writer.io.MemoryDataStore;
 import org.jf.dexlib2.writer.pool.DexPool;
@@ -87,4 +89,48 @@
         Assert.assertEquals("blah", dbElements.get(0).getName());
         Assert.assertEquals("zabaglione", dbElements.get(1).getName());
     }
+
+    @Test
+    public void testEncodedAnnotationElementOrder() {
+        // Elements are out of order wrt to the element name
+        ImmutableSet<ImmutableAnnotationElement> encodedElements =
+                ImmutableSet.of(new ImmutableAnnotationElement("zabaglione", ImmutableNullEncodedValue.INSTANCE),
+                        new ImmutableAnnotationElement("blah", ImmutableNullEncodedValue.INSTANCE));
+
+        ImmutableAnnotationEncodedValue encodedAnnotations =
+                new ImmutableAnnotationEncodedValue("Lan/encoded/annotation", encodedElements);
+
+        ImmutableSet<ImmutableAnnotationElement> elements =
+                ImmutableSet.of(new ImmutableAnnotationElement("encoded_annotation", encodedAnnotations));
+
+        ImmutableAnnotation annotation = new ImmutableAnnotation(AnnotationVisibility.RUNTIME,
+                "Lorg/test/anno;", elements);
+
+        ImmutableClassDef classDef = new ImmutableClassDef("Lorg/test/blah;",
+                0, "Ljava/lang/Object;", null, null, ImmutableSet.of(annotation), null, null);
+
+        MemoryDataStore dataStore = new MemoryDataStore();
+
+        try {
+            DexPool.writeTo(dataStore, new ImmutableDexFile(ImmutableSet.of(classDef)));
+        } catch (IOException ex) {
+            throw new RuntimeException(ex);
+        }
+
+        DexBackedDexFile dexFile = new DexBackedDexFile(new Opcodes(15, false), dataStore.getData());
+        ClassDef dbClassDef = Iterables.getFirst(dexFile.getClasses(), null);
+        Assert.assertNotNull(dbClassDef);
+        Annotation dbAnnotation = Iterables.getFirst(dbClassDef.getAnnotations(), null);
+        Assert.assertNotNull(dbAnnotation);
+
+        AnnotationElement element = Iterables.getFirst(dbAnnotation.getElements(), null);
+        AnnotationEncodedValue dbAnnotationEncodedValue = (AnnotationEncodedValue)element.getValue();
+
+        List<AnnotationElement> dbElements = Lists.newArrayList(dbAnnotationEncodedValue.getElements());
+
+        // Ensure that the elements were written out in sorted order
+        Assert.assertEquals(2, dbElements.size());
+        Assert.assertEquals("blah", dbElements.get(0).getName());
+        Assert.assertEquals("zabaglione", dbElements.get(1).getName());
+    }
 }