COVERAGE SUMMARY

FILE SUMMARY

Name	Executed	Routines	%	Executed	Lines	%	Unexecuted
/home/matt/eu/rds/include/std/map.e	29	29	100.00%	544	546	99.63%	2

ROUTINE SUMMARY

Routine	Executed	Lines		Unexecuted
put()	66	68	97.06%	2
calc_hash()	3	3	100.00%	0
clear()	14	14	100.00%	0
compare()	13	13	100.00%	0
convert_to_large_map()	9	9	100.00%	0
convert_to_small_map()	8	8	100.00%	0
copy()	22	22	100.00%	0
for_each()	12	12	100.00%	0
get()	21	21	100.00%	0
has()	6	6	100.00%	0
keys()	20	20	100.00%	0
load_map()	57	57	100.00%	0
map()	25	25	100.00%	0
nested_get()	9	9	100.00%	0
nested_put()	7	7	100.00%	0
new()	13	13	100.00%	0
new_extra()	4	4	100.00%	0
new_from_kvpairs()	7	7	100.00%	0
new_from_string()	2	2	100.00%	0
optimize()	17	17	100.00%	0
pairs()	23	23	100.00%	0
rehash()	30	30	100.00%	0
remove()	32	32	100.00%	0
save_map()	25	25	100.00%	0
size()	2	2	100.00%	0
statistics()	18	18	100.00%	0
threshold()	6	6	100.00%	0
type_of()	2	2	100.00%	0
values()	32	32	100.00%	0

LINE COVERAGE DETAIL

#	Executed
1		-- (c) Copyright - See License.txt
2		--
3
4		namespace map
5
6		--****
7		-- == Map (hash table)
8		--
9		-- <>
10		--
11		-- A map is a special array, often called an associative array or dictionary,
12		-- in which the index to the data can be any Euphoria object and not just
13		-- an integer. These sort of indexes are also called keys.
14		-- For example we can code things like this...
15		--
16		-- custrec = new() -- Create a new map
17		-- put(custrec, "Name", "Joe Blow")
18		-- put(custrec, "Address", "555 High Street")
19		-- put(custrec, "Phone", 555675632)
20		--
21		-- This creates three elements in the map, and they are indexed by "Name",
22		-- "Address" and "Phone", meaning that to get the data associated with those
23		-- keys we can code ...
24		--
25		-- object data = get(custrec, "Phone")
26		-- -- data now set to 555675632
27		--
28		-- Note~: Only one instance of a given key can exist in a given map, meaning
29		-- for example, we couldn't have two separate "Name" values in the above //custrec//
30		-- map.
31		--
32		-- Maps automatically grow to accommodate all the elements placed into it.
33		--
34		-- Associative arrays can be implemented in many different ways, depending
35		-- on what efficiency trade-offs have been made. This implementation allows
36		-- you to decide if you want a //small// map or a //large// map.\\
37		-- ;small map: Faster for small numbers of elements. Speed is usually proportional
38		-- to the number of elements.
39		-- ;large map: Faster for large number of elements. Speed is usually the same
40		-- regardless of how many elements are in the map. The speed is often slower than
41		-- a small map.\\
42		-- Note~: If the number of elements placed into a //small// map take it over
43		-- the initial size of the map, it is automatically converted to a //large// map.
44		--
45
46		include std/get.e
47		include std/primes.e
48		include std/convert.e
49		include std/math.e
50		include std/stats.e as stats
51		include std/text.e
52		include std/search.e
53		include std/types.e
54		include std/pretty.e
55		include std/eumem.e
56		include std/error.e
57		include std/sort.e
58		include std/serialize.e
59		include std/datetime.e
60		include std/io.e
61
62		enum
63	20	TYPE_TAG, -- ==> 'tag' for map type
64	20	ELEMENT_COUNT, -- ==> elementCount
65	20	IN_USE, -- ==> count of non-empty buckets
66	20	MAP_TYPE, -- ==> Either SMALLMAP or LARGEMAP
67	20	KEY_BUCKETS, -- ==> bucket[] --> bucket = {key[], value[]}
68	20	VALUE_BUCKETS, -- ==> bucket[] --> bucket = {key[], value[]}
69	20	KEY_LIST = 5, -- ==> Small map keys
70	20	VALUE_LIST, -- ==> Small map values
71	20	FREE_LIST -- ==> Small map freespace
72
73	20	constant type_is_map = "Eu:StdMap"
74
75		--****
76		-- Signature:
77		-- function hash(object source, atom algo)
78		--
79		-- Description:
80		-- Calculates a hash value from //key// using the algorithm //algo//
81		--
82		-- Parameters:
83		-- # ##source## : Any Euphoria object
84		-- # ##algo## : A code indicating which algorithm to use.
85		-- ** -5 uses Hsieh. Fastest and good dispersion
86		-- ** -4 uses Fletcher. Very fast and good dispersion
87		-- ** -3 uses Adler. Very fast and reasonable dispersion, especially for small strings
88		-- ** -2 uses MD5 (not implemented yet) Slower but very good dispersion.
89		-- Suitable for signatures.
90		-- ** -1 uses SHA256 (not implemented yet) Slow but excellent dispersion.
91		-- Suitable for signatures. More secure than MD5.
92		-- ** 0 and above (integers and decimals) and non-integers less than zero use
93		-- the cyclic variant (hash = hash * algo + c).
94		-- This is a fast and good to excellent
95		-- dispersion depending on the value of //algo//. Decimals give better dispersion but are
96		-- slightly slower.
97		--
98		-- Returns:
99		-- An integer,
100		-- Except for the MD5 and SHA256 algorithms, this is a 32-bit integer.\\
101		-- A sequence,
102		-- MD5 returns a 4-element sequence of integers\\
103		-- SHA256 returns a 8-element sequence of integers.
104		--
105		-- Comments:
106		-- * For //algo// values from zero to less than 1, that actual value used is (algo + 69096).
107		--
108		-- Example 1:
109		--
110		-- x = hash("The quick brown fox jumps over the lazy dog", 0)
111		-- -- x is 242399616
112		-- x = hash("The quick brown fox jumps over the lazy dog", 99.94)
113		-- -- x is 723158
114		-- x = hash("The quick brown fox jumps over the lazy dog", -99.94)
115		-- -- x is 4175585990
116		-- x = hash("The quick brown fox jumps over the lazy dog", -4)
117		-- -- x is 467406810
118		--
119
120		--****
121		-- === Hashing Algorithms
122
123		public enum
124	20	HSIEH32 = -5,
125	20	FLETCHER32,
126	20	ADLER32,
127	20	MD5,
128	20	SHA256
129
130		--****
131		-- === Operation codes for put
132
133		public enum
134	20	PUT,
135	20	ADD,
136	20	SUBTRACT,
137	20	MULTIPLY,
138	20	DIVIDE,
139	20	APPEND,
140	20	CONCAT,
141	20	LEAVE
142
143	20	constant INIT_OPERATIONS = {PUT, APPEND, CONCAT, ADD, SUBTRACT, LEAVE}
144		--****
145		-- === Types of Maps
146
147	20	public constant SMALLMAP = 's'
148	20	public constant LARGEMAP = 'L'
149
150	20	integer threshold_size = 50
151
152		-- This is a improbable value used to initialize a small map's keys list.
153	20	constant init_small_map_key = -75960.358941
154
155		--****
156		-- === Types
157		--
158
159		--**
160		-- Defines the datatype 'map'
161		--
162		-- Comments:
163		-- Used when declaring a map variable.
164		--
165		-- Example:
166		--
167		-- map SymbolTable = new() -- Create a new map to hold the symbol table.
168		--
169
170	5341	public type map(object obj_p)
171		-- Must be a valid EuMem pointer.
172	5341	if not valid(obj_p, "") then return 0 end if
173
174		-- Large maps have six data elements:
175		-- (1) Data type magic value
176		-- (2) Count of elements
177		-- (3) Number of slots being used
178		-- (4) The map type
179		-- (5) Key Buckets
180		-- (6) Value Buckets
181		-- A bucket contains one or more lists of items.
182
183		-- Small maps have seven data elements:
184		-- (1) Data type magic value
185		-- (2) Count of elements
186		-- (3) Number of slots being used
187		-- (4) The map type
188		-- (5) Sequence of keys
189		-- (6) Sequence of values, in the same order as the keys.
190		-- (7) Sequence. A Free space map.
191	5333	object m_
192
193	5333	m_ = ram_space[obj_p]
194	5333	if not sequence(m_) then return 0 end if
195	5331	if length(m_) < 6 then return 0 end if
196	5331	if length(m_) > 7 then return 0 end if
197	5331	if not equal(m_[TYPE_TAG], type_is_map) then return 0 end if
198	5331	if not integer(m_[ELEMENT_COUNT]) then return 0 end if
199	5331	if m_[ELEMENT_COUNT] < 0 then return 0 end if
200	5331	if not integer(m_[IN_USE]) then return 0 end if
201	5331	if m_[IN_USE] < 0 then return 0 end if
202	5331	if equal(m_[MAP_TYPE],SMALLMAP) then
203	368	if atom(m_[KEY_LIST]) then return 0 end if
204	368	if atom(m_[VALUE_LIST]) then return 0 end if
205	368	if atom(m_[FREE_LIST]) then return 0 end if
206	368	if length(m_[KEY_LIST]) = 0 then return 0 end if
207	368	if length(m_[KEY_LIST]) != length(m_[VALUE_LIST]) then return 0 end if
208	368	if length(m_[KEY_LIST]) != length(m_[FREE_LIST]) then return 0 end if
209	4963	elsif equal(m_[MAP_TYPE],LARGEMAP) then
210	4962	if atom(m_[KEY_BUCKETS]) then return 0 end if
211	4962	if atom(m_[VALUE_BUCKETS]) then return 0 end if
212	4962	if length(m_[KEY_BUCKETS]) != length(m_[VALUE_BUCKETS]) then return 0 end if
213		else
214	1	return 0
215		end if
216	5330	return 1
217		end type
218
219	20	constant maxInt = #3FFFFFFF,
220	20	maxAutoSize = floor( (maxInt - 1 ) / 3.5 )
221
222		--****
223		-- === Routines
224		--
225
226		--**
227		-- Calculate a Hashing value from the supplied data.
228		--
229		-- Parameters:
230		-- # ##pData## : The data for which you want a hash value calculated.
231		-- # ##max_hash_p## : The returned value will be no larger than this value.
232		--
233		-- Returns:
234		-- An integer, the value of which depends only on the supplied data.
235		--
236		-- Comments:
237		-- This is used whenever you need a single number to represent the data you supply.
238		-- It can calculate the number based on all the data you give it, which can be
239		-- an atom or sequence of any value.
240		--
241		-- Example 1:
242		--
243		-- integer h1
244		-- -- calculate a hash value and ensure it will be a value from 1 to 4097.
245		-- h1 = calc_hash( symbol_name, 4097 )
246		--
247
248	44144	public function calc_hash(object key_p, integer max_hash_p)
249		atom ret_
250
251	44144	ret_ = hash(key_p, -4) --HSIEH32)
252	44144	return remainder(ret_, max_hash_p) + 1 -- 1-based
253
254		end function
255
256		--**
257		-- Gets or Sets the threshold value that determines at what point a small map
258		-- converts into a large map structure. Initially this has been set to 50,
259		-- meaning that maps up to 50 elements use the //small map// structure.
260		--
261		-- Parameters:
262		-- # ##new_value_p## : If this is greater than zero then it sets the threshold
263		-- value.
264		--
265		-- Returns:
266		-- An integer, the current value (when ##new_value_p## is less than 1) or the
267		-- old value prior to setting it to ##new_value_p##.
268		--
269	16	public function threshold(integer new_value_p = 0)
270
271	16	if new_value_p < 1 then
272	13	return threshold_size
273		end if
274
275	3	integer old_value_ = threshold_size
276	3	threshold_size = new_value_p
277	3	return old_value_
278
279		end function
280
281		--**
282		-- Determines the type of the map.
283		--
284		-- Parameters:
285		-- # ##m## : A map
286		--
287		-- Returns:
288		-- An integer, Either //SMALLMAP// or //LARGEMAP//
289		--
290	8	public function type_of(map the_map_p)
291	8	return ram_space[the_map_p][MAP_TYPE]
292		end function
293
294		--**
295		-- Changes the width, i.e. the number of buckets, of a map. Only effects
296		-- //large// maps.
297		--
298		-- Parameters:
299		-- # ##m## : the map to resize
300		-- # ##requested_bucket_size_p## : a lower limit for the new size.
301		--
302		-- Returns:
303		-- A map, with the same data in, but more evenly dispatched and hence faster to use.
304		--
305		-- Comment:
306		-- If ##requested_bucket_size_p## is not greater than zero, a new width is automatically derived from the current one.
307		--
308		-- See Also:
309		-- [[:statistics]], [[:optimize]]
310
311
312	18	public procedure rehash(map the_map_p, integer requested_bucket_size_p = 0)
313		integer size_
314		integer index_2_
315		sequence old_key_buckets_
316		sequence old_val_buckets_
317		sequence new_key_buckets_
318		sequence new_val_buckets_
319		object key_
320		object value_
321		sequence temp_map_
322
323	18	if ram_space[the_map_p][MAP_TYPE] = SMALLMAP then
324	1	return -- small maps are not hashed.
325		end if
326
327	17	if requested_bucket_size_p <= 0 then
328		-- grow bucket size_
329	1	size_ = floor(length(ram_space[the_map_p][KEY_BUCKETS]) * 3.5) + 1
330		else
331	16	size_ = requested_bucket_size_p
332		end if
333
334	17	size_ = next_prime(size_, -size_, 2) -- Allow up to 2 seconds to calc next prime.
335	17	if size_ < 0 then
336	1	return -- don't do anything. New size would take too long.
337		end if
338	16	old_key_buckets_ = ram_space[the_map_p][KEY_BUCKETS]
339	16	old_val_buckets_ = ram_space[the_map_p][VALUE_BUCKETS]
340	16	new_key_buckets_ = repeat({}, size_)
341	16	new_val_buckets_ = repeat({}, size_)
342	16	temp_map_ = {type_is_map, 0, 0, LARGEMAP}
343
344	16	for index = 1 to length(old_key_buckets_) do
345	48008	for entry_idx = 1 to length(old_key_buckets_[index]) do
346	39374	key_ = old_key_buckets_[index][entry_idx]
347	39374	value_ = old_val_buckets_[index][entry_idx]
348	39374	index_2_ = calc_hash(key_, size_)
349	39374	new_key_buckets_[index_2_] = append(new_key_buckets_[index_2_], key_)
350	39374	new_val_buckets_[index_2_] = append(new_val_buckets_[index_2_], value_)
351	39374	temp_map_[ELEMENT_COUNT] += 1
352	39374	if length(new_key_buckets_[index_2_]) = 1 then
353	20627	temp_map_[IN_USE] += 1
354		end if
355	39374	end for
356	48008	end for
357
358	16	temp_map_ = append(temp_map_, new_key_buckets_)
359	16	temp_map_ = append(temp_map_, new_val_buckets_)
360
361	16	ram_space[the_map_p] = temp_map_
362	16	end procedure
363
364		--**
365		-- Create a new map data structure
366		--
367		-- Parameters:
368		-- # ##initial_size_p## : An estimate of how many initial elements will be stored
369		-- in the map. If this value is less than the [[:threshold]] value, the map
370		-- will initially be a //small// map otherwise it will be a //large// map.
371		--
372		-- Returns:
373		-- An empty map.
374		--
375		-- Comments:
376		-- A new object of type map is created. The resources allocated for the map will
377		-- be automatically cleaned up if the reference count of the returned value drops
378		-- to zero, or if passed in a call to [[:delete]].
379		--
380		-- Example 1:
381		--
382		-- map m = new() -- m is now an empty map
383		-- map x = new(threshold()) -- Forces a small map to be initialized
384		-- x = new() -- the resources for the map previously stored in x are released automatically
385		-- delete( m ) -- the resources for the map are released
386		--
387
388	80	public function new(integer initial_size_p = 690)
389		integer buckets_
390		sequence new_map_
391		atom temp_map_
392
393	80	if initial_size_p < 3 then
394	1	initial_size_p = 3
395		end if
396	80	if initial_size_p > threshold_size then
397		-- Return a large map
398	57	buckets_ = floor(initial_size_p / 30)
399	57	if buckets_ < 23 then
400	7	buckets_ = 23
401		else
402	50	buckets_ = next_prime(buckets_)
403		end if
404
405
406	57	new_map_ = {type_is_map, 0, 0, LARGEMAP, repeat({}, buckets_), repeat({}, buckets_)}
407		else
408		-- Return a small map
409	23	new_map_ = {type_is_map, 0,0, SMALLMAP, repeat(init_small_map_key, initial_size_p), repeat(0, initial_size_p), repeat(0, initial_size_p)}
410		end if
411	80	temp_map_ = malloc()
412	80	ram_space[temp_map_] = new_map_
413
414	80	return temp_map_
415		end function
416
417		--**
418		-- Returns either the supplied map or a new map.
419		--
420		-- Parameters:
421		-- # ##the_map_p## : An object, that could be an existing map
422		-- # ##initial_size_p## : An estimate of how many initial elements will be stored
423		-- in a new map.
424		--
425		-- Returns:
426		-- A map,
427		-- If ##m## is an existing map then it is returned otherwise this
428		-- returns a new empty map.
429		--
430		-- Comments:
431		-- This is used to return a new map if the supplied variable isn't already
432		-- a map.
433		--
434		-- Example 1:
435		--
436		-- map m = new_extra( foo() ) -- If foo() returns a map it is used, otherwise
437		-- -- a new map is created.
438		--
439
440	8	public function new_extra(object the_map_p, integer initial_size_p = 690)
441	8	if map(the_map_p) then
442	2	return the_map_p
443		else
444	6	return new(initial_size_p)
445		end if
446		end function
447
448
449		--**
450		-- Compares two maps to test equality.
451		--
452		-- Parameters:
453		-- # ##map_1_p## : A map
454		-- # ##map_2_p## : A map
455		-- # ##scope_p## : An integer that specifies what to compare.
456		-- ** 'k' or 'K' to only compare keys.
457		-- ** 'v' or 'V' to only compare values.
458		-- ** 'd' or 'D' to compare both keys and values. This is the default.
459		--
460		-- Returns:
461		-- An integer,
462		-- * -1 if they are not equal.
463		-- * 0 if they are literally the same map.
464		-- * 1 if they contain the same keys and/or values.
465		--
466		-- Example 1:
467		--
468		-- map map_1_p = foo()
469		-- map map_2_p = bar()
470		-- if compare(map_1_p, map_2_p, 'k') >= 0 then
471		-- ... -- two maps have the same keys
472		--
473
474	18	public function compare(map map_1_p, map map_2_p, integer scope_p = 'd')
475		sequence data_set_1_
476		sequence data_set_2_
477
478	18	if map_1_p = map_2_p then
479	2	return 0
480		end if
481
482	16	switch scope_p do
483		case 'v', 'V' then
484	3	data_set_1_ = sort(values(map_1_p))
485	3	data_set_2_ = sort(values(map_2_p))
486
487		case 'k', 'K' then
488	3	data_set_1_ = keys(map_1_p, 1)
489	3	data_set_2_ = keys(map_2_p, 1)
490
491		case else
492	10	data_set_1_ = pairs(map_1_p, 1)
493	10	data_set_2_ = pairs(map_2_p, 1)
494
495		end switch
496
497	16	if equal(data_set_1_, data_set_2_) then
498	12	return 1
499		end if
500
501	4	return -1
502
503		end function
504
505		--**
506		-- Check whether map has a given key.
507		--
508		-- Parameters:
509		-- # ##the_map_p## : the map to inspect
510		-- # ##the_key_p## : an object to be looked up
511		--
512		-- Returns:
513		-- An integer, 0 if not present, 1 if present.
514		--
515		-- Example 1:
516		--
517		-- map the_map_p
518		-- the_map_p = new()
519		-- put(the_map_p, "name", "John")
520		-- ? has(the_map_p, "name") -- 1
521		-- ? has(the_map_p, "age") -- 0
522		--
523		--See Also:
524		-- [[:get]]
525	17	public function has(map the_map_p, object the_key_p)
526		integer index_
527		integer pos_
528
529	17	if ram_space[the_map_p][MAP_TYPE] = LARGEMAP then
530	12	index_ = calc_hash(the_key_p, length(ram_space[the_map_p][KEY_BUCKETS]))
531	12	pos_ = find(the_key_p, ram_space[the_map_p][KEY_BUCKETS][index_])
532		else
533	5	pos_ = find(the_key_p, ram_space[the_map_p][KEY_LIST])
534		end if
535	17	return (pos_ != 0)
536
537		end function
538
539		--**
540		-- Retrieves the value associated to a key in a map.
541		--
542		-- Parameters:
543		-- # ##the_map_p## : the map to inspect
544		-- # ##the_key_p## : an object, the the_key_p being looked tp
545		-- # ##default_value_p## : an object, a default value returned if ##the_key_p## not found.
546		-- The default is 0.
547		--
548		-- Returns:
549		-- An object, the value that corresponds to ##the_key_p## in ##the_map_p##.
550		-- If ##the_key_p## is not in ##the_map_p##, ##default_value_p## is returned instead.
551		--
552		-- Example 1:
553		--
554		-- map ages
555		-- ages = new()
556		-- put(ages, "Andy", 12)
557		-- put(ages, "Budi", 13)
558		--
559		-- integer age
560		-- age = get(ages, "Budi", -1)
561		-- if age = -1 then
562		-- puts(1, "Age unknown")
563		-- else
564		-- printf(1, "The age is %d", age)
565		-- end if
566		--
567		-- See Also:
568		-- [[:has]]
569
570	209	public function get(map the_map_p, object the_key_p, object default_value_p = 0)
571		integer bucket_
572		integer pos_
573		integer from_
574
575	209	if ram_space[the_map_p][MAP_TYPE] = LARGEMAP then
576	155	bucket_ = calc_hash(the_key_p, length(ram_space[the_map_p][KEY_BUCKETS]))
577	155	pos_ = find(the_key_p, ram_space[the_map_p][KEY_BUCKETS][bucket_])
578	155	if pos_ > 0 then
579	107	return ram_space[the_map_p][VALUE_BUCKETS][bucket_][pos_]
580		end if
581	48	return default_value_p
582		else
583	54	if equal(the_key_p, init_small_map_key) then
584	4	from_ = 1
585	4	while from_ > 0 do
586	102	pos_ = find_from(the_key_p, ram_space[the_map_p][KEY_LIST], from_)
587	102	if pos_ then
588	100	if ram_space[the_map_p][FREE_LIST][pos_] = 1 then
589	2	return ram_space[the_map_p][VALUE_LIST][pos_]
590		end if
591		else
592	2	return default_value_p
593		end if
594	98	from_ = pos_ + 1
595	98	end while
596		else
597	50	pos_ = find(the_key_p, ram_space[the_map_p][KEY_LIST])
598	50	if pos_ then
599	42	return ram_space[the_map_p][VALUE_LIST][pos_]
600		end if
601		end if
602		end if
603	8	return default_value_p
604		end function
605
606		--**
607		-- Returns the value that corresponds to the object ##the_keys_p## in the nested map the_map_p. ##the_keys_p## is a
608		-- sequence of keys. If any key is not in the map, the object default_value_p is returned instead.
609	5	public function nested_get( map the_map_p, sequence the_keys_p, object default_value_p = 0)
610	5	for i = 1 to length( the_keys_p ) - 1 do
611	7	object val_ = get( the_map_p, the_keys_p[1], 0 )
612
613	7	if not map( val_ ) then
614		-- not a map
615	1	return default_value_p
616		else
617	6	the_map_p = val_
618	6	the_keys_p = the_keys_p[2..$]
619		end if
620	6	end for
621	4	return get( the_map_p, the_keys_p[1], default_value_p )
622		end function
623
624		--**
625		-- Adds or updates an entry on a map.
626		--
627		-- Parameters:
628		-- # ##the_map_p## : the map where an entry is being added or updated
629		-- # ##the_key_p## : an object, the the_key_p to look up
630		-- # ##the_value_p## : an object, the value to add, or to use for updating.
631		-- # ##operation## : an integer, indicating what is to be done with ##the_value_p##. Defaults to PUT.
632		-- # ##trigger_p## : an integer. Default is 100. See Comments for details.
633		--
634		-- Returns:
635		-- The updated map.
636		--
637		-- Comments:
638		-- * The operation parameter can be used to modify the existing value. Valid operations are:
639		--
640		-- ** ##PUT## ~-- This is the default, and it replaces any value in there already
641		-- ** ##ADD## ~-- Equivalent to using the += operator
642		-- ** ##SUBTRACT## ~-- Equivalent to using the -= operator
643		-- ** ##MULTIPLY## ~-- Equivalent to using the *= operator
644		-- ** ##DIVIDE## ~-- Equivalent to using the /= operator
645		-- ** ##APPEND## ~-- Appends the value to the existing data
646		-- ** ##CONCAT## ~-- Equivalent to using the &= operator
647		-- ** ##LEAVE## ~-- If it already exists, the current value is left unchanged
648		-- otherwise the new value is added to the map.
649		--
650		-- * The //trigger// parameter is used when you need to keep the average
651		-- number of keys in a hash bucket to a specific maximum. The //trigger//
652		-- value is the maximum allowed. Each time a //put// operation increases
653		-- the hash table's average bucket size to be more than the //trigger// value
654		-- the table is expanded by a factor of 3.5 and the keys are rehashed into the
655		-- enlarged table. This can be a time intensive action so set the value
656		-- to one that is appropriate to your application.
657		-- ** By keeping the average bucket size to a certain maximum, it can
658		-- speed up lookup times.
659		-- ** If you set the //trigger// to zero, it will not check to see if
660		-- the table needs reorganizing. You might do this if you created the original
661		-- bucket size to an optimal value. See [[:new]] on how to do this.
662		--
663		-- Example 1:
664		--
665		-- map ages
666		-- ages = new()
667		-- put(ages, "Andy", 12)
668		-- put(ages, "Budi", 13)
669		-- put(ages, "Budi", 14)
670		--
671		-- -- ages now contains 2 entries: "Andy" => 12, "Budi" => 14
672		--
673		--
674		-- See Also:
675		-- [[:remove]], [[:has]], [[:nested_put]]
676
677	4788	public procedure put(map the_map_p, object the_key_p, object the_value_p, integer operation_p = PUT, integer trigger_p = 100 )
678		integer index_
679		integer bucket_
680		atom average_length_
681		integer from_
682
683	4788	if ram_space[the_map_p][MAP_TYPE] = LARGEMAP then
684	4599	bucket_ = calc_hash(the_key_p, length(ram_space[the_map_p][KEY_BUCKETS]))
685	4599	index_ = find(the_key_p, ram_space[the_map_p][KEY_BUCKETS][bucket_])
686	4599	if index_ > 0 then
687		-- The the_value_p already exists.
688	26	switch operation_p do
689		case PUT then
690	4	ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_] = the_value_p
691
692		case ADD then
693	2	ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_] += the_value_p
694
695		case SUBTRACT then
696	1	ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_] -= the_value_p
697
698		case MULTIPLY then
699	1	ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_] *= the_value_p
700
701		case DIVIDE then
702	1	ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_] /= the_value_p
703
704		case APPEND then
705	14	ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_] = append( ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_], the_value_p )
706
707		case CONCAT then
708	1	ram_space[the_map_p][VALUE_BUCKETS][bucket_][index_] &= the_value_p
709
710		case LEAVE then
711		-- Do nothing
712	1	operation_p = operation_p
713
714		case else
715	1	crash("Unknown operation given to map.e:put()")
716
717		end switch
718	25	return
719		end if
720
721	4573	if not eu:find(operation_p, INIT_OPERATIONS) then
722	1	crash("Inappropriate initial operation given to map.e:put()")
723		end if
724	4572	if operation_p = LEAVE then
725	1	return
726		end if
727
728
729		-- write new entry
730	4571	if operation_p = APPEND then
731		-- If appending, then the user wants the the_value_p to be an element, not the entire thing
732	2	the_value_p = { the_value_p }
733		end if
734
735	4571	ram_space[the_map_p][IN_USE] += (length(ram_space[the_map_p][KEY_BUCKETS][bucket_]) = 0)
736	4571	ram_space[the_map_p][ELEMENT_COUNT] += 1 -- elementCount
737	4571	ram_space[the_map_p][KEY_BUCKETS][bucket_] = append(ram_space[the_map_p][KEY_BUCKETS][bucket_], the_key_p)
738	4571	ram_space[the_map_p][VALUE_BUCKETS][bucket_] = append(ram_space[the_map_p][VALUE_BUCKETS][bucket_], the_value_p)
739
740	4571	if trigger_p > 0 then
741	4315	average_length_ = ram_space[the_map_p][ELEMENT_COUNT] / ram_space[the_map_p][IN_USE]
742	4315	if (average_length_ >= trigger_p) then
743	1	rehash(the_map_p)
744		end if
745		end if
746
747	4571	return
748		else -- Small Map
749		-- First, check to see if the key is already in the map.
750	189	if equal(the_key_p, init_small_map_key) then
751		-- Special case when the key happens to be the magic init value.
752		-- We have to double check the free list whenever we have a hit on the key.
753	2	from_ = 1
754	2	while index_ > 0 with entry do
755	51	if ram_space[the_map_p][FREE_LIST][index_] = 1 then
756	1	exit
757		end if
758	50	from_ = index_ + 1
759		entry
760	52	index_ = find_from(the_key_p, ram_space[the_map_p][KEY_LIST], from_)
761	52	end while
762		else
763	187	index_ = find(the_key_p, ram_space[the_map_p][KEY_LIST])
764		end if
765
766		-- Did we find the key?
767	189	if index_ = 0 then
768
769	166	if not eu:find(operation_p, INIT_OPERATIONS) then
770	1	crash("Inappropriate initial operation given to map.e:put()")
771		end if
772		-- No, so add it.
773	165	index_ = find(0, ram_space[the_map_p][FREE_LIST])
774	165	if index_ = 0 then
775		-- No room left, so now it becomes a large map.
776	1	convert_to_large_map(the_map_p)
777	1	put(the_map_p, the_key_p, the_value_p, operation_p, trigger_p)
778	1	return
779		end if
780
781	164	ram_space[the_map_p][KEY_LIST][index_] = the_key_p
782	164	ram_space[the_map_p][FREE_LIST][index_] = 1
783	164	ram_space[the_map_p][IN_USE] += 1
784	164	ram_space[the_map_p][ELEMENT_COUNT] += 1
785
786	164	if operation_p = APPEND then
787	1	the_value_p = { the_value_p }
788		end if
789	164	if operation_p != LEAVE then
790	164	operation_p = PUT -- Initially, nearly everything is a PUT.
791		end if
792		end if
793
794	187	switch operation_p do
795		case PUT then
796	170	ram_space[the_map_p][VALUE_LIST][index_] = the_value_p
797
798		case ADD then
799	1	ram_space[the_map_p][VALUE_LIST][index_] += the_value_p
800
801		case SUBTRACT then
802	1	ram_space[the_map_p][VALUE_LIST][index_] -= the_value_p
803
804		case MULTIPLY then
805	1	ram_space[the_map_p][VALUE_LIST][index_] *= the_value_p
806
807		case DIVIDE then
808	1	ram_space[the_map_p][VALUE_LIST][index_] /= the_value_p
809
810		case APPEND then
811	11	ram_space[the_map_p][VALUE_LIST][index_] = append( ram_space[the_map_p][VALUE_LIST][index_], the_value_p )
812
813		case CONCAT then
814	1	ram_space[the_map_p][VALUE_LIST][index_] &= the_value_p
815
816		case LEAVE then
817		-- do nothing
818	0	case else
819	1	crash("Unknown operation given to map.e:put()")
820
821		end switch
822	186	return
823
824		end if
825	0	end procedure
826
827
828		--**
829		-- Adds or updates an entry on a map.
830		--
831		-- Parameters:
832		-- # ##the_map_p## : the map where an entry is being added or updated
833		-- # ##the_keys_p## : a sequence of keys for the nested maps
834		-- # ##the_value_p## : an object, the value to add, or to use for updating.
835		-- # ##operation_p## : an integer, indicating what is to be done with ##value##. Defaults to PUT.
836		-- # ##trigger_p## : an integer. Default is 51. See Comments for details.
837		--
838		-- Valid operations are:
839		--
840		-- * ##PUT## ~-- This is the default, and it replaces any value in there already
841		-- * ##ADD## ~-- Equivalent to using the += operator
842		-- * ##SUBTRACT## ~-- Equivalent to using the -= operator
843		-- * ##MULTIPLY## ~-- Equivalent to using the *= operator
844		-- * ##DIVIDE## ~-- Equivalent to using the /= operator
845		-- * ##APPEND## ~-- Appends the value to the existing data
846		-- * ##CONCAT## ~-- Equivalent to using the &= operator
847		--
848		-- Returns:
849		-- The modified map.
850		--
851		-- Comments:
852		-- * If existing entry with the same key is already in the map, the value of the entry is updated.
853		-- * The //trigger// parameter is used when you need to keep the average
854		-- number of keys in a hash bucket to a specific maximum. The //trigger//
855		-- value is the maximum allowed. Each time a //put// operation increases
856		-- the hash table's average bucket size to be more than the //trigger// value
857		-- the table is expanded by a factor 3.5 and the keys are rehashed into the
858		-- enlarged table. This can be a time intensive action so set the value
859		-- to one that is appropriate to your application.
860		-- ** By keeping the average bucket size to a certain maximum, it can
861		-- speed up lookup times.
862		-- ** If you set the //trigger// to zero, it will not check to see if
863		-- the table needs reorganizing. You might do this if you created the original
864		-- bucket size to an optimal value. See [[:new]] on how to do this.
865		--
866		-- Example 1:
867		--
868		-- map city_population
869		-- city_population = new()
870		-- nested_put(city_population, {"United States", "California", "Los Angeles"}, 3819951 )
871		-- nested_put(city_population, {"Canada", "Ontario", "Toronto"}, 2503281 )
872		--
873		--
874		-- See also: [[:put]]
875	9	public procedure nested_put( map the_map_p, sequence the_keys_p, object the_value_p, integer operation_p = PUT, integer trigger_p = 51 )
876		atom temp_map_
877
878	9	if length( the_keys_p ) = 1 then
879	3	put( the_map_p, the_keys_p[1], the_value_p, operation_p, trigger_p )
880		else
881	6	temp_map_ = new_extra( get( the_map_p, the_keys_p[1] ) )
882	6	nested_put( temp_map_, the_keys_p[2..$], the_value_p, operation_p, trigger_p )
883	6	put( the_map_p, the_keys_p[1], temp_map_, PUT, trigger_p )
884		end if
885	9	end procedure
886
887		--**
888		-- Remove an entry with given key from a map.
889		--
890		-- Parameters:
891		-- # ##the_map_p## : the map to operate on
892		-- # ##key## : an object, the key to remove.
893		--
894		-- Returns:
895		-- The modified map.
896		--
897		-- Comments:
898		-- * If ##key## is not on ##the_map_p##, the ##the_map_p## is returned unchanged.
899		-- * If you need to remove all entries, see [[:clear]]
900		--
901		-- Example 1:
902		--
903		-- map the_map_p
904		-- the_map_p = new()
905		-- put(the_map_p, "Amy", 66.9)
906		-- remove(the_map_p, "Amy")
907		-- -- the_map_p is now an empty map again
908		--
909		--
910		-- See Also:
911		-- [[:clear]], [[:has]]
912
913	6	public procedure remove(map the_map_p, object the_key_p)
914		integer index_
915		integer bucket_
916		sequence temp_map_
917		integer from_
918
919
920	6	temp_map_ = ram_space[the_map_p]
921	6	if temp_map_[MAP_TYPE] = LARGEMAP then
922	4	bucket_ = calc_hash(the_key_p, length(temp_map_[KEY_BUCKETS]))
923
924	4	index_ = find(the_key_p, temp_map_[KEY_BUCKETS][bucket_])
925	4	if index_ != 0 then
926	4	temp_map_[ELEMENT_COUNT] -= 1
927	4	if length(temp_map_[KEY_BUCKETS][bucket_]) = 1 then
928	3	temp_map_[IN_USE] -= 1
929	3	temp_map_[KEY_BUCKETS][bucket_] = {}
930	3	temp_map_[VALUE_BUCKETS][bucket_] = {}
931		else
932	1	temp_map_[VALUE_BUCKETS][bucket_] = temp_map_[VALUE_BUCKETS][bucket_][1 .. index_-1] & temp_map_[VALUE_BUCKETS][bucket_][index_+1 .. $]
933	1	temp_map_[KEY_BUCKETS][bucket_] = temp_map_[KEY_BUCKETS][bucket_][1 .. index_-1] & temp_map_[KEY_BUCKETS][bucket_][index_+1 .. $]
934		end if
935
936	4	if temp_map_[ELEMENT_COUNT] < floor(51 * threshold_size / 100) then
937	3	ram_space[the_map_p] = temp_map_
938	3	convert_to_small_map(the_map_p)
939	3	return
940		end if
941		end if
942		else
943	2	from_ = 1
944	2	while from_ > 0 do
945	3	index_ = find_from(the_key_p, temp_map_[KEY_LIST], from_)
946	3	if index_ then
947	1	if temp_map_[FREE_LIST][index_] = 1 then
948	1	temp_map_[FREE_LIST][index_] = 0
949	1	temp_map_[KEY_LIST][index_] = init_small_map_key
950	1	temp_map_[VALUE_LIST][index_] = 0
951	1	temp_map_[IN_USE] -= 1
952	1	temp_map_[ELEMENT_COUNT] -= 1
953		end if
954		else
955	2	exit
956		end if
957	1	from_ = index_ + 1
958	1	end while
959		end if
960	3	ram_space[the_map_p] = temp_map_
961	3	end procedure
962
963		--**
964		-- Remove all entries in a map.
965		--
966		-- Parameters:
967		-- # ##the_map_p## : the map to operate on
968		--
969		-- Comments:
970		-- * This is much faster than removing each entry individually.
971		-- * If you need to remove just one entry, see [[:remove]]
972		--
973		-- Example 1:
974		--
975		-- map the_map_p
976		-- the_map_p = new()
977		-- put(the_map_p, "Amy", 66.9)
978		-- put(the_map_p, "Betty", 67.8)
979		-- put(the_map_p, "Claire", 64.1)
980		-- ...
981		-- clear(the_map_p)
982		-- -- the_map_p is now an empty map again
983		--
984		--
985		-- See Also:
986		-- [[:remove]], [[:has]]
987
988	10	public procedure clear(map the_map_p)
989		sequence temp_map_
990
991	10	temp_map_ = ram_space[the_map_p]
992	10	if temp_map_[MAP_TYPE] = LARGEMAP then
993	6	temp_map_[ELEMENT_COUNT] = 0
994	6	temp_map_[IN_USE] = 0
995	6	temp_map_[KEY_BUCKETS] = repeat({}, length(temp_map_[KEY_BUCKETS]))
996	6	temp_map_[VALUE_BUCKETS] = repeat({}, length(temp_map_[VALUE_BUCKETS]))
997		else
998	4	temp_map_[ELEMENT_COUNT] = 0
999	4	temp_map_[IN_USE] = 0
1000	4	temp_map_[KEY_LIST] = repeat(init_small_map_key, length(temp_map_[KEY_LIST]))
1001	4	temp_map_[VALUE_LIST] = repeat(0, length(temp_map_[VALUE_LIST]))
1002	4	temp_map_[FREE_LIST] = repeat(0, length(temp_map_[FREE_LIST]))
1003		end if
1004	10	ram_space[the_map_p] = temp_map_
1005	10	end procedure
1006
1007		--**
1008		-- Return the number of entries in a map.
1009		--
1010		-- Parameters:
1011		-- ##the_map_p## : the map being queried
1012		--
1013		-- Returns:
1014		-- An integer, the number of entries it has.
1015		--
1016		-- Comments:
1017		-- For an empty map, size will be zero
1018		--
1019		-- Example 1:
1020		--
1021		-- map the_map_p
1022		-- put(the_map_p, 1, "a")
1023		-- put(the_map_p, 2, "b")
1024		-- ? size(the_map_p) -- outputs 2
1025		--
1026		--
1027		-- See Also:
1028		-- [[:statistics]]
1029	10	public function size(map the_map_p)
1030	10	return ram_space[the_map_p][ELEMENT_COUNT]
1031		end function
1032
1033		--**
1034		-- Retrieves characteristics of a map.
1035		--
1036		-- Parameters:
1037		-- # ##the_map_p## : the map being queried
1038		--
1039		-- Returns:
1040		-- A sequence, of 7 integers:
1041		-- * ##NUM_ENTRIES## ~-- number of entries
1042		-- * ##NUM_IN_USE## ~-- number of buckets in use
1043		-- * ##NUM_BUCKETS## ~-- number of buckets
1044		-- * ##LARGEST_BUCKET## ~-- size of largest bucket
1045		-- * ##SMALLEST_BUCKET## ~-- size of smallest bucket
1046		-- * ##AVERAGE_BUCKET## ~-- average size for a bucket
1047		-- * ##STDEV_BUCKET## ~-- standard deviation for the bucket length series
1048		--
1049		-- Example 1:
1050		--
1051		-- sequence s = statistics(mymap)
1052		-- printf(1, "The average size of the buckets is %d", s[AVERAGE_BUCKET])
1053		--
1054		--
1055
1056		public enum
1057	20	NUM_ENTRIES,
1058	20	NUM_IN_USE,
1059	20	NUM_BUCKETS,
1060	20	LARGEST_BUCKET,
1061	20	SMALLEST_BUCKET,
1062	20	AVERAGE_BUCKET,
1063	20	STDEV_BUCKET
1064
1065	20	public function statistics(map the_map_p)
1066		sequence statistic_set_
1067		sequence lengths_
1068		integer length_
1069		sequence temp_map_
1070
1071	20	temp_map_ = ram_space[the_map_p]
1072
1073	20	if temp_map_[MAP_TYPE] = LARGEMAP then
1074	18	statistic_set_ = {temp_map_[ELEMENT_COUNT], temp_map_[IN_USE], length(temp_map_[KEY_BUCKETS]), 0, maxInt, 0, 0}
1075	18	lengths_ = {}
1076	18	for i = 1 to length(temp_map_[KEY_BUCKETS]) do
1077	58813	length_ = length(temp_map_[KEY_BUCKETS][i])
1078	58813	if length_ > 0 then
1079	23431	if length_ > statistic_set_[LARGEST_BUCKET] then
1080	60	statistic_set_[LARGEST_BUCKET] = length_
1081		end if
1082	23431	if length_ < statistic_set_[SMALLEST_BUCKET] then
1083	40	statistic_set_[SMALLEST_BUCKET] = length_
1084		end if
1085	23431	lengths_ &= length_
1086		end if
1087	58813	end for
1088	18	statistic_set_[AVERAGE_BUCKET] = stats:average(lengths_)
1089	18	statistic_set_[STDEV_BUCKET] = stats:stdev(lengths_)
1090		else
1091	2	statistic_set_ = {temp_map_[ELEMENT_COUNT],
1092		temp_map_[IN_USE],
1093		length(temp_map_[KEY_LIST]),
1094		length(temp_map_[KEY_LIST]),
1095		length(temp_map_[KEY_LIST]),
1096		length(temp_map_[KEY_LIST]),
1097		0}
1098		end if
1099	20	return statistic_set_
1100		end function
1101
1102		--**
1103		-- Return all keys in a map.
1104		--
1105		-- Parameters;
1106		-- # ##the_map_p##: the map being queried
1107		-- # ##sorted_result##: optional integer. 0 [default] means do not sort the
1108		-- output and 1 means to sort the output before returning.
1109		--
1110		-- Returns:
1111		-- A sequence made of all the keys in the map.
1112		--
1113		-- Comments:
1114		-- If ##sorted_result## is not used, the order of the keys returned is not predicable.
1115		--
1116		-- Example 1:
1117		--
1118		-- map the_map_p
1119		-- the_map_p = new()
1120		-- put(the_map_p, 10, "ten")
1121		-- put(the_map_p, 20, "twenty")
1122		-- put(the_map_p, 30, "thirty")
1123		-- put(the_map_p, 40, "forty")
1124		--
1125		-- sequence keys
1126		-- keys = keys(the_map_p) -- keys might be {20,40,10,30} or some other order
1127		-- keys = keys(the_map_p, 1) -- keys will be {10,20,30,40}
1128		--
1129		--
1130		-- See Also:
1131		-- [[:has]], [[:values]], [[:pairs]]
1132		--
1133	14	public function keys(map the_map_p, integer sorted_result = 0)
1134		sequence buckets_
1135		sequence current_bucket_
1136		sequence results_
1137		integer pos_
1138		sequence temp_map_
1139
1140	14	temp_map_ = ram_space[the_map_p]
1141
1142	14	results_ = repeat(0, temp_map_[ELEMENT_COUNT])
1143	14	pos_ = 1
1144
1145	14	if temp_map_[MAP_TYPE] = LARGEMAP then
1146	7	buckets_ = temp_map_[KEY_BUCKETS]
1147	7	for index = 1 to length(buckets_) do
1148	209	current_bucket_ = buckets_[index]
1149	209	if length(current_bucket_) > 0 then
1150	22	results_[pos_ .. pos_ + length(current_bucket_) - 1] = current_bucket_
1151	22	pos_ += length(current_bucket_)
1152		end if
1153	209	end for
1154		else
1155	7	for index = 1 to length(temp_map_[FREE_LIST]) do
1156	331	if temp_map_[FREE_LIST][index] != 0 then
1157	75	results_[pos_] = temp_map_[KEY_LIST][index]
1158	75	pos_ += 1
1159		end if
1160	331	end for
1161
1162		end if
1163	14	if sorted_result then
1164	8	return sort(results_)
1165		else
1166	6	return results_
1167		end if
1168		end function
1169
1170		--**
1171		-- Return values, without their keys, from a map.
1172		--
1173		-- Parameters:
1174		-- # ##the_map## : the map being queried
1175		-- # ##keys## : optional, key list of values to return.
1176		-- # ##default_values## : optional default values for keys list
1177		--
1178		-- Returns:
1179		-- A sequence, of all values stored in ##the_map##.
1180		--
1181		-- Comments:
1182		-- * The order of the values returned may not be the same as the putting order.
1183		-- * Duplicate values are not removed.
1184		-- * You use the ##keys## parameter to return a specific set of values from
1185		-- the map. They are returned in the same order as the ##keys## parameter. If
1186		-- no ##default_values## is given and one is needed, 0 will be used.
1187		-- * If ##default_values## is an atom, it represents the default value for all
1188		-- values in ##keys##.
1189		-- * If ##default_values## is a sequence, and its length is less than ##keys##,
1190		-- then the last item in ##default_values## is used for the rest of the ##keys##.
1191		--
1192		-- Example 1:
1193		--
1194		-- map the_map_p
1195		-- the_map_p = new()
1196		-- put(the_map_p, 10, "ten")
1197		-- put(the_map_p, 20, "twenty")
1198		-- put(the_map_p, 30, "thirty")
1199		-- put(the_map_p, 40, "forty")
1200		--
1201		-- sequence values
1202		-- values = values(the_map_p)
1203		-- -- values might be {"twenty","forty","ten","thirty"}
1204		-- -- or some other order
1205		--
1206		--
1207		-- Example 2:
1208		--
1209		-- map the_map_p
1210		-- the_map_p = new()
1211		-- put(the_map_p, 10, "ten")
1212		-- put(the_map_p, 20, "twenty")
1213		-- put(the_map_p, 30, "thirty")
1214		-- put(the_map_p, 40, "forty")
1215		--
1216		-- sequence values
1217		-- values = values(the_map_p, { 10, 50, 30, 9000 })
1218		-- -- values WILL be { "ten", 0, "thirty", 0 }
1219		-- values = values(the_map_p, { 10, 50, 30, 9000 }, {-1,-2,-3,-4})
1220		-- -- values WILL be { "ten", -2, "thirty", -4 }
1221		--
1222		--
1223		-- See Also:
1224		-- [[:get]], [[:keys]], [[:pairs]]
1225
1226	18	public function values(map the_map, object keys=0, object default_values=0)
1227
1228	18	if sequence(keys) then
1229	5	if atom(default_values) then
1230	3	default_values = repeat(default_values, length(keys))
1231	2	elsif length(default_values) < length(keys) then
1232	1	default_values &= repeat(default_values[$], length(keys) - length(default_values))
1233		end if
1234
1235	5	for i = 1 to length(keys) do
1236	17	keys[i] = get(the_map, keys[i], default_values[i])
1237	17	end for
1238
1239	5	return keys
1240		end if
1241
1242	13	sequence buckets_
1243	13	sequence bucket_
1244	13	sequence results_
1245	13	integer pos_
1246	13	sequence temp_map_
1247
1248	13	temp_map_ = ram_space[the_map]
1249
1250	13	results_ = repeat(0, temp_map_[ELEMENT_COUNT])
1251	13	pos_ = 1
1252
1253	13	if temp_map_[MAP_TYPE] = LARGEMAP then
1254	6	buckets_ = temp_map_[VALUE_BUCKETS]
1255	6	for index = 1 to length(buckets_) do
1256	186	bucket_ = buckets_[index]
1257	186	if length(bucket_) > 0 then
1258	20	results_[pos_ .. pos_ + length(bucket_) - 1] = bucket_
1259	20	pos_ += length(bucket_)
1260		end if
1261	186	end for
1262		else
1263	7	for index = 1 to length(temp_map_[FREE_LIST]) do
1264	380	if temp_map_[FREE_LIST][index] != 0 then
1265	104	results_[pos_] = temp_map_[VALUE_LIST][index]
1266	104	pos_ += 1
1267		end if
1268	380	end for
1269
1270		end if
1271
1272	13	return results_
1273		end function
1274
1275		--**
1276		--
1277		-- Return all key/value pairs in a map.
1278		--
1279		-- Parameters:
1280		-- # ##the_map_p## : the map to get the data from
1281		-- # ##sorted_result## : optional integer. 0 [default] means do not sort the
1282		-- output and 1 means to sort the output before returning.
1283		--
1284		-- Returns:
1285		-- A sequence, of all key/value pairs stored in ##the_map_p##. Each pair is a
1286		-- sub-sequence in the form {key, value}
1287		--
1288		-- Comments:
1289		-- If ##sorted_result## is not used, the order of the values returned is not predicable.
1290		--
1291		-- Example 1:
1292		--
1293		-- map the_map_p
1294		-- the_map_p = new()
1295		-- put(the_map_p, 10, "ten")
1296		-- put(the_map_p, 20, "twenty")
1297		-- put(the_map_p, 30, "thirty")
1298		-- put(the_map_p, 40, "forty")
1299		--
1300		-- sequence keyvals
1301		-- keyvals = pairs(the_map_p) -- might be {{20,"twenty"},{40,"forty"},{10,"ten"},{30,"thirty"}}
1302		-- keyvals = pairs(the_map_p, 1) -- will be {{10,"ten"},{20,"twenty"},{30,"thirty"},{40,"forty"}}
1303		--
1304		--
1305		-- See Also:
1306		-- [[:get]], [[:keys]], [[:values]]
1307		--
1308	27	public function pairs(map the_map_p, integer sorted_result = 0)
1309		sequence key_bucket_
1310		sequence value_bucket_
1311		sequence results_
1312		integer pos_
1313		sequence temp_map_
1314
1315	27	temp_map_ = ram_space[the_map_p]
1316
1317	27	results_ = repeat({0,0}, temp_map_[ELEMENT_COUNT])
1318	27	pos_ = 1
1319
1320	27	if temp_map_[MAP_TYPE] = LARGEMAP then
1321	15	for index = 1 to length(temp_map_[KEY_BUCKETS]) do
1322	441	key_bucket_ = temp_map_[KEY_BUCKETS][index]
1323	441	value_bucket_ = temp_map_[VALUE_BUCKETS][index]
1324	441	for j = 1 to length(key_bucket_) do
1325	6008	results_[pos_][1] = key_bucket_[j]
1326	6008	results_[pos_][2] = value_bucket_[j]
1327	6008	pos_ += 1
1328	6008	end for
1329	441	end for
1330		else
1331	12	for index = 1 to length(temp_map_[FREE_LIST]) do
1332	516	if temp_map_[FREE_LIST][index] != 0 then
1333	88	results_[pos_][1] = temp_map_[KEY_LIST][index]
1334	88	results_[pos_][2] = temp_map_[VALUE_LIST][index]
1335	88	pos_ += 1
1336		end if
1337	516	end for
1338
1339		end if
1340	27	if sorted_result then
1341	25	return sort(results_)
1342		else
1343	2	return results_
1344		end if
1345		end function
1346
1347		--**
1348		-- Widens a map to increase performance.
1349		--
1350		-- Parameters:
1351		-- # ##the_map_p## : the map being optimized
1352		-- # ##max_p## : an integer, the maximum desired size of a bucket. Default is 25.
1353		-- This must be 3 or higher.
1354		-- # ##grow_p## : an atom, the factor to grow the number of buckets for each
1355		-- iteration of rehashing. Default is 1.333. This must be
1356		-- greater than 1.
1357		--
1358		-- Returns:
1359		-- The optimized map.
1360		--
1361		-- Comments:
1362		-- This rehashes the map until either the maximum bucket size is less than
1363		-- the desired maximum or the maximum bucket size is less than the largest
1364		-- size statistically expected (mean + 3 standard deviations).
1365		--
1366		-- See Also:
1367		-- [[:statistics]], [[:rehash]]
1368		--
1369	10	public procedure optimize(map the_map_p, integer max_p = 25, atom grow_p = 1.333)
1370		sequence stats_
1371		integer next_guess_
1372
1373	10	if ram_space[the_map_p][MAP_TYPE] = LARGEMAP then
1374	5	if grow_p < 1 then
1375	2	grow_p = 1.333
1376		end if
1377	5	if max_p < 3 then
1378	2	max_p = 3
1379		end if
1380
1381	5	next_guess_ = max({1, floor(ram_space[the_map_p][ELEMENT_COUNT] / max_p)})
1382	5	while 1 with entry do
1383
1384	13	if stats_[LARGEST_BUCKET] <= max_p then
1385	4	exit -- Largest is now smaller than the maximum I wanted.
1386		end if
1387
1388	9	if stats_[LARGEST_BUCKET] <= (stats_[STDEV_BUCKET]*3 + stats_[AVERAGE_BUCKET]) then
1389	1	exit -- Largest is smaller than is statistically expected.
1390		end if
1391
1392	8	next_guess_ = floor(stats_[NUM_BUCKETS] * grow_p)
1393
1394		entry
1395	13	rehash(the_map_p, next_guess_)
1396	13	stats_ = statistics(the_map_p)
1397	13	end while
1398		end if
1399	10	end procedure
1400
1401		--**
1402		-- Loads a map from a file
1403		--
1404		-- Parameters:
1405		-- # ##file_name_p## : The file to load from. This file may have been created
1406		-- by the [[:save_map]] function. This can either be a
1407		-- name of a file or an already opened file handle.
1408		--
1409		-- Returns:
1410		-- Either a map, with all the entries found in ##file_name_p##, or -1
1411		-- if the file failed to open, or -2 if the file is incorrectly formatted.
1412		--
1413		-- Comments:
1414		-- If ##file_name_p## is an already opened file handle, this routine will write
1415		-- to that file and not close it. Otherwise, the named file will be created and
1416		-- closed by this routine.
1417		--
1418		-- The input file can be either one created by the [[:save_map]] function or
1419		-- a manually created/edited text file. See [[:save_map]] for details about
1420		-- the required layout of the text file.
1421		--
1422		--
1423		-- Example 1:
1424		--
1425		-- object loaded
1426		-- map AppOptions
1427		-- sequence SavedMap = "c:\myapp\options.txt"
1428		-- loaded = load_map(SavedMap)
1429		-- if equal(loaded, -1) then
1430		-- crash("Map '%s' failed to open", SavedMap)
1431		-- end if
1432		-- -- By now we know that it was loaded and a new map created,
1433		-- -- so we can assign it to a 'map' variable.
1434		-- AppOptions = loaded
1435		-- if get(AppOptions, "verbose", 1) = 3 then
1436		-- ShowIntructions()
1437		-- end if
1438		--
1439		--
1440		-- See Also:
1441		-- [[:new]], [[:save_map]]
1442		--
1443	8	public function load_map(object file_name_p)
1444		integer file_handle_
1445		object line_
1446		integer comment_
1447		integer delim_
1448		object value_
1449		object key_
1450		sequence conv_res_
1451		atom new_map_
1452
1453	8	if sequence(file_name_p) then
1454	7	file_handle_ = open(file_name_p, "rb")
1455		else
1456	1	file_handle_ = file_name_p
1457		end if
1458	8	if file_handle_ = -1 then
1459	1	return -1
1460		end if
1461
1462	7	new_map_ = new(threshold_size) -- Assume a small map initially.
1463
1464		-- Look for a non-printable byte in the first 10 bytes. If none are found then this is a text-formated
1465		-- file otherwise it is a 'raw' saved file.
1466
1467	7	for i = 1 to 10 do
1468	32	delim_ = getc(file_handle_)
1469	32	if delim_ = -1 then
1470	1	exit
1471		end if
1472	31	if not t_print(delim_) then
1473	6	if not t_space(delim_) then
1474	4	exit
1475		end if
1476		end if
1477	27	delim_ = -1
1478	27	end for
1479
1480	7	if delim_ = -1 then
1481		-- A text format file
1482	3	close(file_handle_)
1483	3	file_handle_ = open(file_name_p, "r")
1484	3	while sequence(line_) with entry do
1485	32	comment_ = rmatch("--", line_)
1486	32	if comment_ != 0 then
1487	3	line_ = trim(line_[1..comment_-1])
1488		end if
1489	32	delim_ = find('=', line_)
1490	32	if delim_ > 0 then
1491	22	key_ = trim(line_[1..delim_-1])
1492	22	if length(key_) > 0 then
1493	22	key_ = match_replace("\\-", key_, "-")
1494	22	if not t_alpha(key_[1]) then
1495	13	conv_res_ = value(key_,,GET_LONG_ANSWER)
1496	13	if conv_res_[1] = GET_SUCCESS then
1497	13	if conv_res_[3] = length(key_) then
1498	13	key_ = conv_res_[2]
1499		end if
1500		end if
1501		end if
1502
1503	22	value_ = trim(line_[delim_+1..$])
1504	22	value_ = match_replace("\\-", value_, "-")
1505	22	conv_res_ = value(value_,,GET_LONG_ANSWER)
1506	22	if conv_res_[1] = GET_SUCCESS then
1507	16	if conv_res_[3] = length(value_) then
1508	16	value_ = conv_res_[2]
1509		end if
1510		end if
1511	22	put(new_map_, key_, value_)
1512		end if
1513		end if
1514		entry
1515	35	line_ = gets(file_handle_)
1516	35	end while
1517		else
1518	4	object _ = seek(file_handle_, 0)
1519	4	line_ = deserialize(file_handle_)
1520	4	if atom(line_) then
1521		-- failed to decode the file.
1522	1	return -2
1523		end if
1524	3	if line_[1] = 1 then
1525		-- Saved Map Format version 1
1526	2	key_ = deserialize(file_handle_)
1527	2	value_ = deserialize(file_handle_)
1528
1529	2	for i = 1 to length(key_) do
1530	24	put(new_map_, key_[i], value_[i])
1531	24	end for
1532		else
1533		-- Bad file format
1534	1	return -2
1535		end if
1536		end if
1537	5	if sequence(file_name_p) then
1538	4	close(file_handle_)
1539		end if
1540	5	optimize(new_map_)
1541	5	return new_map_
1542		end function
1543
1544		--**
1545		-- Saves a map to a file.
1546		--
1547		-- Parameters:
1548		-- # ##m## : a map.
1549		-- # ##file_name_p## : Either a sequence, the name of the file to save to,
1550		-- or an open file handle as returned by [[:open]]().
1551		-- # ##type## : an integer. SM_TEXT for a human-readable format (default),
1552		-- SM_RAW for a smaller and faster format, but not human-readable.
1553		--
1554		-- Returns:
1555		-- An integer, the number of keys saved to the file, or -1 if the
1556		-- save failed.
1557		--
1558		-- Comments:
1559		-- If ##file_name_p## is an already opened file handle, this routine will write
1560		-- to that file and not close it. Otherwise, the named file will be created and
1561		-- closed by this routine.
1562		--
1563		-- The SM_TEXT type saves the map keys and values in a text format which can
1564		-- be read and edited by standard text editor. Each entry in the map is saved as
1565		-- a KEY/VALUE pair in the form \\
1566		-- {{{
1567		-- key = value
1568		-- }}}
1569		-- Note that if the 'key' value is a normal string value, it can be enclosed in
1570		-- double quotes. If it is not thus quoted, the first character of the key
1571		-- determines its Euphoria value type. A dash or digit implies an atom, an left-brace
1572		-- implies a sequence, an alphabetic character implies a text string that extends to the
1573		-- next equal '=' symbol, and anything else is ignored.
1574		--
1575		-- Note that if a line contains a double-dash, then all text from the double-dash
1576		-- to the end of the line will be ignored. This is so you can optionally add
1577		-- comments to the saved map. Also, any blank lines are ignored too.
1578		--
1579		-- All text after the '=' symbol is assumed to be the map item's value data.
1580		--
1581		-- The SM_RAW type saves the map in an efficient manner. It is generally smaller
1582		-- than the text format and is faster to process, but it is not human readable and
1583		-- standard text editors can not be used to edit it. In this format, the file will
1584		-- contain three serialized sequences:
1585		-- # Header sequence: {integer:format version, string: date and time of save (YYMMDDhhmmss),
1586		-- sequence: euphoria version {major, minor, revision, patch}}
1587		-- # Keys. A list of all the keys
1588		-- # Values. A list of the corresponding values for the keys.
1589		--
1590		-- Example 1:
1591		--
1592		-- map AppOptions
1593		-- if save_map(AppOptions, "c:\myapp\options.txt") = -1
1594		-- Error("Failed to save application options")
1595		-- end if
1596		-- if save_map(AppOptions, "c:\myapp\options.dat", SM_RAW) = -1
1597		-- Error("Failed to save application options")
1598		-- end if
1599		--
1600		--
1601		-- See Also:
1602		-- [[:load_map]]
1603
1604		public enum
1605	20	SM_TEXT,
1606	20	SM_RAW
1607
1608	4	public function save_map(map the_map_, object file_name_p, integer type_ = SM_TEXT)
1609	4	integer file_handle_ = -2
1610		sequence keys_
1611		sequence values_
1612
1613	4	if sequence(file_name_p) then
1614	3	if type_ = SM_TEXT then
1615	2	file_handle_ = open(file_name_p, "w")
1616		else
1617	1	file_handle_ = open(file_name_p, "wb")
1618		end if
1619		else
1620	1	file_handle_ = file_name_p
1621		end if
1622
1623	4	if file_handle_ < 0 then
1624	1	return -1
1625		end if
1626
1627	3	keys_ = keys(the_map_)
1628	3	values_ = values(the_map_)
1629
1630	3	if type_ = SM_RAW then
1631	2	puts(file_handle_, serialize(
1632		{1, -- saved map version
1633		datetime:format(now_gmt(), "%Y%m%d%H%M%S" ), -- date of this saved map
1634		{4,0,0,0}} -- Euphoria version
1635		))
1636	2	puts(file_handle_, serialize(keys_))
1637	2	puts(file_handle_, serialize(values_))
1638		else
1639	1	for i = 1 to length(keys_) do
1640	12	keys_[i] = pretty_sprint(keys_[i], {2,0,1,0,"%d","%.15g",32,127,1,0})
1641	12	keys_[i] = match_replace("-", keys_[i], "\\-")
1642	12	values_[i] = pretty_sprint(values_[i], {2,0,1,0,"%d","%.15g",32,127,1,0})
1643	12	values_[i] = match_replace("-", values_[i], "\\-")
1644
1645	12	printf(file_handle_, "%s = %s\n", {keys_[i], values_[i]})
1646
1647	12	end for
1648		end if
1649
1650	3	if sequence(file_name_p) then
1651	2	close(file_handle_)
1652		end if
1653	3	return length(keys_)
1654		end function
1655
1656		--**
1657		-- Duplicates a map.
1658		--
1659		-- Parameters:
1660		-- # ##source_map## : map to copy from
1661		-- # ##dest_map## : optional, map to copy to
1662		-- # ##put_operation## : optional, operation to use when ##dest##map## is used.
1663		-- The default is PUT.
1664		--
1665		-- Returns:
1666		-- If ##dest_map## was not provided, an exact duplicate of ##source_map## otherwise
1667		-- ##dest_map##, which does not have to be empty, is returned with the
1668		-- new values copied from ##source_map##, according to the ##put_operation## value.
1669		--
1670		-- Example 1:
1671		--
1672		-- map m1 = new()
1673		-- put(m1, 1, "one")
1674		-- put(m1, 2, "two")
1675		--
1676		-- map m2 = copy(m1)
1677		-- printf(1, "%s, %s\n", { get(m2, 1), get(m2, 2) })
1678		-- -- one, two
1679		--
1680		-- put(m1, 1, "one hundred")
1681		-- printf(1, "%s, %s\n", { get(m1, 1), get(m1, 2) })
1682		-- -- one hundred, two
1683		--
1684		-- printf(1, "%s, %s\n", { get(m2, 1), get(m2, 2) })
1685		-- -- one, two
1686		--
1687		--
1688		-- Example 2:
1689		--
1690		-- map m1 = new()
1691		-- map m2 = new()
1692		--
1693		-- put(m1, 1, "one")
1694		-- put(m1, 2, "two")
1695		-- put(m2, 3, "three")
1696		--
1697		-- copy(m1, m2)
1698		--
1699		-- ? keys(m2)
1700		-- -- { 1, 2, 3 }
1701		--
1702		--
1703		-- Example 3:
1704		--
1705		-- map m1 = new()
1706		-- map m2 = new()
1707		--
1708		-- put(m1, "XY", 1)
1709		-- put(m1, "AB", 2)
1710		-- put(m2, "XY", 3)
1711		--
1712		-- ? pairs(m1) -- { {"AB", 2}, {"XY", 1} }
1713		-- ? pairs(m2) -- { {"XY", 3} }
1714		--
1715		-- -- Add same keys' values.
1716		-- copy(m1, m2, ADD)
1717		--
1718		-- ? pairs(m2)
1719		-- -- { {"AB", 2}, {"XY", 4} }
1720		--
1721		--
1722		-- See Also:
1723		-- [[:put]]
1724
1725	5	public function copy(map source_map, object dest_map=0, integer put_operation = PUT)
1726
1727	5	if map(dest_map) then
1728		-- Copies the contents of one map to another map.
1729	4	sequence keys_set
1730	4	sequence value_set
1731	4	sequence source_data
1732
1733	4	source_data = ram_space[source_map]
1734	4	if source_data[MAP_TYPE] = LARGEMAP then
1735	3	for index = 1 to length(source_data[KEY_BUCKETS]) do
1736	57	keys_set = source_data[KEY_BUCKETS][index]
1737	57	value_set = source_data[VALUE_BUCKETS][index]
1738	57	for j = 1 to length(keys_set) do
1739	5	put(dest_map, keys_set[j], value_set[j], put_operation)
1740	5	end for
1741	57	end for
1742		else
1743	1	for index = 1 to length(source_data[FREE_LIST]) do
1744	50	if source_data[FREE_LIST][index] != 0 then
1745	2	put(dest_map, source_data[KEY_LIST][index], source_data[VALUE_LIST][index], put_operation)
1746		end if
1747	50	end for
1748
1749		end if
1750
1751	4	return dest_map
1752		else
1753	1	atom temp_map = malloc()
1754	1	ram_space[temp_map] = ram_space[source_map]
1755	1	return temp_map
1756		end if
1757		end function
1758
1759
1760		--**
1761		-- Converts a set of Key-Value pairs to a map.
1762		--
1763		-- Parameters:
1764		-- # ##kv_pairs## : A seqeuence containing any number of subsequences that
1765		-- have the format {KEY, VALUE}. These are loaded into a
1766		-- new map which is then returned by this function.
1767		--
1768		-- Returns:
1769		-- A map, containing the data from ##kv_pairs##
1770		--
1771		-- Example 1:
1772		--
1773		-- map m1 = new_from_kvpairs( {
1774		-- {"application", "Euphoria"},
1775		-- {"version", "4.0"},
1776		-- {"genre", "programming language"},
1777		-- {"crc", 0x4F71AE10}
1778		-- })
1779		--
1780		-- v = map:get(m1, "application") --> "Euphoria"
1781		--
1782		--
1783	3	public function new_from_kvpairs(sequence kv_pairs)
1784		object new_map
1785
1786	3	new_map = new( floor(7 * length(kv_pairs) / 2) )
1787	3	for i = 1 to length(kv_pairs) do
1788	10	if length(kv_pairs[i]) = 2 then
1789	10	put(new_map, kv_pairs[i][1], kv_pairs[i][2])
1790		end if
1791	10	end for
1792
1793	3	return new_map
1794
1795		end function
1796
1797		--**
1798		-- Converts a set of Key-Value pairs contained in a string to a map.
1799		--
1800		-- Parameters:
1801		-- # ##kv_string## : A string containing any number of lines that
1802		-- have the format KEY=VALUE. These are loaded into a
1803		-- new map which is then returned by this function.
1804		--
1805		-- Returns:
1806		-- A map, containing the data from ##kv_string##
1807		--
1808		-- Comment:
1809		-- This function actually calls ##[[:keyvalues]]()## to convert the string to
1810		-- key-value pairs, which are then used to create the map.
1811		--
1812		-- Example 1:
1813		-- Given that a file called "xyz.config" contains the lines ...
1814		-- {{{
1815		-- application = Euphoria,
1816		-- version = 4.0,
1817		-- genre = "programming language",
1818		-- crc = 4F71AE10
1819		-- }}}
1820		--
1821		-- map m1 = new_from_string( read_file("xyz.config", TEXT_MODE))
1822		--
1823		-- printf(1, "%s\n", {map:get(m1, "application")}) --> "Euphoria"
1824		-- printf(1, "%s\n", {map:get(m1, "genre")}) --> "programming language"
1825		-- printf(1, "%s\n", {map:get(m1, "version")}) --> "4.0"
1826		-- printf(1, "%s\n", {map:get(m1, "crc")}) --> "4F71AE10"
1827		--
1828		--
1829		--
1830	2	public function new_from_string(sequence kv_string)
1831	2	return new_from_kvpairs( keyvalues (kv_string) )
1832		end function
1833
1834
1835		--**
1836		-- Calls a user-defined routine for each of the items in a map.
1837		--
1838		-- Parameters:
1839		-- # ##source_map## : The map containing the data to process
1840		-- # ##user_rid##: The routine_id of a user defined processing function
1841		-- # ##user_data##: An object. Optional. This is passed, unchanged to each call
1842		-- of the user defined routine. By default, zero (0) is used.
1843		-- # ##in_sorted_order##: An integer. Optional. If non-zero the items in the
1844		-- map are processed in ascending key sequence otherwise
1845		-- the order is undefined. By default they are not sorted.
1846		--
1847		-- Returns:
1848		-- An integer: 0 means that all the items were processed, and anything else is whatever
1849		-- was returned by the user routine to abort the ##for_each()## process.
1850		--
1851		-- Comment:
1852		-- * The user defined routine is a function that must accept four parameters.
1853		-- ## Object: an Item Key
1854		-- ## Object: an Item Value
1855		-- ## Object: The ##user_data## value. This is never used by ##for_each()## itself,
1856		-- merely passed to the user routine.
1857		-- ## Integer: Progress code.
1858		-- *** The ##abs()## value of the progress code is the ordinal call number. That
1859		-- is 1 means the first call, 2 means the second call, etc ...
1860		-- *** If the progress code is negative, it is also the last call to the routine.
1861		-- *** If the progress code is zero, it means that the map is empty and thus the
1862		-- item key and value cannot be used.
1863		-- * The user routine must return 0 to get the next map item. Anything else will
1864		-- cause ##for_each()## to stop running, and is returned to whatever called
1865		-- ##for_each()##.
1866		--
1867		-- Example 1:
1868		--
1869		-- include std/map.e
1870		-- include std/math.e
1871		-- include std/io.e
1872		-- function Process_A(object k, object v, object d, integer pc)
1873		-- writefln("[] = []", {k, v})
1874		-- return 0
1875		-- end function
1876		--
1877		-- function Process_B(object k, object v, object d, integer pc)
1878		-- if pc = 0 then
1879		-- writefln("The map is empty")
1880		-- else
1881		-- integer c
1882		-- c = abs(pc)
1883		-- if c = 1 then
1884		-- writefln("---[]---", {d}) -- Write the report title.
1885		-- end if
1886		-- writefln("[]: [:15] = []", {c, k, v})
1887		-- if pc < 0 then
1888		-- writefln(repeat('-', length(d) + 6), {}) -- Write the report end.
1889		-- end if
1890		-- end if
1891		-- return 0
1892		-- end function
1893		--
1894		-- map m1 = new()
1895		-- map:put(m1, "application", "Euphoria")
1896		-- map:put(m1, "version", "4.0")
1897		-- map:put(m1, "genre", "programming language")
1898		-- map:put(m1, "crc", "4F71AE10")
1899		--
1900		-- -- Unsorted
1901		-- map:for_each(m1, routine_id("Process_A"))
1902		-- -- Sorted
1903		-- map:for_each(m1, routine_id("Process_B"), "List of Items", 1)
1904		--
1905		--
1906		-- The output from the first call could be...
1907		-- {{{
1908		-- application = Euphoria
1909		-- version = 4.0
1910		-- genre = programming language
1911		-- crc = 4F71AE10
1912		-- }}}
1913		--
1914		-- The output from the second call should be...
1915		-- {{{
1916		-- ---List of Items---
1917		-- 1: application = Euphoria
1918		-- 2: crc = 4F71AE10
1919		-- 3: genre = programming language
1920		-- 4: version = 4.0
1921		-- -------------------
1922		-- }}}
1923		--
1924	4	public function for_each(map source_map, integer user_rid, object user_data = 0, integer in_sorted_order = 0)
1925		sequence lKV
1926		object lRes
1927
1928	4	lKV = pairs(source_map, in_sorted_order)
1929	4	if length(lKV) = 0 then
1930	1	return call_func(user_rid, {0,0,user_data,0} )
1931		end if
1932
1933	3	for i = 1 to length(lKV) do
1934	10	if i = length(lKV) then
1935	2	lRes = call_func(user_rid, {lKV[i][1], lKV[i][2], user_data, -i})
1936		else
1937	8	lRes = call_func(user_rid, {lKV[i][1], lKV[i][2], user_data, i})
1938		end if
1939	10	if not equal(lRes, 0) then
1940	1	return lRes
1941		end if
1942	9	end for
1943	2	return 0
1944		end function
1945
1946		-- LOCAL FUNCTIONS --
1947	1	procedure convert_to_large_map(map the_map_)
1948		sequence temp_map_
1949		atom map_handle_
1950
1951	1	temp_map_ = ram_space[the_map_]
1952
1953	1	map_handle_ = new()
1954	1	for index = 1 to length(temp_map_[FREE_LIST]) do
1955	11	if temp_map_[FREE_LIST][index] != 0 then
1956	11	put(map_handle_, temp_map_[KEY_LIST][index], temp_map_[VALUE_LIST][index])
1957		end if
1958	11	end for
1959
1960	1	ram_space[the_map_] = ram_space[map_handle_]
1961	1	end procedure
1962
1963	3	procedure convert_to_small_map(map the_map_)
1964		sequence keys_
1965		sequence values_
1966
1967	3	keys_ = keys(the_map_)
1968	3	values_ = values(the_map_)
1969
1970	3	ram_space[the_map_] = {type_is_map, 0,0, SMALLMAP, repeat(init_small_map_key, threshold_size), repeat(0, threshold_size), repeat(0, threshold_size)}
1971
1972	3	for i = 1 to length(keys_) do
1973	8	put(the_map_, keys_[i], values_[i], PUT, 0)
1974	8	end for
1975
1976	3	end procedure
1977