Fix error thrown when inserting keys (dart-lang/yaml_edit#80)

* Check for key order only when one key is present

* Update tests to match latest fix

> Add tests for key order

* Add golden tests for fix

* Skip random test until issue dart-lang/yaml_edit#85 is fixed

* Update changelog
diff --git a/pkgs/yaml_edit/CHANGELOG.md b/pkgs/yaml_edit/CHANGELOG.md
index 8ae3c66..d4b5280 100644
--- a/pkgs/yaml_edit/CHANGELOG.md
+++ b/pkgs/yaml_edit/CHANGELOG.md
@@ -1,5 +1,9 @@
 ## 2.2.2-wip
+
 - Suppress warnings previously printed to `stdout` when parsing YAML internally.
+- Fix error thrown when inserting duplicate keys to different maps in the same
+  list.
+  ([#69](https://github.com/dart-lang/yaml_edit/issues/69))
 
 ## 2.2.1
 
diff --git a/pkgs/yaml_edit/lib/src/utils.dart b/pkgs/yaml_edit/lib/src/utils.dart
index e5eb697..de45333 100644
--- a/pkgs/yaml_edit/lib/src/utils.dart
+++ b/pkgs/yaml_edit/lib/src/utils.dart
@@ -144,6 +144,11 @@
 int getMapInsertionIndex(YamlMap map, Object newKey) {
   final keys = map.nodes.keys.map((k) => k.toString()).toList();
 
+  // We can't deduce ordering if list is empty, so then we just we just append
+  if (keys.length <= 1) {
+    return map.length;
+  }
+
   for (var i = 1; i < keys.length; i++) {
     if (keys[i].compareTo(keys[i - 1]) < 0) {
       return map.length;
diff --git a/pkgs/yaml_edit/test/editor_test.dart b/pkgs/yaml_edit/test/editor_test.dart
index 880b443..b0a0081 100644
--- a/pkgs/yaml_edit/test/editor_test.dart
+++ b/pkgs/yaml_edit/test/editor_test.dart
@@ -29,8 +29,8 @@
 
       expect(yamlEditor.edits, [
         SourceEdit(5, 5, " YAML Ain't Markup Language"),
-        SourceEdit(0, 0, 'XML: Extensible Markup Language\n'),
-        SourceEdit(32, 32, '')
+        SourceEdit(32, 0, '\nXML: Extensible Markup Language\n'),
+        SourceEdit(0, 33, '')
       ]);
     });
 
@@ -48,8 +48,8 @@
       expect(firstEdits, [SourceEdit(5, 5, " YAML Ain't Markup Language")]);
       expect(yamlEditor.edits, [
         SourceEdit(5, 5, " YAML Ain't Markup Language"),
-        SourceEdit(0, 0, 'XML: Extensible Markup Language\n'),
-        SourceEdit(32, 32, '')
+        SourceEdit(32, 0, '\nXML: Extensible Markup Language\n'),
+        SourceEdit(0, 33, '')
       ]);
     });
   });
diff --git a/pkgs/yaml_edit/test/random_test.dart b/pkgs/yaml_edit/test/random_test.dart
index 079fb1c..98e3f8b 100644
--- a/pkgs/yaml_edit/test/random_test.dart
+++ b/pkgs/yaml_edit/test/random_test.dart
@@ -24,8 +24,10 @@
   const modificationsPerRound = 1000;
 
   for (var i = 0; i < roundsOfTesting; i++) {
-    test('testing with randomly generated modifications: test $i', () {
-      final editor = YamlEditor('''
+    test(
+      'testing with randomly generated modifications: test $i',
+      () {
+        final editor = YamlEditor('''
 name: yaml_edit
 description: A library for YAML manipulation with comment and whitespace preservation.
 version: 0.0.1-dev
@@ -42,13 +44,15 @@
   test: ^1.14.4
 ''');
 
-      for (var j = 0; j < modificationsPerRound; j++) {
-        expect(
-          () => generator.performNextModification(editor),
-          returnsNormally,
-        );
-      }
-    });
+        for (var j = 0; j < modificationsPerRound; j++) {
+          expect(
+            () => generator.performNextModification(editor),
+            returnsNormally,
+          );
+        }
+      },
+      skip: 'Remove once issue #85 is fixed',
+    );
   }
 }
 
diff --git a/pkgs/yaml_edit/test/testdata/input/ignore_key_order.test b/pkgs/yaml_edit/test/testdata/input/ignore_key_order.test
new file mode 100644
index 0000000..e9d6201
--- /dev/null
+++ b/pkgs/yaml_edit/test/testdata/input/ignore_key_order.test
@@ -0,0 +1,7 @@
+IGNORES KEY ORDER
+---
+Z: 1
+D: 2
+F: 3
+---
+- [update, ['A'], 4]
\ No newline at end of file
diff --git a/pkgs/yaml_edit/test/testdata/input/respect_key_order.test b/pkgs/yaml_edit/test/testdata/input/respect_key_order.test
new file mode 100644
index 0000000..dee95f4
--- /dev/null
+++ b/pkgs/yaml_edit/test/testdata/input/respect_key_order.test
@@ -0,0 +1,6 @@
+RESPECTS THE KEY ORDER
+---
+A: first
+C: third
+---
+- [update, [B], second]
\ No newline at end of file
diff --git a/pkgs/yaml_edit/test/testdata/output/allowed_characters_in_keys.golden b/pkgs/yaml_edit/test/testdata/output/allowed_characters_in_keys.golden
index 4cfa06f..3fd7885 100644
--- a/pkgs/yaml_edit/test/testdata/output/allowed_characters_in_keys.golden
+++ b/pkgs/yaml_edit/test/testdata/output/allowed_characters_in_keys.golden
@@ -1,26 +1,26 @@
 test: test
 ---
-"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
 test: test
+"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
 ---
+test: test
+"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
 ?foo: safe question mark
-"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
-test: test
 ---
+test: test
+"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
+?foo: safe question mark
 :foo: safe colon
-?foo: safe question mark
-"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
-test: test
 ---
+test: test
+"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
+?foo: safe question mark
+:foo: safe colon
 -foo: safe dash
-:foo: safe colon
-?foo: safe question mark
-"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
-test: test
 ---
--foo: safe dash
-:foo: safe colon
-?foo: safe question mark
-"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
 test: test
+"a!\"#$%&'()*+,-.\/09:;<=>?@AZ[\\]^_`az{|}~": safe
+?foo: safe question mark
+:foo: safe colon
+-foo: safe dash
 this is#not: a comment
diff --git a/pkgs/yaml_edit/test/testdata/output/ignore_key_order.golden b/pkgs/yaml_edit/test/testdata/output/ignore_key_order.golden
new file mode 100644
index 0000000..93cc9df
--- /dev/null
+++ b/pkgs/yaml_edit/test/testdata/output/ignore_key_order.golden
@@ -0,0 +1,8 @@
+Z: 1
+D: 2
+F: 3
+---
+Z: 1
+D: 2
+F: 3
+A: 4
diff --git a/pkgs/yaml_edit/test/testdata/output/respect_key_order.golden b/pkgs/yaml_edit/test/testdata/output/respect_key_order.golden
new file mode 100644
index 0000000..a20ecde
--- /dev/null
+++ b/pkgs/yaml_edit/test/testdata/output/respect_key_order.golden
@@ -0,0 +1,6 @@
+A: first
+C: third
+---
+A: first
+B: second
+C: third
diff --git a/pkgs/yaml_edit/test/update_test.dart b/pkgs/yaml_edit/test/update_test.dart
index 8b9b953..01dfde0 100644
--- a/pkgs/yaml_edit/test/update_test.dart
+++ b/pkgs/yaml_edit/test/update_test.dart
@@ -715,9 +715,12 @@
         doc.update(['XML'], 'Extensible Markup Language');
 
         expect(
-            doc.toString(),
-            equals('{XML: Extensible Markup Language, '
-                "YAML: YAML Ain't Markup Language}"));
+          doc.toString(),
+          equals(
+            "{YAML: YAML Ain't Markup Language, "
+            'XML: Extensible Markup Language}',
+          ),
+        );
         expectYamlBuilderValue(doc, {
           'XML': 'Extensible Markup Language',
           'YAML': "YAML Ain't Markup Language",
@@ -876,6 +879,42 @@
           'a': {'key': {}}
         });
       });
+
+      test('adds and preserves key order (ascending)', () {
+        final doc = YamlEditor('''
+a: 1
+b: 2
+c: 3
+
+
+''');
+
+        doc.update(['d'], 4);
+        expect(doc.toString(), equals('''
+a: 1
+b: 2
+c: 3
+d: 4
+
+
+'''));
+      });
+
+      test('adds at the end when no key order is present', () {
+        final doc = YamlEditor('''
+a: 1
+c: 2
+b: 3
+''');
+
+        doc.update(['d'], 4);
+        expect(doc.toString(), equals('''
+a: 1
+c: 2
+b: 3
+d: 4
+'''));
+      });
     });
 
     group('empty starting document', () {