htmlparser/jericho/IntStringHashMap.java

// Jericho HTML Parser - Java based library for analysing and manipulating HTML
// Version 3.2
// Copyright (C) 2004-2009 Martin Jericho
// http://jericho.htmlparser.net/
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of either one of the following licences:
//
// 1. The Eclipse Public License (EPL) version 1.0,
// included in this distribution in the file licence-epl-1.0.html
// or available at http://www.eclipse.org/legal/epl-v10.html
//
// 2. The GNU Lesser General Public License (LGPL) version 2.1 or later,
// included in this distribution in the file licence-lgpl-2.1.txt
// or available at http://www.gnu.org/licenses/lgpl.txt
//
// This library is distributed on an "AS IS" basis,
// WITHOUT WARRANTY OF ANY KIND, either express or implied.
// See the individual licence texts for more details.

package net.htmlparser.jericho;

import java.util.*;

/**
 * This is an internal class used to efficiently map integers to strings, which is used in the CharacterEntityReference class.
 */
final class IntStringHashMap {
        private static final int DEFAULT_INITIAL_CAPACITY=15;
        private static final float DEFAULT_LOAD_FACTOR=0.75f;
        private transient Entry[] entries; // length must always be a power of 2.
        private transient int size;
        private int threshold;
        private float loadFactor;
        private int bitmask; // always entries.length-1

        public IntStringHashMap(int initialCapacity, final float loadFactor) {
                this.loadFactor=loadFactor;
                int capacity=1;
                while (capacity<initialCapacity) capacity<<=1;
                threshold=(int)(capacity*loadFactor);
                entries=new Entry[capacity];
                bitmask=capacity-1;
        }

        public IntStringHashMap(final int initialCapacity) {
                this(initialCapacity,DEFAULT_LOAD_FACTOR);
        }

        public IntStringHashMap() {
                this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR);
        }

        public int size() {
                return size;
        }

        public boolean isEmpty() {
                return size==0;
        }

        private int getIndex(final int key) {
                return key&bitmask; // equivalent to (key%entries.length) but more efficient.
        }

        public String get(final int key) {
                Entry entry=entries[getIndex(key)];
                while (entry!=null) {
                        if (key==entry.key) return entry.value;
                        entry=entry.next;
                }
                return null;
        }

        private Entry getEntry(final int key) {
                Entry entry=entries[getIndex(key)];
                while (entry!=null && key!=entry.key) entry=entry.next;
                return entry;
        }

        public boolean containsKey(final int key) {
                return getEntry(key)!=null;
        }

        public String put(final int key, final String value) {
                final int index=getIndex(key);
                for (Entry entry=entries[index]; entry!= null; entry=entry.next) {
                        if (key==entry.key) {
                                final String oldValue=entry.value;
                                entry.value=value;
                                return oldValue;
                        }
                }
                entries[index]=new Entry(key,value,entries[index]);
                if (size++>=threshold) increaseCapacity();
                return null;
        }

        private void increaseCapacity() {
                final int oldCapacity=entries.length;
                final Entry[] oldEntries=entries;
                entries=new Entry[oldCapacity<<1];
                bitmask=entries.length-1;
                for (Entry entry : oldEntries) {
                        while (entry!=null) {
                                final Entry next=entry.next;
                                final int index=getIndex(entry.key);
                                entry.next=entries[index];
                                entries[index]=entry;
                                entry=next;
                        }
                }
                threshold=(int)(entries.length*loadFactor);
        }

        public String remove(final int key) {
                final int index=getIndex(key);
                Entry previous=null;
                for (Entry entry=entries[index]; entry!=null; entry=(previous=entry).next) {
                        if (key==entry.key) {
                                if (previous==null)
                                        entries[index]=entry.next;
                                else
                                        previous.next=entry.next;
                                size--;
                                return entry.value;
                        }
                }
                return null;
        }

        public void clear() {
                for (int i=bitmask; i>=0; i--) entries[i]=null;
                size=0;
        }

        public boolean containsValue(final String value) {
                if (value==null) {
                        for (int i=bitmask; i>=0; i--)
                                for (Entry entry=entries[i]; entry!=null; entry=entry.next)
                                        if (entry.value==null) return true;
                } else {
                        for (int i=bitmask; i>=0; i--)
                                for (Entry entry=entries[i]; entry!=null; entry=entry.next)
                                        if (value.equals(entry.value)) return true;
                }
                return false;
        }

        private static final class Entry {
                final int key;
                String value;
                Entry next;

                public Entry(final int key, final String value, final Entry next) {
                        this.key=key;
                        this.value=value;
                        this.next=next;
                }
        }
}
1	// Jericho HTML Parser - Java based library for analysing and manipulating HTML
2	// Version 3.2
3	// Copyright (C) 2004-2009 Martin Jericho
4	// http://jericho.htmlparser.net/
5	//
6	// This library is free software; you can redistribute it and/or
7	// modify it under the terms of either one of the following licences:
8	//
9	// 1. The Eclipse Public License (EPL) version 1.0,
10	// included in this distribution in the file licence-epl-1.0.html
11	// or available at http://www.eclipse.org/legal/epl-v10.html
12	//
13	// 2. The GNU Lesser General Public License (LGPL) version 2.1 or later,
14	// included in this distribution in the file licence-lgpl-2.1.txt
15	// or available at http://www.gnu.org/licenses/lgpl.txt
16	//
17	// This library is distributed on an "AS IS" basis,
18	// WITHOUT WARRANTY OF ANY KIND, either express or implied.
19	// See the individual licence texts for more details.
20
21	package net.htmlparser.jericho;
22
23	import java.util.*;
24
25	/**
26	* This is an internal class used to efficiently map integers to strings, which is used in the CharacterEntityReference class.
27	*/
28	final class IntStringHashMap {
29	private static final int DEFAULT_INITIAL_CAPACITY=15;
30	private static final float DEFAULT_LOAD_FACTOR=0.75f;
31	private transient Entry[] entries; // length must always be a power of 2.
32	private transient int size;
33	private int threshold;
34	private float loadFactor;
35	private int bitmask; // always entries.length-1
36
37	public IntStringHashMap(int initialCapacity, final float loadFactor) {
38	this.loadFactor=loadFactor;
39	int capacity=1;
40	while (capacity<initialCapacity) capacity<<=1;
41	threshold=(int)(capacity*loadFactor);
42	entries=new Entry[capacity];
43	bitmask=capacity-1;
44	}
45
46	public IntStringHashMap(final int initialCapacity) {
47	this(initialCapacity,DEFAULT_LOAD_FACTOR);
48	}
49
50	public IntStringHashMap() {
51	this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR);
52	}
53
54	public int size() {
55	return size;
56	}
57
58	public boolean isEmpty() {
59	return size==0;
60	}
61
62	private int getIndex(final int key) {
63	return key&bitmask; // equivalent to (key%entries.length) but more efficient.
64	}
65
66	public String get(final int key) {
67	Entry entry=entries[getIndex(key)];
68	while (entry!=null) {
69	if (key==entry.key) return entry.value;
70	entry=entry.next;
71	}
72	return null;
73	}
74
75	private Entry getEntry(final int key) {
76	Entry entry=entries[getIndex(key)];
77	while (entry!=null && key!=entry.key) entry=entry.next;
78	return entry;
79	}
80
81	public boolean containsKey(final int key) {
82	return getEntry(key)!=null;
83	}
84
85	public String put(final int key, final String value) {
86	final int index=getIndex(key);
87	for (Entry entry=entries[index]; entry!= null; entry=entry.next) {
88	if (key==entry.key) {
89	final String oldValue=entry.value;
90	entry.value=value;
91	return oldValue;
92	}
93	}
94	entries[index]=new Entry(key,value,entries[index]);
95	if (size++>=threshold) increaseCapacity();
96	return null;
97	}
98
99	private void increaseCapacity() {
100	final int oldCapacity=entries.length;
101	final Entry[] oldEntries=entries;
102	entries=new Entry[oldCapacity<<1];
103	bitmask=entries.length-1;
104	for (Entry entry : oldEntries) {
105	while (entry!=null) {
106	final Entry next=entry.next;
107	final int index=getIndex(entry.key);
108	entry.next=entries[index];
109	entries[index]=entry;
110	entry=next;
111	}
112	}
113	threshold=(int)(entries.length*loadFactor);
114	}
115
116	public String remove(final int key) {
117	final int index=getIndex(key);
118	Entry previous=null;
119	for (Entry entry=entries[index]; entry!=null; entry=(previous=entry).next) {
120	if (key==entry.key) {
121	if (previous==null)
122	entries[index]=entry.next;
123	else
124	previous.next=entry.next;
125	size--;
126	return entry.value;
127	}
128	}
129	return null;
130	}
131
132	public void clear() {
133	for (int i=bitmask; i>=0; i--) entries[i]=null;
134	size=0;
135	}
136
137	public boolean containsValue(final String value) {
138	if (value==null) {
139	for (int i=bitmask; i>=0; i--)
140	for (Entry entry=entries[i]; entry!=null; entry=entry.next)
141	if (entry.value==null) return true;
142	} else {
143	for (int i=bitmask; i>=0; i--)
144	for (Entry entry=entries[i]; entry!=null; entry=entry.next)
145	if (value.equals(entry.value)) return true;
146	}
147	return false;
148	}
149
150	private static final class Entry {
151	final int key;
152	String value;
153	Entry next;
154
155	public Entry(final int key, final String value, final Entry next) {
156	this.key=key;
157	this.value=value;
158	this.next=next;
159	}
160	}
161	}