String To Constant String Dictionary

string_to_const_string.h and string_to_const_string.c provide an example of a dictionary that maps strings to constant strings.¹ The header file sets up the the necessary definitions and imports the rabbit tree headers. The body then generates a mapping of countries to their capitals and shows off some of the different functions such as tree traversal and filtering.

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
done

Installation

Rabbit Tree does not generate a compiled library. The headers are installed as they are and should be included in source files to generate code.

Installation should be as simple as:

mkdir build
cd build
cmake .. -DCMAKE_INSTALL_PREFIX=/usr
make
make install DESTDIR=/

Obviously the above should be adapted to work with your package manager. If Doxygen is present, documentation will be installed along with the header.

I'll make this an option later. If you can't wait, either submit some code and/or nag me about it.

Tests

Run `scripts/cmake_test.sh' to build the included examples and test them. The test compares the output of the examples to the expected output, but it may differ on your system. If it does, the test will report a false failure.

Examples

The files included in the examples directory along with the documentation should be enough to get you started.

2013-02-09

• Added RBT_KEY_DATA_T.
• Changed RBT_TRAVERSE_WITH_KEY_FUNCTION_T to accept RBT_KEY_DATA_T instead of separate parameters for nodes, keys and bits.
• Restructured some traversal functions to accept RBT_KEY_DATA_T.
• Added some missing macro definitions and fixed other macro inconsistencies.
• Added RBT_FILTER_WITH_KEY().
• Updated examples.

TODO