Commented Header

The comments provide a walkthough of the necessary definitions to create a map of strings to const strings.

////////////////////////////// * Common Headers * //////////////////////////////
/*
  The internal bit keys are represented as unsigned integers so we import the
  standard integer definitions.
*/
#include <stdint.h>
#include <inttypes.h>

/*
  These next 3 lines are just for generating the examples with CMake and can be
  omitted.
*/
#ifndef RBT_NO_CMAKE
#  include "cmake_config.h"
#endif //RBT_NO_CMAKE

/*
  Import common headers. Uncomment the second line to enable debugging messages.
*/
#include "common.h"
// #define RBT_DEBUG 1
#include "debug.h"



////////////////////////////////// * key.h * ///////////////////////////////////
/*
  Now it is time to define the internal key representation. `RBT_KEY_H_PREFIX_`
  determines the function name prefix that will be used for all of the resulting
  key functions. `RBT_PIN_T` determines the size of the unsigned ints in the key
  arrays. Here we use unsigned 8-bit (1-byte) integers as they will align
  perfectly with our string key values (which are arrays of chars). This
  alignment is not necessary. You can use 32-bit unsigned ints as well, and it
  may even be faster on some systems. For large tree trees, however,
  misalignment will lead to some wasted space because a node that holds 1 char
  will still use a 32-bit (4-byte) int. The choice depends on intended usage but
  for most cases it is trivial.
*/

#define RBT_KEY_H_PREFIX_ string_to_const_string_
#define RBT_PIN_T uint_fast8_t


/*
  `RBT_KEY_SIZE_T` determines the type of variable that stores key lengths. For
  example, if you have a fixed-length key such as a 32-bit integer or a 4-byte
  struct, then the longest key will be 32 bits. An unsigned char's maximum value
  is 255, which would therefore suffice. In this case, the keys are string
  values of arbitrary length. They may therefore be any size, but we must select
  a fixed value for the key size type. Here we choose (unsigned!) 32-bit
  integers. The maximum value such an integer may hold is 4294967295, so our key
  length is therefore practically limited to 4294967295 bits, or 536870911
  bytes. They key strings may therefore be over 536 *million* characters long.
  That should be enough.

  `RBT_KEY_SIZE_T_FORMAT` is simply the printf formatter required to print
  values of type `RBT_KEY_SIZE_T`. "%u" is what we use for unsigned integers.
*/

#define RBT_KEY_SIZE_T uint_fast32_t
#define RBT_KEY_SIZE_T_FORMAT PRIuFAST32

/*
  Finally we include `key.h`, which will define the appropriate functions based
  on these macros.
*/
#include "key.h"


////////////////////////////////// * node.h * //////////////////////////////////
/*
  Next it is time to define the tree node type. These will hold keys and values,
  which is why they are defined after the keys above. `RBT_NODE_H_PREFIX_`
  serves the same purpose for the node functions as `RBT_KEY_H_PREFIX_` does for
  the key functions. Here we make them the same because we are only dealing with
  one tree type, but they could be different. This is useful when you want to
  use the same key type in different trees, e.g. instead of
  `string_to_const_string_`, you may use the key prefix `uint8_` to indicate
  generic 8-bit keys.
*/

#define RBT_NODE_H_PREFIX_ string_to_const_string_

/*
  `RBT_VALUE_TYPE` determines the type of value to store in the node. Here we
  store pointers to constrant strings. `RBT_VALUE_NULL` determines our null
  value. A node with this value is considered empty. For strings, we use the
  `NULL` pointer. `RBT_VALUE_IS_EQUAL` is a function for comparing node values.
  It must return 0 if the values are to be considered different and non-zero
  otherwise. Among other things, this is used to determine if the node is empty
  by comparing the value to the null value. Note that the simple `==` comparison
  suffices for values of `const char *` because of the way constant strings are
  store (pointers are re-used and thus comparable) . If we were storing
  allocated strings then we would need to use `strcmp`, because the pointers
  could be different.
*/

#define RBT_VALUE_T const char *
#define RBT_VALUE_NULL NULL
#define RBT_VALUE_IS_EQUAL(a, b) (a == b)

/*
  `RBT_VALUE_COPY` is a function for copying the values. Again, because we are
  dealing with constant strings we can simply copy the pointer. Allocated
  strings would require an invocation of `strcpy` to copy the data from one
  pointer to another. If we used a simple assignment, the original pointer would
  be lost, which would lead to a memory leak, and both nodes would then point to
  the same area of memory.
*/

#define RBT_VALUE_COPY(a, b, fail) a = b

/*
  `RBT_VALUE_FREE` is used to free the value when the node is freed. Here it
  does nothing because constant strings are not allocated, but if the value were
  a pointer to allocated memory then we would use `free(val)`. This function
  allows for more complicated management of values that are no longer used, e.g.
  removing directories from inotify watchlists, etc.
*/

#define RBT_VALUE_FREE(val)

/*
  `RBT_VALUE_FPRINT` is used for printing trees. It should only print the value
  if it is not equal to the null value.
*/

#define RBT_VALUE_FPRINT(fd, val) \
do \
{ \
  if (val != NULL) \
  { \
    fprintf(fd, "%s", val); \
  } \
} while(0)

/*
  Finally we include `node.h` to define the node functions and
  `traverse_with_key.h` for traversal functions. We could optionally define
  `RBT_TRAVERSE_H_PREFIX_` before including the latter to customize the function
  names but this is only necessary when creating different traversal types, e.g.
  for different fixed-length keys.
*/
#include "node.h"
#include "traverse_with_key.h"




//////////////////////////////// * wrapper.h * /////////////////////////////////
/*
  The final section of the header provides a way to automatically convert
  strings to keys. `RBT_WRAPPER_H_PREFIX_` sets the prefix for wrapper function
  names. Again, we choose the same prefix as before. `RBT_KEY_T` is the key
  value type. Here we are using dynamic strings, so the key type will be a
  pointer to an array of chars. `RBT_KEY_SIZE_FIXED` is set to 0 to indicate
  that the key length is variable. If out key type had been an `int` then we
  could have used `sizeof(int)`, for example. The same would work with keys of
  type struct, for example.
*/

#define RBT_WRAPPER_H_PREFIX_ string_to_const_string_
#define RBT_KEY_T char *
#define RBT_KEY_SIZE_FIXED 0

/*
  `RBT_KEY_COUNT_BITS` is a function to return the length **in bits** of the
  key. Here we use `strlen` because we do not care about the trailing `\0` at
  the end of our strings. This has a real consequence for internal key
  representations. If the terminating null character is included, then "foo" is
  not a radix of "foobar" because internally foo is represented as "foo\0", so
  the tree will include a node for "foo" with two child nodes: one for "\0" and
  one for "bar\0". Without the terminating null character, there will only be
  two nodes: "foo" and a child node "bar".

  The "+1 variant will include the terminating null character.
*/

#define RBT_KEY_COUNT_BITS(key) (strlen(key) * BITS_PER_BYTE)
// #define RBT_KEY_COUNT_BITS(key) ((strlen(key) + 1) * BITS_PER_BYTE)

/*
  `RBT_KEY_PTR` is a function to return a pointer to the underlying data so that
  the bytes can be copied from the key to the underlying array and vice versa.
  For a string value the key is already a pointer. For simple non-pointer types
  the `&` operator would be used.
*/

#define RBT_KEY_PTR(key) (key)

/*
  `RBT_KEY_FPRINT` is used to provide a way to print the key. Here the length
  (in bytes) is used with `%.*s` because the strings are not null-terminated.
  The length thus provides a way to know when the end of the string has been
  reached. If we had used null terminators then `%s` could have been used and
  the length could have been ignored.
*/

#define RBT_KEY_FPRINT(fd, key, len) fprintf(fd, "%.*s", (int) len, key);

/*
  Finally we include `wrapper.h` after these definitions to defined the wrapper
  functions.
*/

#include "wrapper.h"

/*
  Note that the wrapper defines how our key types are converted to and from the
  internal key representation specified by the definitions preceding `key.h`
  above. It is important to understand the distinction between the two. Internal
  keys are arrays of bytes (actually, bits). Anything data type that can be
  represented as a continuous array of bytes can be converted to an internal
  key, and this is precisely what the functions in `wrapper.h` do, so that these
  key types can be used to transparently access the tree.
*/

Body

With these definitions, either in a separate header file or in the body of our source, we can create a new map as follows:

string_to_const_string_node_t * node;
node = string_to_const_string_node_new();

And then add values to it with

string_to_constant_string_insert(node, "Switzerland", "Bern");
string_to_constant_string_insert(node, "India", "New Delhi");
string_to_constant_string_insert(node, "China", "Beijing");
string_to_constant_string_insert(node, "Russia", "Moscow");
...

To look up the value associated with “Switzerland”:

const char * capital;
capital = string_to_constant_string_retrieve(node, "Switzerland");

To remove “Switzerland” from the tree:

capital = string_to_constant_string_delete(node, "Switzerland");

The wrapper.h functions are documented here. Note the correspondence between the macro names in the documentation and the function names that result. The RBT_ prefix is replaced with the prefix defined by RBT_WRAPPER_H_PREFIX_ and the rest of the macro name is converted to lower case. This pattern is followed by the other header files. It is possible to use the macro definitions directly if no maps have been defined, e.g. we could use

RBT_INSERT(node, "Switzerland", "Bern");

directly, but only if the most recently defined wrapper.h macros correspond to these function. In a large project, this will likely not be the case, and the fixed definitions are preferred, i.e. string_to_constant_string_*.

The sources include an example file that creates a map of countries to their capitals and demonstrates various filtering and traversal methods that can be performed using these definitions.

Output

The following is the output of the aforementioned example file.

Representation of the tree:
● 
├● 
│├● 
││├● 
│││├● 
││││├● 
│││││├● Kabul
│││││└● 
│││││ ├● 
│││││ │├● Tirane
│││││ │└● Algiers
│││││ └● 
│││││  ├● 
│││││  │├● Andorra la Vella
│││││  │└● Luanda
│││││  └● Saint John's
││││└● 
││││ ├● 
││││ │├● 
││││ ││├● Buenos Aires
││││ ││└● Yerevan
││││ │└● 
││││ │ ├● Canberra
││││ │ └● Vienna
││││ └● Baku
│││└● 
│││ ├● 
│││ │├● 
│││ ││├● 
│││ │││├● 
│││ ││││├● 
│││ │││││├● Manama
│││ │││││└● Dhaka
│││ ││││└● Bridgetown
│││ │││└● 
│││ │││ ├● 
│││ │││ │├● 
│││ │││ ││├● Minsk
│││ │││ ││└● Brussels
│││ │││ │└● Belmopan
│││ │││ └● Porto-Novo
│││ ││└● 
│││ ││ ├● Thimphu
│││ ││ └● 
│││ ││  ├● La Paz (administrative); Sucre (judicial)
│││ ││  └● 
│││ ││   ├● Sarajevo
│││ ││   └● Gaborone
│││ │└● 
│││ │ ├● 
│││ │ │├● Brasilia
│││ │ │└● Bandar Seri Begawan
│││ │ └● 
│││ │  ├● Sofia
│││ │  └● 
│││ │   ├● Ouagadougou
│││ │   └● Bujumbura
│││ └● 
│││  ├● 
│││  │├● 
│││  ││├● 
│││  │││├● 
│││  ││││├● 
│││  │││││├● Phnom Penh
│││  │││││└● Yaounde
│││  ││││└● Ottawa
│││  │││└● Praia
│││  ││└● Bangui
│││  │└● 
│││  │ ├● 
│││  │ │├● N'Djamena
│││  │ │└● 
│││  │ │ ├● Santiago
│││  │ │ └● Beijing
│││  │ └● 
│││  │  ├● 
│││  │  │├● 
│││  │  ││├● Bogota
│││  │  ││└● Moroni
│││  │  │└● 
│││  │  │ ├● Kinshasa
│││  │  │ └● Brazzaville
│││  │  └● 
│││  │   ├● San Jose
│││  │   └● Yamoussoukro (official); Abidjan (de facto)
│││  └● 
│││   ├● 
│││   │├● Zagreb
│││   │└● Havana
│││   └● 
│││    ├● Nicosia
│││    └● Prague
││└● 
││ ├● 
││ │├● 
││ ││├● Copenhagen
││ ││└● 
││ ││ ├● Djibouti
││ ││ └● Roseau
││ ││  └● Santo Domingo
││ │└● 
││ │ ├● 
││ │ │├● 
││ │ ││├● 
││ │ │││├● Dili
││ │ │││└● Quito
││ │ ││└● Cairo
││ │ │└● San Salvador
││ │ └● 
││ │  ├● 
││ │  │├● Malabo
││ │  │└● 
││ │  │ ├● Asmara
││ │  │ └● Tallinn
││ │  └● Addis Ababa
││ └● 
││  ├● 
││  │├● 
││  ││├● Suva
││  ││└● Helsinki
││  │└● Paris
││  └● 
││   ├● 
││   │├● 
││   ││├● Libreville
││   ││└● 
││   ││ ├● Tbilisi
││   ││ └● Berlin
││   │└● Accra
││   └● 
││    ├● 
││    │├● Athens
││    │└● Saint George's
││    └● 
││     ├● 
││     │├● Guatemala City
││     │└● Conakry
││     │ └● Bissau
││     └● Georgetown
│└● 
│ ├● 
│ │├● 
│ ││├● 
│ │││├● 
│ ││││├● Port-au-Prince
│ ││││└● Tegucigalpa
│ │││└● Budapest
│ ││└● 
│ ││ ├● 
│ ││ │├● Reykjavik
│ ││ │└● 
│ ││ │ ├● New Delhi
│ ││ │ └● Jakarta
│ ││ └● 
│ ││  ├● 
│ ││  │├● 
│ ││  ││├● 
│ ││  │││├● Tehran
│ ││  │││└● Baghdad
│ ││  ││└● Dublin
│ ││  │└● Jerusalem*
│ ││  └● Rome
│ │└● 
│ │ ├● 
│ │ │├● 
│ │ ││├● Kingston
│ │ ││└● Tokyo
│ │ │└● Amman
│ │ └● 
│ │  ├● 
│ │  │├● 
│ │  ││├● Astana
│ │  ││└● Nairobi
│ │  │└● 
│ │  │ ├● Tarawa Atoll
│ │  │ └● 
│ │  │  ├● 
│ │  │  │├● Pyongyang
│ │  │  │└● Seoul
│ │  │  └● Pristina
│ │  └● 
│ │   ├● Kuwait City
│ │   └● Bishkek
│ └● 
│  ├● 
│  │├● 
│  ││├● 
│  │││├● 
│  ││││├● 
│  │││││├● Vientiane
│  │││││└● Riga
│  ││││└● 
│  ││││ ├● Beirut
│  ││││ └● Maseru
│  │││└● 
│  │││ ├● 
│  │││ │├● 
│  │││ ││├● Monrovia
│  │││ ││└● Tripoli
│  │││ │└● Vaduz
│  │││ └● Vilnius
│  ││└● Luxembourg
│  │└● 
│  │ ├● 
│  │ │├● 
│  │ ││├● 
│  │ │││├● 
│  │ ││││├● 
│  │ │││││├● Skopje
│  │ │││││└● Antananarivo
│  │ ││││└● 
│  │ ││││ ├● 
│  │ ││││ │├● 
│  │ ││││ ││├● 
│  │ ││││ │││├● Lilongwe
│  │ ││││ │││└● Kuala Lumpur
│  │ ││││ ││└● Male
│  │ ││││ │└● Bamako
│  │ ││││ └● Valletta
│  │ │││└● 
│  │ │││ ├● Majuro
│  │ │││ └● 
│  │ │││  ├● Nouakchott
│  │ │││  └● Port Louis
│  │ ││└● Mexico City
│  │ │└● 
│  │ │ ├● Palikir
│  │ │ └● 
│  │ │  ├● 
│  │ │  │├● Chisinau
│  │ │  │└● 
│  │ │  │ ├● 
│  │ │  │ │├● Monaco
│  │ │  │ │└● Ulaanbaatar
│  │ │  │ └● Podgorica
│  │ │  └● 
│  │ │   ├● Rabat
│  │ │   └● Maputo
│  │ └● Rangoon (Yangon); Naypyidaw or Nay Pyi Taw (administrative)
│  └● 
│   ├● 
│   │├● 
│   ││├● 
│   │││├● Windhoek
│   │││└● no official capital; government offices in Yaren District
│   ││└● 
│   ││ ├● Kathmandu
│   ││ └● 
│   ││  ├● Amsterdam; The Hague (seat of government)
│   ││  └● Wellington
│   │└● 
│   │ ├● 
│   │ │├● Managua
│   │ │└● Niamey
│   │ │ └● Abuja
│   │ └● Oslo
│   └● Muscat
└● 
 ├● 
 │├● 
 ││├● 
 │││├● 
 ││││├● 
 │││││├● 
 ││││││├● 
 │││││││├● Islamabad
 │││││││└● 
 │││││││ ├● Melekeok
 │││││││ └● Panama City
 ││││││└● 
 ││││││ ├● Port Moresby
 ││││││ └● Asuncion
 │││││└● Lima
 ││││└● 
 ││││ ├● Manila
 ││││ └● 
 ││││  ├● Warsaw
 ││││  └● Lisbon
 │││└● Doha
 ││└● 
 ││ ├● 
 ││ │├● Bucharest
 ││ │└● 
 ││ │ ├● Moscow
 ││ │ └● Kigali
 ││ └● 
 ││  ├● 
 ││  │├● 
 ││  ││├● 
 ││  │││├● 
 ││  ││││├● 
 ││  │││││├● 
 ││  ││││││├● Basseterre
 ││  ││││││└● Castries
 ││  │││││└● Kingstown
 ││  ││││└● 
 ││  ││││ ├● Apia
 ││  ││││ └● 
 ││  ││││  ├● San Marino
 ││  ││││  └● Sao Tome
 ││  │││└● Riyadh
 ││  ││└● 
 ││  ││ ├● Dakar
 ││  ││ └● 
 ││  ││  ├● Belgrade
 ││  ││  └● Victoria
 ││  │└● 
 ││  │ ├● 
 ││  │ │├● Freetown
 ││  │ │└● Singapore
 ││  │ └● 
 ││  │  ├● 
 ││  │  │├● Bratislava
 ││  │  │└● Ljubljana
 ││  │  └● 
 ││  │   ├● 
 ││  │   │├● Honiara
 ││  │   │└● Mogadishu
 ││  │   └● 
 ││  │    ├● Pretoria (administrative); Cape Town (legislative); Bloemfontein (judiciary)
 ││  │    └● Juba (Relocating to Ramciel)
 ││  └● 
 ││   ├● 
 ││   │├● 
 ││   ││├● Madrid
 ││   ││└● Colombo; Sri Jayewardenepura Kotte (legislative)
 ││   │└● 
 ││   │ ├● 
 ││   │ │├● Khartoum
 ││   │ │└● Paramaribo
 ││   │ └● 
 ││   │  ├● 
 ││   │  │├● Mbabane
 ││   │  │└● Stockholm
 ││   │  └● Bern
 ││   └● Damascus
 │└● 
 │ ├● 
 │ │├● 
 │ ││├● 
 │ │││├● 
 │ ││││├● 
 │ │││││├● Taipei
 │ │││││└● Dushanbe
 │ ││││└● Dar es Salaam; Dodoma (legislative)
 │ │││└● 
 │ │││ ├● 
 │ │││ │├● Bangkok
 │ │││ │└● 
 │ │││ │ ├● Nassau
 │ │││ │ └● Banjul
 │ │││ └● 
 │ │││  ├● Lome
 │ │││  └● Nuku'alofa
 │ ││└● 
 │ ││ ├● Port-of-Spain
 │ ││ └● 
 │ ││  ├● Tunis
 │ ││  └● 
 │ ││   ├● 
 │ ││   │├● Ankara
 │ ││   │└● Ashgabat
 │ ││   └● Vaiaku village, Funafuti province
 │ │└● 
 │ │ ├● 
 │ │ │├● Kampala
 │ │ │└● 
 │ │ │ ├● Kyiv
 │ │ │ └● 
 │ │ │  ├● 
 │ │ │  │├● Abu Dhabi
 │ │ │  │└● London
 │ │ │  └● Washington D.C.
 │ │ └● 
 │ │  ├● Montevideo
 │ │  └● Tashkent
 │ └● 
 │  ├● 
 │  │├● 
 │  ││├● Port-Vila
 │  ││└● Vatican City
 │  │└● Caracas
 │  └● Hanoi
 └● 
  ├● Sanaa
  └● 
   ├● Lusaka
   └● Harare

Traversal of all key-value pairs in the tree:
Afghanistan -> Kabul
Albania -> Tirane
Algeria -> Algiers
Andorra -> Andorra la Vella
Angola -> Luanda
Antigua and Barbuda -> Saint John's
Argentina -> Buenos Aires
Armenia -> Yerevan
Australia -> Canberra
Austria -> Vienna
Azerbaijan -> Baku
Bahrain -> Manama
Bangladesh -> Dhaka
Barbados -> Bridgetown
Belarus -> Minsk
Belgium -> Brussels
Belize -> Belmopan
Benin -> Porto-Novo
Bhutan -> Thimphu
Bolivia -> La Paz (administrative); Sucre (judicial)
Bosnia and Herzegovina -> Sarajevo
Botswana -> Gaborone
Brazil -> Brasilia
Brunei -> Bandar Seri Begawan
Bulgaria -> Sofia
Burkina Faso -> Ouagadougou
Burundi -> Bujumbura
Cambodia -> Phnom Penh
Cameroon -> Yaounde
Canada -> Ottawa
Cape Verde -> Praia
Central African Republic -> Bangui
Chad -> N'Djamena
Chile -> Santiago
China -> Beijing
Colombia -> Bogota
Comoros -> Moroni
Congo, Democratic Republic of the -> Kinshasa
Congo, Republic of the -> Brazzaville
Costa Rica -> San Jose
Cote d'Ivoire -> Yamoussoukro (official); Abidjan (de facto)
Croatia -> Zagreb
Cuba -> Havana
Cyprus -> Nicosia
Czech Republic -> Prague
Denmark -> Copenhagen
Djibouti -> Djibouti
Dominica -> Roseau
Dominican Republic -> Santo Domingo
East Timor (Timor-Leste) -> Dili
Ecuador -> Quito
Egypt -> Cairo
El Salvador -> San Salvador
Equatorial Guinea -> Malabo
Eritrea -> Asmara
Estonia -> Tallinn
Ethiopia -> Addis Ababa
Fiji -> Suva
Finland -> Helsinki
France -> Paris
Gabon -> Libreville
Georgia -> Tbilisi
Germany -> Berlin
Ghana -> Accra
Greece -> Athens
Grenada -> Saint George's
Guatemala -> Guatemala City
Guinea -> Conakry
Guinea-Bissau -> Bissau
Guyana -> Georgetown
Haiti -> Port-au-Prince
Honduras -> Tegucigalpa
Hungary -> Budapest
Iceland -> Reykjavik
India -> New Delhi
Indonesia -> Jakarta
Iran -> Tehran
Iraq -> Baghdad
Ireland -> Dublin
Israel -> Jerusalem*
Italy -> Rome
Jamaica -> Kingston
Japan -> Tokyo
Jordan -> Amman
Kazakhstan -> Astana
Kenya -> Nairobi
Kiribati -> Tarawa Atoll
Korea, North -> Pyongyang
Korea, South -> Seoul
Kosovo -> Pristina
Kuwait -> Kuwait City
Kyrgyzstan -> Bishkek
Laos -> Vientiane
Latvia -> Riga
Lebanon -> Beirut
Lesotho -> Maseru
Liberia -> Monrovia
Libya -> Tripoli
Liechtenstein -> Vaduz
Lithuania -> Vilnius
Luxembourg -> Luxembourg
Macedonia -> Skopje
Madagascar -> Antananarivo
Malawi -> Lilongwe
Malaysia -> Kuala Lumpur
Maldives -> Male
Mali -> Bamako
Malta -> Valletta
Marshall Islands -> Majuro
Mauritania -> Nouakchott
Mauritius -> Port Louis
Mexico -> Mexico City
Micronesia, Federated States of -> Palikir
Moldova -> Chisinau
Monaco -> Monaco
Mongolia -> Ulaanbaatar
Montenegro -> Podgorica
Morocco -> Rabat
Mozambique -> Maputo
Myanmar (Burma) -> Rangoon (Yangon); Naypyidaw or Nay Pyi Taw (administrative)
Namibia -> Windhoek
Nauru -> no official capital; government offices in Yaren District
Nepal -> Kathmandu
Netherlands -> Amsterdam; The Hague (seat of government)
New Zealand -> Wellington
Nicaragua -> Managua
Niger -> Niamey
Nigeria -> Abuja
Norway -> Oslo
Oman -> Muscat
Pakistan -> Islamabad
Palau -> Melekeok
Panama -> Panama City
Papua New Guinea -> Port Moresby
Paraguay -> Asuncion
Peru -> Lima
Philippines -> Manila
Poland -> Warsaw
Portugal -> Lisbon
Qatar -> Doha
Romania -> Bucharest
Russia -> Moscow
Rwanda -> Kigali
Saint Kitts and Nevis -> Basseterre
Saint Lucia -> Castries
Saint Vincent and the Grenadines -> Kingstown
Samoa -> Apia
San Marino -> San Marino
Sao Tome and Principe -> Sao Tome
Saudi Arabia -> Riyadh
Senegal -> Dakar
Serbia -> Belgrade
Seychelles -> Victoria
Sierra Leone -> Freetown
Singapore -> Singapore
Slovakia -> Bratislava
Slovenia -> Ljubljana
Solomon Islands -> Honiara
Somalia -> Mogadishu
South Africa -> Pretoria (administrative); Cape Town (legislative); Bloemfontein (judiciary)
South Sudan -> Juba (Relocating to Ramciel)
Spain -> Madrid
Sri Lanka -> Colombo; Sri Jayewardenepura Kotte (legislative)
Sudan -> Khartoum
Suriname -> Paramaribo
Swaziland -> Mbabane
Sweden -> Stockholm
Switzerland -> Bern
Syria -> Damascus
Taiwan -> Taipei
Tajikistan -> Dushanbe
Tanzania -> Dar es Salaam; Dodoma (legislative)
Thailand -> Bangkok
The Bahamas -> Nassau
The Gambia -> Banjul
Togo -> Lome
Tonga -> Nuku'alofa
Trinidad and Tobago -> Port-of-Spain
Tunisia -> Tunis
Turkey -> Ankara
Turkmenistan -> Ashgabat
Tuvalu -> Vaiaku village, Funafuti province
Uganda -> Kampala
Ukraine -> Kyiv
United Arab Emirates -> Abu Dhabi
United Kingdom -> London
United States of America -> Washington D.C.
Uruguay -> Montevideo
Uzbekistan -> Tashkent
Vanuatu -> Port-Vila
Vatican City (Holy See) -> Vatican City
Venezuela -> Caracas
Vietnam -> Hanoi
Yemen -> Sanaa
Zambia -> Lusaka
Zimbabwe -> Harare

Counting the number of insertions: 196

Creating a copy of the tree and filtering for capitals beginning with 'T'.
● 
├● 
│├● 
││├● 
│││├● Tirane
│││└● Thimphu
││└● 
││ ├● Tallinn
││ └● Tbilisi
│└● 
│ ├● 
│ │├● 
│ ││├● Tegucigalpa
│ ││└● Tehran
│ │└● 
│ │ ├● Tokyo
│ │ └● Tarawa Atoll
│ └● Tripoli
└● 
 ├● 
 │├● Taipei
 │└● Tunis
 └● Tashkent

Albania -> Tirane
Bhutan -> Thimphu
Estonia -> Tallinn
Georgia -> Tbilisi
Honduras -> Tegucigalpa
Iran -> Tehran
Japan -> Tokyo
Kiribati -> Tarawa Atoll
Libya -> Tripoli
Taiwan -> Taipei
Tunisia -> Tunis
Uzbekistan -> Tashkent

Counting the number of insertions: 12

Creating new tree for capitals beginning with 'T' using a traversal function.
The results should be the same as the filtered copy above.
● 
├● 
│├● 
││├● 
│││├● Tirane
│││└● Thimphu
││└● 
││ ├● Tallinn
││ └● Tbilisi
│└● 
│ ├● 
│ │├● 
│ ││├● Tegucigalpa
│ ││└● Tehran
│ │└● 
│ │ ├● Tokyo
│ │ └● Tarawa Atoll
│ └● Tripoli
└● 
 ├● 
 │├● Taipei
 │└● Tunis
 └● Tashkent

Albania -> Tirane
Bhutan -> Thimphu
Estonia -> Tallinn
Georgia -> Tbilisi
Honduras -> Tegucigalpa
Iran -> Tehran
Japan -> Tokyo
Kiribati -> Tarawa Atoll
Libya -> Tripoli
Taiwan -> Taipei
Tunisia -> Tunis
Uzbekistan -> Tashkent

Counting the number of insertions: 12

Doing a node by node comparison of the two previous trees: they are equivalent.

A representation of the previous tree showing key bits:
010 
  ├0 
  │├0 
  ││├0 
  │││├01011011000110001001100001011011100110100101100001 Tirane
  │││└100110100001110101011101000110000101101110 Thimphu
  ││└1 
  ││ ├01011100110111010001101111011011100110100101100001 Tallinn
  ││ └11011001010110111101110010011001110110100101100001 Tbilisi
  │└1 
  │ ├0 
  │ │├0 
  │ ││├001101111011011100110010001110101011100100110000101110011 Tegucigalpa
  │ ││└1011100100110000101101110 Tehran
  │ │└1 
  │ │ ├001100001011100000110000101101110 Tokyo
  │ │ └101101001011100100110100101100010011000010111010001101001 Tarawa Atoll
  │ └10001101001011000100111100101100001 Tripoli
  └1010 
      ├0011 
      │   ├0000101101001011101110110000101101110 Taipei
      │   └101010110111001101001011100110110100101100001 Tunis
      └1011110100110001001100101011010110110100101110011011101000110000101101110 Tashkent

Creating another copy of the tree and filtering for countries beginning with 'T'.
Taiwan -> Taipei
Tajikistan -> Dushanbe
Tanzania -> Dar es Salaam; Dodoma (legislative)
Thailand -> Bangkok
The Bahamas -> Nassau
The Gambia -> Banjul
Togo -> Lome
Tonga -> Nuku'alofa
Trinidad and Tobago -> Port-of-Spain
Tunisia -> Tunis
Turkey -> Ankara
Turkmenistan -> Ashgabat
Tuvalu -> Vaiaku village, Funafuti province

Counting the number of countries that begin with 'T': 13

Counting again using a prefix filter: 13
done

General

• Deal with TODO lists in comments.
• Document all internal code.
• Expand user documentation with a tutorial and explanations of different uses.
• Eventually profile and benchmark code.
• Optimize (for performance and fun).

node.h

• Compare performance of stack-based and recursive variants and read up on overhead of recursive functions. Implement recursive functions alongside current versions if there is any worthwhile advantage.