IntIntHashMap - by Mikhail Vorontsov, originally called IntIntMap4a [1036017]

sclass IntIntHashMap is IIntIntMap {
  private static final int FREE_KEY = 0;

  public static final int NO_VALUE = 0;

  /** Keys and values */
  private int[] m_data;

  /** Do we have 'free' key in the map? */
  private boolean m_hasFreeKey;
  /** Value of 'free' key */
  private int m_freeValue;

  /** Fill factor, must be between (0 and 1) */
  private final float m_fillFactor;
  /** We will resize a map once it reaches this size */
  private int m_threshold;
  /** Current map size */
  private int m_size;

  /** Mask to calculate the original position */
  private int m_mask;
  private int m_mask2;

  *( final int size, final float fillFactor )
  {
      if ( fillFactor <= 0 || fillFactor >= 1 )
          throw new IllegalArgumentException( "FillFactor must be in (0, 1)" );
      if ( size <= 0 )
          throw new IllegalArgumentException( "Size must be positive!" );
      final int capacity = arraySize(size, fillFactor);
      m_mask = capacity - 1;
      m_mask2 = capacity*2 - 1;
      m_fillFactor = fillFactor;

      m_data = new int[capacity * 2];
      m_threshold = (int) (capacity * fillFactor);
  }

  public int get( final int key )
  {
      int ptr = ( phiMix( key ) & m_mask) << 1;

      if ( key == FREE_KEY )
          return m_hasFreeKey ? m_freeValue : NO_VALUE;

      int k = m_data[ ptr ];

      if ( k == FREE_KEY )
          return NO_VALUE;  //end of chain already
      if ( k == key ) //we check FREE prior to this call
          return m_data[ ptr + 1 ];

      while ( true )
      {
          ptr = (ptr + 2) & m_mask2; //that's next index
          k = m_data[ ptr ];
          if ( k == FREE_KEY )
              return NO_VALUE;
          if ( k == key )
              return m_data[ ptr + 1 ];
      }
  }

  public int put( final int key, final int value )
  {
      if ( key == FREE_KEY )
      {
          final int ret = m_freeValue;
          if ( !m_hasFreeKey )
              ++m_size;
          m_hasFreeKey = true;
          m_freeValue = value;
          return ret;
      }

      int ptr = ( phiMix( key ) & m_mask) << 1;
      int k = m_data[ptr];
      if ( k == FREE_KEY ) //end of chain already
      {
          m_data[ ptr ] = key;
          m_data[ ptr + 1 ] = value;
          if ( m_size >= m_threshold )
              rehash( m_data.length * 2 ); //size is set inside
          else
              ++m_size;
          return NO_VALUE;
      }
      else if ( k == key ) //we check FREE prior to this call
      {
          final int _ret = m_data[ ptr + 1 ];
          m_data[ ptr + 1 ] = value;
          return _ret;
      }

      while ( true )
      {
          ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
          k = m_data[ ptr ];
          if ( k == FREE_KEY )
          {
              m_data[ ptr ] = key;
              m_data[ ptr + 1 ] = value;
              if ( m_size >= m_threshold )
                  rehash( m_data.length * 2 ); //size is set inside
              else
                  ++m_size;
              return NO_VALUE;
          }
          else if ( k == key )
          {
              final int _ret = m_data[ ptr + 1 ];
              m_data[ ptr + 1 ] = value;
              return _ret;
          }
      }
  }

  public int remove( final int key )
  {
      if ( key == FREE_KEY )
      {
          if ( !m_hasFreeKey )
              return NO_VALUE;
          m_hasFreeKey = false;
          --m_size;
          return m_freeValue; //value is not cleaned
      }

      int ptr = ( phiMix( key ) & m_mask) << 1;
      int k = m_data[ ptr ];
      if ( k == key ) //we check FREE prior to this call
      {
          final int res = m_data[ ptr + 1 ];
          shiftKeys( ptr );
          --m_size;
          return res;
      }
      else if ( k == FREE_KEY )
          return NO_VALUE;  //end of chain already
      while ( true )
      {
          ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
          k = m_data[ ptr ];
          if ( k == key )
          {
              final int res = m_data[ ptr + 1 ];
              shiftKeys( ptr );
              --m_size;
              return res;
          }
          else if ( k == FREE_KEY )
              return NO_VALUE;
      }
  }

  private int shiftKeys(int pos)
  {
      // Shift entries with the same hash.
      int last, slot;
      int k;
      final int[] data = this.m_data;
      while ( true )
      {
          pos = ((last = pos) + 2) & m_mask2;
          while ( true )
          {
              if ((k = data[pos]) == FREE_KEY)
              {
                  data[last] = FREE_KEY;
                  return last;
              }
              slot = ( phiMix( k ) & m_mask) << 1; //calculate the starting slot for the current key
              if (last <= pos ? last >= slot || slot > pos : last >= slot && slot > pos) break;
              pos = (pos + 2) & m_mask2; //go to the next entry
          }
          data[last] = k;
          data[last + 1] = data[pos + 1];
      }
  }


  public int size()
  {
      return m_size;
  }

  private void rehash( final int newCapacity )
  {
      m_threshold = (int) (newCapacity/2 * m_fillFactor);
      m_mask = newCapacity/2 - 1;
      m_mask2 = newCapacity - 1;

      final int oldCapacity = m_data.length;
      final int[] oldData = m_data;

      m_data = new int[ newCapacity ];
      m_size = m_hasFreeKey ? 1 : 0;

      for ( int i = 0; i < oldCapacity; i += 2 ) {
          final int oldKey = oldData[ i ];
          if( oldKey != FREE_KEY )
              put( oldKey, oldData[ i + 1 ]);
      }
  }
  
  static int arraySize( final int expected, final float f ) {
      final long s = Math.max( 2, nextPowerOfTwo( (long)Math.ceil( expected / f ) ) );
      if ( s > (1 << 30) ) throw new IllegalArgumentException( "Too large (" + expected + " expected elements with load factor " + f + ")" );
      return (int)s;
    }

  static final int INT_PHI = 0x9E3779B9;

  static int phiMix( final int x ) {
    final int h = x * INT_PHI;
    return h ^ (h >> 16);
  }
}

Snippet ID:	#1036017
Snippet name:	IntIntHashMap - by Mikhail Vorontsov, originally called IntIntMap4a
Eternal ID of this version:	#1036017/1
Text MD5:	8ce9a3657d46ca0b27d0e8fb60246609
Transpilation MD5:	afb8a8ab383f2e8ef2700f711f6a1f1f
Author:	stefan
Category:	javax
Type:	JavaX fragment (include)
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2022-08-30 18:35:36
Source code size:	6260 bytes / 219 lines
Pitched / IR pitched:	No / No
Views / Downloads:	128 / 187
Referenced in:	[show references]

< > BotCompany Repo | #1036017 // IntIntHashMap - by Mikhail Vorontsov, originally called IntIntMap4a

JavaX fragment (include) [tags: use-pretranspiled]

Author comment

1	sclass IntIntHashMap is IIntIntMap {
2	private static final int FREE_KEY = 0;
3
4	public static final int NO_VALUE = 0;
5
6	/** Keys and values */
7	private int[] m_data;
8
9	/** Do we have 'free' key in the map? */
10	private boolean m_hasFreeKey;
11	/** Value of 'free' key */
12	private int m_freeValue;
13
14	/** Fill factor, must be between (0 and 1) */
15	private final float m_fillFactor;
16	/** We will resize a map once it reaches this size */
17	private int m_threshold;
18	/** Current map size */
19	private int m_size;
20
21	/** Mask to calculate the original position */
22	private int m_mask;
23	private int m_mask2;
24
25	*( final int size, final float fillFactor )
26	{
27	if ( fillFactor <= 0 \|\| fillFactor >= 1 )
28	throw new IllegalArgumentException( "FillFactor must be in (0, 1)" );
29	if ( size <= 0 )
30	throw new IllegalArgumentException( "Size must be positive!" );
31	final int capacity = arraySize(size, fillFactor);
32	m_mask = capacity - 1;
33	m_mask2 = capacity*2 - 1;
34	m_fillFactor = fillFactor;
35
36	m_data = new int[capacity * 2];
37	m_threshold = (int) (capacity * fillFactor);
38	}
39
40	public int get( final int key )
41	{
42	int ptr = ( phiMix( key ) & m_mask) << 1;
43
44	if ( key == FREE_KEY )
45	return m_hasFreeKey ? m_freeValue : NO_VALUE;
46
47	int k = m_data[ ptr ];
48
49	if ( k == FREE_KEY )
50	return NO_VALUE; //end of chain already
51	if ( k == key ) //we check FREE prior to this call
52	return m_data[ ptr + 1 ];
53
54	while ( true )
55	{
56	ptr = (ptr + 2) & m_mask2; //that's next index
57	k = m_data[ ptr ];
58	if ( k == FREE_KEY )
59	return NO_VALUE;
60	if ( k == key )
61	return m_data[ ptr + 1 ];
62	}
63	}
64
65	public int put( final int key, final int value )
66	{
67	if ( key == FREE_KEY )
68	{
69	final int ret = m_freeValue;
70	if ( !m_hasFreeKey )
71	++m_size;
72	m_hasFreeKey = true;
73	m_freeValue = value;
74	return ret;
75	}
76
77	int ptr = ( phiMix( key ) & m_mask) << 1;
78	int k = m_data[ptr];
79	if ( k == FREE_KEY ) //end of chain already
80	{
81	m_data[ ptr ] = key;
82	m_data[ ptr + 1 ] = value;
83	if ( m_size >= m_threshold )
84	rehash( m_data.length * 2 ); //size is set inside
85	else
86	++m_size;
87	return NO_VALUE;
88	}
89	else if ( k == key ) //we check FREE prior to this call
90	{
91	final int _ret = m_data[ ptr + 1 ];
92	m_data[ ptr + 1 ] = value;
93	return _ret;
94	}
95
96	while ( true )
97	{
98	ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
99	k = m_data[ ptr ];
100	if ( k == FREE_KEY )
101	{
102	m_data[ ptr ] = key;
103	m_data[ ptr + 1 ] = value;
104	if ( m_size >= m_threshold )
105	rehash( m_data.length * 2 ); //size is set inside
106	else
107	++m_size;
108	return NO_VALUE;
109	}
110	else if ( k == key )
111	{
112	final int _ret = m_data[ ptr + 1 ];
113	m_data[ ptr + 1 ] = value;
114	return _ret;
115	}
116	}
117	}
118
119	public int remove( final int key )
120	{
121	if ( key == FREE_KEY )
122	{
123	if ( !m_hasFreeKey )
124	return NO_VALUE;
125	m_hasFreeKey = false;
126	--m_size;
127	return m_freeValue; //value is not cleaned
128	}
129
130	int ptr = ( phiMix( key ) & m_mask) << 1;
131	int k = m_data[ ptr ];
132	if ( k == key ) //we check FREE prior to this call
133	{
134	final int res = m_data[ ptr + 1 ];
135	shiftKeys( ptr );
136	--m_size;
137	return res;
138	}
139	else if ( k == FREE_KEY )
140	return NO_VALUE; //end of chain already
141	while ( true )
142	{
143	ptr = ( ptr + 2 ) & m_mask2; //that's next index calculation
144	k = m_data[ ptr ];
145	if ( k == key )
146	{
147	final int res = m_data[ ptr + 1 ];
148	shiftKeys( ptr );
149	--m_size;
150	return res;
151	}
152	else if ( k == FREE_KEY )
153	return NO_VALUE;
154	}
155	}
156
157	private int shiftKeys(int pos)
158	{
159	// Shift entries with the same hash.
160	int last, slot;
161	int k;
162	final int[] data = this.m_data;
163	while ( true )
164	{
165	pos = ((last = pos) + 2) & m_mask2;
166	while ( true )
167	{
168	if ((k = data[pos]) == FREE_KEY)
169	{
170	data[last] = FREE_KEY;
171	return last;
172	}
173	slot = ( phiMix( k ) & m_mask) << 1; //calculate the starting slot for the current key
174	if (last <= pos ? last >= slot \|\| slot > pos : last >= slot && slot > pos) break;
175	pos = (pos + 2) & m_mask2; //go to the next entry
176	}
177	data[last] = k;
178	data[last + 1] = data[pos + 1];
179	}
180	}
181
182
183	public int size()
184	{
185	return m_size;
186	}
187
188	private void rehash( final int newCapacity )
189	{
190	m_threshold = (int) (newCapacity/2 * m_fillFactor);
191	m_mask = newCapacity/2 - 1;
192	m_mask2 = newCapacity - 1;
193
194	final int oldCapacity = m_data.length;
195	final int[] oldData = m_data;
196
197	m_data = new int[ newCapacity ];
198	m_size = m_hasFreeKey ? 1 : 0;
199
200	for ( int i = 0; i < oldCapacity; i += 2 ) {
201	final int oldKey = oldData[ i ];
202	if( oldKey != FREE_KEY )
203	put( oldKey, oldData[ i + 1 ]);
204	}
205	}
206
207	static int arraySize( final int expected, final float f ) {
208	final long s = Math.max( 2, nextPowerOfTwo( (long)Math.ceil( expected / f ) ) );
209	if ( s > (1 << 30) ) throw new IllegalArgumentException( "Too large (" + expected + " expected elements with load factor " + f + ")" );
210	return (int)s;
211	}
212
213	static final int INT_PHI = 0x9E3779B9;
214
215	static int phiMix( final int x ) {
216	final int h = x * INT_PHI;
217	return h ^ (h >> 16);
218	}
219	}