001/*
002// This software is subject to the terms of the Eclipse Public License v1.0
003// Agreement, available at the following URL:
004// http://www.eclipse.org/legal/epl-v10.html.
005// You must accept the terms of that agreement to use this software.
006//
007// Copyright (C) 2011-2012 Pentaho
008// All Rights Reserved.
009*/
010package mondrian.util;
011
012import mondrian.olap.Util;
013
014import java.util.*;
015
016/**
017 * Partially-ordered set.
018 *
019 * <p>When you create a partially-ordered set ('poset' for short) you must
020 * provide an {@link Ordering} that determines the order relation. The
021 * ordering must be:</p>
022 *
023 * <ul>
024 *     <li>reflexive: e.lte(e) returns true;</li>
025 *     <li>anti-symmetric: if e.lte(f) returns true,
026 *     then f.lte(e) returns false only if e = f;</li>
027 *     <li>transitive: if e.lte(f) returns true and
028 *     f.lte(g) returns true, then e.lte(g) must return true.</li>
029 * </ul>
030 *
031 * <p>Note that not all pairs of elements are related. If is OK if e.lte(f)
032 * returns false and f.lte(e) returns false also.</p>
033 *
034 * <p>In addition to the usual set methods, there are methods to determine the
035 * immediate parents and children of an element in the set, and method to find
036 * all elements which have no parents or no children (i.e. "root" and "leaf"
037 * elements).</p>
038 *
039 * <p>A lattice is a special kind of poset where there is a unique top and
040 * bottom element. You can use a PartiallyOrderedSet for a lattice also. It may
041 * be helpful to add the top and bottom elements to the poset on
042 * construction.</p>
043 *
044 * @param <E> Element type
045 *
046 * @author Julian Hyde
047 */
048public class PartiallyOrderedSet<E> extends AbstractSet<E>
049{
050    private final Map<E, Node<E>> map;
051    private final Ordering<E> ordering;
052
053    /**
054     * Synthetic node to hold all nodes that have no parents. It does not appear
055     * in the set.
056     */
057    private final Node<E> topNode;
058    private final Node<E> bottomNode;
059
060    private static final boolean DEBUG = false;
061
062    /**
063     * Creates a partially-ordered set.
064     *
065     * @param ordering Ordering relation
066     */
067    public PartiallyOrderedSet(Ordering<E> ordering) {
068        this(ordering, new HashMap<E, Node<E>>());
069    }
070
071    /**
072     * Creates a partially-ordered set, and populates it with a given
073     * collection.
074     *
075     * @param ordering Ordering relation
076     * @param collection Initial contents of partially-ordered set
077     */
078    public PartiallyOrderedSet(Ordering<E> ordering, Collection<E> collection) {
079        this(ordering, new HashMap<E, Node<E>>(collection.size() * 3 / 2));
080        addAll(collection);
081    }
082
083    /**
084     * Internal constructor.
085     *
086     * @param ordering Ordering relation
087     * @param map Map from values to nodes
088     */
089    private PartiallyOrderedSet(Ordering<E> ordering, Map<E, Node<E>> map) {
090        this.ordering = ordering;
091        this.map = map;
092        this.topNode = new TopBottomNode<E>(true);
093        this.bottomNode = new TopBottomNode<E>(false);
094        this.topNode.childList.add(bottomNode);
095        this.bottomNode.parentList.add(topNode);
096    }
097
098    @Override
099    public Iterator<E> iterator() {
100        final Iterator<E> iterator = map.keySet().iterator();
101        return new Iterator<E>() {
102            E previous;
103
104            public boolean hasNext() {
105                return iterator.hasNext();
106            }
107
108            public E next() {
109                return previous = iterator.next();
110            }
111
112            public void remove() {
113                if (!PartiallyOrderedSet.this.remove(previous)) {
114                    // Object was not present.
115                    // Maybe they have never called 'next'?
116                    // Maybe they called 'remove' twice?
117                    // Either way, something is screwy.
118                    throw new IllegalStateException();
119                }
120            }
121        };
122    }
123
124    @Override
125    public int size() {
126        return map.size();
127    }
128
129    @Override
130    public boolean contains(Object o) {
131        //noinspection SuspiciousMethodCalls
132        return map.containsKey(o);
133    }
134
135    @Override
136    public boolean remove(Object o) {
137        @SuppressWarnings("SuspiciousMethodCalls")
138        final Node<E> node = map.remove(o);
139        if (node == null) {
140            return false;
141        }
142        for (int i = 0; i < node.parentList.size(); i++) {
143            Node<E> parent = node.parentList.get(i);
144            for (Node<E> child : node.childList) {
145                if (parent.e == null && child.e == null) {
146                    parent.childList.remove(node);
147                    continue;
148                }
149                replace(parent.childList, node, child);
150            }
151        }
152        for (int i = 0; i < node.childList.size(); i++) {
153            Node<E> child = node.childList.get(i);
154            for (Node<E> parent : node.parentList) {
155                if (child.e == null && parent.e == null) {
156                    child.parentList.remove(node);
157                    continue;
158                }
159                replace(child.parentList, node, parent);
160            }
161        }
162        return true;
163    }
164
165    /**
166     * Adds an element to this lattice.
167     */
168    @Override
169    public boolean add(E e) {
170        assert e != null;
171        assert !DEBUG || isValid(true);
172        Node<E> node = map.get(e);
173        if (node != null) {
174            // already present
175            return false;
176        }
177        Set<Node<E>> parents = findParents(e);
178        Set<Node<E>> children = findChildren(e);
179
180        node = new Node<E>(e);
181
182        for (Node<E> parent : parents) {
183            node.parentList.add(parent);
184            int n = 0;
185            for (int i = 0; i < parent.childList.size(); i++) {
186                Node<E> child = parent.childList.get(i);
187                if (child.e == null || ordering.lessThan(child.e, e)) {
188                    if (parent.childList.contains(node)) {
189                        parent.childList.remove(i);
190                        --i;
191                    } else {
192                        parent.childList.set(i, node);
193                    }
194                    replace(child.parentList, parent, node);
195                    if (!node.childList.contains(child)) {
196                        node.childList.add(child);
197                    }
198                    ++n;
199                }
200            }
201            if (n == 0) {
202                parent.childList.add(node);
203            }
204        }
205
206        // Nodes reachable from parents.
207        final Set<Node<E>> childSet = new HashSet<Node<E>>(node.childList);
208        for (Node<E> child : children) {
209            if (!isDescendantOfAny(child, childSet)) {
210                node.childList.add(child);
211                if (!child.parentList.contains(node)) {
212                    child.parentList.add(node);
213                }
214            }
215        }
216
217        map.put(node.e, node);
218        assert !DEBUG || isValid(true);
219        return true;
220    }
221
222    /**
223     * Returns whether node's value is a descendant of any of the values in
224     * nodeSet.
225     *
226     * @param node Node
227     * @param nodeSet Suspected ancestors
228     * @return Whether node is a descendant of any of the nodes
229     */
230    private boolean isDescendantOfAny(
231        Node<E> node,
232        Set<Node<E>> nodeSet)
233    {
234        final ArrayDeque<Node<E>> deque = new ArrayDeque<Node<E>>();
235        final Set<Node<E>> seen = new HashSet<Node<E>>();
236        deque.add(node);
237        while (!deque.isEmpty()) {
238            final Node<E> node1 = deque.pop();
239            if (nodeSet.contains(node1)) {
240                return true;
241            }
242            for (Node<E> parent : node1.parentList) {
243                if (seen.add(parent)) {
244                    deque.add(parent);
245                }
246            }
247        }
248        return false;
249    }
250
251    private Set<Node<E>> findChildren(E e) {
252        ArrayDeque<Node<E>> descendants = new ArrayDeque<Node<E>>();
253        descendants.add(bottomNode);
254        return findParentsChildren(e, descendants, false);
255    }
256
257    private Set<Node<E>> findParents(E e) {
258        ArrayDeque<Node<E>> ancestors = new ArrayDeque<Node<E>>();
259        ancestors.add(topNode);
260        return findParentsChildren(e, ancestors, true);
261    }
262
263    private Set<Node<E>> findParentsChildren(
264        E e,
265        ArrayDeque<Node<E>> ancestors,
266        boolean up)
267    {
268        final Set<Node<E>> parents = new HashSet<Node<E>>();
269        while (!ancestors.isEmpty()) {
270            final Node<E> ancestor = ancestors.pop();
271            assert ancestor.e == null
272                || (up
273                    ? !ordering.lessThan(ancestor.e, e)
274                    : !ordering.lessThan(e, ancestor.e));
275            assert ancestor.e != e; // e not in tree yet
276            // Example: e = "a", ancestor = "abc".
277            // If there is at least one child c of ancestor such that e <= c
278            // (e.g. "ab", "ac") examine those children. If there are no
279            // such children, ancestor becomes a parent
280            int found = 0;
281            for (Node<E> child
282                : (up ? ancestor.childList : ancestor.parentList))
283            {
284                if (child.e == null) {
285                    continue; // child is the bottom node
286                }
287                if (up
288                    ? ordering.lessThan(e, child.e)
289                    : ordering.lessThan(child.e, e))
290                {
291                    ancestors.add(child);
292                    ++found;
293                } else if (up
294                    ? !ordering.lessThan(child.e, e)
295                    : !ordering.lessThan(e, child.e))
296                {
297                    // e is not less than child (and therefore some descendant
298                    // of child might be less than e). Recurse into its
299                    // children.
300                    ancestors.add(child);
301                }
302            }
303            if (found == 0) {
304                // None of the descendants of the node are greater than e.
305                // Therefore node is a parent, provided that e is definitely
306                // less than node
307                if (ancestor.e == null
308                    || (up
309                        ? ordering.lessThan(e, ancestor.e)
310                        : ordering.lessThan(ancestor.e, e)))
311                {
312                    parents.add(ancestor);
313                }
314            }
315        }
316        return parents;
317    }
318
319    private <T> void replace(List<T> list, T remove, T add) {
320        if (list.contains(add)) {
321            list.remove(remove);
322        } else {
323            final int index = list.indexOf(remove);
324            if (index >= 0) {
325                list.set(index, add);
326            } else {
327                list.add(add);
328            }
329        }
330    }
331
332    /**
333     * Checks internal consistency of this lattice.
334     *
335     * @param fail Whether to throw an assertion error
336     * @return Whether valid
337     */
338    @SuppressWarnings({"ConstantConditions"})
339    public boolean isValid(boolean fail) {
340        // Top has no parents.
341        // Bottom has no children.
342        // Each node except top has at least one parent.
343        // Each node except bottom has at least one child.
344        // Every node's children list it as a parent.
345        // Every node's parents list it as a child.
346        for (Node<E> node : map.values()) {
347            if ((node == topNode)
348                != (node.parentList.isEmpty()))
349            {
350                assert !fail
351                    : "only top node should have no parents " + node
352                      + ", parents " + node.parentList;
353                return false;
354            }
355            if ((node == bottomNode)
356                != (node.childList.isEmpty()))
357            {
358                assert !fail
359                    : "only bottom node should have no children " + node
360                      + ", children " + node.childList;
361                return false;
362            }
363            for (int i = 0; i < node.childList.size(); i++) {
364                Node<E> child = node.childList.get(i);
365                if (!child.parentList.contains(node)) {
366                    assert !fail
367                        : "child " + child + " of " + node
368                        + " does not know its parent";
369                    return false;
370                }
371                if (child.e != null && !ordering.lessThan(child.e, node.e)) {
372                    assert !fail
373                        : "child " + child.e + " not less than parent "
374                        + node.e;
375                    return false;
376                }
377                for (int i2 = 0; i2 < node.childList.size(); i2++) {
378                    Node<E> child2 = node.childList.get(i2);
379                    if (child == child2
380                        && i != i2)
381                    {
382                        assert !fail
383                            : "duplicate child " + child + " of parent " + node;
384                        return false;
385                    }
386                    if (child.e != null
387                        && child2.e != null
388                        && child != child2
389                        && ordering.lessThan(child.e, child2.e))
390                    {
391                        assert !fail
392                            : "relation between children " + child.e
393                              + " and " + child2.e + " of node " + node.e;
394                        return false;
395                    }
396                }
397            }
398            for (Node<E> parent : node.parentList) {
399                if (!parent.childList.contains(node)) {
400                    assert !fail;
401                    return false;
402                }
403            }
404        }
405        final Map<Node, Integer> distanceToRoot =
406            new HashMap<Node, Integer>();
407        distanceRecurse(distanceToRoot, topNode, 0);
408        for (Node<E> node : map.values()) {
409            if (!distanceToRoot.containsKey(node)) {
410                assert !fail : "node " + node + " is not reachable";
411                return false;
412            }
413        }
414
415        // For each pair of elements, ensure that elements are related if and
416        // only if they are in the ancestors or descendants lists.
417        Map<Node<E>, Set<E>> nodeAncestors = new HashMap<Node<E>, Set<E>>();
418        Map<Node<E>, Set<E>> nodeDescendants = new HashMap<Node<E>, Set<E>>();
419        for (Node<E> node : map.values()) {
420            nodeAncestors.put(
421                node,
422                new HashSet<E>(getAncestors(node.e)));
423            nodeDescendants.put(
424                node,
425                new HashSet<E>(getDescendants(node.e)));
426        }
427        for (Node<E> node1 : map.values()) {
428            for (Node<E> node2 : map.values()) {
429                final boolean lt12 = ordering.lessThan(node1.e, node2.e);
430                final boolean lt21 = ordering.lessThan(node2.e, node1.e);
431                if (node1 == node2) {
432                    if (!(lt12 && lt21)) {
433                        assert !fail
434                            : "self should be less than self: " + node1;
435                    }
436                }
437                if (lt12 && lt21) {
438                    if (!(node1 == node2)) {
439                        assert !fail
440                            : "node " + node1.e + " and node " + node2.e
441                              + " are less than each other but are not the same"
442                              + " value";
443                        return false;
444                    }
445                }
446                if (lt12 && !lt21) {
447                    if (!nodeAncestors.get(node1).contains(node2.e)) {
448                        assert !fail
449                            : node1.e + " is less than " + node2.e + " but "
450                              + node2.e + " is not in the ancestor set of "
451                              + node1.e;
452                        return false;
453                    }
454                    if (!nodeDescendants.get(node2).contains(node1.e)) {
455                        assert !fail
456                            : node1.e + " is less than " + node2.e + " but "
457                              + node1.e + " is not in the descendant set of "
458                              + node2.e;
459                        return false;
460                    }
461                }
462                if (lt21 && !lt12) {
463                    if (!nodeAncestors.get(node2).contains(node1.e)) {
464                        assert !fail
465                            : node2.e + " is less than " + node1.e + " but "
466                              + node1.e + " is not in the ancestor set of "
467                              + node2.e;
468                        return false;
469                    }
470                    if (!nodeDescendants.get(node1).contains(node2.e)) {
471                        assert !fail
472                            : node2.e + " is less than " + node1.e + " but "
473                              + node2.e + " is not in the descendant set of "
474                              + node1.e;
475                        return false;
476                    }
477                }
478            }
479        }
480        return true;
481    }
482
483    private void distanceRecurse(
484        Map<Node, Integer> distanceToRoot,
485        Node<E> node,
486        int distance)
487    {
488        final Integer best = distanceToRoot.get(node);
489        if (best == null || distance < best) {
490            distanceToRoot.put(node, distance);
491        }
492        if (best != null) {
493            return;
494        }
495        for (Node<E> child : node.childList) {
496            distanceRecurse(
497                distanceToRoot,
498                child,
499                distance + 1);
500        }
501    }
502
503    public void out(StringBuilder buf) {
504        buf.append("PartiallyOrderedSet size: ");
505        buf.append(size());
506        buf.append(" elements: {");
507        buf.append(Util.nl);
508
509        // breadth-first search, to iterate over every element once, printing
510        // those nearest the top element first
511        final HashSet<E> seen = new HashSet<E>();
512        final ArrayDeque<E> unseen = new ArrayDeque<E>();
513        unseen.addAll(getNonChildren());
514        while (!unseen.isEmpty()) {
515            E e = unseen.pop();
516            buf.append("  ");
517            buf.append(e);
518            buf.append(" parents: ");
519            final List<E> parents = getParents(e);
520            buf.append(parents);
521            buf.append(" children: ");
522            final List<E> children = getChildren(e);
523            buf.append(children);
524            buf.append(Util.nl);
525
526            for (E child : children) {
527                if (seen.add(child)) {
528                    unseen.add(child);
529                }
530            }
531        }
532        buf.append("}");
533    }
534
535    /**
536     * Returns the values in this partially-ordered set that are less-than
537     * a given value and there are no intervening values.
538     *
539     * <p>If the value is not in this set, returns the empty list.</p>
540     *
541     * @see #getDescendants
542     *
543     * @param e Value
544     * @return List of values in this set that are directly less than the given
545     *   value
546     */
547    public List<E> getChildren(E e) {
548        final Node<E> node = map.get(e);
549        if (node == null) {
550            return null;
551        } else if (node.childList.get(0).e == null) {
552            // child list contains bottom element, so officially there are no
553            // children
554            return Collections.emptyList();
555        } else {
556            return new StripList<E>(node.childList);
557        }
558    }
559
560    /**
561     * Returns the values in this partially-ordered set that are greater-than
562     * a given value and there are no intervening values.
563     *
564     * <p>If the value is not in this set, returns the empty list.</p>
565     *
566     * @see #getAncestors
567     *
568     * @param e Value
569     * @return List of values in this set that are directly greater than the
570     *   given value
571     */
572    public List<E> getParents(E e) {
573        final Node<E> node = map.get(e);
574        if (node == null) {
575            return null;
576        } else if (node.parentList.get(0).e == null) {
577            // parent list contains top element, so officially there are no
578            // parents
579            return Collections.emptyList();
580        } else {
581            return new StripList<E>(node.parentList);
582        }
583    }
584
585    public List<E> getNonChildren() {
586        if (topNode.childList.size() == 1
587            && topNode.childList.get(0).e == null)
588        {
589            return Collections.emptyList();
590        }
591        return new StripList<E>(topNode.childList);
592    }
593
594    public List<E> getNonParents() {
595        if (bottomNode.parentList.size() == 1
596            && bottomNode.parentList.get(0).e == null)
597        {
598            return Collections.emptyList();
599        }
600        return new StripList<E>(bottomNode.parentList);
601    }
602
603    @Override
604    public void clear() {
605        map.clear();
606        assert topNode.parentList.isEmpty();
607        topNode.childList.clear();
608        topNode.childList.add(bottomNode);
609        assert bottomNode.childList.isEmpty();
610        bottomNode.parentList.clear();
611        bottomNode.parentList.add(topNode);
612    }
613
614    /**
615     * Returns a list of values in the set that are less-than a given value.
616     * The list is in topological order but order is otherwise
617     * non-deterministic.
618     *
619     * @param e Value
620     * @return Values less than given value
621     */
622    public List<E> getDescendants(E e) {
623        return descendants(e, true);
624    }
625
626    /**
627     * Returns a list of values in the set that are less-than a given value.
628     * The list is in topological order but order is otherwise
629     * non-deterministic.
630     *
631     * @param e Value
632     * @return Values less than given value
633     */
634    public List<E> getAncestors(E e) {
635        return descendants(e, false);
636    }
637
638    private List<E> descendants(E e, boolean up) {
639        Node<E> node = map.get(e);
640        final Collection<Node<E>> c;
641        if (node == null) {
642            c = up ? findChildren(e) : findParents(e);
643        } else {
644            c = up ? node.childList : node.parentList;
645        }
646        if (c.size() == 1 && c.iterator().next().e == null) {
647            return Collections.emptyList();
648        }
649        ArrayDeque<Node<E>> deque = new ArrayDeque<Node<E>>(c);
650
651        final Set<Node<E>> seen = new HashSet<Node<E>>();
652        final List<E> list = new ArrayList<E>();
653        while (!deque.isEmpty()) {
654            Node<E> node1 = deque.pop();
655            list.add(node1.e);
656            for (Node<E> child : up ? node1.childList : node1.parentList) {
657                if (child.e == null) {
658                    // Node is top or bottom.
659                    break;
660                }
661                if (seen.add(child)) {
662                    deque.add(child);
663                }
664            }
665        }
666        return list;
667    }
668
669    /**
670     * Holds a value, its parent nodes, and child nodes.
671     *
672     * <p>We deliberately do not override {@link #hashCode} or
673     * {@link #equals(Object)}. A canonizing map ensures that within a
674     * given PartiallyOrderedSet, two nodes are identical if and only if they
675     * contain the same value.</p>
676     *
677     * @param <E> Element type
678     */
679    private static class Node<E> {
680        final List<Node<E>> parentList = new ArrayList<Node<E>>();
681        final List<Node<E>> childList = new ArrayList<Node<E>>();
682        final E e;
683
684        public Node(E e) {
685            this.e = e;
686        }
687
688        @Override
689        public String toString() {
690            return e.toString();
691        }
692    }
693
694    /**
695     * Subclass of Node for top/bottom nodes. Improves readability when
696     * debugging.
697     *
698     * @param <E> Element type
699     */
700    private static class TopBottomNode<E> extends Node<E> {
701        private final String description;
702
703        public TopBottomNode(boolean top) {
704            super(null);
705            this.description = top ? "top" : "bottom";
706        }
707
708        @Override
709        public String toString() {
710            return description;
711        }
712    }
713
714    /**
715     * Ordering relation.
716     *
717     * <p>To obey the constraints of the partially-ordered set, the function
718     * must be consistent with the reflexive, anti-symmetric, and transitive
719     * properties required by a partially ordered set.</p>
720     *
721     * <p>For instance, if {@code ordering(foo, foo)} returned false for any
722     * not-null value of foo, it would violate the reflexive property.</p>
723     *
724     * <p>If an ordering violates any of these required properties, the behavior
725     * of a {@link PartiallyOrderedSet} is unspecified. (But mayhem is
726     * likely.)</p>
727     *
728     * @param <E> Element type
729     */
730    public interface Ordering<E> {
731        /**
732         * Returns whether element e1 is &le; e2 according to
733         * the relation that defines a partially-ordered set.
734         *
735         * @param e1 Element 1
736         * @param e2 Element 2
737         * @return Whether element 1 is &le; element 2
738         */
739        boolean lessThan(E e1, E e2);
740    }
741
742    private static class StripList<E> extends AbstractList<E> {
743        private final List<Node<E>> list;
744
745        public StripList(List<Node<E>> list) {
746            this.list = list;
747        }
748
749        @Override
750        public E get(int index) {
751            return list.get(index).e;
752        }
753
754        @Override
755        public int size() {
756            return list.size();
757        }
758    }
759
760    /**
761     * Cut-down version of java.util.ArrayDeque, which is not available until
762     * JDK 1.6.
763     *
764     * @param <E> Element type
765     */
766    private static class ArrayDeque<E> {
767        private E[] es; // length must be multiple of 2
768        private int first;
769        private int last;
770
771        public ArrayDeque() {
772            this(16);
773        }
774
775        public ArrayDeque(Collection<E> nodes) {
776            this(nextPowerOf2(nodes.size()));
777            addAll(nodes);
778        }
779
780        private ArrayDeque(int capacity) {
781            first = last = 0;
782            //noinspection unchecked
783            es = (E[]) new Object[capacity];
784        }
785
786        private static int nextPowerOf2(int v) {
787            // Algorithm from
788            // http://graphics.stanford.edu/~seander/bithacks.html
789            v--;
790            v |= v >> 1;
791            v |= v >> 2;
792            v |= v >> 4;
793            v |= v >> 8;
794            v |= v >> 16;
795            v++;
796            return v;
797        }
798
799        @SuppressWarnings({"SuspiciousSystemArraycopy", "unchecked"})
800        private void expand() {
801            Object[] olds = es;
802            es = (E[]) new Object[es.length * 2];
803            System.arraycopy(olds, 0, es, 0, olds.length);
804            if (last <= first) {
805                final int x = last & (olds.length - 1);
806                System.arraycopy(olds, 0, es, olds.length, x);
807                last += olds.length;
808            }
809        }
810
811        public void add(E e) {
812            es[last] = e;
813            last = (last + 1) & (es.length - 1);
814            if (last == first) {
815                expand();
816            }
817        }
818
819        public boolean isEmpty() {
820            return last == first;
821        }
822
823
824        public E pop() {
825            if (last == first) {
826                throw new NoSuchElementException();
827            }
828            E e = es[first];
829            first = (first + 1) & (es.length - 1);
830            return e;
831        }
832
833
834        public void addAll(Collection<E> list) {
835            for (E e : list) {
836                add(e);
837            }
838        }
839    }
840}
841
842// End PartiallyOrderedSet.java