FWD » Core Development » Database

/*

** Module   : ScopedDictionary.java

** Abstract : Provides multiscoped dictionary functionality.

**

** Copyright (c) 2004-2020, 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.

*/

/*

** 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 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>

{

   /** Implements stackable scopes */

   private LinkedList<Node<K, V>> scopes = new LinkedList<>();

   /**

    * 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);

   }

   /**

    * 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));

   }

   /**

    * 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.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);

      key = processKey(key);

      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);

      key = processKey(key);

      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;

      key = processKey(key);

      while (li.hasPrevious())

      {

         dictionary = li.previous().getDictionary(false);

         if (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())

      {

         li.previous().getDictionary(false).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;

      key = processKey(key);

      int depth = 0;

      while (li.hasPrevious())

      {

         dictionary = li.previous().getDictionary(false);

         o = dictionary.get(key);

         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);

      return (node != null) ? node.getDictionary(create) : 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)

   {

      key = processKey(key);

      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();

         if (node.getDictionary(false).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(processKey(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(processKey(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(processKey(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.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)

   {

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

      Map<K, V> dictionary = null;

      V o = null;

      key = processKey(key);

      while (li.hasPrevious())

      {

         dictionary = li.previous().getDictionary(false);

         o = dictionary.get(key);

         if (o != null)

         {

            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 >= 0 && scope < 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;

      key = processKey(key);

      while (li.hasNext())

      {

         dictionary = li.next().getDictionary(false);

         o = dictionary.get(key);

         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;

      key = processKey(key);

      int depth = 0;

      while (li.hasPrevious())

      {

         dictionary = li.previous().getDictionary(false);

         o = dictionary.get(key);

         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 = new HashSet<>();

      while (li.hasPrevious())

      {

         dictionary = li.previous().getDictionary(false);

         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 = new HashSet<>();

      if (scope == -1)

      {

         dictionary = scopes.getFirst().getDictionary(false);

         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)

            {

               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);

         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);

         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)

            {

               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();

                        dictIter = node.getDictionary(false).values().iterator();

                     }

                     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.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.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);

      }

   }

   /**

    * Prints a report of all entries found by scope, starting at the bottom

    * of the stack (of scopes) working toward the top. Uses the

    * <code>System.err</code> stream for output.

    */

   public void dump()

   {

      dump(System.err);

   }

   /**

    * Subclasses which need to process the dictionary lookup key before it is

    * used must override this method.  This default implementation simply

    * returns the <code>key</code> argument unchanged.

    *

    * @param   key

    *          The lookup key.

    *

    * @return  The <code>key</code> argument.

    */

   public K processKey(K key)

   {

      return key;

   }

   /**

    * 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)

   {

      Node<K, V> node = null;

      if (scope == -1)

      {

         node = scopes.getFirst();

      }

      else if (scope == 0)

      {

         node = scopes.getLast();

      }

      else

      {

         int sz  = scopes.size();

         int idx = sz - 1 - scope;

         if (idx >= 0 && idx < sz)

         {

            node = scopes.get(idx);

         }

      }

      return node;

   }

   /**

    * 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());

      si = n.getDictionary(false).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;

      /**

       * The only constructor.

       *

       * @param   extra

       *          Any object that will be associated with this node.

       */

      public Node(Object extra)

      {

         this.extra = extra;

      }

      /**

       * Clone this instance.

       * 

       * @return   A copy of this instance.

       */

      @Override

      protected Node<K, V> clone()

      {

         Node<K, V> node = new Node<>(this.extra);

         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 use have

       *          an empty (immutable) dictionary returned if one does not

       *          already exist.

       *

       * @return  Map object associated with this node, or an empty map if no

       *          such association exists.

       */

      public Map<K, V> getDictionary(boolean create)

      {

         if (dictionary == null)

         {

            if (create)

            {

               dictionary = new HashMap<>(4);

            }

            else

            {

               return Collections.emptyMap();

            }

         }

         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;

      }

   }

}