bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/AbstractOffsetMap.java

   1 /*
   2  * Copyright (c) 2018 AT&T Intellectual Property. All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.protocol.bgp.mode.impl;
   9
  10 import static com.google.common.base.Preconditions.checkArgument;
  11
  12 import com.google.common.annotations.Beta;
  13 import com.google.common.collect.ImmutableSet;
  14 import com.google.common.collect.ImmutableSet.Builder;
  15 import java.lang.reflect.Array;
  16 import java.util.Arrays;
  17 import java.util.Comparator;
  18 import org.opendaylight.yangtools.concepts.Immutable;
  19 import org.slf4j.Logger;
  20 import org.slf4j.LoggerFactory;
  21
  22 /**
  23  * A map maintaining a set of values in an external array corresponding to a set of keys. This class is expected to be
  24  * used as a template, i.e. users subclass it to a concrete map and use exclusively that class to access the
  25  * functionality.
  26  */
  27 @Beta
  28 public abstract class AbstractOffsetMap<K extends Immutable & Comparable<K>, T extends AbstractOffsetMap<K, T>> {
  29     private static final Logger LOG = LoggerFactory.getLogger(AbstractOffsetMap.class);
  30     private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
  31
  32     private final K[] keys;
  33
  34     protected AbstractOffsetMap(final K[] emptyKeys, final Comparator<K> comparator, final ImmutableSet<K> routerIds) {
  35         final K[] array = routerIds.toArray(emptyKeys);
  36         Arrays.sort(array, comparator);
  37         this.keys = array;
  38     }
  39
  40     public final K getKey(final int offset) {
  41         return this.keys[offset];
  42     }
  43
  44     public final int offsetOf(final K key) {
  45         return Arrays.binarySearch(keys, key, comparator());
  46     }
  47
  48     public final boolean isEmpty() {
  49         return keys.length == 0;
  50     }
  51
  52     public final int size() {
  53         return keys.length;
  54     }
  55
  56     public final T with(final K key) {
  57         // TODO: we could make this faster if we had an array-backed Set and requiring
  58         //       the caller to give us the result of offsetOf() -- as that indicates
  59         //       where to insert the new routerId while maintaining the sorted nature
  60         //       of the array
  61         final Builder<K> builder = ImmutableSet.builderWithExpectedSize(size() + 1);
  62         builder.add(keys);
  63         builder.add(key);
  64         return instanceForKeys(builder.build());
  65     }
  66
  67     public final T without(final K key) {
  68         final ImmutableSet<K> set;
  69         final int index = indexOf(key);
  70         if (index < 0) {
  71             LOG.trace("Router key {} not found", key);
  72             set = ImmutableSet.of();
  73         } else {
  74             set = ImmutableSet.copyOf(removeValue(keys, index, emptyKeys()));
  75         }
  76         return instanceForKeys(set);
  77     }
  78
  79     public final <C> C getValue(final C[] array, final int offset) {
  80         checkAccessOffest(offset);
  81         return array[offset];
  82     }
  83
  84     public final <C> void setValue(final C[] array, final int offset, final C value) {
  85         checkAccessOffest(offset);
  86         array[offset] = value;
  87     }
  88
  89     public final <C> C[] expand(final T oldOffsets, final C[] oldArray, final int offset) {
  90         @SuppressWarnings("unchecked")
  91         final C[] ret = (C[]) Array.newInstance(oldArray.getClass().getComponentType(), keys.length);
  92
  93         System.arraycopy(oldArray, 0, ret, 0, offset);
  94         System.arraycopy(oldArray, offset, ret, offset + 1, oldOffsets.size() - offset);
  95         return ret;
  96     }
  97
  98     public final <C> C[] removeValue(final C[] oldArray, final int offset, final C[] emptyArray) {
  99         checkNegativeOffset(offset);
 100         final int length = oldArray.length;
 101         checkArgument(offset < keys.length, INVALIDOFFSET, offset, length);
 102
 103         final int newLength = length - 1;
 104         if (newLength == 0) {
 105             checkArgument(emptyArray.length == 0);
 106             return emptyArray;
 107         }
 108
 109         @SuppressWarnings("unchecked")
 110         final C[] ret = (C[]) Array.newInstance(oldArray.getClass().getComponentType(), newLength);
 111         System.arraycopy(oldArray, 0, ret, 0, offset);
 112         if (offset < newLength) {
 113             System.arraycopy(oldArray, offset + 1, ret, offset, newLength - offset);
 114         }
 115
 116         return ret;
 117     }
 118
 119     protected abstract Comparator<K> comparator();
 120
 121     protected abstract K[] emptyKeys();
 122
 123     protected abstract T instanceForKeys(ImmutableSet<K> newKeys);
 124
 125     private int indexOf(final K key) {
 126         for (int i = 0; i < keys.length; i++) {
 127             if (key.equals(keys[i])) {
 128                 return i;
 129             }
 130         }
 131         return -1;
 132     }
 133
 134     private void checkAccessOffest(final int offset) {
 135         checkNegativeOffset(offset);
 136         checkArgument(offset < keys.length, INVALIDOFFSET, offset, keys.length);
 137     }
 138
 139     private static void checkNegativeOffset(final int offset) {
 140         checkArgument(offset >= 0, "Invalid negative offset %s", offset);
 141     }
 142 }