PHP Form Builder Class I would like my form generator class to be reviewed. I want to know about the following topics:

Is this efficient?
Does this have any flaws?
Is this using the concepts in the proper way?
Are there any security issues?
Is my coding style correct?

<?php
class FormBuilder
{
    public function buildForm($method, $action, $name = null, array $fields)
    {
        $form  = "<form method=\"$method\" action=\"$action\"";
        $form .= empty($name) ? ">" : " name=\"$name\">\n";
        for($i = 0; $i < count($fields); $i++) {
            $form .= $this->buildField($fields[$i]['field'],
                                       $fields[$i]['type'],
                                       $fields[$i]['name'],
                                       empty($fields[$i]['placeholder']) ? '' : $fields[$i]['placeholder'],
                                       empty($fields[$i]['style']) ? '' : $fields[$i]['style'],
                                       empty($fields[$i]['options']) ? '' : $fields[$i]['options'],
                                       empty($fields[$i]['value']) ? '' : $friends[$i]['value']
            );
        }
        $form .= "</form>";
        return $form;
    }
    public function buildField($field, $type, $name, $placeholder = null, $style = null, $options = null, $value = null)
    {
        switch($field)
        {
            case 'input':
                $fieldHTML  = " <input type=\"$type\" name=\"$name\"";
                $fieldHTML .= empty($placeholder) ? "" : " placeholder=\"$placeholder\" ";
                $fieldHTML .= empty($style) ? "" : " style=\"$style\" ";
                $fieldHTML .= ">\n";
                break;
            case 'textbox':
                $fieldHTML  = " <textbox type=\"$type\" name=\"$name\"";
                $fieldHTML .= empty($placeholder) ? "" : " placeholder=\"$placeholder\" ";
                $fieldHTML .= empty($style) ? "" : " style=\"$style\" ";
                $fieldHTML .= "></textbox>\n";
                break;
            case 'submit':
                $fieldHTML  = " <input type=\"$type\" name=\"$name\"";
                $fieldHTML .= empty($style) ? "" : " style=\"$style\" ";
                $fieldHTML .= empty($value) ? "" : " value=\"$value\" ";
                $fieldHTML .= ">\n";
                break;
            default:
                $fieldHTML = "Failed to Build Field. Please make sure that you have set the field properties correctly.<br />";
                break;
        }
        return $fieldHTML;
    }
}

Example:

$formBuilder = new FormBuilder();

echo $formBuilder->buildForm('post',
                        '',
                        'some_name',
                        array(
                            array(
                                'field' => 'input',
                                'type'  => 'text',
                                'name'  => 'name',
                                'placeholder' => 'placeholder',
                                'style' => 'color: red;',
                                'options' => ''
                            ),
                            array(
                                'field' => 'submit',
                                'type'  => 'submit',
                                'name'  => 'send',
                                'placeholder' => '',
                                'style' => 'color: red;',
                                'options' => ''
                            )
                        )
);

?>

Right, a short and simple answer to each of your questions, for now. I'll be expanding on each of the issues through updates:

Is it efficient
Define efficient. If by that, you mean: is it fast, then yes, it probably is. Not as fast as non OO code, but faster than most form builders out there.
If by efficient, however you mean: portable, easy to use (as in clear API), robust and flexible then no. It's not. You can't handle nested forms, validators and to use this code, you need to know what type of array this class expects. Programming by array is not the way to go.

Are there flaws?
Yes, there are, apart from those mentioned above, some other omissions/flaws:

buildField is public, but contrary to what I'd assume, it is incapable of adding fields to the form. The buildForm is a one-shot deal: it returns an HTML string, that is, to all intents and purposes, static.
Stringing together markup is tedious, horrible to debug, and equally pointless to test. If things do go worng, it'll probably result in malformed markup, and the source of the problem will be hard to track.
Forms and ajax are used very often. Ajax implies JS, which in turn implies using meaningful selectors: I can't set ID's here, though. That's an issue!

More to come, because there are a lot of things that need addressing, outside of these primary issues.

Good use of concepts?
IMHO, no. A class should have only 1 job, and yours does. It has only 1 job: to generate a string. But HTML is not just any string: there's grammar and rules involved. It's part of a DOM. PHP ships with the DOMDocument class (and all of its derivatives. That class ensures the markup is valid. You can also add elements to an existing dom, assign and remove attributes, ... the works. Use helper classes. Generating markup is done using objects, too.

Are there any security issues?
Yes, quite a few. If I pass '"><script>location.href=\'spam-site-url\';</script>' as the value for the form name, then the resulting markup will be:

<form method="post" name=""><script>location.url='spam-site-url';</script>

XSS attacks, through any of the fields is easily done

Coding style

Looks alright, apart from the closing ?> tag. According to the official docs, it is optional and even discouraged in PHP-only scripts. But when it comes to coding style/conventions, why not see for yourself if you adhere to them: the coding standards are open to anyone, read through them, and apply them to your code.

Suggestion
If you don't want to use one of the many forbuilders that have been written before, then that's your right. But that doesn't mean you should close your eyes to what they have to offer, and how they do what they do. Check out the Symfony2 form component, or the Formbuilder of Zend, or any of the other frameworks. See how they do things, "borrow" the ideas you like, add your own, and if you find the time: try giving back to the respective communities by contributing...

Update

Is it efficient

Seeing as you're writing object, I'm going to interpret efficiency in an OO context: efficient code abstracts the nitty gritty, while allowing the user to customize almost every aspect through a clean, and concistent API, all the time being reasonable certain that the end-result will be valid, usable markup.

To acchieve all this, you can't just string together markup like you are doing now. OO is about hierarchy, dependency and inheritance.
Think of a form, what defines it behaviour (ie is inherent to the form), and what does it contain (most likely optional).

A form is an element, that uses attributes to define its behaviour. A form element consists of zero or more child elements (inputs, selects, buttons, textarea's, but also fieldsets, labels, etc...). All of these child elements belong to the form, but have their own behaviours (attributes). Some elements, like select, or fieldset can, and often will consist of more than one child element.
Adding these children, or setting their attributes is something that one might do as you go along (ie fetching select options from the db, adding options after constructing the base form). This means that addField has to be matched with a getField method, to get a reference to an existing form element, so the user can alter it.

It is also likely to happen that, for whatever reason, the user wants to pre-set some values, just as it is likely for the user to add form validation, and a method to validate the form, sanitize the submitted data and extract it, either as an array or an object.
All the while, the form should be mutable: it has to be possible to add and remove elements on the fly. That's a lot of work, so I'm not going to write a fully fledged example of how to implement this. Instead, here's how I'd start:

Write 2 distinct classes: FormElement and FormBuilder. The latter takes instances of FormElement, and adds them to its internal FormElement that represents the actual <form> tag.
the FormElement class needn't be used by the user, provided the FormBuilder has some methods like addElement, getElement, removeElement, and so on
the FormBuilder could then be altered, to use FormValidator elements, attached to each of its elements. Once you do this, the form should also implement getFormData and setAll methods, to process and pre-set the form elements.
By this time, you ought to realize that you no longer have a formBuilder class. Instead, you are building a form module. Which opens up the possibility of adding model mapping, form events, plugins, helpers and all that...

Now, notice that I said that a <form> tag is a FormElement, but that it's contained within the FormBuilder. That is because, unlike otehr FormElements, the form needs another abstraction layer. It's a DOM element that contains all of the input fields within the form. It stands to reason, then, that this will be the FormElement that the user will want to use for form validation, and extracting data. This, too, requires a consistent and tidy API, if you want a form module worth using. I therefore suggest to create a third class: class Form extends FormElement, where all of the bulk form interactions live.

Adding FormElements should be as simple as this:

$element = $builder->addElement(
    FormBuilder::ELEMENT_TEXT,//type
    array(
        'id'    => 'txtId',
        'name'  => 'txtName',
        'value' => ''
    )
);//creates DOMNode, adds it to form, and returns a reference to the newly created node
$element->getAttribute('value')->value ='new value value';//or nodeValue

As you can see, I can alter nodes I've added to the form, but it looks kind of faffy and messy. That's why I suggest you wrap the DOMNodes that make up your form in a generic FormElement class, and give it methods like setValue:

public function setValue($val)
{
    //$this->node === the raw DOMNode instance
    $attr = $this->node->getAttribute('value');
    if ($attr === null)//no value attribute yet, create it
        $attr = new DOMAttr('value', $val);
    else//set new value
        $attr->value = $val;
    $this->node->setAttributeNode($attr);
    return $this->node;
}

This is just a crude example, but you get the idea

Update 2:

Are there flaws

Well, I've stated there are quite a few of them already, so I'll just suggest an approach that, IMO, will help you to build a more robust and reliable module. Beginning with something I hinted at in my previous update:

I suggested adding a form element could be done using something along the lines of:

$builder->addField(FormBuilder::ELEMENT_TEXT, $attributesArray);

Let's look into the arguments, first, then how to sanitize and validate them, and finally, how to process them.

the arguments

The first argument is a class constant. For each form element you want to support (select, textarea, radio's, checkboxes, ...) you'll have to create a constant. This makes the user code a lot easier to read/understand. Anyone can see that the snipped above adds a text input to a form, with an array of attributes. Change the first argument to FormBuilder::ELEMENT_TEXTAREA obviously adds a textarea element and so on.
The second array is an (optional) array of attributes. Your method's signature,then, should use type-hinting to ensure that an array is passed. You could create an Attributes class, but in this case, I feel an array will do. The only thing the user must ensure is that the array is associative, because the keys are the attribute names, and the values will be the attribute's value...

Sanitation/validation

How to validate the first argument is up to you, either define each constant to be an int, that is a power of 2: 1, 2, 4, 8, 16, 32, 64, 128, and so on, and use bitwise operators to check if the argument is an int and a power of two, or use a private array where and fill it with all of the constants, and use isset to check if the value passed is a valid constant. I'd opt for the second option, simply because you can then assign a string to each content that you can use to create the node, and use this array to define a couple of basic, but essential attributes for each tag (ie: hidden and text elements will both be input tags, but have a different type-attribute).

The second argument is ensured to be an array (thanks to type-hint). Next step, although this might not be an issue at first, is to map the array, and invoke strip_tags on each value, since attributes shouldn't contain markup.
Also validate the keys of the array, matching them against an array of valid attributes. By this I mean: style and onclick are, in HTML-land, valid attributes, but these kind of attributes should be discouraged. Any decent front-end developer will be more than able to bind event handlers to the form elements without the need to set an onclick attribtue. He'll also be more than capable to churn out CSS that presents the form in any way you like. That's the job of a front-end developer.
Think of it like this: you're creating a FormBuilder, not a FormDesigner, just like you'd expect a builder to build your house, but you have to ask a decorator or interior architect to design what it looks like.

Processing

Well, since I've already stated you should wrap the form element in a Form instance, the same applies to the form elements: they should be instances of the DOMElement class, wrapped in a FormElement instance. Pass those instances on to the form, and let the form instance handle the rest (adding, wrapping in containers etc...).
If anywhere along the line, an invalid argument is passed, or a bad attribute (like style) is being set: don't ignore it, don't try to make sense of things: the code that called your class might have a bug in it, and it should be fixed: Throw an exception to notify the user something is seriously wrong.

To round up, here's a short example of what the FormBuilder class could look like:

class FormBuilder
{
    const ELEMENT_HIDDEN = 'input';
    const ELEMENT_TEXT = 'input';
    const ELEMENT_TEXTAREA = 'textarea';

    /**
     * @var array
     */
    private $constants = array(
        self::ELEMENT_HIDDEN   => array('type' => 'hidden'),
        self::ELEMENT_TEXT     => array('type' => 'text'),
        self::ELEMENT_TEXTAREA => array()
    );

    /**
     * see setAttributes method for usage example
     * @var array
     */
    private $bannedAttributes = array(
        'type'    => 'type is set by FormBuilder',
        'style'   => 'Front-end is not the job of a builder',
        'onclick' => 'Learn JS'//add other on* attributes
    );

    /**
     * @var Form
     */
    private $form = null;//the actual form we're building

    /**
     * Optionally make this final, this constructor creates the form
     * @param array $options = null
     */
    public function __construct(array $options = null)
    {//allow for user to pass specifics, like form attributes
        $formNode = new DOMElement('form');
        if ($options && isset($options['attributes']))
        {
            $formNode = $this->setAttributes(
                $formNode,
                $options['attributes']
            );
        }
        $this->form = new Form($formNode);//create Form wrapper...
    }

    /**
     * Add field to form, after setting optional attributes
     * @param string $type
     * @param array $attribtues = array()
     * @return FormElement
     * @throws InvalidArgumentException
     */
    public function addField($type, array $attribtues = array())
    {
        if (!isset($this->constants[$type]))
        {//optionally allow for direct DOMElement injection here, but I wouldn't
            throw new InvalidArgumentException(
                sprintf(
                    '%s is not a valid type (use %s::ELEMENT_* constants)',
                    $type,
                    __CLASS__
                )
            );
        }
        foreach ($this->constants[$type] as $name => $val)
            $attributes[$name] = $val;//re-assign default attributes, like type
        $node = $this->setAttributes(
            new DOMElement($type),
            $attributes
        );
        $node = new FormElement($node);//set in wrapper
        $this->form->addElement($node);
        return $node;
    }

    /**
     * Set attributes for node
     * @param DOMElement $node
     * @param array $attributes
     * @return DOMElement
     * @throws InvalidArgumentException
     */
    protected function setAttributes(DOMElement $node, array $attributes)
    {
        foreach ($attributes as $name => $val)
        {
            if (isset($this->bannedAttributes[$name]))
            {//symfony2 style exception throwing...
                throw new InvalidArgumentException(
                    sprintf(
                        '%s attribute not allowed: %s',
                        $name,
                        $this->bannedAttributes[$name]
                    )
                );
            }
            //strip_tags to make sure
            $attr = new DOMAttr($name, strip_tags($val));
            $node->setAttributeNode($attr);
        }
        return $node;
    }
}

This really ought to give you some idea as to how to set about building a form module. But this also shows how complex things are about to become. One special attribute you will want to add is the label attribute. This shouldn't be set on the element itself, but rather create a secondary DOMElement with a for attribute. But no matter, we have bigger fish to fry: At the moment, we can't, for example, add fieldsets yet, nor can we remove elements, or determine in which order the elements will be rendered. Look into how other frameworks handle this (often, they wrap elements in divs, and have the Form instance track those, which makes the removeChild calls a lot easier).
I'm not going to do that for you (I'm reviewing code, not writing it), so I say again: look at what is already out there, and let that code inspire you!

Coding style

The code above follows the PHP-FIG standards quite closely (with the exception of Allman-style indentation). I've adopted the Symfony2 way of throwing exceptions, too, because I find it helpful in forcing me to throw exceptions with meaningful messages, and the sprintf reminds me to put some variables in there, so I can see what value was being passed when the exception was thrown.
It's a matter of personal preference, perhaps, but the rest of it (all caps for constants, doc-blocks, camelCased method names and type-hinding) is all conform the standard.


Implement a function that prints all possible combinations of the characters in a string I came across this interview question and it has been asked to print combinations of the characters in a string. For example: "abc" --> a, b, c, ab, ac, bc, abc. Also it has been mentioned that 'ab' and 'ba' are same.

I want to know if there is any improvement I can make in terms of memory usage/performance.

public string[] Combination(string str)
{
    if (string.IsNullOrEmpty(str))
        throw new ArgumentException("Invalid input");

    if (str.Length == 1)
        return new string[] { str };

    // read the last character
    char c = str[str.Length - 1];

    // apart from the last character send remaining string for further processing
    string[] returnArray = Combination(str.Substring(0, str.Length - 1));

    // List to keep final string combinations
    List<string> finalArray = new List<string>();

    // add whatever is coming from the previous routine
    foreach (string s in returnArray)
        finalArray.Add(s);

    // take the last character
    finalArray.Add(c.ToString());

    // take the combination between the last char and the returning strings from the previous routine
    foreach (string s in returnArray)
        finalArray.Add(s + c);

    return finalArray.ToArray();
}

I can suggest following project for combinations and permutations which is very efficient and easy to use:

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

Then it's simple as:

IList<Char> chars = "abc".ToList();
List<string> allCombinations = new List<String>();
for (int i = 1; i <= chars.Count; i++)
{
    var combis = new Facet.Combinatorics.Combinations<Char>(
        chars, i, Facet.Combinatorics.GenerateOption.WithRepetition);
    allCombinations.AddRange(combis.Select(c => string.Join("", c)));
}

foreach (var combi in allCombinations)
    Console.WriteLine(combi);

Output:

a
b
c
aa
ab
ac
bb
bc
cc
aaa
aab
aac
abb
abc
acc
bbb
bbc
bcc
ccc

If you don't want repetion you just have to change GenerateOption.WithRepetition to GenerateOption.WithoutRepetition and the result is:

a
b
c
ab
ac
bc
abc


Throw exception in Spring when loading a file I have this following piece of code:

@Component
public class ManifestReader {

    private final ServletContext servletContext;
    private Properties p;

    @Autowired
    public ManifestReader(final ServletContext servletContext) {
        this.servletContext = servletContext;
    }

    public Properties getManifest() throws IOException {
        if (p == null) {
            p = new Properties();
            p.load(servletContext.getResourceAsStream("/META-INF/MANIFEST.MF"));
        }
        return p;
    }
}

What I want to do it is just, to load the file, and once it is loaded, it can be injected to all the classes that need that properties file. Like here:

@RestController
@RequestMapping(value = "/info")
public class InfoEndPoint {

    private final ManifestReader manifestReader;

    @Autowired
    public InfoEndPoint(final ManifestReader manifestReader) {
        this.manifestReader = manifestReader;
    }

    @RequestMapping(method = RequestMethod.GET)
    public Info get(final HttpServletRequest httpServletRequest) throws IOException {
        final App app = fillApp(httpServletRequest, manifestReader.getManifest());
        final Info info = new Info();
        info.setApp(app);
        return info;
    }
    ....
}

As you can see, everytime I have to call to getManifest I throw an IOException. I don't really want that since I just need to load it once, and then it can be reused without throwing any exception. So, my idea is that you could call to the getManifest method without having to check for any exception.

My first idea was to load the file in the constructor of the class, but I do not know if that is a good practice for Spring. Any clue?

My first idea was to load the file in the constructor of the class, but I do not know if that is a good practice for Spring.

It takes the lazy-loading out of the lazy-loader, but then you could ask yourself what the remaining uses of the class are.

  As you can see, everytime I have to call to getManifest I throw an IOException.

There are two main ways around this:

1. Use UncheckedIOException to wrap IOException:

    public Properties getManifest() {
      if (p == null) {
        p = new Properties();
        try {
          p.load(servletContext.getResourceAsStream("/META-INF/MANIFEST.MF"));
        } catch (IOException ex) {
          throw new UncheckedIOException(ex);
        }
      }
      return p;
    }

This isn't my preferred approach, because all this does is evade the radar, basically. If you're in a pinch, though, this will do the trick. Mind: UncheckedIOException is not a type of IOException.

(On another note: you probably need to mark p as volatile!)

2. Move the loading to an initialization method:

    public Properties getManifest() {
      return p;
    }

    @PostConstruct
    public void init() throws IOException {
      p = new Properties();
      p.load(servletContext.getResourceAsStream("/META-INF/MANIFEST.MF"));
    }

This approach has the added benefit of being thread-safe: no need to fence access to p, and no risk of having a bean in an inoperable state, or filling the log with errors.


PHP Counter Improvement Currently I'm displaying a news feed from an XML file and using a counter to limit the number of news articles that are displayed. But I'm unsure if this is the best way to do it.

Here is my code.

<?php
function get_news($feed) {

$xml = new SimpleXmlElement(uwe_get_file($feed));
$counter = 0;
foreach ($xml->channel->item as $item) {
    echo 'link . '" target="_blank">' . $item->title . '
' . '' . $item->description . '' . '' . $item->pubDate . '' . '
' . '
';
    ++$counter;
    if ($counter == 5) {
        break;
    }
}
}

?>

Any suggestions on how I could improve this counter?

That's a perfectly good and valid way of doing it. Personally, I'd write $counter++ rather than ++$counter, but that's just my personal preference.


Taking and saving pictures using promises I have the following 4 functions that work, however, I am sure that utilising promises will improve my code. I just find them so confusing.

$scope.takePictures = function() {

    document.addEventListener("deviceready", function() {

        var options = {
            quality: 75,
            destinationType: Camera.DestinationType.DATA_URL,
            sourceType: Camera.PictureSourceType.CAMERA,
            allowEdit: true,
            encodingType: Camera.EncodingType.JPEG,
            targetWidth: 200,
            targetHeight: 200,
            popoverOptions: CameraPopoverOptions,
            saveToPhotoAlbum: true
        };

        getImagesFromDevice(options);

    }, false);

}

$scope.getPictures = function() {

    var options = {
        quality: 50,
        destinationType: Camera.DestinationType.DATA_URL,
        sourceType: Camera.PictureSourceType.PHOTOLIBRARY,
        targetWidth: 200,
        targetHeight: 200
    };

    getImagesFromDevice(options);
}

var getImagesFromDevice = function(options) {
    $cordovaCamera.getPicture(options).then(function(imageData) {

        saveFileToParse(imageData);

    }, function(err) {
        // error
    });
}

var saveFileToParse = function(imageData) {
    var parseFile = new Parse.File("mypic.jpg", {
        base64: imageData
    });
    parseFile.save().then(function(response) {
        // The file has been saved to Parse.
        console.log(response._url);

        $scope.activeExercise.images.push(response._url);
        $scope.$apply();
        $scope.customImage = true;

    }, function(error) {
        // The file either could not be read, or could not be saved to Parse.
    });
}

It would be fantastic if someone can improve the above code but further explain the pitfalls in how I have coded it and how it can be improved. If you are able to force a promise explanation in my head that would be great too!

Promises were meant to provide a linear appearance of async code instead of callbacks, as well as make it appear that the control is in one place rather than handing it off to other functions.

Also, functional programming is also of help. Not to the strict sense though, but trying to avoid side effects as much as possible as well as isolating code that mutates stuff to a few known locations can help you reason about your code.

// Let's just move out the handler so both getPictures and takePictures
// look the same.
$scope.takePictures = function () {
  document.addEventListener("deviceready", _takePictures, false);
}

$scope.getPictures = function () {
  // Taking this as an example, we call an async operation
  getImagesFromDevice({
    quality: 50,
    destinationType: Camera.DestinationType.DATA_URL,
    sourceType: Camera.PictureSourceType.PHOTOLIBRARY,
    targetWidth: 200,
    targetHeight: 200
  }).then(function(imageData){
    // When the operation succeeds, this function is called. The nice thing
    // about promises is that if you return a promise, the next chained
    // then listens to that promise instead of the original.
    return saveFileToParse(imageData);
  }).then(function(response){
    // What the above means is that this function now listens to
    // saveFileToParse instead of getImagesFromDevice
    //
    // Also notice that we isolate mutation to the scope to only here
    // and removed it from the other functions.
    $scope.activeExercise.images.push(response._url);
    $scope.$apply();
    $scope.customImage = true;
  });

  // In the end, your operation looks linear
}

function _takePictures() (
  getImagesFromDevice({
    quality: 75,
    destinationType: Camera.DestinationType.DATA_URL,
    sourceType: Camera.PictureSourceType.CAMERA,
    allowEdit: true,
    encodingType: Camera.EncodingType.JPEG,
    targetWidth: 200,
    targetHeight: 200,
    popoverOptions: CameraPopoverOptions,
    saveToPhotoAlbum: true
  }).then(function(imageData){
    return saveFileToParse(imageData);
  }).then(function(response){
    $scope.activeExercise.images.push(response._url);
    $scope.$apply();
    $scope.customImage = true;
  });
}

// These operations do not concern what you're doing with the data. All
// they know is that they receive options, operate, and hand you back
// the data when done. Pretty functional don't you agree?

// Another perk about promises is when you don't return a promise in the
// sequence, all chained thens will resolve using the same value. This
// allows us to chain a then for logging in between without affecting
// the result.

var getImagesFromDevice = function (options) {
  return $cordovaCamera.getPicture(options).then(function (imageData) {
    // logger for success
  }, function (err) {
    // logger for error
  });
}

var saveFileToParse = function (imageData) {
  return (new Parse.File("mypic.jpg", {
    base64: imageData
  })).save().then(function (response) {
    // logger for success
  }, function (error) {
    // logger for error
  });
}

Now if I were to write all this code synchronously, which is how a normal person would go about imperative programming (commands one after the other), the code appears 95% the same.

$scope.takePictures = function () {
  document.addEventListener("deviceready", _takePictures, false);
}

$scope.getPictures = function () {
  var imageData = getImagesFromDevice({
    quality: 50,
    destinationType: Camera.DestinationType.DATA_URL,
    sourceType: Camera.PictureSourceType.PHOTOLIBRARY,
    targetWidth: 200,
    targetHeight: 200
  });

  var response = saveFileToParse(imageData);

  $scope.activeExercise.images.push(response._url);
  $scope.$apply();
  $scope.customImage = true;

}

function _takePictures() (
  var imageData = getImagesFromDevice({
    quality: 75,
    destinationType: Camera.DestinationType.DATA_URL,
    sourceType: Camera.PictureSourceType.CAMERA,
    allowEdit: true,
    encodingType: Camera.EncodingType.JPEG,
    targetWidth: 200,
    targetHeight: 200,
    popoverOptions: CameraPopoverOptions,
    saveToPhotoAlbum: true
  });

  var response = saveFileToParse(imageData);

  $scope.activeExercise.images.push(response._url);
  $scope.$apply();
  $scope.customImage = true;

}

var getImagesFromDevice = function (options) {
  var imageData $cordovaCamera.getPicture(options);
  imageData ? /* success logger */ : /* error logger */;
  return imageData;
}

var saveFileToParse = function (imageData) {
  var response = (new Parse.File("mypic.jpg", { base64: imageData })).save();
  response ? /* success logger */ : /* error logger */;
  return response;
}

Now I'm assuming here that you use a "standard" promise. Angular's $q has a weird quirk where if you don't return anything from the resolve or reject handler, instead of resolving or rejecting with the same value from the original promise, it resolves regardless.

The fix is to manually return data or a reject.

var getImagesFromDevice = function (options) {
  return $cordovaCamera.getPicture(options).then(function (imageData) {
    // logger for success
    return imageData;
  }, function (err) {
    // logger for error
    return $q.reject(err);
  });
}


A C program to find all factorions using a hash table The objective of this program is to find all factorions, which are numbers equal to the sum of the factorials of their digits.

I am seeking suggestions on how to improve the performance of this code, as well as stylistic advice.

#include <stdio.h>
#include <stdlib.h>
#define base 10 //We are working in base 10
#define upper_bound 2540160 //This is 7 x 9! because a factorion can have at most seven digits.
//If it has d digits, it must satisfy the inequality 10^{d-1} < n <= 9!d, which isn't satisfied above d = 8
#define expected_no_of_answers 5 //I chose 5 somewhat arbitrarily. I knew beforehand there are only four answers in base 10

//Function prototype
void create_hash_table(int[]);
void get_fact_digit_sum(int[],int[]);
void display_answers(int[]);

int main()
{
    int hash_table_fact[base], answers[expected_no_of_answers]; //Creating a hash table where t[n] -> n!

    create_hash_table(hash_table_fact);

    get_fact_digit_sum(answers,hash_table_fact);

    display_answers(answers);

    return 0;
}

void create_hash_table(int hash_table_fact[])
{
    int i = 1, fact = 1;
    hash_table_fact[0] = 1; //0! = 1

    for(i = 1; i < base; i++)
    {
        fact = fact*i;
        hash_table_fact[i] = fact;
    }
}

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
    int answerCount = 0, i = 1, temp, sum;

    //Combing through the search space to search for factorions
    for(i = 1; i <= upper_bound; i++)
    {
        temp = i;
        sum = 0;
        //Getting the sum of the factorials of the digits
        while(temp != 0)
        {
            sum = sum + hash_table_fact[ (temp%base) ];
            temp = temp/base;
        }
        if(sum == i)
        {
            answers[answerCount++] = i;
        }
    }

    //Placing a 0 at the end to mark the end of the array
    answers[answerCount] = 0;
}

void display_answers(int answers[])
{
    int i;

    for(i = 0; answers[i] != 0; i++)
    {
        printf("%d\t",answers[i]);
    }
}

You can use the previous sum to compute the next one

Your main loop computes the sum of factorials of digits from scratch for each number, but you are throwing away a lot of work from number to number.  Think about two consecutive numbers, such as:

1234: sum = 1! + 2! + 3! + 4!
1235: sum = 1! + 2! + 3! + 5!

You can see that for 1235, it only differs from 1234 by the last digit, so you can compute its sum more quickly if you do this:

sum = previousSum + 5! - 4!

If the last digit wraps around from 9 to 0, you have to do the same thing with the next digit on the left:

1239: sum = 1! + 2! + 3! + 9!
1240: sum = 1! + 2! + 4! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 4! - 3! // Tens digit

If you reach a new power of 10, you need to do something a little different:

 99: sum =      9! + 9!
100: sum = 1! + 0! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 0! - 9! // Tens digit
sum += 1!      // Hundreds digit (note: do not subtract 0!)

Sample rewrite

Using this idea, your function becomes this:

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
    int answerCount = 0;
    int sum         = 1;

    // Combing through the search space to search for factorions
    for (int i = 1; i <= upper_bound; i++) {
        int temp = i;

        while (1) {
            int digit = temp % base;
            if (digit == 0) {
                sum += hash_table_fact[0] - hash_table_fact[base-1];
                temp /= base;
                if (temp == 1) {
                    // Special case: reached new digit.
                    sum += hash_table_fact[1];
                    break;
                }
            } else {
                sum += hash_table_fact[digit] - hash_table_fact[digit-1];
                break;
            }
        }
        if (sum == i) {
            answers[answerCount++] = i;
        }
    }

    // Placing a 0 at the end to mark the end of the array
    answers[answerCount] = 0;
}

The new way ran 4x faster than the old way for the given upper bound.  If you extend the upper bound to 100 million (even though there are no answers that high), the new way runs 8x faster than the old way.


Selection sort using recursion How does this recursive selection sort look to everyone here? Am I missing anything 'pythonic' about the way I have done it?

def selection_sort(li, out=None):
    if out is None:
        out = []
        li = li[:]

    if len(li) == 0:
        return out

    small = min(li)
    li.remove(small)
    out.append(small)
    return selection_sort(li, out)

def selection_sort(li, out=None):

I dislike the name "li," I think abbreviations are bad.

    if out is None:
        out = []
        li = li[:]

Rather then using the out parameter to do this, I suggest creating a seperate internal function which is called. Otherwise, it looks like the caller to the function might reasonable pass out = something, when its only meant to be used internally.

    if len(li) == 0:
        return out

Better to use if not li:

    small = min(li)
    li.remove(small)
    out.append(small)
    return selection_sort(li, out)

Its a little hard to gauge this code because you are doing two things you shouldn't, using recursion when its not necessary and implementing your own sort routine. But if you are doing so for learning purposes that's fine.

EDIT

Iterative solution:

def selection_sort(li):
    li = li[:]
    out = []

    while li:
        smallest = min(li)
        li.remove(smallest)
        out.append(smallest)

    return out

But why is this better than the recursive solution:

There is a limit to your stack space. If you try to sort a large list using this function you'll get a RuntimeError
Calling a function has extra overhead that iterating in a loop does not, the iterative version will be faster
A loop is usually easier to read then recursion. The while loop makes it easy to see whats doing on, whereas the recursive version requires some thought about the code to see the logic.


Overloading istream>> to read comma-separated input I have the following very simple class:

class accusation
{
private:
    std::string murderer;
    std::string weapon;
    std::string place;
public:
    accusation() = default;
    accusation(std::string, std::string, std::string);
    friend std::ostream& operator<<(std::ostream&, const accusation&);
    friend std::istream& operator>>(std::istream&, accusation&);
};

I have overloaded my extraction from istream operator as follows:

std::istream& operator>>(std::istream& is, accusation& readable)
{
    std::vector<std::string> accusation;
    std::string token, word;
    //divide by commas
    while (std::getline(is, token, ','))
    {
        std::string pushable;
        std::stringstream ss(token);
        while (ss >> word) pushable += word + " ";
        if (pushable.size() != 0) pushable.pop_back(); //remove that last white space
        std::transform(pushable.begin(), pushable.end(), pushable.begin(), ::tolower);
        accusation.push_back(pushable);
    }
    if (accusation.size() == 3)
    {
        is.clear();
        bool valid{ false };
        //check it matches one of the clue::characters
        for (const auto& character : clue::characters)
            if (accusation[0] == character)
            {
                valid = true;
                break;
            }
        if (valid)
        {
            valid = false;
            //check it matches one of the clue::weapons
            for (const auto& weapon : clue::weapons)
                if (accusation[1] == weapon)
                {
                    valid = true;
                    break;
                }
            if (valid)
            {
                valid = false;
                //check it matches one of the clue::places
                for (const auto& place : clue::places)
                    if (accusation[2] == place)
                    {
                        valid = true;
                        break;
                    }
                if (valid)
                {
                    readable.murderer = accusation[0];
                    readable.weapon = accusation[1];
                    readable.place = accusation[2];
                }
                else
                    is.setstate(std::ios_base::failbit);
            }
            else
                is.setstate(std::ios_base::failbit);
        }
        else
            is.setstate(std::ios_base::failbit);
    }
    else
        is.setstate(std::ios_base::failbit);
    return is;
}

I am reading input as green, dagger, kitchen and storing it in my accusation. The first element has to be in clue::characters (an array of possible game characters), second element in clue::weapons, and third element in clue::places.

Can somebody suggest a cleaner way to overload this operator? The code works as expected, but I believe that there is a lot of space for improvements. Any push into the right direction is highly appreciated.

95 percent of programming is looking for redundancies and eliminating them.

For example, why do you bother with reading strings into accusations[] first, and then later copying them into readable.murderer et cetera? Why not just read them directly into readable.murderer? This would have the bonus of eliminating those "magic number" indices 0, 1, and 2, and replacing them with readable (no pun intended) identifiers.

std::getline(is, readable.murderer, ',');
std::getline(is, readable.weapon, ',');
std::getline(is, readable.place, ',');  // shouldn't this last one be '\n' not ','?

You should test your code and see if it does what you wanted.

std::istringstream iss(
    "Mr Green, lead pipe, conservatory\n"
    "Mrs Peacock, noose, kitchen"
);
accusation acc;
iss >> acc;

This reads 5 items into accusation. Is this what you wanted to happen?

Reduce repetition. You have the following snippet repeated three times:

    for (const auto& THING : THINGS)
        if (accusation[INDEX] == THING)
        {
            valid = true;
            break;
        }

So, first of all, we wrap the loop body in curly braces to protect against goto fail; and then we factor it out into a function.

template<class T>
bool vector_contains(const std::vector<T>& vec, const T& value) {
    for (auto&& elt : vec) {
        if (elt == value) {
            return true;
        }
    }
    return false;
}

And then our main function's code can become simply

bool valid = vector_contains(clue::characters, readable.murderer)
          && vector_contains(clue::weapons, readable.weapon)
          && vector_contains(clue::places, readable.place);
if (!valid) {
    is.setstate(std::ios_base::failbit);
}

The body of vector_contains could also be implemented simply by using an STL algorithm, e.g.

template<class T>
bool vector_contains(const std::vector<T>& vec, const T& value) {
    return std::count(vec.begin(), vec.end(), value);
}

or

template<class T>
bool vector_contains(const std::vector<T>& vec, const T& value) {
    return std::find(vec.begin(), vec.end(), value) != vec.end();
}

or

template<class T>
bool vector_contains(const std::vector<T>& vec, const T& value) {
    return std::any_of(vec.begin(), vec.end(), [&](const auto& elt) {
        return elt == value;
    });
}

I named the function vector_contains, rather than simply contains, because in my estimation there is a very real possibility that C++2a might add std::contains to the library and thus break any code using ADL calls to contains.

Minor nits:

I strongly recommend making all your constructors explicit, to eliminate bugs from unintentional implicit conversions. (Yes, even your multi-argument constructors.)
I strongly recommend making operator>> and operator<< into inline friend functions — define them right inside the body of your class. This will make them findable only via ADL, and is generally what you want. It'll look a lot more reasonable, too, once you've refactored your operator>> to be only five or six lines long! :)

You're also doing something weird with stringstream to remove whitespace from the ends of each piece of the string. You should factor that out into a helper function, and then simplify it. Say,

std::string strip(const std::string& s)
{
    int i = 0;
    while (isspace(s[i])) ++i;
    int j = s.size();
    while (j >= 1 && isspace(s[j-1])) --j;
    return s.substr(i, j-i);
}

https://wandbox.org/permlink/uVSolN0Nepk48Mgm

class accusation
{
private:
    std::string murderer;
    std::string weapon;
    std::string place;
public:
    accusation() = default;
    explicit accusation(std::string, std::string, std::string);
    friend std::ostream& operator<<(std::ostream&, const accusation&);
    friend std::istream& operator>>(std::istream& is, accusation& a) {
        std::getline(is, a.murderer, ',');
        std::getline(is, a.weapon, ',');
        std::getline(is, a.place);
        if (!vector_contains(clue::characters, a.murderer) ||
            !vector_contains(clue::weapons, a.weapon) ||
            !vector_contains(clue::places, a.place)) {
            is.setstate(std::ios_base::failbit);
        }
        return is;
    }
};

Deciding whether your std::transform lowercasing should be removed, kept, or folded into the helper function vector_contains (renaming that function to indicate its new purpose, and using a non-mutating facility such as strcasecmp) is left as an exercise for the reader.


Chaining asynchronous tasks that must run sequentially I want to implement an Agent-like object in C#. An Agent wraps some memory location (ideally storing an immutable object) and receives updates to that location. All these updates are performed asynchronously, but sequentially. In other words

  At any point in time, at most one [update submitted to an] Agent is
  being executed.

My current implementation uses the TPL. The Agent keeps a reference to the last update that has been or must be performed, wrapped in a Task. When submitted a new update, you wrap the update in a Task, get a reference to the last Task and replace it, atomically, then invoke ContinueWith on that last Task with this new update Task (everything submitted through a TaskScheduler).

public class Agent<T> where T : class
{
    private T wrappedValue;
    private readonly TaskScheduler scheduler;
    private Task lastTask;

    public Agent (T value, TaskScheduler scheduler)
    {
        this.wrappedValue = value;
        this.scheduler = scheduler;
    }

    public void Send (Action<T> operation)
    {
        Task task = new Task ((action) => ((Action<T>)action) (wrappedValue), operation);
        Task localCurrent;
        do {
            // always append to the end
            localCurrent = lastTask;
        } while(Interlocked.CompareExchange (ref lastTask, task, localCurrent) != localCurrent);

        if (localCurrent == null) {
            task.Start (scheduler);
        } else {
            localCurrent.ContinueWith ((currentTask, scheduler) => {
                task.Start ((TaskScheduler)scheduler);
            }, scheduler, scheduler);
        }
    }
    [...]
}

The first thread to send an action will see null in the field and so needs to Start() the Task directly.

This (seems to) work. Only one submitted action is ever running at a given moment. Additionally, tasks are potentially run on different threads. I don't want a dedicated thread for updates (and I don't want to lock up a TaskScheduler thread).

However, I'm worried about a few things that I think could be improved:

I'd like to be able to ContinueWith the Task task directly, instead of having to start it within a different submitted Action. I feel like I need to create the new Task so that I can atomically exchange the lastTask field's value.
Lambda capturing of local variables, partly alleviated with state objects where possible.
How can I keep a reference to the currently executing Task, so I can short-circuit execution? Or should I use a poison pill to signal termination and not chain any new tasks?
Interlocked for atomicity. Should I use a ConcurrentQueue? How would I manage not having a dedicated thread and only running one Task at a time with a ConcurrentQueue?
Is a Volatile.Read of lastTask necessary for localCurrent = lastTask;?

Doing this now

private void InvokeAndComplete (Action<T> act, TaskCompletionSource<byte> promise)
{
    try {
        act (internalValue);
    } finally {
        // some value we will ignore
        promise.SetResult (1);
    }
}

public Task Alter (Action<T> alterAction)
{
    TaskCompletionSource<byte> promise = new TaskCompletionSource<byte> ();
    Task localLastTask;
    do {
        // Not sure if Volatile.Read is necessary
        localLastTask = Volatile.Read (ref lastTask);
    } while (Interlocked.CompareExchange (ref lastTask, promise.Task, localLastTask) != localLastTask);
    // only this thread has a reference to the object referenced by localLastTask
    return localLastTask.ContinueWith ((currentTask) => {
        InvokeAndComplete (alterAction, promise);
    }, taskScheduler);
}

I would use lock instead of Interlocked, because its much easier to follow and debug. Unless you are after some kind of micro optimization, I think you should keep it simple:

lock (lock)
{
    if (lastTask == null)
    {
       task.Start(scheduler);
    }
    else
    {
        lastTask.ContinueWith(...);
    }
    lastTask = task;
}

I think you can modify your lambda expression to get a current task:

Task task = null;
task = new Task ((action) =>
     {
         CurrentTask = task;
         ((Action<T>)action) (wrappedValue);
     }, operation);

Though I am not too experienced with TPL, so there might be an easier way.


Reverse singly linked list Description:

Given a linked list reverse it and return the new head.

Code:

class Main {
  static class Node {
    public int data;
    public Node next;

    Node(int data) {
      this(data, null);
    }

    Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }

    // Just a helper method, not optimised
    Node append(int data) {
      Node newNode = new Node(data, null);
      Node current = this;

      while (current.next != null) {
        current = current.next;
      }
      current.next = newNode;
      return this;
    }
  }
  // 10 -> 20 -> 30
  // 10    20 -> 30
  // 10 <- 20 -> 30
  //       c     n
  // 10 <- 20 <- 30
  public static Node reverse(Node head) {
    if (head == null || head.next == null) {
      return head;
    }

    Node prev = null;
    Node curr = head;
    Node next = null;

    while (curr != null) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    return prev;
  }

  public static void main(String[] args) {
    Node head = new Node(10)
        .append(20)
        .append(30)
        .append(40);

    Node newHead = reverse(head);
    System.out.println(newHead); // 40 30 20 10
  }
}

Question:

The idea is quite simple i.e. we need to go one by one and we need to reverse the link, for this we need three pointers but I really struggled to put the idea into code. I know that understanding about invariants can help
to write code in a more robust way. How can I help form invariants in this situation to improve the logic?

I can't find any very useful invariant but sum of length of list should be constant. So we can make following assertion:

static int length(Node node) {
    int result = 0;
    while (node != null) {
        result++;
        node = node.next;
    }
    return result;
}

public static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }

    int totalLength = length(head);

    Node prev = null;
    Node curr = head;
    Node next = null;

    while (curr != null) {
        assert length(prev) + length(curr) == totalLength;
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    assert length(prev) + length(curr) == totalLength;

    return prev;
}

It is a bit of a stretch but we can make it easier to understand why invariant is preserved by showing that single node is moved from one list to another:

static class Node {

    // rest of class without changes

    @Override
    public String toString() {
        return  data + " -> " + next;
    }

}

static class List {
    Node head;
    int size() {
        return length(head);
    }

    Node removeFist() {
        Node oldHead = head;
        head = head.next;
        return oldHead;
    }

    boolean isEmpty() {
        return head == null;
    }

    void prepend(Node newHead) {
        newHead.next = head;
        head = newHead;
    }

    static List of(Node node) {
        List list = new List();
        list.head = node;
        return list;
    }
}

static int length(Node node) {
    int result = 0;
    while (node != null) {
        result++;
        node = node.next;
    }
    return result;
}

public static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }

    List reversed = List.of(null);
    List input = List.of(head);
    final int totalSize = input.size();

    while (!input.isEmpty()) {
        assert reversed.size() + input.size() == totalSize;
        reversed.prepend(input.removeFist());
    }
    assert reversed.size() + input.size() == totalSize;

    return reversed.head;
}

Sadly I wouldn't call that improvement. Maybe it would made more sense if List class I added also contained Node tail.


Why is this code so much faster (relatively) in IE7? Here's some code that I ran through jsperf to assess its performance. The first test (named EvalLengthBefore++ in the images below) is the way I would consider normally looping through the elements of an array:

var arr = [];
for (var x = 0; x < 1000; x++) {
  arr.push(Math.random());
}

var len = arr.length;
for (var y = 0; y < len; y++) {
  //do some maths
  var el = arr[y];
  el++; //meaningless operation
}

The second test (named InfiniteLoopWithBreak in the images below) is the method I found in some code that is supposed to to be run in IE7 (it's part of a CSS fallback):

var arr = [];
for (var x = 0; x < 1000; x++) {
  arr.push(Math.random());
}

for (var y = 0;; y += 1) {
  //do some maths
  var el = arr[y];
  if (!el) {
    break;
  }
  el++;
}

In modern browsers, the second method is much slower, which is kind of what I expected. However in IE7 it is just as fast, occasionally faster, in the jsperf tests:

Test results in Chrome:

Test results in IE7

Here are the jsperf tests if you want to run them yourselves.

Why is the second code snippet faster than the rest in IE7?

The short answer:
In your code the arr.length is the major bottleneck. Simply because of the differences between the various implementations of JavaScript. Not only the implementations differ, but also what the engines actually do prior to executing your code.
Why do I think this: simple:

for([[expr evaluated at start of loop]];
    [[expr re-evaluated on each iteration + 1(end of loop)]];
    [[expr evaluated for each iteration +1(end of loop)]]
)

The cases that are fastest on IE7 are those where the conditional expression in the for-loop is either missing or is simply comparing the values of 2 variables.

The long answer, without focussing on arr.length, but keep in mind that here, you're getting a property of an object, that is, sort-of, inherited from the prototype.

The reason why is simply because of how Chrome's V8 compiles the code, and how the Object[[GetProperty]] is implemented. Since JS arrays are just augmented objects (Array instanceof Object is true), getting a value from an array is, essentially the same as someObj.someProp.
Most JS implementations use either a HashMap or HashTable for the objects. Chrome's V8 engine, is a bit of an odd one out, in a couple of crucial ways.

FF's SpiderMonkey/*Monkey engines compile JS code to intermediate byte-code, that runs on a virtual machine.
Their Rhino engine compiles JS to Java, which is also a VM environment. Cf the hybrid model in the img below
JS "engines" of old didn't even go that far, they were just parse-and-execute things. They did no or very little optimization or reflection on the code they were asked to parse.
V8 does things a bit different: it parses, optimizes and compiles the resulting AST (Abstract Syntax Tree) straight into machine-executable code. No byte-code virtual-machine stuff to hold you back:

So, Chrome's V8 compiles to machine code, which cuts down overall execution time (in most cases). In addition to that, the V8 engine does not use a HashTable for object properties. It creates classes:

  To reduce the time required to access JavaScript properties, V8 does not use dynamic lookup to access properties. Instead, V8 dynamically creates hidden classes behind the scenes.

What does this mean for arr.length:

//V8:
arr = [];//creates class, that has length property, value 0
arr.push(123);//arr points to class with property 0 = 123, length = 1

That means that, arr.length or arr[0] both are simple, atomic operations. In terms of time-complexity, they are as close as makes no difference both: O(1). Now, I'm not familiar with the internals of IE's JScript engine, but I'm prepared to take a punt on how arr.length works:

arr.length;//->arr @instancelevel->search(length)
             //
             ==>arr.prototype->search(length)
                 //
                 ==> magic property, probably does something like:
                     return max(@instance.keys) +1

Now, this may range anywhere from pretty accurate to down-right absurd, but the principle stands: getting the length property from an array on engines that don't create classes for instances, is not atomic, and therefore slower.
Sadly, because of MS's software being closed source, I can't tell you what kind of AST the parser churns out, nor what the engine then does with that AST. You'll have to get friendly with someone working in Redmond, or send a very polite email, requesting more info (don't expect an answer, though :-P).

So, V8 compiles the AST directly to machine-executable code, and creates classes to speedup property. In theory, accessing a property in JS, running on V8 should be almost as fast as C++ code. In theory, that is :P.
Internet Explorer's JScript engine, especially IE7, is quite dated. It doesn't do optimization very well. It doesn't compile JS as well as modern day engines do.

I can't find the resource ATM, but I also seem to remember that IE's JScript implementation of objects was, in fact, rather lacking, too. I seem to recall it didn't even use a full-blown HashTable for its objects, which would explain why someArray.length takes ages (since it requires a prototype lookup).

Read more here.


Map String to list of string Input: String : Title; List Tags

Problem statement:

  Need to map title to tags, e.g. title is "china man japan beijing bell" and tags are ["china man" "beijing bell"], output should be ["china man" "japan" "beijing bell"]

What I am doing:

List<String> getTitleSplits(String title, List<String> tags) {
        List<String> titleSplits = title.split(" "));
        List<String> ret = new ArrayList<String>();
        LinkedHashMap<String, Boolean> splitValueMap = new LinkedHashMap<String, Boolean>();
        for(String split : titleSplits) {
            splitValueMap.put(split, FALSE);
        }
        for(String titleSplit : titleSplits) {
                boolean flag = false;
                for(String tag : tags) {
                    if(tag.contains(titleSplit) || tag.contains(titleSplit.toLowerCase())) {
                        List<String> tagSplits = Arrays.asList(tag.split((" ")));
                        List<String> list = new ArrayList<String>();
                        for (String tagSplit : tagSplits) {
                            if (splitValueMap.get(tagSplit) == FALSE &&
                                    titleSplits.contains(tagSplit)) {
                                list.add(tagSplit);
                                splitValueMap.put(tagSplit, TRUE);
                                flag = true;
                            }
                        }
                        if(flag) {
                            ret.add(StringUtils.join(list, " ").trim());
                            splitValueMap.put(titleSplit, TRUE);
                            break;
                        }
                    }
                }
                if(!flag && splitValueMap.get(titleSplit) == FALSE) {
                    ret.add(titleSplit);
                }
            }
        return ret;
}

Please review this.

This problem intrigued me, and it has aspects which relate to a real-world problem I am working on. Performance is a significant concern of mine, and reviewing your code, and the current answer by wassgren (+1), I suspect there's a better way to do it.

In both of your cases, you break the title down to words, and then build up the words in ways to see if they match tags. This creates a challenge which scales badly (I believe the solutions are about \$O(n t^2)\$ (n the size of the title, t the number of tags), and will have poor performance for reasonably sized titles, or tag sets.

A better way would be to only 'split' the title on the tag boundaries... locate each tag inside the title, and, if it is there, identify that location, then look in the next spots.

Still, this requires matching many tags, against many places in the title, which then becomes an order of \$O(nt)\$

Regular expressions, though, are able to significantly improve that by using Automata to match the text. A single regular expression on the title will approach \$O(n)\$ performance, and not significantly depend on the number of tags.

Thus, by building a complex regular expression, you can reduce the algorithmic complexity substantially. So, a regular expression like china man|beijing bell will match the first of those tags in the title.

Regular expressions can also work on word-boundaries, and be case insensitive. Thus, there is no need to do any splitting of the input, and conversion to lower-case....

Because regular expressions have structured orders of evaluation, we can build up a regex that encompasses all the required tags.

There are thus two parts... given a regular expression that matches all the tags, your code becomes simply:

    List<String> result = new ArrayList<>();
    Matcher mat = **SOME_PATTERN**.matcher(text);
    int lastPos = 0;
    while (mat.find()) {
        addNotEmpty(text, lastPos, mat.start(), result);
        result.add(mat.group());
        lastPos = mat.end();
    }
    addNotEmpty(text, lastPos, text.length(), result);

    return result.toArray(new String[result.size()]);

The code to build the regular expression is just a clever way of "orring" the tags:

    List<String> quoted = sources.stream().map(tag -> "\\b" + Pattern.quote(tag) + "\\b")
            .collect(Collectors.toList());
    String pat = String.join("|", quoted);

    return new CompiledTagSet(Pattern.compile(pat, Pattern.CASE_INSENSITIVE), sources.toString());

Note, you look for word boundaries on the tag, and 'quote' it so that any tags containing special regex characters are not going to break things.... Then you concatenate them with the regex 'or' character |.

Finally, you compile it to be case-insensitive.

Putting this all together, you can have a system like:

package tagger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

public class TagSplitter {

    public static final class CompiledTagSet {
        private final Pattern pattern;
        private final String sources;

        private CompiledTagSet(Pattern pattern, String sources) {
            this.pattern = pattern;
            this.sources = sources;
        }

        private Pattern getPatterns() {
            return pattern;
        }

        @Override
        public String toString() {
            return sources;
        }

    }

    public static final CompiledTagSet compileTags(Collection<String> tags) {
        // strip out duplicate, empty, and null tags.
        List<String> sources = tags.stream()
                .filter(tag -> tag != null)
                .map(tag -> tag.trim())
                .filter(tag -> !tag.isEmpty())
                .distinct()
                .collect(Collectors.toList());

        // THIS IS CRITICAL
        /*
         * Sort the 'tags' in reverse order alphabetically. The reason is as follows:
         * If one tag is a prefix of another, like "bobby" and "bobby tables", then we
         * want our regex to match "bobby tables" if it exists, and not just "bobby".
         * Add another tag "tables", and we have three: "bobby", "bobby tables" and
         * "tables". If we were to match the text:
         *     I am bobby tables
         * we want the match to be "bobby tables", and not "bobby" and "tables"
         * Java regular expressions are "alternate ordered" which means, if you have
         * OR conditions in the regex, the first one (left most) that matches, wins.
         * So, if we have the regular expression "bobby|bobby tables|tables" and match
         * that against "I am bobby tables", it will match "bobby" first.
         *
         *  The regular expression "bobby tables|bobby|tables", on the other hand, will
         *  match "bobby tables" first.
         *
         *  By sorting the tags in reverse order, longer tags will happen first.
         *
         *  I believe this will also make track-back mechanisms faster in the automaton
         *  if closely related tags are closer together.
         */
        sources.sort(Comparator.reverseOrder());

        List<String> quoted = sources.stream().map(tag -> "\\b" + Pattern.quote(tag) + "\\b").collect(Collectors.toList());
        String pat = String.join("|", quoted);

        return new CompiledTagSet(Pattern.compile(pat, Pattern.CASE_INSENSITIVE), sources.toString());
    }

    private static final void addNotEmpty(String text, int left, int right, List<String> target) {
        if (right <= left) {
            return;
        }
        String candidate = text.substring(left, right).trim();
        if (candidate.isEmpty()) {
            return;
        }
        target.add(candidate);
    }

    public static String[] splitByTags(final String text, final CompiledTagSet tags) {

        List<String> result = new ArrayList<>();
        Matcher mat = tags.getPatterns().matcher(text);
        int lastPos = 0;
        while (mat.find()) {
            addNotEmpty(text, lastPos, mat.start(), result);
            result.add(mat.group());
            lastPos = mat.end();
        }
        addNotEmpty(text, lastPos, text.length(), result);

        return result.toArray(new String[result.size()]);

    }

    public static String[] splitByTags(final String text, String...tags) {
        // filter and process the tags.
        // remove null values, duplicates, empty strings, etc.
        return splitByTags(text, compileTags(Arrays.asList(tags)));
    }

    public static void main(String[] args) {
        String[][] tagSets = {
                {"china man", "beijing bell", "man eater"}

        };
        String[] inputs = {"China man eater Japan Beijing bell"};

        List<CompiledTagSet> compiled = Arrays.stream(tagSets).map(tags -> compileTags(Arrays.asList(tags))).collect(Collectors.toList());

        for (String input : inputs) {
            for (CompiledTagSet ts : compiled) {
                System.out.printf("Split: %s%nUsing: %s%nMatch: %s",
                        input, ts, Arrays.toString(splitByTags(input, ts)));
            }
        }

    }
}

Note that there is special handling for situations where one tag is a prefix of another tag.

The above code produces the output:

Split: China man eater Japan Beijing bell
Using: [man eater, china man, beijing bell]
Match: [China man, eater Japan, Beijing bell]


Program that reads a string from the keyboard and tests whether it contains a valid date I know this task could be done in more practical ways, but the professor only want us to solve it with the "if" statement. I tested and it meets the condition for each task, but I still feel this code looks a bit awkward, I think there is an easier way to get it done. Can someone give me any advice?

import javax.swing.JOptionPane;
public class ValidDate {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        String Smonth =
                JOptionPane.showInputDialog ("Enter the Month");
        int month = Integer.parseInt(Smonth);

        if (month <= 0 || month > 12)
        {
            JOptionPane.showMessageDialog (null, " The month you entered is wrong" );
            System.exit (0);
        }

        String Sday =
                JOptionPane.showInputDialog ("Enter the Day");
        int day = Integer.parseInt(Sday);

         if (day <= 0 || day > 31)
            {
                JOptionPane.showMessageDialog (null, " The day you entered is wrong" );
                System.exit (0);
            }
         else if (month == 4 || month == 6 || month == 9 || month == 11 && day > 30)
            {
                JOptionPane.showMessageDialog (null, " The day you entered is wrong because " + month + " month has only 30 days");
                System.exit (0);
            }

        String Syear =
                JOptionPane.showInputDialog ("Enter the Year");
        int year = Integer.parseInt(Syear);
        boolean leap = ((year % 4 == 0) && (year % 100 != 0) || (year % 400 == 0));

         if (leap == false && month == 2 && day >=29)
        {
            JOptionPane.showMessageDialog (null, " The Date you entered is wrong since " + year +" is not a leap year" );
            System.exit (0);
        }
        else
            JOptionPane.showMessageDialog (null, " The Date you entered is " + month + "/" + day + "/" + year);

    }

}

First, a few comments about style.

You shouldn't start variable names with a capital letter, that's used for constants and class names.  So instead of Smonth and Sday, use monthStr and dayStr.
If you put braces around the statement after an if, put them around the else as well.  Your last if/else doesn't do that.
Instead of saying leap == false, say !leap.

I think the one thing that could make your code look cleaner and clearer would be to move repeated code off into a separate method.  For example, you're repeatedly opening a JOptionPane, getting a value and then converting it to an integer.  Why not put that in a separate method, so you could call:

int month = getValue("Month");

This would reduce the clutter in your main method and have the added advantage that if you wanted to change how you ask the user for values, you would only have to do it in one place.  Do that with your error checking as well and your code improve quite a bit.


Java Max-Stack implementation to return maximum value in the stack I have written the below program to write a Java stack implementation. I have added a method which returns the maximum value in the stack, e.g, a pop. The implementation for this is based on the Max Heap Sort algorithim. I have little doubt on the time complexity analysis - it's not \$O(\log n)\$ is it?

public class Stack {

    int top = -1;
    int[] stack;

    public Stack(int size) {
        stack = new int[size];
    }

    public void push(int v) {
        if (top == stack.length - 1) {
            System.out.println("Oveflow!!");
            return;
        }
        stack[++top] = v;
    }

    public void pop() {
        if (top < 0) {
            System.out.println("Empty stack");
            return;
        }

        stack[top] = 0;
        top--;

    }

    public int getMax() {

        int[] c = stack.clone();
         // not a complete heap sort, but with below approach, i am trying bubble up.
        // build the heap starting from n/2, as any nodes after n/2 are leaf(s)
        for (int j = stack.length / 2; j >= 0; j--) {
            buildMaxHeap(c, j, c.length - 1);
        }

        return c[0];
    }

    private void buildMaxHeap(int[] clone, int i, int j) {
        int root = i;

        while (root * 2 + 1 <= j) {
            int c = root * 2 + 1;

            if ((c + 1) <= j && clone[c] <= clone[c + 1]) {
                c = c + 1;

            }

            if (clone[root] < clone[c]) {
                int t = clone[root];
                clone[root] = clone[c];
                clone[c] = t;
                root = c;
            } else {
                root++;
            }
        }

    }

    public void display() {
        System.out.println("------------------------");
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i]);
        }
    }
}

Running time:

The running time is not O(lg(n)) is O(n) since you are building a max heap.

You iterate over  elements (no leaf elements). Knowing this we can conclude that is at least O(n).
The function called buildMaxHeap is actually O(h), h being the height of the node (which you call i). So because the height of any heap is

and because this summation to the infinity ends up being constant:

we get O(n).

Names:

buildMaxHeap doesn't actually builds the max heap so it name is not appropriate. This function is commonly called maxheapify and is to maintain the heap property. Also I would change the name of parameter named clone for something more generic, because in that context it doesn't matter if its a clone or not.

Pop:

Pop doesn't return the element poped, neither I see a top function so this stack is pointless.

Code

This part:

 if ((c + 1) <= j && clone[c] <= clone[c + 1]) {
     c = c + 1;
 }

Can be change to this

 if ((c + 1) <= j && clone[c] < clone[c + 1]) {
     ++c;
 }

Because if both are equal why bother incrementing c ?

This is not that important though I am just nitpicking.

This part could be improved as well:

 if (clone[root] < clone[c]) {
    int t = clone[root];
    clone[root] = clone[c];
    clone[c] = t;
    root = c;
 } else {
    root++;
 }

For the swapping it would be more readable to implement a method named swap. Also if there is no swapping the algorithm should terminate, because the lower subtrees are already max heaps so its pointless. This is the reason why building a max heap starts at floor(n/2).

so this part would end up like this

 if (clone[root] >= clone[c]) break;

 swap(clone, root, c);
 root = c;

Conclusion:

Given the hidden constant factor in your function getMax (cloning the array and the hidden constant factor in building a max heap) its better to do it the straightforward way:

    int max = Integer.MIN_VALUE;
    for(int i = 0; i <= top; ++i)
        max = Math.max(max, stack[i]);

or for Java 8:

    OptionalInt i = Arrays.stream(stack,0, top+1).max();

Additional notes:
This also can be improved with Java generics.


Outputting a countdown in a div I got this code working with the jQuery Countdown Plugin to take a string input and output a countdown in a div.  Is there a better way of implementing this?

JSFiddler

HTML

Here

Script

function stringToCountdown(element,str){
        /* Parse the String */
        var hh = parseInt(str.substr(0,2),10);
        var mm = parseInt(str.substr(2,2),10);
        var ss = parseInt(str.substr(4,2),10);
        var parity = parseInt(str.substr(4,2),10);

        var austDay = new Date();
        austDay = new Date(    austDay.getFullYear() , austDay.getMonth(),
                            austDay.getDate(),austDay.getHours()+hh,
                            austDay.getMinutes()+mm, austDay.getSeconds()+ss );
        $('#defaultCountdown').countdown({until:austDay , compact: true,format: 'dHMs',expiryText: 'No More Counter for you'});
        }

        $(function () {
          stringToCountdown('#defaultCountdown6','000005');
       });

Should I rewrite this to make it simpler and faster?

You may combine var statements and put them top of your function. Strip unused variables like parity and use element variable instead of using #defaultCountdown directly. And lastly, a little formatting will make your code much readable. Here is the result.

If you're trying to accomplish relative countdown, plugin itself supports it. I also put an example to show how to do it.

function stringToCountdown(selector, str){
    var hh = parseInt(str.substr(0,2), 10),
        mm = parseInt(str.substr(2,2), 10),
        ss = parseInt(str.substr(4,2), 10),
        austDay = new Date();

    austDay = new Date(
        austDay.getFullYear(),
        austDay.getMonth(),
        austDay.getDate(),
        austDay.getHours() + hh,
        austDay.getMinutes() + mm,
        austDay.getSeconds() + ss
    );

    $(selector).countdown({
        until: austDay,
        compact: true,
        format: 'dHMs',
        expiryText: 'No More Counter for you'
    });
}

$(function () {
    stringToCountdown('#defaultCountdown','000010');
});

And this is less readable version. There is no extra variable. So it may run a little bit faster.

function stringToCountdown(selector, str){
    var austDay = new Date();
    $(selector).countdown({
        until: new Date(
            austDay.getFullYear(),
            austDay.getMonth(),
            austDay.getDate(),
            austDay.getHours() + parseInt(str.substr(0,2), 10),
            austDay.getMinutes() + parseInt(str.substr(2,2), 10),
            austDay.getSeconds() + parseInt(str.substr(4,2), 10)
        ),
        compact: true,
        format: 'dHMs',
        expiryText: 'No More Counter for you'
    });
}

$(function () {
    stringToCountdown('#defaultCountdown','000010');
});


Read .csv files and convert the rows into dict for looping This script tries to parse .csv files and returns an iterable object to fetch one row at a time to do some process. It works fine but I think it needs improvements to make it efficient.

    import os
    from csv import DictReader

    class CSVHandler:
        DELIMIT = ','  # delimiter for csv
        FIELDS = set(list(['foo', 'bar']))  # fields that I want

        def __init__(self, file_path: str):
            self.file_path = file_path
            self.file_obj = None
            self.reader = DictReader([])

        def read_file(self):
            if self._is_file_ok:
                try:
                    self.file_obj = open(self.file_path, newline='')
                    self.reader = DictReader(self.file_obj)
                    unmatched = self._is_fields_ok
                    if isinstance(unmatched, set):
                        print(f"Warning : field set's unmatched! {unmatched}")
                except IOError:
                    print(f'Unable to open/read file : "{self.file_path}"')
            else:
                print(f'Invalid file : "{self.file_path}"')
            return self

        @property
        def _is_file_ok(self):
            if os.path.isfile(self.file_path):
                if os.path.exists(self.file_path):
                    if self.file_path.endswith('.csv'):
                        return True
            return False

        @property
        def _is_fields_ok(self):
            if self.reader or not self.FIELDS:
                return self.FIELDS - set(self.reader.fieldnames)
            return False

        def _trim_row(self, row: dict):
            trimmed_row = dict.fromkeys(self.FIELDS, None)
            for field in self.FIELDS:
                if field in row:
                     trimmed_row[field] = row[field]
            return trimmed_row

        def __enter__(self):
            return self

        def __iter__(self):
            return (self._trim_row(dict(row)) for row in self.reader)

        def __next__(self):
            return self._trim_row(dict(next(self.reader)))

        def __len__(self):
            return len(list(self.reader))

        def __exit__(self, exc_type, exc_val, exc_tb):
            if self.file_obj is not None:
                self.file_obj.close()

    if __name__ == '__main__':
        with CSVHandler('file_name.csv').read_file() as csv_h:
            for rows in csv_h:
                pass
```

Welcome to CR!

As others recommended, you need to be more clear. I can give you some stylistic critique.

I like that you are using type hinting in the parameters. I recommend you also hint the return types for your functions like:

def _trim_row(self, row: dict) -> list:
            trimmed_row = dict.fromkeys(self.FIELDS, None)
            for field in self.FIELDS:
                if field in row:
                     trimmed_row[field] = row[field]
            return trimmed_row

Now, more importantly I recommend you create strong documentation for your code so that we can understand the idea behind it, what bugs it has, as well as its efficiency failures (you can use codetags such as # BUG: or # FIXME:).

For your convenience, you can also edit your code in an IDE that enables pylinting, where you can get suggestions about how stylistically good your code is, I recommend VS Code with the Python and autoDocstring extensions.

By putting your code in VS Code, I got the following suggestions for improvements:

""" [INSERT MODULE DESCRIPTION] """

import os
from csv import DictReader

class CSVHandler:
    """[INSERT CLASS DESCRIPTION]
    """
    DELIMIT = ','  # delimiter for csv
    FIELDS = set(list(['foo', 'bar']))  # fields that I want

    def __init__(self, file_path: str):
        """[summary]

        Arguments:
            file_path {str} -- [description]
        """
        self.file_path = file_path
        self.file_obj = None
        self.reader = DictReader([])

    def read_file(self):
        """[summary]

        Returns:
            [type] -- [description]
        """
        if self._is_file_ok:
            try:
                self.file_obj = open(self.file_path, newline='')
                self.reader = DictReader(self.file_obj)
                unmatched = self._is_fields_ok
                if isinstance(unmatched, set):
                    print(f"Warning : field set's unmatched! {unmatched}")
            except IOError:
                print(f'Unable to open/read file : "{self.file_path}"')
        else:
            print(f'Invalid file : "{self.file_path}"')
        return self

    @property
    def _is_file_ok(self):
        """[summary]

        Returns:
            [type] -- [description]
        """
        if os.path.isfile(self.file_path):
            if os.path.exists(self.file_path):
                if self.file_path.endswith('.csv'):
                    return True
        return False

    @property
    def _is_fields_ok(self):
        """[summary]

        Returns:
            [type] -- [description]
        """
        if self.reader or not self.FIELDS:
            return self.FIELDS - set(self.reader.fieldnames)
        return False

    def _trim_row(self, row: dict):
        """[summary]

        Arguments:
            row {dict} -- [description]

        Returns:
            [type] -- [description]
        """
        trimmed_row = dict.fromkeys(self.FIELDS, None)
        for field in self.FIELDS:
            if field in row:
                trimmed_row[field] = row[field]
        return trimmed_row

    def __enter__(self):
        return self

    def __iter__(self):
        return (self._trim_row(dict(row)) for row in self.reader)

    def __next__(self):
        return self._trim_row(dict(next(self.reader)))

    def __len__(self):
        return len(list(self.reader))

    def __exit__(self, exc_type, exc_val, exc_tb):
        if self.file_obj is not None:
            self.file_obj.close()

if __name__ == '__main__':
    with CSVHandler('file_name.csv').read_file() as csv_h:
        for rows in csv_h:
            pass

Another suggestion that I can give you is to know what you are importing and import just what you need. So, import os should be replaced with from os import path and remove os. from if os.path.isfile(self.file_path): and if os.path.exists(self.file_path):.

Following this, you will understand your code better, and you will be able to ask more specific questions about it.


Draw the table like 6³ = 3³ + 4³ + 5³ to 100³ = 35³ + 70³ + 85³ I want to draw the table like this:

6³ = 3³ + 4³ + 5³
9³ = 1³ + 6³ + 8³
12³ = 6³ + 8³ + 10³
18³ = 2³ + 12³ + 16³
18³ = 9³ + 12³ + 15³
19³ = 3³ + 10³ + 18³
20³ = 7³ + 14³ + 17³
.....
100³ = 35³ + 70³ + 85³

I've tried this:

$start = microtime(true);
funcC(100);
echo microtime(true) - $start;

function funcC($n){

    $tnum = 3;
    $s = '³';

    $testmax = $n-$tnum;
    $p3a = array();

    $numlist = array_fill(0, 10, array());

    for ($i = 0; $i <= $n; $i++) {
        $j = pow($i,3);
        $p3a[] = $j;
        $numlist[$j%10][$j] = $i;
    }

    for ($i = $tnum; $i <= $n; $i++) {
        $ipow = $p3a[$i];
        for ($j = 1; $j <= $i; $j++) {

            for ($k = $j+1; $k <= $testmax+2; $k++) {

                if($p3a[$j]+$p3a[$k] > $ipow){break;}

                $diff = $ipow - ($p3a[$j]+$p3a[$k]);
                $diff_t =  $diff%10;

                if(isset($numlist[$diff_t][$diff]) && $numlist[$diff_t][$diff]>$k ){

                    echo " $i$s  =  $j$s + $k$s + ".$numlist[$diff_t][$diff].$s.'<br>'.PHP_EOL;
                    break;
                }
            }
        }
    }
}

It is ok, but I want to know a faster way of doing this.

This code uses 0.59064292907715 as test code here.

I would make a few changes for readability:

Rename:

$p3a → $cubes
$numlist → $cubeRoots

Hard-code $tnum.  It's not going to vary anyway, since it wasn't a parameter.
Eliminate $testmax.  It's not worth the effort to save a few loop iterations.
More generous horizontal spacing.  (You use lots of newlines in your source code, but need more spaces.)

Changing $numlist from a two-level array to a 1-dimensional array results in better readability as well as a performance improvement.

$i * $i * $i is simpler and faster than pow($i, 3).

Changing the termination condition of your inner loop results in an even more dramatic performance improvement.

Overall, this completes in about 1/3 of the time of the original code:

function funcC($n) {
    $exp = '³';

    $cubes = array();
    $cubeRoots = array();

    for ($i = 0; $i <= $n; $i++) {
        $j = $i * $i * $i;
        $cubes[$i] = $j;
        $cubeRoots[$j] = $i;
    }

    for ($i = 3; $i <= $n; $i++) {

        for ($j = 1; $j <= $i; $j++) {
            for ($k = $j; ($diff = $cubes[$i] - $cubes[$j] - $cubes[$k]) >= $cubes[$k]; $k++) {
                if (isset($cubeRoots[$diff])) {
                    echo " $i$exp  =  $j$exp + $k$exp + " . $cubeRoots[$diff] . $exp . '<br>' . PHP_EOL;
                    break;
                }
            }
        }

    }

}


Two implementations of website internationalization I have attempted to create an internationalization system for my PHP framework that I'm working on.

For the purpose I decided I will be using MySQL to store languages and translations. Respectively I have the tables

languages
id  | name
----+--------
1   | English
2   | Spanish

translations
id | 1             | 2           | n ...
---+---------------+-------------+------
1  | Hello, $user  | Hola, $user |   ...
2  | Friend        | Amigo       |   ...

I was told that this is not a normalized database structure. I think that this structure is easier to use, because if I were to add a column lang_id where I'd store the id of the language the string represents, then when I'm selecting I'd have to do

SELECT string FROM translations WHERE id = ? AND lang_id = {$lang_id}

Instead of what I currently use

SELECT {$lang_id} FROM translations WHERE id = ?

It looks simpler to me, also avoids the use of complex primary keys and uses less memory too. If I'm not correct please don't hesitate to criticize!

I have created two implementations of the logic class, one using eval in its base, other one using preg_replace_callback.

First implementation: Eval

class Translator {
    private $stmt = null;
    private static $instance;

    public static function getInstance(){
        if(!self::$instance){
            self::$instance = new self;
        }
        return self::$instance;
    }

    private function __construct() {
        $this->stmt = \X\Database::connection()->prepare('SELECT '.$_SESSION['lang_id'].' FROM translations WHERE id = ?')->getStmt();
    }

    public function get($id, $variables){
        $this->stmt->execute(array($id));
        foreach($variables as $k => $v){
            $$k = $v;
        }
        unset($id); unset($variables); unset($k); unset($v);

        return eval('return "'.addslashes($this->stmt->fetch(\PDO::FETCH_NUM)[0]).'";');
    }
}

Example usage in a view, assuming $t = \X\Translator::getInstance();

With variables

<?= $t->get(1, array('user'=>'John Doe')) ?>

Without variables

<?= $t->get(2) ?>

Second implementation: Regular Expressions

class Translator {
    public static function init(){
        ob_start();

        register_shutdown_function('\X\Translator::translateDocument');
    }

    public static function translateDocument(){
        $t = \X\Database::connection()->prepare('SELECT '.$_SESSION['lang_id'].' FROM translations WHERE id = ?')->getStmt();

        echo preg_replace_callback('/\{\{\s*(\d+)\s*(?:,(.+?))?\s*}}/', function($matches) use($t){
            $t->execute(array($matches[1]));

            if(count($matches) > 2){
                $keys = array();
                $vals = array();
                preg_replace_callback('/([^\s]+):\s*([^\;]+);/', function($matchesInner) use(&$keys, &$vals){
                    $keys[] = $matchesInner[1];
                    $vals[] = $matchesInner[2];
                }, $matches[2]);
                return str_replace($keys,$vals,$t->fetch(\PDO::FETCH_NUM)[0]);
            }else{
                return $t->fetch(\PDO::FETCH_NUM)[0];
            }
        }, ob_get_clean());
    }
}

Example usage, assuming that \X\Translator::init() has been called

With variables

{{ 1, $user: John Doe; }}

Without variables

{{ 2 }}

Finally

I ran a benchmark consisting of 5 runs of 1000 translations each, showing the statistics

#Average execution time
    eval:  0.65 sec
    regex: 1.15 sec

#Memory used
    eval:  240 kb
    regex: 253 kb

Creating the translations table with an indefinite number of weirdly named columns is a bad idea. Subsequently adding a language will be awkward: it involves ALTERing the table, then a series of UPDATEs.

I suggest a table with normalization…

CREATE TABLE translations (
    id INTEGER NOT NULL,
    lang_id INTEGER NOT NULL,
    string VARCHAR(???),
    PRIMARY KEY (id, lang_id),
    FOREIGN KEY (lang_id) REFERENCES languages (id)
);

Then, for your programming convenience, create a view for each language that you support.

CREATE OR REPLACE VIEW en AS
    SELECT string
    FROM translations AS t
        JOIN languages AS l
            ON t.lang_id = l.id
    WHERE l.name = 'English';

Alternatively, define a stored procedure to satisfy your laziness.

That way, your schema stays normalized.  Adding a view is less risky than altering a table. Even your queries read better:

SELECT string FROM en WHERE id = ?;

However, for performance, I think you would be better off querying and caching all of the strings (probably a few hundred — no big deal) in PHP than issuing a separate query per string.


How to deal with interface inheritance and common properties? I'm trying to design a generic caching system that takes keyed items and allows either read-only or read-write access to a cached version of it. The read-only backing interface is:

public interface IReadableItem<TKey>
{
  TKey Key { get; }
}

However, I need to be able to dynamically update the key of my writable items. I've come up with two options, but both are unappealing.

I can forgo the inheritance:

public interface IWritableItem<TKey>
{
  TKey Key { get; set; }
}

... but this leaves me in a situation where I have to specify that every class is both an IWritableItem and an IReadableItem in order to allow read-write access.

On the other hand, I can use the new keyword to override the underlying inheritence:

public interface IWritableItem<TKey> : IReadableItem<TKey>
{
  new TKey Key { get; set; }
}

... but this leaves me with a bad code-smell, especially when attempting to explicitly implement the interface at the class level.

Is this a situation where I should just take the lesser of two evils, or is there a Third Way?

What I would do is to use inheritance, but have only setter in IWritableItem:

public interface IReadableItem<TKey>
{
    TKey Key { get; }
}

public interface IWritableItem<TKey> : IReadableItem<TKey>
{
    new TKey Key { set; }
}

This still works as expected:

class Foo<T> : IWritableItem<T>
{
    public T Key { get; set; }
}

It also has the advantage that you can't implement the getter for IWritableItem differently from the getter for IReadableItem.


HNews "ask section" page scraping Python script Here is a small script I wrote to get the HNews ask section and display them without using a web browser.  I'm just looking for feedback on how to improve my style/coding logic/overall code.

#!/usr/bin/python

'''This script gets the headlines from hacker news ask section'''

import urllib2
import HTMLParser
import re

class HNParser(HTMLParser.HTMLParser):
def __init__(self):
    HTMLParser.HTMLParser.__init__(self)
    self.data=[]
    self.recording=0

def handle_starttag(self, tag, attribute):
    if tag!='a':
        return
    elif self.recording:
        self.recording +=1
        return
    for name, value in attribute:
        if name=='href' and value[0]=='i':
            break
    else:
        return
    self.recording=1

def handle_endtag(self, tag):
    if tag=='a' and self.recording:
        self.recording-=1

def handle_data(self, data):
    if self.recording:
        self.data.append(data)

HOST='http://news.ycombinator.com/ask'
parser=HNParser()
f=urllib2.urlopen(HOST)
rawHTML=f.read()
parser.feed(rawHTML)
i=0
for items in parser.data:
    try:
        print parser.data[2*i]
        i+=1
    except IndexError:
        break
 parser.close()

This is how I would modify your script. Comments are inline. This version is PEP8-PyLint-PyFlakes approved. ;-)

#!/usr/bin/python

'''This script gets the headlines from hacker news ask section'''

import urllib2
import HTMLParser
# remove unused imports

class HNParser(HTMLParser.HTMLParser):

    # use class-level attribute instead of "magic" strings.
    tag_name = 'a'

    def __init__(self):
        HTMLParser.HTMLParser.__init__(self)
        self.data = []
        self.recording = 0

    def handle_starttag(self, tag, attribute):

        if tag != self.tag_name:
            return

        # clearer implicit loop, with no "break"
        if not any(name == 'href' and value.startswith('item')
                for name, value in attribute):
            return

        # no need to check if self.recording == 0, because in that case setting
        # self.recording = 1 is equivalent to incrementing self.recording!
        self.recording += 1

    def handle_endtag(self, tag):
        if tag == self.tag_name and self.recording:
            self.recording -= 1

    def handle_data(self, data):
        if self.recording:
            self.data.append(data)

def main():
    HOST = 'http://news.ycombinator.com/ask'
    parser = HNParser()
    f = urllib2.urlopen(HOST)
    rawHTML = f.read()
    parser.feed(rawHTML)
    try:
        # use fancy list indexing and omit last "Feature Request" link
        for item in parser.data[:-1:2]:
            print item
    finally:
        # close the parser even if exception is raised
        parser.close()

if __name__ == '__main__':
    main()


Project Euler #3 - how inefficient is my code? So I am essentially a complete newbie to programming, and have been attempting to learn Python by completing the Project Euler problems. I haven't gotten very far, and this is my code for problem #3 :

  The prime factors of 13195 are 5, 7, 13 and 29.
  What is the largest prime factor of the number 600851475143 ?

Although my solution works, I'd like to know how I can improve.

primes = [2]
factors = []

def isPrime(x):
    a = 1
    if x == 1:
        return False
    while a < x:
        a += 1
        if x % a == 0 and a != x and a != 1:
            return False
            break
    return True

def generatePrime():
    a = primes[-1]+1
    while isPrime(a) == False:
        a += 1
    primes.append(a)

def primeFactor(x):
    a = primes[-1]
    while a <= x:
        if x % a == 0:
            factors.append(a)
            x /= a
        generatePrime()
        a = primes[-1]

primeFactor(input("Enter the number: "))
print("The prime factors are: " + str(factors) + "\nThe largest prime factor is: " + str(sorted(factors)[-1]))

You can save quite a bit time on your prime generation. What you should keep in mind is that a prime is a number which is no multiple of a prime itself; all other numbers are.

So in your isPrime function you can just go through your primes list and check if each prime is a divisor of the number. If not, then it is a prime itself. Of course you would need to make sure that you fill your primes list enough first.

As the most basic idea, you only need to check until sqrt(n), so you only generate numbers this far. And you can also just skip every even number directly. You could also make similar assumptions for numbers dividable by 3 etc., but the even/uneven is the simplest one and enough to get fast results for not too big numbers.

So a prime generation algorithm, for possible prime divisors up to n, could look like this:

primes = [2]
for i in range(3, int(math.sqrt(n)), 2):
    isPrime = not any(i % p == 0 for p in primes)
    if isPrime:
        primes.append(i)

Then to get the prime factors of n, you just need to check those computed primes:

primeFactors = []
m = n
for p in primes:
    while m % p == 0:
        m = m / p
        primeFactors.append(p)
    if m == 0:
        break

print('The prime factorization of `{0}` is: {1}'.format(n, '×'.join(map(str,primeFactors))))

For the euler problem 3 with n = 317584931803, this would produce the following output:

  The prime factorization of 317584931803 is: 67×829×1459×3919