| 1 | package com.github.sanity.pav | |
| 2 | ||
| 3 | import java.util.* | |
| 4 | ||
| 5 | /** | |
| 6 | * A doubly-linked-list with functionality that is particularly useful for implementing the | |
| 7 | * pool-adjacent violators algorithm. Specifically, supports iterating through the list while replacing | |
| 8 | * pairs of elements in the list. | |
| 9 | */ | |
| 10 | ||
| 11 | /* | |
| 12 | Before replacement: | |
| 13 | p n | |
| 14 | A B C D | |
| 15 | | | |
| 16 | ||
| 17 | After replacement: | |
| 18 | p n | |
| 19 | A X D | |
| 20 | | | |
| 21 | */ | |
| 22 | ||
| 23 |
3
1. getNext : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList::getNext to ( if (x != null) null else throw new RuntimeException ) → SURVIVED 2. getPrevious : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList::getPrevious to ( if (x != null) null else throw new RuntimeException ) → KILLED 3. getValue : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList::getValue to ( if (x != null) null else throw new RuntimeException ) → KILLED |
class PairSubstitutingDoublyLinkedList<V>(var value: V, var previous: PairSubstitutingDoublyLinkedList<V>? = null, var next: PairSubstitutingDoublyLinkedList<V>? = null) { |
| 24 | ||
| 25 | companion object { | |
| 26 | ||
| 27 | fun <V> createFromList(list: List<V>): PairSubstitutingDoublyLinkedList<V> { | |
| 28 |
1
1. createFromList : negated conditional → KILLED |
if (list.isEmpty()) { |
| 29 | throw IllegalArgumentException("Cannot create PairSubstitutingDoublyLinkedList with empty list") | |
| 30 | } else { | |
| 31 | val mcArray = list.map { PairSubstitutingDoublyLinkedList(it) }.toTypedArray() | |
| 32 |
5
1. createFromList : changed conditional boundary → SURVIVED 2. createFromList : Changed increment from 1 to -1 → KILLED 3. createFromList : Replaced integer subtraction with addition → KILLED 4. createFromList : negated conditional → KILLED 5. createFromList : negated conditional → KILLED |
for (i in mcArray.indices) { |
| 33 |
2
1. createFromList : changed conditional boundary → KILLED 2. createFromList : negated conditional → KILLED |
if (i > 0) { |
| 34 |
2
1. createFromList : Replaced integer subtraction with addition → KILLED 2. createFromList : removed call to com/github/sanity/pav/PairSubstitutingDoublyLinkedList::setNext → KILLED |
mcArray[i - 1].next = mcArray[i] |
| 35 |
2
1. createFromList : Replaced integer subtraction with addition → KILLED 2. createFromList : removed call to com/github/sanity/pav/PairSubstitutingDoublyLinkedList::setPrevious → KILLED |
mcArray[i].previous = mcArray[i - 1] |
| 36 | } | |
| 37 | } | |
| 38 |
1
1. createFromList : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList$Companion::createFromList to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return mcArray[0] |
| 39 | } | |
| 40 | } | |
| 41 | } | |
| 42 | ||
| 43 | class Cursor<V>(private val after: PairSubstitutingDoublyLinkedList<V>) { | |
| 44 | val previousValue: V? | |
| 45 |
2
1. getPreviousValue : negated conditional → KILLED 2. getPreviousValue : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList$Cursor::getPreviousValue to ( if (x != null) null else throw new RuntimeException ) → KILLED |
get() = after.previous?.value |
| 46 | val nextValue: V | |
| 47 |
1
1. getNextValue : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList$Cursor::getNextValue to ( if (x != null) null else throw new RuntimeException ) → KILLED |
get() = after.value |
| 48 | } | |
| 49 | ||
| 50 | /** | |
| 51 | * Iterate through the list. The cursor is positioned between two elements unless at the first element. The | |
| 52 | * cursor can be used to retrieve the element before or after the cursor. | |
| 53 | * | |
| 54 | * The handler may optionally return a value, if it does this value will replace the elements before and after the cursor, | |
| 55 | * and the cursor will be repositioned before the new replacement element. | |
| 56 | */ | |
| 57 | fun iterate(handler: (Cursor<V>) -> V?) { | |
| 58 | var afterCursor: PairSubstitutingDoublyLinkedList<V>? = this | |
| 59 |
1
1. iterate : negated conditional → KILLED |
while (afterCursor != null) { |
| 60 | val cursor = Cursor<V>(afterCursor) | |
| 61 | val replacementValue = handler(cursor) | |
| 62 |
1
1. iterate : negated conditional → KILLED |
if (replacementValue != null) { |
| 63 | /* | |
| 64 | Before replacement: | |
| 65 | p n | |
| 66 | A B C D | |
| 67 | | | |
| 68 | ||
| 69 | After replacement: | |
| 70 | p n | |
| 71 | A X D | |
| 72 | | | |
| 73 | */ | |
| 74 | val C = afterCursor | |
| 75 | val B = afterCursor.previous | |
| 76 |
1
1. iterate : negated conditional → KILLED |
if (B == null) throw IllegalArgumentException("Cannot replace values at start of chain") |
| 77 | val D = C.next | |
| 78 | B.value = replacementValue; val X = B; | |
| 79 |
1
1. iterate : negated conditional → KILLED |
X.next = D; if (D != null) D.previous = X |
| 80 | afterCursor = X | |
| 81 | } else { | |
| 82 | afterCursor = afterCursor.next | |
| 83 | } | |
| 84 | ||
| 85 | } | |
| 86 | } | |
| 87 | ||
| 88 | /** | |
| 89 | * Transform the PairSubstitutingDoublyLinkedList into a List | |
| 90 | */ | |
| 91 | fun toArrayList(): ArrayList<V> { | |
| 92 | val arrayList = ArrayList<V>() | |
| 93 |
1
1. toArrayList : removed call to com/github/sanity/pav/PairSubstitutingDoublyLinkedList::iterate → KILLED |
iterate { |
| 94 | arrayList.add(it.nextValue) | |
| 95 |
1
1. invoke : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList$toArrayList$1::invoke to ( if (x != null) null else throw new RuntimeException ) → KILLED |
null |
| 96 | } | |
| 97 |
1
1. toArrayList : mutated return of Object value for com/github/sanity/pav/PairSubstitutingDoublyLinkedList::toArrayList to ( if (x != null) null else throw new RuntimeException ) → KILLED |
return arrayList |
| 98 | } | |
| 99 | } | |
| 100 | ||
Mutations | ||
| 23 |
1.1 2.2 3.3 |
|
| 28 |
1.1 |
|
| 32 |
1.1 2.2 3.3 4.4 5.5 |
|
| 33 |
1.1 2.2 |
|
| 34 |
1.1 2.2 |
|
| 35 |
1.1 2.2 |
|
| 38 |
1.1 |
|
| 45 |
1.1 2.2 |
|
| 47 |
1.1 |
|
| 59 |
1.1 |
|
| 62 |
1.1 |
|
| 76 |
1.1 |
|
| 79 |
1.1 |
|
| 93 |
1.1 |
|
| 95 |
1.1 |
|
| 97 |
1.1 |
|
| 103 |
1.1 |
|
| 107 |
1.1 |