Ok I went through it and some of the things I thought I could get rid of were because I've been in C++ for the past 9 months. Anyway I was able to remove a field from the base AdjType that needed to be extended so that brings the foot print down to 8 bytes and if you turn them into shorts 4 bytes. I'd say that's reasonable.
Go over the code and comments and let me know what you think.
Here's the list container, it's Iterator and the type to extend
SuperStrict
'Adjacency List
'This implementation is specialized for maintaining a hierarchy using a left child - right sibling tree
'The main list object.
Type AdjList
Field loopStart:Int 'used to work with Max's built in for...eachin
Field theLists:AdjNode[] 'Since the hierarchy is maintained by consts an array is required to hold the nodes for speed
'no New() method because you can't pass params
'Method New() EndMethod
'Ctor for convenience
Function Create:AdjList(n:Int = 8)
Local temp:AdjList = New AdjList
temp.Init(n)
Return temp
EndFunction
'Set the size of the hierarchy to begin with
'How many types are there?
Method Init(n:Int = 8)
theLists = New AdjNode[n]
For Local i:Int = 0 To n-1
theLists[i] = New AdjNode
Next
EndMethod
'Add an object to the list
Method addObject(o:AdjType)
theLists[o._type].addObject(o)
EndMethod
'Remove an object from the list
Method removeObject(o:AdjType)
theLists[o._type].removeObject(o)
EndMethod
'get a list of a specific type
Method listOfType:AdjType[](n:Int)
Return theLists[n].aList
EndMethod
'add a child to the parent node p
Method addRelationship(p:Int, c:Int)
theLists[p].addChild(c)
theLists[c].setParent(p)
EndMethod
Method From:AdjList(n:Int)
setLoopStart(n)
Return Self
EndMethod
'used to work with Max's built in for...eachin
Method setLoopStart(i:Int)
loopStart = i
End Method
'used to work with Max's built in for...eachin
Method ObjectEnumerator:AdjIterator()
Return AdjIterator.Create(theLists,loopStart)
EndMethod
EndType
'This is the object to extended
Type AdjType
'these could easily become shorts or even possibly bytes
Field _Type:Int 'the type of this object
Field p_Type:Int 'the parent type to this object. -1 = root
'Standard initialization for the adj list doesn't need to be overridden
Method Init(t:Int, p:Int = 0)
_Type = t
p_Type = p
EndMethod
Function ForList:Object() Abstract
End Type
'Holds the info about all the objects and their children and parents
Type AdjNode
Field children:Int[] 'this array holds a list of all the children types to this type
Field aList:AdjType[] 'this is a list of the children to this type: a Linked List could make it more dynamic
Field _type:Int 'the place of this type in the hirearchy
Field p_type:Int
Method addObject(o:AdjType)
If _type=aList.length Then grow()
aList[_type]=o
'o.o_Index = _type
_type:+1
End Method
Method removeObject(o:AdjType)
If o._Type > aList.length-1 Then Return
aList[_type]._type = o._type
aList[o._type] = aList[_type]
_type:-1
EndMethod
Method addChild(i:Int)
children = children[..children.length+1]
children[children.length-1] = i
EndMethod
Method setParent(p:Int)
p_type = p
EndMethod
Method grow()
aList = aList[..aList.length+10]
EndMethod
EndType
'Used with For...EachIn to do a bredth 1st traversal (all siblings are looked at before moving on to children)
Type AdjIterator
Field n_Index:Int 'index of the start of the iterator
Field o_Index:Int 'counter in theLists array to hold the iterator's place
Field theLists:AdjNode[] 'the list of nodes being looped through
Field que:intQue 'the int que to keep track of lists to check
Method New()
que = New intQue
EndMethod
'get the list to loop through and set up a que to do a bredth first traversal
Method Init(tLists:AdjNode[],loopStart:Int)
theLists = tLists
n_Index = loopStart
For Local i:Int = 0 To theLists[n_Index].children.length-1
que.push(theLists[n_Index].children[i])
Next
EndMethod
'make an iterator
Function Create:AdjIterator(tLists:AdjNode[],loopStart:Int)
Local tAI:AdjIterator = New AdjIterator
tAI.Init(tLists,loopStart)
Return tAI
EndFunction
Method HasNext:Int()
If o_Index < theLists[n_Index].aList.length Then Return True
Repeat
If Not que.isEmpty() Then
n_Index = que.pop()
o_Index = 0
For Local i:Int = 0 To theLists[n_Index].children.length-1
que.push(theLists[n_Index].children[i])
Next
If theLists[n_Index].aList.length > o_Index Then Return True
Else
Return False
End If
Forever
EndMethod
Method NextObject:Object()
o_Index:+1
Return theLists[n_Index].aList[o_Index-1]
EndMethod
EndType
'Integer que use internally by the iterator To keep track of child lists to loop through
Type intQue
Field que:Int[]
Field front:Int
Field back:Int
Field num:Int
Method New()
que = que[..5]
EndMethod
Method push(i:Int)
If isFull() Then Return
que[back]=i
back:+1
back:*(back < que.length)
EndMethod
Method pop:Int()
If isEmpty() Then Return 0
If front = que.length-1 Then
front = 0
Return que[que.length-1]
Else
front:+1
Return que[front-1]
End If
End Method
Method isEmpty:Int()
If (front = back) And (num = 0) Then
shrink()
Return True
End If
Return False
EndMethod
Method isFull:Int()
If (front = back) And (num <> 0) Then grow()
Return False
EndMethod
Method grow()
que = que[..que.length+5]
EndMethod
Method shrink()
que = que[..5]
EndMethod
EndType
This is a commented example
SuperStrict
Framework brl.Basic
Import "AdjList.bmx"
'Mix up the numbers to test that order doesn't matter
Const TYPE_A:Int = 0
Const TYPE_B:Int = 7
Const TYPE_C:Int = 3
Const TYPE_D:Int = 2
Const TYPE_E:Int = 8
Const TYPE_F_1:Int = 6
Const TYPE_F_2:Int = 5
Const TYPE_F_3:Int = 1
Const TYPE_G:Int = 4
'Our base type for this list
Type A Extends AdjType
Global List:AdjList 'the only list object
'this returns the list
'Basicly hard code the type const
'This function is unnessecary if you make your consts match your type names i.e. TYPE_A ~= A etc. Why? show you later
'If you can do without it you'll minimize the stuff you have to put in every type to a single method call to Init(...)
Function ForList:AdjList()
List.setLoopStart(TYPE_A)
Return List
EndFunction
'------- Application Specific ---------
Field xx:Int,yy:Int 'x,y coords? why not
'Function to initialize out object
'this function can be application specific
'the type and parent and passed in but this could be hard coded in a New() Method
Function Create:A(t:Int,p:Int,tx:Int,ty:Int)
Local temp:A = New A
'---- Call this -----
temp.Init(t,p)
'--------------------
temp.xx = tx
temp.yy = ty
List.addObject(temp) 'Optional, but we made the list for a reason...
Return temp
End Function
EndType
Type B Extends A
Function Create:B(t:Int,p:Int,tx:Int,ty:Int)
Local temp:B = New B
temp.Init(t,p) 'only method that must be called within our initialization
'x and y flip in B
temp.xx = ty
temp.yy = tx
List.addObject(temp)
Return temp
End Function
Function ForList:AdjList()
List.setLoopStart(TYPE_B)
Return List
EndFunction
EndType
Type C Extends A
Field name:String 'lets add something to C and his children
Function Create:C(t:Int,p:Int,tx:Int,ty:Int)
Local temp:C = New C
temp.Init(t,p)
temp.xx = tx
temp.yy = ty
List.addObject(temp)
Return temp
End Function
Method setName(n:String)
name = n
EndMethod
Function ForList:AdjList()
List.setLoopStart(TYPE_C)
Return List
EndFunction
End Type
Type D Extends C
Function Create:D(t:Int,p:Int,tx:Int,ty:Int)
Local temp:D = New D
temp.Init(t,p)
temp.xx = tx
temp.yy = ty
List.addObject(temp)
Return temp
End Function
Method setName(n:String)
name = "D"+n+"D"
EndMethod
Function ForList:AdjList()
List.setLoopStart(TYPE_D)
Return List
EndFunction
End Type
Type E Extends C
Method New()
Init(TYPE_E,TYPE_C)
EndMethod
Function Create:E(t:Int,p:Int,tx:Int,ty:Int)
Local temp:E = New E
'temp.Init(t,p) 'only method that must be called within our initialization
'we hard coded them into this type for demo purposes
temp.xx = tx
temp.yy = ty
List.addObject(temp)
Return temp
End Function
Method setName(n:String)
name = "EEEEEEE- "+n+" -EEEEEEEEE"
EndMethod
Function ForList:AdjList()
List.setLoopStart(TYPE_E)
Return List
EndFunction
End Type
'With this type I will show that the list can be purely logical
'In other words you could have one type and implement a hierarchy logically
'This is why you may not want to hard code _Type and p_Type in your objects
'Has to extend C since it's the furthest up object that can represent the most of it's data
'I wouldn't mix my types like this where one type has 3 different 'types' in the list and each type is a truely unique type
Type F Extends C
Field whichF:Int 'were's gonna have 3 f types
Function Create:F(t:Int,p:Int,tx:Int,ty:Int)
Local temp:F = New F
temp.Init(t,p) 'only method that must be called within our initialization
temp.xx = tx
temp.yy = ty
List.addObject(temp)
Return temp
End Function
Method setName(n:String)
name = "F"+whichF+" :-: "+n 'more different
EndMethod
Method setF(f:Int)
whichF = f
EndMethod
'F could be placed any where in the tree under C so we'll leave this and use another method to get only our F and lower
Function ForList:AdjList()
List.setLoopStart(TYPE_C)
Return List
EndFunction
End Type
'Logically child of F_2 in our list
Type G Extends C
Function Create:G(t:Int,p:Int,tx:Int,ty:Int)
Local temp:G = New G
temp.Init(t,p) 'only method that must be called within our initialization
temp.xx = tx
temp.yy = ty
List.addObject(temp)
Return temp
End Function
Method setName(n:String)
name = "Jigga "+n
EndMethod
Function ForList:AdjList()
List.setLoopStart(TYPE_G)
Return List
EndFunction
EndType
'First make the list
A.List = AdjList.Create(9)
'Now lets setup our hierarchy
'This could go in a function in Type A or the root of any number of such structures
'This should be set and not changed at all
A.List.addRelationship(TYPE_A,TYPE_B)
A.List.addRelationship(TYPE_A,TYPE_C)
A.List.addRelationship(TYPE_C,TYPE_D)
A.List.addRelationship(TYPE_C,TYPE_E)
A.List.addRelationship(TYPE_E,TYPE_F_1)
A.List.addRelationship(TYPE_D,TYPE_F_2)
A.List.addRelationship(TYPE_F_1,TYPE_F_3)
A.List.addRelationship(TYPE_F_2,TYPE_G)
Rem
So this is our hierarchy \ tree \ adjacency list
A
/ \
B C
/ \
D E
| |
F2 F1
| |
G F3
EndRem
'Now we can make some objects
Local aa:A = A.Create(TYPE_A,-1,123,456)
Local bb:B = B.Create(TYPE_B,TYPE_A,123,456)
bb = B.Create(TYPE_B,TYPE_A,123,456)
Local cc:C = C.Create(TYPE_C,TYPE_A,123,456); cc.setName("C")
Local dd:D = D.Create(TYPE_D,TYPE_C,123,456); dd.setName("D")
Local ee:E = E.Create(TYPE_E,TYPE_C,123,456); ee.setName("E")
ee = E.Create(TYPE_E,TYPE_C,123,456); ee.setName("E")
Local ff:F = F.Create(TYPE_F_1,TYPE_E,123,456); ff.setF(1); ff.setName("F")
ff = F.Create(TYPE_F_1,TYPE_E,123,456); ff.setF(1); ff.setName("F")
ff = F.Create(TYPE_F_2,TYPE_D,123,456); ff.setF(2); ff.setName("F")
ff = F.Create(TYPE_F_2,TYPE_D,123,456); ff.setF(2); ff.setName("F")
ff = F.Create(TYPE_F_3,TYPE_F_1,123,456); ff.setF(3); ff.setName("F")
ff = F.Create(TYPE_F_3,TYPE_F_1,123,456); ff.setF(3); ff.setName("F")
Local gg:G = G.Create(TYPE_G,TYPE_F_2,987,654); gg.setName("G")
gg = G.Create(TYPE_G,TYPE_F_2,987,654); gg.setName("G")
'And now we can test them
'Each loop should print itself and it's children
Print "---A---"
For aa = EachIn A.ForList()
Print aa._Type+", "+aa.p_Type+", "+"("+aa.xx+", "+aa.yy+")"
Next
Print
Print "---B---"
For bb = EachIn B.ForList()
Print bb._Type+", "+bb.p_Type+", "+"("+bb.xx+", "+bb.yy+")"
Next
Print
Print "---C---"
For cc = EachIn C.ForList()
Print cc._Type+", "+cc.p_Type+", "+"("+cc.xx+", "+cc.yy+")"+", "+cc.name
Next
'from here we have to use c becuase logical parents don't match technical parents (F extends C not D or E and G extends C not F)
Print
Print "---D---"
For cc = EachIn D.ForList()
Print cc._Type+", "+cc.p_Type+", "+"("+cc.xx+", "+dd.yy+")"+", "+cc.name
Next
Print
Print "---E---"
For cc = EachIn E.ForList()
Print cc._Type+", "+cc.p_Type+", "+"("+cc.xx+", "+cc.yy+")"+", "+cc.name
Next
Print
Print "---F_1---"
'if we know the corresponding const we can get our list this way instead of hard coding it
'this way we could reduce the amount of code by not having a function for every type
'since we're already adding 2 fields to every type this seems like a good idea to me
For cc = EachIn F.List.From(TYPE_F_1)
Print cc._Type+", "+cc.p_Type+", "+"("+cc.xx+", "+cc.yy+")"+", "+cc.name
Next
Print
Print "---F_2---"
For cc = EachIn F.List.From(TYPE_F_2)
Print cc._Type+", "+cc.p_Type+", "+"("+cc.xx+", "+cc.yy+")"+", "+cc.name
Next
Print
Print "---F_3---"
For cc = EachIn F.List.From(TYPE_F_3)
Print cc._Type+", "+cc.p_Type+", "+"("+cc.xx+", "+cc.yy+")"+", "+cc.name
Next
Print
Print "---G---"
For cc = EachIn G.ForList()
Print cc._Type+", "+cc.p_Type+", "+"("+cc.xx+", "+cc.yy+")"+", "+cc.name
Next