001: /* CVS ID: $Id: StringHeap.java,v 1.1.1.1 2002/10/02 18:42:49 wastl Exp $ */
002: package net.wastl.webmail.misc;
003:
004: /*
005: * StringHeap.java
006: *
007: * Created: Mon Oct 4 13:28:09 1999
008: *
009: * Copyright (C) 1999-2000 Sebastian Schaffert
010: *
011: * This program is free software; you can redistribute it and/or
012: * modify it under the terms of the GNU General Public License
013: * as published by the Free Software Foundation; either version 2
014: * of the License, or (at your option) any later version.
015: *
016: * This program is distributed in the hope that it will be useful,
017: * but WITHOUT ANY WARRANTY; without even the implied warranty of
018: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
019: * GNU General Public License for more details.
020: *
021: * You should have received a copy of the GNU General Public License
022: * along with this program; if not, write to the Free Software
023: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
024: */
025: /**
026: * This class is a simple heap structure for sorting Strings lexicographically.
027: * It is mainly used in WebMail for generating a sorted output of Hashkeys.
028: *
029: * @author Sebastian Schaffert
030: * @version
031: */
032:
033: public class StringHeap {
034:
035: int num_entries;
036: String[] keys;
037:
038: public StringHeap(int capacity) {
039: keys = new String[capacity + 1];
040: num_entries = 0;
041: }
042:
043: /**
044: * Insert a key/value pair
045: * Reorganize Heap afterwards
046: */
047: public void insert(String key) {
048: keys[num_entries] = key;
049: num_entries++;
050:
051: increase(num_entries);
052: }
053:
054: /**
055: * Return and delete the key with the lowest long value. Reorganize Heap.
056: */
057: public String next() {
058: String ret = keys[0];
059: keys[0] = keys[num_entries - 1];
060: num_entries--;
061:
062: decrease(1);
063:
064: return ret;
065: }
066:
067: public boolean isEmpty() {
068: return num_entries == 0;
069: }
070:
071: /**
072: * Remove an Object from the Heap.
073: * Unfortunately not (yet) of very good complexity since we are doing
074: * a simple linear search here.
075: * @param key The key to remove from the heap
076: */
077: public void remove(String key) {
078: for (int i = 0; i < num_entries; i++) {
079: if (key.equals(keys[i])) {
080: num_entries--;
081: int cur_pos = i + 1;
082: keys[i] = keys[num_entries];
083: decrease(cur_pos);
084: break;
085: }
086: }
087: }
088:
089: /**
090: * Lift an element in the heap structure
091: * Note that the cur_pos is actually one larger than the position in the array!
092: */
093: protected void increase(int cur_pos) {
094: while (cur_pos > 1
095: && keys[cur_pos - 1].compareTo(keys[cur_pos / 2 - 1]) < 0) {
096: String tmp1 = keys[cur_pos / 2 - 1];
097: keys[cur_pos / 2 - 1] = keys[cur_pos - 1];
098: keys[cur_pos - 1] = tmp1;
099: cur_pos /= 2;
100: }
101: }
102:
103: /**
104: * Lower an element in the heap structure
105: * Note that the cur_pos is actually one larger than the position in the array!
106: */
107: protected void decrease(int cur_pos) {
108: while ((cur_pos * 2 <= num_entries && keys[cur_pos - 1]
109: .compareTo(keys[cur_pos * 2 - 1]) > 0)
110: || (cur_pos * 2 + 1 <= num_entries && keys[cur_pos - 1]
111: .compareTo(keys[cur_pos * 2]) > 0)) {
112: int lesser_son;
113: if (cur_pos * 2 + 1 <= num_entries) {
114: lesser_son = keys[cur_pos * 2 - 1]
115: .compareTo(keys[cur_pos * 2]) < 0 ? cur_pos * 2
116: : cur_pos * 2 + 1;
117: } else {
118: lesser_son = cur_pos * 2;
119: }
120: String tmp1 = keys[cur_pos - 1];
121: keys[cur_pos - 1] = keys[lesser_son - 1];
122: keys[lesser_son - 1] = tmp1;
123: cur_pos = lesser_son;
124: }
125: }
126:
127: } // StringHeap
|