Partial Specialization Question

5cript

Ich möchte etwas in der folgenden Art realisieren:

template <unsigned A, unsigned B>
struct Blatt
{
    struct Code { enum : unsigned { value = A }; };
    struct Count { enum : unsigned { value = B }; };
};

template <typename LhsT, RhsT, unsigned Count>
struct Knoten
{
    struct Left { using type = LhsT }; // left path in binary tree
    struct Right { using type = RhsT }; // right path in binary tree
    struct Count { enum : unsigned { value = Count; } };
};

template <typename Tree>
class CodeGenerator
{
// fehler?
};

template<>
class CodeGenerator <Blatt<EGAL, EGAL>>
{
// metaprogramm A
};

template<>
class CodeGenerator <Knoten<EGAL, EGAL, EGAL>>
{
// metaprogramm B
};

CodeGenerator läuft über einen binären Baum, der aus Knoten und Blättern besteht. Jetzt möchte ich Blätter anders als Knoten behandeln und die Blätter als Abbruchbedingung der Rekursion verwenden.

Ich hoffe mein Konstrukt ist nicht fundamentalfalsch angelegt -.-

Allerdings ist mein Template Spezialisierungs Skill nicht hoch genug um den obigen Zauber zu casten :<

[Randinfo: Das hier ist ein Projekt um Boost::MPL zu lernen. Es wird eine Huffmancodierung aus einem Beispieltext erstellt. Der Baum wird korrekt aufgebaut und "CodeGenerator" soll nun wieder von Wurzel bis Blatt runterlaufen und dabei eine CodeSequence erstellen.]

EDIT: obiger code ist hier im Forum entstanden, da der tatsächliche Code deutlich komplizierter ist.

Columbo

Etwa so?

template<unsigned A, unsigned B>
class CodeGenerator <Blatt<A,B>>
{
    // [...]
};

template <typename LhsT, typename RhsT, unsigned Count>
class CodeGenerator <Knoten<LhsT, RhsT, Count>>
{
    // [...]
};

Ich würde übrigens mehrere Knoten/Blätter in einem Knoten wenn möglich durch variadische Templates behandeln.

5cript

Arcoth schrieb:

Etwa so?

template<unsigned A, unsigned B>
class CodeGenerator <Blatt<A,B>>
{
    // [...]
};
 
template <typename LhsT, typename RhsT, unsigned Count>
class CodeGenerator <Knoten<LhsT, RhsT, Count>>
{
    // [...]
};

Ja theoretisch schon, aber Lhs, Rhs und Count müssten aus
Tree (siehe mein Beispiel Code) hervorgehen. (EDIT: und A, Das ginge nur wenn die Parameter automatisch deduziert werden könnten.

Arcoth schrieb:

Ich würde übrigens mehrere Knoten/Blätter in einem Knoten wenn möglich durch variadische Templates behandeln.

Was meinst du damit? "mehrere Knoten/Blätter in einem Knoten" bei einem binären Baum? kann doch gar nicht. Habe dich vermutlich falsch verstanden.

EDIT:

Beispiel:

Tree=
Knoten<
    Knoten<
        Blatt<?, ?>, 
        Knoten<
            Blatt<?, ?>, 
            Blatt<?, ?>
        >
    >
>

Columbo

Das ginge nur wenn die Parameter automatisch deduziert werden könnten.

Und warum können die Argumente nicht deduziert werden? Kannst du mal ein klitzekleines Testprogramm liefern?

"mehrere Knoten/Blätter in einem Knoten" bei einem binären Baum? kann doch gar nicht. Habe dich vermutlich falsch verstanden.

Das binär hab' ich überlesen, damit bin ich derjenige der nicht verstanden hat.

5cript

Arcoth schrieb:

Kannst du mal ein klitzekleines Testprogramm liefern?

Ja ein Augenblick

5cript

Es kann sein, dass der Inhalt von CodeGenerator noch nicht Sinn ergibt.
Ich war da mittendrin im Gedankenprozess.

#include <boost/mpl/vector.hpp>
#include <boost/mpl/push_back.hpp>

namespace mpl = boost::mpl;

template <typename LhsT, // another node or a leaf
          typename RhsT, // another node or a leaf
          unsigned CountV> // the occurence count or probability (whichever you like to use)
struct BinaryTreeNode
{
    struct Left { using type = LhsT; }; // 1 side
    struct Right { using type = RhsT; }; // 0 side

    // Count is an internal convention for the probabilty
    struct Count { static constexpr unsigned value = CountV; };
};

template <char SymbolV, unsigned CountV>
struct Codeword
{
    struct Symbol { static constexpr unsigned value = SymbolV; };
    struct Count { static constexpr unsigned value = CountV; };
};

// for leaves
template <typename TreeT,
          typename CodeAccumulatorT>
struct CodeGenerator
{
	using type = TreeT; // which is of type "Codeword"

    struct Code { using type = CodeAccumulatorT; };
};

// for nodes
template <typename TreeT,
          typename CodeAccumulatorT>
struct CodeGenerator <?> // <- this
{
	struct Left // subtree
	{
		using type = typename CodeGenerator <typename TreeT::Left::type,
											 typename mpl::push_back <CodeAccumulatorT, mpl::bool_<1>::type>::type
											>::type;
	};
	struct Right // subtree
	{
		using type = typename CodeGenerator <typename TreeT::Right::type,
											 typename mpl::push_back <CodeAccumulatorT, mpl::bool_<0>::type>::type
											>::type;
	};

	using type = TreeT;
};

// hier ein generierter Baum:
// kommt aus "NodeFactory" (hier nicht mit drin um es kurz zu halten)
using Tree =
    boost::mpl::v_item<BinaryTreeNode<BinaryTreeNode<BinaryTreeNode<Codeword<(char)117, 5u>, BinaryTreeNode<BinaryTreeNode<Codeword<(char)98,
	1u>, Codeword<(char)112, 1u>, 2u>, Codeword<(char)106, 3u>, 5u>, 10u>, BinaryTreeNode<Codeword<(char)108, 6u>, Codeword<(char)115, 6u>,
	12u>, 22u>, BinaryTreeNode<BinaryTreeNode<BinaryTreeNode<Codeword<(char)111, 3u>, Codeword<(char)100, 3u>, 6u>, Codeword<(char)101, 8u>,
	14u>, BinaryTreeNode<BinaryTreeNode<Codeword<(char)97, 4u>, Codeword<(char)105, 4u>, 8u>, BinaryTreeNode<BinaryTreeNode<Codeword<(char)39,
	2u>, Codeword<(char)109, 2u>, 4u>, Codeword<(char)114, 5u>, 9u>, 17u>, 31u>, 53u>, boost::mpl::vector0<mpl_::na>, 0>::type;

using result = CodeGenerator <Tree, mpl::vector <>>::type;

int main()
{
}

camper

// for nodes
template <typename LhsT, typename RhsT, unsigned CountV,
          typename CodeAccumulatorT>
struct CodeGenerator <BinaryTreeNode<LhsT,RhsT,CountV>,CodeAccumulatorT>

5cript

... ok (getestet, code abgeändert und läuft)

Ich glaube ich verstehe Spezialisierung jetzt besser als vorher.

EDIT: es läuft jetzt auch komplett. Ich danke für die Hilfe.
Mit Template Meta Programmierung macht das Programmieren wieder Spaß!