001: // kelondroIntBytesMap.java
002: // (C) 2006 by Michael Peter Christen; mc@anomic.de, Frankfurt a. M., Germany
003: // first published 08.06.2006 on http://www.anomic.de
004: //
005: // $LastChangedDate: 2006-04-02 22:40:07 +0200 (So, 02 Apr 2006) $
006: // $LastChangedRevision: 1986 $
007: // $LastChangedBy: orbiter $
008: //
009: // LICENSE
010: //
011: // This program is free software; you can redistribute it and/or modify
012: // it under the terms of the GNU General Public License as published by
013: // the Free Software Foundation; either version 2 of the License, or
014: // (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: package de.anomic.kelondro;
026:
027: import java.util.ArrayList;
028: import java.util.HashSet;
029: import java.util.Iterator;
030: import java.util.Random;
031:
032: public class kelondroIntBytesMap {
033:
034: // we use two indexes: one for initialization, and one for data aquired during runtime
035: // this has a gread advantage, if the setup-data is large. Then a re-organisation of
036: // the run-time data does not need much memory and is done faster.
037: // we distinguish two phases: the init phase where data can only be written
038: // to index0 with addb, and a runtime-phase where data can only be written
039: // to index1 with putb.
040:
041: private kelondroRow rowdef;
042: private kelondroRowSet index0, index1;
043: private kelondroOrder<kelondroRow.Entry> entryOrder;
044:
045: public kelondroIntBytesMap(int payloadSize, int initSize) {
046: this .rowdef = new kelondroRow(
047: "Cardinal key-4 {b256}, byte[] payload-" + payloadSize,
048: kelondroNaturalOrder.naturalOrder, 0);
049: this .index0 = new kelondroRowSet(rowdef, initSize);
050: this .index1 = null;
051: this .entryOrder = new kelondroRow.EntryComparator(
052: rowdef.objectOrder);
053: }
054:
055: public long memoryNeededForGrow() {
056: if (index1 == null)
057: return index0.memoryNeededForGrow();
058: else
059: return index1.memoryNeededForGrow();
060: }
061:
062: public kelondroRow row() {
063: return index0.row();
064: }
065:
066: public byte[] getb(int ii) {
067: assert ii >= 0 : "i = " + ii;
068: byte[] key = kelondroNaturalOrder.encodeLong((long) ii, 4);
069: if (index0 != null) {
070: if (index1 == null) {
071: // finish initialization phase
072: index0.sort();
073: index0.uniq();
074: index1 = new kelondroRowSet(rowdef, 0);
075: }
076: kelondroRow.Entry indexentry = index0.get(key);
077: if (indexentry != null)
078: return indexentry.getColBytes(1);
079: }
080: assert (index1 != null);
081: kelondroRow.Entry indexentry = index1.get(key);
082: if (indexentry == null)
083: return null;
084: return indexentry.getColBytes(1);
085: }
086:
087: public byte[] putb(int ii, byte[] value) {
088: assert ii >= 0 : "i = " + ii;
089: assert value != null;
090: byte[] key = kelondroNaturalOrder.encodeLong((long) ii, 4);
091: if (index0 != null) {
092: if (index1 == null) {
093: // finish initialization phase
094: index0.sort();
095: index0.uniq();
096: index1 = new kelondroRowSet(rowdef, 0);
097: }
098: kelondroRow.Entry indexentry = index0.get(key);
099: if (indexentry != null) {
100: byte[] oldv = indexentry.getColBytes(1);
101: indexentry.setCol(0, key);
102: indexentry.setCol(1, value);
103: index0.put(indexentry);
104: return oldv;
105: }
106: // else place it in the index1
107: }
108: // at this point index1 cannot be null
109: assert (index1 != null);
110:
111: kelondroRow.Entry newentry = rowdef.newEntry();
112: newentry.setCol(0, (long) ii);
113: newentry.setCol(1, value);
114: kelondroRow.Entry oldentry = index1.put(newentry);
115: if (oldentry == null)
116: return null;
117: return oldentry.getColBytes(1);
118: }
119:
120: public void addb(int ii, byte[] value) {
121: assert index1 == null; // valid only in init-phase
122: assert ii >= 0 : "i = " + ii;
123: assert value != null;
124: kelondroRow.Entry newentry = index0.row().newEntry();
125: newentry.setCol(0, (long) ii);
126: newentry.setCol(1, value);
127: index0.addUnique(newentry);
128: }
129:
130: public byte[] removeb(int ii) {
131: assert ii >= 0 : "i = " + ii;
132:
133: byte[] key = kelondroNaturalOrder.encodeLong((long) ii, 4);
134: if (index0 != null) {
135: if (index1 == null) {
136: // finish initialization phase
137: index0.sort();
138: index0.uniq();
139: index1 = new kelondroRowSet(rowdef, 0);
140: }
141: kelondroRow.Entry indexentry = index0.remove(key, true);
142: if (indexentry != null) {
143: return indexentry.getColBytes(1);
144: }
145: // else remove it from the index1
146: }
147: // at this point index1 cannot be null
148: assert (index1 != null);
149: if (index1.size() == 0)
150: return null;
151: kelondroRow.Entry indexentry = index1.remove(key, true);
152: if (indexentry == null)
153: return null;
154: return indexentry.getColBytes(1);
155: }
156:
157: public byte[] removeoneb() {
158: if ((index1 != null) && (index1.size() != 0)) {
159: kelondroRow.Entry indexentry = index1.removeOne();
160: assert (indexentry != null);
161: if (indexentry == null)
162: return null;
163: //assert consistencyAnalysis0() : "consistency problem: " + consistencyAnalysis();
164: return indexentry.getColBytes(1);
165: }
166: if ((index0 != null) && (index0.size() != 0)) {
167: kelondroRow.Entry indexentry = index0.removeOne();
168: assert (indexentry != null);
169: if (indexentry == null)
170: return null;
171: //assert consistencyAnalysis0() : "consistency problem: " + consistencyAnalysis();
172: return indexentry.getColBytes(1);
173: }
174: return null;
175: }
176:
177: public int size() {
178: if ((index0 != null) && (index1 == null)) {
179: //assert consistencyAnalysis0() : "consistency problem: " + consistencyAnalysis();
180: return index0.size();
181: }
182: if ((index0 == null) && (index1 != null)) {
183: //assert consistencyAnalysis0() : "consistency problem: " + consistencyAnalysis();
184: return index1.size();
185: }
186: assert ((index0 != null) && (index1 != null));
187: //assert consistencyAnalysis0() : "consistency problem: " + consistencyAnalysis();
188: return index0.size() + index1.size();
189: }
190:
191: public Iterator<kelondroRow.Entry> rows() {
192: if (index0 != null) {
193: if (index1 == null) {
194: // finish initialization phase
195: index0.sort();
196: index0.uniq();
197: index1 = new kelondroRowSet(rowdef, 0);
198: }
199: return index0.rows(true, null);
200: }
201: assert (index1 != null);
202: if (index0 == null) {
203: return index1.rows(true, null);
204: }
205: return new kelondroMergeIterator<kelondroRow.Entry>(index0
206: .rows(true, null), index1.rows(true, null), entryOrder,
207: kelondroMergeIterator.simpleMerge, true);
208: }
209:
210: public void flush() {
211: if (index0 != null) {
212: index0.sort();
213: index0.trim(true);
214: }
215: if (index1 != null) {
216: index1.sort();
217: index1.trim(true);
218: }
219: }
220:
221: public kelondroProfile profile() {
222: if (index0 == null)
223: return index1.profile();
224: if (index1 == null)
225: return index0.profile();
226: return kelondroProfile.consolidate(index0.profile(), index1
227: .profile());
228: }
229:
230: public static void main(String[] args) {
231: boolean assertEnabled = false;
232: assert assertEnabled = true;
233: System.out.println((assertEnabled) ? "asserts are enabled"
234: : "enable asserts with 'java -ea'; not enabled yet");
235: long start = System.currentTimeMillis();
236: long randomstart = 0;
237: Random random = new Random(randomstart);
238: long r;
239: Long R;
240: int p, rc = 0;
241: ArrayList<Long> ra = new ArrayList<Long>();
242: HashSet<Long> jcontrol = new HashSet<Long>();
243: kelondroIntBytesMap kcontrol = new kelondroIntBytesMap(1, 0);
244: for (int i = 0; i < 1000000; i++) {
245: r = Math.abs(random.nextLong() % 10000);
246: //System.out.println("add " + r);
247: jcontrol.add(new Long(r));
248: kcontrol.putb((int) r, "x".getBytes());
249: if (random.nextLong() % 5 == 0)
250: ra.add(new Long(r));
251: if ((ra.size() > 0) && (random.nextLong() % 7 == 0)) {
252: rc++;
253: p = Math.abs(random.nextInt()) % ra.size();
254: R = (Long) ra.get(p);
255: //System.out.println("remove " + R.longValue());
256: jcontrol.remove(R);
257: kcontrol.removeb((int) R.longValue());
258: assert kcontrol.removeb((int) R.longValue()) == null;
259: }
260: assert jcontrol.size() == kcontrol.size();
261: }
262: System.out.println("removed: " + rc
263: + ", size of jcontrol set: " + jcontrol.size()
264: + ", size of kcontrol set: " + kcontrol.size());
265: System.out.println("Time: "
266: + ((System.currentTimeMillis() - start) / 1000)
267: + " seconds");
268: }
269:
270: }
|