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 >= 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;
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;
}
}
}