// Finds value for all empty cells with index >=k
 bool backtrack(int k)
 {
     if (k >= bt.size())
         return true;
     int i = bt[k].first;
     int j = bt[k].second;
     // fast path - only 1 possibility
     if (cells[i][j].value)
         return backtrack(k + 1);
     auto constraints = cells[i][j].constraints;
     // slow path >1 possibility.
     // making snapshot of the state
     array<array<cell,9>,9> snapshot(cells);
     for (int v = 1; v <= 9; v++) {
         if (!constraints[v]) {
             if (set(i, j, v)) {
                 if (backtrack(k + 1))
                     return true;
             }
             // restoring from snapshot,
             // note: computationally this is cheaper
             // than alternative implementation with undoing the changes
             cells = snapshot;
         }
     }
     return false;
 }

void MainWindow::slotCopy()
{
  if(opt.arg_debug) printf("slotCopy\n");
  QPixmap pm;
  snapshot(pm);
  QApplication::clipboard()->setPixmap(pm);
}

static void frame_complete(void) {
    ++frame;
    
    if (snapshot_prefix || compare_prefix) {
        Image::Image *ref = NULL;
        if (compare_prefix) {
            char filename[PATH_MAX];
            snprintf(filename, sizeof filename, "%s%04u.png", compare_prefix, frame);
            ref = Image::readPNG(filename);
            if (!ref) {
                return;
            }
            if (retrace::verbosity >= 0)
                std::cout << "Read " << filename << "\n";
        }
        
        Image::Image src(window_width, window_height, true);
        snapshot(src);

        if (snapshot_prefix) {
            char filename[PATH_MAX];
            snprintf(filename, sizeof filename, "%s%04u.png", snapshot_prefix, frame);
            if (src.writePNG(filename) && retrace::verbosity >= 0) {
                std::cout << "Wrote " << filename << "\n";
            }
        }

        if (ref) {
            std::cout << "Frame " << frame << " average precision of " << src.compare(*ref) << " bits\n";
            delete ref;
        }
    }
    
    ws->processEvents();
}

NSPStatus 
Namespace::namespaceSaveToXml(std::string filepath)
{
	// add xml header
	XMLNode xMainNode = XMLNode::createXMLTopNode("xml", TRUE);
	xMainNode.addAttribute_("version",		XML_VERSION);
	xMainNode.addAttribute_("encoding",		XML_ENCODING);
	xMainNode.addAttribute_("standalone",	XML_STANDALONE);

	// add namespace header
	XMLNode node = xMainNode.addChild(XML_NSP_HEADER_NODE_NAME);
	node.addAttribute_("version",			 XML_NSP_VERSION);
	node.addAttribute_("xmlns:xsi",			 XML_NSP_SCHEMA_INSTANCE);
	node.addAttribute_("xsi:schemaLocation", XML_NSP_SCHEMA_LOCATION);
	
	// add application header 
	XMLNode appHeader = node.addChild(m_appName.data());
	appHeader.addAttribute_("appName",		m_appName.data());
	appHeader.addAttribute_("appVersion",	m_appVersion.data());
	appHeader.addAttribute_("creatorName",	m_creatorName.data());
	
	TTNodePtr root = NSPDirectory->getRoot();
	
	// recursive method to get the namespace and build the xml tree
	snapshot(appHeader, root);
	
	// write the datas in xml file
	xMainNode.writeToFile(filepath.c_str(), XML_ENCODING);

	return NSP_NO_ERROR;
}

void wavetable_normalize(void *vol, void *unused2, void *unused3)
{
	snapshot(S_T_WAVE_DATA);
		
	CydWavetableEntry *w = &mused.mus.cyd->wavetable_entries[mused.selected_wavetable];
	
	if (w->samples > 0)
	{
		int m = 0;
				
		for (int s = 0 ; s < w->samples ; ++s)
		{
			m = my_max(m, abs(w->data[s]));
		}
		
		debug("Peak = %d", m);
		
		if (m != 0)
		{
			for (int s = 0 ; s < w->samples ; ++s)
			{
				w->data[s] = my_max(my_min((Sint32)w->data[s] * CASTPTR(int, vol) / m, 32767), -32768);
			}
		}
		
		invalidate_wavetable_view();
	}

vespalib::string
StateReporter::getMetrics(const vespalib::string &consumer)
{
    metrics::MetricLockGuard guard(_manager.getMetricLock());
    std::vector<uint32_t> periods = _manager.getSnapshotPeriods(guard);
    if (periods.empty()) {
        return ""; // no configuration yet
    }
    uint32_t interval = periods[0];

    // To get unset metrics, we have to copy active metrics, clear them
    // and then assign the snapshot
    metrics::MetricSnapshot snapshot(
            _manager.getMetricSnapshot(guard, interval).getName(), interval,
            _manager.getActiveMetrics(guard).getMetrics(), true);

    snapshot.reset(0);
    _manager.getMetricSnapshot(guard, interval).addToSnapshot(
            snapshot, _component.getClock().getTimeInSeconds().getTime());

    vespalib::asciistream json;
    vespalib::JsonStream stream(json);
    metrics::JsonWriter metricJsonWriter(stream);
    _manager.visit(guard, snapshot, metricJsonWriter, consumer);
    stream.finalize();
    return json.str();
}

void keyboard(unsigned char key, int x, int y)
{
	static bool quadview=true;
	switch(key)
	{
	case 'P':
	case 'p':
		{
			static char filename[25];
			double timing=getElapsedTime();

			snprintf(filename, sizeof(filename), "%011.6lf.%s", timing, suffix);
			printf("snapshot parameters: %dx%d, %s\n", width, height, filename);
			snapshot(width, height, filename);
		}
		break;
	case 'Q':
	case 'q':
		glutDisplayFunc(quadview?display:display4);
		quadview=!quadview;
		break;
	case 27: /* ESC */
		exit(EXIT_SUCCESS);
		break;
	}

	glutPostRedisplay();
}

void wavetable_drop_lowest_bit(void *unused1, void *unused2, void *unused3)
{
	if (!mused.wavetable_bits)
	{
		debug("Wave is silent");
		return;
	}
		
	snapshot(S_T_WAVE_DATA);
		
	const CydWavetableEntry *w = &mused.mus.cyd->wavetable_entries[mused.selected_wavetable];
	
	Uint16 mask = 0xffff << (__builtin_ffs(mused.wavetable_bits));
	
	if (w->samples > 0)
	{
		int d = 0;
				
		for (; d < w->samples ; ++d)
		{
			w->data[d] &= mask;
		}
		
		invalidate_wavetable_view();
	}
}

void root_node(shared_ptr<Net<Dtype> > net, int iters, Dtype lr)
{
    const std::vector<Blob<Dtype>*>& result = net -> output_blobs();

    boost::posix_time::ptime timer = boost::posix_time::microsec_clock::local_time();

    MPI_Status status;
    std::vector<Blob<Dtype>*> bottom_vec;
    float loss;

    init_buffer(iters, FLAGS_snapshot_intv, net);

    for (int i = 0; i < iters; i++) {

        MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

        ApplyUpdate(net, lr, status.MPI_SOURCE);
        std::cout << i << std::endl;

        if (i % FLAGS_snapshot_intv == 0)
            snapshot(net, i, (boost::posix_time::microsec_clock::local_time() - timer).total_milliseconds());
    }

    save_snapshot(FLAGS_snap_path);
}

void notifyNodeRemovedFromDocument(ContainerNode& insertionPoint, Node& node)
{
    ASSERT(insertionPoint.inDocument());
    node.removedFrom(insertionPoint);

    if (!is<ContainerNode>(node))
        return;
    ChildNodesLazySnapshot snapshot(node);
    while (RefPtr<Node> child = snapshot.nextNode()) {
        // If we have been added to the document during this loop, then we
        // don't want to tell the rest of our children that they've been
        // removed from the document because they haven't.
        if (!node.inDocument() && child->parentNode() == &node)
            notifyNodeRemovedFromDocument(insertionPoint, *child.get());
    }

    if (!is<Element>(node))
        return;

    if (node.document().cssTarget() == &node)
        node.document().setCSSTarget(nullptr);

    if (RefPtr<ShadowRoot> root = downcast<Element>(node).shadowRoot()) {
        if (!node.inDocument() && root->host() == &node)
            notifyNodeRemovedFromDocument(insertionPoint, *root.get());
    }
}

TEST( FilesystemSnapshot, managingEntries )
{
   Filesystem& fs = TSingleton< Filesystem >::getInstance();
   FilesystemSnapshot snapshot( fs );
   snapshot.add( FilePath( "/root/assets/b.txt" ), 0, 0 );
   snapshot.add( FilePath( "/root/code/c.lua" ), 0, 0 );
   snapshot.add( FilePath( "/root/assets/a.txt" ), 0, 0 );
   
   std::string snapshotStr = "(0)root;(1)code;(2)c.lua;(1)assets;(2)b.txt;(2)a.txt;";
   CPPUNIT_ASSERT_EQUAL( snapshotStr, snapshot.toString() );

   // removing a non-existing entry from a non-existing directory
   snapshot.remove( FilePath( "/root/gameplay/x.txt" ) );
   CPPUNIT_ASSERT_EQUAL( snapshotStr, snapshot.toString() );

   // removing a non-existing entry from an existing directory
   snapshot.remove( FilePath( "/root/code/x.txt" ) );
   CPPUNIT_ASSERT_EQUAL( snapshotStr, snapshot.toString() );

   // removing an existing entry
   snapshot.remove( FilePath( "/root/assets/a.txt" ) );
   snapshotStr = "(0)root;(1)code;(2)c.lua;(1)assets;(2)b.txt;";
   CPPUNIT_ASSERT_EQUAL( snapshotStr, snapshot.toString() );

   // removing an existing entry
   snapshot.remove( FilePath( "/root/assets" ) );
   snapshotStr = "(0)root;(1)code;(2)c.lua;";
   CPPUNIT_ASSERT_EQUAL( snapshotStr, snapshot.toString() );
}

void ThreadState::postGCProcessing()
{
    checkThread();
    if (gcState() != EagerSweepScheduled && gcState() != LazySweepScheduled)
        return;

    m_didV8GCAfterLastGC = false;
    if (isMainThread())
        m_allocatedObjectSizeBeforeSweeping = Heap::allocatedObjectSize();

#if ENABLE(GC_PROFILE_HEAP)
    // We snapshot the heap prior to sweeping to get numbers for both resources
    // that have been allocated since the last GC and for resources that are
    // going to be freed.
    bool gcTracingEnabled;
    TRACE_EVENT_CATEGORY_GROUP_ENABLED("blink_gc", &gcTracingEnabled);
    if (gcTracingEnabled)
        snapshot();
#endif

    {
        if (isMainThread())
            ScriptForbiddenScope::enter();

        SweepForbiddenScope forbiddenScope(this);
        {
            // Disallow allocation during weak processing.
            NoAllocationScope noAllocationScope(this);
            {
                TRACE_EVENT0("blink_gc", "ThreadState::threadLocalWeakProcessing");
                // Perform thread-specific weak processing.
                while (popAndInvokeWeakPointerCallback(Heap::s_markingVisitor)) { }
            }
            {
                TRACE_EVENT0("blink_gc", "ThreadState::invokePreFinalizers");
                invokePreFinalizers(*Heap::s_markingVisitor);
            }
        }

        if (isMainThread())
            ScriptForbiddenScope::exit();
    }

#if ENABLE(OILPAN)
    if (gcState() == EagerSweepScheduled) {
        // Eager sweeping should happen only in testing.
        setGCState(Sweeping);
        completeSweep();
    } else {
        // The default behavior is lazy sweeping.
        setGCState(Sweeping);
    }
#else
    // FIXME: For now, we disable lazy sweeping in non-oilpan builds
    // to avoid unacceptable behavior regressions on trunk.
    setGCState(Sweeping);
    completeSweep();
#endif
}

ingame_savegame::ingame_savegame(saved_game &gamestate,
					game_display& gui, const config& snapshot_cfg, const compression::format compress_saves)
	: savegame(gamestate, compress_saves, _("Save Game")),
	gui_(gui)
{
	gamestate.set_snapshot(snapshot_cfg);
	snapshot().merge_with(snapshot_cfg);
}

void ReadArchiveTask::run(const volatile Flags &aborted)
{
	QString error;
	Snapshot snapshot(m_container);
	IFileContainerScanner::ScanArguments args = {snapshot, aborted};
	m_container->scanner()->scan(args, error);
	postEvent(new Event(this, Event::ScanComplete, error, aborted, snapshot));
}

ActiveHwndTracker::ActiveHwndTracker(QObject *parent)
    : QObject(parent)
{
    d = new PrivData();
    Hook *hook = new Hook(this);
    this->connect(hook, SIGNAL(activated(HookEvent)), SLOT(snapshot(HookEvent)));
    hook->hookEvent(EVENT_SYSTEM_FOREGROUND);
}

void Puzzle::pretty_print(const OutputSettings& settings) {
    GameBoard tmp = to_game_board();
    m_impl->m_board = tmp.to_string(settings);
    for (PuzzleSnapshot& snapshot_text : m_impl->m_snapshots) {
        GameSnapshot snapshot(snapshot_text.moves(), tmp.variant());
        snapshot_text.moves() = snapshot.to_string(settings);
    }
}

void frame_complete(unsigned call_no) {
    ++frame;

    if (snapshot_frequency == FREQUENCY_FRAME ||
        snapshot_frequency == FREQUENCY_FRAMEBUFFER) {
        snapshot(call_no);
    }
}

void ActionsManager::doAction( int id_action )
{
    switch( id_action )
    {
        case PLAY_ACTION:
            play(); break;
        case STOP_ACTION:
            THEMIM->stop(); break;
        case OPEN_ACTION:
            THEDP->openDialog(); break;
        case PREVIOUS_ACTION:
            THEMIM->prev(); break;
        case NEXT_ACTION:
            THEMIM->next(); break;
        case SLOWER_ACTION:
            THEMIM->getIM()->slower(); break;
        case FASTER_ACTION:
            THEMIM->getIM()->faster(); break;
        case FULLSCREEN_ACTION:
            fullscreen(); break;
        case EXTENDED_ACTION:
            THEDP->extendedDialog(); break;
        case PLAYLIST_ACTION:
            playlist(); break;
        case SNAPSHOT_ACTION:
            snapshot(); break;
        case RECORD_ACTION:
            record(); break;
        case FRAME_ACTION:
            frame(); break;
        case ATOB_ACTION:
            THEMIM->getIM()->setAtoB(); break;
        case REVERSE_ACTION:
            THEMIM->getIM()->reverse(); break;
        case SKIP_BACK_ACTION:
            skipBackward();
            break;
        case SKIP_FW_ACTION:
            skipForward();
            break;
        case QUIT_ACTION:
            THEDP->quit();  break;
        case RANDOM_ACTION:
            THEMIM->toggleRandom(); break;
        case INFO_ACTION:
            THEDP->mediaInfoDialog(); break;
        case OPEN_SUB_ACTION:
            THEDP->loadSubtitlesFile(); break;
        case FULLWIDTH_ACTION:
            if( p_intf->p_sys->p_mi )
                p_intf->p_sys->p_mi->getFullscreenControllerWidget()->toggleFullwidth();
            break;
        default:
            msg_Warn( p_intf, "Action not supported: %i", id_action );
            break;
    }
}

void ingame_savegame::create_filename()
{
	std::stringstream stream;

	const std::string ellipsed_name = font::make_text_ellipsis(gamestate().classification().label,
			font::SIZE_NORMAL, 200);
	stream << ellipsed_name << " " << _("Turn") << " " << snapshot()["turn_at"];
	set_filename(stream.str());
}

void FloorMatSensor::run() {
  // take a snapshot of the mat
  snapshot();
  
  // count people on the mat
  int n = countPeople();
  
  // create a sensor reading and send it to the callback
  _callback(getReading(getValueString(n)));
}