1 /* 2 * This file is part of ELKI: 3 * Environment for Developing KDD-Applications Supported by Index-Structures 4 * 5 * Copyright (C) 2018 6 * ELKI Development Team 7 * 8 * This program is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Affero General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Affero General Public License for more details. 17 * 18 * You should have received a copy of the GNU Affero General Public License 19 * along with this program. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 package de.lmu.ifi.dbs.elki.utilities.datastructures.heap; 22 23 import java.util.ArrayList; 24 import java.util.Comparator; 25 import java.util.Iterator; 26 import java.util.List; 27 28 import de.lmu.ifi.dbs.elki.utilities.exceptions.AbortException; 29 30 /** 31 * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements 32 * with the highest value. However, this variation keeps a list of tied 33 * elements. 34 * 35 * @author Erich Schubert 36 * @since 0.4.0 37 * 38 * @param <E> Object type 39 */ 40 public class TiedTopBoundedUpdatableHeap<E> extends TopBoundedUpdatableHeap<E> { 41 /** 42 * List to keep ties in. 43 */ 44 private List<E> ties = new ArrayList<>(); 45 46 /** 47 * Constructor with comparator. 48 * 49 * @param maxsize Maximum size of heap (unless tied) 50 * @param comparator Comparator 51 */ TiedTopBoundedUpdatableHeap(int maxsize, Comparator<? super E> comparator)52 public TiedTopBoundedUpdatableHeap(int maxsize, Comparator<? super E> comparator) { 53 super(maxsize, comparator); 54 } 55 56 /** 57 * Constructor for Comparable objects. 58 * 59 * @param maxsize Maximum size of heap (unless tied) 60 */ TiedTopBoundedUpdatableHeap(int maxsize)61 public TiedTopBoundedUpdatableHeap(int maxsize) { 62 this(maxsize, null); 63 } 64 65 @Override size()66 public int size() { 67 return super.size() + ties.size(); 68 } 69 70 @Override clear()71 public void clear() { 72 super.clear(); 73 ties.clear(); 74 } 75 76 @Override offerAt(int pos, E e)77 public void offerAt(int pos, E e) { 78 if(pos == IN_TIES) { 79 for(Iterator<E> i = ties.iterator(); i.hasNext();) { 80 E e2 = i.next(); 81 if(e.equals(e2)) { 82 if(compare(e, e2) <= 0) { 83 i.remove(); 84 index.removeInt(e2); 85 } 86 return; 87 } 88 } 89 throw new AbortException("Heap corrupt - should not be reached"); 90 } 91 // Updated object will be worse than the current ties 92 if(pos >= 0 && !ties.isEmpty() && compare(e, ties.get(0)) < 0) { 93 removeAt(pos); 94 index.removeInt(e); 95 // assert(checkHeap() == null) : "removeObject broke heap: "+ checkHeap(); 96 // Move one object back from ties 97 final E e2 = ties.remove(ties.size() - 1); 98 // index.remove(e2); 99 super.offerAt(NO_VALUE, e2); 100 return; 101 } 102 super.offerAt(pos, e); 103 } 104 105 @Override peek()106 public E peek() { 107 if(ties.isEmpty()) { 108 return super.peek(); 109 } 110 else { 111 return ties.get(ties.size() - 1); 112 } 113 } 114 115 @Override poll()116 public E poll() { 117 if(ties.isEmpty()) { 118 return super.poll(); 119 } 120 else { 121 E e = ties.remove(ties.size() - 1); 122 index.removeInt(e); 123 return e; 124 } 125 } 126 127 @Override handleOverflow(E e)128 protected void handleOverflow(E e) { 129 boolean tied = false; 130 if(comparator == null) { 131 @SuppressWarnings("unchecked") 132 Comparable<Object> c = (Comparable<Object>) e; 133 if(c.compareTo(queue[0]) == 0) { 134 tied = true; 135 } 136 } 137 else { 138 if(comparator.compare(e, queue[0]) == 0) { 139 tied = true; 140 } 141 } 142 if(tied) { 143 ties.add(e); 144 index.put(e, IN_TIES); 145 } 146 else { 147 index.removeInt(e); 148 // Also remove old ties. 149 for(E e2 : ties) { 150 index.removeInt(e2); 151 } 152 ties.clear(); 153 } 154 } 155 } 156