7 Replies - 5000 Views - Last Post: 12 May 2014 - 11:45 PM

#1 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3453
  • View blog
  • Posts: 10,659
  • Joined: 05-May 12

C++ Challenge: List Elements in Tree by Atomic Number

Post icon  Posted 11 May 2014 - 12:13 AM

The elements in a periodic table have been loaded into a binary tree. The original programmer chose to key the elements by the symbolic names of the elements in anticipation that the most common operation will be to look up elements by their symbol. Suddenly, he has a need to display the elements by atomic number.

The challenge is to printout the contents of the binary tree in atomic weight order without copying the data or references/pointers to the data into a separate data structure (i.e. array, list, tree, etc.), file, or database. Only modify the DumpTreeByAtomicNumber, and add any additional functions, variables, or includes that you may need.

Please remember to post your solutions in spoiler tags so that others can tackle this challenge fresh. You don't need to repost the entire code. You can just post your DumpTreeByAtomicNumber() function and any supporting functions, variables, or includes.

The code and Elements.txt file is below. It requires a C++11 compliant compiler.

#include <iostream>
#include <fstream>
#include <string>
#include <memory>
#include <cstring>
#include <cerrno>
#include <cassert>

using namespace std;

template <class T>
class Tree
{
public:
    Tree()
        : _root()
    {
    }

    void Insert(T & data)
    {
        _root = Insert(_root, data);
    }

    //
    //  The visitor parameter is called by the Traverse() method as each node
    //  in the tree is visited.
    //
    //  The functor or function pointer has a the following signature:
    //
    //      bool visitor(T data)
    //
    //      Parameters:
    //          data    - the data that was stored in the tree by Insert()
    //
    //      Return value:
    //          true indicates that the traversal should continue.
    //          false indicates that the traversal should stop.
    //
    template <typename Visitor>
    void Traverse(Visitor visitor)
    {
        Traverse(_root, visitor);
    }

private:
    struct Node
    {
        T                   _data;
        shared_ptr<Node>    _left;
        shared_ptr<Node>    _right;

        Node(T & data)
            : _data(data)
            , _left()
            , _right()
        {
        }
    };

    shared_ptr<Node> _root;

    shared_ptr<Node> Insert(shared_ptr<Node> node, T & data)
    {
        if (!node)
            return make_shared<Node>(data);

        if (data < node->_data)
            node->_left = Insert(node->_left, data);
        else
            node->_right = Insert(node->_right, data);
        return node;
    }

    template <typename Visitor>
    bool Traverse(shared_ptr<Node> node, Visitor visitor)
    {
        return !node ||
               (    Traverse(node->_left, visitor) &&
                    visitor(node->_data) &&
                    Traverse(node->_right, visitor));
    }
};

struct Element
{
    int     Number;
    string  Symbol;
    string  Name;

    Element()
        : Number(0)
        , Symbol()
        , Name()
    {
    }

    int operator<(const Element & rhs)
    {
        return this->Symbol < rhs.Symbol;
    }
};

bool LoadElementsIntoTree(std::string filename, Tree<Element> & tree);
void DumpTreeBySymbol(Tree<Element> & tree);
void DumpTreeByAtomicNumber(Tree<Element> & tree);

int main ()
{
    Tree<Element> tree;
    if (LoadElementsIntoTree("Elements.txt", tree))
    {
        DumpTreeBySymbol(tree);
        DumpTreeByAtomicNumber(tree);
    }
    return(0);
}

bool LoadElementsIntoTree(std::string filename, Tree<Element> & tree)
{
    cout << "Loading elements from " << filename << "..." << endl;
    assert(!filename.empty());
    ifstream input(filename.c_str());

    if (!input)
    {
        perror(filename.c_str());
        return false;
    }

    int count = 0;
    Element temp;

    while (input >> temp.Name >> temp.Symbol >> temp.Number)
    {
        cout << temp.Name
             << " (" << temp.Symbol << ") "
             << temp.Number
             << endl;
        count++;

        tree.Insert(temp);
    }

    if (input.eof())
    {
        cout << "Loaded " << count << " elements" << endl;
    }
    else
    {
        cerr << "Encountered error reading line "
             << count + 1 << ": "
             << strerror(errno)
             << endl;
        return false;
    }

    return true;
}

void DumpTreeBySymbol(Tree<Element> & tree)
{
    printf("Element by Symbol:\n");
    tree.Traverse([] (Element & element)
                  {
                      cout << element.Symbol << ":"
                           << element.Name << " "
                           << element.Number
                           << endl;
                      return true;
                  });
}

void DumpTreeByAtomicNumber(Tree<Element> & tree)
{
    // TODO: Implement me!
}



Vanadium	V	23
Berkelium	Bk	97
Radon	Rn	86
Carbon	C	6
Actinium	Ac	89
Antimony	Sb	51
Mercury	Hg	80
Radium	Ra	88
Europium	Eu	63
Rutherfordium	Rf	104
Scandium	Sc	21
Phosphorus	P	15
Boron	B	5
Germanium	Ge	32
Lanthanum	La	57
Barium	Ba	56
Technetium	Tc	43
Curium	Cm	96
Neon	Ne	10
Holmium	Ho	67
Rhodium	Rh	45
Arsenic	As	33
Roentgenium	Rg	111
Seaborgium	Sg	106
Lead	Pb	82
Sulfur	S	16
Nickel	Ni	28
Nitrogen	N	7
Ununquadium	Uuq	114
Aluminum	Al	13
Ytterbium	Yb	70
Copernicium	Cp	112
Ununpentium	Uup	115
Erbium	Er	68
Fluorine	F	9
Bohrium	Bh	107
Yttrium	Y	39
Americium	Am	95
Hassium	Hs	108
Rhenium	Re	75
Oxygen	O	8
Tin	Sn	50
Beryllium	Be	4
Einsteinium	Es	99
Krypton	Kr	36
Hydrogen	H	1
Promethium	Pm	61
Xenon	Xe	54
Indium	In	49
Bromine	Br	35
Ununseptium	Uus	117
Gold	Au	79
Iodine	I	53
Cobalt	Co	27
Uranium	U	92
Hafnium	Hf	72
Mendelevium	Md	101
Californium	Cf	98
Thallium	Tl	81
Astatine	At	85
Helium	He	2
Silicon	Si	14
Thulium	Tm	69
Meitnerium	Mt	109
Ununoctium	Uuo	118
Praseodymium	Pr	59
Lithium	Li	3
Lawrencium	Lr	103
Cesium	Cs	55
Protactinium	Pa	91
Zinc	Zn	30
Ununhexium	Uuh	116
Rubidium	Rb	37
Dysprosium	Dy	66
Argon	Ar	18
Polonium	Po	84
Strontium	Sr	38
Terbium	Tb	65
Francium	Fr	87
Iron	Fe	26
Calcium	Ca	20
Fermium	Fm	100
Chromium	Cr	24
Platinum	Pt	78
Palladium	Pd	46
Tantalum	Ta	73
Molybdenum	Mo	42
Plutonium	Pu	94
Titanium	Ti	22
Ruthenium	Ru	44
Lutetium	Lu	71
Samarium	Sm	62
Zirconium	Zr	40
Niobium	Nb	41
Dubnium	Db	105
Selenium	Se	34
Nobelium	No	102
Manganese	Mn	25
Copper	Cu	29
Potassium	K	19
Cadmium	Cd	48
Darmstadtium	Ds	110
Tellurium	Te	52
Neptunium	Np	93
Sodium	Na	11
Gallium	Ga	31
Iridium	Ir	77
Silver	Ag	47
Neodymium	Nd	60
Magnesium	Mg	12
Tungsten	W	74
Gadolinium	Gd	64
Osmium	Os	76
Chlorine	Cl	17
Thorium	Th	90
Bismuth	Bi	83
Ununtrium	Uut	113
Cerium	Ce	58



Updates:
- Noted that you'll need a C++ compiler that supports C++11. For those with C++98 compliant compilers, see code in spoiler below.
- Made code compile cleanly for g++ if you turn on all the warning, not just -Wall and -Wpedantic. Thanks to jimblumberg
- References or pointers to the data should also not be put into another data structure.

C++98 code:
Spoiler

This post has been edited by Skydiver: 11 May 2014 - 08:27 PM
Reason for edit:: Updated code to compile cleanly. More details.


Is This A Good Question/Topic? 1
  • +

Replies To: C++ Challenge: List Elements in Tree by Atomic Number

#2 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2240
  • View blog
  • Posts: 9,410
  • Joined: 29-May 08

Re: C++ Challenge: List Elements in Tree by Atomic Number

Posted 11 May 2014 - 07:16 AM

I'd implement it like so in pseudo C#

Spoiler

This post has been edited by AdamSpeight2008: 11 May 2014 - 07:48 AM

Was This Post Helpful? 1
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3453
  • View blog
  • Posts: 10,659
  • Joined: 05-May 12

Re: C++ Challenge: List Elements in Tree by Atomic Number

Posted 11 May 2014 - 07:15 PM

Excellent rules lawyering. :) Serves me right for trying to write a challenge description at 3:00AM. I've updated the challenge description to also exclude copying references or pointers to the data into another data structure.

But even without that restriction, note that Node was private to Tree and you wouldn't have access to the Node pointers.
Was This Post Helpful? 0
  • +
  • -

#4 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 651
  • View blog
  • Posts: 2,224
  • Joined: 31-December 10

Re: C++ Challenge: List Elements in Tree by Atomic Number

Posted 12 May 2014 - 08:59 AM

I was wondering if that was considered copying or not. I figured it was kind of cheating...

*EDIT*:
Just so you know, I got a warning about the strerror() function and it recommends using strerror_s().

This post has been edited by vividexstance: 12 May 2014 - 09:01 AM

Was This Post Helpful? 0
  • +
  • -

#5 jimblumberg  Icon User is online

  • member icon


Reputation: 3987
  • View blog
  • Posts: 12,300
  • Joined: 25-December 09

Re: C++ Challenge: List Elements in Tree by Atomic Number

Posted 12 May 2014 - 09:58 AM

Quote

Just so you know, I got a warning about the strerror() function and it recommends using strerror_s().

My first suggestion is to find a more standard compliant compiler, and if that is not an option I recommend you following the steps mentioned in the following link. Compiler Warning (level 3) C4996 and disable these bogus warnings.

Quote

Some CRT and Standard C++ Library functions have been deprecated in favor of new, more secure functions. For more information on which function to use instead, see the documentation for the deprecated function in the error message. To turn off CRT deprecation warnings, define _CRT_SECURE_NO_WARNINGS. For more information about deprecated functions, see Security Features in the CRT and Safe Libraries: C++ Standard Library.



Jim

This post has been edited by jimblumberg: 12 May 2014 - 11:14 AM

Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2240
  • View blog
  • Posts: 9,410
  • Joined: 29-May 08

Re: C++ Challenge: List Elements in Tree by Atomic Number

Posted 12 May 2014 - 10:15 AM

The original challenge never mention that using data structure of references was disallowed. So I exploited the loophole.
Was This Post Helpful? 0
  • +
  • -

#7 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 769
  • Joined: 27-June 09

Re: C++ Challenge: List Elements in Tree by Atomic Number

Posted 12 May 2014 - 10:31 AM

Interesting, I have never seen syntax like this in c++. It looks very lambda-esque. Is the following similar to what you are looking for? (I don't have access to a compiler at the moment, and my syntax is probably off).

Spoiler

This post has been edited by mojo666: 13 May 2014 - 12:19 AM

Was This Post Helpful? 0
  • +
  • -

#8 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 762
  • View blog
  • Posts: 2,214
  • Joined: 20-March 10

Re: C++ Challenge: List Elements in Tree by Atomic Number

Posted 12 May 2014 - 11:45 PM

Well probably not very good,

but it works.


Spoiler

This post has been edited by Skydiver: 14 May 2014 - 09:08 PM
Reason for edit:: Put code in code tags.

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1