indexing - Data structure to represent piecewise continuous range? -

-

say have integer-indexed array of length 400, , want drop out few elements beginning, lots end, , middle too, without altering original array. is, instead of looping through array using indices {0...399}, want use piecewise continuous range such as

{3...15} ∪ {18...243} ∪ {250...301} ∪ {305...310}

what data structure describe kind of index ranges? obvious solution make "index mediator" array, containing mappings continuos zero-based indexing new coordinates above, feels quite wasteful, since elements in sequential numbers, few occasional "jumps". besides, if find that, oh, want modify range bit? whole index array have rebuilt. not nice.

a few points note:

  • the ranges never overlap. if new range added data structure, , overlaps existing ranges, whole thing should merged. is, if add above example range {300... 308}, should instead replace last 2 ranges {250...310}.
  • it should quite cheap loop through whole range.
  • it should relatively cheap query value directly: "give me original index corresponding 42nd index in mapped coordinates".
  • it should possible (though maybe not quite cheap) work other way round: "give me mapped coordinate corresponding 42 in original coordinates, or tell if it's mapped @ all."

before rolling own solution, i'd know if there exists well-known data structure solves class of problems elegantly.

thanks!

seems array or list of integer pairs best data structure. choice whether second integer of pair end point or count first integer.

edit: on further reflection, problem database index has do. if integer pairs don't have in numeric order, can handle splits easier. if number sequence has remain in order, need data structure allows add integer pairs middle of array or list.

a split having change (6, 12) integer pair (6, 9) (11, 12), when 10 removed, example.

besides, if find that, oh, want modify range bit? whole index array have rebuilt. not nice.

true. perhaps 1 integer pair needs change. worst case, you'd have rebuild entire array or list.


Comments

Post a Comment

Popular posts from this blog

android - Spacing between the stars of a rating bar? -

-
ho can set spacing beween stars? thats ratingbar: ratingbar = (ratingbar) inflater.inflate(r.layout.ratingbar, null); ratingbar.setlayoutparams(new layoutparams(layoutparams.wrap_content, layoutparams.wrap_content)); the layout: <?xml version="1.0" encoding="utf-8"?> <ratingbar xmlns:android="http://schemas.android.com/apk/res/android" style="@style/mystyle" android:layout_alignparentright="true" android:layout_height="19dp" android:layout_width="wrap_content" android:numstars="5"> </ratingbar> the style: <style name="mystyle" parent="@android:style/widget.ratingbar"> <item name="android:progressdrawable">@drawable/android_r2_ratingstar_yellow</item> <item name="android:indeterminatedrawable">@drawable/android_r2_ratingstar_grey</item> </style> thanks, cheers you have ...
Read more

html - Instapaper-like algorithm -

-
does of algorithm extracts contents webpage? instapaper ? there 2 steps instapaper does: find main content block on page (excluding headers, footers, menus etc) from content block extract , format text to find content block (typically html block element, div containing key page text content) instapaper uses algorithm 1 used readability . can @ source of readability.js see what's going on, @ core tries find area on page highest text/link ratio, although has other simple scoring metrics (e.g. off top of head, things ratio of text commas, para elements etc) go heuristics. once have identified root node element, relevant content, you'll need format it, if want can pull node element containing text out of source document , insert yours, in reality you'll want remove existing styles , apply own, standard , feel. if want output nice text-only can use jericho's renderer . update1 : should mention else instapaper - follow 'pagination' links (...
Read more

c# - How to execute a particular part of code asynchronously in a class -

-
i creating speech recognition engine that's going respond user commands.i have created button enable , disable speech recognition per user convenience.i have used dispose() of speech engine disable speech recoginition.here code private void button1_click(object sender, routedeventargs e) { engineon = !engineon; if (engineon) { speechengine = speech.createspeechengine(); //speech class creates , returns new speech engine. speechengine.audiolevelupdated += new eventhandler<audiolevelupdatedeventargs>(speechengine_audiolevelupdated); // use system's default microphone speechengine.setinputtodefaultaudiodevice(); speechengine.loadgrammar(new dictationgrammar()); // start listening speechengine.recognizeasync(recognizemode.multiple); } else { speechclass.myengine.dispose(); } } but disposal of speech obj...
Read more