+ * returns a search order for buckets. This method can be used for optimizing a search for + * equal symbols. The client of this class can store symbols in buckets of similar symbols. + * Those buckets get an id denoted by an integer. The most appropriate bucket for a symbol is + * the first element in the array returned by this method. The symbol should therefore be put + * into that bucket. + *
+ *+ * In case a search for an equal symbol shall be performed at the client side, the client + * checks the available buckets in the order given as return value of this method. All other + * buckets are searched afterwards. In this scenario it is ensured, that the equal symbol is + * found as soon as possible as the search always starts in the most appropriate bucket. + * However, the other buckets are searched, as well, if no equal symbol is found. Therefore, + * in the worst case, all buckets are searched. In the optimal case, the equal symbol is found + * in the first bucket. + *
+ *+ * The returned array should contain different integers in each field. This allows a most + * efficient search. If an integer is repeated, it is up to the clien, if this is ignored. + *
+ * + * @param symbol the symbol for which the bucket order is to be returned + * + * @return a search order for buckets as described + * + * @see SymbolMap + */ + public int[] getBucketSearchOrder(T symbol); } Index: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java =================================================================== --- trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java (revision 1251) +++ trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java (revision 1251) @@ -0,0 +1,867 @@ +// Copyright 2012 Georg-August-Universität Göttingen, Germany +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package de.ugoe.cs.autoquest.usageprofiles; + +import java.io.Serializable; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.HashMap; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; + +/** + *+ * This class is a data structure for holding symbols which is more efficient than a simple list. + * This data structure can be used with a comparator to adapt the effective list behavior and to + * define the equals strategy for comparing objects. After a certain size ({@link #MAX_LIST_SIZE}), + * the symbol map creates a symbol index consisting of buckets. This allows searching for symbols + * in a more efficient order as the search can start in the most appropriate of the internal + * buckets. + *
+ *+ * The class is called a map, although it is not. It may contain the same element as separate keys. + * This implementation is done for performance improvements. If it is required to really assure, + * that a key exists only once, then each call to the {@link #addSymbol(Object, Object)} method + * should be done only, if the {@link #containsSymbol(Object)} method for the same symbol returns + * false. + *
+ * + * @see SymbolComparator + * + * @author Patrick Harms + */ +public class SymbolMap+ * default serial version UID + *
+ */ + private static final long serialVersionUID = 1L; + + /** + *+ * the maximum number of symbols in this map which is still only treated as list instead of + * using buckets. + *
+ */ + private static final int MAX_LIST_SIZE = 15; + + /** + *+ * Comparator to be used for comparing the symbols with each other and to determine a bucket + * search order + *
+ */ + private SymbolComparator+ * Internally maintained plain list of symbols and associated values + *
+ */ + private List+ * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the symbol index using buckets + * for optimizing the search order. + *
+ */ + private Map+ * When using buckets, not any symbol may be associated a correct bucket by the used + * comparator. Therefore, we set a default bucket for all such symbols. This may change + * if the comparator defines the same bucket for a specific symbol. + *
+ */ + private int defaultBucket = 0; + + /** + *+ * Instantiates a symbol map with a comparator + *
+ * + * @param comparator the comparator to use for comparing symbols and for determining bucket + * search orders + * + * @throws IllegalArgumentException if the provided comparator is null + */ + public SymbolMap(SymbolComparator+ * Copy constructure + *
+ * + * @param otherMap the other map to be copied including its comparator + * + * @throws IllegalArgumentException if the provided other map is null + */ + public SymbolMap(SymbolMap+ * Returns the size of the map, i.e. the number of symbol entries + *
+ * + * @return as described + */ + public int size() { + return symbolList.size(); + } + + /** + *+ * Returns true if this map is empty, i.e. if {@link #size()} returns 0 + *
+ * + * @return as described + */ + public boolean isEmpty() { + return symbolList.isEmpty(); + } + + /** + *+ * Returns true if the provided symbol was stored in this map. + *
+ * + * @param symbol the symbol to check if it was stored in this map + * + * @return as described + * + * @throws IllegalArgumentException if the provided symbol is null + */ + public boolean containsSymbol(K symbol) { + if (symbol == null) { + throw new IllegalArgumentException("symbol must not be null"); + } + + return getEntry(symbol) != null; + } + + /** + *+ * Returns the value associated to the provided symbol in this map. If there is no value + * associated to the given symbol or if the symbol is not stored in this map, the method + * returns null. + *
+ * + * @param symbol the symbol to return the value for + * + * @return as described + * + * @throws IllegalArgumentException if the provided symbol is null + */ + public V getValue(K symbol) { + if (symbol == null) { + throw new IllegalArgumentException("symbol must not be null"); + } + + Map.Entry+ * Adds a symbol and an associated value to the map. If the value is null, the symbol is added, + * anyway and {@link #containsSymbol(Object)} will return true for that symbol. Adding the + * same symbol twice will produce two entries. This is contradictory to typical map + * implementations. To prevent this, the {@link #containsSymbol(Object)} and + * {@link #removeSymbol(Object)} methods should be used to ensure map behavior. + *
+ * + * @param symbol the symbol to add to the map + * @param value the value to associate to the symbol in this map + * + * @return as described + * + * @throws IllegalArgumentException if the provided symbol is null + */ + public void addSymbol(K symbol, V value) { + if (symbol == null) { + throw new IllegalArgumentException("symbol must not be null"); + } + + Map.Entry+ * Removes a symbol and its associated value from the map. If the symbol is stored several + * times, the first of its occurrences is removed. + *
+ * + * @param symbol the symbol to be removed from the map + * + * @return as described + * + * @throws IllegalArgumentException if the provided symbol is null + */ + public V removeSymbol(K symbol) { + if (symbol == null) { + throw new IllegalArgumentException("symbol must not be null"); + } + + for (int i = 0; i < symbolList.size(); i++) { + if (comparator.equals(symbolList.get(i).getKey(), symbol)) { + // found the symbol. Remove it from the list, and if required, also from the map. + V value = symbolList.remove(i).getValue(); + + if (symbolList.size() > MAX_LIST_SIZE) { + removeFromSymbolBuckets(symbol); + } + + return value; + } + } + + return null; + } + + /** + *+ * Returns a collection of all symbols in this map. + *
+ * + * @return as described + */ + public Collection+ * Returns a collection of all values associated to symbols in this map. May contain null + * values, if some of the symbols are mapped to null. The length of the returned collection + * is in any case the same as the size of the map. + *
+ * + * @return as described + */ + public Collection+ * Removes all symbols and associated values from the map. + *
+ */ + public void clear() { + symbolList.clear(); + symbolBuckets = null; + } + + /* (non-Javadoc) + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + return symbolList.size(); + } + + /* (non-Javadoc) + * @see java.lang.Object#equals(java.lang.Object) + */ + @SuppressWarnings("unchecked") + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + else if (this.getClass().isInstance(obj)) { + SymbolMap+ * Internally used to create symbol buckets in case the number of stored symbols increased + * above {@link #MAX_LIST_SIZE}. + *
+ */ + private void createSymbolBuckets() { + //System.out.println("creating symbol buckets"); + symbolBuckets = new HashMap+ * Adds a symbol and its value to its corresponding bucket. The corresponding bucket is + * retrieved from the symbol comparator. It is the first element of the search order returned + * by the symbol comparator. If the comparator does not define a search order for the symbol + * the entry is added to the default bucket. If the comparator defines a bucket id + * identical to the default bucket id, the default bucket id is shifted to another value. + *
+ */ + private void addToSymbolBucket(Map.Entry+ * Removes the entry for a given symbol from the buckets. It uses the bucket search order + * defined by the symbol comparator to find the symbol as fast as possible. + *
+ */ + private Map.Entry+ * Updates the default bucket id to a new one + *
+ */ + private void setNewDefaultBucketId() { + int oldDefaultBucket = defaultBucket; + do { + defaultBucket += 1; + } + while (symbolBuckets.containsKey(defaultBucket)); + + symbolBuckets.put(defaultBucket, symbolBuckets.get(oldDefaultBucket)); + } + + /** + *+ * searches for the entry belonging to the given symbol. The method either uses the list if + * buckets are not used yet, or it uses the buckets and searches them in the order defined + * by the comparator. If the symbol isn't found and the comparator does not refer all buckets, + * then also the other buckets are searched for the symbol. + *
+ */ + private Map.Entry+ * Convenience method to look up a symbol in a list of entries using the comparator. + *
+ */ + private Map.Entry+ * Internally used data structure for storing symbol value pairs + *
+ * + * @author Patrick Harms + */ + private class SymbolMapEntry implements Map.Entry+ * Simple constructor for initializing the entry with a symbol and its associated value. + *
+ */ + private SymbolMapEntry(K symbol, V value) { + super(); + this.symbol = symbol; + this.value = value; + } + + /* (non-Javadoc) + * @see java.util.Map.Entry#getKey() + */ + @Override + public K getKey() { + return symbol; + } + + /* (non-Javadoc) + * @see java.util.Map.Entry#getValue() + */ + @Override + public V getValue() { + return value; + } + + /* (non-Javadoc) + * @see java.util.Map.Entry#setValue(java.lang.Object) + */ + @Override + public V setValue(V value) { + V oldValue = this.value; + this.value = value; + return oldValue; + } + + /* (non-Javadoc) + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + return symbol.hashCode(); + } + + /* (non-Javadoc) + * @see java.lang.Object#equals(java.lang.Object) + */ + @SuppressWarnings("unchecked") + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + else if (this.getClass().isInstance(obj)) { + SymbolMapEntry other = (SymbolMapEntry) obj; + return (symbol.equals(other.symbol) && + (value == null ? other.value == null : value.equals(other.value))); + } + else { + return false; + } + } + + } + + /** + *+ * Used to create an efficient facade for accessing the internal list of entries either only + * for the symbols or only for the values. It is a default implementation of the collection + * interface. The entry facade provided to the constructor decides, if either the list + * accesses only the symbols or only the values. + *
+ * + * @author Patrick Harms + */ + private class ReadOnlyCollectionFacade+ * Initializes the facade with the facaded list and the facade to be used for the entries + *
+ */ + private ReadOnlyCollectionFacade(List+ * Implementation of an iterator to facade an iterator on the internal list of symbol entries. + *
+ * + * @author Patrick Harms + */ + private class ReadOnlyCollectionIteratorFacade+ * initialized this facade with the facaded iterator and the entry facade to be used for + * the entries. + *
+ */ + private ReadOnlyCollectionIteratorFacade(Iterator+ * Used to facade symbol entries and to return only this part of an entry, that is relevant. + *
+ * + * @author Patrick Harms + */ + private abstract class EntryFacade+ * Returns only the part of an entry that is relevant or required. + *
+ * + * @param entry of which the part shall be returned + * + * @return the part of the entry to be returned + */ + protected abstract T getFacadedElement(Entry+ * Implementation of the entry facade returning the entries key, i.e. the symbol. + *
+ * + * @author Patrick Harms + */ + private class SymbolFacade extends EntryFacade+ * Implementation of the entry facade returning the entries value, i.e. the value associated to + * the symbol. + *
+ * + * @author Patrick Harms + */ + private class ValueFacade extends EntryFacade- * Adds a given subsequence to the trie and increases the counters accordingly. + * Adds a given subsequence to the trie and increases the counters accordingly. NOTE: This + * method does not add the symbols to the list of known symbols. This is only ensured using + * the method {@link #train(List, int)}. *
* @@ -162,5 +163,4 @@ protected void add(List- * adds a list of new symbols to the collection of known symbols. Uses the - * {@link #addToKnownSymbols(Object)} method for each element of the provided list. - *
- * - * @param symbols the list of symbols to be added to the known symbols - */ - private void addToKnownSymbols(List
@@ -115,5 +115,5 @@
this.symbol = null;
count = 0;
- children = new LinkedList