001/**
002 *
003 * Copyright (c) 2014, the Railo Company Ltd. All rights reserved.
004 *
005 * This library is free software; you can redistribute it and/or
006 * modify it under the terms of the GNU Lesser General Public
007 * License as published by the Free Software Foundation; either 
008 * version 2.1 of the License, or (at your option) any later version.
009 * 
010 * This library is distributed in the hope that it will be useful,
011 * but WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013 * Lesser General Public License for more details.
014 * 
015 * You should have received a copy of the GNU Lesser General Public 
016 * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
017 * 
018 **/
019/*
020 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
021 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
022 *
023 *
024 *
025 *
026 *
027 *
028 *
029 *
030 *
031 *
032 *
033 *
034 *
035 *
036 *
037 *
038 *
039 *
040 *
041 *
042 */
043
044package lucee.commons.collection;
045
046import java.io.Externalizable;
047import java.util.Collection;
048import java.util.HashMap;
049import java.util.Iterator;
050import java.util.Map;
051import java.util.Set;
052
053import lucee.runtime.exp.ExpressionException;
054import lucee.runtime.exp.PageException;
055
056public abstract class AbstractMapPro<K,V> implements MapPro<K,V>,Externalizable {
057    /**
058     * Sole constructor.  (For invocation by subclass constructors, typically
059     * implicit.)
060     */
061    protected AbstractMapPro() {
062    }
063    
064    // TODO better implementation
065    @Override
066    public void writeExternal(java.io.ObjectOutput out) throws java.io.IOException {
067        out.writeObject(new HashMap(this));
068    }
069    @Override
070    public void readExternal(java.io.ObjectInput in) throws java.io.IOException, ClassNotFoundException {
071        this.putAll((Map)in.readObject());
072    }
073    
074    
075
076    // Query Operations
077
078    /**
079     * {@inheritDoc}
080     *
081     * <p>This implementation returns <tt>entrySet().size()</tt>.
082     */
083    public int size() {
084        return entrySet().size();
085    }
086
087    /**
088     * {@inheritDoc}
089     *
090     * <p>This implementation returns <tt>size() == 0</tt>.
091     */
092    public boolean isEmpty() {
093        return size() == 0;
094    }
095
096    /**
097     * {@inheritDoc}
098     *
099     * <p>This implementation iterates over <tt>entrySet()</tt> searching
100     * for an entry with the specified value.  If such an entry is found,
101     * <tt>true</tt> is returned.  If the iteration terminates without
102     * finding such an entry, <tt>false</tt> is returned.  Note that this
103     * implementation requires linear time in the size of the map.
104     *
105     * @throws ClassCastException   {@inheritDoc}
106     * @throws NullPointerException {@inheritDoc}
107     */
108    public boolean containsValue(Object value) {
109        Iterator<Entry<K,V>> i = entrySet().iterator();
110        if (value==null) {
111            while (i.hasNext()) {
112                Entry<K,V> e = i.next();
113                if (e.getValue()==null)
114                    return true;
115            }
116        } else {
117            while (i.hasNext()) {
118                Entry<K,V> e = i.next();
119                if (value.equals(e.getValue()))
120                    return true;
121            }
122        }
123        return false;
124    }
125
126    /**
127     * {@inheritDoc}
128     *
129     * <p>This implementation iterates over <tt>entrySet()</tt> searching
130     * for an entry with the specified key.  If such an entry is found,
131     * <tt>true</tt> is returned.  If the iteration terminates without
132     * finding such an entry, <tt>false</tt> is returned.  Note that this
133     * implementation requires linear time in the size of the map; many
134     * implementations will override this method.
135     *
136     * @throws ClassCastException   {@inheritDoc}
137     * @throws NullPointerException {@inheritDoc}
138     */
139    public boolean containsKey(Object key) {
140        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
141        if (key==null) {
142            while (i.hasNext()) {
143                Entry<K,V> e = i.next();
144                if (e.getKey()==null)
145                    return true;
146            }
147        } else {
148            while (i.hasNext()) {
149                Entry<K,V> e = i.next();
150                if (key.equals(e.getKey()))
151                    return true;
152            }
153        }
154        return false;
155    }
156
157    /**
158     * {@inheritDoc}
159     *
160     * <p>This implementation iterates over <tt>entrySet()</tt> searching
161     * for an entry with the specified key.  If such an entry is found,
162     * the entry's value is returned.  If the iteration terminates without
163     * finding such an entry, <tt>null</tt> is returned.  Note that this
164     * implementation requires linear time in the size of the map; many
165     * implementations will override this method.
166     *
167     * @throws ClassCastException            {@inheritDoc}
168     * @throws NullPointerException          {@inheritDoc}
169     */
170    public V get(Object key) {
171        Iterator<Entry<K,V>> i = entrySet().iterator();
172        if (key==null) {
173            while (i.hasNext()) {
174                Entry<K,V> e = i.next();
175                if (e.getKey()==null)
176                    return e.getValue();
177            }
178        } else {
179            while (i.hasNext()) {
180                Entry<K,V> e = i.next();
181                if (key.equals(e.getKey()))
182                    return e.getValue();
183            }
184        }
185        return null;
186    }
187
188
189    // Modification Operations
190
191    /**
192     * {@inheritDoc}
193     *
194     * <p>This implementation always throws an
195     * <tt>UnsupportedOperationException</tt>.
196     *
197     * @throws UnsupportedOperationException {@inheritDoc}
198     * @throws ClassCastException            {@inheritDoc}
199     * @throws NullPointerException          {@inheritDoc}
200     * @throws IllegalArgumentException      {@inheritDoc}
201     */
202    public V put(K key, V value) {
203        throw new UnsupportedOperationException();
204    }
205
206    /**
207     * {@inheritDoc}
208     *
209     * <p>This implementation iterates over <tt>entrySet()</tt> searching for an
210     * entry with the specified key.  If such an entry is found, its value is
211     * obtained with its <tt>getValue</tt> operation, the entry is removed
212     * from the collection (and the backing map) with the iterator's
213     * <tt>remove</tt> operation, and the saved value is returned.  If the
214     * iteration terminates without finding such an entry, <tt>null</tt> is
215     * returned.  Note that this implementation requires linear time in the
216     * size of the map; many implementations will override this method.
217     *
218     * <p>Note that this implementation throws an
219     * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt>
220     * iterator does not support the <tt>remove</tt> method and this map
221     * contains a mapping for the specified key.
222     *
223     * @throws UnsupportedOperationException {@inheritDoc}
224     * @throws ClassCastException            {@inheritDoc}
225     * @throws NullPointerException          {@inheritDoc}
226     */
227    public V remove(Object key) {
228        Iterator<Entry<K,V>> i = entrySet().iterator();
229        Entry<K,V> correctEntry = null;
230        if (key==null) {
231            while (correctEntry==null && i.hasNext()) {
232                Entry<K,V> e = i.next();
233                if (e.getKey()==null)
234                    correctEntry = e;
235            }
236        } else {
237            while (correctEntry==null && i.hasNext()) {
238                Entry<K,V> e = i.next();
239                if (key.equals(e.getKey()))
240                    correctEntry = e;
241            }
242        }
243
244        V oldValue = null;
245        if (correctEntry !=null) {
246            oldValue = correctEntry.getValue();
247            i.remove();
248        }
249        return oldValue;
250    }
251
252
253    // Bulk Operations
254
255    /**
256     * {@inheritDoc}
257     *
258     * <p>This implementation iterates over the specified map's
259     * <tt>entrySet()</tt> collection, and calls this map's <tt>put</tt>
260     * operation once for each entry returned by the iteration.
261     *
262     * <p>Note that this implementation throws an
263     * <tt>UnsupportedOperationException</tt> if this map does not support
264     * the <tt>put</tt> operation and the specified map is nonempty.
265     *
266     * @throws UnsupportedOperationException {@inheritDoc}
267     * @throws ClassCastException            {@inheritDoc}
268     * @throws NullPointerException          {@inheritDoc}
269     * @throws IllegalArgumentException      {@inheritDoc}
270     */
271    public void putAll(Map<? extends K, ? extends V> m) {
272        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
273            put(e.getKey(), e.getValue());
274    }
275
276    /**
277     * {@inheritDoc}
278     *
279     * <p>This implementation calls <tt>entrySet().clear()</tt>.
280     *
281     * <p>Note that this implementation throws an
282     * <tt>UnsupportedOperationException</tt> if the <tt>entrySet</tt>
283     * does not support the <tt>clear</tt> operation.
284     *
285     * @throws UnsupportedOperationException {@inheritDoc}
286     */
287    public void clear() {
288        entrySet().clear();
289    }
290
291
292    // Views
293
294    /**
295     * Each of these fields are initialized to contain an instance of the
296     * appropriate view the first time this view is requested.  The views are
297     * stateless, so there's no reason to create more than one of each.
298     */
299    transient volatile Set<K>        keySet = null;
300    transient volatile Collection<V> values = null;
301
302    /**
303     * {@inheritDoc}
304     *
305     * <p>This implementation returns a set that subclasses {@link AbstractSet}.
306     * The subclass's iterator method returns a "wrapper object" over this
307     * map's <tt>entrySet()</tt> iterator.  The <tt>size</tt> method
308     * delegates to this map's <tt>size</tt> method and the
309     * <tt>contains</tt> method delegates to this map's
310     * <tt>containsKey</tt> method.
311     *
312     * <p>The set is created the first time this method is called,
313     * and returned in response to all subsequent calls.  No synchronization
314     * is performed, so there is a slight chance that multiple calls to this
315     * method will not all return the same set.
316     */
317    public Set<K> keySet() {
318        if (keySet == null) {
319            keySet = new AbstractSet<K>() {
320                public Iterator<K> iterator() {
321                    return new Iterator<K>() {
322                        private Iterator<Entry<K,V>> i = entrySet().iterator();
323
324                        public boolean hasNext() {
325                            return i.hasNext();
326                        }
327
328                        public K next() {
329                            return i.next().getKey();
330                        }
331
332                        public void remove() {
333                            i.remove();
334                        }
335                    };
336                }
337
338                public int size() {
339                    return AbstractMapPro.this.size();
340                }
341
342                public boolean isEmpty() {
343                    return AbstractMapPro.this.isEmpty();
344                }
345
346                public void clear() {
347                    AbstractMapPro.this.clear();
348                }
349
350                public boolean contains(Object k) {
351                    return AbstractMapPro.this.containsKey(k);
352                }
353            };
354        }
355        return keySet;
356    }
357
358    /**
359     * {@inheritDoc}
360     *
361     * <p>This implementation returns a collection that subclasses {@link
362     * AbstractCollection}.  The subclass's iterator method returns a
363     * "wrapper object" over this map's <tt>entrySet()</tt> iterator.
364     * The <tt>size</tt> method delegates to this map's <tt>size</tt>
365     * method and the <tt>contains</tt> method delegates to this map's
366     * <tt>containsValue</tt> method.
367     *
368     * <p>The collection is created the first time this method is called, and
369     * returned in response to all subsequent calls.  No synchronization is
370     * performed, so there is a slight chance that multiple calls to this
371     * method will not all return the same collection.
372     */
373    public Collection<V> values() {
374        if (values == null) {
375            values = new AbstractCollection<V>() {
376                public Iterator<V> iterator() {
377                    return new Iterator<V>() {
378                        private Iterator<Entry<K,V>> i = entrySet().iterator();
379
380                        public boolean hasNext() {
381                            return i.hasNext();
382                        }
383
384                        public V next() {
385                            return i.next().getValue();
386                        }
387
388                        public void remove() {
389                            i.remove();
390                        }
391                    };
392                }
393
394                public int size() {
395                    return AbstractMapPro.this.size();
396                }
397
398                public boolean isEmpty() {
399                    return AbstractMapPro.this.isEmpty();
400                }
401
402                public void clear() {
403                    AbstractMapPro.this.clear();
404                }
405
406                public boolean contains(Object v) {
407                    return AbstractMapPro.this.containsValue(v);
408                }
409            };
410        }
411        return values;
412    }
413
414    public abstract Set<Entry<K,V>> entrySet();
415
416    /**
417     * Compares the specified object with this map for equality.  Returns
418     * <tt>true</tt> if the given object is also a map and the two maps
419     * represent the same mappings.  More formally, two maps <tt>m1</tt> and
420     * <tt>m2</tt> represent the same mappings if
421     * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the
422     * <tt>equals</tt> method works properly across different implementations
423     * of the <tt>Map</tt> interface.
424     *
425     * <p>This implementation first checks if the specified object is this map;
426     * if so it returns <tt>true</tt>.  Then, it checks if the specified
427     * object is a map whose size is identical to the size of this map; if
428     * not, it returns <tt>false</tt>.  If so, it iterates over this map's
429     * <tt>entrySet</tt> collection, and checks that the specified map
430     * contains each mapping that this map contains.  If the specified map
431     * fails to contain such a mapping, <tt>false</tt> is returned.  If the
432     * iteration completes, <tt>true</tt> is returned.
433     *
434     * @param o object to be compared for equality with this map
435     * @return <tt>true</tt> if the specified object is equal to this map
436     */
437    public boolean equals(Object o) {
438        if (o == this)
439            return true;
440
441        if (!(o instanceof Map))
442            return false;
443        Map<K,V> m = (Map<K,V>) o;
444        if (m.size() != size())
445            return false;
446
447        try {
448            Iterator<Entry<K,V>> i = entrySet().iterator();
449            while (i.hasNext()) {
450                Entry<K,V> e = i.next();
451                K key = e.getKey();
452                V value = e.getValue();
453                if (value == null) {
454                    if (!(m.get(key)==null && m.containsKey(key)))
455                        return false;
456                } else {
457                    if (!value.equals(m.get(key)))
458                        return false;
459                }
460            }
461        } catch (ClassCastException unused) {
462            return false;
463        } catch (NullPointerException unused) {
464            return false;
465        }
466
467        return true;
468    }
469
470    // TODO add again current implementation creates a infinti loop when child=this
471    /*public int hashCode() {
472        int h = 0;
473        Iterator<Entry<K,V>> i = entrySet().iterator();
474        while (i.hasNext())
475            h += i.next().hashCode();
476        return h;
477    }*/
478
479    /**
480     * Returns a string representation of this map.  The string representation
481     * consists of a list of key-value mappings in the order returned by the
482     * map's <tt>entrySet</tt> view's iterator, enclosed in braces
483     * (<tt>"{}"</tt>).  Adjacent mappings are separated by the characters
484     * <tt>", "</tt> (comma and space).  Each key-value mapping is rendered as
485     * the key followed by an equals sign (<tt>"="</tt>) followed by the
486     * associated value.  Keys and values are converted to strings as by
487     * {@link String#valueOf(Object)}.
488     *
489     * @return a string representation of this map
490     */
491    public String toString() {
492        Iterator<Entry<K,V>> i = entrySet().iterator();
493        if (! i.hasNext())
494            return "{}";
495
496        StringBuilder sb = new StringBuilder();
497        sb.append('{');
498        for (;;) {
499            Entry<K,V> e = i.next();
500            K key = e.getKey();
501            V value = e.getValue();
502            sb.append(key   == this ? "(this Map)" : key);
503            sb.append('=');
504            sb.append(value == this ? "(this Map)" : value);
505            if (! i.hasNext())
506                return sb.append('}').toString();
507            sb.append(',').append(' ');
508        }
509    }
510
511    /**
512     * Returns a shallow copy of this <tt>AbstractMap</tt> instance: the keys
513     * and values themselves are not cloned.
514     *
515     * @return a shallow copy of this map
516     */
517    protected Object clone() throws CloneNotSupportedException {
518        AbstractMapPro<K,V> result = (AbstractMapPro<K,V>)super.clone();
519        result.keySet = null;
520        result.values = null;
521        return result;
522    }
523
524    /**
525     * Utility method for SimpleEntry and SimpleImmutableEntry.
526     * Test for equality, checking for nulls.
527     */
528    private static boolean eq(Object o1, Object o2) {
529        return o1 == null ? o2 == null : o1.equals(o2);
530    }
531
532    // Implementation Note: SimpleEntry and SimpleImmutableEntry
533    // are distinct unrelated classes, even though they share
534    // some code. Since you can't add or subtract final-ness
535    // of a field in a subclass, they can't share representations,
536    // and the amount of duplicated code is too small to warrant
537    // exposing a common abstract class.
538
539
540    /**
541     * An Entry maintaining a key and a value.  The value may be
542     * changed using the <tt>setValue</tt> method.  This class
543     * facilitates the process of building custom map
544     * implementations. For example, it may be convenient to return
545     * arrays of <tt>SimpleEntry</tt> instances in method
546     * <tt>Map.entrySet().toArray</tt>.
547     *
548     * @since 1.6
549     */
550    public static class SimpleEntry<K,V>
551        implements Entry<K,V>, java.io.Serializable
552    {
553        private static final long serialVersionUID = -8499721149061103585L;
554
555        private final K key;
556        private V value;
557
558        /**
559         * Creates an entry representing a mapping from the specified
560         * key to the specified value.
561         *
562         * @param key the key represented by this entry
563         * @param value the value represented by this entry
564         */
565        public SimpleEntry(K key, V value) {
566            this.key   = key;
567            this.value = value;
568        }
569
570        /**
571         * Creates an entry representing the same mapping as the
572         * specified entry.
573         *
574         * @param entry the entry to copy
575         */
576        public SimpleEntry(Entry<? extends K, ? extends V> entry) {
577            this.key   = entry.getKey();
578            this.value = entry.getValue();
579        }
580
581        /**
582         * Returns the key corresponding to this entry.
583         *
584         * @return the key corresponding to this entry
585         */
586        public K getKey() {
587            return key;
588        }
589
590        /**
591         * Returns the value corresponding to this entry.
592         *
593         * @return the value corresponding to this entry
594         */
595        public V getValue() {
596            return value;
597        }
598
599        /**
600         * Replaces the value corresponding to this entry with the specified
601         * value.
602         *
603         * @param value new value to be stored in this entry
604         * @return the old value corresponding to the entry
605         */
606        public V setValue(V value) {
607            V oldValue = this.value;
608            this.value = value;
609            return oldValue;
610        }
611
612        @Override
613        public boolean equals(Object o) {
614            if (!(o instanceof Map.Entry))
615                return false;
616            Map.Entry e = (Map.Entry)o;
617            return eq(key, e.getKey()) && eq(value, e.getValue());
618        }
619
620        @Override
621        public int hashCode() {
622            return (key   == null ? 0 :   key.hashCode()) ^
623                   (value == null ? 0 : value.hashCode());
624        }
625
626        /**
627         * Returns a String representation of this map entry.  This
628         * implementation returns the string representation of this
629         * entry's key followed by the equals character ("<tt>=</tt>")
630         * followed by the string representation of this entry's value.
631         *
632         * @return a String representation of this map entry
633         */
634        public String toString() {
635            return key + "=" + value;
636        }
637
638    }
639
640    /**
641     * An Entry maintaining an immutable key and value.  This class
642     * does not support method <tt>setValue</tt>.  This class may be
643     * convenient in methods that return thread-safe snapshots of
644     * key-value mappings.
645     *
646     * @since 1.6
647     */
648    public static class SimpleImmutableEntry<K,V>
649        implements Entry<K,V>, java.io.Serializable
650    {
651        private static final long serialVersionUID = 7138329143949025153L;
652
653        private final K key;
654        private final V value;
655
656        /**
657         * Creates an entry representing a mapping from the specified
658         * key to the specified value.
659         *
660         * @param key the key represented by this entry
661         * @param value the value represented by this entry
662         */
663        public SimpleImmutableEntry(K key, V value) {
664            this.key   = key;
665            this.value = value;
666        }
667
668        /**
669         * Creates an entry representing the same mapping as the
670         * specified entry.
671         *
672         * @param entry the entry to copy
673         */
674        public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
675            this.key   = entry.getKey();
676            this.value = entry.getValue();
677        }
678
679        /**
680         * Returns the key corresponding to this entry.
681         *
682         * @return the key corresponding to this entry
683         */
684        public K getKey() {
685            return key;
686        }
687
688        /**
689         * Returns the value corresponding to this entry.
690         *
691         * @return the value corresponding to this entry
692         */
693        public V getValue() {
694            return value;
695        }
696
697        /**
698         * Replaces the value corresponding to this entry with the specified
699         * value (optional operation).  This implementation simply throws
700         * <tt>UnsupportedOperationException</tt>, as this class implements
701         * an <i>immutable</i> map entry.
702         *
703         * @param value new value to be stored in this entry
704         * @return (Does not return)
705         * @throws UnsupportedOperationException always
706         */
707        public V setValue(V value) {
708            throw new UnsupportedOperationException();
709        }
710
711        @Override
712        public boolean equals(Object o) {
713            if (!(o instanceof Map.Entry))
714                return false;
715            Map.Entry e = (Map.Entry)o;
716            return eq(key, e.getKey()) && eq(value, e.getValue());
717        }
718
719        @Override
720        public int hashCode() {
721            return (key   == null ? 0 :   key.hashCode()) ^
722                   (value == null ? 0 : value.hashCode());
723        }
724
725        /**
726         * Returns a String representation of this map entry.  This
727         * implementation returns the string representation of this
728         * entry's key followed by the equals character ("<tt>=</tt>")
729         * followed by the string representation of this entry's value.
730         *
731         * @return a String representation of this map entry
732         */
733        public String toString() {
734            return key + "=" + value;
735        }
736
737    }
738    
739    public static PageException invalidKey(Map<?,?> map,Object key, boolean remove) {
740
741                StringBuilder sb=new StringBuilder();
742                Iterator<?> it = map.keySet().iterator();
743                Object k;
744                while(it.hasNext()){
745                        k = it.next();
746                        if(sb.length()>0)sb.append(',');
747                        sb.append(k.toString());
748                }
749                return new ExpressionException(
750                                (remove?
751                                                "cannot remove key ["+key+"] from struct, key doesn't exist":
752                                                "key [" + key + "] doesn't exist") +
753                                " (existing keys:" + sb.toString() + ")" );
754        }
755
756}