1 /* 2 Copyright 2019 The Kubernetes Authors. 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 package value 18 19 // List represents a list object. 20 type List interface { 21 // Length returns how many items can be found in the map. 22 Length() int 23 // At returns the item at the given position in the map. It will 24 // panic if the index is out of range. 25 At(int) Value 26 // AtUsing uses the provided allocator and returns the item at the given 27 // position in the map. It will panic if the index is out of range. 28 // The returned Value should be given back to the Allocator when no longer needed 29 // by calling Allocator.Free(Value). 30 AtUsing(Allocator, int) Value 31 // Range returns a ListRange for iterating over the items in the list. 32 Range() ListRange 33 // RangeUsing uses the provided allocator and returns a ListRange for 34 // iterating over the items in the list. 35 // The returned Range should be given back to the Allocator when no longer needed 36 // by calling Allocator.Free(Value). 37 RangeUsing(Allocator) ListRange 38 // Equals compares the two lists, and return true if they are the same, false otherwise. 39 // Implementations can use ListEquals as a general implementation for this methods. 40 Equals(List) bool 41 // EqualsUsing uses the provided allocator and compares the two lists, and return true if 42 // they are the same, false otherwise. Implementations can use ListEqualsUsing as a general 43 // implementation for this methods. 44 EqualsUsing(Allocator, List) bool 45 } 46 47 // ListRange represents a single iteration across the items of a list. 48 type ListRange interface { 49 // Next increments to the next item in the range, if there is one, and returns true, or returns false if there are no more items. 50 Next() bool 51 // Item returns the index and value of the current item in the range. or panics if there is no current item. 52 // For efficiency, Item may reuse the values returned by previous Item calls. Callers should be careful avoid holding 53 // pointers to the value returned by Item() that escape the iteration loop since they become invalid once either 54 // Item() or Allocator.Free() is called. 55 Item() (index int, value Value) 56 } 57 58 var EmptyRange = &emptyRange{} 59 60 type emptyRange struct{} 61 62 func (_ *emptyRange) Next() bool { 63 return false 64 } 65 66 func (_ *emptyRange) Item() (index int, value Value) { 67 panic("Item called on empty ListRange") 68 } 69 70 // ListEquals compares two lists lexically. 71 // WARN: This is a naive implementation, calling lhs.Equals(rhs) is typically the most efficient. 72 func ListEquals(lhs, rhs List) bool { 73 return ListEqualsUsing(HeapAllocator, lhs, rhs) 74 } 75 76 // ListEqualsUsing uses the provided allocator and compares two lists lexically. 77 // WARN: This is a naive implementation, calling lhs.EqualsUsing(allocator, rhs) is typically the most efficient. 78 func ListEqualsUsing(a Allocator, lhs, rhs List) bool { 79 if lhs.Length() != rhs.Length() { 80 return false 81 } 82 83 lhsRange := lhs.RangeUsing(a) 84 defer a.Free(lhsRange) 85 rhsRange := rhs.RangeUsing(a) 86 defer a.Free(rhsRange) 87 88 for lhsRange.Next() && rhsRange.Next() { 89 _, lv := lhsRange.Item() 90 _, rv := rhsRange.Item() 91 if !EqualsUsing(a, lv, rv) { 92 return false 93 } 94 } 95 return true 96 } 97 98 // ListLess compares two lists lexically. 99 func ListLess(lhs, rhs List) bool { 100 return ListCompare(lhs, rhs) == -1 101 } 102 103 // ListCompare compares two lists lexically. The result will be 0 if l==rhs, -1 104 // if l < rhs, and +1 if l > rhs. 105 func ListCompare(lhs, rhs List) int { 106 return ListCompareUsing(HeapAllocator, lhs, rhs) 107 } 108 109 // ListCompareUsing uses the provided allocator and compares two lists lexically. The result will be 0 if l==rhs, -1 110 // if l < rhs, and +1 if l > rhs. 111 func ListCompareUsing(a Allocator, lhs, rhs List) int { 112 lhsRange := lhs.RangeUsing(a) 113 defer a.Free(lhsRange) 114 rhsRange := rhs.RangeUsing(a) 115 defer a.Free(rhsRange) 116 117 for { 118 lhsOk := lhsRange.Next() 119 rhsOk := rhsRange.Next() 120 if !lhsOk && !rhsOk { 121 // Lists are the same length and all items are equal. 122 return 0 123 } 124 if !lhsOk { 125 // LHS is shorter. 126 return -1 127 } 128 if !rhsOk { 129 // RHS is shorter. 130 return 1 131 } 132 _, lv := lhsRange.Item() 133 _, rv := rhsRange.Item() 134 if c := CompareUsing(a, lv, rv); c != 0 { 135 return c 136 } 137 // The items are equal; continue. 138 } 139 } 140