    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      https://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.map;
    018
    019import java.io.IOException;
    020import java.io.ObjectInputStream;
    021import java.io.ObjectOutputStream;
    022import java.io.Serializable;
    023import java.util.Collection;
    024import java.util.HashMap;
    025import java.util.Iterator;
    026import java.util.Map;
    027import java.util.Objects;
    028import java.util.Set;
    029import java.util.concurrent.TimeUnit;
    030import java.util.function.Predicate;
    031
    032import org.apache.commons.collections4.collection.AbstractCollectionDecorator;
    033import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
    034import org.apache.commons.collections4.set.AbstractSetDecorator;
    035
    036/**
    037 * Decorates a {@code Map} to evict expired entries once their expiration
    038 * time has been reached.
    039 * <p>
    040 * When putting a key-value pair in the map this decorator uses a
    041 * {@link ExpirationPolicy} to determine how long the entry should remain alive
    042 * as defined by an expiration time value.
    043 * </p>
    044 * <p>
    045 * When accessing the mapped value for a key, its expiration time is checked,
    046 * and if it is a negative value or if it is greater than the current time, the
    047 * mapped value is returned. Otherwise, the key is removed from the decorated
    048 * map, and {@code null} is returned.
    049 * </p>
    050 * <p>
    051 * When invoking methods that involve accessing the entire map contents (i.e
    052 * {@link #containsValue(Object)}, {@link #entrySet()}, etc.) this decorator
    053 * removes all expired entries prior to actually completing the invocation.
    054 * </p>
    055 * <p>
    056 * <strong>Note that {@link PassiveExpiringMap} is not synchronized and is not
    057 * thread-safe.</strong> If you wish to use this map from multiple threads
    058 * concurrently, you must use appropriate synchronization. The simplest approach
    059 * is to wrap this map using {@link java.util.Collections#synchronizedMap(Map)}.
    060 * This class may throw exceptions when accessed by concurrent threads without
    061 * synchronization.
    062 * </p>
    063 *
    064 * @param <K> The type of the keys in this map
    065 * @param <V> The type of the values in this map
    066 * @since 4.0
    067 */
    068public class PassiveExpiringMap<K, V>
    069    extends AbstractMapDecorator<K, V>
    070    implements Serializable {
    071
    072    /**
    073     * A {@link ExpirationPolicy ExpirationPolicy}
    074     * that returns an expiration time that is a
    075     * constant about of time in the future from the current time.
    076     *
    077     * @param <K> The type of the keys in the map
    078     * @param <V> The type of the values in the map
    079     * @since 4.0
    080     */
    081    public static class ConstantTimeToLiveExpirationPolicy<K, V>
    082        implements ExpirationPolicy<K, V> {
    083
    084        /** Serialization version */
    085        private static final long serialVersionUID = 1L;
    086
    087        /** The constant time-to-live value measured in milliseconds. */
    088        private final long timeToLiveMillis;
    089
    090        /**
    091         * Default constructor. Constructs a policy using a negative
    092         * time-to-live value that results in entries never expiring.
    093         */
    094        public ConstantTimeToLiveExpirationPolicy() {
    095            this(-1L);
    096        }
    097
    098        /**
    099         * Constructs a policy with the given time-to-live constant measured in
    100         * milliseconds. A negative time-to-live value indicates entries never
    101         * expire. A zero time-to-live value indicates entries expire (nearly)
    102         * immediately.
    103         *
    104         * @param timeToLiveMillis The constant amount of time (in milliseconds)
    105         *        an entry is available before it expires. A negative value
    106         *        results in entries that NEVER expire. A zero value results in
    107         *        entries that ALWAYS expire.
    108         */
    109        public ConstantTimeToLiveExpirationPolicy(final long timeToLiveMillis) {
    110            this.timeToLiveMillis = timeToLiveMillis;
    111        }
    112
    113        /**
    114         * Constructs a policy with the given time-to-live constant measured in
    115         * the given time unit of measure.
    116         *
    117         * @param timeToLive The constant amount of time an entry is available
    118         *        before it expires. A negative value results in entries that
    119         *        NEVER expire. A zero value results in entries that ALWAYS
    120         *        expire.
    121         * @param timeUnit The unit of time for the {@code timeToLive}
    122         *        parameter, must not be null.
    123         * @throws NullPointerException if the time unit is null.
    124         */
    125        public ConstantTimeToLiveExpirationPolicy(final long timeToLive,
    126                                                  final TimeUnit timeUnit) {
    127            this(validateAndConvertToMillis(timeToLive, timeUnit));
    128        }
    129
    130        /**
    131         * Determine the expiration time for the given key-value entry.
    132         *
    133         * @param key The key for the entry (ignored).
    134         * @param value The value for the entry (ignored).
    135         * @return if {@link #timeToLiveMillis} &ge; 0, an expiration time of
    136         *         {@link #timeToLiveMillis} +
    137         *         {@link System#currentTimeMillis()} is returned. Otherwise, -1
    138         *         is returned indicating the entry never expires.
    139         */
    140        @Override
    141        public long expirationTime(final K key, final V value) {
    142            if (timeToLiveMillis >= 0L) {
    143                // avoid numerical overflow
    144                final long nowMillis = System.currentTimeMillis();
    145                if (nowMillis > Long.MAX_VALUE - timeToLiveMillis) {
    146                    // expiration would be greater than Long.MAX_VALUE
    147                    // never expire
    148                    return -1;
    149                }
    150
    151                // timeToLiveMillis in the future
    152                return nowMillis + timeToLiveMillis;
    153            }
    154
    155            // never expire
    156            return -1L;
    157        }
    158    }
    159
    160    private final class EntrySet extends AbstractSetDecorator<Entry<K, V>> {
    161
    162        /** Generated serial version ID. */
    163        private static final long serialVersionUID = 1L;
    164
    165        private EntrySet(final Set<Entry<K, V>> set) {
    166            super(set);
    167        }
    168
    169        @Override
    170        public void clear() {
    171            PassiveExpiringMap.this.clear();
    172        }
    173
    174        @Override
    175        public boolean contains(final Object object) {
    176            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    177            return super.contains(object);
    178        }
    179
    180        @Override
    181        public boolean containsAll(final Collection<?> coll) {
    182            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    183            return super.containsAll(coll);
    184        }
    185
    186        @Override
    187        public boolean isEmpty() {
    188            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    189            return super.isEmpty();
    190        }
    191
    192        @Override
    193        public Iterator<Entry<K, V>> iterator() {
    194            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    195            return new EntrySetIterator(super.iterator());
    196        }
    197
    198        @Override
    199        public boolean remove(final Object object) {
    200            if (object instanceof Map.Entry) {
    201                final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) object;
    202                final Object key = entry.getKey();
    203                if (PassiveExpiringMap.this.containsKey(key)) {
    204                    final Object value = PassiveExpiringMap.this.get(key);
    205                    if (Objects.equals(value, entry.getValue())) {
    206                        PassiveExpiringMap.this.remove(key);
    207                        return true;
    208                    }
    209                }
    210            }
    211            return false;
    212        }
    213
    214        @Override
    215        public boolean removeAll(final Collection<?> coll) {
    216            Objects.requireNonNull(coll, "coll");
    217            boolean changed = false;
    218            if (size() > coll.size()) {
    219                for (final Object obj : coll) {
    220                    changed |= remove(obj);
    221                }
    222            } else {
    223                final Iterator<?> it = iterator();
    224                while (it.hasNext()) {
    225                    if (coll.contains(it.next())) {
    226                        it.remove();
    227                        changed = true;
    228                    }
    229                }
    230            }
    231            return changed;
    232        }
    233
    234        @Override
    235        public boolean removeIf(final Predicate<? super Entry<K, V>> filter) {
    236            Objects.requireNonNull(filter, "filter");
    237            boolean changed = false;
    238            final Iterator<Entry<K, V>> it = iterator();
    239            while (it.hasNext()) {
    240                if (filter.test(it.next())) {
    241                    it.remove();
    242                    changed = true;
    243                }
    244            }
    245            return changed;
    246        }
    247
    248        @Override
    249        public boolean retainAll(final Collection<?> coll) {
    250            Objects.requireNonNull(coll, "coll");
    251            boolean changed = false;
    252            final Iterator<?> it = iterator();
    253            while (it.hasNext()) {
    254                if (!coll.contains(it.next())) {
    255                    it.remove();
    256                    changed = true;
    257                }
    258            }
    259            return changed;
    260        }
    261
    262        @Override
    263        public int size() {
    264            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    265            return super.size();
    266        }
    267
    268        @Override
    269        public Object[] toArray() {
    270            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    271            return super.toArray();
    272        }
    273
    274        @Override
    275        public <T> T[] toArray(final T[] array) {
    276            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    277            return super.toArray(array);
    278        }
    279    }
    280
    281    private final class EntrySetIterator extends AbstractIteratorDecorator<Entry<K, V>> {
    282        private Entry<K, V> lastReturned;
    283
    284        private EntrySetIterator(final Iterator<Entry<K, V>> iterator) {
    285            super(iterator);
    286        }
    287
    288        @Override
    289        public Entry<K, V> next() {
    290            lastReturned = super.next();
    291            return lastReturned;
    292        }
    293
    294        @Override
    295        public void remove() {
    296            super.remove();
    297            if (lastReturned != null) {
    298                PassiveExpiringMap.this.expirationMap.remove(lastReturned.getKey());
    299                lastReturned = null;
    300            }
    301        }
    302    }
    303
    304    /**
    305     * A policy to determine the expiration time for key-value entries.
    306     *
    307     * @param <K> The key object type.
    308     * @param <V> The value object type
    309     * @since 4.0
    310     */
    311    @FunctionalInterface
    312    public interface ExpirationPolicy<K, V>
    313        extends Serializable {
    314
    315        /**
    316         * Determine the expiration time for the given key-value entry.
    317         *
    318         * @param key The key for the entry.
    319         * @param value The value for the entry.
    320         * @return The expiration time value measured in milliseconds. A
    321         *         negative return value indicates the entry never expires.
    322         */
    323        long expirationTime(K key, V value);
    324    }
    325
    326    private final class KeySet extends AbstractSetDecorator<K> {
    327
    328        /** Generated serial version ID. */
    329        private static final long serialVersionUID = 1L;
    330
    331        private KeySet(final Set<K> set) {
    332            super(set);
    333        }
    334
    335        @Override
    336        public void clear() {
    337            PassiveExpiringMap.this.clear();
    338        }
    339
    340        @Override
    341        public boolean contains(final Object key) {
    342            PassiveExpiringMap.this.removeIfExpired(key, PassiveExpiringMap.this.now());
    343            return super.contains(key);
    344        }
    345
    346        @Override
    347        public boolean containsAll(final Collection<?> coll) {
    348            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    349            return super.containsAll(coll);
    350        }
    351
    352        @Override
    353        public boolean isEmpty() {
    354            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    355            return super.isEmpty();
    356        }
    357
    358        @Override
    359        public Iterator<K> iterator() {
    360            return new KeySetIterator(PassiveExpiringMap.this.entrySet().iterator());
    361        }
    362
    363        @Override
    364        public boolean remove(final Object key) {
    365            final boolean hasKey = contains(key);
    366            if (hasKey) {
    367                PassiveExpiringMap.this.remove(key);
    368            }
    369            return hasKey;
    370        }
    371
    372        @Override
    373        public boolean removeAll(final Collection<?> coll) {
    374            Objects.requireNonNull(coll, "coll");
    375            boolean changed = false;
    376            if (size() > coll.size()) {
    377                for (final Object obj : coll) {
    378                    changed |= remove(obj);
    379                }
    380            } else {
    381                final Iterator<?> it = iterator();
    382                while (it.hasNext()) {
    383                    if (coll.contains(it.next())) {
    384                        it.remove();
    385                        changed = true;
    386                    }
    387                }
    388            }
    389            return changed;
    390        }
    391
    392        @Override
    393        public boolean removeIf(final Predicate<? super K> filter) {
    394            Objects.requireNonNull(filter, "filter");
    395            boolean changed = false;
    396            final Iterator<K> it = iterator();
    397            while (it.hasNext()) {
    398                if (filter.test(it.next())) {
    399                    it.remove();
    400                    changed = true;
    401                }
    402            }
    403            return changed;
    404        }
    405
    406        @Override
    407        public boolean retainAll(final Collection<?> coll) {
    408            Objects.requireNonNull(coll, "coll");
    409            boolean changed = false;
    410            final Iterator<?> it = iterator();
    411            while (it.hasNext()) {
    412                if (!coll.contains(it.next())) {
    413                    it.remove();
    414                    changed = true;
    415                }
    416            }
    417            return changed;
    418        }
    419
    420        @Override
    421        public int size() {
    422            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    423            return super.size();
    424        }
    425
    426        @Override
    427        public Object[] toArray() {
    428            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    429            return super.toArray();
    430        }
    431
    432        @Override
    433        public <T> T[] toArray(final T[] array) {
    434            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    435            return super.toArray(array);
    436        }
    437    }
    438
    439    private final class KeySetIterator implements Iterator<K> {
    440        private final Iterator<Entry<K, V>> iterator;
    441
    442        private KeySetIterator(final Iterator<Entry<K, V>> iterator) {
    443            this.iterator = iterator;
    444        }
    445
    446        @Override
    447        public boolean hasNext() {
    448            return iterator.hasNext();
    449        }
    450
    451        @Override
    452        public K next() {
    453            return iterator.next().getKey();
    454        }
    455
    456        @Override
    457        public void remove() {
    458            iterator.remove();
    459        }
    460    }
    461
    462    private final class ValuesCollection extends AbstractCollectionDecorator<V> {
    463
    464        /** Generated serial version ID. */
    465        private static final long serialVersionUID = 1L;
    466
    467        private ValuesCollection(final Collection<V> coll) {
    468            super(coll);
    469        }
    470
    471        @Override
    472        public void clear() {
    473            PassiveExpiringMap.this.clear();
    474        }
    475
    476        @Override
    477        public boolean contains(final Object value) {
    478            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    479            return super.contains(value);
    480        }
    481
    482        @Override
    483        public boolean containsAll(final Collection<?> coll) {
    484            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    485            return super.containsAll(coll);
    486        }
    487
    488        @Override
    489        public boolean isEmpty() {
    490            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    491            return super.isEmpty();
    492        }
    493
    494        @Override
    495        public Iterator<V> iterator() {
    496            return new ValuesIterator(PassiveExpiringMap.this.entrySet().iterator());
    497        }
    498
    499        @Override
    500        public boolean remove(final Object value) {
    501            final Iterator<V> it = iterator();
    502            while (it.hasNext()) {
    503                if (Objects.equals(it.next(), value)) {
    504                    it.remove();
    505                    return true;
    506                }
    507            }
    508            return false;
    509        }
    510
    511        @Override
    512        public boolean removeAll(final Collection<?> coll) {
    513            Objects.requireNonNull(coll, "coll");
    514            boolean changed = false;
    515            final Iterator<?> it = iterator();
    516            while (it.hasNext()) {
    517                if (coll.contains(it.next())) {
    518                    it.remove();
    519                    changed = true;
    520                }
    521            }
    522            return changed;
    523        }
    524
    525        @Override
    526        public boolean removeIf(final Predicate<? super V> filter) {
    527            Objects.requireNonNull(filter, "filter");
    528            boolean changed = false;
    529            final Iterator<V> it = iterator();
    530            while (it.hasNext()) {
    531                if (filter.test(it.next())) {
    532                    it.remove();
    533                    changed = true;
    534                }
    535            }
    536            return changed;
    537        }
    538
    539        @Override
    540        public boolean retainAll(final Collection<?> coll) {
    541            Objects.requireNonNull(coll, "coll");
    542            boolean changed = false;
    543            final Iterator<?> it = iterator();
    544            while (it.hasNext()) {
    545                if (!coll.contains(it.next())) {
    546                    it.remove();
    547                    changed = true;
    548                }
    549            }
    550            return changed;
    551        }
    552
    553        @Override
    554        public int size() {
    555            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    556            return super.size();
    557        }
    558
    559        @Override
    560        public Object[] toArray() {
    561            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    562            return super.toArray();
    563        }
    564
    565        @Override
    566        public <T> T[] toArray(final T[] array) {
    567            PassiveExpiringMap.this.removeAllExpired(PassiveExpiringMap.this.now());
    568            return super.toArray(array);
    569        }
    570    }
    571
    572    private final class ValuesIterator implements Iterator<V> {
    573        private final Iterator<Entry<K, V>> iterator;
    574
    575        private ValuesIterator(final Iterator<Entry<K, V>> iterator) {
    576            this.iterator = iterator;
    577        }
    578
    579        @Override
    580        public boolean hasNext() {
    581            return iterator.hasNext();
    582        }
    583
    584        @Override
    585        public V next() {
    586            return iterator.next().getValue();
    587        }
    588
    589        @Override
    590        public void remove() {
    591            iterator.remove();
    592        }
    593    }
    594
    595    /** Serialization version */
    596    private static final long serialVersionUID = 1L;
    597
    598    /**
    599     * First validate the input parameters. If the parameters are valid, convert
    600     * the given time measured in the given units to the same time measured in
    601     * milliseconds.
    602     *
    603     * @param timeToLive The constant amount of time an entry is available
    604     *        before it expires. A negative value results in entries that NEVER
    605     *        expire. A zero value results in entries that ALWAYS expire.
    606     * @param timeUnit The unit of time for the {@code timeToLive}
    607     *        parameter, must not be null.
    608     * @throws NullPointerException if the time unit is null.
    609     */
    610    private static long validateAndConvertToMillis(final long timeToLive,
    611                                                   final TimeUnit timeUnit) {
    612        Objects.requireNonNull(timeUnit, "timeUnit");
    613        return TimeUnit.MILLISECONDS.convert(timeToLive, timeUnit);
    614    }
    615
    616    /** Map used to manage expiration times for the actual map entries. */
    617    private final Map<Object, Long> expirationMap = new HashMap<>();
    618
    619    /** The policy used to determine time-to-live values for map entries. */
    620    private final ExpirationPolicy<K, V> expiringPolicy;
    621
    622    /**
    623     * Default constructor. Constructs a map decorator that results in entries
    624     * NEVER expiring.
    625     */
    626    public PassiveExpiringMap() {
    627        this(-1L);
    628    }
    629
    630    /**
    631     * Constructs a map decorator using the given expiration policy to determine
    632     * expiration times.
    633     *
    634     * @param expiringPolicy The policy used to determine expiration times of
    635     *        entries as they are added.
    636     * @throws NullPointerException if expiringPolicy is null
    637     */
    638    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy) {
    639        this(expiringPolicy, new HashMap<>());
    640    }
    641
    642    /**
    643     * Constructs a map decorator that decorates the given map and uses the given
    644     * expiration policy to determine expiration times. If there are any
    645     * elements already in the map being decorated, they will NEVER expire
    646     * unless they are replaced.
    647     *
    648     * @param expiringPolicy The policy used to determine expiration times of
    649     *        entries as they are added.
    650     * @param map The map to decorate, must not be null.
    651     * @throws NullPointerException if the map or expiringPolicy is null.
    652     */
    653    public PassiveExpiringMap(final ExpirationPolicy<K, V> expiringPolicy,
    654                              final Map<K, V> map) {
    655        super(map);
    656        this.expiringPolicy = Objects.requireNonNull(expiringPolicy, "expiringPolicy");
    657    }
    658
    659    /**
    660     * Constructs a map decorator that decorates the given map using the given
    661     * time-to-live value measured in milliseconds to create and use a
    662     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
    663     *
    664     * @param timeToLiveMillis The constant amount of time (in milliseconds) an
    665     *        entry is available before it expires. A negative value results in
    666     *        entries that NEVER expire. A zero value results in entries that
    667     *        ALWAYS expire.
    668     */
    669    public PassiveExpiringMap(final long timeToLiveMillis) {
    670        this(new ConstantTimeToLiveExpirationPolicy<>(timeToLiveMillis),
    671                new HashMap<>());
    672    }
    673
    674    /**
    675     * Constructs a map decorator using the given time-to-live value measured in
    676     * milliseconds to create and use a
    677     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. If there
    678     * are any elements already in the map being decorated, they will NEVER
    679     * expire unless they are replaced.
    680     *
    681     * @param timeToLiveMillis The constant amount of time (in milliseconds) an
    682     *        entry is available before it expires. A negative value results in
    683     *        entries that NEVER expire. A zero value results in entries that
    684     *        ALWAYS expire.
    685     * @param map The map to decorate, must not be null.
    686     * @throws NullPointerException if the map is null.
    687     */
    688    public PassiveExpiringMap(final long timeToLiveMillis, final Map<K, V> map) {
    689        this(new ConstantTimeToLiveExpirationPolicy<>(timeToLiveMillis),
    690             map);
    691    }
    692
    693    /**
    694     * Constructs a map decorator using the given time-to-live value measured in
    695     * the given time units of measure to create and use a
    696     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy.
    697     *
    698     * @param timeToLive The constant amount of time an entry is available
    699     *        before it expires. A negative value results in entries that NEVER
    700     *        expire. A zero value results in entries that ALWAYS expire.
    701     * @param timeUnit The unit of time for the {@code timeToLive}
    702     *        parameter, must not be null.
    703     * @throws NullPointerException if the time unit is null.
    704     */
    705    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit) {
    706        this(validateAndConvertToMillis(timeToLive, timeUnit));
    707    }
    708
    709    /**
    710     * Constructs a map decorator that decorates the given map using the given
    711     * time-to-live value measured in the given time units of measure to create
    712     * {@link ConstantTimeToLiveExpirationPolicy} expiration policy. This policy
    713     * is used to determine expiration times. If there are any elements already
    714     * in the map being decorated, they will NEVER expire unless they are
    715     * replaced.
    716     *
    717     * @param timeToLive The constant amount of time an entry is available
    718     *        before it expires. A negative value results in entries that NEVER
    719     *        expire. A zero value results in entries that ALWAYS expire.
    720     * @param timeUnit The unit of time for the {@code timeToLive}
    721     *        parameter, must not be null.
    722     * @param map The map to decorate, must not be null.
    723     * @throws NullPointerException if the map or time unit is null.
    724     */
    725    public PassiveExpiringMap(final long timeToLive, final TimeUnit timeUnit, final Map<K, V> map) {
    726        this(validateAndConvertToMillis(timeToLive, timeUnit), map);
    727    }
    728
    729    /**
    730     * Constructs a map decorator that decorates the given map and results in
    731     * entries NEVER expiring. If there are any elements already in the map
    732     * being decorated, they also will NEVER expire.
    733     *
    734     * @param map The map to decorate, must not be null.
    735     * @throws NullPointerException if the map is null.
    736     */
    737    public PassiveExpiringMap(final Map<K, V> map) {
    738        this(-1L, map);
    739    }
    740
    741    /**
    742     * Normal {@link Map#clear()} behavior with the addition of clearing all
    743     * expiration entries as well.
    744     */
    745    @Override
    746    public void clear() {
    747        super.clear();
    748        expirationMap.clear();
    749    }
    750
    751    /**
    752     * All expired entries are removed from the map prior to determining the
    753     * contains result.
    754     * {@inheritDoc}
    755     */
    756    @Override
    757    public boolean containsKey(final Object key) {
    758        removeIfExpired(key, now());
    759        return super.containsKey(key);
    760    }
    761
    762    /**
    763     * All expired entries are removed from the map prior to determining the
    764     * contains result.
    765     * {@inheritDoc}
    766     */
    767    @Override
    768    public boolean containsValue(final Object value) {
    769        removeAllExpired(now());
    770        return super.containsValue(value);
    771    }
    772
    773    /**
    774     * All expired entries are removed from the map prior to returning the entry set.
    775     * {@inheritDoc}
    776     */
    777    @Override
    778    public Set<Entry<K, V>> entrySet() {
    779        removeAllExpired(now());
    780        return new EntrySet(super.entrySet());
    781    }
    782
    783    /**
    784     * All expired entries are removed from the map prior to returning the entry value.
    785     * {@inheritDoc}
    786     */
    787    @Override
    788    public V get(final Object key) {
    789        removeIfExpired(key, now());
    790        return super.get(key);
    791    }
    792
    793    /**
    794     * All expired entries are removed from the map prior to determining if it is empty.
    795     * {@inheritDoc}
    796     */
    797    @Override
    798    public boolean isEmpty() {
    799        removeAllExpired(now());
    800        return super.isEmpty();
    801    }
    802
    803    /**
    804     * Determines if the given expiration time is less than {@code now}.
    805     *
    806     * @param now The time in milliseconds used to compare against the
    807     *        expiration time.
    808     * @param expirationTimeObject The expiration time value retrieved from
    809     *        {@link #expirationMap}, can be null.
    810     * @return {@code true} if {@code expirationTimeObject} is &ge; 0
    811     *         and {@code expirationTimeObject} &lt; {@code now}.
    812     *         {@code false} otherwise.
    813     */
    814    private boolean isExpired(final long now, final Long expirationTimeObject) {
    815        if (expirationTimeObject != null) {
    816            final long expirationTime = expirationTimeObject.longValue();
    817            return expirationTime >= 0 && now >= expirationTime;
    818        }
    819        return false;
    820    }
    821
    822    /**
    823     * All expired entries are removed from the map prior to returning the key set.
    824     * {@inheritDoc}
    825     */
    826    @Override
    827    public Set<K> keySet() {
    828        removeAllExpired(now());
    829        return new KeySet(super.keySet());
    830    }
    831
    832    /**
    833     * The current time in milliseconds.
    834     */
    835    private long now() {
    836        return System.currentTimeMillis();
    837    }
    838
    839    /**
    840     * {@inheritDoc}
    841     * <p>
    842     * Add the given key-value pair to this map as well as recording the entry's expiration time based on the current time in milliseconds and this map's
    843     * {@link #expiringPolicy}.
    844     * </p>
    845     */
    846    @Override
    847    public V put(final K key, final V value) {
    848        // remove the previous record
    849        removeIfExpired(key, now());
    850
    851        // record expiration time of new entry
    852        final long expirationTime = expiringPolicy.expirationTime(key, value);
    853        expirationMap.put(key, Long.valueOf(expirationTime));
    854
    855        return super.put(key, value);
    856    }
    857
    858    @Override
    859    public void putAll(final Map<? extends K, ? extends V> mapToCopy) {
    860        for (final Map.Entry<? extends K, ? extends V> entry : mapToCopy.entrySet()) {
    861            put(entry.getKey(), entry.getValue());
    862        }
    863    }
    864
    865    /**
    866     * Deserializes the map in using a custom routine.
    867     *
    868     * @param in The input stream
    869     * @throws IOException Thrown if an error occurs while reading from the stream
    870     * @throws ClassNotFoundException if an object read from the stream cannot be loaded
    871     */
    872    @SuppressWarnings("unchecked")
    873    // (1) should only fail if input stream is incorrect
    874    private void readObject(final ObjectInputStream in)
    875        throws IOException, ClassNotFoundException {
    876        in.defaultReadObject();
    877        map = (Map<K, V>) in.readObject(); // (1)
    878    }
    879
    880    /**
    881     * Normal {@link Map#remove(Object)} behavior with the addition of removing
    882     * any expiration entry as well.
    883     * {@inheritDoc}
    884     */
    885    @Override
    886    public V remove(final Object key) {
    887        expirationMap.remove(key);
    888        return super.remove(key);
    889    }
    890
    891    /**
    892     * Removes all entries in the map whose expiration time is less than
    893     * {@code now}. The exceptions are entries with negative expiration
    894     * times; those entries are never removed.
    895     *
    896     * @see #isExpired(long, Long)
    897     */
    898    private void removeAllExpired(final long nowMillis) {
    899        final Iterator<Map.Entry<Object, Long>> iter = expirationMap.entrySet().iterator();
    900        while (iter.hasNext()) {
    901            final Map.Entry<Object, Long> expirationEntry = iter.next();
    902            if (isExpired(nowMillis, expirationEntry.getValue())) {
    903                // remove entry from collection
    904                super.remove(expirationEntry.getKey());
    905                // remove entry from expiration map
    906                iter.remove();
    907            }
    908        }
    909    }
    910
    911    /**
    912     * Removes the entry with the given key if the entry's expiration time is
    913     * less than {@code now}. If the entry has a negative expiration time,
    914     * the entry is never removed.
    915     */
    916    private void removeIfExpired(final Object key, final long nowMillis) {
    917        final Long expirationTimeObject = expirationMap.get(key);
    918        if (isExpired(nowMillis, expirationTimeObject)) {
    919            remove(key);
    920        }
    921    }
    922
    923    /**
    924     * All expired entries are removed from the map prior to returning the size.
    925     * {@inheritDoc}
    926     */
    927    @Override
    928    public int size() {
    929        removeAllExpired(now());
    930        return super.size();
    931    }
    932
    933    /**
    934     * All expired entries are removed from the map prior to returning the value collection.
    935     * {@inheritDoc}
    936     */
    937    @Override
    938    public Collection<V> values() {
    939        removeAllExpired(now());
    940        return new ValuesCollection(super.values());
    941    }
    942
    943    /**
    944     * Serializes this object to an ObjectOutputStream.
    945     *
    946     * @param out The target ObjectOutputStream.
    947     * @throws IOException thrown when an I/O errors occur writing to the target stream.
    948     */
    949    private void writeObject(final ObjectOutputStream out)
    950        throws IOException {
    951        out.defaultWriteObject();
    952        out.writeObject(map);
    953    }
    954}