array set ::grid {}
array set ::rows {}
array set ::columns {}

#
# The parent size
#
set pwidth 336
set pheight 400

array set ::requests {
 .w1,width 40
 .w1,height 20

 .w2,width 60
 .w2,height 30

 .w3,width 100
 .w3,height 100

 .wb4,width 50
 .wb4,height 50
}

proc _grid.insert {path column row _sticky_ sticky _colspan_ colspan} {
 global grid rows columns

 if {![info exists grid($path)]} {
  lappend grid(list) $path
 }
 set grid($path,column) $column
 set grid($path,row) $row
 set grid($path,columnratio) 0
 set grid($path,rowratio) 0
 set grid($path,sticky) $sticky ;#TODO verify $sticky
 set grid($path,columnspan) $colspan ;#TODO verify $colspan


 if {![info exists rows($row,list)]} {
  lappend rows($row,list) $path
 } else {
  set rows($row,list) [_grid.layout.insert $path $rows($row,list) column]
 }

 if {![info exists colums($column,list)]} {
  lappend columns($column,list) $path
 } else {
  set columns($column,list) [_grid.layout.insert $path $columns($column,list) row]
 }

 _grid.layout
}


#key is generally column or row
proc _grid.layout.insert {p list key} {
 global grid

 set inserted 0

 set list [lsort -unique $list]

 #insert the item in a sorted fashion into the list
 for {set i 0} {$i < [llength $list]} {incr i} {
  set e [lindex $list $i]
  set ca $grid($e,$key)
  set cb $grid($p,$key)

  #puts "$e:$ca $p:$cb"

  if {$cb < $ca} {
   set list [linsert $list $i $p]
   set inserted 1
   break
  } elseif {$cb == $ca} {
   #THIS IS INVALID
   return -code error "2 widgets are in the same grid $key $ca.  These widgets are $e and $p."
  }
 }

 if {!$inserted} {
  lappend list $p
 }
 return $list
}

proc _grid.layout.find.peak.columns {} {
 global rows grid
 set r 0
 #
 # Find the peak number of columns.
 #
 foreach {key rowlist} [array get rows *,list] {
  set peak 0
  foreach p $rowlist {
   incr peak $grid($p,columnspan)
  }
  if {$peak > $r} {
   set r $peak
  }
 }
 return $r
}


proc _grid.layout {} {
 global grid requests pwidth pheight rows columns

 array set columnwidths {}

 set peakcolumns [_grid.layout.find.peak.columns]

 if {$peakcolumns <= 0} {
  #empty grid?
  return
 }

 #
 # Set the width for the grid widgets.
 #
 foreach {key rowlist} [array get rows *,list] { 
  #puts $rowlist

  set totalwidth $pwidth
  set c $peakcolumns

  #
  # Make the first pass, and set the initial widths.
  #
  foreach p $rowlist {
   catch {unset grid($p,widthset)}
   set reqw $requests($p,width) 
   set w [expr {$totalwidth * $grid($p,columnspan) / $c}]

   if {[lsearch -exact $grid($p,sticky) width] < 0} {
    if {$reqw < $w} {
     set w $reqw
     set grid($p,widthset) 1
    }
   }

   for {set i 0} {$i < $grid($p,columnspan)} {incr i} {
    set col [expr {$i + $grid($p,column)}]

    if {[info exists columnwidths($col)]} {
     if {$w > $columnwidths($col)} {
      set columnwidths($col) [expr {$w / $grid($p,columnspan)}]
     } else {
      set w $columnwidths($col)
     }
    } else {
     set columnwidths($grid($p,column)) $w
    }
   }

   set grid($p,width) $w
   set totalwidth [expr {$totalwidth - $w}]
   incr $grid($p,columnspan)
  }

  #
  # Make a 2nd pass, and set the growable regions to a larger size.
  #
  set totalwidth $pwidth
  set c $peakcolumns

  set growable [list]

  foreach p $rowlist {
   if {[info exists grid($p,widthset)]} {
    set c [expr {$c - $grid($p,columnspan)}]
    set totalwidth [expr {$totalwidth - $grid($p,width)}]
   } else {
    lappend growable $p
   }
  }

  continue
  if {$c > 0} {
   #
   # We have at least 1 widget that is growable, 
   # due to the constrained size of others.
   #
   foreach p $growable {
    set w [expr {$totalwidth * $grid($p,columnspan) / $c}]
    set columnwidths($grid($p,column)) $w
    set grid($p,width) $w
   }
  }
 }

 parray columnwidths
# parray grid
}

if 0 {
 Rules:

  when -sticky [list width] use the maximum space for the slot according to the space ratio
  when -sticky {} use the request unless request > maximium space for the slot
  when -row is equal to another widget's -row and -column is equal to another widget's -column then go by the order of processing

}


#scrollbar (4 is also a test, instead of 3)
_grid.insert .w1 4 0 -sticky [list height] -columnspan 2
_grid.insert .w2 1 0 -sticky [list width height] -columnspan 1
puts 3:[time {_grid.insert .w3 2 0 -sticky [list width height]  -columnspan 1}]
puts 4:[time {_grid.insert .wb4 1 1 -sticky [list width height] -columnspan 1}]
parray grid