pathelementmap.go

Documentation: sigs.k8s.io/structured-merge-diff/v4/fieldpath

     1  /*
     2  Copyright 2018 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 fieldpath
    18  
    19  import (
    20  	"sort"
    21  
    22  	"sigs.k8s.io/structured-merge-diff/v4/value"
    23  )
    24  
    25  // PathElementValueMap is a map from PathElement to value.Value.
    26  //
    27  // TODO(apelisse): We have multiple very similar implementation of this
    28  // for PathElementSet and SetNodeMap, so we could probably share the
    29  // code.
    30  type PathElementValueMap struct {
    31  	valueMap PathElementMap
    32  }
    33  
    34  func MakePathElementValueMap(size int) PathElementValueMap {
    35  	return PathElementValueMap{
    36  		valueMap: MakePathElementMap(size),
    37  	}
    38  }
    39  
    40  type sortedPathElementValues []pathElementValue
    41  
    42  // Implement the sort interface; this would permit bulk creation, which would
    43  // be faster than doing it one at a time via Insert.
    44  func (spev sortedPathElementValues) Len() int { return len(spev) }
    45  func (spev sortedPathElementValues) Less(i, j int) bool {
    46  	return spev[i].PathElement.Less(spev[j].PathElement)
    47  }
    48  func (spev sortedPathElementValues) Swap(i, j int) { spev[i], spev[j] = spev[j], spev[i] }
    49  
    50  // Insert adds the pathelement and associated value in the map.
    51  // If insert is called twice with the same PathElement, the value is replaced.
    52  func (s *PathElementValueMap) Insert(pe PathElement, v value.Value) {
    53  	s.valueMap.Insert(pe, v)
    54  }
    55  
    56  // Get retrieves the value associated with the given PathElement from the map.
    57  // (nil, false) is returned if there is no such PathElement.
    58  func (s *PathElementValueMap) Get(pe PathElement) (value.Value, bool) {
    59  	v, ok := s.valueMap.Get(pe)
    60  	if !ok {
    61  		return nil, false
    62  	}
    63  	return v.(value.Value), true
    64  }
    65  
    66  // PathElementValueMap is a map from PathElement to interface{}.
    67  type PathElementMap struct {
    68  	members sortedPathElementValues
    69  }
    70  
    71  type pathElementValue struct {
    72  	PathElement PathElement
    73  	Value       interface{}
    74  }
    75  
    76  func MakePathElementMap(size int) PathElementMap {
    77  	return PathElementMap{
    78  		members: make(sortedPathElementValues, 0, size),
    79  	}
    80  }
    81  
    82  // Insert adds the pathelement and associated value in the map.
    83  // If insert is called twice with the same PathElement, the value is replaced.
    84  func (s *PathElementMap) Insert(pe PathElement, v interface{}) {
    85  	loc := sort.Search(len(s.members), func(i int) bool {
    86  		return !s.members[i].PathElement.Less(pe)
    87  	})
    88  	if loc == len(s.members) {
    89  		s.members = append(s.members, pathElementValue{pe, v})
    90  		return
    91  	}
    92  	if s.members[loc].PathElement.Equals(pe) {
    93  		s.members[loc].Value = v
    94  		return
    95  	}
    96  	s.members = append(s.members, pathElementValue{})
    97  	copy(s.members[loc+1:], s.members[loc:])
    98  	s.members[loc] = pathElementValue{pe, v}
    99  }
   100  
   101  // Get retrieves the value associated with the given PathElement from the map.
   102  // (nil, false) is returned if there is no such PathElement.
   103  func (s *PathElementMap) Get(pe PathElement) (interface{}, bool) {
   104  	loc := sort.Search(len(s.members), func(i int) bool {
   105  		return !s.members[i].PathElement.Less(pe)
   106  	})
   107  	if loc == len(s.members) {
   108  		return nil, false
   109  	}
   110  	if s.members[loc].PathElement.Equals(pe) {
   111  		return s.members[loc].Value, true
   112  	}
   113  	return nil, false
   114  }
   115
View as plain text