1#import <Foundation/Foundation.h>
2#import "AMutableArray.h"
3#import "LinkedHashMap.h"
4#import "RuntimeException.h"
5
6extern NSInteger const DEFAULT_INITIAL_CAPACITY;
7extern float const DEFAULT_LOAD_FACTOR;
8
9@implementation LHMEntry
10
11@synthesize before;
12@synthesize after;
13@synthesize accessOrder;
14
15- (id) newEntry:(NSInteger)aHash key:(NSString *)aKey value:(id)aValue next:(LHMEntry *)aNext
16{
17    return [[LHMEntry alloc] init:aHash key:aKey value:aValue next:aNext];
18}
19
20- (id) init:(NSInteger)aHash key:(NSString *)aKey value:(id)aValue next:(LHMEntry *)aNext
21{
22    self = [super init:aHash key:aKey value:aValue next:aNext];
23    if (self) {
24    }
25    return self;
26}
27
28
29- (void) dealloc
30{
31    [before release];
32    [after release];
33    [super dealloc];
34}
35
36/**
37 * Removes this entry from the linked list.
38 */
39- (void) removeEntry
40{
41    before.after = after;
42    after.before = before;
43}
44
45
46/**
47 * Inserts this entry before the specified existing entry in the list.
48 */
49- (void) addBefore:(LHMEntry *)existingEntry
50{
51    after = [existingEntry retain];
52    before = [existingEntry.before retain];
53    before.after = [self retain];
54    after.before = [self retain];
55}
56
57
58/**
59 * This method is invoked by the superclass whenever the value
60 * of a pre-existing entry is read by Map.get or modified by Map.set.
61 * If the enclosing Map is access-ordered, it moves the entry
62 * to the end of the list; otherwise, it does nothing.
63 */
64- (void) recordAccess:(LinkedHashMap *)m
65{
66    LinkedHashMap *lhm = (LinkedHashMap *)m;
67    if (lhm.accessOrder) {
68        lhm.modCount++;
69        [self removeEntry];
70        [self addBefore:lhm.header];
71    }
72}
73
74- (void) recordRemoval:(LinkedHashMap *)m
75{
76    [self removeEntry];
77}
78
79@end
80
81@implementation LinkedHashIterator
82
83@synthesize nextEntry;
84@synthesize lastReturned;
85@synthesize lhm;
86
87+ (LinkedHashIterator *) newIterator:(LinkedHashMap *)aLHM
88{
89    return [[LinkedHashIterator alloc] init:aLHM];
90}
91
92- (id) init:(LinkedHashMap *)aLHM
93{
94    self = [super init];
95    if ( self ) {
96        lhm = aLHM;
97        nextEntry = lhm.header.after;
98        lastReturned = nil;
99        expectedModCount = lhm.modCount;
100/*
101        AMutableArray *a = [AMutableArray arrayWithCapacity:lhm.Capacity];
102        LHMEntry *tmp = lhm.header.after;
103        while ( tmp != lhm.header ) {
104            [a addObject:tmp];
105            tmp = tmp.after;
106        }
107        anArray = [NSArray arrayWithArray:a];
108 */
109    }
110    return self;
111}
112
113- (BOOL) hasNext
114{
115    return nextEntry != lhm.header;
116}
117
118- (void) remove
119{
120    if (lastReturned == nil)
121        @throw [[IllegalStateException newException] autorelease];
122    if (lhm.modCount != expectedModCount)
123        @throw [[ConcurrentModificationException newException:@"Unexpected modCount"] autorelease];
124    [lhm remove:(NSString *)(lastReturned.key)];
125    lastReturned = nil;
126    expectedModCount = lhm.modCount;
127}
128
129- (LHMEntry *) nextEntry
130{
131    if (lhm.modCount != expectedModCount)
132        @throw [[ConcurrentModificationException newException:@"Unexpected modCount"] autorelease];
133    if (nextEntry == lhm.header)
134        @throw [[[NoSuchElementException alloc] init] autorelease];
135    LHMEntry * e = lastReturned = nextEntry;
136    nextEntry = e.after;
137    return e;
138}
139
140- (void) dealloc
141{
142    [nextEntry release];
143    [lastReturned release];
144    [super dealloc];
145}
146
147@end
148
149@implementation LHMKeyIterator
150+ (LHMKeyIterator *)newIterator:(LinkedHashMap *)aLHM
151{
152    return [[LHMKeyIterator alloc] init:aLHM];
153}
154
155- (id) init:(LinkedHashMap *)aLHM
156{
157    self = [super init:aLHM];
158    if ( self ) {
159    }
160    return self;
161}
162
163- (NSString *) next
164{
165    return [self nextEntry].key;
166}
167
168@end
169
170@implementation LHMValueIterator
171+ (LHMValueIterator *)newIterator:(LinkedHashMap *)aLHM
172{
173    return [[LHMValueIterator alloc] init:aLHM];
174}
175
176- (id) init:(LinkedHashMap *)aLHM
177{
178    self = [super init:aLHM];
179    if ( self ) {
180    }
181    return self;
182}
183
184- (id) next
185{
186    return [self nextEntry].value;
187}
188
189@end
190
191@implementation LHMEntryIterator
192+ (LHMEntryIterator *)newIterator:(LinkedHashMap *)aLHM
193{
194    return [[LHMEntryIterator alloc] init:aLHM];
195}
196
197- (id) init:(LinkedHashMap *)aLHM
198{
199    self = [super init:aLHM];
200    if ( self ) {
201    }
202    return self;
203}
204
205- (LHMEntry *) next
206{
207    return [self nextEntry];
208}
209
210@end
211
212//long const serialVersionUID = 3801124242820219131L;
213
214@implementation LinkedHashMap
215
216@synthesize header;
217@synthesize accessOrder;
218
219/**
220 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
221 * with the specified initial capacity and load factor.
222 *
223 * @param  initialCapacity the initial capacity
224 * @param  loadFactor      the load factor
225 * @throws IllegalArgumentException if the initial capacity is negative
226 * or the load factor is nonpositive
227 */
228+ (id) newLinkedHashMap:(NSInteger)anInitialCapacity
229             loadFactor:(float)loadFactor
230            accessOrder:(BOOL)anAccessOrder
231{
232    return [[LinkedHashMap alloc] init:anInitialCapacity
233                            loadFactor:loadFactor
234                           accessOrder:(BOOL)anAccessOrder];
235}
236
237+ (id) newLinkedHashMap:(NSInteger)anInitialCapacity loadFactor:(float)loadFactor
238{
239    return [[LinkedHashMap alloc] init:anInitialCapacity loadFactor:loadFactor];
240}
241
242+ (id) newLinkedHashMap:(NSInteger)anInitialCapacity
243{
244    return [[LinkedHashMap alloc] init:anInitialCapacity loadFactor:DEFAULT_LOAD_FACTOR];
245}
246
247/**
248 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
249 * specified initial capacity, load factor and ordering mode.
250 *
251 * @param  initialCapacity the initial capacity
252 * @param  loadFactor      the load factor
253 * @param  accessOrder     the ordering mode - <tt>true</tt> for
254 * access-order, <tt>false</tt> for insertion-order
255 * @throws IllegalArgumentException if the initial capacity is negative
256 * or the load factor is nonpositive
257 */
258- (id) init:(NSInteger)anInitialCapacity loadFactor:(float)aLoadFactor accessOrder:(BOOL)anAccessOrder
259{
260    self = [super init:anInitialCapacity loadFactor:aLoadFactor];
261    if ( self ) {
262        accessOrder = anAccessOrder;
263        header = [[[LHMEntry alloc] init:-1 key:nil value:nil next:nil] retain];
264        header.before = header.after = header;
265    }
266    return self;
267}
268
269- (id) init:(NSInteger)anInitialCapacity loadFactor:(float)aLoadFactor
270{
271    self = [super init:anInitialCapacity loadFactor:aLoadFactor];
272    if ( self ) {
273        accessOrder = NO;
274        header = [[[LHMEntry alloc] init:-1 key:nil value:nil next:nil] retain];
275        header.before = header.after = header;
276    }
277    return self;
278}
279
280/**
281 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
282 * with the specified initial capacity and a default load factor (0.75).
283 *
284 * @param  initialCapacity the initial capacity
285 * @throws IllegalArgumentException if the initial capacity is negative
286 */
287- (id) init:(NSInteger)initialCapacity
288{
289    self = [super init:initialCapacity loadFactor:DEFAULT_LOAD_FACTOR];
290    if ( self ) {
291        accessOrder = NO;
292        header = [[[LHMEntry alloc] init:-1 key:nil value:nil next:nil] retain];
293        header.before = header.after = header;
294    }
295    return self;
296}
297
298/**
299 * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
300 * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
301 * instance is created with a default load factor (0.75) and an initial
302 * capacity sufficient to hold the mappings in the specified map.
303 *
304 * @param  m the map whose mappings are to be placed in this map
305 * @throws NullPointerException if the specified map is null
306 */
307- (id) initWithM:(LinkedHashMap *)m
308{
309    self = [super initWithM:m];
310    if ( self ) {
311        accessOrder = NO;
312        header = [[[LHMEntry alloc] init:-1 key:nil value:nil next:nil] retain];
313        header.before = header.after = header;
314    }
315    return self;
316}
317
318/**
319 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
320 * with the default initial capacity (16) and load factor (0.75).
321 */
322- (id) init
323{
324    self = [super init];
325    if ( self ) {
326        accessOrder = NO;
327        header = [[[LHMEntry alloc] init:-1 key:nil value:nil next:nil] retain];
328        header.before = header.after = header;
329    }
330    return self;
331}
332
333
334/**
335 * Transfers all entries to new table array.  This method is called
336 * by superclass resize.  It is overridden for performance, as it is
337 * faster to iterate using our linked list.
338 */
339- (void) transfer:(AMutableArray *)newTable
340{
341    NSInteger newCapacity = [newTable count];
342
343    for (LHMEntry * e = header.after; e != header; e = e.after) {
344        NSInteger index = [self indexFor:e.hash length:newCapacity];
345        e.next = [newTable objectAtIndex:index];
346        [newTable replaceObjectAtIndex:index withObject:e];
347    }
348
349}
350
351/**
352 * Returns <tt>true</tt> if this map maps one or more keys to the
353 * specified value.
354 *
355 * @param value value whose presence in this map is to be tested
356 * @return <tt>true</tt> if this map maps one or more keys to the
357 * specified value
358 */
359- (BOOL) containsValue:(id)value
360{
361    if (value == nil) {
362
363        for (LHMEntry * e = header.after; e != header; e = e.after)
364            if (e.value == nil)
365                return YES;
366
367    }
368    else {
369
370        for (LHMEntry * e = header.after; e != header; e = e.after)
371            if ([value isEqualTo:e.value])
372                return YES;
373
374    }
375    return NO;
376}
377
378/**
379 * Returns the value to which the specified key is mapped,
380 * or {@code null} if this map contains no mapping for the key.
381 *
382 * <p>More formally, if this map contains a mapping from a key
383 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
384 * key.equals(k))}, then this method returns {@code v}; otherwise
385 * it returns {@code null}.  (There can be at most one such mapping.)
386 *
387 * <p>A return value of {@code null} does not <i>necessarily</i>
388 * indicate that the map contains no mapping for the key; it's also
389 * possible that the map explicitly maps the key to {@code null}.
390 * The {@link #containsKey containsKey} operation may be used to
391 * distinguish these two cases.
392 */
393- (id) get:(NSString *)aKey
394{
395    LHMEntry * e = (LHMEntry *)[self getEntry:aKey];
396    if (e == nil)
397        return nil;
398    [e recordAccess:self];
399    return e.value;
400}
401
402
403/**
404 * Removes all of the mappings from this map.
405 * The map will be empty after this call returns.
406 */
407- (void) clear
408{
409    [super clear];
410    header.before = header.after = header;
411}
412
413- (void) dealloc {
414    [header release];
415    [super dealloc];
416}
417
418- (LHMEntryIterator *) newEntryIterator
419{
420    return [LHMEntryIterator newIterator:self];
421}
422
423- (LHMKeyIterator *) newKeyIterator
424{
425    return [LHMKeyIterator newIterator:self];
426}
427
428- (LHMValueIterator *) newValueIterator
429{
430    return [LHMValueIterator newIterator:self];
431}
432
433
434/**
435 * This override alters behavior of superclass put method. It causes newly
436 * allocated entry to get inserted at the end of the linked list and
437 * removes the eldest entry if appropriate.
438 */
439- (void) addEntry:(NSInteger)aHash key:(NSString *)aKey value:(id)aValue bucketIndex:(NSInteger)aBucketIndex
440{
441    [self createEntry:aHash key:aKey value:aValue bucketIndex:aBucketIndex];
442    LHMEntry * eldest = header.after;
443    if ([self removeEldestEntry:eldest]) {
444        [self removeEntryForKey:eldest.key];
445    }
446    else {
447        if (count >= threshold)
448            [self resize:2 * [buffer length]];
449    }
450}
451
452
453/**
454 * This override differs from addEntry in that it doesn't resize the
455 * table or remove the eldest entry.
456 */
457- (void) createEntry:(NSInteger)aHash key:(NSString *)aKey value:(id)aValue bucketIndex:(NSInteger)bucketIndex
458{
459    LHMEntry *old = (LHMEntry *)ptrBuffer[bucketIndex];
460    LHMEntry *e = [[[LHMEntry alloc] init:aHash key:aKey value:aValue next:old] retain];
461    ptrBuffer[bucketIndex] = (id)e;
462    [e addBefore:header];
463    count++;
464}
465
466
467/**
468 * Returns <tt>true</tt> if this map should remove its eldest entry.
469 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
470 * inserting a new entry into the map.  It provides the implementor
471 * with the opportunity to remove the eldest entry each time a new one
472 * is added.  This is useful if the map represents a cache: it allows
473 * the map to reduce memory consumption by deleting stale entries.
474 *
475 * <p>Sample use: this override will allow the map to grow up to 100
476 * entries and then delete the eldest entry each time a new entry is
477 * added, maintaining a steady state of 100 entries.
478 * <pre>
479 * private static final NSInteger MAX_ENTRIES = 100;
480 *
481 * protected boolean removeEldestEntry(Map.LHMEntry eldest) {
482 * return count() > MAX_ENTRIES;
483 * }
484 * </pre>
485 *
486 * <p>This method typically does not modify the map in any way,
487 * instead allowing the map to modify itself as directed by its
488 * return value.  It <i>is</i> permitted for this method to modify
489 * the map directly, but if it does so, it <i>must</i> return
490 * <tt>false</tt> (indicating that the map should not attempt any
491 * further modification).  The effects of returning <tt>true</tt>
492 * after modifying the map from within this method are unspecified.
493 *
494 * <p>This implementation merely returns <tt>false</tt> (so that this
495 * map acts like a normal map - the eldest element is never removed).
496 *
497 * @param    eldest The least recently inserted entry in the map, or if
498 * this is an access-ordered map, the least recently accessed
499 * entry.  This is the entry that will be removed it this
500 * method returns <tt>true</tt>.  If the map was empty prior
501 * to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
502 * in this invocation, this will be the entry that was just
503 * inserted; in other words, if the map contains a single
504 * entry, the eldest entry is also the newest.
505 * @return   <tt>true</tt> if the eldest entry should be removed
506 * from the map; <tt>false</tt> if it should be retained.
507 */
508- (BOOL) removeEldestEntry:(LHMEntry *)eldest
509{
510    return NO;
511}
512
513@end
514