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.List; 26 27 /** 28 * A size-limited heap similar to {@link TopBoundedHeap}, discarding elements 29 * with the highest value. However, this variation keeps a list of tied 30 * elements. 31 * 32 * @author Erich Schubert 33 * @since 0.4.0 34 * 35 * @has - - - UnorderedIter 36 * 37 * @param <E> Object type 38 */ 39 public class TiedTopBoundedHeap<E> extends TopBoundedHeap<E> { 40 /** 41 * List to keep ties in. 42 */ 43 private List<E> ties = new ArrayList<>(); 44 45 /** 46 * Constructor with comparator. 47 * 48 * @param maxsize Maximum size of heap (unless tied) 49 * @param comparator Comparator 50 */ TiedTopBoundedHeap(int maxsize, Comparator<? super E> comparator)51 public TiedTopBoundedHeap(int maxsize, Comparator<? super E> comparator) { 52 super(maxsize, comparator); 53 } 54 55 /** 56 * Constructor for Comparable objects. 57 * 58 * @param maxsize Maximum size of heap (unless tied) 59 */ TiedTopBoundedHeap(int maxsize)60 public TiedTopBoundedHeap(int maxsize) { 61 this(maxsize, null); 62 } 63 64 @Override size()65 public int size() { 66 return super.size() + ties.size(); 67 } 68 69 @Override clear()70 public void clear() { 71 super.clear(); 72 ties.clear(); 73 } 74 75 @Override peek()76 public E peek() { 77 if (ties.isEmpty()) { 78 return super.peek(); 79 } else { 80 return ties.get(ties.size() - 1); 81 } 82 } 83 84 @Override poll()85 public E poll() { 86 if (ties.isEmpty()) { 87 return super.poll(); 88 } else { 89 return ties.remove(ties.size() - 1); 90 } 91 } 92 93 @Override replaceTopElement(E e)94 public E replaceTopElement(E e) { 95 if (ties.isEmpty()) { 96 return super.replaceTopElement(e); 97 } 98 // Fall back to classic emulation via poll and offer: 99 E prev = poll(); 100 add(e); 101 return prev; 102 } 103 104 @Override handleOverflow(E e)105 protected void handleOverflow(E e) { 106 boolean tied = false; 107 if (comparator == null) { 108 @SuppressWarnings("unchecked") 109 Comparable<Object> c = (Comparable<Object>) e; 110 if (c.compareTo(queue[0]) == 0) { 111 tied = true; 112 } 113 } else { 114 if (comparator.compare(e, queue[0]) == 0) { 115 tied = true; 116 } 117 } 118 if (tied) { 119 ties.add(e); 120 } else { 121 // Also remove old ties. 122 ties.clear(); 123 } 124 } 125 126 /** 127 * Get an unordered heap iterator. 128 * 129 * @return Iterator. 130 */ 131 @Override unorderedIter()132 public UnorderedIter unorderedIter() { 133 return new UnorderedIter(); 134 } 135 136 /** 137 * Unordered heap iterator class. 138 * 139 * @author Erich Schubert 140 * 141 */ 142 public class UnorderedIter extends Heap<E>.UnorderedIter { 143 /** 144 * Constructor. 145 */ UnorderedIter()146 protected UnorderedIter() { 147 super(); 148 } 149 150 @Override valid()151 public boolean valid() { 152 return pos < size(); 153 } 154 155 @Override get()156 public E get() { 157 final int ssize = TiedTopBoundedHeap.super.size(); 158 if (pos < ssize) { 159 return super.get(); 160 } else { 161 return ties.get(pos - ssize); 162 } 163 } 164 } 165 } 166