Need help with Trie insertions, I am currently working on a DSA specialization on Coursera, Strings course

I am trying the insertion operation in a Trie and a read operation for the below implementation I am having trouble with insertion.

import java.util.*; class node{ public int val; public node ptrs[]; node(){     this.val =0;     ptrs = new node[26];     for (node ptr : ptrs) {         ptr = null;     }   }     } class Tree{ public node root = new node(); public int pass =0; void insert(String s) {     node trv = root;     for (int i = 0; i < s.length(); i++) {         if (trv.ptrs[s.charAt(i) - 'A'] == null) {             trv.ptrs[s.charAt(i) - 'A'] = new node();             trv.val = ++pass;           //  System.out.println(s.charAt(i)+" val : "+trv.val);         }          trv = trv.ptrs[s.charAt(i) - 'A'];     } } private void visit(node trv){     for(int i =0;i<26;i++){         if(trv.ptrs[i]!=null){             System.out.println((char)(i+'A')+" : "+trv.val);             visit(trv.ptrs[i]);         }     } } void call(){     this.visit(root);  }  } public class trie {   public static void main(String[] args) {     Scanner sc = new Scanner(System.in);     int n = sc.nextInt();     Tree t = new Tree();     while (n-- > 0) {         String s = sc.next();         t.insert(s);     }     t.call();     sc.close();  } } 

my output :

3 ATAGA ATC GAT A : 7 T : 2 A : 6 G : 4 A : 5 C : 6 G : 7 A : 8 T : 9 

expected output :

3 ATAGA ATC GAT A : 1 T : 2 A : 3 G : 4 A : 5 C : 6 G : 7 A : 8 T : 9 

Does every specialization of Craft you take get the class skill bonus, or just the first?

Suppose I’m playing a character with Craft as a class skill. I put 1 rank in it, select Weaponsmith to fit my background and end up with Craft (Weapons) +4. Now, if I later decide I want to be able to make bows and arrows, do I also get another +3 bonus on Craft (Bows) when I invest a new rank? There are different kinds of craft, just like there are different kinds of knowledge, but the class skill bonus for craft is completely unspecified.

Generalization / Specialization. When and where???

I've always been of the opinion that you should generalize your functions only when it's required and specialize when it is only being used for one use.

This is under the assumption that you do not see any other use for the function in the foreseeable future. If you know you'll need it for other things later then I feel you should generalize just to save yourself the trouble later on. But generalizing without any foreseeable future case but making the assumption that there might be seems…

Generalization / Specialization. When and where???

Does magic subschool matter for Spell Specialization?

Spell Specialization says:

Select one spell of a school for which you have taken the Spell Focus feat. Treat your caster level as being two higher for all level-variable effects of the spell.

Every time you gain an even level in the spellcasting class you chose your spell from, you can choose a new spell to replace the spell selected with this feat, and that spell becomes your specialized spell.

Does the feat only matter for the school or does the subschool matter as well?

Example: I have Spell Focus Evocation. If I use Spell Specialization on Magic Missile, school Evocation [force], can I switch it to Fireball, school Evocation [fire]?

Specialization vs generalization in programming languages

Consider two programming languages:

  • a general-purpose one $ L_{G}$ (for example C++)
  • domain-specific language $ L_{S}$ (for example mathematica)

Note that both of them are Turing complete.


Now imagine that you want to create a new language that can combine the advantages of $ L_{G}$ and $ L_{S}$ . If you don’t want to create a new language from scratch you are left with two options:

  • Option A: specialize $ L_{G}$ to make it handle the constructs of $ L_{S}$ (basically create what is called an Embedded Domain Specific Language)
  • Option B: generalize $ L_{S}$ to make it handle the constructs of $ L_{G}$

Intuitively, option A seems simpler, and the most likely to work in practice. However, I would like to go beyond this intuition and I was wondering:

  • Is there a way to formalize this problem (typically in theoretical computer science / logic / type theory)?
  • Do you know of any reference / paper / book that could back this intuition up?

Emulating Virtual Registers by experimenting with unions, bitfields, structs and template specialization

To get a better handle and understanding of how bitfields, unions, and the byte alignment of structures work, I’m simulating a template Register structure.

The requirements of my Register are as follows:

  • Default size or width of a register is 8bits or 1 byte
  • Larger size registers must be a multiple of 8
  • Registers are less than or equal 64 bits in size or 8 bytes.

I have a set of structures which build of each other in a cascading effect starting from the base unit of a Byte down to a QWord.

My Registers are template specializations.

Here is my code so far:

-main.cpp-

#include <iostream> #include "Register.h"  int main() {      Register r1;     std::cout << "Register<8>\n";     for (i8 i = 0; i < 21; i++) {         r1.register_.value_ = i;         // make sure to cast to a larger size due to int8_t being defined by char.         std::cout << static_cast<std::uint16_t>(r1.register_.value_) << "\n";     }     std::cout << '\n';      // Note: my output shows: 0 1 1 0 0 1 0 0      // as I am running on an intel x86-64 bit Quad Core Extreme     // this is expected since my machine is little endian.     r1.register_.value_ = static_cast<std::int8_t>( 38 );     std::cout << "Bit Values\n";     std::cout << static_cast<bool>(r1.register_.b0) << " "                << static_cast<bool>(r1.register_.b1) << " "                << static_cast<bool>(r1.register_.b2) << " "                << static_cast<bool>(r1.register_.b3) << " "               << static_cast<bool>(r1.register_.b4) << " "                << static_cast<bool>(r1.register_.b5) << " "                << static_cast<bool>(r1.register_.b6) << " "                << static_cast<bool>(r1.register_.b7) << "\n\n";      Register<16> r2;     std::cout << "Register<16>\n";     for (i16 i = 0; i < 21; i++) {         r2.register_.value_ = i;         // make sure to cast to a larger size due to int8_t being defined by char.         std::cout << static_cast<std::uint16_t>(r2.register_.value_) << "\n";     }     std::cout << '\n';      Register<32> r3;     std::cout << "Register<32>\n";     for (i32 i = 0; i < 21; i++) {         r3.register_.value_ = i;         // make sure to cast to a larger size due to int8_t being defined by char.         std::cout << static_cast<std::uint32_t>(r3.register_.value_) << "\n";     }     std::cout << '\n';      Register<64> r4;     std::cout << "Register<64>\n";     for (i64 i = 0; i < 21; i++) {         r4.register_.value_ = i;         // make sure to cast to a larger size due to int8_t being defined by char.         std::cout << static_cast<std::uint64_t>(r4.register_.value_) << "\n";     }     std::cout << '\n';      return EXIT_SUCCESS; } 

-output-

Register<8> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  Bit Values 0 1 1 0 0 1 0 0  Register<16> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  Register<32> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  Register<64> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

-Register.h-

#pragma once  #include <vector> // include for typedefs below. typedef std::int8_t  i8; typedef std::int16_t i16; typedef std::int32_t i32; typedef std::int64_t i64;  struct MyByte {     union {         i8 value_;         struct {             i8 b0 : 1;             i8 b1 : 1;             i8 b2 : 1;             i8 b3 : 1;             i8 b4 : 1;             i8 b5 : 1;             i8 b6 : 1;             i8 b7 : 1;         };     }; };  struct MyWord {        // same as short or i16       union {         i16 value_;         union {             MyByte byte_[2];             struct {                 MyByte b0_;                 MyByte b1_;             };         };     }; };  struct MyDWord {       // same as int or i32     union {         i32 value_;          struct {             MyWord w0_;             MyWord w1_;         };          union {             MyByte byte_[4];             struct {                 MyByte b0_;                 MyByte b1_;                 MyByte b2_;                 MyByte b3_;             };         };     }; }; 

I had asked a question on stack overflow about specific output due to behavior of std::int8_t being defined from char that is now fixed.

I have a general idea or grasp on unions, bitfields, byte alignment of structs etc. and I am aware of the complications of bitfields especially when it comes to the endian of a machine.

After my question was answered I had dropped a basic general question in the comment of that answer and my question there was this:

“Do you see any other issues or major concerns with how the bitfield and nameless unions and structs are coupled together?”

I was giving a link to this talk as a reply to my question in which I had watched. It has given me some insight and useful information which now leads me to here with a hand of questions and concerns about my code. Some pertain to the video while others don’t. Before I start to ask my questions or list my concerns, there are a few things about my code or the particular behavior that I am after.

Since I’m simulating what a memory register in a PC would be like I’m trying to model the fact that I had mentioned above about the default and basic unit size is 8 bytes, that a register can be a multiple of 8 and that it has to be in the range of [8,64]. I also like the idea that I would have an 8 bit value at the base level but coupled together with a union and a bitfield only to be able to quickly and easily access the individual bits. And as the size of the registers get larger, the same cascading effect should apply. For example in a 64bit register the actual single value_ is 64 bits or 8 bytes wide in memory, but is coupled with unions to smaller sizes so that one could access a specific DWord, Word or Byte from within a QWord and they can access any one of its 64 bits. This is the behavior of the structure that I am after since I’m trying to model a register in which I would like to use in one of my projects where I’ll be emulating a virtual PC. Now that you have the background. I’ll go a head an get to the questions and concerns.

  • I would like to know what your thoughts and opinions are on the overall structure of my code and its design as is without any influence of my questions and concerns below. Meaning these replies would completely dependent on the code itself and independent of any other proposal.
  • Is there a more simplified and compact way to do this without having to worry about type casting?
  • Since this is a personal project and I’m not overly concerned with the endian atm, however I do feel that it should be addressed early on as opposed to later on if I decide to make this portable, what could be done to minimize or alleviate the checks and conversions due to endian?
  • I would like to have these registers to be trivially copyable. Meaning you can copy one Register<8> to another Register<8> but you wouldn’t be able to copy a Register<16> to a Register<32>. I was thinking of maybe making a function that would allow you to copy from one Register type to another.
  • Would using std::bitfield<> and the use of bitstreams be a viable option?
    • If so how would I be able to incorporate them into this design?
    • If not what is the main cause or reasoning behind why they wouldn’t work? Would this be considered Type Punning and if so, would this be a Good or Bad example; please explain either case along with their pros and cons.
  • There is only one nuisance to me right now and that is the fact that I have to go an extra level deep to retrieve my values for example:

    Register r;

    r.register_.value_ = 12;


  • … Would there be a way to bypass the Registers member to be able to retrieve the value_ member from the inner structures directly? If show how and if not are there any alternatives?

error: non-type partial specialization

Estoy intentando especializar una plantilla para el operator<< de mi clase. Concretamente, especializar para el tipo char:

#include <string>  struct Test {   template< typename T, typename TRAITS = std::char_traits< T > > Test &operator<<( const T * ); };  template< typename TRAITS > Test &Test::operator<< < char, TRAITS >( const char * ) { return *this; } 

Intento una comprobación básica …

g++ -std=c++11 -Wall -Wextra -pedantic -c test.hpp

Y me muestra unos bonitos errores:

error: non-type partial specialization operator<< <char, TRAITS> is not allowed
error: no declaration matches Test& Test::operator<<(const char*)
note: candidate is: template<class T, class TRAITS> Test& Test::operator<<(const T*)

  • ¿ Qué estoy haciendo mal ?
  • ¿ Cómo lo soluciono ?

If read strictly, can an arcanist get free spells from Greater Spell Specialization?

Greater Spell Specialization is a feat published in Ultimate Magic (2011), three years before the arcanist appeared in the Advanced Class Guide.

Unlike a wizard, an arcanist does not expend his prepared spells normally. However, with this feat…

By sacrificing a prepared spell of the same or higher level than your specialized spell, you may spontaneously cast your specialized spell

Can an arcanist get a few more spell slots per day using this feat, losing spells prepared (a bit of utility)? Is this a good choice for an optimized arcanist?

$q$-plane partitions & specialization & interlinks

MacMahon’s enumeration of all plane partions (PP) inside an $ n$ -cube generalizes to $ $ {\tt PP_n}(q)=\prod_{i,j,k=1}^n\frac{1-q^{i+j+k-1}}{1-q^{i+j+k-2}}.$ $ A $ q$ -analogue of symmetric plane partitions in an $ n$ -cube $ $ {\tt SPP_n}(q)=\prod_{i,j=1}^n\frac{1-q^{i+j+n-1}}{1-q^{i+j+i-2}}.$ $ The ordinary self-complementary plane partitions in a $ (2n)$ -cube $ $ {\tt SCPP_{2n}}=\prod_{i=1}^n \frac{(i-1)!^2 (i+2n-1)!^2}{(i+n-1)!^4}.$ $ The following numerical observations fascinated me. Any explicit and pointed reference would be appreciated, if available.

QUESTION. Is there some sort of overarching explanation for these identities? Failing short of that, can you give a combinatorial or conceptual reason? $ $ {\tt SPP_{2n}(-1)=PP_n(1)}, \qquad {\tt PP_{2n}(-1)=SCPP_{2n}}, \qquad {\tt PP_{2n}(-1)=[PP_n(1)]^2}.$ $

I believe that $ {\tt PP_{2n}(-1)=SCPP_{2n}}$ is known.