BRiX
Advanced Computing Environment
Hosted by SourceForge
brix-os project page

Previous: Strings ----- Up: Contents ----- Next: Functions

Lists

show notes
Features that need to be added to the page or ideas that haven't been thought out.
  • rename empty_list_error exception?

The List type represents a linked collection of objects with a common parent. The parentheses tuple literal defaults to the List type when not annotated or consumed by a constructor. Unlike brackets and braces, parentheses can not be used as default types with less than two elements. This is overcome by using undefined tuple elements to declare empty and single element lists. The undefined elements are also used to switch between single and double linked lists.

	a := (,)	// single link, empty (Object)
	b := (1,)	// single link, one element (Int)
	c := (1,2,3)	// single link, three elements (Int)
	d := (,,)	// double link, empty (Object)
	e := (,1)	// double link, one element (Int)
	f := (,1,2,3)	// double link, three elements (Int)

	// create an empty single-link list of Ints
	a:List of Int = (,)
	b := (List of Int).new()
	c := (,):List of Int
	// create an empty double-link list of Ints
	d:List of Int = (,,)

	a.push(1)		// push item to list
	value := a.pop()	// pop item from list

Usage

links List of type
  • links -- optional `single or `double
  • of -- required syntax when type is given
  • type -- element type

Interfaces

Slots

Methods

Properties

Operators


Sample Definition

	ListNode = deftype (T:Type) {
	  constructor (data:T, `nullable next:Self)
	  slot next = next
	  slot data = data
	}

	DoubleListNode = deftype (T:Type) {
	  constructor (data:T, `nullable prev:Self, `nullable next:Self)
	  slot prev = prev
	  slot next = next
	  slot data = data
	}

	`export-root List = deftype `open (
	        `prefix-flag links:Enum(single double) = `single,
	        `keyword of `from-constructor T:Type = Object)
	{
	  tetra.compiler.set_as_default_tuple(`paren, 2, `no-keys)
	  inherit collection_interface
	  constructor (elements:Object ...) -> {
	    // create ListNodes for each element
	    ...
	  }
	  `private `nullable slot head:ListNode(T) = null
	  `private `nullable slot tail:ListNode(T) = null
	  method push(value:T) {
	    if((typeOf self).links == `double)
	      self.tail = (value, self.tail, null) : DoubleListNode((typeOf self).T)
	    else
	      self.tail = (value, null) : ListNode((typeOf self).T)
	    if(null? self.head) self.head = self.tail
	  }
	  method pop() -> T {
	    if(null? self.tail) throw empty_list_error
	    node := self.tail
	    if((typeOf self).links == `double) {
	      node.prev.next = null
	      self.tail = node.prev
	    } else let n = self.head -> {
	      while(n.next !== node) n = n.next
	      n.next = null
	      self.tail = prev
	    }
	    value := node.data
	    system.gc.releaseObject(node, `shallow) // explicit de-allocation
	    return value
	  }
	  method first() -> T {
	    // return value of first node
	    return self.head.data
	  }
	  method last() -> T {
	    // return value of last node
	    ...
	  }
	  new = def () return tetra.construct_object() // create an empty list
	  makeIterator = def (`ref l:Self, reversed:Boolean)
	    return (l, reversed) : deftype (T:Type of List) {
	      inherit collection_iterator_interface(T.T)

	      ...

	    }(typeOf l)
	  isEmpty = def (l:Self) return null? l.head
	}

The definition of List uses the restricted system.gc.releaseObject function to explicitly free unused memory. This prevents the module from being compiled by normal users and should only be used by system and compiler related code. The List type is part of the compiler framework and its use is an acceptable optimization.

The tetra.compiler.set_as_default_tuple extension allows the type to be used as a literal.

Previous: Strings ----- Up: Contents ----- Next: Functions