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