001: // kelondroMScoreCluster.java
002: // -----------------------
003: // (C) by Michael Peter Christen; mc@anomic.de
004: // first published on http://www.anomic.de
005: // Frankfurt, Germany, 2004
006: // last major change: 28.09.2004
007: //
008: // This program is free software; you can redistribute it and/or modify
009: // it under the terms of the GNU General Public License as published by
010: // the Free Software Foundation; either version 2 of the License, or
011: // (at your option) any later version.
012: //
013: // This program is distributed in the hope that it will be useful,
014: // but WITHOUT ANY WARRANTY; without even the implied warranty of
015: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
016: // GNU General Public License for more details.
017: //
018: // You should have received a copy of the GNU General Public License
019: // along with this program; if not, write to the Free Software
020: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
021: //
022: // Using this software in any meaning (reading, learning, copying, compiling,
023: // running) means that you agree that the Author(s) is (are) not responsible
024: // for cost, loss of data or any harm that may be caused directly or indirectly
025: // by usage of this softare or this documentation. The usage of this software
026: // is on your own risk. The installation and usage (starting/running) of this
027: // software may allow other people or application to access your computer and
028: // any attached devices and is highly dependent on the configuration of the
029: // software which must be done by the user of the software; the author(s) is
030: // (are) also not responsible for proper configuration and usage of the
031: // software, even if provoked by documentation provided together with
032: // the software.
033: //
034: // Any changes to this file according to the GPL as documented in the file
035: // gpl.txt aside this file in the shipment you received can be done to the
036: // lines that follows this copyright notice here, but changes must not be
037: // done inside the copyright notive above. A re-distribution must contain
038: // the intact and unchanged copyright notice.
039: // Contributions and changes to the program code must be marked as such.
040:
041: package de.anomic.kelondro;
042:
043: import java.text.ParseException;
044: import java.text.SimpleDateFormat;
045: import java.util.Iterator;
046: import java.util.Map;
047: import java.util.Random;
048: import java.util.SortedMap;
049: import java.util.TreeMap;
050:
051: public final class kelondroMScoreCluster<E> {
052:
053: protected final TreeMap<E, Long> refkeyDB; // a mapping from a reference to the cluster key
054: protected final TreeMap<Long, E> keyrefDB; // a mapping from the cluster key to the reference
055: private long gcount;
056: private int encnt;
057:
058: public kelondroMScoreCluster() {
059: refkeyDB = new TreeMap<E, Long>();
060: keyrefDB = new TreeMap<Long, E>();
061: gcount = 0;
062: encnt = 0;
063: }
064:
065: public static final String shortDateFormatString = "yyyyMMddHHmmss";
066: public static final SimpleDateFormat shortFormatter = new SimpleDateFormat(
067: shortDateFormatString);
068: public static final long minutemillis = 60000;
069: public static long date2000 = 0;
070:
071: static {
072: try {
073: date2000 = shortFormatter.parse("20000101000000").getTime();
074: } catch (ParseException e) {
075: }
076: }
077:
078: public static int object2score(Object o) {
079: if (o instanceof Integer)
080: return ((Integer) o).intValue();
081: if (o instanceof Long) {
082: long l = ((Long) o).longValue();
083: if (l < (long) Integer.MAX_VALUE)
084: return (int) l;
085: o = ((Long) o).toString();
086: }
087: if (o instanceof Double) {
088: double d = 1000d * ((Double) o).doubleValue();
089: return (int) Math.round(d);
090: }
091: String s = "";
092: if (o instanceof String)
093: s = (String) o;
094:
095: // this can be used to calculate a score from a string
096: if ((s == null) || (s.length() == 0) || (s.charAt(0) == '-'))
097: return 0;
098: try {
099: long l = 0;
100: if (s.length() == shortDateFormatString.length()) {
101: // try a date
102: l = ((shortFormatter.parse(s).getTime() - date2000) / minutemillis);
103: if (l < 0)
104: l = 0;
105: } else {
106: // try a number
107: l = Long.parseLong(s);
108: }
109: // fix out-of-ranges
110: if (l > Integer.MAX_VALUE)
111: return Integer.MAX_VALUE;
112: if (l < 0) {
113: System.out
114: .println("string2score: negative score for input "
115: + s);
116: return 0;
117: }
118: return (int) l;
119: } catch (Exception e) {
120: // try it lex
121: int len = s.length();
122: if (len > 5)
123: len = 5;
124: int c = 0;
125: for (int i = 0; i < len; i++) {
126: c <<= 6;
127: c += plainByteArray[(byte) s.charAt(i)];
128: }
129: for (int i = len; i < 5; i++)
130: c <<= 6;
131: if (c > Integer.MAX_VALUE)
132: return Integer.MAX_VALUE;
133: if (c < 0) {
134: System.out
135: .println("string2score: negative score for input "
136: + s);
137: return 0;
138: }
139: return c;
140: }
141: }
142:
143: private static byte[] plainByteArray;
144: static {
145: plainByteArray = new byte[256];
146: for (int i = 0; i < 32; i++)
147: plainByteArray[i] = (byte) i;
148: for (int i = 32; i < 96; i++)
149: plainByteArray[i] = (byte) (i - 32);
150: for (int i = 96; i < 128; i++)
151: plainByteArray[i] = (byte) (i - 64);
152: for (int i = 128; i < 256; i++)
153: plainByteArray[i] = (byte) (i & 0X20);
154: }
155:
156: private long scoreKey(int elementNr, int elementCount) {
157: return (((long) (elementCount & 0xFFFFFFFFL)) << 32)
158: | ((long) (elementNr & 0xFFFFFFFFL));
159: }
160:
161: public synchronized long totalCount() {
162: return gcount;
163: }
164:
165: public synchronized int size() {
166: return refkeyDB.size();
167: }
168:
169: public synchronized void incScore(E[] objs) {
170: for (int i = 0; i < objs.length; i++)
171: addScore(objs[i], 1);
172: }
173:
174: public synchronized void decScore(E[] objs) {
175: for (int i = 0; i < objs.length; i++)
176: addScore(objs[i], -1);
177: }
178:
179: public synchronized void incScore(E obj) {
180: addScore(obj, 1);
181: }
182:
183: public synchronized void decScore(E obj) {
184: addScore(obj, -1);
185: }
186:
187: public synchronized void setScore(E obj, int newScore) {
188: if (obj == null)
189: return;
190: //System.out.println("setScore " + obj.getClass().getName());
191: Long usk = refkeyDB.remove(obj); // get unique score key, old entry is not needed any more
192: if (newScore < 0)
193: throw new kelondroOutOfLimitsException(newScore);
194:
195: if (usk == null) {
196: // set new value
197: usk = new Long(scoreKey(encnt++, newScore));
198:
199: // put new value into cluster
200: refkeyDB.put(obj, usk);
201: keyrefDB.put(usk, obj);
202:
203: } else {
204: // delete old entry
205: keyrefDB.remove(usk);
206:
207: // get previous handle and score
208: long c = usk.longValue();
209: int oldScore = (int) ((c & 0xFFFFFFFF00000000L) >> 32);
210: int oldHandle = (int) (c & 0xFFFFFFFFL);
211: gcount -= oldScore;
212:
213: // set new value
214: usk = new Long(scoreKey(oldHandle, newScore)); // generates an unique key for a specific score
215: refkeyDB.put(obj, usk);
216: keyrefDB.put(usk, obj);
217: }
218:
219: // increase overall counter
220: gcount += newScore;
221: }
222:
223: public synchronized void addScore(E obj, int incrementScore) {
224: if (obj == null)
225: return;
226: //System.out.println("setScore " + obj.getClass().getName());
227: Long usk = refkeyDB.remove(obj); // get unique score key, old entry is not needed any more
228:
229: if (usk == null) {
230: // set new value
231: if (incrementScore < 0)
232: throw new kelondroOutOfLimitsException(incrementScore);
233: usk = new Long(scoreKey(encnt++, incrementScore));
234:
235: // put new value into cluster
236: refkeyDB.put(obj, usk);
237: keyrefDB.put(usk, obj);
238:
239: } else {
240: // delete old entry
241: keyrefDB.remove(usk);
242:
243: // get previous handle and score
244: long c = usk.longValue();
245: int oldScore = (int) ((c & 0xFFFFFFFF00000000L) >> 32);
246: int oldHandle = (int) (c & 0xFFFFFFFFL);
247:
248: // set new value
249: int newValue = oldScore + incrementScore;
250: if (newValue < 0)
251: throw new kelondroOutOfLimitsException(newValue);
252: usk = new Long(scoreKey(oldHandle, newValue)); // generates an unique key for a specific score
253: refkeyDB.put(obj, usk);
254: keyrefDB.put(usk, obj);
255:
256: }
257:
258: // increase overall counter
259: gcount += incrementScore;
260: }
261:
262: public synchronized int deleteScore(E obj) {
263: // deletes entry and returns previous score
264: if (obj == null)
265: return 0;
266: //System.out.println("setScore " + obj.getClass().getName());
267: Long usk = refkeyDB.remove(obj); // get unique score key, old entry is not needed any more
268: if (usk == null)
269: return 0;
270:
271: // delete old entry
272: keyrefDB.remove(usk);
273:
274: // get previous handle and score
275: int oldScore = (int) ((usk.longValue() & 0xFFFFFFFF00000000L) >> 32);
276:
277: // decrease overall counter
278: gcount -= oldScore;
279:
280: return oldScore;
281: }
282:
283: public synchronized boolean existsScore(E obj) {
284: return (refkeyDB.get(obj) != null);
285: }
286:
287: public synchronized int getScore(E obj) {
288: if (obj == null)
289: return 0;
290: Long cs = refkeyDB.get(obj);
291: if (cs == null)
292: return 0;
293: return (int) ((cs.longValue() & 0xFFFFFFFF00000000L) >> 32);
294: }
295:
296: public synchronized int getMaxScore() {
297: if (refkeyDB.size() == 0)
298: return -1;
299: return (int) ((keyrefDB.lastKey().longValue() & 0xFFFFFFFF00000000L) >> 32);
300: }
301:
302: public synchronized int getMinScore() {
303: if (refkeyDB.size() == 0)
304: return -1;
305: return (int) ((keyrefDB.firstKey().longValue() & 0xFFFFFFFF00000000L) >> 32);
306: }
307:
308: public synchronized Object getMaxObject() {
309: if (refkeyDB.size() == 0)
310: return null;
311: //return getScores(1, false)[0];
312: return keyrefDB.get(keyrefDB.lastKey());
313: }
314:
315: public synchronized Object getMinObject() {
316: if (refkeyDB.size() == 0)
317: return null;
318: //return getScores(1, true)[0];
319: return keyrefDB.get(keyrefDB.firstKey());
320: }
321:
322: public synchronized E[] getScores(int maxCount, boolean up) {
323: return getScores(maxCount, up, Integer.MIN_VALUE,
324: Integer.MAX_VALUE);
325: }
326:
327: @SuppressWarnings("unchecked")
328: public synchronized E[] getScores(int maxCount, boolean up,
329: int minScore, int maxScore) {
330: if (maxCount > refkeyDB.size())
331: maxCount = refkeyDB.size();
332: E[] s = (E[]) new Object[maxCount];
333: Iterator<E> it = scores(up, minScore, maxScore);
334: int i = 0;
335: while ((i < maxCount) && (it.hasNext()))
336: s[i++] = it.next();
337: if (i < maxCount) {
338: // re-copy the result array
339: E[] sc = (E[]) new Object[i];
340: System.arraycopy(s, 0, sc, 0, i);
341: s = sc;
342: sc = null;
343: }
344: return s;
345: }
346:
347: public String toString() {
348: return refkeyDB + " / " + keyrefDB;
349: }
350:
351: public synchronized Iterator<E> scores(boolean up) {
352: if (up)
353: return new simpleScoreIterator<E>();
354: return new reverseScoreIterator<E>();
355: }
356:
357: public synchronized Iterator<E> scores(boolean up, int minScore,
358: int maxScore) {
359: return new komplexScoreIterator<E>(up, minScore, maxScore);
360: }
361:
362: private class komplexScoreIterator<A extends E> implements
363: Iterator<E> {
364:
365: boolean up;
366: TreeMap<Long, E> keyrefDBcopy;
367: E n;
368: int min, max;
369:
370: @SuppressWarnings("unchecked")
371: public komplexScoreIterator(boolean up, int minScore,
372: int maxScore) {
373: this .up = up;
374: this .min = minScore;
375: this .max = maxScore;
376: this .keyrefDBcopy = (TreeMap<Long, E>) keyrefDB.clone(); // NoSuchElementException here?
377: internalNext();
378: }
379:
380: public boolean hasNext() {
381: return (n != null);
382: }
383:
384: private void internalNext() {
385: Long key;
386: int score = (max + min) / 2;
387: while (keyrefDBcopy.size() > 0) {
388: key = (Long) ((up) ? keyrefDBcopy.firstKey()
389: : keyrefDBcopy.lastKey());
390: n = (E) keyrefDBcopy.remove(key);
391: score = (int) ((key.longValue() & 0xFFFFFFFF00000000L) >> 32);
392: if ((score >= min) && (score <= max))
393: return;
394: if (((up) && (score > max))
395: || ((!(up)) && (score < min))) {
396: keyrefDBcopy = new TreeMap<Long, E>();
397: n = null;
398: return;
399: }
400: }
401: n = null;
402: }
403:
404: public E next() {
405: E o = n;
406: internalNext();
407: return o;
408: }
409:
410: public void remove() {
411: if (n != null)
412: deleteScore(n);
413: }
414:
415: }
416:
417: private class reverseScoreIterator<A extends E> implements
418: Iterator<E> {
419:
420: SortedMap<Long, E> view;
421: Long key;
422:
423: public reverseScoreIterator() {
424: view = keyrefDB;
425: }
426:
427: public boolean hasNext() {
428: return view.size() > 0;
429: }
430:
431: public E next() {
432: key = view.lastKey();
433: view = view.headMap(key);
434: E value = keyrefDB.get(key);
435: //System.out.println("cluster reverse iterator: score = " + ((((Long) key).longValue() & 0xFFFFFFFF00000000L) >> 32) + ", handle = " + (((Long) key).longValue() & 0xFFFFFFFFL) + ", value = " + value);
436: return value;
437: }
438:
439: public void remove() {
440: Object val = keyrefDB.remove(key);
441: if (val != null)
442: refkeyDB.remove(val);
443: }
444:
445: }
446:
447: private class simpleScoreIterator<A extends E> implements
448: Iterator<E> {
449:
450: Iterator<Map.Entry<Long, E>> ii;
451: Map.Entry<Long, E> entry;
452:
453: public simpleScoreIterator() {
454: ii = keyrefDB.entrySet().iterator();
455: }
456:
457: public boolean hasNext() {
458: return ii.hasNext();
459: }
460:
461: public E next() {
462: entry = ii.next();
463: //System.out.println("cluster simple iterator: score = " + ((((Long) entry.getKey()).longValue() & 0xFFFFFFFF00000000L) >> 32) + ", handle = " + (((Long) entry.getKey()).longValue() & 0xFFFFFFFFL) + ", value = " + entry.getValue());
464: return entry.getValue();
465: }
466:
467: public void remove() {
468: ii.remove();
469: if (entry.getValue() != null)
470: refkeyDB.remove(entry.getValue());
471: }
472:
473: }
474:
475: public static void main(String[] args) {
476:
477: String t = "ZZZZZZZZZZ";
478: System.out.println("score of " + t + ": " + object2score(t));
479: if (args.length > 0) {
480: System.out.println("score of " + args[0] + ": "
481: + object2score(args[0]));
482: System.exit(0);
483: }
484:
485: System.out.println("Test for Score: start");
486: kelondroMScoreCluster<String> s = new kelondroMScoreCluster<String>();
487: long c = 0;
488:
489: // create cluster
490: long time = System.currentTimeMillis();
491: Random random = new Random(1234);
492: int r;
493: int count = 20;
494: int[] mem = new int[count];
495:
496: for (int x = 0; x < 100; x++) {
497: for (int i = 0; i < count; i++) {
498: r = random.nextInt();
499: mem[i] = r;
500: s.addScore("score#" + r, r);
501: c += r;
502: }
503:
504: // delete some
505: int p;
506: for (int i = 0; i < (count / 2); i++) {
507: p = (int) (random.nextFloat() * count);
508: if (s.existsScore("score#" + mem[p])) {
509: System.out.println("delete score#" + mem[p]);
510: s.deleteScore("score#" + mem[p]);
511: c -= mem[p];
512: }
513: }
514: }
515:
516: System.out.println("result:");
517: Object[] result;
518: result = s.getScores(s.size(), true);
519: for (int i = 0; i < s.size(); i++)
520: System.out.println("up: " + result[i]);
521: result = s.getScores(s.size(), false);
522: for (int i = 0; i < s.size(); i++)
523: System.out.println("down: " + result[i]);
524:
525: System.out.println("finished create. time = "
526: + (System.currentTimeMillis() - time));
527: System.out.println("total=" + s.totalCount() + ", elements="
528: + s.size() + ", redundant count=" + c);
529:
530: /*
531: // delete cluster
532: time = System.currentTimeMillis();
533: for (int i = 0; i < 10000; i++) {
534: s.deleteScore("score#" + i + "xxx" + i + "xxx" + i + "xxx" + i + "xxx");
535: c -= i/10;
536: }
537: System.out.println("finished delete. time = " + (System.currentTimeMillis() - time));
538: System.out.println("total=" + s.totalCount() + ", elements=" + s.size() + ", redundant count=" + c);
539: */
540: }
541: }
|