/*
** Module   : ScopedDictionary.java
** Abstract : Provides multiscoped dictionary functionality.
**
** Copyright (c) 2004-2009, Golden Code Development Corporation.
**
** -#- -I- --Date-- -----------------------Description------------------------
** 001 ECF 20051028 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 Added new method getScopeAt(int) which gives access to the
**                  user objects at any depth.
** 003 ECF 20060208 Added values() and entrySet() methods. These are analogs
**                  to the keySet() methods to round out the map-like API.
** 004 NVS 20070118 Added new methods to replace the extra object in the current
**                  or any other scope.
** 005 ECF 20071029 Implemented generics. Intentionally left the 'extra' data as
**                  Object for now.
** 006 GES 20080308 Added writer support to dump methods so that I18N issues
**                  can be improved.
** 007 SIY 20080904 Minor cleanups.
** 008 ECF 20090115 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 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.
*/

/*
** 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 should have received a copy of the GNU Affero General Public License
** along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

package com.goldencode.lang;

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

/**
 * 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>
 * @author NVS
 * @author ECF
 * @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<Node<K, V>>();

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

   /**
    * Copy constructor. This will create an instance with a new list of scopes
    * that has as its contents the same exact scopes as the original (the
    * scope instances are the same, but exist in two separate lists that have
    * indentical contents).
    * <p>
    * This means that the maintenance of the list of scopes can safely be done
    * independently between the two copies. Scopes can be deleted (even if they
    * are common scopes) and scopes can be added. The scope list changes will
    * only be visible in the instance on which they are made.
    * <p>
    * This must be differentiated from how the contents of a scope are managed.
    * Since the current scope instances themselves are shared, any modifications
    * to the contents of the existing scopes must be properly synchronized
    * because the changes will be shared between all dictionaries that have
    * been duplicated in this manner. This means that any entries added, changed
    * or removed in common scopes will be visible to all duplicated instances.
    *
    * @param    original
    *           The instance to copy from.
    */
   public ScopedDictionary(ScopedDictionary<K, V> original)
   {
      scopes.addAll(original.scopes);
   }

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

   /**
    * 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();
      else
         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)
   {
      if (scope == -1)
      {
         return scopes.getFirst().getExtra();
      }
      else
      {
         ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
         
         int depth = 0;
         
         while (li.hasPrevious())
         {
            Node<K, V> n = li.previous();
            if (depth == scope)
            {
               return n.getExtra();
            }
            depth++;
         }
      }

      return null;
   }

   /**
    * 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)
   {
      if (scope == -1)
      {
         scopes.getFirst().setExtra(extra);
         return;
      }
      else
      {         
         ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
         
         int depth = 0;
         
         while (li.hasPrevious())
         {
            Node<K, V> n = li.previous();
            if (depth == scope)
            {
               n.setExtra(extra);
               return;
            }
            depth++;
         }
      }
   }

   /**
    * 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.containsKey(key);
      dictionary.put(key, value);
      
      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.
    * @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)
   {
      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 (depth == scope)
         {
            return node.getDictionary(create);
         }
      }

      return null;
   }

   /**
    * Removes 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)
   {
      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 (depth == scope)
         {
            key = processKey(key);
            
            return (node.getDictionary(false).remove(key) != null);
         }
      }

      return false;
   }
   
   /**
    * 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)
   {
      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 (depth == scope)
         {
            key = processKey(key);
            node.getDictionary(true).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)
   {
      V result = null;
      
      if (scope == -1)
      {
         key = processKey(key);
         Map<K, V> dictionary = scopes.getFirst().getDictionary(false);
         result = dictionary.get(key);
      }
      else
      {         
         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 (depth == scope)
            {
               key = processKey(key);
               result = node.getDictionary(false).get(key);
               
               break;
            }
         }
      }

      return result;
   }
   
   /**
    * 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)
   {
      ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
      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 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<K>();

      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<K>();
      
      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<Map.Entry<K, V>>();

      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<Map.Entry<K, V>>();
      
      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 a collection containing all defined values.
    *
    * @return   The collection view of all values defined in all scopes,
    */
   public Collection<V> values()
   {
      ListIterator<Node<K, V>> li = scopes.listIterator(scopes.size());
      Map<K, V> dictionary = null;
      List<V> values = new ArrayList<V>();

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

      return values;
   }

   /**
    * 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;
      List<V> values = new ArrayList<V>();
      
      if (scope == -1)
      {
         dictionary = scopes.getFirst().getDictionary(false);
         values.addAll(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.addAll(dictionary.values());
               break;
            }
            depth++;
         }
      }
      
      return 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.
    */
   protected K processKey(K key)
   {
      return key;
   }
   
   /**
    * 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 --- " + 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.
    *
    * @param   <K>
    *          Dictionary key type
    * @param   <V>
    *          Dictionary value type
    */
   protected static class Node<K, V>
   {
      /** 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;
      }

      /**
       * 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<K, V>(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;
      }
   }
}