Quickly Determining the Position of Data in an Array

Question

I have a data structure as the image below illustrates. I need to quickly figure out the index of the cells to the right or left of the highlighted cell group.

You can see in the code below I am naively looping through ALL cells at every index to determine if there is a cell at the requested index. This works great when I have a few (hundred) cells, but breaks down quickly when I have thousands of cells.

In this particular case the highlighted group is mobile, and can only move to the index before or after the previous/next occupied cell. So groupMinX/maxX is the minimum and maximum x value it can move based on the position of other cells in the row.

            private var movingGroup:CellGroup; //selected group

 public function getCellAtIndex(index:int):ICell
 {
  for each(var cell:ICell in cells)
  {
   if(cell.index==index)
    return cell;
  }

  return null;
 }

 public function groupMinX(xPos:Number):Number
 {
  var index:int = xPos/cellSize;
  var cellsOnLeft:Array = getAllCellsOnLeft(index-1);
  if(cellsOnLeft.length > 0)
   return cellsOnLeft[cellsOnLeft.length-1].x + cellSize;
  return 0;
 }

 public function groupMaxX(xPos:Number):Number
 {
  var index:int = xPos/cellSize;
  var cellsOnRight:Array = getAllCellsOnRight(index);
  if(cellsOnRight.length > 0)
   return cellsOnRight[0].x;
  return (maxIndex)*cellSize;
 }

 private function getAllCellsOnLeft(ofIndex:int):Array
 {
  var index:int = 1;
  var cells:Array = [];
  while( ofIndex >= 0 )
  {
   var cell:ICell = getCellAtIndex(ofIndex);
   if(cell && !movingGroup.containsCell(cell))
    cells.unshift( cell );
   ofIndex--;
  }
  return cells;  
 }

 private function getAllCellsOnRight(ofIndex:int):Array
 {
  var index:int = 1;
  var cells:Array = [];
  while( index <= maxIndex )
  {
   var cell:ICell = getCellAtIndex( ofIndex + index );
   if(cell && !movingGroup.containsCell(cell))
    cells.push( cell );
   index++;
  }
  return cells;  
 }

What I am looking for is an efficient method for scanning/tracking the cells. The array I am looping through doesn't actually contain the blank cells, but it has the cells with the index property.

Answer 1

Whoops in my tweet I added the wrong link. Use a linked list. Have your 'Cell' class implement a Linked List Node interface. No need to loop or use conditionals.

http://en.wikipedia.org/wiki/Linked%5Flist

Answer 2

You could just pre-cache the indices of the cell on the left and the cell on the right ... Your choice of a data structure is non-ideal. Please describe what you are trying to do at a higher level. Was this data structure given to you, or did you come up with it?

Answer 3

I'm not sure if I am missing something here but if this is a numerically index array of objects (cells), I think you could do something like...

cellsArr[cellsArr.indexOf(cellObj1) - 1] // previous cell    
cellsArr[cellsArr.indexOf(cellObj2) + 1] // get the cell after a "highlighted" cell

Answer 4

As the list is ordered, I would suggest you do a binary search to find your wanted cell. Then, rather than looping through the elements to the left and the right, simply slice the array to form two new arrays of the left and right side.

Something like so, parhaps? (please excuse any syntactical errors, I don't know actionscript...)

private function search(array:Array, index:int, low:int, high:int) :int 
{ 
  if (high < low)
    return -1 
  var middle:int = low + ((high - low) / 2) 
  if (array[middle].index > index)
    return search(array, index, low, middle - 1)
  else if (array[middle].index < index)
    return search(array, index, middle + 1, high)
  else
    return middle 
}  

private function sliceBitsOff(index:int)
{
   var index:int = search(yourArray, 7, 0, yourArray.length-1)
   var rightArray:Array = yourArray.slice(0, index - 1)
   var leftArray:Array = yourArray.slice(index + 1, yourArray.length)
}