Matteo Scandolo | a428586 | 2020-12-01 18:10:10 -0800 | [diff] [blame] | 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 | } |