LongMap


1   package com.quadcap.util.collections;
2   
3   /* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
4    *
5    * This software is distributed under the Quadcap Free Software License.
6    * This software may be used or modified for any purpose, personal or
7    * commercial.  Open Source redistributions are permitted.  Commercial
8    * redistribution of larger works derived from, or works which bundle
9    * this software requires a "Commercial Redistribution License"; see
10   * http://www.quadcap.com/purchase.
11   *
12   * Redistributions qualify as "Open Source" under  one of the following terms:
13   *   
14   *    Redistributions are made at no charge beyond the reasonable cost of
15   *    materials and delivery.
16   *
17   *    Redistributions are accompanied by a copy of the Source Code or by an
18   *    irrevocable offer to provide a copy of the Source Code for up to three
19   *    years at the cost of materials and delivery.  Such redistributions
20   *    must allow further use, modification, and redistribution of the Source
21   *    Code under substantially the same terms as this license.
22   *
23   * Redistributions of source code must retain the copyright notices as they
24   * appear in each source code file, these license terms, and the
25   * disclaimer/limitation of liability set forth as paragraph 6 below.
26   *
27   * Redistributions in binary form must reproduce this Copyright Notice,
28   * these license terms, and the disclaimer/limitation of liability set
29   * forth as paragraph 6 below, in the documentation and/or other materials
30   * provided with the distribution.
31   *
32   * The Software is provided on an "AS IS" basis.  No warranty is
33   * provided that the Software is free of defects, or fit for a
34   * particular purpose.  
35   *
36   * Limitation of Liability. Quadcap Software shall not be liable
37   * for any damages suffered by the Licensee or any third party resulting
38   * from use of the Software.
39   */
40  
41  import java.util.Iterator  ;
42  
43  import com.quadcap.util.Debug;
44  
45  /**
46   * A map with long values as keys
47   *
48   * @author Stan Bailes
49   */
50  public class LongMap {
51      int                         size    = 0;
52      Entry[]                     entries;
53      Entry                       freeList;
54  
55      /**
56       * Create an empty map with a specified number of buckets.
57       */
58      public LongMap(int initSize) {
59          initSize |= 1;
60          while (!isPrime(initSize)) initSize += 2;
61          entries = new Entry[initSize];
62      }
63  
64      /**
65       * Return the Object with the specified key value
66       */
67      public synchronized final Object   get(long key) {
68          int h = hash(key);
69          for (Entry entry = entries[h]; entry != null; entry = entry.next) {
70              if (entry.key == key) return entry.val;
71          }
72          return null;
73      }
74  
75      /**
76       * Insert a key, value pair
77       */
78      public synchronized final void put(long key, Object   val) {
79          int h = hash(key);
80          for (Entry entry = entries[h]; entry != null; entry = entry.next) {
81              if (entry.key == key) {
82                  entry.val = val;
83                  return;
84              }
85          }
86          Entry entry = getEntry(key, val);
87          entry.next = entries[h];
88          entries[h] = entry;
89      }
90  
91      /**
92       * Remove the specified key
93       */
94      public synchronized final void remove(long key) {
95          int h = hash(key);
96          Entry prev = null;
97          Entry entry = entries[h];
98          while (entry != null) {
99              Entry next = entry.next;
100             if (entry.key == key) {
101                 if (prev == null) {
102                     entries[h] = next;
103                 } else {
104                     prev.next = next;
105                 }
106                 freeEntry(entry);
107                 return;
108             }
109             prev = entry;
110             entry = next;
111         }
112     }
113 
114     public String   toString() {
115         StringBuffer   sb = new StringBuffer  ("{");
116         LongIterator k = keys();
117         String   delim = "";
118         while (k.hasNext()) {
119             long v = k.nextLong();
120             Object   d = get(v);
121             sb.append(delim);
122             sb.append(v);
123             sb.append('=');
124             sb.append(String.valueOf(d));
125             delim = ",";
126         }
127         sb.append("}");
128         return sb.toString();
129     }
130             
131             
132 
133     /**
134      * Return the number of entries
135      */
136     public final int size() { return size; }
137 
138     public final int buckets() { return entries.length; }
139 
140     //-------------------------------------------------------
141     final Entry getEntry(long key, Object   val) {
142         Entry entry = freeList;
143         if (entry == null) {
144             entry = new Entry();
145         } else {
146             freeList = entry.next;
147         }
148         entry.key = key;
149         entry.val = val;
150         size++;
151         return entry;
152     }
153 
154     final void freeEntry(Entry entry) {
155         size--;
156         entry.val = null;
157         entry.next = freeList;
158         freeList = entry;
159     }
160 
161     final boolean isPrime(int x) {
162         return IntMap.isPrime(x);
163     }
164 
165     public LongIterator keys() {
166         return new LongMapIterator(this);
167     }
168 
169     final int hash(long key) {
170         int h = (int)(key % entries.length);
171         if (h < 0) {
172             h = 0 - h;
173         }
174         return h;
175     }
176 
177     class Entry {
178         long            key;
179         Object            val;
180         Entry           next;
181     }
182 
183     public class LongMapIterator implements LongIterator {
184         LongMap                 map;
185         int                     epos            = 0;
186         Entry                   entry           = null;
187         Entry                   last            = null;
188         
189         public LongMapIterator(LongMap map) {
190             this.map = map;
191             advance();
192         }
193 
194         public boolean hasNext() {
195             return entry != null;
196         }
197 
198         void advance() {
199             last = entry;
200             if (entry != null && entry.next != null) {
201                 entry = entry.next;
202             } else {
203                 entry = null;
204             }
205             while (epos < map.entries.length && entry == null) {
206                 entry = map.entries[epos++];
207             }
208         }
209             
210         public Object   next() {
211             Long   ret = null;
212             if (entry != null) {
213                 ret = new Long  (entry.key);
214                 advance();
215             }
216             return ret;
217         }
218 
219         public long nextLong() {
220             long ret = 0;
221             if (entry != null) {
222                 ret = entry.key;
223                 advance();
224             }
225             return ret;
226         }
227 
228         public void remove() {
229             if (last != null) {
230                 map.remove(last.key);
231                 last = null;
232             }
233         }
234     }
235 }
236
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags