# ScopedDictionary.java

    /*
    ** Module   : ScopedDictionary.java
    ** Abstract : Provides multiscoped dictionary functionality.
    **
    ** Copyright (c) 2004-2025, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- --JPRM-- ----------------------------------Description-----------------------------------
    ** 001 ECF 20051028   @23220 Abstracted from ScopedSymbolDictionary, which
    **                           is now a subclass of this class. This was
    **                           necessary to provide the base functionality
    **                           of this class (scoped mapping) without the
    **                           assumption that all keys are of type String.
    **                           This class uses Object for its entry keys.
    ** 002 NVS 20051207   @23672 Added new method getScopeAt(int) which gives
    **                           access to the user objects at any depth.
    ** 003 ECF 20060208   @24705 Added values() and entrySet() methods. These
    **                           are analogs to the keySet() methods to round
    **                           out the map-like API.
    ** 004 NVS 20070118   @31892 Added new methods to replace the extra object
    **                           in the current or any other scope.
    ** 005 ECF 20071029   @35630 Implemented generics. Intentionally left the
    **                           'extra' data as Object for now.
    ** 006 GES 20080308   @37669 Added writer support to dump methods so that
    **                           I18N issues can be improved.
    ** 007 SIY 20080904   @39716 Minor cleanups.
    ** 008 ECF 20090115   @41159 Added new methods. deleteScope(boolean)
    **                           optionally propagates entries up when popping
    **                           a scope; clear() removes all entries from all
    **                           scopes (but leaves the scopes intact);
    **                           removeEntryAtScope(K, int) removes a specific
    **                           entry from a specific scope;
    **                           getDictionaryAtScope(int) returns a map for a
    **                           given scope to enable direct manipulation.
    ** 009 ECF 20090218   @41335 Major memory improvement. Dictionary for each
    **                           node is now created lazily for operations
    **                           which write to the dictionary. For operations
    **                           which simply read, an immutable, empty map is
    **                           used in nodes where no dictionary yet exists.
    **                           Also reduced the starting size of the map.
    ** 010 GES 20111205          Exposed processKey() as public.
    ** 011 SVL 20131028          Added addEntryAt().
    ** 012 ECF 20150222          Made adding entries slightly more efficient, by avoiding an
    **                           unnecessary key check.
    ** 013 ECF 20150322          Rewrote the implementation of the values methods to eliminate the
    **                           copying of data to new collection objects, to improve performance.
    ** 014 ECF 20160429          Added removeEntryThroughScope.
    ** 015 ECF 20160607          Added variant of lookup which takes starting scope.
    ** 016 CA  20160728          Added copyAll API, to allow a dictionary duplication; if the
    **                           keepGlobal flag is true, then the global scope is shared between the
    **                           source and the copy; otherwise, it's duplicated.
    ** 017 CA  20161010          Added apply, an API which will execute the given code for all
    **                           the key's values, in all scopes, starting from innermost to global,
    **                           until the caller decides to terminate the search.
    ** 018 ECF 20180311          Added reverseLookup variant to begin search at an arbitrary scope.
    ** 019 ECF 20190302          dumpScope now shows depth.
    ** 020 ECF 20190322          Optimized getDictionaryAtScope for the common case.
    ** 021 GES 20200706          Optimized all at scope operations to index into the list instead of using an
    **                           iterator.
    ** 022 CA  20201003          Allow IdentityHashMap dictionaries.
    ** 023 AIL 20210507          Allow lookup with validator function.
    ** 024 TW  20220617          Allow using a TailMap for dirtyBuffers at the BufferManager (refs #6356).
    **     EVL 20221130          Fixed NPE for key processing.
    ** 025 CA  20230215          Performance improvement: replaced lambda calls with singleton (per dictionary)
    **                           Function or Supplier instances.  This is required to avoid the overhead of lambda
    **                           resolution at the JVM level, as direct calls are faster than lambda calls.
    **         20230223          Avoid the overhead of calculating an empty map when the scope has no dictionary -
    **                           internally, Node.getDictionary(false) will return null if there is no dictionary;
    **                           but, getDictionaryAtScope() will still return an empty map, instead of null.
    ** 026 GBB 20230512          Logging methods replaced by CentralLogger/ConversionStatus.
    ** 027 CA  20230727          ScopedSymbolDictionary now uses a CaseInsensitiveHashMap for case-insensitive
    **                           dictionaries, so 'processKey' is no longer needed.
    ** 028 CA  20230818          'keySet(int)' must also use the factory methods to create the map/set.
    ** 029 AB2 20250415          Added lookupAll and lookupAllDictionaries methods. See #9722.
    ** 030 RNC 20250423          Reverted commit with entry 029. See #9914.
    */

    /*
    ** This program is free software: you can redistribute it and/or modify
    ** it under the terms of the GNU Affero General Public License as
    ** published by the Free Software Foundation, either version 3 of the
    ** License, or (at your option) any later version.
    **
    ** This program is distributed in the hope that it will be useful,
    ** but WITHOUT ANY WARRANTY; without even the implied warranty of
    ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    ** GNU Affero General Public License for more details.
    **
    ** You may find a copy of the GNU Affero GPL version 3 at the following
    ** location: https://www.gnu.org/licenses/agpl-3.0.en.html
    **
    ** Additional terms under GNU Affero GPL version 3 section 7:
    **
    **   Under Section 7 of the GNU Affero GPL version 3, the following additional
    **   terms apply to the works covered under the License.  These additional terms
    **   are non-permissive additional terms allowed under Section 7 of the GNU
    **   Affero GPL version 3 and may not be removed by you.
    **
    **   0. Attribution Requirement.
    **
    **     You must preserve all legal notices or author attributions in the covered
    **     work or Appropriate Legal Notices displayed by works containing the covered
    **     work.  You may not remove from the covered work any author or developer
    **     credit already included within the covered work.
    **
    **   1. No License To Use Trademarks.
    **
    **     This license does not grant any license or rights to use the trademarks
    **     Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
    **     of Golden Code Development Corporation. You are not authorized to use the
    **     name Golden Code, FWD, or the names of any author or contributor, for
    **     publicity purposes without written authorization.
    **
    **   2. No Misrepresentation of Affiliation.
    **
    **     You may not represent yourself as Golden Code Development Corporation or FWD.
    **
    **     You may not represent yourself for publicity purposes as associated with
    **     Golden Code Development Corporation, FWD, or any author or contributor to
    **     the covered work, without written authorization.
    **
    **   3. No Misrepresentation of Source or Origin.
    **
    **     You may not represent the covered work as solely your work.  All modified
    **     versions of the covered work must be marked in a reasonable way to make it
    **     clear that the modified work is not originating from Golden Code Development
    **     Corporation or FWD.  All modified versions must contain the notices of
    **     attribution required in this license.
    */

    package com.goldencode.p2j.util;

    import com.goldencode.p2j.util.logging.*;

    import java.io.*;
    import java.util.*;
    import java.util.function.*;

    /**
     * Implements a symbol dictionary with multiple levels of scope.  Entries can
     * be added to, removed from and queried in the dictionary.  Each entry
     * consists of an <code>Object</code> key and an optional, user-defined
     * object that can store arbitrary user data.  As a result of the lookup
     * process, if an entry is found, the user-defined object is returned.
     * <p>
     * When entries are added, they are stored in a flat list called a scope.
     * Each scope can store a set of entries where each symbol key must be unique.
     * The user has control over how many scopes exist.  By default, no scopes
     * are available.  The user of this class is responsible for adding scopes
     * using the <code>addScope</code> method.  When the entries stored in the
     * current scope should no longer be available, the scope can be removed
     * using the <code>deleteScope</code> method.  This multilevel scope
     * approach can be thought of as a stack of scopes where the current scope
     * is the top of the stack and the bottom of the stack has a special scope
     * that is considered "global".  Entries can be added to the current scope
     * or to the global scope using the <code>addEntry</code> method.
     * <p>
     * Since the global scope has a special meaning, a convenience constructor
     * is provided that automatically creates the global scope.
     * <p>
     * Keys must only be unique within a single scope.  If the same key exists
     * in multiple scopes, the instance found closest to the current scope (top
     * of stack) is the one that is found on lookup.  Likewise, when an entry
     * is deleted using <code>deleteEntry</code>, the topmost entry is the one
     * removed.
     * <p>
     * @param   <K>
     *          Dictionary key type
     * @param   <V>
     *          Dictionary value type
     */
    public class ScopedDictionary<K, V>
    {
       /** Logger */
       private static final CentralLogger LOG = CentralLogger.get(ScopedDictionary.class);

       /** Implements stackable scopes */
       private LinkedList<Node<K, V>> scopes = new LinkedList<>();

       /** Flag indicating if the {@link Node#dictionary}'s keys can use the identity hash code. */
       private boolean identityKeys = false;

       /** Singleton function returning true.  This is instance-local, as is typed on the dictionary's type. */
       private final Function<V, Boolean> TRUE = new Function<V, Boolean>()
       {
          @Override
          public Boolean apply(V t)
          {
             return true;
          }
       };

       /** Singleton function returning {@link #factoryNodeIdentityHashMap} on this dictionary instance. */
       private final Function<Integer, Map<K,V>> SUPPLY_IDENTITY_HASHMAP = new Function<Integer, Map<K,V>>()
       {
          @Override
          public Map<K, V> apply(Integer t)
          {
             return ScopedDictionary.this.factoryNodeIdentityHashMap(t);
          }
       };

       /** Singleton function returning {@link #factoryNodeHashMap} on this dictionary instance. */
       private final Function<Integer, Map<K,V>> SUPPLY_HASHMAP = new Function<Integer, Map<K,V>>()
       {
          @Override
          public Map<K, V> apply(Integer t)
          {
             return ScopedDictionary.this.factoryNodeHashMap(t);
          }
       };

       /**
        * Default constructor.
        */
       public ScopedDictionary()
       {
       }

       /**
        * Convenience constructor that automatically creates the global scope.
        *
        * @param  extra
        *         Object to be associated with the global scope.
        */
       public ScopedDictionary(Object extra)
       {
          addScope(extra);
       }

       /**
        * Get the {@link #identityKeys} flag.
        *
        * @return  identityKeys
        *           See {@link #setIdentityKeys}.
        */
       public boolean getIdentityKeys()
       {
          return identityKeys;
       }

       /**
        * Set the {@link #identityKeys} flag.
        *
        * @param    identityKeys
        *           When <code>true</code>, the dictionary will be an {@link IdentityHashMap}.
        */
       public void setIdentityKeys(boolean identityKeys)
       {
          this.identityKeys = identityKeys;
       }

       /**
        * Clear this dictionary and copy all content from the source.  The global scope will be either
        * duplicated or kept as a standalone reference, to be shared among copies.
        *
        * @param    source
        *           The source dictionary.
        * @param    keepGlobal
        *           When <code>true</code>, the global dictionary is exposed directly to this copy;
        *           otherwise is duplicated.
        */
       public void copyAll(ScopedDictionary<K, V> source, boolean keepGlobal)
       {
          scopes.clear();

          Node<K, V> global = source.scopes.getFirst();

          for (Node<K, V> node : source.scopes)
          {
             Node<K, V> newNode = null;

             if (global != null && keepGlobal && node == global)
             {
                newNode = global;
                global = null;
             }
             else
             {
                newNode = node.clone();
             }

             scopes.add(newNode);
          }
       }

       /**
        * Creates a new scope and associates a user-defined object with it.
        * The new scope appears on top of the stack.
        *
        * @param  extra
        *         Object to be associated with new scope.
        */
       public void addScope(Object extra)
       {
          scopes.addLast(new Node<K, V>(extra, identityKeys, SUPPLY_IDENTITY_HASHMAP, SUPPLY_HASHMAP));
       }

       /**
        * Deletes the current scope which is the one on the top of the stack.
        * It gets popped off the stack and all entries defined in that scope
        * are no longer accessible.
        */
       public void deleteScope()
       {
          deleteScope(false);
       }

       /**
        * Deletes the current scope which is the one on the top of the stack, and
        * optionally propagates all entries defined in that scope to the next
        * scope on the stack.  Any existing entries in the next scope, which have
        * the same keys as entries in the deleted scope, are overwritten.
        *
        * @param   propagate
        *          <code>true</code> to propagate entries up to the next scope;
        *          <code>false</code> to simply remove those entries.
        */
       public void deleteScope(boolean propagate)
       {
          Node<K, V> removed = scopes.removeLast();
          if (propagate)
          {
             Node<K, V> next = scopes.getLast();
             if (next != null)
             {
                Map<K, V> oldDict = removed.getDictionary(false);
                if (oldDict != null && !oldDict.isEmpty())
                {
                   Map<K, V> dict = next.getDictionary(true);
                   dict.putAll(oldDict);
                }
             }
          }
       }

       /**
        * Accesses the user object in the current scope.
        *
        * @return  Object associated with the current dictionary.
        */
       public Object getScope()
       {
          if (scopes.size() > 0)
          {
             return scopes.getLast().getExtra();
          }

          return null;
       }

       /**
        * Replaces the user object in the current scope.
        *
        * @param   extra
        *          Any object that will be associated with this scope.
        */
       public void setScope(Object extra)
       {
          if (scopes.size() > 0)
          {
             scopes.getLast().setExtra(extra);
          }
       }

       /**
        * Accesses the user object in the scope specified. The current scope is
        * the one on the top of the stack.
        *
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the value must be gotten. Use -1 to reference the global
        *          scope.
        *
        * @return  Object associated with the specified scope.
        */
       public Object getScopeAt(int scope)
       {
          Node<K, V> node = getNodeAt(scope);

          return (node == null) ? null : node.getExtra();
       }

       /**
        * Replaces the user object in the scope specified. The current scope is
        * the one on the top of the stack.
        *
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the value must be gotten. Use -1 to reference the global
        *          scope.
        * @param   extra
        *          Any object that will be associated with this scope.
        */
       public void setScopeAt(int scope, Object extra)
       {
          Node<K, V> node = getNodeAt(scope);

          if (node != null)
          {
             node.setExtra(extra);
          }
       }

       /**
        * Returns the stack depth.
        *
        * @return  Number of scopes currently on the stack.
        */
       public int size()
       {
          return scopes.size();
       }

       /**
        * Adds a value to the current or global scope or replaces its
        * user-defined object. The current scope is the one on the top of the
        * stack. The global scope is always the first scope created on the stack.
        * If only one scope is on the stack, both refer to the same scope.
        *
        * @param   global
        *          Specifies the target scope. <code>false</code> specifies the
        *          current scope, and <code>true</code> specifies the global
        *          scope.
        * @param   key
        *          The lookup key.
        * @param   value
        *          The stored value which may be any object.
        *
        * @return  <code>true</code> if the entry has been added,
        *          <code>false</code> if its value has been replaced.
        */
       public boolean addEntry(boolean global, K key, V value)
       {
          Node<K, V> n = null;
          Map<K, V> dictionary = null;
          boolean result = false;

          if (global)
          {
             n = scopes.getFirst();
          }
          else
          {
             n = scopes.getLast();
          }

          dictionary = n.getDictionary(true);

          result = (dictionary.put(key, value) == null);

          return result;
       }

       /**
        * Adds a value to the scope at the specified depth or replaces its user-defined object.
        *
        * @param   depth
        *          zero-based index of the target scope, starting from the outermost scope.
        * @param   key
        *          The lookup key.
        * @param   value
        *          The stored value which may be any object.
        *
        * @return  <code>true</code> if the entry has been added,
        *          <code>false</code> if its value has been replaced.
        *
        * @throws  ArrayIndexOutOfBoundsException
        *          if invalid <code>depth</code> is specified.
        */
       public boolean addEntryAt(int depth, K key, V value)
       throws ArrayIndexOutOfBoundsException
       {
          Node<K, V> n = null;
          Map<K, V> dictionary = null;
          boolean result = false;

          n = scopes.get(depth);

          dictionary = n.getDictionary(true);

          result = (dictionary.put(key, value) == null);

          return result;
       }

       /**
        * Searches all scopes from the top of the stack down and deletes
        * the first found occurrence of the target entry.
        *
        * @param   key
        *          The lookup key.
        *
        * @return  <code>true</code> if the entry has been deleted.
        */
       public boolean deleteEntry(K key)
       {
          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
          Map<K, V> dictionary = null;

          while (li.hasPrevious())
          {
             dictionary = li.previous().getDictionary(false);
             if (dictionary != null && dictionary.remove(key) != null)
             {
                return true;
             }
          }

          return false;
       }

       /**
        * Removes all entries from all scopes in the stack, top scope first.
        * Does not remove any scopes.
        */
       public void clear()
       {
          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
          while (li.hasPrevious())
          {
             Map<K, V> dict = li.previous().getDictionary(false);
             if(dict != null)
             {
                dict.clear();
             }
          }
       }

       /**
        * Searches all scopes from the top of the stack down for the specified
        * key and value pair and returns 0-based index of the depth where
        * that pair is found.  Both the key and the value must be matched to
        * the given parameters for this to succeed.
        *
        * @param   key
        *          The lookup key.
        * @param   value
        *          The value to search.
        *
        * @return  0-based index of the scope depth at which value is found.
        */
       public int locate(K key, V value)
       {
          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
          Map<K, V> dictionary = null;
          V o = null;

          int depth = 0;

          while (li.hasPrevious())
          {
             dictionary = li.previous().getDictionary(false);
             o = dictionary != null ? dictionary.get(key) : null;

             if (o != null && o.equals(value))
             {
                return depth;
             }

             depth++;
          }

          return -1;
       }

       /**
        * Returns the dictionary from the scope specified, or <code>null</code> if
        * the specified scope does not exist.
        *
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) at
        *          which the value must be set. Use -1 for the global scope.
        * @param   create
        *          <code>true</code> to create a dictionary for this scope if one
        *          does not already exist;  <code>false</code> to have an empty
        *          (immutable) dictionary returned if one does not already exist.
        *
        * @return  The dictionary, if any, associated with the specified scope.
        *          Note that this may be an immutable, empty map if no dictionary
        *          exists at this scope, and <code>create</code> is set to
        *          <code>false</code>.  If the scope itself does not exist, then
        *          <code>null</code> is returned.
        */
       public Map<K, V> getDictionaryAtScope(int scope, boolean create)
       {
          Node<K, V> node = getNodeAt(scope);

          if (node != null)
          {
             Map<K, V> dict = node.getDictionary(create);
             return dict == null ? Collections.EMPTY_MAP : dict;
          }

          return null;
       }

       /**
        * Remove the entry with the specified key from all scopes up to and including the scope
        * specified.
        *
        * @param   key
        *          The lookup key.
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from which the entry
        *          is to be removed. It will be removed from every scope in which it exists, up to
        *          and including this depth.
        *
        * @return  The number of scopes from which the entry was removed, or {@code 0} if it was not
        *          found.
        */
       public int removeEntryThroughScope(K key, int scope)
       {
          int count = 0;

          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());

          for (int depth = 0; li.hasPrevious() && depth <= scope; depth++)
          {
             Node<K, V> node = li.previous();

             Map<K, V> dict = node.getDictionary(false);
             if (dict != null && dict.remove(key) != null)
             {
                count++;
             }
          }

          return count;
       }

       /**
        * Remove the entry with the specified key from the scope specified.
        *
        * @param   key
        *          The lookup key.
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the entry is to be removed.
        *
        * @return  <code>true</code> if the value was removed set, or
        *          <code>false</code> if it was not found.
        */
       public boolean removeEntryAtScope(K key, int scope)
       {
          Map<K, V> dict = getDictionaryAtScope(scope, false);

          return (dict == null || dict.remove(key) != null);
       }

       /**
        * Sets specified value within the entry in the scope specified.
        *
        * @param   key
        *          The lookup key.
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) at
        *          which the value must be set.
        * @param   value
        *          The replacement value.
        *
        * @return  <code>true</code> if the value was successfully set, or
        *          <code>false</code> if any error occurred.
        */
       public boolean setValueAtScope(K key, int scope, V value)
       {
          Map<K, V> dict = getDictionaryAtScope(scope, true);

          if (dict != null)
          {
             dict.put(key, value);
             return true;
          }

          return false;
       }

       /**
        * Gets the value for the given key in the scope specified.
        *
        * @param   key
        *          The lookup key.
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the value must be gotten. Use -1 to reference the global
        *          scope.
        *
        * @return  The object found or <code>null</code> if no such name exists.
        */
       public V getValueAtScope(K key, int scope)
       {
          Map<K, V> dict = getDictionaryAtScope(scope, false);

          return (dict == null) ? null : dict.get(key);
       }

       /**
        * Execute the given code for all values, in all scopes, for the specified key.
        * <p>
        * This will walk all dictionaries, from the innermost scope to the global scope.  If a
        * dictionary mapping doesn't exist in a certain scope for this key, that scope will not be
        * processed.
        * <p>
        * The scope processing will continue until the caller (via the code function) decides to
        * terminate the processing.
        *
        * @param    key
        *           The key which needs to have its values processed.
        * @param    code
        *           The code to be applied to each dictionary, for the given key.  If this function
        *           returns true, the search will end.
        */
       public void apply(K key, Function<Map<K, V>, Boolean> code)
       {
          // walk all dictionaries, from the innermost scope to the global scope
          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
          while (li.hasPrevious())
          {
             Node<K, V> node = li.previous();

             Map<K, V> dictionary = node.getDictionary(false);

             if (dictionary == null || !dictionary.containsKey(key))
             {
                continue;
             }

             if (code.apply(dictionary))
             {
                break;
             }
          }
       }

       /**
        * Searches all scopes from the top of the stack down for a given entry.
        *
        * @param   key
        *          The lookup key.
        *
        * @return  The user-defined object associated with entry or <code>null</code> if not found.
        */
       public V lookup(K key)
       {
          return lookup(key, scopes.size());
       }

       /**
        * Searches all scopes from the specified scope in the stack down for a given entry.
        *
        * @param   key
        *          The lookup key.
        * @param   fromScope
        *          The 1-based index from which to start the backwards walk of scopes to be searched.
        *          For instance, to search the full dictionary, the size of the dictionary should be
        *          passed for this parameter; to search only the bottom scope, 1 should be passed.
        *
        * @return  The user-defined object associated with entry or <code>null</code> if not found.
        */
       public V lookup(K key, int fromScope)
       {
          return lookup(key, fromScope, TRUE);
       }

       /**
        * Searches all scopes from the specified scope in the stack down for a given entry.
        *
        * @param   key
        *          The lookup key.
        * @param   fromScope
        *          The 1-based index from which to start the backwards walk of scopes to be searched.
        *          For instance, to search the full dictionary, the size of the dictionary should be
        *          passed for this parameter; to search only the bottom scope, 1 should be passed.
        * @param   isValid
        *          This function should provide a boolean stating if the current scope should be
        *          returned or not. The first scope for which this function is true, will be returned.
        *
        * @return  The user-defined object associated with entry or <code>null</code> if not found,
        *          according to the validation provided.
        */
       public V lookup(K key, int fromScope, Function<V, Boolean> isValid)
       {
          // a kind of simple NPE protection in key processing, it can be null
          if (key == null)
          {
             return null;
          }

          ListIterator<Node<K, V>> li = scopes.listIterator(fromScope);
          Map<K, V> dictionary = null;
          V o = null;

          while (li.hasPrevious())
          {
             dictionary = li.previous().getDictionary(false);
             o = dictionary != null ? dictionary.get(key) : null;
             if (o != null && isValid.apply(o))
             {
                return o;
             }
          }

          return null;
       }

       /**
        * Searches all scopes bottom up, starting from the global to the innermost scope.
        *
        * @param   key
        *          The lookup key.
        *
        * @return  The user-defined object associated with entry or <code>null</code> if not found.
        */
       public V reverseLookup(K key)
       {
          return reverseLookup(key, 0);
       }

       /**
        * Searches all scopes bottom up, starting from the specified scope to the innermost scope.
        *
        * @param   key
        *          The lookup key.
        * @param   scope
        *          The 0-based scope at which to start the reverse lookup. Must be in the range
        *          {@code (scope &gt;= 0 && scope &lt; size())}.
        *
        * @return  The user-defined object associated with entry or <code>null</code> if not found.
        *
        * @throws  IndexOutOfBoundsException
        *          if {@code scope} is outside of the permitted range.
        */
       public V reverseLookup(K key, int scope)
       {
          Iterator<Node<K, V>> li = scopes.listIterator(scope);
          Map<K, V> dictionary = null;
          V o = null;

          while (li.hasNext())
          {
             dictionary = li.next().getDictionary(false);
             o = dictionary != null ? dictionary.get(key) : null;
             if (o != null)
             {
                return o;
             }
          }

          return null;
       }

       /**
        * Searches all scopes from the top of the stack down for a given entry.
        *
        * @param   key
        *          The lookup key.
        *
        * @return  The nesting level (depth) of the scope where the entry is
        *          defined first or -1 if not found.
        */
       public int locate(K key)
       {
          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
          Map<K, V> dictionary = null;
          V o = null;

          int depth = 0;
          while (li.hasPrevious())
          {
             dictionary = li.previous().getDictionary(false);
             o = dictionary != null ? dictionary.get(key) : null;
             if (o != null)
             {
                return depth;
             }
             depth ++;
          }

          return -1;
       }

       /**
        * Returns a set containing all defined keys.
        *
        * @return   The set view of all keys defined in all scopes,
        */
       public Set<K> keySet()
       {
          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
          Map<K, V> dictionary = null;
          Set<K> s = identityKeys ? Collections.newSetFromMap(factoryIdentityHashMap()) : factoryHashSetFromMap();

          while (li.hasPrevious())
          {
             dictionary = li.previous().getDictionary(false);
             if (dictionary != null)
             {
                s.addAll(dictionary.keySet());
             }
          }

          return s;
       }

       /**
        * Returns a set containing all defined keys in the scope specified.
        *
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the keys are collected. Use -1 to reference the global
        *          scope.
        *
        * @return  The set of all keys from the specified scope (and only that
        *          scope).
        */
       public Set<K> keySet(int scope)
       {
          Map<K, V> dictionary = null;
          Set<K> keys = identityKeys ? Collections.newSetFromMap(factoryIdentityHashMap())
                                     : factoryHashSetFromMap();

          if (scope == -1)
          {
             dictionary = scopes.getFirst().getDictionary(false);
             if (dictionary != null)
             {
                keys.addAll(dictionary.keySet());
             }
          }
          else
          {
             ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());

             int depth = 0;

             while (li.hasPrevious())
             {
                dictionary = li.previous().getDictionary(false);

                if (depth == scope)
                {
                   if (dictionary != null)
                   {
                      keys.addAll(dictionary.keySet());
                   }
                   break;
                }
                depth++;
             }
          }

          return keys;
       }

       /**
        * Returns a set containing all defined entries (as <code>Map.Entry</code>
        * objects).
        *
        * @return   The set view of all entries defined in all scopes,
        */
       public Set<Map.Entry<K, V>> entrySet()
       {
          ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
          Map<K, V> dictionary = null;
          Set<Map.Entry<K, V>> s = new HashSet<>();

          while (li.hasPrevious())
          {
             dictionary = li.previous().getDictionary(false);
             if (dictionary != null)
             {
                s.addAll(dictionary.entrySet());
             }
          }

          return s;
       }

       /**
        * Returns a set containing all defined entries (as <code>Map.Entry</code>
        * objects) in the scope specified.
        *
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the entries are collected. Use -1 to reference the global
        *          scope.
        *
        * @return  The set of all entries from the specified scope (and only that
        *          scope).
        */
       public Set<Map.Entry<K, V>> entrySet(int scope)
       {
          Map<K, V> dictionary = null;
          Set<Map.Entry<K, V>> entries = new HashSet<>();

          if (scope == -1)
          {
             dictionary = scopes.getFirst().getDictionary(false);
             if (dictionary != null)
             {
                entries.addAll(dictionary.entrySet());
             }
          }
          else
          {
             ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());

             int depth = 0;

             while (li.hasPrevious())
             {
                dictionary = li.previous().getDictionary(false);

                if (depth == scope)
                {
                   if (dictionary != null)
                   {
                      entries.addAll(dictionary.entrySet());
                   }
                   break;
                }
                depth++;
             }
          }

          return entries;
       }

       /**
        * Returns an unmodifiable collection view of all defined values.
        *
        * @return   The collection view of all values defined in all scopes.
        */
       public Collection<V> values()
       {
          Collection<V> view = new AbstractCollection<V>()
          {
             // iterator of scopes from most current to least current
             private final ListIterator<Node<K, V>> scopeIter = scopes.listIterator(scopes.size());

             // total number of elements across all scopes
             private int size = -1;

             // this object iterates over every value in every dictionary in every scope
             @Override
             public Iterator<V> iterator()
             {
                Iterator<V> iter = new Iterator<V>()
                {
                   // iterator over the current scope's dictionary
                   private Iterator<V> dictIter = null;

                   // next value
                   private V next = null;

                   // can another value be iterated?
                   public boolean hasNext()
                   {
                      if (next == null)
                      {
                         advance();
                      }

                      return (next != null);
                   }

                   // get the next value, if any
                   public V next()
                   {
                      if (!hasNext())
                      {
                         throw new NoSuchElementException();
                      }

                      V rv = next;
                      next = null;

                      return rv;
                   }

                   // no-op
                   public void remove()
                   {
                      throw new UnsupportedOperationException();
                   }

                   // iterate forward one element; if current node is exhausted, move to previous
                   // scope and try again
                   private void advance()
                   {
                      while (next == null)
                      {
                         if (dictIter != null && dictIter.hasNext())
                         {
                            next = dictIter.next();

                            // found one
                            return;
                         }

                         if (scopeIter.hasPrevious())
                         {
                            Node<K, V> node = scopeIter.previous();
                            Map<K, V> dict = node.getDictionary(false);
                            if (dict != null)
                            {
                               dictIter = dict.values().iterator();
                            }
                            else
                            {
                               dictIter = Collections.emptyIterator();
                            }
                         }
                         else
                         {
                            dictIter = null;

                            // nothing left to iterate
                            return;
                         }
                      }
                   }
                };

                return iter;
             }

             // returns number of all values across all scopes
             @Override
             public int size()
             {
                if (size < 0)
                {
                   int count = 0;

                   for (Node<K, V> node : scopes)
                   {
                      count += node.dictionary.size();
                   }

                   size = count;
                }

                return size;
             }
          };

          return view;
       }

       /**
        * Returns a collection containing all defined values in the scope
        * specified.
        *
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the values are collected. Use -1 to reference the global
        *          scope.
        *
        * @return  The set of all values from the specified scope (and only that
        *          scope).
        */
       public Collection<V> values(int scope)
       {
          Map<K, V> dictionary = null;
          Collection<V> values = null;

          if (scope == -1)
          {
             dictionary = scopes.getFirst().getDictionary(false);
             values = dictionary == null ? Collections.emptyList() : dictionary.values();
          }
          else
          {
             ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());

             int depth = 0;

             while (li.hasPrevious())
             {
                dictionary = li.previous().getDictionary(false);

                if (depth == scope)
                {
                   values = dictionary == null ? Collections.emptyList() : dictionary.values();
                   break;
                }
                depth++;
             }
          }

          if (values == null)
          {
             return Collections.emptyList();
          }

          return Collections.unmodifiableCollection(values);
       }

       /**
        * Prints a report of all entries found by scope, starting at the bottom
        * of the stack (of scopes) working toward the top.
        *
        * @param   output
        *          <code>PrintStream</code> object to which to dump.
        */
       public void dump(PrintStream output)
       {
          dump(new PrintWriter(output, true));
       }

       /**
        * Prints a report of all entries found by scope, starting at the bottom
        * of the stack (of scopes) working toward the top.
        *
        * @param   output
        *          <code>PrintWriter</code> object to which to dump.
        */
       public void dump(PrintWriter output)
       {
          ListIterator<Node<K, V>> li = scopes.listIterator(0);
          Node<K, V> n = null;

          int depth = 0;
          while (li.hasNext())
          {
             n = li.next();
             dumpScope(n, depth++, "", output);
          }

          output.println("=================================");
       }

       /**
        * Prints a report of all entries found in the current scope.
        *
        * @param   text
        *          Additional text to print.
        * @param   output
        *          <code>PrintStream</code> object to which to dump.
        */
       public void dumpCurrentScope(String text, PrintStream output)
       {
          dumpCurrentScope(text, new PrintWriter(output, true));
       }

       /**
        * Prints a report of all entries found in the current scope.
        *
        * @param   text
        *          Additional text to print.
        * @param   output
        *          <code>PrintWriter</code> object to which to dump.
        */
       public void dumpCurrentScope(String text, PrintWriter output)
       {
          Node<K, V> n = scopes.getLast();
          if (n != null)
          {
             dumpScope(n, scopes.size(), text, output);
          }
       }

       /**
        * Factory method for an {@link IdentityHashMap}
        *
        * @return  a new {@link IdentityHashMap}
        */
       protected Map<K, Boolean> factoryIdentityHashMap()
       {
          return new IdentityHashMap<>();
       }

       /**
        * Factory method for a {@link Set} as returned by {@link #keySet}
        *
        * @return  a new {@link HashSet}
        */
       protected Set<K> factoryHashSetFromMap()
       {
          return new HashSet<>();
       }

       /**
        * Factory method for an {@link IdentityHashMap} at the scope items (the {@link Node} inner class)
        *
        * @param size
        *        The maximum expected size of the Map
        *
        * @return  a new {@link IdentityHashMap}
        */
       protected Map<K, V> factoryNodeIdentityHashMap(int size)
       {
          return new IdentityHashMap<>(size);
       }

       /**
        * Factory method for a {@link HashMap} at the scope items (the {@link Node} inner class)
        *
        * @param size
        *        The maximum expected size of the Map
        *
        * @return  a new {@link HashMap}
        */
       protected Map<K, V> factoryNodeHashMap(int size)
       {
          return new HashMap<>(size);
       }

       /**
        * Obtain the node at the specified depth from the top of the stack.
        *
        * @param   scope
        *          The depth (in number of scopes from the top of the stack) from
        *          which the value must be gotten. Use -1 to reference the global
        *          scope.
        *
        * @return  Node associated with the specified scope.
        */
       protected Node<K, V> getNodeAt(int scope)
       {
          if (scopes.isEmpty())
          {
             return null;
          }

          if (scope == 0)
          {
             // this is the most used call
             return scopes.getLast();
          }
          else if (scope == -1)
          {
             return scopes.getFirst();
          }
          else
          {
             int sz  = scopes.size();
             int idx = sz - 1 - scope;

             if (idx >= 0 && idx < sz)
             {
                return scopes.get(idx);
             }
          }

          return null;
       }

       /**
        * Prints a report of all entries found in a given scope.
        *
        * @param   n
        *          The <code>Node</code> instance to dump.
        * @param   depth
        *          The indent level.
        * @param   text
        *          Additional text to print.
        * @param   output
        *          <code>PrintWriter</code> object to which to dump.
        */
       private void dumpScope(Node<K,V> n, int depth, String text, PrintWriter output)
       {
          Iterator<Map.Entry<K, V>> si = null;
          StringBuilder indent = new StringBuilder();

          for (int i = 0; i < depth - 1; i ++)
          {
             indent.append("--- ");
          }

          output.println(indent + text + " scope " + (depth + 1) + " --- " + n.getExtra());
          Map<K, V> dict = n.getDictionary(false);
          if (dict != null)
          {
             si = dict.entrySet().iterator();

             indent.append("    ");
             while (si.hasNext())
             {
                output.println(indent.toString() + si.next());
             }
          }
       }

       /**
        * Represents complex items on the stack of scopes.
        * Every item is made of a dictionary and a user-specific object.
        */
       protected static class Node<K, V>
       implements Cloneable
       {
          /** Represents an instance of dictionary. */
          private Map<K, V> dictionary = null;

          /** Stores a user supplied object associated with the dictionary. */
          private Object extra = null;

          /** Flag indicating if the {@link #dictionary}'s keys can use the identity hash code. */
          private final boolean identityKeys;

          /** Points to a generator function that supplies a new IdentityHashMap. */
          private Function<Integer, Map<K,V>> supplyIdentityHashMap;

          /** Points to a generator function that supplies a new HashMap. */
          private Function<Integer, Map<K,V>> supplyHashMap;

          /**
           * The only constructor.
           *
           * @param   extra
           *          Any object that will be associated with this node.
           * @param   identityKeys
           *          When <code>true</code>, the {@link #dictionary} will be an {@link IdentityHashMap}.
           * @param   supplyIdentityHashMap
           *          Points to a generator function that supplies a new IdentityHashMap.
           * @param   supplyHashMap
           *          Points to a generator function that supplies a new HashMap.
           */
          private Node(Object                      extra,
                       boolean                     identityKeys,
                       Function<Integer, Map<K,V>> supplyIdentityHashMap,
                       Function<Integer, Map<K,V>> supplyHashMap)
          {
             this.extra = extra;
             this.identityKeys = identityKeys;
             this.supplyIdentityHashMap = supplyIdentityHashMap;
             this.supplyHashMap = supplyHashMap;
          }

          /**
           * Clone this instance.
           *
           * @return   A copy of this instance.
           */
          @Override
          protected Node<K, V> clone()
          {
             Node<K, V> node = new Node<>(extra, identityKeys, supplyIdentityHashMap, supplyHashMap);
             node.dictionary = null;

             if (dictionary != null)
             {
                node.dictionary = new HashMap<>();
                node.dictionary.putAll(this.dictionary);
             }

             return node;
          }

          /**
           * Accesses the dictionary at this node.  If no dictionary is associated
           * with this node, one can be created optionally.  Otherwise, an empty,
           * immutable map is returned.
           *
           * @param   create
           *          <code>true</code> to create a dictionary for this node if
           *          one does not already exist;  <code>false</code> to have <code>null</code> returned if one
           *          does not already exist.
           *
           * @return  Map object associated with this node, or <code>null</code> if there is no map object
           *          associated with this node and 'create' flag is false.
           */
          public Map<K, V> getDictionary(boolean create)
          {
             if (dictionary == null)
             {
                if (create)
                {
                   dictionary = (identityKeys ? supplyIdentityHashMap.apply(4) : supplyHashMap.apply(4));
                }
                else
                {
                   return null;
                }
             }

             return dictionary;
          }

          /**
           * Accesses the user supplied object at this node.
           *
           * @return  Object associated with this node.
           */
          public Object getExtra()
          {
             return extra;
          }

          /**
           * Replaces the user supplied object at this node.
           *
           * @param   extra
           *          Any object that will be associated with this node.
           */
          public void setExtra(Object extra)
          {
             this.extra = extra;
          }
       }
    }