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 ≤ 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 ≤ 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